Concursul "Stelele Matematicii "2012 -juniori pr 4.

[anamariaradu]

Fie $X$ o multime cu $|X|=n\ge 1$ elemente . O familie $F$ de subultimi distincte ale lui $X$ este zisa a avea proprietea $P$ daca exista $A, B \in F$ astfel incat $A \subset B$ si $|B-A|=1$.
i)Demonstrati ca $m= 2^{n-1}$ este cea mai mica valoare , astfel incat orice familie $F$ cu $|F| >m$ sa aiba proprietatea $P$.
ii)Gasiti toate familie $F$ cu $|F|=2^{n-1}$, si care nu au proprietatea $P$.

[Laurențiu Ploscaru]

Considerăm graful $G$ în care mulţimea $V$ a vârfurilor reprezintă cele $2^n$ submulţimi ale lui $X$. Punem muchie între două vârfuri dacă submulţimile $A$ şi $B$ corespunzătoare lor respectă proprietăţile $A\in B$ şi $|B-A|=1$.
Partiţionăm $V$ în $n+1$ submulţimi $V_0,V_1,V_2,...,V_n$ astfel încât în $V_i$ se află vârfurile ce corespund mulţimilor de cardinal $i$, unde $i=\overline{0,n}$.
Să observăm că dintr-un vârf $v\in V_t$ pleacă $t$ muchii în $V_{t-1}$ şi $n-t$ muchii în $V_{t+1}$, aşadar $deg(v)=n$ pentru orice vârf $v$ la grafului. O consecinţă imediată este că graful are $n\cdot 2^{n-1}$ muchii.
Cerinţa problemei este echivalentă cu a arăta că o componentă liberă a grafului are cel mult $2^{n-1}$ vârfuri şi să determinăm componentele libere cu număr maxim de vârfuri.
Prima parte este o simplă reducere la absurd; presupunem că există o componentă liberă cu cel puţin $2^{n-1}+1$ vârfuri, atunci orice vârf $w$ din aceasta trimite cele $n$ muchii în exterior, deci am avea măcar $n(2^{n-1}+1)$ muchii, ceea ce reprezintă o contradicţie.
Fie $S$ o componentă liberă cu număr maxim de vârfuri. Pentru partea a doua avem nevoie doar de următoarele observaţii uşor de arătat:
1. Dacă pentru un $k=\overline{1,n}$ avem $V_k\subset S$, atunci $V_{k-1}\cap S=\emptyset$.
2. Dacă pentru un $k=\overline{1,n}$ avem $V_k\cap S=\emptyset$, atunci $V_{k-1}\subset S$.
Având doar două posibilităţi, şi anume $X\in S$ sau $X\notin S$, obţinem pe baza argumentelor de mai sus că avem două componente libere cu număr maxim de vârfuri, şi anume familiile ce conţin mulţimile $V_{\widehat{0}}$ şi $V_{\widehat{1}}$, clasele fiind luate modulo $2$.
O simplă identitate între coeficienţii binomiali, $\displaystyle\sum_{k=0}^{\lceil n/2\rceil -1}\dbinom{n}{2k+1}=\displaystyle\sum_{k=0}^{\lfloor n/2\rfloor}\dbinom{n}{2k}$, arată că acestea au exact $2^{n-1}$ vârfuri.