|
     
|
Question: Chicken McNumbers McDonald's sells Chicken McNuggets in packs of 6, 9, 20. You could purchase, say, 21 nuggets through the purchase of two 6-packs and one 9-pack. You cannot, regardless of how clever, purchase exactly ten nuggets. We'll say ten is an impossible number. Not all numbers are possible, but after a certain point, every number can be achieved. Find the largest impossible number. Now suppose McD's sells x-packs and y-packs of nuggets, where x and y are relatively prime (that means, the greatest common factor of x and y is 1). Find, with proof, a formula for the largest impossible number regardless of the choice of x and y. Answer: First, a lemma: if m and n are possible, then m+n is possible. Proof: if m and n are possible, then there are a1, b1, a2, b2 such that a1*x+b1*y=m and a2*x+b2*y=n. So m+n=a1*x+b1*y+2*x+b2*y=(a1+a2)*x+(b1+b2)*y so m+n is possible by buying a1+a2 packs of x, and b1+b2 packs of y. Part one: 6,9, and 20. First, suppose that they sold packs of 2 and 3. Then every even number would be possible, since it would be a multiple of 2, and every odd number greater than 1 would be three more than a positive even number, and so every number greater than 1 is possible. If we multiply every number in the preceding paragraph by 3, we find that in the case of 6 and 9 packs, every multiple of 3 is possible, other than three itself. Furthermore, 20 =2 mod 3, so every number greater than 23 which is 2 more than a multiple of 3 is possible (if w=3k+2, w>23, then w=3(k-6)+20 and k-6>0. 3(k-6) is possible because it's a multiple of 3 other than 3 itself. 20 is possible, since it can be obtained by buying one 20 pack. Their sum is possible (see lemma), so w is possible). And 40 = 1 mod 3, so every number greater than 43 which is one more than a multiple of 3 is possible (proof is similar to previous one). That covers everything, so from 43 on every number is possible. Suppose 43 is possible. Then how many 20 packs should we buy? If we buy none, then we are left trying to get a number which is not divisible by 3 from adding numbers that are divisible by 3, which isn't possible. If we buy exactly one, then we need 23 more, which again is not divisible by 3, so that's not possible either. If we buy two, then we need 3 more, and they don't sell 3 packs. So 43 is impossible, but everything greater than it is possible, so it is the greatest impossible number. Part two: x and y Note:
The last two terms are divisible by y, so the first must be as well. X
and y are co-prime, so it follows that y|a+1. If a+1=0, then a=-1, which
means that we're buying a negative number of x packs, which isn't allowed
(I assume).
So a+1>0, which means that a+1>=y, and a>=y-1. Therefore,
z=x*y-x-y>=(y-1)*x+b*y=x*y-x+b*y.
Subtracting (x*y-x) from both sides,
-y>=b*y, so b is negative, which isn't allowed. So z is impossible.
Suppose w=z+c=x*y-x-y+c where c is a positive integer, and w is
impossible. Consider the sequence w+y, w, w-y, w-2yw-x*y+2y. Note that
there are a total of x terms. Since there are x elements in Z/xZ, and
none of the terms in the sequence correspond to the same element (this
follows from elementary group theory and the fact that x and y are
co-prime), every element of Z/xZ has a term in the sequence that
corresponds to it. Specifically, there is a term that corresponds to 0,
that is, divisible by x. If it is anything other than the first term,
then w is equal to a multiple of y plus a multiple of x, so it is
possible. So the only way for w to be impossible is if w+y is divisible
by x.
w+y=x*y-x+c=x*y+(c-x)
x*y is divisible by x, so since w+y is divisible by x, (c-x) is divisible
by x. c>0, so c-x>-x. There's no number divisible by x between -x and
zero, so c-x>=0.
w=x*y+(c-x)-y=(x-1)*y+(c-x)
Both terms are nonnegative, and they are divisible by y and x,
respectively. So w is possible. This shows that z is the greatest
impossible number.
-- Ryan Flarity
|
