Word Problem

jdevious22

New member
Joined
Jul 24, 2009
Messages
1
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.
 
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.
 
Came across this neat solution:

Tackle it from the point of view of a restaurant waiter making up orders.

First, note that the waiter never needs to deliver more than 1 box of 9 nuggets: he can exchange any set of 2 boxes of 9 for 3 boxes of 6. Also, he never needs to deliver more than 2 boxes of 20: 3 boxes of 20 can be exchanged for 10 boxes of 6. We can therefore assume that all orders will be delivered as 0 or 1 box of 9, 0, 1 or 2 boxes of 20, plus a certain number of boxes of 6 (noted as N below). As a result, all possible deliveries of nuggets (up to an exchange of boxes of 9 or 20 for boxes of 6) fall into one of the 6 following cases:

0 x 9-pack / 0 x 20-pack : 6N nuggets
1 x 9-pack / 0 x 20-pack : 6N+9 = 6(N+1)+3 nuggets
0 x 9-pack / 1 x 20-pack : 6N+20 = 6(N+3)+2 nuggets
1 x 9-pack / 1 x 20-pack : 6N+29 = 6(N+4)+5 nuggets
0 x 9-pack / 2 x 20-packs : 6N+40 = 6(N+6)+4 nuggets
1 x 9-pack / 2 x 20-packs : 6N+49 = 6(N+8)+1 nuggets

where N = > 0.

As all the possible residuals modulo 6 are covered, it is clear that for any large enough order, a solution can be found.
Also, for each value of the residual (each line of the above table), the minimum possible order can be found by setting N=0, and the largest impossible one is this number minus 6, which is 43.
 
Top