0
$\begingroup$

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!

$\endgroup$
2
  • 1
    $\begingroup$ 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 $\endgroup$
    – Will Jagy
    Nov 11, 2015 at 1:43
  • 1
    $\begingroup$ 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. $\endgroup$
    – lulu
    Nov 11, 2015 at 1:45

1 Answer 1

0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.