FYS: Puzzles and Paradoxes--Problem Set 10
Complete exactly three of the following five problems.
1. There are seventy-six coins sitting on the table; thirty-eight are currently heads and thirty-eight are currently tails. You are sitting at the table with a blindfold and gloves on. You are able to feel where the coins are, but are unable to see or feel if they are heads or tails. You must create two sets of coins. Each set must have the same number of heads and tails as the other group. You can only move or flip the coins, and you are unable to determine their current state.
Is it possible to guarantee that you create two groups of coins with the same number of heads and tails in each group? Justify your answer.
2. There are three switches in the basement. Each corresponds to one of three light sockets--one on the first floor, one on the second floor, and one in the attic. Each socket currently contains a standard incandescent light bulb. (The attic ceiling is low, so watch your head). You can turn the switches on and off and leave them in any position.
What is the minimum number of flights of stairs ('up' is a distinct travel from 'down' the same flight) you must travel to determine which switch goes with which socket? Justify your answer.
3. Flipper and Guesser are going to play a game. Guesser starts by choosing one of the eight possible strings of three coin tosses in a row. For example, HHH, or TTT, or HHT or whatever. Flipper then gets to pick one of the remaining seven possible strings. Flipper will then start flipping a fair coin continuously until either one of the two strings comes up. The person whose string comes up first is the winner.
Is this a fair game?
4.You are one of nineteen new prisoners to Logic Hell. Upon arrival, the warden, Mephistopholes, tells all nineteen of you that, "You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another. In the prison is a switch room, which contains two light switches labeled 1 and 2, each of which can be in either the up or the down position. I am not telling you their present positions. The switches are not connected to anything. After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him or her to the switch room. This prisoner will select one of the two switches and reverse its position. The prisoner must flip one switch when he or she visits the switch room, and may only flip one of the switches. Then the prisoner will be led back to his or her cell. No one else will be allowed to alter the switches until I lead the next prisoner into the switch room. I'm going to choose prisoners at random. I may choose the same prisoner three times in a row, or I may jump around and come back. I will not touch the switches; if I wanted you dead you would already be dead. Given enough time, everyone will eventually visit the switch room the same number of times as everyone else. At any time, anyone may declare to me, 'We have all visited the switch room.' If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will all die horribly. You will be carefully monitored, and any attempt to break any of these rules will result in instant death to all of you"
Is there a strategy that will guarantee that you and your fellow prisoners can be set free?
5.[Bonus Point Problem] You have entered Plato's Heaven whereupon you come across three pillars, Truth, Beauty, and Wisdom. Unfortunately, you do not know which pillar is which. You do however know that (i) Truth, when asked a non-paradoxical yes/no question, always answers truthfully with 'yes' or 'no'; (ii) Beauty, when asked a non-paradoxical yes/no question, always answers falsely with 'yes' or 'no'; and (iii) Wisdom, when asked a non-paradoxical yes/no question, always answers randomly with 'yes' or 'no'. All three pillars will remain silent for any other type of question or communication.
What is the minimum number of 'yes/no' questions required to determine the identity of all three pillars?
Due: Friday, April 7 at the beginning of class.