My batty and quite senile great-grandmother (on my wife's side) left me a fish and chip shop in her final will and testament after she was beheaded for treason (...long story).
The executioner of the will (not of her head) informed us that she stipulated that there was one thing that may never be changed - that the shop may only ever sell their fish and chips (best haddock this side of the Atlantic btw) in portions of 6, 9 and 20.
In a community-wide initiative to advertise their shop they asked the following question: What would be the largest order of fish and chips that one cannot order from us?
(a free albatross flavor ice-cube was given to those who provided a formula for any X, Y, Z combination...)
Answer
I think the answer is
43
Because
Any integer greater than 1 can be expressed as a sum of the form 2m+3n where m and n are non-negative integers. This is easy to show as all even integers are already in the form 2m and odd integers >1 can be expressed in the form 2m+3.
Hence, any integer, greater than 3 and divisble by 3 can be expressed in the form 6m+9n=3×(2m+3n) where m and n are non-negative integers.
Similarly, any number of the form 3k+2 (for integer k) greater than 23 can be expressed in the form 20+6m+9n and any number of the form 3k+1 (for integer k) greater than 43 can be expressed in the form (2×20)+6m+9n for non-negative integers m and n. Hence, all orders of size greater than 43 can be satisfied.
Clearly, a order of size 43 is unobtainable since any order with only portions of size 6 and 9 is divisible by 3, any portion with a single 20 and portions of 6 and 9 is of the form 3k+2 for integer k and having two portions of 20 already brings us to an order of size 40 whereby any extra portion provides us with an overshoot.
No comments:
Post a Comment