My favorite candy come in packages of 5 or 6. What's the largest number for which I cannot buy exactly that many candies? Can this be generalized?I got a result yesterday. I liked its symmetry but couldn't figure out why it worked. I think I have the why down now, but I'm not sure I could explain it well yet. I thought you and your kids might enjoy playing with it.
The beach is fun, too. :^)
[Edited on April 24: The generalization discussed in the comments involves using two numbers that are relatively prime, ie GCF(A,B)=1. JD blogged 5 years ago about "The McNuggets Puzzle", using 3 numbers, which share some common factors. Cool extension!]
Posts
19, and yes, it can be generalized.
ReplyDeleteOh, you want to know how?
We can make the observation that 6-5=1 (which is obvious, I know, but let me continue). That means that you can add one candy to your total by getting rid of a 5-pack and adding a 6-pack. To show this works, imagine you have k*6+l*5=n candies, and add 6-5=1 to that equation. You get (k+1)*6-(l-1)=n+1
(hmmm, lower-case l and the digit 1 look exceedingly similar in this font. I hope it's clear from context).
Also crucial is the fact that 5 6-packs have the same number of candies as 6 5-packs. So if your count of 5 packs gets too low, you can bump it by 6 by taking away 5 6-packs.
You can do 18 candies with 3 6-packs. Using our +1 method, 19 won't work since we'd need -1 5-packs and 4 6-packs. The alternative (using the 5-6 for 6-5 trick) would be -1 6-pack and 5 5-packs, which is also unphysical. Using the +1 method, we get 20 as 0 6-packs and 4 5-packs. We have enough 5-packs to take us to 24 (4 6-packs), and 25 is obviously 5 5-packs. Using the +1 method 5 more times we get 30 in 5 six packs,which we can swap for 6 five-packs. From there on out, the +1 methods will always give us 5 six-packs before we run out of five-packs, and we can thus always readjust and keep going.
To actually generalize, let m,n be pack-sizes such that m, n are relatively prime. By Euler, that means there are s, t>0 such that sm-tn = 1 (you may have to switch m and t to ensure s,t>0). Our +1 method is now add s m-packs and take away t n-packs. Our 30-switcheroo means we can substitute n m-packs for m n-packs without changing the number of candies.
Let A be the number of candies we are trying to make with m-packs and n-packs. By using the +1 method A times on the 0-candy trivial solution, we get Asm-Atn = A. As it stands, -At n-packs is clearly negative, so we need to add km n-packs while subtracting kn m-packs until the number of n-packs is non-negative. That means km-At > 0 or k > At/m. There will then be As-kn m-packs. So to be physical, we also have to have As-kn > 0, or As/n > k. Putting these together you get As/n > k > At/m, or s/n > k/A > t/m.
Since s,t are uniquely determined by m,n, we've transformed the problem into finding the largest denominator A such that no k exists where s/n > k/A > t/m.
Subtracting t/m from all parts, you get s/n-t/m > k/A - t/m > 0
The LHS becomes (sm-tn)/nm = 1/nm, so 1/nm > k/A - t/m > 0. It's obvious that if A > nm, then we can always find a suitable k. That, at least, sets an upper-limit on our search.
Here my off-handed attempt at generalization drops off. I came up with a formula which doesn't work.
This is a very nice problem which I've liked for years.
ReplyDeleteHere is how I think about it when I try to explain it. For concreteness, I'll use 5 and 6 (but this generalizes to any pair of relatively prime numbers.)
1) If you can find five integers in a row that "work", you have found an upper bound on the answer to the problem. Why? (Because you can simply add a package of 5 to buy the next five numbers, another package of 5 to buy the next five numbers, and so on.)
2) Now take four six-packs = 24. You can "step down" to 23 by substituting a five-pack for a six pack, and you can repeat this sequentially to get 22, 21, and 20. So, now we know that it's possible to get five numbers in a row 20, 21, 22, 23, and 24, and now we know that our answer must be less than 20.
3) Okay, so now we need to examine 19 as our first candidate. It's small enough that we can quickly see that we can't buy 19, so 19 is our answer.
Now, it's straightforward to generalize the arguments in 1) and 2) above to deal with the more general case of any two relatively prime integers m and n, so it is easy to see that the answer must, in general, be less than or equal to m(n-1) - n (or, equivalently, mn - m - n).
But finding a nice simple way to explain that the inequality is actually an exact equality for the general case--not very easy.
If the two numbers are mutually prime, the largest impossible total will be the product minus the sum.
ReplyDeleteDo you remember Kate's Chicken McNugget problem?
ReplyDelete@Craig: Vaguely. I just tried to search and couldn't find it. Can you point me? Or remind me how the connection goes?
ReplyDeleteBlaise, I got lost in your reasoning - too many letters for me. But I think Mary's explanation is similar to yours. Am I right?
Mary wrote: "But finding a nice simple way to explain that the inequality is actually an exact equality for the general case--not very easy."
Exactly. :^)
But I think I've got it. I thought in terms of modulo or remainders. 6 and 5 might not be the best example because the remainders go up too nicely.
Zeitz used 7 and 11. I know I'll be ok for each multiple of 7. 11=4mod7 (no 3 bar equivalence key to type with...), so after 11, each number of the form 7a+4 will be ok. 22=1mod7, so after 22, each number of the form 7a+1 will be ok. And so on. There are only 6 remainders, so by the time I reach 11*6=66=3mod7, I have each remainder covered. That's my upper bound, 11*(7-1)=11*7-11.
Now how far back do I have to go? My 'last impossible number' must be between 11*5 and 11*6. By 11*5, I had all the remainders but one covered. So the only 'impossible numbers' in this range are equivalent to 3 mod 7. And the last one will be 7 less than 66.
Mary, does that work for you?
Curmudgeon, I like calling it the product minus the sum. Do you have any cool insights into why product minus sum gives the answer?
Oh, and thanks for playing. It makes doing these so much more fun!
ReplyDeleteI think a lot of us have posted this as "the McNuggets problem" of course it hurts that they no longer come in 6, 9, and 20 packs (I think).
ReplyDeleteHere's mine
The chicken nugget problem (not "Kate's" by a long shot!) is the same problem but using 6, 9, and 20. I used Mary's approach - once you can make the smaller-number number of consecutive numbers (ha!), you're done.
ReplyDeleteI'm assuming this is a dumb question but Sue do you think that book is worth getting?
I just deleted a comment I wrote but it may show up for some of you in your readers. I was confused about which book Kate meant.
ReplyDeleteKate, Zeitz's book is fabulous. It's full of hard problems, and has lots of ideas about problem solving. The level is pretty high, but that won't slow you down.
It's a bit cheaper than the other book I thought you were talking about. Look here.