MathDB

k<= m(m-1)/n(n-1) for n-elements subsets of {1,...,m}

Source: Singapore Open Math Olympiad 2004 2nd Round p1 SMO

April 3, 2020

combinatoricsSubsetsinequalities

Problem Statement

Let

m,n

be integers so that

m \ge n > 1

. Let

F_1,...,F_k

be a collection of

n

-element subsets of

\{1,...,m\}

so that

F_i\cap F_j

contains at most

1

element,

1 \le i < j \le k

. Show that

k\le \frac{m(m-1)}{n(n-1)}