Friday 14 February 2014

problems

Posted by speedygeoff on Friday, February 14, 2014 with
Sitting around the table the other day with a few speedygeese I posed a couple of simple problems. Simple to me, a mathematician, when viewed clearly, so I thought at least the other mathematicians/IT people there might come up with the right answers. But they did struggle a bit and some prompting was needed. To be fair, it was straight after training.

I will restate in general terms the two problems I gave them. When I posed the question to the group I was more specific (I think I chose 23 for x). The answers are below the surprisingly relevant cartoon! The problems concerned a hypothetical tennis tournament. Any number of people are allowed to enter and play in this tournament. I am the tournament manager and will allow byes only in the first round. (a) If x people enter the tournament, how many matches do I have to schedule? (b) If x people enter the tournament, how many games will there be in the first round?

So I suppose you will jump to the answers below, but have a think about it first; try some values for x to get an idea how it works. Note that x can be any positive integer.



The answers are: (a) the simple way of looking at this is that every match eliminates one player. Only one player, the winner, doesn't get eliminated. So x-1 players need to be eliminated, which is the number of matches to be scheduled. (b) Much trickier. If x is a power of 2 there are no byes and there are x/2 games in the first round. If x is not a power of 2, let y be the next power of two greater than x, then the number of players absent from the first round is y-x, the number of players actually playing is therefore x-(y-x) which is 2x-y, and the number of matches is half that. For example, a tournament of 20 players would have 12 (32-20) sitting out while the other 8 would be playing in 4 matches to decide which 4 would join the 12 for a second round of 16 players. Easy!

This is the sort of thing one thinks about sometimes when out running.