Donut Dilemma: Newsletter Challenge (January 2021)

43...

Donuts? It's actually the infamous McNugget number. Above 43, any integer can be expressed as a multiple of 6, 9, and 20, i.e. a*6 + b*9 + c*20.

https://mathworld.wolfram.com/McNuggetNumber.html

It sounds like something Paul Erdos would be involved in.

(Actually, Frobenius)

The proof is not that difficult. I wrote a Matlab script to break down numbers 1 - 50.

1 Not Purchasable

2 Not Purchasable

3 Not Purchasable

4 Not Purchasable

5 Not Purchasable

6 = 0x20 + 0x9 + 1x6

7 Not Purchasable

8 Not Purchasable

9 = 0x20 + 1x9 + 0x6

10 Not Purchasable

11 Not Purchasable

12 = 0x20 + 0x9 + 2x6

13 Not Purchasable

14 Not Purchasable

15 = 0x20 + 1x9 + 1x6

16 Not Purchasable

17 Not Purchasable

18 = 0x20 + 2x9 + 0x6

19 Not Purchasable

20 = 1x20 + 0x9 + 0x6

21 = 0x20 + 1x9 + 2x6

22 Not Purchasable

23 Not Purchasable

24 = 0x20 + 2x9 + 1x6

25 Not Purchasable

26 = 1x20 + 0x9 + 1x6

27 = 0x20 + 3x9 + 0x6

28 Not Purchasable

29 = 1x20 + 1x9 + 0x6

30 = 0x20 + 2x9 + 2x6

31 Not Purchasable

32 = 1x20 + 0x9 + 2x6

33 = 0x20 + 3x9 + 1x6

34 Not Purchasable

35 = 1x20 + 1x9 + 1x6

36 = 0x20 + 4x9 + 0x6

37 Not Purchasable

38 = 1x20 + 2x9 + 0x6

39 = 0x20 + 3x9 + 2x6

40 = 2x20 + 0x9 + 0x6

41 = 1x20 + 1x9 + 2x6

42 = 0x20 + 4x9 + 1x6

43 Not Purchasable

44 = 1x20 + 2x9 + 1x6

45 = 0x20 + 5x9 + 0x6

46 = 2x20 + 0x9 + 1x6

47 = 1x20 + 3x9 + 0x6

48 = 0x20 + 4x9 + 2x6

49 = 2x20 + 1x9 + 0x6

50 = 1x20 + 2x9 + 2x6

Each number breaks down into n = 20a + 9b + 6c. There are 6 numbers in a row after 43 that can be "purchased". If number n is "purchaseable", n+6 can be purchased just be increasing 'c' by one. So once you have 6 in a row, you're home free for the rest of the integers.

six is 2 x 3 and 9 is 3 x 3

Using 2 and 3 you can easily get any number above 2

If the number is odd subtract 3 then divide by 2 to get the number of 2s

So all multiples of three are possible above 6.

Because 20 is 2 mod 3, above and including 26 all numbers equal to 0 mod 3 or 2 mod 3 are possible.

And because 40 is 1 mod 3, above and including 46 all numbers are possible.

45 is 0 mod 3

44 is 2 mod 3

43 is 1 mod 3 and so is the greatest number not possible.

Boxes come with 6 donuts, 9 donuts, and 20 donuts inside. You can't buy part of a box. The question is "what number of donuts can you buy made up of a combination of full boxes?"

In #3, a is the number of 20 donut boxes, b the number of 9 donut boxes, and c the number of 6 donut boxes. The total number of donuts purchased is n = 20a + 9b + 6c. Not every number n can be broken down with a, b, and c as integers.

Pardon?

I'm not splitting any boxes.

Perhaps the first couple of lines are not clear. I'm basically just saying that with 6 and 9, you can make any number ≥ 6 which is a multiple of 3 (0 modulo 3).

From there because 20 is 2 modulo 3: above 26 inclusive any number which is 0 or 2 modulo 3 is possible. And, because 40 is 1 modulo 3: above 46 inclusive any number which is 0, 1 or 2 modulo 3 is possible. So we only need to examine 45 (0 mod3 ) 44 (2 mod 3) and 43 which is the answer.

I see where you're coming from now. Every even 0 modulo 3 is taken care of by "6 boxes" (2 x 3) and every odd 0 modulo 3 is taken care of by a "9 box" (3 x 3). So you can get the "even" 0 modulo 3s with the "six boxes" and substitute in a "nine box" to get the odd 0 modulo 3s.

When you get up where you can use the "20 box", you have 2 extra donuts, so the same pattern from the "six" and "nine" boxes is shifted up by 2 donuts, and when you can use 2 "20 boxes", the same pattern is shifted up by 4 (or up by 1).

Very clever! I like it!

You've got to know your doughnut limit....!

Someone is making a lot of dough out of selling all these do[ugh]nuts...

"What is the greatest number" Infinity of course!

<...Infinity...>

It is going to prove difficult to purchase that number, indeed...