Computer Science 0 Solutions

MAT 2011 Q6

(i) Alice and Bob can't both be telling the truth (it wasn't both Bob and Diane who broke the vase)

Alternatively, Bob and Diane directly contradict each other, so one or more of them is lying.

(ii) Either it was Diane or it wasn't; so one of Bob or Diane is telling the truth.

Alternatively, either it was Charlie or it wasn't; so one of Charlie or Diane is telling the truth.

(iii) Only one of them is lying, so either Alice or Bob is telling the truth. If Bob is telling the truth then Diane broke the vase, so Diane and Alice are both lying... but we've been told that exactly one of them is lying. So instead, Alice is telling the truth and Bob broke the vase (just to make sure, check that Charlie and Diane are both telling the truth, just to make sure)

(iv) Either Bob or Diane is the one telling the truth (their statements directly contradict each other). If Bob is telling the truth then it was Diane, but then Charlie would be telling the truth too (and we've been told that exactly one of them is telling the truth). So instead it's Diane who's telling the truth, and what Bob says (accusing Diane) really is wrong. So who broke the vase? We know that Alice and Charlie are both lying, so in particular Charlie is lying, so Charlie broke the vase.

(v) Perhaps Alice or Diane broke the vase (not Bob or Charlie because we saw in the previous two parts that if Bob broke the vase then exactly three of them are telling the truth, or if Charlie broke the vase then exactly one of them is telling the truth). Check that if Alice broke the vase then Alice and Bob are lying, but Charlie and Diane are telling the truth. Check that if Diane broke the vase then Alice is lying, Bob is telling the truth, Charlie is telling the truth and Diane is lying. In either case, exactly two of them are telling the truth.

(vi) Across the previous three parts we have shown that if 1 or 2 or 3 of the statements are true, then either Alice or Bob or Charlie or Diane (any of them!) could have broken the vase. If we don't know how many of the statements are true, then any of the four of them could have broken the vase.

Extension

Consider the $n$ possibilities for who broke the vase. In each case, some number of the statements turn out to be true. But if it's possible that any number of the statements are true, then that includes all the possibilities under consideration.

You should still think about this; can we always decide if statements are true or false?

Daisy pointed out on the livestream that the argument above is incorrect if $n=1$. Can you see why?

MAT 2012 Q6

(i) If Alice can see any red hats, then they would not be able to deduce their own hat colour (either possibility would give combination of hats satisfying the conditions). But Alice can deduce their hat colour, so Alice must see two blue hats. Since there is a red hat, we can deduce that Alice has a red hat. The hats go RBB.

(ii) Alice cannot see two blue hats otherwise (by the previous part) they would know their hat colour; so they can see at least one red hat. Even with this information, Bob is unable to deduce their own hat colour, so Bob cannot see a blue hat. So Charlie has a red hat.

(iii) Alice can see matching hats (if Alice could see one of each then they wouldn't be able to deduce their own hat colour). Bob hears this and sees Charlie's hat, so Bob knows that their own hat will match. We hear Bob say red, so both Bob and Charlie have red hats. Alice's is therefore blue (there is at least one of each). The hats go BRR.

(iv) Alice can see one of each colour, otherwise Alice would know that their hat was whatever colour they couldn't see (by the previous part). Bob hears this, and must see a blue hat to conclude that their hat is red. So Charlie has a blue hat, Bob has a red hat, and nobody except the father knows the colour of Alice's hat. The hats go RBR or BBR.

(v) There are only three possibilities; all red RRR, or BRR, or RRB. If Alice can see RB then we must be in the RRB case, but Alice doesn't know the colour of their own hat. So we're in one of the other cases; RRR or BRR. Charlie's hat is red.

Extension

If the first logician is wearing a red hat, and they're the only one wearing a red hat, then they immediately announce that they know their hat colour. This is extremely unusual and, sensing the occasion, all the other logicians are able to deduce that they're wearing blue hats and they're part of something really special.

However, if the first logician can see any red hats then they must admit that they cannot deduce their own hat colour. In fact, any logician who can see at least one red hat must similarly admit that they do not know their own hat colour. Perhaps there are $n+1$ red hats; the $n$ that I can see plus mine, or perhaps there are $n$ red hats; either would be equally confusing for the poor folk behind me.

Out of the logicians wearing a red hat, the front-most one gets to do something clever. This particular logician can only see blue hats, but they hear the person behind them admit that they don't know their own hat colour. "Hang on," thinks this front-most red-hatted logician, "if my hat is blue (like all the hats I can see), then the person behind me should really have realised that something was up. So my hat is red." They announce that they know their hat colour. The logicians in front of them (if there are any) realise what has happened and announce that they each know their hat colour too.

MAT 2013 Q6

(i) If the number on Bob's head isn't 1, then Alice wouldn't know whether their number was one more or one less than Bob's. But somehow Alice can deduce their own number, so it must be the case that Alice sees 1 and knows that their number is 2. Charlie should have picked larger numbers if they wanted this game to be more mysterious!

(ii) The primes in this range are 2, 3, 5, 7. So Bob's number must be (1 or 3) or (2 or 4) or (4 or 6) or (6 or 8). Note that if Alice sees 1 or 3 or 2 or 8 then Alice could deduce which case we're in; those numbers only appear once on my list. But Alice cannot deduce their number, so Alice must see 4 or 6. That's a big clue for Bob, but Bob is somehow unable to deduce their own number from those two possibilities. The only way Bob could still be confused is if the number on Alice's head is 5. (Alice and Charlie know what Bob's number is, but Bob doesn't, and neither do we).

(iii) To start with, Alice cannot see the number 1 or the number 10, otherwise the information that the difference is 1 would reveal Alice's number to Alice, like in part (i).

Alice then talks to Charlie. The square numbers in this range are 1 and 4 and 9. It must be the case that Alice can see a number which is next to one square number and next to one not-a-square number. Checking the possibilities from 2 to 9, we conclude that Alice can perhaps see 2 or 3 or 5 or 8 (but not 4 or 6 or 7 or 9, each of which is next to two not-a-square numbers).

Bob hears all of this and now knows that Bob's number is 2 or 3 or 5 or 8. Bob can also see Alice's number. Bob is somehow unable to determine Bob's number. It must be the case that Bob sees precisely the number 4 on Alice's forehead, the only number which is between two options on the list of possibilities for Bob's number. So Alice's number is 4. I can't help Bob; I don't know their number either.

Extension

Alice can't see 1 or 16. Perhaps Alice sees 3, or 8, or 10, or 14. Bob is confused, so Bob sees 9.

MAT 2014 Q6

(i) How is Pam able to state the factors of the number so easily? The only way that this makes sense is if the product has no non-trivial factors, which only happens if $x=1$ and $y$ is a prime. So Pam knows that $x=1$ and $y$ is the number Alice whispered to them.

(ii) In this game, Pam reveals that the product is not prime. Sam has heard the sum 4, so the possibilities are just $x=1$ and $y=3$, or $x=2$ and $y=2$. It must be the second case, because the product is not prime. So $x=2$ and $y=2$.

(iii) We're told that the product is 4, which is not prime, which is why Pam says that they don't know $x$ and $y$. The possibilities are $x=1$ and $y=4$, or $x=2$ and $y=2$.

Sam therefore either receives the sum 5 or 4. If the sum is 4 then we're in the previous case where Pam didn't know $x$ and $y$, the sum was 4, and Sam could deduce the numbers. This time, Sam is unable to deduce $x$ and $y$, because the sum is 5. The numbers might be $x=1$ and $y=4$, or $x=2$ and $y=3$. In either case the product is not prime, so Sam is unable to say which case we're in.

This is enough to reveal to Pam that the sum is not 4 (otherwise we'd be in the case we had in part (ii)), so the sum is 5. So the numbers are $x=1$ and $y=4$.

(iv) We're told that the product is 8, so the numbers are either $x=1$ and $y=8$, or $x=2$ and $y=4$. Sam is told the sum, which must be either 9 or 6. How did Sam already know that Pam wouldn't have a prime product to deal with? If the sum were 6 then the numbers might have been 1 and 5, so Sam wouldn't have been able to make this extraordinary claim. So the sum was 9, and Sam knew that the product was either $1\times8$ or $2\times 7$ or $3\times 6$ or $4\times 5$, none of which is prime.

Now that we know the sum is 9 (and Pam knows this too, so Pam deduces $x$ and $y$), we know that the numbers are $x=1$ and $y=8$.

(v) The sum is 5, so there are only two possibilities, $x=1$ and $y=4$, or $x=2$ and $y=3$. The product is 4 in the first case and 6 in the second case. But we saw in part (iii) that if the product is 4 then, after the two initial statements, Pam can deduce $x$ and $y$. So here it must be the case that $x=2$ and $y=3$.

Let's check this. Pam gets product 6 and considers $x=1$ and $y=6$, or $x=2$ and $y=3$. Sam gets the sum 5 and considers $x=1$ and $y=4$, or $x=2$ and $y=3$. Pam's first statement doesn't help Sam. So Sam announces that they do not know what $x$ and $y$ are. Pam now reconsiders their cases. If $x=1$ and $y=6$ then Sam would have the sum 7 and would be considering $x=3$ and $y=4$, so Sam would still be unsure even with the news that Pam doesn't know the numbers. In both of Pam's cases, it makes sense for Sam to still be unsure. Pam announces that they don't know the numbers. Sam now reconsiders their cases. If $x=1$ and $y=4$ then, by part (iii), Pam would just have worked out the numbers. So it's the other case that's true; $x=2$ and $y=3$.