Skip to main content
2 of 6
added 968 characters in body
votbear
  • 4.7k
  • 19
  • 32

Answer:

Let F(X, Y) be the number of turns you need to solve your own number, if you're A.
For simplicity purposes, let Y be the larger of the two, Y >= X.

F(X, Y) = 1. (If X = Y)
F(X, Y) = F(X, Y - X) + 1 (Otherwise)

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 1 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:

Let F(X, Y) be the number of turns you need to solve your own number, if you're A.
For simplicity purposes, let Y be the larger of the two, Y >= X.

F(X, Y) = 1. (If X = Y)
F(X, Y) = F(X, Y - X) + 1 (Otherwise)

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)
C's case will be F(B, 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.

By the way, answering based on the number of iterations is tricky if they're asked one by one... Depending on A's ordering (before or after the others), the answer can be up to one iteration faster.

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

votbear
  • 4.7k
  • 19
  • 32