Logic Puzzle: Buying donuts puzzle

I thought it would be fun to try something new here. So I am going to present a logic puzzle and let people try to answer it. I will post the solution in the future but I want to give people a chance to try to solve it.

So here is the first 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?

Published 31 July 08 06:00 by Tom

Filed under: Microsoft, Trivia of the Day, Logic Puzzles

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

# Francois Ward said on July 31, 2008 9:32 AM:

I suck pretty bad at these things since I've stopped doing them regularly a decade or so ago.

That said, now I was a box of donuts, damn you!

# Joseph Tyrrell said on July 31, 2008 10:05 AM:

Infinity? Or is that too easy an answer?

# Andrey Andreev said on July 31, 2008 11:00 AM:

Nice, thinking thinking thinking...

# Paul C. said on July 31, 2008 11:52 AM:

This question is lacking in clarity. With the way it is currently phrased, you could buy an infinite number of donuts, as well as no donuts at all. For instance, if you wanted 1 donut, you COULD buy a box of 6, you'd just have 5 leftovers... If you wanted 213 donuts, you COULD buy 10 boxes of 20, 1 box of 9, and 1 box of 6, but would end up with 2 donuts left over. I'm not trying to argue about the semantics of the question, but they do leave some holes in determining an appropriate response.

# Andy said on July 31, 2008 12:27 PM:

Dim test As Integer = 0

Dim remainder As Integer

Dim indivisible As New List(Of Integer)

Do While test < 10000

test += 1

remainder = test

For i As Integer = 0 To Math.Floor(test / 6)

remainder = remainder - i * 6

For j As Integer = 0 To Math.Floor(test / 9)

remainder = Math.Max(0, remainder - j * 9)

For k As Integer = 0 To Math.Floor(test / 20)

remainder = Math.Max(0, remainder - k * 20)

If remainder <> 0 OrElse test <> i * 6 + j * 9 + k * 20 Then

If Not indivisible.Contains(test) Then indivisible.Add(test)

Else

If indivisible.Contains(test) Then indivisible.Remove(test)

Continue Do

End If

Loop

MsgBox(indivisible.Max())

# Rich said on July 31, 2008 12:43 PM:

Answer: 43

Also impossible: 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37

# Raj Kaimal said on July 31, 2008 3:43 PM:

6x + 9y + 20z + 19

where x, y and z = ∞

# ZagNut said on July 31, 2008 4:27 PM:

An infinite amount of donuts is impossible to buy.

# JB King said on July 31, 2008 4:29 PM:

Assuming that one can sell only boxes of 6,9, and 20, I think the answer is 43. The key is to find the lowest 6 consecutive numbers that can be made as anything after that is just a 6 or multiple of 6 on top of one of the underlying formulas.

Here are 44-49 done using those 3 numbers, noting that 9*2 = 6*3:

44 = 20*1 + 6*4 or 20*1+6*1+9*2

45 = 9*5 or 6*3 + 9*3

46 = 20*2+6*1

47 = 20*1+9*3

48 = 6*8 or 9*2+6*5 or 9*4+6*2

49 = 20*2 + 9*1

I do find it interesting that nowhere do I use all 3 numbers. Now, how is 43 impossible? First note that 6 and 9 have 3 as a common factor so any combination of a multiple of those 2 will be divisible by 3. 43 is congruent to 1 mod 3, (42=2*3*7) and so with 20 being congruent to 2 mod 3 we would need to have 2 boxes of 20 which leaves only 3 left which is less than 6 or 9.

However, if one is allowed to use the boxes as a way to count the donuts and can remove from the final set any of these 3 values this comes to a different resolution as 43 becomes possible by taking a box of 9 and putting into it a box of 6 to remove along with the 2 boxes of 20. Now the maximum number of donuts becomes a much more difficult challenge as for example 11 can be done by taking a box of 9 out of a box of 20. Here I would need to find the lowest 3 in a row as I can use a 9 box with 6 removed to produce a 3 to add onto any value. Can I do 1,2,3? 3 is easiest as 9-6, 2 can be done by 20 minus 3 sets of 6, i.e. 20-6*3, and 1 can be done by 2 sets of 6 and one set of 9 minus a set of 20. Thus, the greatest number of donuts impossible to sell is none as there has to be at least one donut sold to have a transaction or negative 1 if one accepts a nothing transaction.

