# Word Problem: What is the largest amount you cannot buy?

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!

• en.wikipedia.org/wiki/Coin_problem There is no easy formula for three coins They talk a bit about how to be sure you have finished the problem in the section on the Mcnugget number Nov 11, 2015 at 1:43
• Hint: as $5$ is the smallest, try to get all the possible remainders upon division by $5$. Turns out that it is hardest to get the remainder of $1$. First instance is $36$. It follows that $31$ is the largest unreachable case.
– lulu
Nov 11, 2015 at 1:45

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.$$