The Chicken McNugget Theorem Applied to a Piano Problem

Here’s a question from the AMS 2020 Who Wants to Be a Mathematician Championship Finals:

Candidate Luke Robitaille answered 20 seconds after the host finished reading the question. Can you figure out the right answer?

Answer: E

Luke explained that every key was accessible from middle C if we can jump in 5 and 7 note increments either direction. He quoted something called “The Chicken McNugget Theorem”, which I had never heard of.

What is the Chicken McNugget Theorem?

Let’s take a quick detour to learn what this theorem is.

Some Googling took me to https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem, which says:

First, let’s make sure we can apply this theorem from the conditions stated above.

• 5 and 7 are both relatively prime, meaning they don’t have any common divisors greater than 1.
• 5 and 7 are both positive.

Let’s break it down, using an example of chicken nuggets. Say McDonalds only sells chicken nuggets in boxes of 5 or 7. So I could get 10 nuggets by buying two boxes of 5, or 12 nuggets with one box of 5 and one box of 7.

There’s clearly no way for me to buy just one nugget, since the smallest unit is 5 nuggets. Similarly, there’s also no way for me to just buy 16 nuggets, since there’s no way to combine 5 and 7 to get 16.

This theorem is telling us what the *largest* such number is that cannot be composed of the smaller units — it’s mn-m-n, which is 35–7–5, or 23.

Let’s test it out!

• How would we get 24? We could do 2 boxes of 7 (14 nuggets) and then 2 boxes of 5 (10 nuggets).
• How would we get 25? We could do 5 boxes of 5.
• How would we get 26? We could do 3 boxes of 7 (21 nuggets) and then 1 box of 5 (5 nuggets).

Cool, empirically seems to work. I won’t go into the proof, but you can read it here: https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem

How does the Chicken McNugget Theorem apply to this problem?

Luke explains, “You can go far enough to the left and far enough to the right and eventually you can get anywhere… anything more than 23 you can make of 5’s and 7’s. If you want to hit something on the right, you can go far enough to the left and then use the Chicken McNugget theorem, or vice versa.”

I had to take a moment to process this:

• 1/ We start at middle C on the keyboard, and there are 88 keys.
• 2/ If we jump “far enough” (i.e. more than 23 keys to the left), then by the Chicken McNugget theorem, we can get to all the keys to the right (imagine instead of keys they’re just numbers; we can compose the values 24, 25, 26, and so on).
• 3/ If we jump “far enough” (i.e. more than 23 keys to the right), then by the same reasoning above, we can get to all the keys on the left.
• 4/ This means that we can reach every key, and actually the “starting at middle C” isn’t necessary information! (e.g., if we started at the first key, or the last key, the above reasoning would still apply).

Hope you found this interesting (and aren’t craving nuggets now)!

For more articles like this, follow me on Medium. Not a member yet? Join the community. Want more software engineering interview guides and coding question tips? Check out all of my writing organized by topic in this article.

If you have any requests for what I should write, please let me know!