chicken nuggets

Chicken Nuggets

At some point in time McDonold's only sold chicken nuggets in packs of 9 and 20. An interesting problem then became: What is the largest integeer number of McNuggets such that it cannot be purchased perfectly using these packs? i.e. there are no leftover or extra nuggets.

To generalize and cast it in a more understandable framework, we can think of this as saying what is the largest integer such that it cannot be expressed in X x M + Y x N, where X & Y are positive integers and M & N are positive and relatively prime integers.

straightforward argument

The most intuitive way to go about solving this problem is to list out the positive numbers starting with 0. WLOG, assume M > N. As we list out all of the numbers starting from 0, we can determine that integer z (mod) m. It must be congruent to an element in the set {0, 1...(m-1)}. note that once any integer z is 'purchasable' then all integers that are of the form u == z (mod) m must also be purchasable (because we can just buy the difference in packs of "m" chicken nuggets.

Note also that any integer that is a multiple of "n" is also purchasable. Note also that n = n (mod m), since they are relatively prime. Here is the key part. if n & m are relatively prime, then each multiple of n, up to 'm x n' will have a different remainder. i.e. a x n != b x n (mod m) for positive integers a and b, such that 0 < a, b < m. Then, as we iterate through the multiples of n, and mod them with m, we must be congruent to an element in the set {0, 1,...(m-1)}, and we must be different.

Any multiple of n is purchasable, and then every number greater than a*n that is congruent to a*n (mod m) is also purchasable.

Finally, The last integer in the set of {0, 1,...(m-1)} to be congruent to will happen when we take the multiple n*(m-1). That will be purchasable, but all of the numbers congruent to that mod(m) before would have not been purchasable. So the greatest non-purchasable integer is n(m-1) - m!

formal mathematical proof

(todo; write out everything in more detail)

1. By Bezout's lemma, we can write 1 = x' * m + y' * n if m & n have gcd of 1 and x and y are integers
2. Therefore we can write N= N*x'*m = N*y'*n
3. Therefore, we can write any integer N as a linear combination of m and n, but it is only purchasable if that linear combinations only uses positive multipliers
4. Define the set An := {x*m -kn + y*m +km, k element integers} , for any (x,y) in the solution set An. I.e, for an integer N, all the solutions take this form, once we have a solution x,y from that set.
5. (todo; write proof of this)
6. By divisibility theorem, we know that if we constrain 0 < bn < (m-1), there is only one solution, call it (an, bn). This is because all solutions for bn would differ by some difference km which would move it outside the range
7. An integer is purchasable, upon this restriction, if an is greater than 0. If an is greater than zero, we simply find any solution an, bn s.t both are positive. If an < 0, then clearly an, bn is not a solution. But it may be possible for some other solution to exist if we choose the right k. So let's divide the set of possible k to be <=0 or >0. If k <=0, then, by our definition, bn would certainly become negative. if k>0, then an would remain negative. That means that once we find a solution an, bn, with this restriction, the only purchasable scenario is when an >= 0.

Solution: Taking all of this information, a non-purchasable integer is when an is less than 0 and bn is within that range. We want to find the maximum of that set. Obviously the integer formed from a solution in this set (an *m + bn *n) will be greatest when an and bn are greatest. The max is the solution (-1, m-1). Therefore, the largest non-purchasable integer is -1 * m + (m-1) * n = m*n - m - n. Q.E.D.