Maths Olympiad Prep

Library / /68 of 860

Combinatorics Difficulty 4.7 AIME Find the answer

How many nonempty subsets of {1,2,3,,12}\{1,2,3, \ldots, 12\} have the property that the sum of the largest element and the smallest element is 13?

A number or a short expression. Spacing and $ signs are ignored.

Solution

If aa is the smallest element of such a set, then 13a13-a is the largest element, and for the remaining elements we may choose any (or none) of the 122a12-2 a elements a+1,a+2,,(13a)1a+1, a+2, \ldots,(13-a)-1. Thus there are 2122a2^{12-2 a} such sets whose smallest element is aa. Also, 13aa13-a \geq a clearly implies a<7a<7. Summing over all a=1,2,,6a=1,2, \ldots, 6, we get a total of 210+28+26++20=45+44++40=(461)/(41)=4095/3=13652^{10}+2^{8}+2^{6}+\cdots+2^{0}=4^{5}+4^{4}+\cdots+4^{0}=\left(4^{6}-1\right) /(4-1)=4095 / 3=1365 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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.