Chicken McNuggets

You drove for hours last week to get your hands on McDonald's limited edition Szechuan sauce, and now you need some chicken nuggets for you and all of your friends. You can buy McNuggets in boxes of 6, 9, and 20. What is the largest whole number of nuggets that it is not possible to obtain by purchasing some combination of boxes of 6, 9, and 20? Click below for the answer.

There might be cleverer solutions to this problem, but we can do this fairly easily by listing combinations. Once we hit a streak of six numbers in a row that we can obtain, we know that the last number we couldn't obtain before the streak is the largest such number. Beyond that streak of six we can just add one or more boxes of 6 nuggets to one of those numbers to obtain any higher number. (There may be other combinations to obtain some of these numbers, but we only need one combination for each.)

Number	Boxes
1	Not Possible
2	Not Possible
3	Not Possible
4	Not Possible
5	Not Possible
6	6
7	Not Possible
8	Not Possible
9	9
10	Not Possible
11	Not Possible
12	6 + 6
13	Not Possible
14	Not Possible
15	6 + 9
16	Not Possible
17	Not Possible
18	9 + 9
19	Not Possible
20	20
21	6 + 6 + 9
22	Not Possible
23	Not Possible
24	6 + 9 + 9
25	Not Possible
26	20 + 6
27	9 + 9 + 9
28	Not Possible
29	20 + 9
30	6 + 6 + 9 + 9
31	Not Possible
32	6 + 6 + 20
33	6 + 9 + 9 + 9
34	Not Possible
35	6 + 9 + 20
36	9 + 9 + 9 + 9
37	Not Possible
38	9 + 9 + 20
39	6 + 6 + 9 + 9 + 9
40	20 + 20
41	6 + 6 + 9 + 20
42	6 + 9 + 9 + 9 + 9
43	Not Possible
44	6 + 9 + 9 + 20
45	9 + 9 + 9 + 9 + 9
46	6 + 20 + 20
47	9 + 9 + 9 + 20
48	6 + 6 + 9 + 9 + 9 + 9
49	9 + 20 + 20

That's six in a row, so we can get any higher number of nuggets just by adding boxes of 6 to those combinations. That means that 43 is the largest number of Chicken McNuggets that you cannot buy by combining boxes of 6, 9, and 20.