ANSWER Logic Puzzle: Buying donuts puzzle

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.

Published 04 August 08 01:15 by Tom

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS

Comments

# Pregnant Man » ANSWER Login Puzzle: Buying donuts puzzle said on August 4, 2008 2:13 PM:

PingBack from http://wordnew.acne-reveiw.info/?p=15716

# Allaoua Cheraitia said on August 5, 2008 12:53 PM:

The difference between the numbers times the number of numbers to which one is added will give you the answer.

delta1 = 9-6 =3

delta2 = 20-9 =11

number of numbers = 3

Highest number that number of donuts cannot be acquired is:

(11+3)*3 + 1 = 43

Any higher than that can be a combination of any box of donuts - Obviously higher numbers make it easier.

Name (required)
Your URL (optional)
Comments (required)
Remember Me?

Search

This Blog

Home
Email

All my posts are provided "AS IS" with no warranties, and confer no rights. All the expressions expressed herein are entirely my own and not necessarily those of Microsoft. In addition, thoughts and opinions often change. Because a weblog is intended to provide a semi-permanent point-in-time snapshot, you should not consider out of date posts to reflect current thoughts and opinions.