(Math geek)

# Jarvis said on July 31, 2008 4:36 PM:

The grammar of that question is atrocious, so it is hard to tell the exact meaning of the question. However, given the most likely meaning either there is no solution to that question or there is a typo in the question. *Any* multiple of any of those numbers plus *any* other number is impossible to get if you are requiring a discrete set of full doughnut boxes. There is no greatest number. This is one of the worst kinds of puzzle question: it's called 'guess what I'm thinking because I've left out a crucial piece of information and expect you to be psychic'.

# Sascha said on July 31, 2008 4:59 PM:

"What is the greatest number of donuts that it is impossible to buy?"

This does not even sound like a real sentence. Are there any limitations? Obviously there is no upper limit to how many donuts you can buy, no matter what kind of boxes he sells. Please correct your logic puzzle, this is lame.

# smcASP.NET said on July 31, 2008 6:49 PM:

aaahhhh... what? ".. the greatest number of donuts that it is impossible to buy?" That question doesn't make sense.

# Raaga said on July 31, 2008 8:19 PM:

are there any other conditions ?

# Tom said on July 31, 2008 11:42 PM:

I have gotten a few questions about this. Sorry for the wording of the puzzle. Basically you just want to find the largest number of donuts that you cannot buy. And no, the answer is not infinity. There are no other rules or limitations. I'll post the solution and the comments early next week.

# George Ter-Saakov said on August 1, 2008 12:08 AM:

115 am i right?

PS: Sorry about double commenting.. it's just i do not get any confirmation if my comment went through or not. I am just being redirected to the home page....and i do not see my comment...

# kris said on August 1, 2008 1:18 AM:

i got it too...nice one!!! it tempted me to write a program at first, but then i realised it was too easy to be worth the typing :)

# Robert Johnston said on August 1, 2008 1:42 AM:

Well, using longhand manual calculation, I got a value of 43 as the most you cannot buy. My list of the "Unobtainable" amounts is: 1,2,3,4,5,7,8,10,11,13,14,16,17,19,22,23,25,28,31,34,37,43

I'm probably wrong, but it's worth a try.

# Chris said on August 1, 2008 8:01 AM:

The answer is: "there is no donut".

# Eduardo said on August 1, 2008 8:10 AM:

How many boxes does of each category does the baker has? Can the baker make an unlimitted number of boxes?

On the other hand, is the purchase of the donuts done in one day? How much the baker can produce in one day?

My guess is that if infinity is not an option, then we ned to look for the limitations the baker has or by the number of boxes I can carry?

Am I close?

# Steve Webster said on August 1, 2008 8:23 AM:

20 is the greatest you can buy

21 is the greatest you cannot

# ZagNut said on August 1, 2008 10:01 AM:

Dude, there's no "right" answer, as long as the following number exists:

donuts = 20*a + 9*b + 6*c + 1

# Jon said on August 1, 2008 10:10 AM:

I'm sorry, but if there are no other rules or limitations. The answer *is* that there is no largest number. You can take any multiple combinations of boxes of donuts of 6, 9, or 20 and then simply add 1. There, you cannot buy that many because you need at least 5 more to make a full box. You can do that exercise an infinite number of times. I suspect either you aren't giving us the full question or the 'answer' you have is incorrect mathematically.

# Andrew Tollervey said on August 1, 2008 10:31 AM:

It either depends upon a) who is buying them and the amount of cash/credit they have available, or b) how many donuts and at what price the baker is willing/able to sell them for. If the total funds available to spend is greater than the aggregated cost of the maximum number the baker can supply, then only 'b' is relevant, otherwise 'a'. If both a and b are relevant, the door is left open to other factors, such has time to deliver is greater than the lifetime of the person purchasing - but that would be silly to consider :)

# Dave said on August 1, 2008 2:05 PM:

This is a really interesting question. I've been going over it in my head for most of the day but I haven't gotten very far. The problem needs to be approached in a way that will prove all values can be reached after a certain number. That number is the answer to the original question. Here's what I've eliminated so far:

