MathDB

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

Source: 6-th Taiwanese Mathematical Olympiad 1997

January 18, 2007

logarithmscombinatorics unsolvedcombinatorics

Problem Statement

For

n\geq k\geq 3

, let

X=\{1,2,...,n\}

and let

F_{k}

a the family of

k

-element subsets of

X

, any two of which have at most

k-2

elements in common. Show that there exists a subset

M_{k}

X

with at least

[\log_{2}{n}]+1

elements containing no subset in

F_{k}