Maths Olympiad Prep

Track / Stage 5 / 134 of 400 #734 of 1964

Problem 734

AIME late
Combinatorics Difficulty 5.3 Find the answer

6. Let the set M={1,2,,1000}M=\{1,2, \cdots, 1000\}, and for any non-empty subset XX of MM, let aXa_{X} denote the sum of the largest and smallest numbers in XX. Then, the arithmetic mean of all such aXa_{X} is \qquad .

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

Official solutions — 2

Solution 1

6. Pair the non-empty subsets of MM. For each non-empty subset XMX \subset M, let
X={1001xxX}, X^{\prime}=\{1001-x \mid x \in X\},

then when X1X_{1} is also a non-empty subset of MM, and XX1X \neq X_{1}, we have XX1X^{\prime} \neq X^{\prime}{ }_{1}. Thus, all non-empty subsets are divided into two categories: (A) XXX^{\prime} \neq X, (B) X=XX^{\prime}=X.

For XX in (B), it must be that αX=1001\alpha_{X}=1001. For a pair of XX and XX^{\prime} in (A), we have αX+αX=1001×2=2002\alpha_{X}+\alpha_{X^{\prime}}=1001 \times 2=2002. From this, it is evident that the arithmetic mean of all αX\alpha_{X} is 1001.

Solution 2

1001
6. 【Analysis and Solution】Pair the non-empty subsets of MM. For each non-empty subset XMX \subset M, let
X={1001xxX} X^{\prime}=\{1001-x \mid x \in X\} \text {, }

then when X1X_{1} is also a non-empty subset of MM, and XX1X^{\prime} \neq X_{1}, we have XX1X^{\prime} \neq X^{\prime}{ }_{1}. Thus, all non-empty subsets are divided into two categories:
(A) XXX^{\prime} \neq X, (B) X=XX^{\prime} = X.

For XX in (B), it must be that ax=1001a_{x}=1001. For a pair of XX and XX^{\prime} in (A), we have ax+ax=1001×2=2002a_{x}+a_{x^{\prime}}=1001 \times 2=2002. Therefore, the arithmetic mean of all axa_{x} is 1001.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.