MathDB

1

Part of 2004 Singapore MO Open

Problems(1)

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

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

4/3/2020
Let m,nm,n be integers so that m≥n>1m \ge n > 1. Let F1,...,FkF_1,...,F_k be a collection of nn-element subsets of {1,...,m}\{1,...,m\} so that Fi∩FjF_i\cap F_j contains at most 11 element, 1≤i<j≤k1 \le i < j \le k. Show that k≤m(m−1)n(n−1)k\le \frac{m(m-1)}{n(n-1)}
combinatoricsSubsetsinequalities