XXXIII OM - I - Zadanie 5

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

W pewnym zakładzie pracy każdy pracownik jest członkiem dokładnie jednego ze 100 związków zawodowych. Pracownicy mają wybrać dyrektora spośród dwóch kandydatów. Członkowie każdego ze związków umawiają się, czy wstrzymują się od głosu lub na którego z dwóch kandydatów będą głosować. Dowieść, że istnieje taki związek, że jeśli jego członkowie wstrzymają się od głosowania, a członkowie wszystkich innych związków będą głosować na któregoś z dwóch kandydatów, to kandydaci na dyrektora nie otrzymają równej liczby głosów.

Rozwiązanie

Niech $a_1, a_2, \ldots, a_{100}$ będą odpowiednio liczbami członków poszczególnych związków. Możemy założyć, że pewna z liczb $a_1, \ldots, a_{100}$ (np. $a_j$ ) jest nieparzysta, gdyż w przeciwnym razie podzielilibyśmy wszystkie $a_i$ przez maksymalną potęgę dwójki dzielącą je wszystkie. Jeżeli teraz suma $a_1+ \ldots+ a_{100}$ jest liczbą parzystą, to jeśli członkowie $i$ -tego związku wstrzymają się od głosu, to liczba pozostałych głosów $a_1+ \ldots+a_{j-1}+a_{j+1} + \ldots+ a_{100}$ będzie nieparzysta. Zatem liczby głosów oddanych na każdego kandydata nie mogą być równe. Jeśli natomiast suma $a_1+ \ldots+ a_{100}$ jest liczbą nieparzystą, to pewien jej składnik musi być parzysty (suma stu liczb nieparzystych jest liczbą parzystą), niech na przykład $a_k = 2s$ . Jeżeli w tym przypadku członkowie $k$ -tego związku wstrzymają się od głosu, suma $a_1 + \ldots a_{k-1} + a_{k+1} + \ldots + a_{100}$ jest liczbą nieparzystą. Liczby głosów oddanych na poszczególnych kandydatów nie mogą być równe.