tag:blogger.com,1999:blog-5303307482158922565.post1029806906239427677..comments2024-03-22T13:39:55.941-07:00Comments on Math Mama Writes...: More Number TheorySue VanHattumhttp://www.blogger.com/profile/10237941346154683902noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-5303307482158922565.post-4089797642679451162011-04-24T17:52:37.002-07:002011-04-24T17:52:37.002-07:00I just deleted a comment I wrote but it may show u...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. <br /><br />Kate, 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.<br /><br />It's a bit cheaper than the other book I thought you were talking about. Look <a href="http://www.bookfinder.com/search/?ac=sl&st=sl&qi=z32iToxRlhHoI,9HBNZ,s7Ah,Ik_7075782828_1:100:667&bq=author%3Dpaul%2520zeitz%26title%3Dart%2520and%2520craft%2520of%2520problem%2520solving" rel="nofollow">here</a>.Sue VanHattumhttps://www.blogger.com/profile/10237941346154683902noreply@blogger.comtag:blogger.com,1999:blog-5303307482158922565.post-22750996858726581352011-04-24T17:14:01.120-07:002011-04-24T17:14:01.120-07:00The chicken nugget problem (not "Kate's&q...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.<br /><br />I'm assuming this is a dumb question but Sue do you think that book is worth getting?Katehttps://www.blogger.com/profile/14229054922453438248noreply@blogger.comtag:blogger.com,1999:blog-5303307482158922565.post-36095907600541432682011-04-23T21:30:02.902-07:002011-04-23T21:30:02.902-07:00I think a lot of us have posted this as "the ...I 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).<br /><br /><a href="http://jd2718.wordpress.com/2006/09/10/the-mcnuggets-puzzle/" rel="nofollow">Here's mine</a>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5303307482158922565.post-87766263220905251172011-04-23T15:24:49.839-07:002011-04-23T15:24:49.839-07:00Oh, and thanks for playing. It makes doing these s...Oh, and thanks for playing. It makes doing these so much more fun!Sue VanHattumhttps://www.blogger.com/profile/10237941346154683902noreply@blogger.comtag:blogger.com,1999:blog-5303307482158922565.post-21741938622414072102011-04-23T15:23:46.921-07:002011-04-23T15:23:46.921-07:00@Craig: Vaguely. I just tried to search and couldn...@Craig: Vaguely. I just tried to search and couldn't find it. Can you point me? Or remind me how the connection goes?<br /><br />Blaise, I got lost in your reasoning - too many letters for me. But I think Mary's explanation is similar to yours. Am I right?<br /><br />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." <br /><br />Exactly. :^)<br /><br />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.<br /><br />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. <br /><br />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.<br /><br />Mary, does that work for you?<br /><br />Curmudgeon, I like calling it the product minus the sum. Do you have any cool insights into why product minus sum gives the answer?Sue VanHattumhttps://www.blogger.com/profile/10237941346154683902noreply@blogger.comtag:blogger.com,1999:blog-5303307482158922565.post-11755661882318220742011-04-22T08:32:46.031-07:002011-04-22T08:32:46.031-07:00Do you remember Kate's Chicken McNugget proble...Do you remember Kate's Chicken McNugget problem?Craig Danielshttps://www.blogger.com/profile/13397752180490590098noreply@blogger.comtag:blogger.com,1999:blog-5303307482158922565.post-77737998608786757912011-04-20T10:22:36.352-07:002011-04-20T10:22:36.352-07:00If the two numbers are mutually prime, the largest...If the two numbers are mutually prime, the largest impossible total will be the product minus the sum.Curmudgeonhttps://www.blogger.com/profile/04323026187622872114noreply@blogger.comtag:blogger.com,1999:blog-5303307482158922565.post-45868964577819387592011-04-19T21:50:30.760-07:002011-04-19T21:50:30.760-07:00This is a very nice problem which I've liked f...This is a very nice problem which I've liked for years. <br /><br />Here 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.)<br /><br />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.)<br /><br />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. <br /><br />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.<br /><br />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).<br /><br />But finding a nice simple way to explain that the inequality is actually an exact equality for the general case--not very easy.Mary O'Keeffehttp://albanyareamathcircle.blogspot.com/noreply@blogger.comtag:blogger.com,1999:blog-5303307482158922565.post-13620061878423365732011-04-19T20:41:28.471-07:002011-04-19T20:41:28.471-07:0019, and yes, it can be generalized.
Oh, you w...19, and yes, it can be generalized.<br /><br /><br /><br /><br /><br />Oh, you want to know how?<br /><br />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 <br /><br />(hmmm, lower-case l and the digit 1 look exceedingly similar in this font. I hope it's clear from context).<br /><br />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.<br /><br />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.<br /><br />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.<br /><br />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.<br /><br />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. <br /><br />Subtracting t/m from all parts, you get s/n-t/m > k/A - t/m > 0<br />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.<br /><br />Here my off-handed attempt at generalization drops off. I came up with a formula which doesn't work.Buddha Buckhttps://www.blogger.com/profile/17167036913705912859noreply@blogger.com