Szczególne podzbiory

[mol_ksiazkowy]

\(\displaystyle{ A_1,...A_n}\) są podzbiorami zbioru \(\displaystyle{ S= \{ 1, ..., 200 \}}\) i jeśli \(\displaystyle{ a, b \in S}\) to istnieje \(\displaystyle{ j}\) : \(\displaystyle{ a, b \in A_j}\) ale żadna liczba z przedziału \(\displaystyle{ (a, b)}\) nie należy do \(\displaystyle{ A_j}\). Udowodnić, że \(\displaystyle{ n \geq 10^4}\)

[kerajs]

Przedziałem jednostkowym o końcach będących liczbami ze zbioru S który najczęściej będzie występował w \(\displaystyle{ (a,b)}\) będzie przedział (100,101). Wystąpi on dla par a, b:
\(\displaystyle{ 1 \ \ 101 \\
\ \ 1 \ \ 102 \\
\ \ 1 \ \ 103 \\
.... \\
\ \ 1 \ \ 200 \\
\\
\ \ 2 \ \ 101 \\
\ \ 2 \ \ 102 \\
\ \ 2 \ \ 103 \\
.... \\
\ \ 2 \ \ 200 \\
\\
...\\
...\\
...\\
...\\
\\
100 \ \ 101 \\
100 \ \ 102 \\
100 \ \ 103 \\
.... \\
100 \ \ 200}\)
których jest \(\displaystyle{ 10^4}\), więc liczba podzbiorów \(\displaystyle{ A_i}\) nie może być mniejsza.

Pozostaje wskazać takie podzbiory \(\displaystyle{ A_i}\) które spełniają tezę, a ich liczność jest równa \(\displaystyle{ 10^4}\)
Przykład takich podzbiorów to:
\(\displaystyle{ \left\{ 1,200\right\} , \left\{ 2,199\right\} ,\left\{ 3,198\right\} , .... ,\left\{ 100,101\right\} , \\
\left\{ 1,2,200\right\} , \left\{ 1,3,200\right\} ,\left\{ 1,4,200\right\} , .... , \left\{ 1,199,200\right\}, \\
\left\{ 2,3,199\right\} , \left\{ 2,4,199\right\} ,\left\{ 2,5,199\right\} , .... , \left\{ 2,198,199\right\}, \\
....\\
....\\
....\\
\left\{ 98,99,103\right\} , \left\{ 98,100,103\right\} ,\left\{ 98,101,103\right\} , \left\{ 98,102,103\right\}, \\
\left\{ 99,100,102\right\} , \left\{ 99,101,102\right\}}\)