Maths Olympiad Prep

Library / /228 of 462

Combinatorics Difficulty 5.8 AIME, harder Prove it Ireland

Let n>1n > 1 be an integer and Ω:={1,2,,2n1,2n}\Omega := \{1, 2, \dots, 2n-1, 2n\} the set of all positive integers that are not larger than 2n2n.
A non-empty subset SS of Ω\Omega is called sum-free if, for all elements x,yx, y belonging to SS, x+yx+y does not belong to SS. We allow x=yx=y in this condition.
Prove that Ω\Omega has more than 2n2^n distinct sum-free subsets.

Solution

Any non-empty subset of Ψ={n+1,n+2,,2n}\Psi = \{n+1, n+2, \dots, 2n\} is obviously a sum-free subset of Ω\Omega, and there are 2n12^n - 1 of these. Also, every non-empty subset of the set Φ\Phi of odd numbers in Ω\Omega is also a sum-free subset and there are 2n12^n - 1 of these. The number of common subsets in the union of these two collections is 2n/212^{\lceil n/2 \rceil} - 1. So Ω\Omega has at least 2(2n1)(2n/21)>2n2(2^n - 1) - (2^{\lceil n/2 \rceil} - 1) > 2^n sum-free subsets. Alternatively, for any n2n \ge 2, {1,4}\{1, 4\} and {2,3}\{2, 3\} are sum-free subsets of Ω\Omega and they are neither subsets of Ψ\Psi nor of Φ\Phi. Together with the 2n12^n - 1 non-empty subsets of Ψ\Psi or of Φ\Phi they provide the required 2n+12^n + 1 sum-free subsets.

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.