Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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. – Emily Dec 19 '12 at 19:59
Ask your colleague. – Chris Eagle Dec 21 '12 at 0:20
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
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|cite|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

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|cite|improve this answer
How do you know? – MJD Dec 19 '12 at 22:10

Your Answer


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.