.100 people is seated in a column. Devil puts a hat of either red or blue on everyone's head. Everyone can only see the hats of all the people sitting before him. Each one has to say the color of his own hat, starting from the one sitting on the last seat who can see the hats of all 99 people before him, but not his own. He would be killed if he guessed wrong. After the last one guessed, the 99th person would guess. All his information is the hats on the 98 people before him and what the last one guessed, which he can hear. He would also be killed if he guessed wrong. Each person guess in turn till the person sitting on the first seat. Each one's information is the hats of people before him and what the people after him guessed. Those 100 people can get together and devise a strategy before the Devil puts on the hats. Devil would know their strategy and try to put on the hats so he can kill as many people as possible. What's the best strategy those 100 people can come up with to minimize the total number of people being killed? Assume everyone is unselfish and works together for this common goal.
100 pirates needs to allocate 100 identical laptops among
them. Their democratic system works as follows:
All pirates are ranked by their seniority. First, the most senior
pirate (called "Majority leader") propose an allocation plan that
states exactly how many laptops each pirate would get. The 100 pirates
would vote on the plan (no filibuster) and it would pass if more than
or equal to half pirates voted for it. If it passes, pirates take
their laptops and go home. If it fails, the one who proposed the plan
(the most senior pirate in this case) would be killed, and then the
second most senior pirate would take the place of "Majority leader"
and propose his plan. We repeat the same process above in the order of
seniority until someone's plan is passed.
Assume every pirate makes his decision based on the following
priorities:
1. He doesn't want to die.
2. Given he's not going to die, he would prefer to get as many laptops as possible.
3. Given he's going to get the same number of laptops, he would prefer as many other pirates to die as possible.
Also assume every pirate is smart and knows everyone else is smart, and so on. (See what "so on" means, rigorously.) What will happen? i.e. whose proposal will be passed and what is the proposal?
** Pirates' democracy, part 2:
What happens if there are 435 pirates (but still only 100 laptops)?
This is qualitatively more difficult than the case with 100
pirates.
(There is nothing magic about 435. It's just the number of
Representatives.)
GoBang is an oriental chess game, also called 5-in-a-Row. Here we consider a modified version:
The board is a grid extending infinitely to all four directions. In
each turn, player A puts two black stones on the board while player B
puts down only one white stone. Player A wins if 1000 of his black
stones form a consecutive line (either vertical, horizontal, or
diagonal). Player B tries to block A from achieving that
goal. However, player B himself can never win (i.e. the game continues
even if 1000 of his white stones form a line). Show that player A has
a strategy so that he can always achieve the goal and win, no matter
how player B plays.
A dog is in the center of a round swimming pool. A tiger, who can't swim, is on the edge of the wimming pool and tries to catch the dog. What's the maximum ratio of the tiger's running speed and the dog's swimming speed given that the dog can swim ashore without being caught by the tiger? What's the strategy (i.e. swimming route) the dog should use?
Note: this problem can be solved by differential equation. However, there is an elegant solution using only elementary math. Unfortunately, I am not aware of any closed form analytic solution.
# Hint: see the speed ratio (approximate)
## Hint: see the speed ratio (exact)
What's the degree of angle 'a'?
According to Hai Huang, this problem appears in
American Airline in-flight magazine. Does AA assume its passengers
have IQ > 150 ?!
For more info, see http://thinkzone.wlonk.com/MathFun/Triangle.htm
There is only one person on an island. He either always tells the truth or always lies, but you don't know which is the case. You reach an intersection and don't know if you should turn left or right. You can only ask him one "Yes/No" question. What question should you ask so you can figure out the direction you need to go?
100 prisoners are held incommunicado in a jail. They are being brought into a court room randomly. Each time they enter into the court, they can either turn on or turn off the light. Initially the light is off. Assume each prisoner will be brought into the court for many times and no two of them will be in the court at the same time. At any time, a prisoner can claim that each of the 100 prisoners has been in the court room for at least once. They will all be released if the claim is correct and put to death if it's wrong. These 100 prisoners could devise a strategy before they went to the jail. How could they guarantee their freedom eventually?
** Survival of the smart prisoners, part 2:
What happens if the initial state of the light is unknown?