Freigeben über

ANSWER Logic Puzzle: Buying donuts puzzle

  • Artikel

Here is the answer to the question that was posted, here. There are a few ways to answer this, you can use the brute force method or you can look for an easier way.  This actually turns out to be a problem space where there is a specific way to solve it, On the Frobenius’ Problem of three numbers.

Puzzle

A baker sells donuts in boxes of 6, 9, and 20. What is the greatest number of donuts that it is impossible to buy?

 

 

Solution

I’m going to show the brute force method to solve this, you can read that link to find the more elegant way.

The largest number of donuts that can’t be bought will be the smallest number of donuts that cannot be bought followed by six numbers that can be bought. This is because once we have six consecutive numbers that can be bought, any subsequent number can be made by just adding a multiple of six to one of those combinations.

From there, start at 21 and looked for the first series of six numbers that can be bought. This was made easier by noting that every multiple of 3 greater than 12 can be bought (by combining the 6 and the 9) and simply checking whether x-6 can be bought, whether x-9 can be bought, and whether x-20 can be bought.  Below are the results (x=cannot buy; . = can buy)

21 .
22 x
23 x
24 .
25 x
26 .
27 .
28 x
29 .
30 .
31 x
32 .
33 .
34 x
35 .
36 .
37 x
38 .
39 .
40 .
41 .
42 .
43 x
44 .
45 .
46 .
47 .
48 .
49 .
50 .

So, clearly 43 is the largest number of donuts that can’t be bought exactly.

Comments