[borisp]

Bingo...another hint from the interview was "What if only YOU were allowed to make the announcement to the guards?" At that point my friend solved it. (I am terrible at this sort of quirky problem solving, which is probably why I find it fascinating.)

You mentioned monk/dots type problems...there is an interesting follow - up to this type of problem, probably more interesting than the problem itself. Here is the simplest version I know, maybe it's already been worked out here:

Suppose that on an island no one ever talks about eye color, looks in the mirror, etc. because of a strange custom: if you ever know your eye color for certain, you must take a pill that night that kills you in your sleep. Further, everyone has either blue or brown eyes, and they are perfectly rational, etc. Everyone knows the eye color of everyone but themselves. One day a traveler shows up and announces to the entire island "At least one of you has blue eyes."

An easy induction then shows that if N people have blue eyes, then on the (N+1)st day they don't wake up, and on the (N+2)nd day everyone else doesn't wake up. This proves that "If the traveler makes this announcement, then everyone dies."

However, is it an "only if?" Meaning, if 300 people live on the island, and 150 of them have blue eyes, the traveler is announcing information that everybody already knows. So why the need for the traveler? Why didn't everyone kill themselves already? What new info does he provide?

One common response is that the traveler provides the base case for the induction, which actually only demonstrates that he is needed for an inductive argument. Induction does not have a monopoly on proof techniques, so this isn't really a proof of necessity.

So the follow up question is to prove that "If the traveler never comes, then no one dies (from the custom)."