You are at Mcdonald's and are ordering chicken nuggets. There are 6, 9, and 20 piece options available. What is the largest order you can make that cannot be fulfilled by combining these three options.
Lets consider a similar, but smaller, problem of the same type. You go to a stamp machine that dispenses 3 and 4 cent stamps. You notice that if you have a sufficient supply of coins, you can obtain stamps to the value of any whole number of cents except for 1 cent, 2 cents, and 5 cents.
If a stamp machine were to dispense only stamps of values m cents and n cents, how many exact postage values in cents cannot be made and what is the highest value not attainable? This involves only two variables while yours involves three variables. It can be solved by creating an array of the numbers in a manner similar to the two dimensional array for the following example.
If m and n have a common factor, there will always be an infinite number of values that cannot be made. Thus, m and need be relatively prime.
Consider first the stamp values of m = 3 cents and n = 22 cents. Create a table starting with 1, writing consecutive numbers in rows with n numbers to a row, stopping with m rows (m < n). All obtainable numbers are now marked off. They consist of 1) the multiples of n (the last column), 2) the remaining (n - 1) multiples of m (3, 6, 9, 12, 15, 18, etc.), and 3) the numbers directly below each marked multiple of m, obtainable by adding to the multiple of an appropriate multiple of n. We end up with the following, the / following a number meaning it has been crossed out.
.1...2...3/....4...5....6/...7...8.....9/...10..11...12/..13..14..15/..16..17...18/..19..20..21/..22/
23.24/.25/.26..27/.28/.29..30/..31/..32..33/..34/..35..36/..37/..38.39/..40/...41.42/.43/..44/
45/46/.47/.48/.49/.50/.51/.52/..53/..54/.55/..56/..57/.58/..59/..60/.61/.62/..63/.64/.65/..66/
for a total of 21 unattainable whole number values.
If m and n have no common factor, the table contains marks in every column; then all numbers larger than those appearing in the table are obtainable, and the answer to the problem is the quantity of unmarked numbers.
The highest unobtainable number is less than the lowest common multiple of the numbers.
An expression for the number of unattainable numbers is N = (n - 1)(m - 1)/2. For the example, N = (3 - 1)(22 - 1)/2 = 2x21/2 = 21. (Works only with two values)
The highest unattainable number is expressable by H = mn - (m + n) = n(m - 1) - m which produces 41 as the highest unattainable number. (Works only with two values)
Your problem has three numbers so we can format it as a 15 (6+9) by 20 array within which we cross out multiples of 6, 9, and combinations of 6 and 9 and their multiples, 15, 18, 21, 24, 27, 30, 33, etc., and 20 along the way. Your array would look like the following:
...1.......2.....3.....4......5......6/....7.....8......9/..10....11.....12/....13.....14....15/...16.....17...18/....19......20/
..21/....22....23/..24/...25....26/...27/..28....29/..30/...31.....32/....33/....34....35/...36/....37...38/....39/....40/
..41/....42/...43/..44/...45/...46/...47/..48/...49/..50/...51/....52/....53/....54/...55/...56/...57/...58/....59/....60/
..61/....62/...63/..64/...65/...66/...67/..68/...69/..70/...71/....72/....73/....74/...75/...76/...77/...78/....79/....80/
..81/../.82/...83/..84/...85/...86/...87/..88/...89/..90/...91/....92/....93/....94/...95/...96/...97/..98/.....99/...100/
101/./102/.103/.104/.105/.106/.107/.108/.109/.110/.111/..112/..113/...114/.115/.116/.117/.118/...119/...120/
121/./122/.123/.124/.125/.126/.127/.128/.129/.130/.131/..132/..133....134/.135/.136/.137/.138/...139/...140/
141/./142/.143/.144/.145/.146/.147/.148/.149/.150/.151/..152/..153/..154/..155/.156/.157/.168/...159/...160/
161/./162/.163/.164/.165/.166/.167/.168/.169/.170/.171/..172/..173/..174/..175/.176/.177/.178/...179/...180/
181/./182/.183/.184/.185/.186/.187/.188/.189/.190/.191/..192/..193/..194/..195/.196/.197/.198/...199/...200/
for a total of 20 unobtainable whole numbers and 37 as the highest unobtainable number.
A new team sport has been created called Shuttle. In this game, there are 3 ways to score points. A troi is worth 13 points, a gorn is worth 10 points and a crusher is worth 6 points. What number represents the largest score
that cannot be made in this game?"
Make an array 10 by 20 crossing out all multiples of 6, 10, 13, 16, 19, and 23. The largest number not crossed out is the highest unattainable score.
