Seven puzzles
Posted: Fri Mar 02, 2007 9:26 pm
I got sent these by a maths lecturer so here you all go:
1)
The names of 100 prisoners are placed in 100 wooden boxes, one name to a box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room; each may look in at most 50 boxes, but must leave the room exactly as he found it and is permitted no further
communication with the others.
The prisoners have a chance to plot their strategy in advance, and they are going to need it, because unless every single prisoner finds his own name all will subsequently be executed.
Find a strategy for them which which has probability of success exceeding 30%.
2)
At many train stations, post offices and currier services around the world, the cost of sending a rectangular box is determined by the sum of its dimensions; that is, length plus width plus height.
Prove that you can't "cheat" by packing a box into a cheaper box.
3)
Each resident of Dot-town carries a red or blue dot on his (or her) forehead, but if he ever figures out what color it is he kills himself. Each day the residents gather; one day a stranger comes and tells them something|anything|non-trivial about the number of blue dots. Prove that eventually every resident kills himself.
4)
Suppose you have an algebraic expression involving variables, addition, multiplication, and parentheses. You repeatedly attempt to expand it using the distributive law. How do you know that the expression doesn't continue to expand forever? "Non-trivial" means here that there is some number of blue dots for which the statement would not have been true. Thus we have a frighteningly general version of classical problems involving knowledge about knowledge.
5)
Jan and Maria have fallen in love (via the internet) and Jan wishes to mail her a ring. Unfortunately, they live in the country of Kleptopia where anything sent through the mail will be stolen unless it is enclosed in a padlocked box. Jan and Maria each have plenty of padlocks, but none to which the other has a key. How can Jan get the ring safely into Maria's hands? (Two solutions, but one is much more elegant and worth more points).
6)
As a result of temporary magical powers, you have made it to the Wimbledon finals and are playing Roger Federer for all the marbles. However, your powers cannot last the whole match. What score do you want it to be when they disappear, to maximize your chances of hanging on for a win?
7)
A logician is again visiting the South Seas, and is as before at a fork, wanting to know which of two roads leads to the village. This time, present are three willing natives, one each from a tribe of invariable truth-tellers, a tribe of invariable liars, and a tribe of random answerers. Of course the logician doesn't know which native is from which tribe. Moreover, he is permitted to ask only two yes-or-no questions, each question being directed to just one native. Can he get the information he needs?
1)
The names of 100 prisoners are placed in 100 wooden boxes, one name to a box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room; each may look in at most 50 boxes, but must leave the room exactly as he found it and is permitted no further
communication with the others.
The prisoners have a chance to plot their strategy in advance, and they are going to need it, because unless every single prisoner finds his own name all will subsequently be executed.
Find a strategy for them which which has probability of success exceeding 30%.
2)
At many train stations, post offices and currier services around the world, the cost of sending a rectangular box is determined by the sum of its dimensions; that is, length plus width plus height.
Prove that you can't "cheat" by packing a box into a cheaper box.
3)
Each resident of Dot-town carries a red or blue dot on his (or her) forehead, but if he ever figures out what color it is he kills himself. Each day the residents gather; one day a stranger comes and tells them something|anything|non-trivial about the number of blue dots. Prove that eventually every resident kills himself.
4)
Suppose you have an algebraic expression involving variables, addition, multiplication, and parentheses. You repeatedly attempt to expand it using the distributive law. How do you know that the expression doesn't continue to expand forever? "Non-trivial" means here that there is some number of blue dots for which the statement would not have been true. Thus we have a frighteningly general version of classical problems involving knowledge about knowledge.
5)
Jan and Maria have fallen in love (via the internet) and Jan wishes to mail her a ring. Unfortunately, they live in the country of Kleptopia where anything sent through the mail will be stolen unless it is enclosed in a padlocked box. Jan and Maria each have plenty of padlocks, but none to which the other has a key. How can Jan get the ring safely into Maria's hands? (Two solutions, but one is much more elegant and worth more points).
6)
As a result of temporary magical powers, you have made it to the Wimbledon finals and are playing Roger Federer for all the marbles. However, your powers cannot last the whole match. What score do you want it to be when they disappear, to maximize your chances of hanging on for a win?
7)
A logician is again visiting the South Seas, and is as before at a fork, wanting to know which of two roads leads to the village. This time, present are three willing natives, one each from a tribe of invariable truth-tellers, a tribe of invariable liars, and a tribe of random answerers. Of course the logician doesn't know which native is from which tribe. Moreover, he is permitted to ask only two yes-or-no questions, each question being directed to just one native. Can he get the information he needs?
