Tournaments and Logs
With the NCAA basketball tournaments kicking off, here is a post about an exercise I put together for our pre-calculus class last semester on tournaments and logs. I find a lot of students do not have a good intuitive grasp of the logarithm function and why it might be useful. This exercise actually originated when my son was around 5 and began racing his toy cars. (See the video above – it was hard to determine the winner by eye so we filmed it and ran the finish in slow motion; you can freeze-frame it at around 0:02 to see who won.) He started collecting matchbox cars and when he got to 16 of them, I suggested he do a tournament. This kept him busy for a while. A few days later he came back to me, puzzled, saying “How do I do that thing with the cars if I have 23 of them?” So now we had to enter the world of byes or play-in rounds. This led to following “workshop” I ran for my pre-calc students. We had just covered exponential and logarithmic functions. I paraphrase the assignment below with some explanation. For the actual handout I used, click here.
Workshop: Set up a Tournament using Logarithms
Assume a single-elimination tournament with winners advancing to another contest while losers are eliminated, repeating until only one team is left.
the number of competitors, n
Devise a procedure to indicate:
- the number of rounds in the tournament, r
- the number of byes in the first round, b
As to what meant by “procedure”, I gave some direction, but not a lot, saying it should consist of short, simple steps mostly involving mathematical operations. Students are certainly used to following procedures, methods, algorithms, etc. but seemed a lot less comfortable coming up with one themselves.
I split my students into groups of around 3 to work on this. It didn’t take long for them to figure out that for 16 teams there are 4 rounds, for 32 teams there are 5 rounds, for 64 teams there are 6 rounds, etc. And so in general 2r = n as long as n is a power of 2. If n is not a power of 2, they realized that some kind of byes are necessary. I provided an example of this with 5 teams on the handout for the exercise. Some groups started to realize the importance of the power-of-2 numbers near the number of competitors.
Using these ideas, one group emerged with the following step in their procedure: “Round n up to the nearest power of 2.” That’s a great start, and isn’t hard if we know our powers of 2. But what if we want to automate the process, i.e. use a computer? For instance, what’s the command to “round up to the nearest power of 2” in Excel, Mathematica, c++, etc.?
With a little encouragement, some groups began to consider using the function log2x in their procedures. It dawned on them that they could solve for the number of rounds in their formula 2r = n by taking logs: log2n = r. In other words, the number of rounds in this kind of tournament is equal to the log2 of the number of teams, assuming n is a power of 2. If not, one can round up by taking the ceiling of log2n (i.e. let r = ceil(log2n)) and that gives the total number of rounds with some teams receiving first round byes.
How many byes are there? To figure this out, note that after rounding r upwards there are 2r slots for n teams. Teams with byes effectively take up 2 slots in the first round, # of non-bye teams is n – b, so totaling the slots we have 2b + (n – b) = 2r, and solving for b yields b = 2r – n.
Putting it all together, here is one procedure that will work:
- y := log2n
- r := max (y, ceil(y)) ( = y if y is an integer, = y rounded up if not )
- b := 2r – n
Some of the student groups made it this far in the 50 minute class period. So that was good. Others struggled with the whole exercise.
There are a lot of variations on this kind of workshop. Here are a few ideas:
- Cut-throat tournaments in which 3 competitors vie in a contest, instead of 2 (e.g. “21” basketball game, cut-throat racquetball, …).
- Simple exponential population models to illustrate inverse function relationship of the exponential function and logarithmic function.
- For instance, a cellular organism divides into 2 every 15 minutes. Say we start with 34. A little later we have 272 (or maybe 261 – what other assumptions might we make there?). How long did that take?
- You can solve the previous problem without using logs by doubling. But the doubling method doesn’t scale well. Consider this variation: Start with just 2 organisms. Suppose a bit later on, there are 68,720,000,000. How much time has passed? Do you really want to double 2 up to 68 billion? (Answers at the end of this post.)
The NCAA men’s basketball tournament now consists of 68 teams. So the calculation goes like this:
- y := log2(68) ~= 6.09
- r: = max(y,ceil(y)) = max(6.09,7) = 7 — so 7 rounds
- b: = 2r –n = 27 – 68 = 128 – 68 = 60 — so 60 byes
The other way of looking at it is 68 – 60 = 8 teams “play in”, the so-called “First Four”. These just happened – Cal Poly, Tennessee, Illinois, and Albany won, so now we’re at a power of 2 number of teams from here on out.
Hopefully this kind of exercise can help build intuition about log functions. If you double something up to a higher number, log tells you how many doublings there were. Start with one winner from a contest of two, and those two were in turn each winners from contests of two, and so. Doubling your way up gives you the number of times you’ve doubled, which is the number of rounds, and is given by the log2 of the number of teams you end up with.
The handout for this workshop is available here. Feel free to use it and let me know if it ends up being useful.
I think the main thing my 5-year old took away from this was that there were these “special numbers” that made setting up the tournament simple. So his plan was to work up to 64 matchbox cars, then maybe even 128.
Answers to exponential population questions: 45 minutes; 9 hours