LII OM - II - Zadanie 6

Zawody matematyczne:

LII OM, 2000-2001

Etap:

Dla danej liczby całkowitej dodatniej $n$ rozstrzygnąć, czy podzbiorów $n$ -elementowych zbioru $\{1,2,3,\ldots,2n-1,2n\}$ mających sumę elementów parzystą jest tyle samo, co podzbiorów $n$ -elementowych mających nieparzystą sumę elementów. Jeśli nie, to rozstrzygnąć, których jest więcej i o ile.

Rozwiązanie

Połączmy liczby ze zbioru $S = \{1,2,3,\ldots,2n-1,2n\}$ w pary:

$<br /> (1,2),\ (3,4),\ \ldots, (2n-1,2n).<br />$

Niech $X$ będzie dowolnym $n$ -elementowym podzbiorem zbioru $S$ . Wybierzmy (jeśli jest to możliwe) najmniejszą liczbę $x$ ze zbioru $X$ o tej własności, że liczba $y$ występująca w parze z liczbą $x$ nie należy do zbioru $X$ . Następnie usuńmy ze zbioru $X$ element $x$ zastępując go elementem $y$ . Otrzymany zbiór nazwijmy $f(X)$ . Zbiory $X$ i $f(X)$ mają sumy elementów różnej parzystości.

W dalszej części rozwiązania rozpatrzymy dwa przypadki:

(a) Liczba $n$ jest nieparzysta.

Odwzorowanie $f$ jest określone dla dowolnego $n$ -elementowego podzbioru zbioru $S$ i łączy ono w pary $(X,f(X))$ wszystkie podzbiory $n$ -elementowe o nieparzystej sumie elementów ze wszystkimi $n$ -elementowymi podzbiorami o sumie elementów parzystej. To dowodzi, że $n$ -elementowych podzbiorów o parzystej sumie elementów jest tyle samo, co $n$ -elementowych podzbiorów o nieparzystej sumie elementów.

(b) Liczba $n$ jest parzysta.

W tym przypadku odwzorowania $f$ nie da się określić jedynie na tych $n$ -elementowych podzbiorach zbioru $S$ , które są złożone z pełnych par. Zbiorów tych jest $n \choose {n/2}$ i wszystkie one mają sumę elementów o takiej samej parzystości, jak parzystość liczby $n/2$ . Pozostałe podzbiory możemy połączyć w pary $(X,f(X))$ . Jeżeli $n$ dzieli się przez cztery, to $n$ -elementowych podzbiorów o parzystej sumie elementów jest o ${n \choose n/2}$ więcej niż $n$ -elementowych podzbiorów o nieparzystej sumie elementów. Jeśli natomiast $n$ nie dzieli się przez cztery, to podzbiorów o nieparzystej sumie elementów jest o ${n \choose n/2}$ więcej.