Competition problem — Combinatorics

Library / /67 of 520

Combinatorics Difficulty 5.5 AIME, harder Prove it

Let $A$ be a finite set of (not necessarily positive) integers, and let $m \geqslant 2$ be an integer. Assume that there exist non-empty subsets $B_{1}, B_{2}, B_{3}, \ldots, B_{m}$ of $A$ whose elements add up to the sums $m^{1}, m^{2}, m^{3}, \ldots, m^{m}$ , respectively. Prove that $A$ contains at least $m / 2$ elements.

Solution

Let $A=\left\{a_{1}, \ldots, a_{k}\right\}$ . Assume that, on the contrary, $k=|A|0$ and large enough $m$ we get $k \geqslant(1 / 2-\varepsilon) m$ . The proof uses the fact that the combinations $\sum c_{i}!$ with $c_{i} \in\{0,1, \ldots, i\}$ are all distinct. Comment 2. The problem statement holds also if $A$ is a set of real numbers (not necessarily integers), the above proofs work in the real case.

Note: The original text already appears to be in English. If there was a specific part or a different text you wanted translated, please let me know!

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.