MathDB

Let

n,m

be positive integers. Let

A_1,A_2,A_3, ... ,A_m

be sets such that

A_i \subseteq \{1, 2, 3, . . . , n\}

and

|A_i| = 3

for all

i

(i.e.

A_i

consists of three different positive integers each at most

n

). Suppose for all

i < j

we have

|A_i \cap A_j | \le 1

(i.e.

A_i

and

A_j

have at most one element in common). (a) Prove that

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

. (b) Show that for all

n \ge3

it is possible to have

m \ge \frac{(n-1)(n-2)}{ 6}

Problem Statement