MathDB

9

Part of 1997 Taiwan National Olympiad

Problems(1)

subset with at least $[\log_2{n}]+1$ elements

Source: 6-th Taiwanese Mathematical Olympiad 1997

1/18/2007
For n≥k≥3n\geq k\geq 3, let X={1,2,...,n}X=\{1,2,...,n\} and let FkF_{k} a the family of kk-element subsets of XX, any two of which have at most k−2k-2 elements in common. Show that there exists a subset MkM_{k} of XX with at least [log⁡2n]+1[\log_{2}{n}]+1 elements containing no subset in FkF_{k}.
logarithmscombinatorics unsolvedcombinatorics