Thursday, October 11, 2012

Forehead Numbers Brain Teaser of Khan Academy

Today I remembered a little brainteaser I saw on Khan Academy quite a while back:  Khan Academy Link or Youtube Link

What surprises me though is that people still seem to think that there are values for which this can not be solved. My conjecture is that it CAN be solved for all 3-tuples of numbers provided that the participants know that they are unique.

I would recommend seeing the teaser and understanding the logic behind it before reading further.

3 years ago, when I first saw this, I posted a reply on Youtube describing the same 'game' from the perspective of a player who sees 15 and 11. For the sake of simplicity we'll call the player with 15 A and the one with 11 on his forehead C. Therefore the game is described from the perspective of B:
A-figures out his number (15)
B-figures out his number also
C-figures out his number as well (11)

The question then is, what is B's number (obviously it's either 26 or 4 but which one)?

I'm still not going to give the answer, but what I'm going to do is explain it on a particular 3-tuple which somebody on Khan Academy says it's impimpossibleimpossibleossible: numbers 5 7 and 12.
Let's presume they are again named A B and C respectively, A starts.
A sees 7 and 12 therefore he can be either 5 or 19 (sum), since he doesn't know he passes.
B sees 5 and 12 therefore he can be either 7 or 17, doesn't know => passes
C sees 5 and 7, he can be 12 sure, but since he's a PERFECT LOGICIAN, he'll think what if he was 2 (the difference).

Let's see the game unfolding in C's mind, when he presumes that he's 2:
Numbers: 5 7 and 2
A - can be 5 or 9 - pass
B - can be 7 OR 3 - now B can presume that he's 3.
So, again, this is all unfolding in C's mind, B would've seen a 5 (A) and a 2 (what C thinks he might have) and there fore would've thought that he was 3. Then, in B's mind the game would've unfolded like this:
Numbers: 5 3 and 2
A - can be 5 or 1, so, like in the previous assumptions he can think what would've happen if he was one
Remember, just to keep track, we're explaining what C thinks of what B thinks of what A would think and I'm being dead serious about what I'm writing (even my head's starting to hurt).
So from A's mind:
Numbers 1 3 and 2
Now notice that we reach a solvable position: B can figure out his number, since he knows the numbers are unique (he can't be also 1). So again, from A's mind in B's mind in C's mind:
A - can be 5 or 1 - pass
B - can only be 3 (remember, A is 1 in this scenario) therefore he SHOULD know his number.

BUT! B said pass, which tells A that he can not be 1, therefore he must be 5 (if B was 3 and C was 2)

Now, coming back out of the mind of B from the mind of C, so back in our initial configuration (5 7 12)
C can not deduce his number so he passes and now we go onto the second round:
A passes
So now C thinks again, if he 2, B would've thought he was either 3 or 7 and furthermore, B would think that since A said pass, he can NOT be 3 (by the previous logic) therefore he's 7
But B passes what does this mean? it means that C is not 2, he's 12
So now C know's that he's 12 and he can safely say his number and receive a bag of kudos for being so smart (well not really).

So in the end, the game unfolds like this:
A = 5, B = 7, C = 12
A - pass
B - pass
C - pass

A - pass
B - pass
C - figures out he's 12

And then the other figure out their numbers as well - this is pretty trivial considering they are perfect logicians they can be either one of two options, so:

A - figures his number, 5
B - figures his number also, 7

If you managed to follow what happened then congrats! To be honest I have a hard time following, so it might be helpful to take a piece of paper in case you're struggling with the recursive nature of their thinking.
What I find it interesting is how much this resembles Euclid's algorithm for computing the GCD between two numbers. From what I can figure out, the game always ends no matter what numbers you choose - eventually they will presume that they are the smaller of the numbers  that they can be and will therefore reach a stage in which the "uniqueness" rule kicks in.

I'm also thinking what would happen if instead of having 2 possible options (sum and difference) we choose any number of functions that can be performed on two numbers. So say we have a game in which a player can be the sum, difference or the integral part of the average (integral part so that we only have natural numbers) of the other two. Also I'm wondering if using this the game can be extended to arbitrary numbers of players.

Thanks for reading :P