MathDB

Let

n \geq 2

be an integer, let

S

be a set of

n

elements, and let

A_i , \; 1\leq i \leq m

, be distinct subsets of

S

of size at least

2

such that A_i \cap A_j \not\equal{} \emptyset, A_i \cap A_k \not\equal{} \emptyset, A_j \cap A_k \not\equal{} \emptyset, \;\textrm{imply}\ \;A_i \cap A_j \cap A_k \not\equal{} \emptyset \ . Show that m \leq 2^{n\minus{}1}\minus{}1. P. Erdos

Problem Statement