How to Cheat at Hangman
When I was at Yale, I remember taking our most famous computer science class, CS223, with Professor Stanley Eisenstat.
Professor Eisenstat wrote out a game of hangman on the board with 3 letters filled out:
We had 8 guesses to get this right. The class started shouting out different possibilities. We started very confidently with will, kill, mill … this went on for quite a while as we gradually lost that confidence. Then Professor Eisenstat told us that there were many different words that this could be — far more than 8. Bill, Dill, Fill, Gill, Hill, Jill, Kill, Mill, Pill, Sill, Till, and Will. 12 words in fact. Here’s where the cheating comes in. Because Professor Eisenstat hadn’t committed to an answer beforehand, there was no way that we could win the game. When we chose a letter, he removed that word from the set of possible winners. He always had an option that we hadn’t chosen.
This was used as an example of an adversary that prevents a program from getting its job done. It also shows that what could be an easy problem is often far more difficult than it first appears.
Another interesting situation came up my freshman year. It was a beautiful day and we were sitting outside in a seminar called “Perspectives on Science.” As we were sitting on the lawn under a tree, one of my classmates was performing a demonstration of how probability works. If you flip a coin a large number of times, half of the time will be heads and the other half tails.
“Can someone give me a quarter?” she asked the group. My friend Christine Aidala excitedly reached into her pocket and grabbed a quarter. The first person flipped the coin.
“Heads,” they said.
“Heads,” the second said.
By this time the quarter came back to the leader who examined the coin. “Who walks around with a two headed quarter?!” she blurted out in surprise. As it turns out, Christine did. At the time, we were obsessed about Tom Stoppard’s Rosencrantz and Guildenstern are Dead which includes a scene where the laws of probability are broken with a coin that continuously lands on heads. So Christine got one.