Mismatched Letters

Soon after her wedding, a young bride hand-writes 100 thank you letters to all of her recent wedding guests and addresses 100 matching envelopes. Being in a hurry to get them in the mail, her new husband randomly stuffs the letters into envelopes and mails them out. What is the probability that exactly 99 of the letters made it into the right envelope?

This problem may seem difficult to model, but don't worry, it isn't necessary. If 99 out of 100 letters are in the right envelope, then the 100th one must be as well. So there is a probability of 0 that exactly 99 are correct.

Flipping 100 Coins

You have 100 fair coins and you flip them all at the same time. Any that come up tails you set aside. The ones that come up heads you flip again. How many rounds do you expect to play before only one coin remains? What if you start with 1000 coins? Click below for the answer.

When you flip 100 coins in the first round, you should expect to see about 50 heads. When you flip those 50 coins again in the second round, you should expect about 25 heads. This (approximate) halving pattern will continue until you're left with only one coin. On average, it will take 6 or 7 rounds when starting with 100 coins because $$log_2(100) = 6.644$$
When you start with 1000 coins, the game will last about 10 rounds. (So if you want to bet someone that you can flip a coin and have it come up heads 10 times in a row, you'll greatly improve your odds if you start with 1000 coins!)

See my Probability GitHub repository for a script that shows how to model this problem in Python.

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.

Knights or Knaves?

You find yourself on the Island of Knights and Knaves, a logical kingdom whose inhabitants either always lie (Knaves) or always tell the truth (Knights). You encounter three of said inhabitants, call them Alice, Bob, and Carol. You ask the following questions.

To Alice you ask, "Is Bob a Knight or a Knave?"

"A Knight," she answers.

To Bob you ask, "Are Alice and Carol both Knights or both Knaves?"

"Yes," replies Bob.

Finally, you ask Carol, "Is Bob a Knight or a Knave?"

"A Knave," she says.

Who is a Knight and who is a Knave? Click below for the answer.

Since Alice and Carol answered differently to the same question, they cannot both be Knights or Knaves, they must represent one of each type. Since this is counter to what Bob answered, he must be lying. Bob must be a Knave. That means that Carol answered truthfully, and is a Knight, and Alice did not, so she is a Knave.

True or False?

You're taking your college entrance exam, and things are not going well. You spent too much time answering the essay questions and word problems, and now you're running out of time. You turn to the final section and are relieved to find that it consists of 100 True/False questions. The bad news is that you only have 2 minutes left to complete the entire exam!

You figure it doesn't matter if you answer all True, all False, or just guess randomly. Odds are you'll probably get half of them right either way. You begin scribbling in your answers.

How many different ways (unique sequences) are there to answer 100 True/False questions? Click below for the answer.

If you're a computer programmer, you may have recognized right away that this is just a binary counting problem in disguise. Substitute 1 for True and 0 for False, and this is the same as asking how many unique values can be represented by 100 binary bits. Since that's every value from all 0s to all 1s, the answer is $2^{100}$, or 1,267,650,600,228,229,401,496,703,205,376.

King's Sentence

A man is caught poaching on the King's property. He is brought before the King to be sentenced.

The King says, "You must give me one statement. If it is true, you will killed by lions. If it is false, you will be killed by trampling of wild buffalo."

In the end, the King has to let the man go.

What was the man's statement? Click below to see the answer.

The man can get out of the punishment by making a paradoxical statement, such as "I will NOT be killed by lions." If that statement was true, the man would be killed by lions, making the statement false. Another statement that would have worked is "I will be killed by trampling of wild buffalo."

A Boy and a Girl

Two children, one boy and one girl, make the following statements.

"I am a boy" said the child with brown hair.

"I am a girl" said the child with red hair.

At least one of the children is lying. Who is the boy and who is the girl? Click below for the answer.

Both children are lying.

The child with the brown hair is the girl, and the child with the red hair is the boy.

(If only one child had lied, they would both be boys or both be girls.)