MathDB

Let

k,m,n

be positive integers such that

1\le m\le n

and denote

S=\{1,2,\ldots,n\}

. Suppose that

A_1,A_2,\ldots,A_k

are

m

-element subsets of

S

with the following property: for every

i=1,2,\ldots,k

there exists a partition

S=S_{1,i}\cup S_{2,i}\cup\ldots\cup S_{m,i}

(into pairwise disjoint subsets) such that
(i)

A_i

has precisely one element in common with each member of the above partition. (ii) Every

A_j,j\ne i

is disjoint from at least one member of the above partition.
Show that

k\le\binom{n-1}{m-1}

Problem Statement