3
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – Emily
    Dec 19, 2012 at 19:59
  • 1
    $\begingroup$ Ask your colleague. $\endgroup$ Dec 21, 2012 at 0:20
  • $\begingroup$ 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? $\endgroup$
    – Adam
    Dec 3, 2013 at 1:54
  • $\begingroup$ @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. $\endgroup$
    – John
    Dec 3, 2013 at 1:56

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
1
  • 4
    $\begingroup$ How do you know? $\endgroup$
    – MJD
    Dec 19, 2012 at 22:10
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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$’. $\endgroup$ Dec 20, 2012 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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