Coin Flipping Game

You have ten coins in a row, all facing tails up. You are to perform a sequence of moves on the coins where one move consists of flipping over any one coin from tails to heads, then flipping over the coin to its immediate right (whether the second coin is heads or tails does not matter, just flip it over). Can you prove that no matter what moves you select, there are a finite number of moves in the sequence? (In other words, prove that you will always reach a state where there are no more legal moves.) Click below for the answer.

It helps to try this out a few times to get a feel for how the combinations of coins progresses as you make moves in this game. If you don't have any coins handy, just use 0s (tails) and 1s (heads) on a piece of paper, starting with ten 0s, and work through a few sequences. Here's an example:

00000 00000
00000 11000
00001 01000
00001 10000
00001 11100
00010 11100
...

Now, instead of focusing on the sequence of moves, focus on the sequence of resulting numbers. Do you notice anything? This is a binary number sequence that is always increasing. The rules of the game are designed such that no matter which bit you choose, the next number in the sequence will always be higher. (Because you flip a 0 to a 1, then flip a lower-order bit.) Since the sequence is strictly increasing, you must eventually reach a state where there are no more legal moves.

A Knight, a Knave, and a Spy

You find yourself on the Island of Knights, Knaves, and Spies, a logical kingdom whose inhabitants always lie (Knaves), always tell the truth (Knights), or who can do either (Spies). You encounter three of said inhabitants, call them Alice, Bob, and Carol. You are told by your guide (a trustworthy Knight) that in this group there are one of each type of inhabitant, a Knight, a Knave, and a Spy. You ask the following questions.

To Alice you ask, "Are you a Knight?"

"No," she answers.

To Bob you ask, "Are you a Spy?"

"No," replies Bob.

Finally, you ask Carol, "Are you a Knave?"

"No," she says.

Can you tell from these answers who is a Knight, who is a Knave, and who is a Spy? Click below for the answer.

Alice must be a Spy. A Knight could never answer "No" to her question, because they'd be lying. A Knave couldn't either, because they'd be telling the truth.

Bob must be a Knight. A Knave could not answer "No" to that question, since they'd be telling the truth. A Spy could, but we've already established that Alice is the Spy in this group.

Carol's answer is consistent with what a Knight or a Knave would say (or a Spy might say), but by process of elimination, she must be a Knave.

The King's Adviser

A king decides he is going to fire one of his advisers. He tells him that he has written "You're fired" on one slip of paper, and "You can stay" on another, and that the adviser is to choose one at random. The king has secretly written "You're fired" on both notes, but unbeknownst to the king, the adviser has found this out! How can the adviser keep his job without telling the king that he knows both notes are the same?

The adviser can select either one of the notes, then destroy it by throwing it in the fire (or by eating it, if there is no convenient fire nearby). He can then tell the king to open the other note, and deduce by elimination which was the one selected. Since the remaining note is guaranteed to say "You're fired," the king must pretend that the note the adviser selected said "You can stay."

Water Glasses

You have five glasses arranged in a row. The first two are empty and the last three are filled with water. By moving only one glass, can you arrange them so full and empty glasses alternate? Click below for the answer.

Pick up the fourth glass, pour the water into the first glass, then replace the fourth (now empty) glass to its original position.