.png)
5 hours ago
2
Earlier today I set these two puzzles. Here they are again with solutions.
1. Go compare!
A dealer places one hundred cards on a table. On their face-down sides are the numbers from 1 to 100. The cards are randomly arranged so you have no idea at the beginning which card is which. Your task is to identify the 1 card and the 100 card without turning any of them over.
The only way to learn information about the cards is by comparison. At any stage, you may choose two and ask the dealer which is smaller and which is larger. The dealer always knows. They will never tell you the number on the cards, just which is smaller and which is larger.
It is possible to identify the 1 card after asking the dealer to make 99 comparisons. First, ask them to compare any two cards. Make a note of the lower card, and ask them to compare it with one of the 98 remaining cards. Make a note of the lower card, and ask them to compare it with one of the 97 remaining cards. And so on. The lower card in the 99th comparison must be lower than all other cards, and thus is the 1 card. Likewise you can identify the 100 card after 99 comparisons, making a total of 198 comparisons to find both highest and lowest cards.
Can you find a method to identify the 1 and the 100 cards using less comparisons? What’s the optimal strategy?
Solution You can do it in 148 comparisons.
STEP 1: Divide the cards into fifty pairs. Ask the dealer to compare the cards in each pair. (Total: 50 comparisons.)
STEP 2: Consider the 50 lower cards from these comparisons. This group contains the 1 card. It will take 49 comparisons to identify with 100 per cent certainty which is the 1 card, which we do by comparing any two cards, taking the lower one, etc, and going through the remaining 48 as we did above.
STEP 3. By the same logic, the remaining 50 cards contain the 100 card. It will take 49 comparisons of this group to identify with 100 per cent certainty the 100 card. TOTAL: 50 + 49 + 49 = 148 comparisons.
This strategy is optimal. The proof is somewhat technical for a general audience, but if any mathematicians want to write it down in full in the comments below I’m sure some readers will be grateful.
2. The rope trick
You are a burglar at the top of a 20m building, which has a ledge half way down on which it is possible to stand. There are hooks at the top of the building and on the ledge. You have a 15m length of rope and a knife. You can cut the rope if you like, and also make any type of knot anywhere on the rope, which uses up no length, and which can be placed on either hook.
How would you use the rope to descend the building safely? You are not allowed to jump off the building or the rope.
Solution
Cut the rope into two pieces of 5m and 10m. Make a knot at one end of the 5m rope. Thread the 10m rope through this knot and tie its ends together. Make a knot at the other end of the 5m rope and attach it to the hook. Dangle the ropes down the side of the building and climb down them. The joined ropes have a combined lenth of 10m (5m + 5m), which gets you to the ledge. Untie the ends of the 10m rope and pull it through the other rope. This rope will get you down the final 10m when you attach it to the hook on the ledge.
Thanks to Geza Bohus for suggesting today’s puzzles. Geza was a Hungarian maths olympiad contestant many moons ago and is now semi-retired after a career in academia and industry, specialising in machine learning and financial modelling. These are two of his favourite puzzles.
I’ve been setting a puzzle here on alternate Mondays since 2015. I’m always on the look-out for great puzzles. If you would like to suggest one, email me.
