why you can't order 43 nuggets.

Added: 2026-05-12

[00:00:00]Today we're going to look at a famous version of a classic combinatorial number theory problem. And this is offhand known as the chicken McNugget problem or the chicken McNugget theorem.

[00:00:11]And so it's based off of this fact. I don't know if this fact is true anymore, but at least at one time McDonald's sold McNuggets in quantities of 6, 9, and 20.

[00:00:23]And then the question goes like this. Is there a largest number of nuggets that you cannot achieve just with those three orders? And if there is a largest number, what is it? So, let's analyze this a couple of different ways. We're going to start with a warm-up problem.

[00:00:41]And then we'll look at a simplified version of this setup. Simplified in that there are two different types of orders, but actually generalized in that we allow any two types of orders. and then we'll circle back to our main problem here. Okay, so let's look at the following warm-ups. Let's say that we only have the possibility of sixnugget and nine nugget orders. So in other words, you can't order 20 at a time.

[00:01:10]Well, let's see which ones are possible with just six and nine nuggets. And this is pretty easy to see. Obviously, you can order six nuggets or nine nuggets.

[00:01:23]That's just a single order of each. You can also order six plus six or 12 nuggets. That would be two orders of the six nuggets. You can order 6 + 9. That would be one of each. So, that's 15. You can get 18 nuggets two different ways, as three six orders or as two nine orders. So, there's 18 as a possibility.

[00:01:47]And now you can see that you can just add six to any of these numbers and achieve any multiple of three. So if we add 6 to 15, we'll get 21. If we add 6 to 18, we'll get 24. So on and so forth.

[00:02:01]So here we have 21, 24, 27, 30 as possible and so on and so forth. But let's observe that we essentially or not even essentially we get every multiple of three um past six.

[00:02:19]But what is three in terms of 6 and 9?

[00:02:22]Well, it's the GCD. So, we get every multiple of the GCD of 6 and 9 as long as we've got gotten past this like starting point of six. And so kind of obviously three is not achievable which would be the only other multiple of three that's off of this list. And now which ones are impossible? Well, I think it's pretty easy to see that nothing that is not on this list is is possible.

[00:02:50]So if you have a non multiple of three, well then you cannot achieve a non multiple of three using two multiples of three. And then like I said before, you can't get anything smaller than six for obvious reasons. So now let's say what about using six and 20 orders? Well, we could analyze this the same way, but I'm going to actually simplify it a little bit to just to highlight something that's happening more generally. And I'm going to divide both of these by two.

[00:03:19]And I'm dividing both of them by two because that's the greatest common divisor of six and 20. But we can really just think about this as orders of three and 10, but they're orders of pairs of nuggets. So our units are not nuggets anymore. There are pairs of nuggets. So I'll just say here three and 10 pairs of nuggets. So let's see what's possible here. And just keep in mind that what we're talking about being possible is orders of pairs of nuggets. So let's observe that we can order 3 6 and 9.

[00:03:56]That's just 3 * 1, 3 * 2, and 3 * 3. We can get 10. You can do like an exhaustion thing and see that it is impossible to get 11, but you can obviously get 12. You can get 13 because that is 10 + 3. You can get 15 because that's going to be a multiple of three.

[00:04:19]You can get 16 because that's 10 + 3 + 3. You can get 18 because that's a multiple of 3.

[00:04:29]And in fact, after 18, you'll see that everything is possible. 19 is possible because we can get 9 + 10. 20 is possible because we can get 10 + 10. 21 is possible because let's see, that's just going to be seven orders of three.

[00:04:48]And then 22 is possible because we already know that 12 is possible. And then so on and so forth. And so I'll let you like work out some more if you feel like that's necessary. But I think it's kind of getting pretty clear that we can get everything after this. So in other words, if we can get everything after that, then we can easily see the smallest one that is missed or I guess I should say the largest one that's missed is 17. So 17 is impossible. Now this doesn't mean that you can make every order of nuggets because remember that these are pairs of nuggets. We would really have to scale this up. And so that means that we would have a possibility of 6, 12, 18, 20, 24, so on and so forth. And we would actually miss every odd number after that point right there. And let's see, the largest even number that we could not achieve is 17* 2, which is 34. So, now that we've kind of done these warm-up problems and highlighted this important fact that perhaps it's nice to look at numbers that are relatively prime that have GCD of one because those seem to allow us to achieve everything after a certain point. Let's look at some definitions and then we're going to prove a couple of more general results before we loop back to this main question. So here's a definition just to simplify our jargon.

