22
$\begingroup$

This feels like it should be a common puzzle, but I haven't found anything exactly like it searching online, so here goes. Apologies if it's a duplicate.

Three logicians, person 1, 2, and 3, along with a host, are playing a game. The host places one of three hats, each with a positive integer label A, B, or C, on the head of each player. All the player's know at the start is that A = B + C. They do not know who is wearing A, B, or C. The players can look at each other's hats, but they cannot see their own hat. The host asks each person in order(starting with person 1, then 2, then 3), what number is on their hat. If they know their own number, they say it, otherwise they say "I don't know" and the host moves on to the next player. If the host reaches person 3 and no one has stated their number, he starts again from person 1 and so on. The game ends when one of the players correctly states the number on their own hat.

Assuming no one makes guesses unless they are sure, show that the person wearing hat A can always win.

Bonus: Give a method for determining how many iterations(asking person 1, then 2, then 3, is one iteration) the host must make for a given pair B C before someone can answer correctly.

$\endgroup$
  • $\begingroup$ Can the players see the letter and number on each other's hats? And will there always be one each letter? Also, does to win mean to guess first? $\endgroup$ – Lily Potter Mar 20 '18 at 2:01
  • $\begingroup$ Welcome to Puzzling Stack Exchange! You can get a badge by take a tour here, puzzling.stackexchange.com/tour! :D $\endgroup$ – QuantumTwinkie Mar 20 '18 at 2:04
  • 2
    $\begingroup$ @LilyPotter If they know the letters, i don't think this will be a problem at all :P $\endgroup$ – votbear Mar 20 '18 at 2:04
  • 1
    $\begingroup$ Thanks QuantumTwinkie, I'll take the tour! And I see votbear, so I guess they just see numbers on each other's hats, but one of them is always secretly A, B, or C (and only the host knows this). $\endgroup$ – Lily Potter Mar 20 '18 at 2:06
  • $\begingroup$ b and c are distinct? $\endgroup$ – Oray Mar 20 '18 at 5:32
20
$\begingroup$

Answer:

Let $F(X, Y)$ be the number of turns you need to solve your own number, if you're A.
Where $X$ and $Y$ are the numbers you see, with $Y$ being the larger of the two $(Y >= X)$.

$$F(X,Y) = \begin{cases} \text{1} &\quad\text{if X = Y} \\ \text{$1 + F(X, Y - X)$} &\quad\text{otherwise} \\ \end{cases}$$
And yes, A will always be able to answer first.

First, some observations

When someone sees 2 hats in front of him (say X and Y), he only has 2 possibilities for his own hat:
1) He's A. It means his hat is X+Y.
2) He's not A. It means A is the bigger one between X and Y, and his own hat is the difference between X and Y.

Additionally, if X and Y is the same, then 2) is impossible since it would be 0, while the hat numbers are strictly positive. Therefore, if there are two hats of the same number between the three, then the one with hat A will solve his own number within a turn.

Alright. Now, let's take a look at different possibilities:

