Here's a good one:
There are 100 prisoners in solitary cells. Prisoners will be selected at random to go into an interrogation room that contains a light bulb they can turn on or off. If one of the prisoners is able to assert that all 100 prisoners have been through the interrogation room at least once, then they will all be set free. If the assertion is wrong, then all the prisoners will die. The prisoners are allowed to get together for one night beforehand to formulate a plan after which they will not have any communication with one another except via the light switch (which cannot be viewed from outside of the interrogation room.)
Propose a fool-proof strategy that will ensure all prisoners have been through the interrogation room.
This puzzle kept us occupied for the better part of two days...