The McNugget Problem

When Mr. Rice was a high schooler, Mc. Donald’s introduced the Chicken Mc. Nugget. At that time, Mc. Nuggets came in boxes of 6 pieces, 9 pieces, and 20 pieces. It may astonish you to discover that in high school Mr. Rice was kind of a geek. One day while he was sitting in Mc. Donald’s with his just as geeky friends, they tried to figure out something about Chicken Mc. Nuggets. Buying only whole boxes (that means 6, 9, or 20 pieces), what is the largest number of Chicken Mc. Nuggets you CANNOT buy?

As an example, you cannot buy 1 Mc. Nugget, you cannot buy 7 Mc. Nuggets, but you can buy 15 Mc. Nuggets (a box of 6 and a box of 9).

So, once again, what is the largest number of Chicken Mc. Nuggets you CANNOT buy, when you are only buying whole boxes of 6 pieces, 9 pieces, and 20 pieces?

You can use the matrix below to help you. There is a pattern that you can use to find the solution. You need to be able to explain to me how you got your answer.

1	7	13	19	25	31	37	43	49	55	61	67	73	79	85	91	97
2	8	14	20	26	32	38	44	50	56	62	68	74	80	86	92	98
3	9	15	21	27	33	39	45	51	57	63	69	75	81	87	93	99
4	10	16	22	28	34	40	46	52	58	64	70	76	82	88	94	100
5	11	17	23	29	35	41	47	53	59	65	71	77	83	89	95	101
6	12	18	24	30	36	42	48	54	60	66	72	78	84	90	96	102

Answer:

The smallest number you can buy is 6. So, if you can buy 6, you can buy 12, 18, 24, 30, etc. That means you can cross our all the numbers on that line. The next number you can buy is 9. So if you can buy 9, you can buy 15, 21, 27, 33, etc. So you can cross out all the numbers on that line also. The next number you can buy is 20. So if you can buy 20, you can buy 26, 32, 38, etc. So you can cross out all the numbers on that line. The next number you can buy is 29 (a box of 20 and a box of 9). So if you can buy 29, you can buy 35, 41, 47, etc. So you can cross out all the numbers on that line. The next number you can buy is 40 (2 boxes of 20). If you can buy 40, you can buy 46, 52, 58, etc. The next number you can buy is 49 (2 boxes of 20 and a box of 9). So if you can buy 49, you can buy 55, 61, 67, etc. You can cross everything on that line out.

Now that you all of these numbers crossed out, you will see that 43 is the largest number left. That means that the largest number of McNuggets that you CANNOT buy when they are sold in boxes of 6, 9, and 20, is 43. You can buy every other number greater than that. That leads us to a way more important question; what part of the chicken does the McNugget come from?