How can i solve this math word problem, without just using guess and check?

How can i solve this math word problem, without just using guess and check?


How can i solve this math word problem, without just using guess and check?


At McDonalds you can ordr Chicken McNuggets in boxes of 6,9 and 20. What is the largest number such that you can not order any combination of the above to achieve exactly the number you want?|||10 out of 10 plus a gold star for a super star because that's how good you are|||(2^43,112,609)-1 = largest known prime number|||Brace yourself.





This is really hard to do without guess-and-check. But there is a sneaky way.





First, realize that all multiples of 3 above 6 are possible. Proof:





*The even multiples of 3 are all multiples of 6.


*You can make any odd multiple of 3, except for 3 itself, by adding one of those to 9. That is, 9, 15, 21, 27...





That helps! All multiples of 3 are orderable. Therefore, if a number can be MADE into a multiple of 3 by subtracting 20 or a multiple of 20, it's orderable. For example, 32 - 20 = 12, so you can get 32 McNuggets by ordering 20 + 6 + 6.





Can we make any number into a multiple of 3 like that? Yes, above a certain point! Proof:





Try dividing numbers %26gt;= 6 by 3.





If the remainder is 0, that number is possible; it's divisible by 3, and we just proved that all multiples of 3 that are %26gt;= 6 are possible.





If the remainder is 2, try subtracting 20. 20 is 18 + 2, which makes it a multiple of 3 plus a remainder of 2. So subtracting 20 from your number will give you a difference that's a multiple of 3, because the two remainders cancel out! This is called a property of 'modulo arithmetic.'





To see this in action:





26 / 3 = 8 remainder 2.


26 - 20 = 6, a multiple of 3.





So anything that has a remainder of 2 when divided by 3, and is above 23, is possible, because we can just put in a single 20-pack, and make the rest with 6-packs, and possibly a single 9-pack.





We've covered remainder 0 and remainder 2. The last possible case is numbers with remainder 1 when divided by 3. We can't fix that by subtracting 20, but what if we subtract 40? After all, 40 / 3 = 13 remainder 1.





So if we subtract 40 from any number with remainder 1, we're left with a multiple of 3! For example:





49 / 3 = 16 remainder 1.


49 - 40 = 9, a multiple of 3.





THEREFORE, any number greater than or equal to 40 can be turned into a multiple of 3. We just have to subtract either nothing (if it's already a multiple of 3), 20, or 40.





And since all multiples of 3 %26gt;= 6 are possible, all numbers %26gt;= 46 are possible!





Therefore, we don't have to worry about anything over 46. Let's count backwards, then:





45 is possible.


44 is possible


43 is definitely not possible. (43 / 3 gives remainder 1. We can only eliminate that remainder by subtracting 40, but that leaves us with 3, which is not one of our numbers.)





Since everything %26gt;= 46 is possible, 43 must be the last impossible case.





QED.





SHORT VERSION:





1) Every multiple of 3 %26gt;= 6 is possible.


2) If a number %26gt; 40 is not a multiple of 3, then you can make it a multiple of 3 by subtracting either 20 or 40.


4) Therefore, any number greater or equal to 40 + 6 will work.


5) So. 46 is an upper-bound we can count down from.


6) 43 is the last number to fail.