LIII OM - II - Zadanie 3

Zawody matematyczne:

LIII OM, 2001-2002

Etap:

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

$ K_{2}>\frac{n}{4}-\frac{n}{30}. $

Analogicznie stwierdzamy, że

$ K_{i}>\frac{n}{4}-(i-1)\frac{n}{30}\ \textrm{dla}\ i=3,4,5,6. $

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

$ K_{1}+K_{2}+K_{3}+K_{4}+K_{5}+K_{6}>\frac{6n}{4}-(1+2+3+4+5)\frac{n}{30}=n. $

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.