Chicken McNugget Theorem: trying to find way on checking that it's possible up to 150

[apple2357]

So McDonald's sold its nuggets in packs of 9 and 20. Math enthusiasts were curious to find the largest number of nuggets that could not have been bought with these packs. It turns out this is 151 and there is a theorem ( called Chicken McNugget theorem) that can prove this. Google it,if interested!

I am more interested in trying to find a way on checking that it is possible up to 150. Clearly, i could use a spreadsheet and systematically check all cases but is there another way?
So for example, is it possible to get 46
This would mean 9a+20b = 46 for some positive integer a, b ? Do i just guess?

 

[Denis]

So for example, is it possible to get 46?
This would mean 9a+20b = 46 for some positive integer a, b ? Do i just guess?

a and b can also = 0
If you buy 27 nuggets: 9*3 + 20*0 = 27
If you buy 40 nuggets: 9*0 + 20*2 = 40

 

[Dr.Peterson]

So McDonald's sold its nuggets in packs of 9 and 20. Math enthusiasts were curious to find the largest number of nuggets that could not have been bought with these packs. It turns out this is 151 and there is a theorem ( called Chicken McNugget theorem) that can prove this. Google it,if interested!

I am more interested in trying to find a way on checking that it is possible up to 150. Clearly, i could use a spreadsheet and systematically check all cases but is there another way?
So for example, is it possible to get 46
This would mean 9a+20b = 46 for some positive integer a, b ? Do i just guess?

You may be misunderstanding the theorem. (Usually the problem is stated in terms of 6, 9, and 20, which is the original form, but your theorem, perhaps from here, is a simplified version.)

The claim is not that every number up through 150 can be obtained, but that every number greater than 151 can, but 151 itself can't.

