Combining Boxes

Date: 04/27/98 at 15:26:43
From: John Grainger
Subject: What is the largest possible number?

Uncle Dube's Dandelion Delectables come only in boxes of 6, 9 or 20. 
What is the largest number of Delectables you can't buy?

Date: 04/29/98 at 14:01:47
From: Doctor Jen
Subject: Re: What is the largest possible number?

Okay. I assume you're not allowed to say: "I have a box of 20 
delectables, and I'll throw two away, therefore I have 18" ... and 
other similar ideas. Because that way you could get ANY number of 
items, and the number you can't make wouldn't exist.

So now the question becomes: "What is the largest number you can't 
make by adding together 6, 9 and 20?"

If we think about the problem for a minute, we see that if we can find 
a way of making six consecutive numbers, we will be able to make every 
number after that. Suppose we find a group of six numbers: 
  
  n1, n2, n3, n4, n5, n6

Then if we keep adding six to these, we can make any number we like. 
Do you see that? 

So, if we can find a group of six consecutive numbers, we'll know that 
the largest number we can't make lies below the first of these.

Well, here's how I did it but I'm not saying there's no other way:
 
9 + 6 + 6 = 21. So if I have a number, replacing a box of 20 with 
9 + 6 + 6 gives me one more than that number, right?

Well, 5 boxes of 20 give me 100. And:
 
     4*20 + 9 + 6 + 6    = 101
     3*20 + 2(9 + 6 + 6) = 102
     2*20 + 3(9 + 6 + 6) = 103
     1*20 + 4(9 + 6 + 6) = 104
     5(9 + 6 + 6)        = 105

So here we have six consecutive numbers. So we know that the largest 
number we can't make is less than 100, because 100 is the first of 
this six, and we can now make any number that is greater than 100.

Then I started from 99, and worked backwards, seeing which numbers 
could be made up. 99 can be made, because it's 11*9. 98 can be made, 
because it's 4*20 + 2*9. 

It sounds as though that would take a long time, but it's surprisingly 
quick - you can eliminate multiples of 6, 9 and 20 straight off. Then 
you can add these multiples to get other possible numbers. If you 
write out the numbers 1-99 and cross them off as you go, you won't 
forget where you've got to. Do try for yourself, and make sure it 
works.

Anyway, I worked down like that until I got to 43 - and that I believe 
is the answer. 

-Doctor Jen,  The Math Forum
Check out our web site! http://mathforum.org/dr.math/