MathDB

7

Part of 2015 Irish Math Olympiad

Problems(1)

sum- free subsets of set of all positive integers not larger than 2n

Source: Irmo 2015 p2 q7

9/16/2018
Let n>1n > 1 be an integer and Ω={1,2,...,2n−1,2n}\Omega=\{1,2,...,2n-1,2n\} the set of all positive integers that are not larger than 2n2n. A nonempty subset SS of Ω\Omega is called sum-free if, for all elements x,yx, y belonging to S,x+yS, x + 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.
combinatoricsSetsSubsets