LII OM - II - Zadanie 6

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.

Komentarze

Dodaj nową odpowiedź