Powiedzmy, że rodzina zbiorów jest zamknieta na sumowanie, gdy wraz ze zbiorami \(\displaystyle{ A,B}\) tej rodziny, do rodziny należy także \(\displaystyle{ A\cup B}\)
Hipoteza Frankla
Dla dowolnej skończonej i zamknietej na sumowanie rodziny zbiorów \(\displaystyle{ \mathcal{A}}\), gdzie \(\displaystyle{ \bigcup \mathcal{A} \neq \left\{ \right\}}\), to istnieje element \(\displaystyle{ x \in \bigcup \mathcal{A}}\), który należy do przynajmniej polowy zbiorów tej rodziny.
Niech \(\displaystyle{ \mathcal{A}}\) będzie taką rodziną zbiorów. Niech zawiera ona \(\displaystyle{ n}\) zbiorów niepustych i być może zbiór pusty \(\displaystyle{ \mathcal{A}=\left\{ A _{1}, A _{2},\ldots,A _{n},\varnothing \right\}}\) -
\(\displaystyle{ n+1}\) maksymalnie zbiorów
Łatwo sprawdzić, że dla \(\displaystyle{ n=1}\) oraz dla \(\displaystyle{ n=2}\) hipoteza jest prawdziwa.
Możemy zatem założyć że \(\displaystyle{ n \ge 3}\)
\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|c|}
A_{1} & A _{2} & \ldots & A_{n-1} &A_{n}& \varnothing\\ \hline
A_{1}\cup A_{2} & A_{2}\cup A_{3} & \ddots & A_{n-1}\cup A_{n} & & \\
A_{1}\cup A_{3}&A_{2}\cup A_{4} & \\
\vdots & \vdots & \\
A_{1}\cup A_{n} & A_{2}\cup A_{n} & \\
\end{tabular}}\)
W tej tabeli wypisałem tyle niekoniecznie różnych zbiorów w postaci sum:
\(\displaystyle{ \left( n-1\right) +\left( n-2\right) +\left( n-3\right)+ \ldots +1= \frac{\left( n-1\right) \cdot n}{2}}\)
Ale te wszystkie zbiory- sumy- należą do rodziny zbiorów \(\displaystyle{ \mathcal{A}}\), bo ta rodzina jest zamknięta na sumowanie.
Zatem wśród tych zbiorów jest tylko co najwyżej \(\displaystyle{ n+1}\) różnych zbiorów.
Ukryta treść:
Zatem znajdzie się tam zbiór, który wystapi co najmniej \(\displaystyle{ \frac{\left( n-1\right) \cdot n}{2 \cdot \left( n-2\right)} >n/2}\) razy. Zatem wystapi on co najmniej \(\displaystyle{ \frac{n}{2} + \frac{1}{2}= \frac{n+1}{2}}\) razy
Z trudem oszacowałem.
Może was zdziwie, ale nie wiem jak to skończyć.
Wybierzmy jeden z elementów tego zbioru. Weźmy pierwsze przedstawienie, wybrany element wpadnie do jednego ze zbiorów. W porzadku. Weźmy drugie przedstawienie, element wpadnie do chociaż jednego zbioru, ale może do tego samego co poprzednio- może być np. \(\displaystyle{ X=A_{1} \cup A_{2}=A_{1} \cup A_{3}}\)
Takie, itp. mam problemy z powtarzaniem się zbiorów, i nie wiem jak to dokończyć. Jak wybrać ten element?
Proszę o pomoc.
