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.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź