Maths Olympiad Prep

Library / /24 of 86

Combinatorics Difficulty 6.2 National Olympiad Prove it United States

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 1.511.51 to buy one of every kind. (There is no discount based on the number of candies in a purchase.) Unfortunately, Anna only has 0.750.75.

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

Solution:

For part (a), pick boxes containing 22 different candies chosen at random. Let their total cost be mm cents. If m75m \leq 75, Anna can buy these candies. Otherwise, m76m \geq 76. In this case, the other 22 candies have a total cost of 151m75151-m \leq 75 cents, so Anna can buy those candies instead.

For part (b), rank the candies from most to least expensive and consider the 19th19^{\text{th}} 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 19th19^{\text{th}} 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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.