Donut in three packs

Homer Simpson's bakery sells donuts in 5 packs, 9 packs and 13 packs. What is the largest number of donuts that he can't buy exactly?


The answer is 21.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

I do not know any formal solution but I did experimentally with a gf:

1 ( 1 x 5 ) ( 1 x 9 ) ( 1 x 13 ) \frac{1}{\left(1-x^5\right) \left(1-x^9\right) \left(1-x^{13}\right)}

Finding the taylor series of which gives you:

+ 4 x 50 + 4 x 49 + 3 x 48 + 2 x 47 + 3 x 46 + 4 x 45 + 3 x 44 + 2 x 43 + 2 x 42 + 3 x 41 + 3 x 40 + 2 x 39 + 2 x 38 + 2 x 37 + 3 x 36 + 2 x 35 + x 34 + 2 x 33 + 2 x 32 + 2 x 31 + x 30 + x 29 + 2 x 28 + 2 x 27 + x 26 + x 25 + x 24 + 2 x 23 + x 22 + x 20 + x 19 + 2 x 18 + x 15 + x 14 + x 13 + x 10 + x 9 + x 5 + 1 \cdots+4 x^{50}+4 x^{49}+3 x^{48}+2 x^{47}+3 x^{46}+4 x^{45}+3 x^{44}+2 x^{43}+2 x^{42}+3 x^{41}+3 x^{40}+2 x^{39}+2 x^{38}+2 x^{37}+3 x^{36}+2 x^{35}+x^{34}+2 x^{33}+2 x^{32}+2 x^{31}+x^{30}+x^{29}+2 x^{28}+2 x^{27}+x^{26}+x^{25}+x^{24}+2 x^{23}+x^{22}+x^{20}+x^{19}+2 x^{18}+x^{15}+x^{14}+x^{13}+x^{10}+x^9+x^5+1

Looks like everything higher than 21 is possible.

Read on for a proof that all integer quantities > 21 can be expressed as a multiple sum of these quantites:

22 = 13 + 9

23 = 13 + 5 + 5

24 = 9 + 5 + 5 + 5

25 = 5 + 5 + 5 + 5 + 5

26 = 13 + 13

To get a number higher than 26, you just need to add 5's to the extreme right of the sequences...

Analytical Solution:

When the value of the coins are in arithmetic progression, this formula works:

F r o b e n i u s ( a , a + d , a + 2 d + . . . a + s d ) = ( a 2 s + 1 ) a + ( d 1 ) \ ( a 1 ) 1 Frobenius(a,a+d,a+2d+...a+sd)=\left(\left\lfloor \frac{a-2}{s}\right\rfloor +1\right) a+(d-1) \ (a-1)-1

Plugin a=5,d=4,s=2. The answer is then 21

Thanks to @bobbym none for the analytical solution.

This is also known as the Frobenius Coin Problem . There is only a general solution for the 2 box case.

I've updated the answer to 21.

Calvin Lin Staff - 7 years ago

Log in to reply

Sorry for the error everyone! It slipped me!

Sameer L. - 7 years ago

Mathematica Code:

FrobeniusNumber[{5, 9, 13}]

Returns 21

I've an analytical solution, I'll update it

Log in to reply

Can you explain how the "analytical solution" works? What is the logic behind it?

Calvin Lin Staff - 7 years ago

I've added a better solution, check it out!

Should't 11 be the answer? Because all the integer values beyond 11 can be represented by the eqn : 5x+9y+13z

Sharad Chandran - 6 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...