Hey folks – long time no see. I recently presented at my favorite math conference (the Mathematics Educator Apprecation Day conference) on an intersection between math and computer science, and I thought I’d write up
the gist of the presentation I wrote up the whole thing I don’t know how to be brief. Sorry / not sorry – here we go:
Some Background: A Tricky Math Standard
There’s a Common Core Math standard that I find especially tricky:
A1.F-LE.A.3: Observe, using graphs and tables, that a quantity increasing exponentially exceeds a quantity increasing linearly or quadratically
In the picture above, we see several functions growing and rising vertically as you move to the right of the x-axis. One way to interpret these graphs is: the y-position of a graph represents how much energy it took to move a certain x distance, and the window of the graph in the y-direction represents how much total energy you have. With this interpretation, functions that reach the top first are the worst in terms of efficiency – it took the maximum amount of energy to move the shortest distance. In the picture above, the exponential function used up all of its energy around 35 units on the x-axis, the quadratic function runs out of energy around 40 units, and the linear function runs out of energy around 100 units.
One thing that’s curious about this standard is that your choice of window matters. These same functions, at different windows, tell different stories:
In the first graph with a 10×10 window, it looks like the linear function is the worst – it uses up all of its energy by the end of the picture, while the other functions still have energy left. In the 20×20 window, it looks like the quadratic function is the worst because its growth started to “catch up” with the linear function. In both of those early graphs, the exponential function is the best and barely growing at all – but, as you zoom out to 100×100, you see the exponential function eventually grows so steep that it quickly outpaces the other two.
But – this picture is just for 3 arbitrary functions I chose. Maybe there’s a different choice of functions with different coefficients that create a different picture? Maybe there’s a version where the exponential graph is always more efficient than the others? Spoiler alert – there isn’t.
In my opinion, this is the trickiest part of the standard: for any linear, quadratic, or exponential equation: eventually you can find a window that shows this picture where the exponential is worse than the quadratic is worse than the linear. It doesn’t matter the coefficients of the equations or the base of the exponential (well, as long as it’s >1): eventually the exponential is the worst and the linear graph is the best.
Trying to teach this standard essentially requires students to compare and contrast 3 different function families, which means there needs to be a reason for us to care about 3 different function families happening simultaneously. Ultimately, I’d love to get to a place where showing students this graph feels earned and relevant and we can have meaningful conversations about the story being told here. And (in my opinion) that can be kind of rare outside of arbitrary, contextless exercises.
Connecting to Computer Science
But – it turns out all the things that make this standard awkward are things that computer scientists do pretty regularly. It’s part of a general body of analysis around algorithm efficiency: you have several algorithms or programs that all solve the same problem but you need to know which one does it the fastest or most efficiently. Trying to sort numbers is a good example of this: the end result is the same every time (a bunch of numbers in order), but the path we take to get there can look very very different with some going faster than others. Check out this quirky video of different sorting algorithms to see what I mean:
In these situations, its common to encounter different function families that correspond to different implementations. It’s also common to ask “What happens as the size of your problem gets bigger? What happens when you add just one more element?”, which is analogous to adjusting the window of your graph and seeing how your functions behave.
This type of algorithm analysis shows up in several computer science courses, and in my job as a curriculum writer for Code.org I happened to be looking at two lessons in this area from their AP CS Principles curriculum: Algorithm Efficiency and Unreasonable Time. Both lessons are framed around different types of lotteries and rules for winning, where each version of the lottery corresponds to a different function family. The computer science standards don’t require students to dive too deeply into the math, but since I was presenting at a math conference, I saw an opportunity to adapt the ideas in these lessons so they could also be used to hit the standard at the start of this post.
One last thing before getting to the activity: what follows wouldn’t’ve been possible without Jeff Olson’s (@jolson_codes) Tool to Teach Binary Search. I’ve used this in my computer science classes before; it’s amazing; and it’s pretty much a lottery clicker game already. I saw an opportunity to remix his work to create different versions of the lottery game that you can play online. So, as you keep reading and play with the widgets below, credit to Jeff for laying the foundation that I could build off of.
Lottery Activity #1
Imagine a group of people have entered a lottery and the winning number has been drawn, but each person is keeping their ticket hidden. Your job is to find the winning ticket or prove there is no winner in the least amount of time (measured by clicks).
You can start by playing this version: https://dancodedotorg.github.io/lottery-ticket-games/index-1.html. Go ahead – pause reading this post – give yourself a few minutes to play the game. Play multiple times – try to get a really low score. What do you notice? What do you wonder? What strategies can you find?
Did you play a bunch? Cool cool. Because I’m about to spoil this version of the lottery game.
Hopefully you noticed that the tickets are always in order. And because they’re in order, you can eliminate half of them with each guess. That’s cool – there’s strategy involved; it doesn’t have to just be “click everything randomly”.
In the computer science world, there are two questions we tend to ask when looking at strategies:
(1) What’s the best theoretical score and what would need to occur for that to happen?
(2) What’s the worst theoretical score and what would need to occur for that to happen?
(take a second to think about these if you want)
The best score isn’t super interesting – it’s 1 and it happens when you get super lucky and guess the number correctly the first time.
The worst score is a little more interesting – it happens when the number is your very last guess or (more generally) when there is no winning lottery number. When we use the halving strategy, the total number of guesses we need is the same as however many times we need to take half of our tickets until there are none left. For 21 tickets, this looks like 21 –> 10 –> 5 –> 2 –> 1 –> 0 where each –> represents clicking on a ticket to reveal the value and then eliminating half of the choices. Since there are 5 arrows, means you can always find the winning number or prove there isn’t one in at most 5 clicks. Sidenote: Algebra II and beyond teachers might notice an interesting connection between this strategy and base-2 logarithms.
Lottery Activity #2
Great – but: having all the tickets in a sorted order isn’t very realistic. It’s more realistic to have just a pile of tickets on your table that you need to go through. Here’s what this version of the lottery looks like: https://dancodedotorg.github.io/lottery-ticket-games/index-2.html
This version is less fun and the strategy is less interesting. The best theoretical possibility is still the same – getting lucky on the first click. The worst theoretical possibility is worst than before: since the tickets are out of order, you have to click every single one before you can be sure that the winning ticket is or isn’t there.
But, there’s a new interesting question we can ask. Imagine we checked all of our tickets and didn’t find a winner. But, because we’re so unorganized, we discovered one more ticket hidden underneath some napkins or laundry or something else. Now that we have this one more ticket, how many new possibilities do we need to check to see if we have a winning ticket?
Turns out it’s super easy – barely an inconvenience. We just have to check this one extra ticket. In general: every time we add a new mystery lottery ticket, the number of tickets we need to check goes up by a constant amount of 1 every time. In fact, it’s the most boring linear function: f(x) = x
Because this version of the lottery wasn’t super interesting, let’s make it more interesting by changing the rules a bit
Lottery Activity #3
In this version of the lottery, you need to combine your ticket with one other ticket to form the winning number. In other words: pairs of lottery tickets are required to match the winning number. And if you have a pair of tickets, both people win. Here’s this version of the lottery to play around with: https://dancodedotorg.github.io/lottery-ticket-games/index-3.html
Quick pause: there are ways to implement this version in a classroom with students, such as using this Lottery Ticket app that students can pull up on their phone. Imagine having students generate a lottery ticket, then displaying a randomly generated winning number, then telling them they need to see if there’s another person in the room where your number + their number sums to the winning number. These moments of controlled chaos were some of my favorites in the classroom, especially since the experience of physically trying to find someone else whose number can pair with yours really grounds the analysis that comes next.
One nice thing about this version is it re-introduces strategy – for example, you can immediately eliminate any tickets whose values are already greater than the winning number. You can also have some conversations about iterating based on trial and error – for example, picking two numbers you think might be close to the winning number and adjusting your guess from there. If the sum was too high, look for a way to lower one of the numbers in your pair; if the sum was too low, look for a way to raise one of the numbers in your pair.
Because we’re looking at pairs, the analysis of this lottery looks a little more complicated. Here’s one way to represent the worst case prove-there-isn’t-a-winner scenario with 5 tickets:
Each blue connection represents a different possible pairing. Since there are 10 connections, as a worst case, we need to check all 10 possible pairs.
Similar to last time, we can ask what happens if we discover we accidentally forgot 1 ticket and need to add it to the mix. Or, if you’re doing it with students, a student arrives late and generates a new lottery ticket – how many new possibilities do we need to check now?
This time it’s more interesting – adding just one more ticket means the number of possibilities we need to check has increased. In fact, it includes all of the previous possibilities plus a new connection for each of the previous tickets. In general, this pattern looks like this:
There’s some interesting stuff to notice here. In our worst case column, the difference between each worst case is also increasing. And, curiously, if you take the second difference, you see that second difference is constant. And whenever the second differences in a table are constant, it means you’re looking at a quadratic function.
Specifically, this growth pattern looks like 1 + 2 + 3 + 4 + 5 + …, which is the triangular numbers sequence. There are lots of ways to analyze this series visually and arrive at the specific formula, but it turns out in this table that the function we’re looking at is n(n-1)/2. Which is indeed quadratic and matches our table analysis – whooo!
Lottery Game #4
Ya know – why limit ourselves to just pairs? Let’s play a version where any combination of tickets can be combined to get a winning number: https://dancodedotorg.github.io/lottery-ticket-games/index-4.html. Note: I recommend playing with 5 tickets instead of 21…
Trying to figure out the worst case for this lottery is a game of investigating combinations. For 5 tickets: how many 1-ticket possibilities are there? How many 2-ticket combinations are there? How many 3-ticket… 4-ticket… and 5-ticket combinations are there? Here’s what that looks like visually:
If you’re having students physically walk around the room and try to find matches, this kind of visualization can develop naturally from that type of interaction. There are also lots of explorations to go off of depending on your subject area (Pascal’s Triangle… combinatorics and n Choose r… etc).
Again, things get interesting when you ask “What happens when someone new comes along? Now how many lottery tickets do we have to check?”. And boy of boy – it’s a doozy.
Here’s where I try to explain the purple parts of the image above. When we add a new ticket, we have to add it to every possible combination we’ve discovered so far. You can imagine this as taking each original combination, then adding this new ticket to the end of it. This effectively doubles the amount of possibilities. And, we also have to check the ticket on its own, which is just 1 more possibility to test. If you were to express this pattern as a sequence, term n+1 = 2(term n) + 1. Or as a table, it’d look like this:
Since we’ve been looking at differences in tables this whole time, we can do the same trick here. And when we do, we see a multiplicative relationship – the differences are doubling each time. And whenever we notice this pattern in a table, it means we have an exponential function.
Quick Sidenote: Asking “how much more complex does this get when you add just 1 more term?” and seeing the exponential growth relationship has a familiar computational analogue: it’s how password security works. Every time you add a new character to your password, you’re not adding to how long it will take someone to crack your password, you’re multiplying how long it takes someone to crack your password. A fun exercise is to go to How Secure Is My Password? and start typing in long passwords. Eventually you notice that each new character adds days, then weeks, then months, then years, then decades to how long it takes someone to crack the password.
At this point, we’ve looked at 4 lottery games and done some deeper mathematical analysis on 3 of them. Ultimately, the goal is to get to a place where showing students a graph with a linear, quadratic, and exponential function feels earned and relevant and we can have meaningful conversations about the story being told here. And I think we’re there:
It’s been a long road, but at this point this graph should have meaning beyond just three different function families. The red linear function represents the random-order lottery game, the blue quadratic function represents the pairs lottery game, and the green exponential function represents the the all-combinations lottery game. Depending on how this ran in class, each graph may also represent a specific student experience – either clicking tickets in the online widgets, or running around the room trying to find folks with winning tickets. In the Desmos link above, there’s a slider and a table where you can explore each of the functions and verify the type of growth we explored in the earlier mathematical analysis.
But – this isn’t the whole story, because we also need to motivate that it’s not just these particular functions that behave this way. We need a way to motivate that any linear, quadratic, and exponential function will eventually settle into this pattern. So – stay with me here: we introduce robots
In the same Desmos link (https://www.desmos.com/calculator/8z771gdbus) , there’s a “Secrets Shhhh” folder that expands to reveal our two robots. If we add those as coefficients to our functions, it slows their growth which represents the robots “speeding up” how long it takes to sort through lottery tickets. Ideally, we’d add them to our two least efficient lotteries like so:
The quadratic function has the purple robot coefficient, slowing it’s growth by 1/5. The exponential function has the blue robot coefficient, slowing it’s growth by 1/20. The t variable represents the number of total tickets in the lottery. The screenshot shows that with 5 tickets and these robots, the linear function is actually the slowest – by the time you finish checking your lottery, the other robots are way ahead. But, by the time you’re at 12 lottery tickets, we have a familiar story where linear lottery is the fastest and the exponential lottery takes way longer than the others:
But – that’s just with these robots. Maybe there are some other robots who can speed up or slow down the lotteries. Let’s see what happens when we assign a robot to each of our lotteries and we can adjust how fast they go. You can experiment with those robots in this Desmos link: https://www.desmos.com/calculator/za16oc3umw
The three r sliders represent the robots, and the subscript represents which lottery they’re working on. Increasing the slider represents how fast the robot works – for example, setting r4 to 10 means the robot paired with the exponential lottery goes 10x as fast as you do. The essential question is: is there a speed you can set the robots so the exponential lottery always beats the linear lottery, no matter how many tickets there are? Spoiler alert: the answer is no. And because the answer is no, it means we’ve used graphs and tables to show a quantity increasing exponentially exceeds a quantity increasing linearly or quadratically (hey! That was the standard from the top of this post! We did it!)
Wrapping Up This Post
It’s a long road and there’s lots of potential detours along the way, but ultimately we’ve got several lottery games that can be used to analyze different function families and several opportunities to get students investigating these lotteries, either through the online widgets or in-person using a lottery app. I originally presented this at the MEAD conference – here are the slides from that presentation, but this post ended up being more in-depth than the slides were. Hope it sparks some new ideas. Maybe there’s some Desmos Activity Builder magic that could happen to make it more streamlined?