In our "Proof" podcast, we set the following puzzle:
Tom employs a labourer, who is going to work for him for seven days.
Every
day the labourer wants to be paid one gold ring for each day they have
worked. So at the end of the week they should leave with seven gold
rings.
Tom has a chain with seven gold links, but cannot simply give the laborourer all seven links, because
the labourer wouldn't return. Equally, the labourer wants to ensure that
they leave every day with as many gold links as days that they've
worked, otherwise, they, again, won't return.
Tom could cut each link and pay the labourer one link per day, using seven cuts. But this wastes a lot of gold.
What is the minimum number of links that Tom must cut in order to make sure the labourer can always leave with the correct number of gold links?
What was your answer?
We can do it in one cut! Here's how:
Cut only the fifth ring.
Using these links we can pay the labourer the exact amount everyday, on the understanding that we can take back the links we've already given them.
Explicitly,
Day 1: give the 1 link piece;
Day 2: take back the 1 link piece, and give the 2 link piece;
Day 3: give the 1 link piece (the labourer already has the two, so they have three links altogether);
Day 4: take back the 1 and 2 link pieces and give the 4 link piece;
Day 5: give the 1 link piece;
Day 6: take back the 1 link piece, and give the 2 link piece;
Day 7: give the 1 link piece.
Thus, at the end of the seven days the labourer has all seven links and was never short-changed!
This puzzle relies on the fact that all the numbers between 1 and 7 can be written in binary, using three bits:
1=001,
2=010,
3=011,
4=100,
5=101,
6=110,
7=111.
Consider the extension to this problem. Tom wants the labourer to work for 15 days and has a chain of 15 gold links. What is the minimum number of cuts would he need to do now?
Think you know the answer? Comment below, tweet at us or email us at podcastmaths@gmail.com
No comments:
Post a Comment