The Magic of Logic (11)
A fine late summer day, sunny and warm. The grandkids are back from a two-week holiday in Italy. The family has been very cautious, but we have to keep distance for a while. Time for a little logic.
In Covid-19 times, their parents have insisted, we have to avoid infection: them infecting us! I explained: if you, grandkids, have caught the virus in Italy, chances are you will have no symptoms, or just sniffles and a sore throat. In very rare cases it may become serious, and they will take you to hospital. On the other hand if I or their grandmother catch it from you, it will be the other way around: chances are we will have to go to hospital, maybe to intensive care.
So what can can do on this beautiful day is social distance in the garden, and discuss some logic and science. I came equipped: my dear friend Christian Hesse now supplies me with new puzzles, which we tune to the level of seven and eight-year-olds. Today's problem was the following:
You are organizing a tennis tournament, with eight players. How many matches will take place, in total?
We need to know how many times a court needs to be prepared. Enders and Hennes worked that out quite easily: we start with four matches, the four winners play two matches, and then there is a final between the two winners. So seven matches in total.
Okay, so we want to organize a tournament with 64 players. How many matches? Hennes decided that was too hard for him, while Enders strolled around counting: 32 + 16 + 8 + 4 + 2 +1 = 63! Not easy to do in your mind.
But now came the next question: you want to run a tournament with one thousand and 24 players. How many matches? Big sigh. Enders embarked on the task of adding the numbers: 512 matches plus 256 plus 128… too hard to work out in the garden without paper and pencil. So I told him to think about the previous tournaments we had solved. After a short while he said. “1023 matches?” Correct! And just to make sure: how many matches is 10,000 players start the event? 9,999 he replied immediately.
But there are a couple of questions to resolve: why is it one match less than the number of players? I tried to explain it in the way Christian had suggested: each player is knocked out in one match, except the winner. So we need to stage n-1 matches to eliminate all but one of the players. They cannot be knocked out in less matches. But, Enders said, a player who is knocked out may have played more than one match. He might have won two or three matches before losing. So it could be more than n-1. No, because in each of the matches he won a player was knocked out, and it counts for them. We tested it with sixteen players, and in spite of player A winning all his games until the final, the number of matches conducted is 15. Eureka!
But now the question remained: all this works perfectly for powers of two: 16 = 2⁴, and 1024 is 2¹⁰. But what about other numbers? We figured that out as well. If seven players start there are three matches and one of the players gets a “bye”. In the next round he joins the three players who won, and there are four players taking part in two matches. The two winners play each other, so the total number of matches is 3 + 2 +1 = six matches. We tried it on ten: five matches to start, then five players left. Four of them play two matches, and one gets a bye. Two of them win, one gets a bye, and he plays against the winner of the next match. Makes 5 + 3 +1 = 9. It always works out to n-1. I think Enders got it all, and was quite pleased with the problem. Thank you, Christian, keep them coming.
Before we left we swept the driveway of the very large number of acorns that covered the ground around the giant oak tree. And doing this we discussed a little science problem: why do oak trees sometimes produce ten times as many acorns as normal? And why do they do this every sixth year (here in Germany)? I will tell you the answer, as I explained it to the kids, in a separate article.