Two logicians place cards on their foreheads so that what is written on the card is visible only to the other logician. Consecutive positive integers have been written on the cards. The following conversation ensues:

A: "I don't know my number."

B: "I don't know my number."

A: "I don't know my number."

B: "I don't know my number."

........ n statements of ignorance later..........

A or B: "I know my number."

What is on the card and how does the logician know it?

The first few iterations:

A has a 2 on his forehead, B has a 1
A:y
A thinks "B has a 1, so I must have a 2"

A-1, B-2
A:n, B:y
B thinks "A has a 1, so I must have a 2"

A-2, B-3
A:n, B:y
"A has a 2. If I had a 1, A would have already answered, so I must have a 3."

A-3, B-2
A:n, B:n, A:y
"B has a 2. If I had a 1, B would have already answered, so I must have a 3."

A-4, B-3
A:n, B:n, A:y
"B has a 3. If I had a 2, B would have already answered, so I must have a 4."

A-3, B-4
A:n, B:n, A:n, B:y
"A has a 3. If I had a 2, A would have already answered, so I must have a 4."

A-4, B-5
A:n, B:n, A:n, B:y
"A has a 4. If I had a 3, A would have already answered, so I must have a 5."

A-5, B-4
A:n, B:n, A:n, B:n A:y
"B has a 4. If I had a 3, B would have already answered, so I must have a 5."

A-6, B-5
A:n, B:n, A:n, B:n A:y
"B has a 5. If I had a 4, B would have already answered, so I must have a 6."

For each "no" heard, that player knows the number on their head must be higher than that number of no's (e.g., hearing 4 no's means that the number on their head must be at least 5.)

So they say "no" until they have heard either the number they see on the other's head, or one less than that number. They then say yes, and add one to the number they see for their number.

So if n statements of ignorance have passed before someone says yes, then the number said will be either n+1 or n+2, depending on if the other person's card is n or n+1.

Posted by Ender on 2003-04-11 06:37:44