There is a bakery with 3 options for a box of cupcakes: a box of 5, a box of 9 and a box of 24.
The question being asked is "What is the largest number of cupcakes that you cannot buy?"
Using these order sizes, you can, for example, order exactly 19 bite-size cupcakes. You’d order a box of 9 and two boxes of 5. But, you can’t order exactly 17 bite-size cupcakes. There’s no way to combine boxes of 5, 9 and 24 to get exactly 17 cupcakes. Are there larger size orders than 17 cupcakes that you cannot get exactly?
I've been stuck on this problem because I keep wanting to just add up all the possible combinations but I'm curious if there is a faster/more reliable way to do so.
I understand that the answer will be a number that cannot work because it won't share a common divisor among the numbers and none of the boxes of cupcakes numbers will add equally into the number being found.
Please share any insight you have to help me figure this out!
The message that I got from the wikipedia article on the Frobenius coin problem is that, for three or more coins, we need to investigate numbers that can be represented by hand or by computer, there is no magic formula. At the same time, having done that much, there is an easy means of proving that we have finished the job.
We cannot represent $31$ as $5x+9y+24z$ for integers $x,y,z \geq 0.$ The smallest denomination is $5,$ next we represent five in a row.
$$ 32 = 5 \cdot 1 + 9 \cdot 3 + 24 \cdot 0, $$ $$ 33 = 5 \cdot 0 + 9 \cdot 1 + 24 \cdot 1, $$ $$ 34 = 5 \cdot 2 + 9 \cdot 0 + 24 \cdot 1, $$ $$ 35 = 5 \cdot 7 + 9 \cdot 0 + 24 \cdot 0, $$ $$ 36 = 5 \cdot 0 + 9 \cdot 4 + 24 \cdot 0. $$
If we want to represent any number larger than $36$ we can do it. Take some $n \geq 37.$ There is some $k \geq 1$ such that $n - 5 k$ is in the range from $32$ to $36,$ $$ 32 \leq n - 5 k < 36.$$ Indeed, $$ k = \left\lfloor \frac{n-32}{5} \right\rfloor $$ From the list above, find $$ n-5k = 5x + 9 y + 24 z. $$ Then $$ n = 5(x+k) + 9 y + 24 z. $$ $$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$
Addendum: we had $$ 32 \leq n - 5 k < 36. $$ We could write this as $$ n - 5 k = 32 + \delta, \; \; \; \; \mbox{where} \; \; \; 0 \leq \delta \leq 4. $$ $$ n - 32 = 5 k + \delta, \; \; \; \; \mbox{where} \; \; \; 0 \leq \delta \leq 4. $$ Indeed, $$ \left\lfloor \frac{n-32}{5} \right\rfloor = \left\lfloor \frac{ 5k + \delta }{5} \right\rfloor = \left\lfloor k + \frac{ \delta }{5} \right\rfloor = k, $$ because $k$ is a positive integer and $$ 0 \leq \frac{ \delta }{5} < 1; $$ $$ k \leq k + \frac{ \delta }{5} < k + 1. $$