LIII OM - II - Zadanie 3

W $ n $-osobowym stowarzyszeniu działa sześć komisji. W skład każdej z nich wchodzi nie mniej niż $ n/4 $ osób. Dowieść, że istnieją dwie komisje oraz grupa licząca nie mniej niż $ n/30 $ osób, należących do obu tych komisji.

Rozwiązanie

Ponumerujmy komisje liczbami $ 1,2,\ldots,6 $ i oznaczmy przez $ K_i $ liczbę tych członków $ i $-tej komisji, którzy nie są członkami żadnej komisji o numerze mniejszym od $ i $.

$ K_1 $ to liczba wszystkich członków komisji nr $ 1 $, co daje $ K_1 \geq n/4 $.

Przypuśćmy, że część wspólna dowolnych dwóch komisji liczy mniej niż $ n/30 $ osób.

Ponieważ w skład komisji nr $ 2 $ wchodzi co najmniej $ n/4 $ osób, więc liczba tych członków komisji nr $ 2 $, którzy nie są w komisji nr $ 1 $ musi być większa od $ n/4 $ - $ n/30 $. Stąd

\[<br />
K_{2}>\frac{n}{4}-\frac{n}{30}.<br />
\]

Analogicznie stwierdzamy, że

\[<br />
K_{i}>\frac{n}{4}-(i-1)\frac{n}{30}\ \textrm{dla}\ i=3,4,5,6.<br />
\]

Dodając stronami powyższe nierówności uzyskujemy

\[<br />
K_{1}+K_{2}+K_{3}+K_{4}+K_{5}+K_{6}>\frac{6n}{4}-(1+2+3+4+5)\frac{n}{30}=n.<br />
\]

Otrzymaliśmy sprzeczność, gdyż wielkość $ K_{1}+K_{2}+\ldots+K_{6} $ jest nie większa od liczby wszystkich członków stowarzyszenia, czyli $ n $. Zatem do części wspólnej pewnych dwóch komisji należy co najmniej $ n/30 $ osób.

Komentarze

Dodaj nową odpowiedź