Friday, March 27, 2009

solution: 7-11

The question was posed in terms of tuck-shop coupons, but this problem is classically stated in terms of postage stamps. Essentially,

What is the largest number which cannot be expressed as a sum of 7's and 11's?

Consider a different (but related) question: If we have an amount that is possible, how can we increase it by one? Since there is no one-rupee stamp, we would have to trade some appropriate combination of stamps to accomplish an increase. Add a few whose sum is N, take away a few whose sum is N-1. It is also worth mentioning that the trade will only be 7's for 11's or 11's for 7's. We will not have to worry about some complicated mixture. (if we gave a 7 and received a 7 we could ignore the 7 in both cases and accomplish the same change).

The problem becomes: can we find the smallest multiple of 7 which is one less than a multiple of 11? Or, can we find the smallest multiple of 11 which is one less than a multiple of 7? Take 3*7=21, which is one less than 2*11=22. Also, 5*11=55, which is one less than 7*8=56.
What this means is that to take an amount which works and increase it by one, we can either trade three 7's or five 11's. If either of the two options is available to us, then the next amount can be expressed in terms of 7's and 11's.

The amounts which do work but cannot be increased are those numbers which are the sum of fewer than three 7's and fewer than five 11's. The largest of these numbers will have two 7's and four 11's; 2*7+4*11=58 is therefore the largest number which cannot be increased, which means that 59 cannot be constructed as a sum of 7's and 11's. The next number, 60, can be made (with one 11 and seven 7's), so every number greater than or equal to 60 can be made with 7's and 11's.

Therefore 59 is the largest number which cannot be expressed as a sum of 7's and 11's.

No comments:

Post a Comment