Computer Science 0
Part of the Oxford MAT Livestream.
MAT questions
MAT 2011 Q6
Alice, Bob, Charlie, and Diane are playing together when one of them breaks a precious vase. They all know who broke the vase. When questioned they make the following statements:
\begin{align*}
\text{Alice}:&\quad\text{It was Bob.}\\
\text{Bob}:&\quad\text{It was Diane.}\\
\text{Charlie}:&\quad\text{It was not me.}\\
\text{Diane}:&\quad\text{What Bob says is wrong.}
\end{align*}
Each statement is either true or false.
(i) Explain why at least one of the four must be lying.
(ii) Explain why at least one of them must be telling the truth.
(iii) Let us suppose that exactly one of the four is lying, so the other three are telling the truth. Who is lying? Who did break the vase? Explain your answer.
(iv) Let us now suppose that exactly one of the four is telling the truth, so the other three are lying. Who is telling the truth? Who did break the vase? Explain your answer.
(v) Let us now suppose that two of the statements are true and two are false. List the people who might now have broken the vase. Justify your answers.
(vi) Hence show that if we don't know how many of the four statements are true, then any one of the four could have broken the vase.
Hints
(i) We could check all the four possibilities for which of them broke the vase. In fact, this strategy works well for all the parts of this question! For a quicker solution though, notice that two people can't both be telling the truth if their statements are inconsistent.
(ii) Charlie's statement seems pretty "likely" to be true (not a proof!). If they're not telling the truth, is anyone else telling the truth?
(iii) We know from the first part that at least one of A and B is lying. If exactly one of the four is lying, then either A or B is telling the truth. Check those two cases.
(iv) From part (ii), we know that at least one of B or D is telling the truth. If exactly one of them is telling the truth, the other must be lying.
(v) There are only four possibilities for the person who broke the vase, and you've already eliminated a couple of possibilities in the previous parts of this question. Who's left?
(vi) Don't overthink it, look back at what you've done across the previous parts.
Extension
[Just for fun, not part of the MAT question]
- Overthink the last part. Is it always true that if have true/false statements from each of $n$ suspects and we don't know how many of the statements are true, then we cannot deduce anything about who broke the vase?
MAT 2012 Q6
Alice, Bob, and Charlie are well-known expert logicians; they always tell the truth.
They are sat in a row, as illustrated above. In each of the scenarios below, their father puts a red or blue hat on each of their heads. Alice can see Bob's and Charlie's hats, but not her own; Bob can see only Charlie's hat; Charlie can see none of the hats. All three of them are aware of this arrangement.
(i) Their father puts a hat on each of their heads and says "Each of your hats is either red or blue. At least one of you has a red hat." Alice then says "I know the colour of my hat." What colour is each person's hat? Explain your answer.
(ii) Their father puts a new hat on each of their heads and again says: "Each of your hats is either red or blue. At least one of you has a red hat." Alice then says "I don't know the colour of my hat." Bob then says "I don't know the colour of my hat." What colour is Charlie's hat? Explain your answer.
(iii) Their father puts a new hat on each of their heads and says: "Each of your hats is either red or blue. At least one of you has a red hat, and at least one of you has a blue hat." Alice says "I know the colour of my hat." Bob then says "Mine is red." What colour is each person's hat? Explain your answer.
(iv) Their father puts a new hat on each of their heads and says: "Each of your hats is either red or blue. At least one of you has a red hat, and at least one of you has a blue hat." Alice then says "I don't know the colour of my hat." Bob then says "My hat is red". What colour is Charlie's hat? Explain your answer.
(v) Their father puts a new hat on each of their heads and says: "Each of your hats is either red or blue. Two of you who are seated adjacently both have red hats." Alice then says "I don't know the colour of my hat." What colour is Charlie's hat? Explain your answer.
Hints
(i) Consider the four possibilities for what Alice can see. Alice is an expert logician, so we know that they are able to do this careful consideration too. Alice can deduce the colour of their hat. Eve though we don't currently know the colour of Alice's hat, that tells us something about the information that Alice had and processed.
(ii) Compare and contrast this situation with what happened in the previous part. Alice's statement has changed. Despite being an expert logician, Alice is unable to deduce the colour of their own hat. What does that tell you?
(iii) Once again, consider the four possibilities for what Alice can see. Some of them are inconsistent with Alice's statement. Can you see which ones?
Now Bob is somehow able to deduce the colour of their own hat. What does that tell you about the possibilities?
(iv) Why doesn't Alice have enough information to deduce their own hat colour? Remember, Alice is an expert logician, so if they have enough information to deduce their own hat colour then they will do so!
Alice is a well-known expert logician, so Bob knows that Alice is an expert logician. This means that when Bob hears that Alice can't deduce their own hat colour, it's not because Alice isn't clever enough to process the information available to them. That tells Bob something about the information that Alice had.
(v) How many possibilities are there? If you need to, list all eight for the possible red/blue hat arrangements, and decide how many of them satisfy the condition that the father states.
Extension
[Just for fun, not part of the MAT question]
- There are a billion well-known expert logicians sat in a row (as in the diagram, but with a billion people instead of three). Everyone is either wearing a red hat or a blue hat. Each logician can only see the hats in front of them. Everyone is told that there is at least one red hat. One by one, starting at the back, each logician must say whether they know their hat colour (either stating "I know the colour of my hat" or "I do not know the colour of my hat"). What happens?
MAT 2013 Q6
Alice, Bob, and Charlie are well-known expert logicians; they always tell the truth.
In each of the scenarios below, Charlie writes a whole number of Alice and Bob's foreheads. The difference between the two numbers is one: either Alice's number is one larger than Bob's, or Bob's number is one larger than Alice's. Each of Alice and Bob can see the number on the other's forehead, but can't see their own number.
(i) Charlie writes a number on Alice and Bob's foreheads, and says "Each of your numbers is at least 1. The difference between the numbers is 1."
Alice then says "I know my number."
Explain why Alice's number must be 2. What is Bob's number?
(ii) Charlie now writes new numbers on their foreheads, and says "Each of your numbers is between 1 and 10 inclusive. The difference between the numbers is 1. Alice's number is a prime." (A prime number is a number greater than 1 that is divisible only by 1 and itself.)
Alice then says "I don't know my number."
Bob then says "I don't know my number."
What is Alice's number? Explain your answer.
(iii) Charlie now writes new numbers on their foreheads, and says "Each of your numbers is between 1 and 10 inclusive. The difference between the numbers is 1."
Alice then says "I don't know my number. Is my number a square number?"
Charlie then says "If I told you that, you would know your number."
Bob then says "I don't know my number."
What is Alice's number? Explain your answer.
Hints
(i) What would happen if the number on Bob's forehead was, say, 37? What could the number on Alice's forehead be? Would Alice be able to deduce their own number? What property of the number 37 does your argument rely on?
(ii) First use a version of the idea you had in part (i) to eliminate two possibilities for the number on Bob's forehead.
The primes between 1 and 10 inclusive are 2, 3, 5, and 7.
Alice is unable to deduce their number despite being an expert logician. What does that tell you?
(iii) Note that Charlie's statement is essentially "good question!". Alice has asked a good question. What made it a good question? What are the possibilities for the number Alice is looking at?
Bob is confused. Poor Bob. It's not for lack of trying; Bob is an expert logician. And it's not for lack of trust; Bob knows that Alice and Charlie are expert logicians, so their conversation must have been based on correct facts about primes and so on. What's going on?
Extension
[Just for fun, not part of the MAT question]
- Charlie now writes new numbers on their foreheads, and says "Each of your numbers is between 1 and 16 inclusive. The difference between the numbers is 1."
Alice then says "I don't know my number. Is my number a prime number?"
Charlie then says "If I told you that, you would know your number."
Bob then says "I don't know my number."
What is Alice's number? Explain your answer.
MAT 2014 Q6
Alice plays a game with her friends Sam and Pam. In each game Alice chooses two integers $x$ and $y$ with $1 \le x \le y$. She whispers the sum $x+y$ to Sam, and the product $x \times y$ to Pam, so that neither knows what the other was told. Sam and Pam then have to try to work out what the numbers are. Sam and Pam are well-known expert logicians.
(i) In the first game, Pam says "I know $x$ and $y$.''
What can we deduce about the values of $x$ and $y$? Explain your answer.
(ii) In the second game, Pam says "I don't know what $x$ and $y$ are.''
Sam then says "I know $x$ and $y$.''
Suppose the sum is 4. What are $x$ and $y$? Explain your answer.
(iii) In the third game, Pam says "I don't know what $x$ and $y$ are.''
Sam then says "I don't know what $x$ and $y$ are.''
Pam then says "I now know $x$ and $y$.''
Suppose the product is 4. What are $x$ and $y$? Explain your answer.
(iv) In the fourth game, Pam says "I don't know what $x$ and $y$ are.''
Sam then says "I already knew that.''
Pam then says "I now know $x$ and $y$.''
Suppose the product is 8. What are $x$ and $y$? Explain your answer.
(v) Finally, in the fifth game, Pam says "I don't know what $x$ and $y$ are.''
Sam then says "I don't know what $x$ and $y$ are.''
Pam then says "I don't know what $x$ and $y$ are.''
Sam then says "I now know $x$ and $y$.''
Suppose the sum is 5. What are $x$ and $y$? Explain your answer.
Hints
(i) Note that $x\leq y$ so it's enough for Pam to deduce the set of numbers that have been multiplied, knowing that the smaller number is $x$ (or if they're the same, it doesn't matter which is $x$ and which is $y$). The numbers $x$ and $y$ are factors of the product. Pam somehow knows which factors have been multiplied; that's a bit weird.
(ii) Pam's statement at the top tells us that we're not in the case described in the previous part.
Note that we're told the sum. What are the possibilities for $x$ and $y$? Also note that Pam doesn't know this sum!
(iii) Note that we're told the product. What are the possibilities for $x$ and $y$? Also note that Sam doesn't know this product!
(iv) Sam says that they already knew something, which means that as soon as they heard the sum they knew that, out of all the possibilities for $x$ and $y$ and the product, Pam would be unable to deduce the numbers. The product is 8. What could the numbers be, and why is Sam so confident?
(v) The sum is 5 so there are not many possibilities for the $x$ and $y$. Work through each case, pretending to be either Pam or Sam. What product or sum are they told, and what cases are they considering at each stage of the conversation? Do their statements make sense? If not, move to the next case, or read it from the other person's point of view.