Maths Olympiad Prep

Track / Stage 5 / 174 of 400 #774 of 1964

Problem 774

AIME late
Combinatorics Difficulty 5.4 Find the answer

(13) (50 points) Let k,nk, n be given integers, n>k2n > k \geqslant 2. For any nn-element set PP, consider the sums of the elements of all kk-element subsets of PP, and let the set of these sums be QQ. The number of elements in the set QQ is denoted as CQC_{Q}. Find the maximum value of CQC_{Q}.

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

Official solution

(13) The maximum value of CQC_{Q} is Cnk\mathrm{C}_{n}^{k}.
Since PP has Cnk\mathrm{C}_{n}^{k} kk-element subsets, it is obvious that CQCnkC_{Q} \leqslant \mathrm{C}_{n}^{k}.
Below, we point out that for the set P={2,22,,2n}P=\left\{2,2^{2}, \cdots, 2^{n}\right\}, the corresponding CQC_{Q} equals Cnk\mathrm{C}_{n}^{k}, i.e., the sum of elements of any two different kk-element subsets of PP are not equal. Thus, the maximum value of CQC_{Q} is Cnk\mathrm{C}_{n}^{k}.

In fact, if the set PP has two different kk-element subsets A={2r1A=\left\{2^{r_{1}}\right., 2r2,,2rk},B={2s1,2s2,,2sk}\left.2^{r_{2}}, \cdots, 2^{r_{k}}\right\}, B=\left\{2^{s_{1}}, 2^{s_{2}}, \cdots, 2^{s_{k}}\right\}, such that the sums of the elements of AA and BB are equal, then
2r1+2r2++2rk=2s1+2s2++2sk=M. 2^{r_{1}}+2^{r_{2}}+\cdots+2^{r_{k}}=2^{s_{1}}+2^{s_{2}}+\cdots+2^{s_{k}}=M .

Since (1) can be viewed as the binary representation of the positive integer MM, and since rir_{i} are distinct and sis_{i} are distinct, by the uniqueness of the binary representation of positive integers, we deduce from (1) that the set {r1\left\{r_{1}\right., r2,,rk}\left.r_{2}, \cdots, r_{k}\right\} must be the same as {s1,s2,,sk}\left\{s_{1}, s_{2}, \cdots, s_{k}\right\}, thus the subsets A=BA=B, which is a contradiction.
This proves our conclusion.

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