Skrypcik: tw. Olsona i zadanie o 2n liczbach

31 marca 2005

Rozważamy takie zadanie:

Zadanie. Dana jest liczba naturalna n > 1. Wykaż, że spośród 2n − 1 liczb całkowitych można wybrać n o sumie podzielnej przez n.

Mimo prostego sformułowania jest to trudne zadanie. Po dłuższej chwili myślenia zauważmy, że:

Spostrzeżenie. Wystarczy udowodnić ten fakt dla n b_{}ed _{}acych liczb _{}a pierwsz _{}a.

Dowód. Niech n = ab, a, b > 1. Niech T (x) oznacza, że teza zadania zachodzi dla n = x. Jeśli wykażemy, że T (a), T (b) ⇒ T (ab), to b_{}edzie to oznaczało, że jeśli T (p) dla każdej pierwszej p, to T (n) dla każdego n > 1. Niech wi_{}ec a b > 1. Weźmy wobec tego 2ab−1 liczb całkowitych. Z pierwszych 2a − 1 liczb wybieramy a o sumie podzielnej przez a, pozostałe a − 1 wrzucamy spowrotem do puli liczb - mamy ich teraz (2b − 1)a − 1. Jesteśmy w stanie tak wybierać 2b − 1 razy, po tym ruchu zostanie nam a − 1 liczb, z którymi już nic nie zrobimy. Mamy wi_{}ec 2b − 1 zbiorów po a liczb, każdy o sumie podzielnej przez a. Weźmy teraz 2b − 1 liczb, b_{}ed _{}acych sumami tych zbiorów podzielonymi przez a. Wybieramy z tych liczb b o sumie podzielnej przez b i suma tych wybranych ab liczb (z tych zbiorów co wybraliśmy liczby przez nie stworzone) dzieli si_{}e przez ab.

■

Wobec tego możemy si_{}e zaj _{}ać rozważaniami tylko dla n = p pierwszych. Spróbujmy zrobić to nie wprost i zastosować mega-super-bajer sztuczk_{}e.

Weźmy wszystkie możliwe podzbiory naszych 2p − 1 liczb. Jest ich \binom{2p−1}{p}, co nie dzieli si_{}e przez p. Dodajmy p − 1-sze pot_{}egi sum tych podzbiorów. Robimy nie wprost – każda suma jest niepodzielna przez p, wi_{}ec z Małego Twierdzenia Fermata p − 1-sza pot_{}ega przystaje do 1 modulo p. Czyli cała suma jest sum _{}a \binom{2p−1}{p} jedynek modulo p, czyli nie dzieli si_{}e przez p.

Oznaczmy te liczby a_{1}, a_{2}, …, a_{2p−1} . Spójrzmy na wyrażenie a_{1}^{k_{1}}a_{2}^{k_{2}} …a_{2p−1}^{k_{2p−1}} , przy czym k_{1} + … + k_{2p−1} = p − 1. Ile razy takie wyrażenie powstanie przy rozbiciu naszej sumy z wzorów dwumianowych Newtona (tj jaki b_{}edzie przy nim współczynnik)? Niech w nim k liczb spośród k_{1}, …, k_{2p−1} jest dodatnich. Każde takie wyrażenie powstaje z składnika sumy, gdzie w zbiorze sumowanym wyst_{}epuj _{}a wszystkie liczby o dodatnich wykładnikach k_{i}. Wobec tego takich nawiasów jest \binom{2p−1−k}{p−k} (wybieramy pozostałe liczby to tych k liczb). Ta liczba dla 0 < k < p jest podzielna przez p. Przy tym oczywiście, z każdego nawiasu współczynnik przy tym wyrazie b_{}edzie taki sam. Wobec tego Współczynnik przy tym wyrazie b_{}edzie podzielny przez p. Czyli cała suma b_{}edzie podzielna przez p, sprzeczność.

■

To był bardzo pomysłowy dowód. A teraz twierdzenie, które załatwia takie przypadki: Twierdzenie Olsona. Niech k > 1 b_{}edzie liczb _{}a całkowit _{}a, a p liczb _{}a pierwsz _{}a. Spośród

k(p − 1) + 1 elementów grupy ℤ_{p}^{k} można wybrać niepusty podzbiór o sumie zero.

Gwoli wyjaśnienia: grupa ℤ_{p}^{k} to elementy zbioru {0, 1, …, p − 1}^{k} (czyli każdy element to k reszt modulo p) z dodawaniem na każdej współrz_{}ednej modulo p.

Stosuj _{}ac to twierdzenie już bardzo łatwo rozwi _{}azać zadanie dla n = p pierwszych: niech nasze liczby to b_{}ed _{}a a_{1}, a_{2}, …, a_{2p−1} , weźmy do tw. Olsona dla k = 2 liczby (a_{i}, 1). Istnieje ich podzbiór o sumie (0, 0), ale skoro tak, to tych liczb musi być p, aby druga współrz_{}edna si_{}e wyzerowała. Czyli istnieje p liczb spośród danych o sumie podzielnej przez p.

■