Problem:
C/1 Sugar Station sells 44 different kinds of candies, packaged one to a box. Each box is priced at a positive integer number of cents, and it costs to buy one of every kind. (There is no discount based on the number of candies in a purchase.) Unfortunately, Anna only has .
a) Show that Anna can buy at least 22 boxes, each containing a different candy.
b) Show that Anna can do even better, buying at least 25 boxes, each containing a different candy.
Solution:
For part (a), pick boxes containing 22 different candies chosen at random. Let their total cost be cents. If , Anna can buy these candies. Otherwise, . In this case, the other 22 candies have a total cost of cents, so Anna can buy those candies instead.
For part (b), rank the candies from most to least expensive and consider the candy in the ranking. If this candy costs 4 cents or more, then the first 19 candies cost at least 76 cents and so the last 25 candies cost at most 75 cents. But if the most expensive candy costs 3 cents or less, then so do the remaining 25 candies in the list, so the last 25 candies again cost at most 75 cents.