MathDB

1. Some proper partitions

P_1, \dots , P_n

of a finite set

S

(that is, partitions containing at least two parts) are called independent if no matter how we choose one class from each partition, the intersection of the chosen classes is nonempty. Show that if the inequality
\frac{\left | S \right | }{2} < \left |P_1 \right | \dots \left |P_n \right |\qquad (*)
holds for some independent partitions, then

P_1, \dots , P_n

is maximal in the sense that there is no partition

P

such that

P,P_1, \dots , P_n

are independent. On the other hand, show that inequality

(*)

is not necessary for this maximality. (C.20) [E. Gesztelyi]

Problem Statement