In my experience thinking is nigh impossible with your hands on the keyboard. Thinking happens in the shower, or with a pen in your hand and a sheet of paper in front of you, or in a conversation.
Here's a homework question that I got last week:
Two numbers x and y in 0..50 with x <= y get selected. Bob gets told x^2+y^2, Alice gets told x+y. Alice and Bob have the following conversation:
- Bob: I don't know which numbers x and y are.
- Alice: I don't know which numbers x and y are.
- Bob: I don't know which numbers x and y are.
- Alice: I don't know which numbers x and y are.
- Bob: I don't know which numbers x and y are.
- Alice: I don't know which numbers x and y are.
- Bob: Now I know which numbers x and y are.
Question: which numbers can x and y be?
If you're able to solve this problem by firing up your editor and starting coding the 10 lines of code required to solve it I'd be very surprised. Hard problems require real thinking.
Maybe my thinking is a bit slow here, but can't you even only begin to hope to answer this question if you assume Alice and Bob are cooperating in some fashion?
It's a very awkwardly phrased recursion problem. The point is to find a unique x, y where x <= y. The algorithm starts with the set of all possible (x, y) pairs, and switches between the Bob and Alice stages.
In Bob's stage, eliminate pairs that give a unique value for x^2 + y^2. If such a unique value matches the value Bob was given, then obviously you know x, y for sure.
Otherwise, switch to Alice's stage, which operates on the remaining pairs from Bob's stage, and eliminates all pairs that give a unique value for x + y.
The weirdness in the question is both Alice and Bob are performing the exact same algorithm, but (to use CSP parlance) there is a channel from Bob to Alice in Bob's stage, and vice versa, due to the different information given to both parties. Alice must wait for Bob to declare if the algorithm has terminated or not.
I don't think the algorithm you're proposing works, although that was my first idea as well. And I don't a priori see why the pair (x,y) would have to be unique (but it does appear to be, even if instead of choosing x and y in 0..5 you choose from all natural numbers).
Well, it is assumed they are speaking the truth, and it is assumed that they are good mathematicians (i.e. if they could know what x and y are at some point, they would know).
The idea is that if Bob says that he doesn't know what x and y are, then Alice can deduce some things from that, because she knows for which x and y he would know what they are. For example, after the first time Bob says he doesn't know Alice can deduce that x=1 y=1 is not the solution, because then Bob would know (because Bob gets told 1^2 + 1^2 = 2, and 2 = x^2 + y^2 implies x=1 y=1).
That's a similar puzzle. Maybe it's because I solved the homework puzzle first, but the blue eyes puzzle is much much easier. You might want to try to solve that first ;)
The cool thing about the blue eyes puzzle is that you can solve it without a computer or pen and paper.
Here's a homework question that I got last week:
Two numbers x and y in 0..50 with x <= y get selected. Bob gets told x^2+y^2, Alice gets told x+y. Alice and Bob have the following conversation:
- Bob: I don't know which numbers x and y are.
- Alice: I don't know which numbers x and y are.
- Bob: I don't know which numbers x and y are.
- Alice: I don't know which numbers x and y are.
- Bob: I don't know which numbers x and y are.
- Alice: I don't know which numbers x and y are.
- Bob: Now I know which numbers x and y are.
Question: which numbers can x and y be?
If you're able to solve this problem by firing up your editor and starting coding the 10 lines of code required to solve it I'd be very surprised. Hard problems require real thinking.