There is a non vegetarian restaurant which sells chicken pieces in orders of 6, 9 and 20.
Calculate the maximum number of chicken pieces you cannot order from that restaurant ?
More Puzzles
Blog Archive
-
►
2008
(84)
- March 2008 (19)
- April 2008 (2)
- May 2008 (2)
- July 2008 (4)
- August 2008 (6)
- September 2008 (10)
- October 2008 (10)
- November 2008 (5)
- December 2008 (26)
-
►
2009
(73)
- January 2009 (16)
- February 2009 (6)
- March 2009 (6)
- April 2009 (8)
- May 2009 (5)
- June 2009 (6)
- July 2009 (5)
- August 2009 (4)
- September 2009 (4)
- October 2009 (2)
- November 2009 (4)
- December 2009 (7)
-
►
2010
(28)
- January 2010 (1)
- February 2010 (4)
- March 2010 (5)
- April 2010 (4)
- May 2010 (2)
- June 2010 (1)
- July 2010 (1)
- August 2010 (2)
- September 2010 (1)
- October 2010 (1)
- November 2010 (2)
- December 2010 (4)
-
►
2011
(25)
- January 2011 (3)
- February 2011 (4)
- March 2011 (3)
- April 2011 (3)
- May 2011 (1)
- June 2011 (1)
- July 2011 (1)
- August 2011 (3)
- September 2011 (1)
- October 2011 (2)
- November 2011 (2)
- December 2011 (1)
-
►
2012
(10)
- January 2012 (2)
- March 2012 (1)
- April 2012 (1)
- May 2012 (1)
- July 2012 (1)
- September 2012 (1)
- October 2012 (1)
- November 2012 (1)
- December 2012 (1)
-
►
2013
(1)
- November 2013 (1)
-
▼
2014
(12)
- February 2014 (3)
- March 2014 (1)
- April 2014 (1)
- May 2014 (1)
- September 2014 (1)
- October 2014 (1)
- November 2014 (3)
- December 2014 (1)
-
►
2015
(52)
- January 2015 (8)
- February 2015 (13)
- March 2015 (7)
- April 2015 (4)
- May 2015 (3)
- June 2015 (1)
- July 2015 (2)
- August 2015 (2)
- September 2015 (3)
- October 2015 (4)
- November 2015 (3)
- December 2015 (2)
-
►
2016
(13)
- January 2016 (2)
- February 2016 (1)
- April 2016 (1)
- May 2016 (5)
- June 2016 (2)
- October 2016 (1)
- December 2016 (1)
-
►
2017
(3)
- February 2017 (3)
15 comments:
Any number which is not a multiple of 6,9,20,54,120,180,1080.
I caculated that 49 is the greatest number of chicken pieces which can be ordered for which there there are no combinations of mutiples of 6,9,20. I calculated all the combinations which fulfill orders from 50 to 100 and conjecture that all chicken orders greater than 49 can be fulfilled! - GAK
I caculated that 49 is the greatest number of chicken pieces which can be ordered for which there there are no combinations of mutiples of 6,9,20. I calculated all the combinations which fulfill orders from 50 to 100 and conjecture that all chicken orders greater than 49 can be fulfilled! - GAK
49 is not correct - two 20's and a9 equal 49. Also, the first comment can't be correct, either. 15 is not a multiple of the listed numbers, but 6+9 does the trick easily.
I think the answer is 37. This is not an elegant proof, but I think it works. The problem is of the form 6A+9B+20C = D. We must find Max D' where D' <> D and D' and D are in the set of whole numbers. It can be shown for any order over 6 that every number divisible by 3 is covered just by considering the 6 and 9 piece orders...
if 6A+9B = 3C where C is a whole number greater than 1...then 2A+3B = C and it can easily be seen that for every C over 2 there is a combination of A and B that reaches it (set B = 0 and you can cover every even number with some number A and every odd number is covered by A-1 and B=1). So our existing gap is orders below 6 pieces and any number not divisible by 3.
I think we can agree that if by magic we were given or could reach the numbers -1 and -2, then we would cover every existing whole number 4 and over (all multiples of 3 and by using -1 and -2 all the numbers in between).
By that logic, consider whole number mulitple orders (C) of the larger 20-piece product. So 20C = D. For C=1, 20 mod 3 = 2 (20 divided by 3 has a remainder of 2). So by adding 20 to sets of 6 and 9 we can cover all multiples of 3 over 20 plus 2. (for instance we had already covered multiples of 3 - 6,9,12,15,18,21,24,27, etc...now we also cover 20+3=23 which is 21+2, 20+6=26 which is 24+2, 20+9=29 which is 27+2..etc...) So now we have covered all whole numbers N over 6 divisible by 3 and whole numbers M over 20 where M mod 3 = 2 (M divided by 3 is remainder 2). Not covered is all whole numbers P over 20 with P mod 3 = 1 ( for instance 43 is 42 divided by 3 = 14 with a remainder of 1). Now consider the sets of 20 again where C=2. You can reach 40 with 2sets. 40 mod 3 = 1 (39/3 = 13 remainder 1). So now I can reach all remainder 1 numbers over 40. I have now covered all numbers divisible by 3, all numbers divisble by 3 with a remainder 2 over 20 and all numbers divisble by 3 with a remainder 1 over 40. So all numbers over 40 are accounted for. Under 40, what is't covered is numbers under 6, numbers under 20 mod 3 not equal to zero (remainder 1 or 2) and numbers under 40 mod 3 = 1. The largest number D under 40 where D mod 3 = 1 is 37.
infinite its a vegetarian restaurant
Let us read the problem again. It is a NON vegaterian resturant. It also states how many pieces CAN NOT be ordered, not how many Can. The answer is Any number that is NOT 6, 9, or 20 or a multiple of 6, 9, or 20 can NOT be ordered.
answer is 20
I think the answer is 37. I really appreciated your effort. Online study now very useful for the students. Students like these types of resources. I already found a website of math practice for my kids, Both my kids start learning from this website free of cost.
Learn Math Fast
I was thinking about my proof and realized I made an error...so I am surprised no one called me out on this, but the answer turns out not to be 37. It is 43. The logic above is right, but I missed something important. This gives me a chance to adjust and summarize my rambling proof to make it a bit clearer. Basically, all multiples of 3 EXCEPT 3 itself are covered by 6 and 9. If you do a little bit of work, you can prove this for yourself. Add the pack of 20. Since 20 is a "remainder 2" number when dividing by 3, using 20 covers all numbers when dividing by 3 that give a remainder of 2 (26, 29,32,35 etc) EXCEPT the first one, 23 (just like the first 3), because we can use 20 to start at a remainder 2 number (20) and just use 6 and 9 to cover all the numbers of the form "20+multiple of 3" (remainder 2 numbers) greater than 26. So we have covered all multiples of 3 over 6, and all "remainder 2" numbers when dividing by 3 over 26. So far, we haven't covered any "remainder 1" numbers when dividing by 3. Now add another 20-pack and start at 40. 40 is a "Remainder 1" number when dividing by 3. So we can now cover all "Remainder 1" numbers when dividing by 3 over 40 (46,49,52,55,etc..)EXCEPT the first one - 43. So 43 is the highest number. My mistake was not incorporating the fact that the first 3 was not covered when starting at 20 and 40, just like when starting from 0.
It's better to close that restaurant.. :-P
0 it is a vegitarian restaurant and therefore will not sell chicken
7*10*21 = 1470
?
1073?
(6*9*20) -7
Can we get confirmation of the correct answer please? ... then I'll wrap my head around the proof.
43
Good explanation here
http://en.wikipedia.org/wiki/Coin_problem
The answer is 43.
1) Let N >= 44 be an integer number. We shall show that there exists non-negative integers A, B, C such that 6*A + 9*B + 20*C = N. We consider 6 cases depending on the remainder of N when divided by 6.
1.0) N = 0 mod 6.
Let A = N / 6, B = 0 and C = 0. Since N >= 44 we have A >= 7. In addition 6*A + 9*B + 20*C = 6*N/6 + 9*0 + 20*0 = N.
1.1) N = 1 mod 6.
Let A = (N - 1)/6 - 8, B = 1 and C = 2. Since N = 1 mod 6 and N >= 44 we have N >= 49. Hence A >= (49 - 1)/6 - 8 = 0. In addition 6*A + 9*B + 20*C = (N - 1) - 48 + 9*1 + 20*2 = N.
1.2) N = 2 mod 6.
Let A = (N - 2)/6 - 3, B = 0 and C = 1. With arguments similar as before we obtain N >= 44, A >= 4 and 6*A + 9*B + 20*C = N.
1.3) N = 3 mod 6.
A = (N - 3)/6 - 1, B = 1 and C = 0. We have N >= 45, A >= 6 and 6*A + 9*B + 20*C = N.
1.4) N = 4 mod 6.
A = (N - 4)/6 - 6, B = 0, C = 2. We have N >= 46, A >= 1 and 6*A + 9*B + 20*C = N.
1.5) N = 5 mod 6.
A = (N - 5)/6 - 4, B = 1, C = 1. We have N >= 47, A >= 3 and 6*A + 9*B + 20*C = N.
Now, we shall show that it's impossible to have 6*A + 9*B + 20*C = 43 with A, B and C non-negative integer numbers. Suppose by contradiction that this is possible.
Since A, B >=0 we have 20*C <= 43 which implies C <= 2.
If C = 0, then 6*A + 9*B = 43 - 20*C = 43. This cannot be possible since 6*A + 9*B is divisible by 3 and 43 is not.
If C = 1, then 6*A + 9*B = 43 - 20*C = 23. This cannot be possible since 6*A + 9*B is divisible by 3 and 23 is not.
If C = 2, then 6*A + 9*B = 43 - 20*C = 3, hence 2*A + 3*B = 1. Therefore, 2*A <= 1, i.e., A = 0 and 3*B <= 1, i.e., B = 0. But this leads to another contradiction since 1 = 2*A + 3*B = 2*0 + 3*0 = 0.
Post a Comment