McNugget Theorem? Nah!
McNuggets come in boxes of 7, 13, and 19. What is the largest amount of McNuggets that the customer cannot exactly obtain?
The answer is 50.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
4 solutions
Great Solution! Can you prove the claim that "in general the elements of S ′ ( n ) are congruent to n (mod 6)" ? And is it just a special case or can it be generalised to numbers other than 7,13,19?
It's enough to show that 5 0 ∈ / S and that 5 1 , 5 2 , … , 5 7 ∈ S , because we can get any larger element in S by adding the appropriate multiple of 7 to the solution for one of 5 1 , … , 5 7 .
The representations of 5 1 through 5 7 are trivial to find, and then looking mod 7 at 7 a + 1 3 b + 1 9 c = 5 0 yields that b + 2 c ≡ 6 mod 7 , so either b ≥ 6 or c ≥ 3 , which gives a left-hand side that is too large, so 5 0 ∈ / S .
Arithmetic Progression case for Coin Problem with a = 7 , d = 6 , s = 2
Which gives the answer a ( ⌊ s a − 2 ⌋ + 1 ) + ( d − 1 ) ( a − 1 ) − 1 = 5 0
Well if that doesn't make this problem trivial...
Oh well, there is at least one way of doing this problem without knowing the Frobenius number theorem. Those who don't know the theorem should have lot's of fun :)
Log in to reply
Similar to Agnishom Chattopadhyay's solution here
With patience, Generating function:
( 1 − x 7 ) ( 1 − x 1 3 ) ( 1 − x 1 9 ) 1 = 1 + x 7 + x 1 3 + x 1 4 + x 1 9 + x 2 0 + x 2 1 + 2 x 2 6 + x 2 7 + x 2 8 + x 3 2 + 2 x 3 3 + x 3 4 + x 3 5 + x 3 8 + 2 x 3 9 + 2 x 4 0 + x 4 1 + x 4 2 + 2 x 4 5 + 2 x 4 6 + 2 x 4 7 + x 4 8 + x 4 9 + x 5 1 + 3 x 5 2 + 2 x 5 3 + 2 x 5 4 + x 5 5 + sum of all powers of ( x ≥ 5 6 )
It appears that all powers of 5 1 and higher are possible, so answer is 5 0
Alternatively, one could work backwards from a two case problem, if it's only two numbers: 7 and 1 3 , then the number we're looking for is 7 × 1 3 − 7 − 1 3 = 7 1 . So we just need to work backwards from 7 1
7 1 = 0 ⋅ 6 + 4 ⋅ 1 3 + 1 ⋅ 1 9 7 0 = 1 0 ⋅ 7 + 0 ⋅ 1 3 + 0 ⋅ 1 9 6 9 = 8 ⋅ 7 + 1 ⋅ 1 3 + 0 ⋅ 1 9 6 8 = 7 ⋅ 7 + 0 ⋅ 1 3 + 1 ⋅ 1 9 6 7 = 4 ⋅ 7 + 3 ⋅ 1 3 + 0 ⋅ 1 9 6 6 = 4 ⋅ 7 + 0 ⋅ 1 3 + 2 ⋅ 1 9 6 5 = 0 ⋅ 7 + 5 ⋅ 1 3 + 0 ⋅ 1 9 6 4 = 0 ⋅ 7 + 2 ⋅ 1 3 + 2 ⋅ 1 9 6 3 = 9 ⋅ 7 + 0 ⋅ 1 3 + 0 ⋅ 1 9 6 2 = 7 ⋅ 7 + 1 ⋅ 1 3 + 0 ⋅ 1 9 6 1 = 6 ⋅ 7 + 1 ⋅ 1 3 + 1 ⋅ 1 9 6 0 = 3 ⋅ 7 + 3 ⋅ 1 3 + 0 ⋅ 1 9 5 9 = 2 ⋅ 7 + 2 ⋅ 1 3 + 1 ⋅ 1 9 5 8 = 0 ⋅ 7 + 3 ⋅ 1 3 + 1 ⋅ 1 9 5 7 = 0 ⋅ 7 + 0 ⋅ 1 3 + 3 ⋅ 1 9 5 6 = 8 ⋅ 7 + 0 ⋅ 1 3 + 0 ⋅ 1 9 5 5 = 6 ⋅ 7 + 1 ⋅ 1 3 + 0 ⋅ 1 9 5 4 = 5 ⋅ 7 + 0 ⋅ 1 3 + 1 ⋅ 1 9 5 3 = 3 ⋅ 7 + 1 ⋅ 1 3 + 1 ⋅ 1 9 5 2 = 1 ⋅ 7 + 2 ⋅ 1 3 + 1 ⋅ 1 9 5 1 = 0 ⋅ 7 + 1 ⋅ 1 3 + 2 ⋅ 1 9
Exhaust all possible ways for 5 1 = 7 a + 1 3 b + 1 9 c with integers 0 ≤ a ≤ 7 , 0 ≤ b ≤ 3 , 0 ≤ c ≤ 2 , we will see that there's no solution, which we can draw the same conclusion.
Let's define S ′ as the complement of S ; in other words S ′ contains all the possible quantities of McNuggets that you can buy. Now let's define S ′ ( n ) , a subset of S ′ , as all possible quantities of McNuggets that you can buy given that you buy precisely n boxes of McNuggets. The elements of the first few subsets ( S ’ ( n ) ) are listed below:
S ′ ( 1 ) = {7,13,19}
S ′ ( 2 ) = {14,20,26,32,38}
S ′ ( 3 ) = {21,27,33,39,45,51,57}
Notice that all of the elements of S ′ ( 1 ) are congruent to 1 (mod 6), all the elements of S ′ ( 2 ) are congruent to 2 (mod 6), and all the elements of S ′ ( 3 ) are congruent to 3 (mod 6). In fact, in general the elements of S ’ ( n ) are congruent to n (mod 6).
Now for the fun part: suppose you wanted to test and see if a customer can buy precisely 37 McNuggets. Note that the sets S ’ ( 1 ) and S ’ ( 7 ) are both congruent to 1 (mod 6), while the sets S ’ ( 2 ) , S ’ ( 3 ) ,... S ’ ( 6 ) , are not congruent to 1 (mod 6). The highest element of S ’ ( 1 ) is 19, while the lowest element of S ’ ( 7 ) is 49, so since 37 is greater than every element in S ′ ( 1 ) but less than every element in S ′ ( 7 ) , 37 must be a member of the union of the sets S ’ ( 2 ) , S ’ ( 3 ) ,... S ’ ( 6 ) in order to be a member of S ′ . But 37 mod 6 = 1, so 37 cannot possibly a member of the aforementioned union of sets. Therefore the customer cannot buy exactly 37 McNuggets!
The example above illustrates the inspiration behind the following theorem, which can be used to solve the problem: Let x be a natural number. x is an element of S iff there exists a natural number n , congruent to x (mod 6), such that 1 9 ( n − 6 ) < x < 7 n .
(Note: The full proof of this theorem is a little bit long to add to this solution. I will post the proof as a note tomorrow and insert the link to the note here.)
So let's see the theorem in action using n = 8: The inequality for x will be 3 8 < x < 5 6 . We are looking for values of x that are congruent to 8 (mod 6), and it turns out we find two: 44 and 50. Since n = 8 is a value of n that satisfies the theorem for both 44 and 50, both numbers are elements of S .
Now let’s try n = 9: The inequality for x will be 5 7 < x < 6 3 . We are looking for values of x that are congruent to 9 (mod 6), but it turns out that we can’t find any! What about n = 10? The inequality for x will be 7 6 < x < 7 0 , which is of course a ridiculous contradiction. The same can be said for any n > 10. Thus we can’t find any more elements of S for n > 8, and since any additional elements of S greater than 50 can only be found with n > 8, this means that there simply aren't any. Therefore the largest element in S , or the largest number of McNuggets that a customer cannot buy, is 5 0