There are several versions of this puzzle. One version was heard on "Car Talk", and that's what I will work from. I enjoy this puzzle because it absolutely stumped me. I couldn't see a way to solve the problem, I convinced myself it was impossible, and the answer pointed out some flaws in the way I was thinking.
There's a brand new prison. One hundred new death row convicts are standing in the prison yard, the warden reads them the usual rules and regulations, and then makes a surprise statement.
"I don't run this jail like most wardens would. I'm going to give you a chance to escape fair and square. To do so, you will all have to work together to meet my challenge."
"Here's how it works. Do you see that little building in the middle of the yard? Inside there is a wall switch that controls a lightbulb, which is either ON and OFF. I randomly set the switch just now, but I'll never touch it again."
"You will all be in solitary confinement. But every day I will take one of you from his cell into that little room for five minutes. While the convict is in the room, he may look at the lightbulb, and flip the switch if desired. That's all that's allowed."
"Although I will pick a convict more or less at random each day, I will guarantee you that eventually, every one of you will go into the room, and if you're here long enough, every one of you will enter that room an unlimited number of times. Now, as I am walking you back from that room to your cell, you may say nothing, or you may announce to me that you believe that every convict has been in the room. If you are correct, all the convicts go free. If you are incorrect, then I will have you all executed."
"You now have one hour to debate your strategy, and then you're going into your cells and you will never see another person here, except me!"
Of course, one "strategy" would simply be to wait for about a year or so, and then risk an announcement. But can you think of a strategy that will guarantee that the announcement can be made, and made correctly?
I give up, let me see the solution.