Enter your email address:


May 16, 2014

Deductive Math Problem

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 ?

15 comments:

Anonymous said...

Any number which is not a multiple of 6,9,20,54,120,180,1080.

gknudsen said...

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

gknudsen said...

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

KPM said...

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.

Anonymous said...

infinite its a vegetarian restaurant

IBM Ron said...

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.

mta said...

answer is 20

Unknown said...

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

KPM said...

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.

Anonymous said...

It's better to close that restaurant.. :-P

Anonymous said...

0 it is a vegitarian restaurant and therefore will not sell chicken

Waldo said...

7*10*21 = 1470
?

Anonymous said...

1073?
(6*9*20) -7

Can we get confirmation of the correct answer please? ... then I'll wrap my head around the proof.

dogtag114 said...

43

Good explanation here

http://en.wikipedia.org/wiki/Coin_problem

Unknown said...

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.