Tough Nut

P

psoft

New member
Joined
Jan 21, 2006
Messages
6
You are given an infinite number of cookie boxes containing either 6, 9 or 280 cookies. You are allowed to use these boxes in any combination so desired. What is the maximum number of cookies that you cannot give out using the above boxes?
Anyone got the solution :lol:
 
psoft said:
You are given an infinite number of cookie boxes containing either 6, 9 or 280 cookies. You are allowed to use these boxes in any combination so desired. What is the maximum number of cookies that you cannot give out using the above boxes? Anyone got the solution :lol:
Click to expand...
What grade are you in?
Solving this is not simple...
Here's a solution for 6, 9 or 20 (not mine):

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 one box of 9 nuggets: he can exchange any
set of two boxes of nine for 3 boxes of six). Also, he never needs to deliver more than 2 boxes of 20
(3 boxes of 20 can be exchanged for 10 packs of 6). We can then assume that all orders will be delivered
as 0 or 1 box of nine, 0, 1 or 2 boxes of 20, plus a certain amount of boxes of 6 (which I will note N).
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, the number of packs of 6, is a positive number, or zero.

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, thus 43.
 
psoft its really obvious you aren't posting these questions because you need help, you're posting them to waste other people's time.. and its rude.
 
Here is a similar problem with 2 items which you can apply to three items in three pairings.

If a stamp machine were to dispense only stamps of values m cents and n cents, m less than n, how many exact postage values in cents cannot be made and what is the highest value not attainable?

If m and n have a common factor, there will always be an infinite number of values that cannot be made. Thus, m and n need be relatively prime.

For illustrative purposes, consider an example with the stamp values of m = 4 cents and n = 7 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 (4, 8, 12, 16, 20, and 24 in the example), 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 table, 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/
for a total of 9 unattainable values and 17 as the highest unattainable value.

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 expression giving the number of unattainable numbers directly is N = (n - 1)(m - 1)/2. For our m = 4 and n = 7 example, N = (4 - 1)(7 - 1)/2 = 3x6/2 = 9.

The expression giving the highest unattainable number directly is H = 2N - 1 = mn - (m + n) = n(m - 1) - m. For our example, H = 7(4) - (7 + 4) = 17.

Considering the case where m = 3 and n = 10:

.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/

for a total of 9 unattainable whole number values, verifiable by N = (3 - 1)(10 - 1)/2 = 2x9/2 = 9, the highest being 2(9) - 1 = 17.

Consider the case where m = 5 and n = 11.

After crossing out the numbers according to the rules of engagement, I was left with 20 uncrossed numbers. Using the expressions for the highest and total unavailable values, N = (5 - 1)(11 - 1)/2 = 4x10/2 = 20 and H = 2(20) - 1 = 39.

Considering m = 5 and n = 7 cent stamps, we derive

.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/

Counting, we find 12 impossible postage amounts, the highest being 23 cents. Verifying, the unobtainable N = (n - 1)(m - 1)/2 = (6)(4)/2 = 12 and the highest unobtainable postage becomes H = mn - (m + n) = 5(7) - (5+7) = 35 -12 = 23.

The expressions for calculating the total number of unattainable values and the highest unattainable value derives from the following. Several values of m and n were examined to arrive at the following data.
For n = 7...........N........H.......N..........H......N..........H
m = 3................6........11
m = 4....................................9..........17
m = 5.......................................................12.........23
For n = 11.........N........H.......N..........H......N..........H
m = 3...............10.......19
m = 5..................................20.........39
m = 7.......................................................30.........59
For n = 13.........N........H.......N..........H......N..........H
m = 5...............24......47
m = 7..................................36.........71
m = 11.....................................................60........119

We can now create straight line relationships of the form y = mx + b for each value of n. Letting m be the x value and N and H the y value, we obtain
For n = 7 N = 3m - 3 and h = 6m - 7
For n = 11, N = 5m - 5 and H = 10m -11
For n = 13 N = 6m - 6 and h = 12m - 13

Careful examination of these expressions and the associated data reveal that, for each value of n, the slope in the N expressions is (n-1)/2 while the y intercept is -(n-1)/2. Similarly, for each value of n, the slope of the H expressions is (n-1) while the y intercept is -n. In general then, substituting these expressions for the slope and y intercept in place of the specific numbers derived for specific values of n, we can express the N value by N = (n-1)m/2 - (n-1)/2 which when expanded and simplified results in N = (n-1)(m-1)/2. We can also express the H value by H = (n-1)m - n.
 
You must log in or register to reply here.
Top