Reuniune fortata de submultimi

[Filip Chindea]

Fie \( n \ge 3 \) intreg si \( m \ge 2^{n - 1} + 1 \). Sa se arate ca orice familie de submultimi distincte, nevide \( (A_j)_{j \in \overline{1, m}} \) ale lui \( \{1, 2, ..., n\} \) are proprietatea ca exista \( i, j, k \) distincti cu \( A_i \cup A_j = A_k \).

[TST IV 2008, Problema 3, autor: Marius Cavachi]

[Beniamin Bogosel]

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.

[Filip Chindea]

Atunci multimile \( B_i\cap \{1,2,...,n\} \) satisfac ipoteza de inductie [...]

Numai daca sunt nevide!

PS. Poate ca este necesara o ipoteza inductiva mai tare - deocamdata nu am idee de vreo solutie (si se pare ca oricum pragul propus poate fi imbunatatit). In orice caz, abordarea standard a fost in mare ca mai sus.

[Beniamin Bogosel]

In cazul in care una e vida, inseamna ca e chiar \( \{n+1\} \), si cred ca se poate repara solutia...