So in fact it is not at all true that "it is possible up to 150". On the other hand, if you wanted to find whether a given number can be obtained (maybe that's what you meant to say), there are standard methods; it involves solving a linear Diophantine equation, or you can do what is suggested here.

 

[Dr.Peterson]

So McDonald's sold its nuggets in packs of 9 and 20. Math enthusiasts were curious to find the largest number of nuggets that could not have been bought with these packs. It turns out this is 151 and there is a theorem ( called Chicken McNugget theorem) that can prove this. Google it,if interested!

I am more interested in trying to find a way on checking that it is possible up to 150. Clearly, i could use a spreadsheet and systematically check all cases but is there another way?
So for example, is it possible to get 46
This would mean 9a+20b = 46 for some positive integer a, b ? Do i just guess?

Let's take your example. How can we find a and b such that 9a+20b = 46?

The last reference I gave suggests a "greedy algorithm", and the link to that gives an example. It's a little hard to follow, though. Here's what I'd do for your example:

To make b as big as possible (greedy), we need b=46/20=2 (rounding down); 20*2 = 40, which is too small by 6. We can't make 6 from 9.

Decrease b to 1. Now 20*1 = 20, which is too small by 26. That isn't a multiple of 9, so we continue.

Decrease b to 0. We'd need to make 46 as a multiple of 9 alone, which is impossible. So we've found that 46 can't be obtained.
​

On the other hand, let's try to make 47:

To make b as big as possible, we need b=47/20=2 (rounding down); 20*2 = 40, which is too small by 7. We can't make 7 from 9.

Decrease b to 1. Now 20*1 = 20, which is too small by 27. That is a multiple of 9 (27 = 9*3), so we have a solution: a=3, b=1.

9*3+20*1 = 47
​

For this case, with only two variables, there are well-known ways to find a solution with less trial and error; but with more than two, this may be the best way.

However, a spreadsheet is probably a better way to make a list of all numbers under 151 that can be obtained.

 

[mmm4444bot]

… for some positive integer a, b …

a and b can also = 0
…

Are you using that McNugget theorem or something? :wink:

 

[apple2357]

You may be misunderstanding the theorem. (Usually the problem is stated in terms of 6, 9, and 20, which is the original form, but your theorem, perhaps from here, is a simplified version.)

The claim is not that every number up through 150 can be obtained, but that every number greater than 151 can, but 151 itself can't.

So in fact it is not at all true that "it is possible up to 150". On the other hand, if you wanted to find whether a given number can be obtained (maybe that's what you meant to say), there are standard methods; it involves solving a linear Diophantine equation, or you can do what is suggested here.

Ok, thanks. I clearly have misunderstood something here. So any number >151 can be obtained?? This seems remarkable!
In the artofproblems solving link, it does talk about the ' find the largest number of nuggets that could not have been bought with these packs'
This doesn't suggest any number >151 will work?

 

[mmm4444bot]

… it [says] 'find the largest number of nuggets that could not have been bought with these packs'

[the answer is 151]

This doesn't suggest any number >151 will work?

No, the answer does suggest that; any number greater than 151 is possible because 151 is the largest number that isn't possible. Maybe I don't understand your question (because Dr. Peterson just explained this).

Here's a partial list of nugget numbers from 120 through 159. Blue numbers are feasible and red numbers aren't.

… 120, 121, 122, 123, 124, 125, 126, 127, 128, 129,
… 130, 131, 132, 133, 134, 135, 136, 137, 138, 139,
… 140, 141, 142, 143, 144, 145, 146, 147, 148, 149,
… 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, …

The list continues, and no number larger than 151 will be red. Therefore, 151 is the largest number of nuggets that can't be bought by those packs. (Of the first 151 non-negative Integers, I think 76 of them are red.)

 

[apple2357]

No, the answer does suggest that; any number greater than 151 is possible because 151 is the largest number that isn't possible. Maybe I don't understand your question (because Dr. Peterson just explained this).

Here's a partial list of nugget numbers from 120 through 159. Blue numbers are feasible and red numbers aren't.

… 120, 121, 122, 123, 124, 125, 126, 127, 128, 129,
… 130, 131, 132, 133, 134, 135, 136, 137, 138, 139,
… 140, 141, 142, 143, 144, 145, 146, 147, 148, 149,
… 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, …

The list continues, and no number larger than 151 will be red. Therefore, 151 is the largest number of nuggets that can't be bought by those packs. (Of the first 151 non-negative Integers, I think 76 of them are red.)

Ok, thanks. Should i be surprised that no number above 151 will be red? To me it seems surprising and can't quite see why it would be true.

 

[Dr.Peterson]

Ok, thanks. Should i be surprised that no number above 151 will be red? To me it seems surprising and can't quite see why it would be true.

It isn't surprising that you are surprised; that sort of thing is what makes math fun!

But there's a pretty simple explanation for why there should be such a number, and once you see it, it's almost "obvious".

If you have a number n that you can make, using enough 9's and 20's, then you can just trade 4 20's (80) for 9 9's (81), and you will have a way to make the next number, n+1. Or, if you don't have enough 20's, you can trade 11 9's (99) for 5 20's (100). Once the numbers are big enough, at least one of those will be possible; and you can keep going forever, making every number from there on. The hard part is to find that number.

 

[apple2357]

It isn't surprising that you are surprised; that sort of thing is what makes math fun!

But there's a pretty simple explanation for why there should be such a number, and once you see it, it's almost "obvious".

If you have a number n that you can make, using enough 9's and 20's, then you can just trade 4 20's (80) for 9 9's (81), and you will have a way to make the next number, n+1. Or, if you don't have enough 20's, you can trade 11 9's (99) for 5 20's (100). Once the numbers are big enough, at least one of those will be possible; and you can keep going forever, making every number from there on. The hard part is to find that number.

Ok, I see, so something like this :

151 - not possible (largest number for which it is not possible....)

152 = 8x 9 + 4 x 20

153 = 8x9 + 9x 9 ( replacing 4x20 by 9x9) = 17x9 + 0x20

154 = 6x9 + 5x20 ( replacing 11x9 by 5x20)

155 = 6x9 + 1x20 + 9x9 ( replacing 4x20 by 9x9) = 15x 9+1x20

156 =

etc..

etc... very interesting...