Problems

Frodo ventures into a thick fog where he is to meet his three companions: Sam, Merry, and Pippin. He can tell they are standing in a row, in front of him – one on the left, one in the middle, and one on the right – but he cannot see who is who. To help, he asks each of them to speak.

Remember: Sam always lies, Merry always tells the truth, and Pippin sometimes lies and sometimes tells the truth.

Here is what Frodo hears:

• The one on Frodo’s left says: “Merry is next to me.”

• The one on Frodo’s right says: “The person who just spoke is Pippin.”

• The one in the middle says: “On my left is Sam.”

Can you work out who is standing on Frodo’s left, in the middle, and on the right?

In the first room, there are two doors. The signs on them say:

1. There is treasure behind this door, and a trap behind the other door.

2. Behind one of these doors there is treasure and behind the other there is a trap.

Your guide says: One of the signs is true and the other is false. Which door will you open?

In the second room, there are two doors. Both statements on them say:

1. There is a treasure behind both doors.

2. There is a treasure behind both doors.

Your guide says: The first sign is true if there is treasure behind the first door, otherwise it is false. The second sign is false if there is treasure behind the second door, otherwise it is true. What do you do?

In the third room, there are three doors. The statements on them say:

1. Behind this door there is a trap.

2. Behind this door there is treasure.

3. There is a trap behind the second door.

Your guide says: There is treasure behind one of the doors exactly. At most one of the three signs is true - but it is possible all of them are false.
Which door will you open?

There are two doors in the room with the following signs:

1. There is treasure behind at least one of the doors.

2. There is a trap behind the first door.

Your guide says: The signs are either both true or both false.
Which door will you open?

There are three doors with the following statements:

1. Behind the second door there is a trap.

2. Behind this door there is a trap.

3. A trap is behind the first door.

Your guide says: There is treasure behind one of the doors exactly. The sign on that door is true, but at least one of the other ones will be false.
Which door will you open?

There are two doors with the following signs:

1. There is either a trap behind this door or there is treasure behind the second door.

2. There is treasure behind the first door.

Your guide says: The signs are either both true or both false. Which door will you open?

Now you have two doors with the statements:

1. It makes no difference which door you pick.

2. There is treasure behind the first door.

Your guide says: The first sign is true if there is treasure behind the first door, otherwise it is false. The second sign is false if there is treasure behind the second door, otherwise it is true. What do you do?

Jason has \(20\) red balls and \(14\) bags to store them. Prove that there is a bag which contains at least two balls.

One of the most useful tools for proving mathematical statements is the Pigeonhole principle. Here is one example: suppose that a flock of at least \(10\) pigeons flies into a set of \(9\) pigeonholes to roost. Prove that at least one of these \(9\) pigeonholes must have at least two pigeons in it.