[00:06:19]If a and b is bigger than one with gcd of ab being equal to one, let's define something called the frobinius number of a and b. And we'll use the notation g of ab and that will be equal to the largest positive number that is not of the form ax + b y where x and y are bigger than or equal to zero. And we can easily extend this to the Fbinius number of a, b, and c, which would be the largest positive number not of the form ax plus b y + c z. And you could extend it to more numbers in a obvious way. And so here's a big theorem that will guide us for this simplified version of our problem. And that is that this froinius number of a and b g of ab is equal to ab minus a minus b. And let's observe that that corresponds with what we've already seen. Notice that by just calculations we saw that g of 310 was equal to 17.

[00:07:22]That was the largest number that was not of the form 3x + 10 y. And that's also equal to 3 * 10 - 3 - 10. pretty obviously. And so we've got two things to prove. The first thing to prove is that a b minus a minus b is not achievable. And then we'll show that everything above that is achievable.

[00:07:46]Okay. So how are we going to show that this is not achievable? Well, we're going to do this by way of contradiction by supposing that it is achievable. So let's suppose we have some numbers x and y. they're bigger than or equal to zero with ax + b y or maybe we'll write it like this a minus a minus b is equal to ax + b y. So in other words, we've written a minus a minus b in the correct form. And now what we'll do is reduce this thing mod a and mod b and get some information out of those reductions and then loop that back into our equation.

[00:08:27]So here is our mod a reduction. Remember that that just means that we're going to divide by a and keep the remainder. So let's see that's going to give us b * y is congruent to well let's what's going to be left over here? It's going to beb modulo a. And so I swapped my left and right hand side, but I think it's pretty clear that that's what we're going to get because AB, A, and Ax are all multiples of A. But now the GCD of A and B is one. But that means that B has an inverse mod A. That's a pretty standard number theory fact. So that means that Y is congruent to -1 modulo A. But in other words, we can write y as let's see a * m -1 where m is bigger than or equal to 1. Observe that we have to have m bigger than or equal to 1 because y is supposed to be bigger than or equal to 0. But if m is 0 or smaller that will make y negative. So now let's move on to a reduction modulo b and see what we get out of that. So that's going to give us this. We'll have ax is congrent to minus a modulo b for essentially a parallel argument to what we had before. But that's going to give us x is congrent to -1 mod.

[00:10:02]Or in other words, we have x is equal to b * n -1. And again, we know that n is bigger than or equal to one for essentially the same reason that we had before. So now what I want to do is loop all of these things, or I guess not all of these things, these two equations back into this equation up here and see what we get. So maybe I'll swap the order of that equation. So, we're going to have a * x, but notice that x is b * n -1 + b * y, but y was a * m -1 is equal to a b - a - b. Okay, great. But now let's multiply some things out and let's observe that we have a b and then m + n minus a minus b is equal to a b minus a minus b. So I multiplied out the left hand side and then I did a little bit of regrouping.

[00:11:04]But check it out. We have this a minus b or minus a minus b cancing on both sides of the equation. And then we can divide both sides of this equation by a b. But that's going to give us m + n is equal to 1. But let's observe that that's impossible because we know that m is bigger than or equal to 1 and n is bigger than or equal to 1. But if m and n are both bigger than or equal to one, then m + n is bigger than or equal to two. But a number can't simultaneously be equal to one and bigger than or equal to two. So we've got our contradiction contradicting this assumption right here that our number a minus a minus b was achievable or representable of the form ax plus b y. Okay, great. So let's see.

