Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A colleague posted this on a whiteboard (as a brain-teaser I guess):


A $\rightarrow$ B;
B $\rightarrow$ C;
AD $\rightarrow$ E;
BE $\rightarrow$ C;
BF $\rightarrow$ D;
AC $\rightarrow$ F

What is the minimum set I need to determine A, B, C, D, E, and F?


I'm not interested in help solving the problem. I'd just like to know the general domain of the problem because it's not clear to me. It probably is clear to a mathematics community.

For example, does it deal with set theory, or logic? Or some other area of math?

share|improve this question
2  
If you had some notion of what $\to$ means and what juxtaposing two symbols means, then it could be viewed as a group-theoretic problem. –  Arkamis Dec 19 '12 at 19:59
1  
Ask your colleague. –  Chris Eagle Dec 21 '12 at 0:20
2  
Two upvotes, one favorite, two insightful answers, and yet closed as not a real question. I think the answerers understood exactly what I was asking, and provided great answers. But five people can stop the parade. Stack Exchange at its finest. –  John Dec 21 '12 at 19:43
    
I dont quite follow. In order to determine A, you need not B. In order to determine C you need B. What is the resolution? –  Adam Dec 3 '13 at 1:54
    
@Adam I have no idea. I probably should just delete the question. I just wanted at the time to see if I could come up with the correct answer without asking my colleagues about the notation. –  John Dec 3 '13 at 1:56

2 Answers 2

up vote 2 down vote accepted

I first interpreted this as a dependency graph, with $pq\to r$ meaning that if you know $p$ and $q$, then you can find $r$, or that tasks $p$ and $q$ are prerequisites for $r$, or something of that sort.

Understood this way, then it is a problem of graph theory, to find the source vertices of the directed graph determined by the given relations. There is one source, $A$, because from $A$ we can get to $B$ and to $C$; then from $AC$ we get to $F$; from $BF$ we get to $D$; and from $AD$ we get to $E$.

But I have no way to be sure that this is the intended interpretation. It might mean something completely different. For example, $pq\to r$ might mean that if $p$ and $q$ are riding in the same taxi then $r$ cannot ride there too, and the question is to find the minimum required number of taxis; then the answer is very different. Or it might be as Jonathan Christensen says, which is different again. Or perhaps $pq\to r$ means that whenever you have letters $p$ and $q$ adjacent in a word, you can replace them with $r$, and the question is to find the number of English words that transform into other English words.

Without more explanation from your colleague, I don't think the question can be reasonably answered.

share|improve this answer
    
I think that the question at the end of the problem just about rules out the taxi interpretation and the word interpretation: the questions don’t fit. Jonathan’s interpretation is essentially the same as the dependency graph interpretation: just substitute ‘if $p$ and $q$ are true, then so is $r$’ for ‘if you know $p$ and $q$, then you can find $r$’. –  Brian M. Scott Dec 20 '12 at 2:48
1  
Thanks for the answer. Unfortunately the close police have struck. Merry Christmas! –  John Dec 21 '12 at 23:17

It's logic. A-F are either true or false, and the question is which ones you need to know (at a minimum) to determine the truth of all six of them.

Edit: AB means "A and B," the arrow is implication.

share|improve this answer
4  
How do you know? –  MJD Dec 19 '12 at 22:10
    
Thanks for the answer. It's too bad that people closing it cannot see that this answered my question. –  John Dec 21 '12 at 23:17
    
+1: Excellent inference. –  copper.hat Dec 19 '13 at 5:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.