Maths Olympiad Prep

Library / /1 of 15

Combinatorics Difficulty 4.0 AIME Find the answer Philippines

Problem:

How many nonempty subsets of {1,2,,10}\{1,2, \ldots, 10\} have the property that the sum of its largest element and its smallest element is 1111?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

If aa is the smallest element of such a set, then 11a11 - a is the largest element, and for the remaining elements we may choose any (or none) of the 102a10 - 2a elements a+1,a+2,,(11a)1a + 1, a + 2, \ldots, (11 - a) - 1. Thus there are 2102a2^{10 - 2a} such sets whose smallest element is aa. We also require that 11aa11 - a \geq a or a<6a < 6. We see that there are
a=152102a=a=044a=45141=10233=341 \sum_{a=1}^{5} 2^{10 - 2a} = \sum_{a=0}^{4} 4^{a} = \frac{4^{5} - 1}{4 - 1} = \frac{1023}{3} = 341
possible sets.

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.