[00:11:58]We have taken care of this first thing that we need to prove to prove that g a b is ab minus a minus b. Now let's look at the second thing which is to prove that everything bigger than this ab minus a minus b is achievable. Thanks for sticking around this long into the video. If you're enjoying the video, make sure and give it a thumbs up. And if you're not yet subscribed, consider subscribing. It really helps out. We're zooming in on 350,000 subscribers and I think it'd be great if you helped us get there. Okay, so now we're going to show that if n is bigger than a b minus a minus b, then it's achievable. But if it's bigger than this number, then it has to be bigger than or equal to 1 + that number. But that can factor as a minus1 * b minus 1. Perhaps that will be helpful. So let's now that we have or let's suppose that we have an n bigger than this cutoff or I should say bigger than or equal to one more than this cutoff. I'll write it like that. So now what we want to do is pick some number y and I'm going to say that that y is between 0 and a minus1 and it's going to satisfy the following congruence and it's going to be congruent to b inverse * n modulo a. Now you might say well how do we know we can do that? Well notice that b is relatively prime to a. That's one of our assumptions. So that means it has an inverse mod a. We just multiply that to n and that's going to give us some residue class modulo a. But everything that's a residue mod a can be in this form right here of a number between 0 and a minus one. So it's as simple as that. But now that congruence can be rewritten as b * y is congrent to n modulo a. But now we can rewrite that as a little bit of an arithmetic problem.

[00:14:05]That means that n minus b * y is congrent to 0 modulo a. But if it's congrent to 0 mod a, it is a multiple of a. So that's going to be equal to a * x with x being some integer.

[00:14:25]Good. So again, that's exactly the same thing as this right here. Now, what is going to finish this thing off? Well, I'll just put that right here as our want. And what will finish this thing off is if we show that x is bigger than or equal to zero. Because if x is bigger than or equal to 0, then moving some things around gives us ax + b y is equal to n. And notice that x and y will both be bigger than or equal to zero. If we can show that x is bigger than or equal to 0. Recall that y was already chosen to be bigger than or equal to 0. So how can we do that? Well, let's observe the following calculation. We have ax is equal to n minus b * y. But let's bring a bit of an inequality into this. So this is going to be bigger than or equal to a -1 * b -1.

[00:15:26]and then minus a minus1 * b. Now, you might see not see where all of those inequalities come from, but let's lay them out over here. This is because our n is bigger than or equal to a minus1 * b minus one. And then it's because our y is between 0 and a minus one. But that means that negative y is between a minus one and zero. So that's why you get this thing right here. But now we can uh pretty easily see that if we were to multiply all of this out and then add or combine some things together, we get that this is equal to a or a + 1. But let's cut out the middle here and observe that means that ax is bigger than or equal to minus a + 1. So we've got a multiple of a that's bigger than a + 1. Now you might already see why this tells us that x is bigger than or equal to 0, but let's just lay it out uh in a lot of details just in case. So let's put some multiples of a on a number line. So we've got here this zeroth multiple of a. Then we've got a, we have 2 a, we have 3 a, so on and so forth in that direction. Back in this direction, we have a, we have -2 a. Obviously, back here we have -3 a. So on and so forth.

[00:17:03]So where is a + 1? Well, that's going to be right here. So negative a + one is right there. But observe that we've got a multiple of a which is bigger than a + 1. But if it's bigger than negative a + 1, look at all of the multiples of a that are bigger than a + 1. They're simply 0 a 2 a 3 a so on and so forth.

[00:17:33]But that would correspond to x being bigger than or equal to zero as needed.

[00:17:40]Okay. So we've done it. We've proven that not only is this number a b minus a minus b not achievable but everything larger than it is achievable which is exactly what we needed to do to show that g of ab the frobinius number of a and b was a minus a minus b. So now that we've done this smaller but more general problem let's loop back and see what we can say about our original question. So before diving into our question over here, I'd just like to point out that it was proven by Curtis in 1990 that for general natural numbers a b and c bigger than one, the frobinius number of them which we were using the notation g of a b c cannot be built from poloms in a b and c. So that means that it was proven that it's not equal to a polomial in a b and c or a peace-wise function defined by polomials or a b and c or some other forms that were listed in the main result and in fact there's no known closed formula and well this shows that if there is a closed formula it won't look like a polomial and so it's really unknown what this general thing looks like. Okay, so now back to the main problem, which is this question right here. What's the largest number of nuggets that cannot be ordered? And we're going to prove that the largest number of nuggets that can't be ordered in our new notation g of 6 920 is equal to 43. And so that means that we're going to need to prove that 43 is not achievable, not orderable, but everything bigger than 43 is orderable.

