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 \times (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\times 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