Let's say you're A (but you don't know that), and you're looking at 2 hats in front of you - call them X and Y.

Case 1: X = 1, Y = 1, You = 2 - Solved in iteration #1
You have 2 possibilities: 2 or 0.
As 0 is impossible, you can immediately answer 2 the first time you were questioned.

Case 2: X = 1, Y = 2, You = 3 - Solved in iteration #2
You have 2 possibilities: 3 or 1.
However, if you were 1, then Y would be seeing Case 1 in front of them, and will solve it within the first iteration. Therefore, if the game is not over yet after the first iteration, you'll know you're 3, and solve it in the second.

Case 3: X = 2, Y = 2, You = 4 - Solved in iteration #1
Again, it's trivial if X and Y is the same.

Case 4: X = 1, Y = 3, You = 4 - Solved in iteration #3
You have 2 possibilities: 4 or 2.
However, if you were 2, then Y would be seeing Case 2 in front of them, and will solve it within 2 iterations. Therefore, if the game is not over yet after 2 iterations, you'll know you're 4, and solve it in the third.

Case 5: X = 2, Y = 3, You = 5 - Solved in iteration #2
You have 2 possibilities: 5 or 1.
However, if you were 1, then Y would be seeing Case 2 in front of them. You know the drill by now.

Case 6: X = 1, Y = 4, You = 5 - Solved in iteration #4
You have 2 possibilities: 5 or 3.
However, if you were 3, then Y would be seeing Case 4 in front of them.

Case 7: X = 2, Y = 4, You = 6 - Solved in iteration #2
You have 2 possibilities: 6 or 2.
However, if you were 2, then Y would be seeing Case 3 in front of them.

And so on and so on.

Generalizing this, we get the rule above:

If X and Y are the same, then you must be A, and will answer in one iteration.

Otherwise, you will have 2 possibilities: X+Y or Y-X.
But if you're Y-X, that means you're not A. Y will be the actual A, since they're the largest of the three, and they will be seeing X and (Y-X) in front of them.

It gets recursive here - if that is the case, then that person has 2 possibilities too, and so on.. this will go until we reach point where a person has 2 same numbers in front of them.
Thus: Let $F(X, Y)$ be the number of turns you need to solve your own number, with $Y$ being the larger of the two $(Y >= X)$.

$$F(X,Y) = \begin{cases} \text{1} &\quad\text{if X = Y} \\ \text{$1 + F(X, Y - X)$} &\quad\text{otherwise} \\ \end{cases}$$

The reason the guy with A hat always solves first is because by the nature of this formula, they will always be one step ahead of the others:

Remember that $A = B + C$.
A's case will be $F(B, C)$
B's case will be $F(C, B + C) = 1 + F(B, C)$
C's case will be $F(B, B + C) = 1 + F(B, C)$

As you can see, B and C will reach $F(B, C)$ in one iteration... but that's what A started with! As such, they'll always lag one iteration behind A.

Do note however that the actual answer is actually slightly more complicated, thanks to the effect of asking them in order:

Answering based on the number of iterations is tricky if they're asked one by one, as depending on A's ordering (before or after the others), the answer can change.

For every step of the recursion where the A answers after the Y, then the final answer will be one iteration shorter (as he can already know the current iteration Y's answer without waiting for the next iteration). So it's more like this:
$$F(X,Y) = \begin{cases} \text{1} &\quad\text{if X = Y} \\ \text{$F(X, Y - X)$} &\quad\text{if X $\ne$ Y and you answer after Y} \\ \text{$1 + F(X, Y - X)$} &\quad\text{if X $\ne$ Y and you answer before Y} \\ \end{cases}$$
Still, even though this is the more 'correct' answer, I think the simplified formula is a better answer as it is easier to understand. This issue of less-iterations-due-to-answering-order feels completely unrelated to the main riddle, and only serves to add unnecessary complexity.

To solve this, I propose that within one round/iteration of questioning, all of them are asked separately and at the same time, and likewise they can only know of that entire round's result all at once afterwards.

$\endgroup$
  • $\begingroup$ Nice! You're pretty much there, I'd just like a little bit more rigor with regards to showing why your reasoning in the third spoiler block applies to all positive integers.(also I think there's a typo in the explanation of case 5). As for the second part, with the question as currently stated the number of iterations can deviate by more than 1 from your formula, though it would be correct if I implemented your suggestion. I agree that the question might be improved by your proposal but I felt like this way was more natural to understand and reason about. $\endgroup$ – Max Wang Mar 20 '18 at 21:06
  • $\begingroup$ I added some extra explanation, but i don't know if that helps at all, haha. At some point it feels like i'm just explaining something trivial. And you're right, it can definitely deviate by more than one iteration, fixed that part. Still, i kind of disagree with 'more natural to understand'. Having them submit their answer all at once (e.g. using paper or the like) feels pretty understandable imo, and is definitely worth making the problem much simpler rather than adding the complexity of possibly less iterations based on the ordering. $\endgroup$ – votbear Mar 21 '18 at 2:45
  • 1
    $\begingroup$ You're good. I was originally looking for an explicit explanation of why the recursion you gave always terminates but looking at it again, it seems obvious. I didn't see it at first because the way I solved this myself was the reverse: I started with all values X=Y(1,1;2,2;3,3...etc) and showed that every positive integer pair can be built from one of these "seeds". And I think you're right about the simplification being better as that causes the second question to neatly reduce to "what is the runtime of Euclid's Algorithm". $\endgroup$ – Max Wang Mar 21 '18 at 4:32
  • 1
    $\begingroup$ Ah right, euclid's algorithm. I knew this formula reminded me of something :P $\endgroup$ – votbear Mar 21 '18 at 7:24
3
$\begingroup$

Partial answer

If

$B=C$ then it is trivial because A can see two hats with the same number and so A knows that (s)he is A and the value of the number on their hat.

But if

$B\ne C$ then there is a problem. Always each person will see two numbers one greater than the other.

although

If the numbers are 1, 2, 3 then A will know after one round if the other two did not know, because then (s)he will know that the numbers are not 1,1,2.

and

If the numbers are 1,3,4 then we continue as before - after two rounds A who can see 1,3 will know it is not 1,2,3 because otherwise the person who is 3 would have known after one round. Meanwhile the other two cannot tell - the person looking at 1,4 has to wait until 3 rounds to know that their hat is not 2 or 3.

sadly at this point I have to leave it and return later. I suspect that

the number of rounds is equal to the greater of B and C less 1, but this problem deserves a proper answer that I am not able to finish at the moment.... [edit - ok so this part is completey wrong! but left in for posterity]

$\endgroup$
  • $\begingroup$ You're on the right track, just keep going. $\endgroup$ – Max Wang Mar 20 '18 at 4:43
  • $\begingroup$ @GoldenKing thanks, but I have to leave it for a bit now... and I am sure it will be solved when I get back, but very nice problem $\endgroup$ – tom Mar 20 '18 at 4:47
0
$\begingroup$

The pattern for other's reference:

1. If 0 is used:

0 is used

2. If same numbers are used:

Same numbers
Pattern: 1,2,3,4,5,6,7,8,......

3. If unique numbers are used:

Unique numbers
Pattern: 2,2,4,4,6,6,8,......

$\endgroup$
  • 1
    $\begingroup$ It is said "positive integer". There is no possible 0. $\endgroup$ – Untitpoi Mar 20 '18 at 7:06

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.