[00:19:25]Okay, so let's start with 43 not being achievable. And so let's by way of contradiction suppose that it is. So let's suppose that we have xy and z which are bigger than or equal to 0. And we have 6x + 9 y + 20 z is equal to 43.

[00:19:49]And so now we're going to take turns reducing this thing mod 2 and three to get some forms of y and z and then run this back through the equation. Okay, so let's first reduce this thing mod 2. But let's observe 6 and 20 are even so. So those are 0 mod 2 and 9 and 43 are odd.

[00:20:12]So those are 1 mod 2. So that tells us that y is congrent to 1 modulo 2. But that means that y is equal to 2 * m + 1 where m is bigger than or equal to 0.

[00:20:28]It's got to be bigger than or equal to 0 because we want this thing to be a non- negative number. Okay, great. But now let's reduce this thing modulo 3 and see what we get out of that. So that's going to give us let's see 6 and 9 are congrent to 0 mod 3. They're multiples of three. 20 is 2 mod 3 because it's two more than 18. So we have 2 z is congrent to 1 modulo 3. Now that's because 43 is one more than 42 and 42 is a multiple of three. Okay. So now this means that z is congrent to 2 mod 3 because the inverse of 2 is itself mod 3. But this means that Z can be written as 3 * N + 2 and N is bigger than or equal to 0. All right.

[00:21:23]So now we're going to loop this version of y and z into our equation and see if anything goes wrong. So let's start over here with 43. That's going to be equal to 6x + 9 y. But we're going to write y as 2 * m + 1. and then plus 20 z. But we're going to write z as 3 * n + 2. But now let's multiply everything out.

[00:21:51]That's going to give us 6x + 18 m + 60 n and then plus we have 9 + 40 49.

[00:22:04]But recall that x, m, and n were all bigger than or equal to zero. So this is bigger than or equal to 49.

[00:22:11]But that's a clear problem. We have 43 is bigger than or equal to 49 giving us a contradiction. Contradicting our ability to represent 43 with 69 and 20.

[00:22:27]Okay, so 43 is impossible. Let's prove that everything else is possible.

[00:22:32]Everything bigger than 43 is possible.

[00:22:34]Okay, so now we're going to show that if n is bigger than or equal to 44, then it is achievable. But let's observe that if n is bigger than or equal to 44, we can find a k bigger than or equal to 0 where n is expressible as 44 + 6k, 45 + 6k, 46 + 6k, so on and so forth to 49 + 6k.

[00:22:54]Notice that we don't need 50 because 50 is equal to 44 + 6. We don't need 51 because that's 45 + 6. So on and so forth. And so now the game is essentially just to express 40 through 44 through 49 as a linear combination of 69 and 20 and then absorb the 6k into the six part and then we're done. And so let's do this perhaps for 47 then I'll fill in a couple more and then I'll leave others as homework. Okay. So 47 can be written as let's see it's going to be 6 * k + 9 * 3 + and then we have 20 * 1. So let's just verify that that's going to be 47 right here plus 6k. So that's good. Now what about this one up here? So we can write this as 6 * k + 4. So observe that's going to be 6k + 24. But that leaves a 20 left over. So that's going to be 20 * 1. We could put a 9 * 0 in there if we wanted to just to fill it all out. But let's not do that. Now what about 6k + 45? Well, that's pretty easy. This is just 6k + 9 * 5. And then well, what's one more interesting one? Well, let's look at this one at the bottom. This can be written as 6k + 9 * 1 + 20 * 2 because 49 is pretty clearly 9 * 1 + 20 * 2. We're just left with the 6 * k. So, I'll leave it to you to fill in these other two to finish off this proof. But needless to say, we have proven that 43 is the largest number of nuggets that cannot be ordered in quantity of quantities of 6, 9, and 20. And that's a good place to