This is not an eating competition, instead you have to think.
The Challenge
Chicken McNuggets can be ordered in the sizes of 6, 9 and 20 pieces. Being allowed to use a combination of the sizes, what is the highest number that you can NOT order?
Example: 98 pieces can be ordered using a combination (4×20 pieces + 2×9 pieces). 14 pieces cannot be ordered (no combination of 6, 9 and 20 equals 14)
Solution
To solve this we created a small optimisation model that for a proposed number verifies if it is possible to order that quantity.
- The variables are the number of 6-packs, 9-packs and 20-packs respectively.
- The objective is to maximise the total number of nuggets ordered.
- The total number of nuggets ordered is constrained to not be larger than a quantity currently investigated
- In a loop the program tests order quantities in a decreasing order until the maximum order is not equal the constraint/proposed quantity.
Example Code
Console Output
class TheMcNuggetsChallenge
ojAlgo
2019-05-09
OPTIMAL 100.0 @ { 0, 0, 5 }
OPTIMAL 99.0 @ { 5, 1, 3 }
OPTIMAL 98.0 @ { 0, 2, 4 }
OPTIMAL 97.0 @ { 8, 1, 2 }
OPTIMAL 96.0 @ { 0, 4, 3 }
OPTIMAL 95.0 @ { 1, 1, 4 }
OPTIMAL 94.0 @ { 0, 6, 2 }
OPTIMAL 93.0 @ { 4, 1, 3 }
OPTIMAL 92.0 @ { 2, 0, 4 }
OPTIMAL 91.0 @ { 4, 3, 2 }
OPTIMAL 90.0 @ { 2, 2, 3 }
OPTIMAL 89.0 @ { 0, 1, 4 }
OPTIMAL 88.0 @ { 8, 0, 2 }
OPTIMAL 87.0 @ { 0, 3, 3 }
OPTIMAL 86.0 @ { 1, 0, 4 }
OPTIMAL 85.0 @ { 0, 5, 2 }
OPTIMAL 84.0 @ { 4, 0, 3 }
OPTIMAL 83.0 @ { 0, 7, 1 }
OPTIMAL 82.0 @ { 7, 0, 2 }
OPTIMAL 81.0 @ { 2, 1, 3 }
OPTIMAL 80.0 @ { 0, 0, 4 }
OPTIMAL 79.0 @ { 2, 3, 2 }
OPTIMAL 78.0 @ { 0, 2, 3 }
OPTIMAL 77.0 @ { 8, 1, 1 }
OPTIMAL 76.0 @ { 0, 4, 2 }
OPTIMAL 75.0 @ { 1, 1, 3 }
OPTIMAL 74.0 @ { 0, 6, 1 }
OPTIMAL 73.0 @ { 4, 1, 2 }
OPTIMAL 72.0 @ { 2, 0, 3 }
OPTIMAL 71.0 @ { 4, 3, 1 }
OPTIMAL 70.0 @ { 5, 0, 2 }
OPTIMAL 69.0 @ { 0, 1, 3 }
OPTIMAL 68.0 @ { 5, 2, 1 }
OPTIMAL 67.0 @ { 0, 3, 2 }
OPTIMAL 66.0 @ { 1, 0, 3 }
OPTIMAL 65.0 @ { 0, 5, 1 }
OPTIMAL 64.0 @ { 4, 0, 2 }
OPTIMAL 63.0 @ { 0, 7, 0 }
OPTIMAL 62.0 @ { 7, 0, 1 }
OPTIMAL 61.0 @ { 2, 1, 2 }
OPTIMAL 60.0 @ { 0, 0, 3 }
OPTIMAL 59.0 @ { 2, 3, 1 }
OPTIMAL 58.0 @ { 0, 2, 2 }
OPTIMAL 57.0 @ { 5, 3, 0 }
OPTIMAL 56.0 @ { 0, 4, 1 }
OPTIMAL 55.0 @ { 1, 1, 2 }
OPTIMAL 54.0 @ { 0, 6, 0 }
OPTIMAL 53.0 @ { 4, 1, 1 }
OPTIMAL 52.0 @ { 2, 0, 2 }
OPTIMAL 51.0 @ { 4, 3, 0 }
OPTIMAL 50.0 @ { 5, 0, 1 }
OPTIMAL 49.0 @ { 0, 1, 2 }
OPTIMAL 48.0 @ { 8, 0, 0 }
OPTIMAL 47.0 @ { 0, 3, 1 }
OPTIMAL 46.0 @ { 1, 0, 2 }
OPTIMAL 45.0 @ { 0, 5, 0 }
OPTIMAL 44.0 @ { 4, 0, 1 }
Not possible to order 43 nuggets
If you believe there is a number greater than 100 that cannot be ordered, then you need to modify and run the code yourself.