Evident ca daca demonstram pentru
\( m=2^{n-1}+1 \), afirmatia va fi adevarata si pentru un numar mai mare.
Deoarece sunt mai mult de jumatate dintre submultimile lui
\( \{1,2,3,...,n\} \) exista 2 disjuncte nevide astfel incat reuniunea lor este
\( \{1,2,...,n\} \). (le grupam in perechi
\( (X,\ \{1,2,...,n\}\setminus X) \)) Deci daca
\( \{1,2,...,n\} \) este in familie, atunci problema este rezolvata.
Pentru
\( n=3 \) multimile pot fi:
\( \{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\} \). Se poate observa ca daca alegem 5 submultimi diferite de
\( \{1,2,3\} \), proprietatea ceruta este adevarata.
Sa demonstram prin inductie proprietatea. Presupunem ca pentru
\( n \) este adevarata. Sa o demonstram pentru
\( n+1 \).
Daca avem o familie de
\( m= 2^{n}+1 \) submultimi distincte ale multimii
\( \{1,2,...,n+1\} \), atunci ori exista
\( 2^{n-1}+1 \) submultimi incluse in
\( \{1,2,...,n\} \), ori exista
\( 2^{n-1}+1 \) submultimi care contin pe
\( n+1 \). Fie
\( B_1,...,B_{m} \) aceste sub multimi.(care sunt ori in primul caz, ori in celelalt)
Atunci multimile
\( B_i\cap \{1,2,...,n\} \) satisfac ipoteza de inductie si evident ca vom avea trei submultimi cu proprietatea ceruta.
Cu aceasta, problema este rezolvata.