CSC 165: Warm-up puzzles

The following puzzles serve as indirect motivation for this course. Each of these problems relates in some way to problems we encounter in computer science. We'll be examining techniques that help us reason about such problems and solve them.

The level of difficulty of these problems varies. Some of these puzzles are easy, and most people can solve them in a few minutes. Some are difficult, and unlikely you will solve them without knowledge of some specific techniques. Solutions can probably be easily discovered with a little research, but are much more rewarding if you work them out yourself.

1. 3 boxes
   Suppose you are a contestant on a game show and you are presented with 3 boxes. Inside one is a prize, which you will win if you chose the correct box. The game goes thusly: you choose a box, and the host opens one of the remaining boxes which is empty. You may then switch your choice to the remaining box or stay with your original choice.
   Which box would you choose for the best chance of winning the prize? Why?
2. 3 labelled boxes
   In the next round, you are again presented with 3 boxes, one containing a small prize. This time, you must choose one box, and if you choose correctly, you win the prize. On closer examination, you notice a label on each box.

   The prize is not here.

   The prize is here.

   The prize is not here.

   Which box do you choose?
3. 2 labelled boxes
   In the net round, you are presented with just two boxes, with one containing a prize. The host explains that two stagehands Adam and Brian pack the boxes. Adam always puts a true statement on the box, and Brian always puts a false statement on the box. You don't know who packed the boxes, or ever if they were both packed by the same person or different people. The boxes say:

   The prize is not here.

   Exactly one box was packed by Brian.

   Which box do you choose?
4. 2 labelled boxes surprise
   In the final round, you are presented with two more boxes. The host tells you one box contains the grand prize, but if you choose the wrong one, you lose everything. The labels say:

   The prize is not here.

   Exactly one statement on the boxes is false.

   You reason that if the statement on the right box is true, the left box statement must be false, so the prize is in the left box. If the statement on the right box is false, either both statements are true or both are false. They cannot both be true, since the one on the right is false. So both are false, and the prize must be in the left box. So you choose the left box.
   You open it and it's empty! The host claims he didn't lie to you.
   What's wrong? (The difference between this and the previous puzzle is subtle but basic and essential for rigorous treatment of logic.)
5. Knights and Knaves
   On the island of knights and knaves, every inhabitant is either a knight or a knave. Knights always tell the truth, and knaves always lie. You come across two inhabitants, let's call them A and B.
   1. Person A says: "I am a knave or B is a knight."
      Can you determine what A and B are?
   2. Person A says: "We are both knaves."
      What are A and B?
   3. Person A says: "If B is a knave, then I'm a knight."
      Person B says: "We are different."
      What are A and B?
   4. You ask A: "Are you both knights?" A answers either Yes or No, but you don't know enough to solve the problem.
      You then ask B: "Are you both knaves?" B answers either Yes or No, and now you know the answer.
      What are A and B?
   5. A and B are guarding two doors, one leading to treasure and one leading to a ferocious lion which will surely eat you. You must choose one door. You may ask one guard one yes/no question before choosing a door. What question do you ask? Is it easier if you know one is a knight and one is a knave (but you don't know which is which)?
6. Mother Eve
   Theorem: There is a woman on Earth such that is she becomes sterile, the whole human race will die out because all women will become sterile.
   Proof: Either all women will become sterile or not. If yes, then any woman satisfies the theorem. If no, then there is some woman that does not become sterile. She is then the one such that if she becomes sterile (but she does not), the whole human race will die out.
   Is this argument convincing?
7. Santa Claus
   Wife: Santa Claus exists, if I am not mistaken.
   Husband: Well of course Santa Claus exists, if you are not mistaken.
   Wife: Hence my statement is true.
   Husband: Of course!
   Wife: So I was not mistaken, and you admitted that if I was not mistaken, then Santa Claus exists. Therefore Santa Claus exists.
   Are you convinced? Why or why not?
8. Daemon in a Pentagon
   There is a pentagon and at each vertex there is an integer number. The numbers can be negative, but their sum is positive. A daemon living inside the pentagon manipulates the numbers with the following atomic action. If it spots a negative number at one of the vertices, it adds that number to its two neighbours and negates the number at the original vertex. Prove that no matter what numbers we start with, eventually the daemon cannot change any of the numbers.