Obviously to start, all multiples of 6, 9, and 20 can be reached at all times. After the target number of donuts >6, all multiples of 3 are able to be reached as well. Since obviously there is a number larger than 6 that can't be reached (7 for example), we can generalize it and say that all multiples of 3 can be reached.

So the answer isn't a multiple of 3, 6, 9, or 20. That's all I can come up with though.

# Stephen said on August 1, 2008 2:06 PM:

Given the wording and trickiness of some logic puzzles, I'm going to go with zero donuts.

According to the rules, it didn't say that you had to have no 'remainder' or extras of donuts.

To get 1 donut, you buy any box and have some leftover donuts. To get 3525 donuts you buy 177 boxes of 20, leaving 15 extra donuts, etc.

# James said on August 1, 2008 2:50 PM:

You need to buy a quantity that can be factored by 6, 9, or 20. Since primes have no factors you can not buy prime number of donuts. There are already proofs to prove there exists an infinite number of primes (won't bother repeating one), therefore the answer in in fact infinity. I don't know why you said it's not.

Or is this one of those things where the answer has no math basis? Kinda like, you are only able to buy as many as the baker can bake.

# Jean-Philippe Leconte said on August 1, 2008 4:42 PM:

Answer: 43

Just by listing the possible answers, you find out that the first 6 sequential numbers you can produce are 44 to 49, those allow you to produce all possible numbers.

For fun : 6, 9, 12, 15, 18, 20, 21, 24, 26, 27, 29, 30, 32, 33, 35, 36, 38, 39, 40, 41, 42, 44, 45, 46, 47, 48, 49...

Didn't even have to fire Mathematica... ;) but thx for the puzzle. (yes, I doubled every letter in my email domain part)

# Andrey Andreev said on August 1, 2008 6:28 PM:

My wife calculated the number 43. She showed 43 to be impossible and the 6 numbers after 43 to be "possible", by which one easily concludes that every larger number is possible (by adding a 6box to a proved one). I can post a detailed proof if requested

# Matthew Dennis said on August 2, 2008 10:29 PM:

37, after that there is a sequence of 6 numbers that can be made, so by adding 6 to the numbers allows the remaining numbers to be made.

Used BFI alogrithm (brute force and ignorance)

# Hanan said on August 3, 2008 6:12 AM:

The answer is 5, you can purchase any number greater than that, it will just require purchasing a few extra donuts along with them.

# joshka said on August 3, 2008 11:32 AM:

ans: 43

1. can buy any amount where n % 3 = 0 for n>=6

as:

9x0 + 6x1 = 6

9x1 + 6x0 = 9

9x0 + 6x2 = 12

9x1 + 6x1 = 15

9x0 + 6x3 = 18

...

2. similarly any amount where n % 3 = 2 for n>= 26

(26 % 3 = 2, and 26= 20+6)

3. similarly any amount where n % 3 = 1 for n >= 46 (20x2 + 6)

thus:

as n % 3 = 0, 1, or 2 for all n, the answer is less than 46.

45 % 3 = 0 (thus from 1, buyable)

44 % 3 = 2 (thus from 2, buyable)

43 % 3 is not buyable

lots missed from this logic for a full proof, but it's close enough.

# ASP.NET Debugging said on August 4, 2008 1:16 PM:

Here is the answer to the question that was posted, here . There are a few ways to answer this, you can

# Douglas Adams said on August 4, 2008 4:14 PM:

If I where to guess 42. Which is the Answer to Life, the Universe, and Everything.

# Tom said on August 4, 2008 4:28 PM:

The answer is now posted at:

http://blogs.msdn.com/tom/archive/2008/08/04/answer-login-puzzle-buying-donuts-puzzle.aspx

# rahulso said on August 11, 2008 1:08 PM:

That was cool :-)

Thanks for posting it Tom.

# Neil said on June 16, 2009 12:33 PM:

Hi, I found a website with logic puzles online. It's Crosswords-world.net, and this is the link to nonograms section <a href="http://crosswords-world.net/jap/">японские">http://crosswords-world.net/jap/">японские кроссворды</a> or this http://crosswords-world.net/jap/. There are more interesting puzzles.