Ukryta treść:
Nazwijmy osoby \(\displaystyle{ A _{1}, A _{2}, ..., A _{100}}\), oraz porcje lodów \(\displaystyle{ B _{1}, B _{2}, ..., B _{100}}\). Ponadto zbiór zawierający powyższe 200 elementów nazwijmy \(\displaystyle{ X}\). Rozpatrzmy teraz funkcję \(\displaystyle{ f(x) : X \rightarrow \left\{-1,1 \right\} .}\) Funckja ta przyjmuje wartość \(\displaystyle{ 1}\) jeżeli osoba \(\displaystyle{ A _{i}}\) zamówiła lody śmietankowe, i \(\displaystyle{ -1}\) - jeżeli czekoladowe. Analogicznie \(\displaystyle{ f(B _{j}) =1}\) jeżeli \(\displaystyle{ B _{j}}\) są porcją lodów śmietankowych, i \(\displaystyle{ -1}\) jeśli są czekoladowe. Funkcja ta jest o tyle fajna, że wyrażenie \(\displaystyle{ f(A _{k} )f(B _{l})}\) wynosi \(\displaystyle{ 1}\) gdy zamówienie się zgadza (np. osoba która chciała czekoladowe dostała czekoladowe), oraz \(\displaystyle{ -1}\), gdy się nie zgadza. Celem zadania jest więc pokazanie, że istnieje taka permutacja, powiedzmy \(\displaystyle{ \sigma}\), że \(\displaystyle{ \sum_{1}^{100}f(A _{i}) }f(B _{\sigma(i)} ) \ge 52-48 = 4.}\), bo musi być co najmniej 52 zadowolonych klientów (wartości iloczynu równych \(\displaystyle{ 1}\)). Przekształćmy odrobinę tezę, zakładając przy okazji bez straty ogólności, że osoby od \(\displaystyle{ A _{1} do A _{51}}\) zamówiły śmietankowe, a reszta czekoladowe (indeks stojący przy osobie wcale nie oznacza numeru miejsca na którym ona siedzi):
\(\displaystyle{ \sum_{1}^{100}f(A _{i}) }f(B _{\sigma(i)} ) \ge 4}\)
\(\displaystyle{ \sum_{1}^{51}f(A _{i}) }f(B _{\sigma(i)} )+\sum_{52}^{100}f(A _{i}) }f(B _{\sigma(i)} ) \ge 4}\)
\(\displaystyle{ \sum_{1}^{51}1 \cdot f(B _{\sigma(i)} )+\sum_{52}^{100}(-1) \cdot f(B _{\sigma(i)} )\ge 4}\)
\(\displaystyle{ \sum_{1}^{51}f(B _{\sigma(i)}) - \sum_{52}^{100}f(B _{\sigma(i)}) \ge 4}\)
Jest dokładnie 51 śmietankowych i 49 czekoladowych, tak więc \(\displaystyle{ \sum_{1}^{100}f(B _{\sigma(i)})=2}\). Mamy więc:
\(\displaystyle{ \sum_{1}^{51}f(B _{\sigma(i)}) - \sum_{52}^{100}f(B _{\sigma(i)}) \ge 2 + \sum_{1}^{100}f(B _{\sigma(i)})}\)
\(\displaystyle{ \sum_{1}^{51}f(B _{\sigma(i)}) - \sum_{52}^{100}f(B _{\sigma(i)}) \ge 2 + \sum_{1}^{51}f(B _{\sigma(i)})+\sum_{52}^{100}f(B _{\sigma(i)})}\)
\(\displaystyle{ -2 \ge 2 \cdot \sum_{52}^{100}f(B _{\sigma(i)})}\)
\(\displaystyle{ -1 \ge \sum_{52}^{100}f(B _{\sigma(i)})}\).
Zadanie sprowadza się teraz tylko do wykazania, że dla dowolnej permutacji ciągu \(\displaystyle{ (1, 1, ..., 1, -1, -1, ..., -1)}\) (51 jedynek i 49 (-1)-ynek) jesteśmy w stanie wskazać taki \(\displaystyle{ 49-}\)wyrazowy podciąg, którego suma wyrazów jest niewiększa od \(\displaystyle{ -1}\).
Wpiszmy w tym celu w okrąg \(\displaystyle{ 100-}\)kąt foremny i oznaczmy jego wierzchołki przez \(\displaystyle{ M _{1}, M _{2}, ... M _{100}}\) , oraz każdemu wierzchołkowi przypiszmy wartość \(\displaystyle{ 1}\) i \(\displaystyle{ -1}\), przy czym jedynek oczywiście jest dokładnie 51. Jest ich o dwie więcej od \(\displaystyle{ (-1)}\)-ynek, więc gdzieś na okręgu istnieją takie dwa punkty, że \(\displaystyle{ M_{k}}\) i \(\displaystyle{ M_{k+1}}\) mają przypisaną wartość 1. Nie zmniejszymy ogólności zakładając, że są to \(\displaystyle{ M _{1}}\) i \(\displaystyle{ M _{2}}\).
Rozpatrzmy teraz podciągi \(\displaystyle{ (M _{3}, M _{4}, ... , M _{51})}\) i \(\displaystyle{ (M _{52}, M _{53}, ... , M _{100})}\). Łącznie na okręgu tym występuje \(\displaystyle{ 49}\) wierzchołków równych \(\displaystyle{ -1}\), wszystkie muszą znaleźć się w tych dwóch podciągach długości \(\displaystyle{ 49}\), tak więc z zasady szufladkowej Dirichleta w którymś z nich znajdzie się \(\displaystyle{ 25}\) (lub może więcej) \(\displaystyle{ (-1)}\)-ynek, co jest równoznaczne, z tym, że suma wyrazów w jednym z tych podciągów jest mniejsza lub równa \(\displaystyle{ -1}\), co było do udowodnienia
\(\displaystyle{ \sum_{1}^{100}f(A _{i}) }f(B _{\sigma(i)} ) \ge 4}\)
\(\displaystyle{ \sum_{1}^{51}f(A _{i}) }f(B _{\sigma(i)} )+\sum_{52}^{100}f(A _{i}) }f(B _{\sigma(i)} ) \ge 4}\)
\(\displaystyle{ \sum_{1}^{51}1 \cdot f(B _{\sigma(i)} )+\sum_{52}^{100}(-1) \cdot f(B _{\sigma(i)} )\ge 4}\)
\(\displaystyle{ \sum_{1}^{51}f(B _{\sigma(i)}) - \sum_{52}^{100}f(B _{\sigma(i)}) \ge 4}\)
Jest dokładnie 51 śmietankowych i 49 czekoladowych, tak więc \(\displaystyle{ \sum_{1}^{100}f(B _{\sigma(i)})=2}\). Mamy więc:
\(\displaystyle{ \sum_{1}^{51}f(B _{\sigma(i)}) - \sum_{52}^{100}f(B _{\sigma(i)}) \ge 2 + \sum_{1}^{100}f(B _{\sigma(i)})}\)
\(\displaystyle{ \sum_{1}^{51}f(B _{\sigma(i)}) - \sum_{52}^{100}f(B _{\sigma(i)}) \ge 2 + \sum_{1}^{51}f(B _{\sigma(i)})+\sum_{52}^{100}f(B _{\sigma(i)})}\)
\(\displaystyle{ -2 \ge 2 \cdot \sum_{52}^{100}f(B _{\sigma(i)})}\)
\(\displaystyle{ -1 \ge \sum_{52}^{100}f(B _{\sigma(i)})}\).
Zadanie sprowadza się teraz tylko do wykazania, że dla dowolnej permutacji ciągu \(\displaystyle{ (1, 1, ..., 1, -1, -1, ..., -1)}\) (51 jedynek i 49 (-1)-ynek) jesteśmy w stanie wskazać taki \(\displaystyle{ 49-}\)wyrazowy podciąg, którego suma wyrazów jest niewiększa od \(\displaystyle{ -1}\).
Wpiszmy w tym celu w okrąg \(\displaystyle{ 100-}\)kąt foremny i oznaczmy jego wierzchołki przez \(\displaystyle{ M _{1}, M _{2}, ... M _{100}}\) , oraz każdemu wierzchołkowi przypiszmy wartość \(\displaystyle{ 1}\) i \(\displaystyle{ -1}\), przy czym jedynek oczywiście jest dokładnie 51. Jest ich o dwie więcej od \(\displaystyle{ (-1)}\)-ynek, więc gdzieś na okręgu istnieją takie dwa punkty, że \(\displaystyle{ M_{k}}\) i \(\displaystyle{ M_{k+1}}\) mają przypisaną wartość 1. Nie zmniejszymy ogólności zakładając, że są to \(\displaystyle{ M _{1}}\) i \(\displaystyle{ M _{2}}\).
Rozpatrzmy teraz podciągi \(\displaystyle{ (M _{3}, M _{4}, ... , M _{51})}\) i \(\displaystyle{ (M _{52}, M _{53}, ... , M _{100})}\). Łącznie na okręgu tym występuje \(\displaystyle{ 49}\) wierzchołków równych \(\displaystyle{ -1}\), wszystkie muszą znaleźć się w tych dwóch podciągach długości \(\displaystyle{ 49}\), tak więc z zasady szufladkowej Dirichleta w którymś z nich znajdzie się \(\displaystyle{ 25}\) (lub może więcej) \(\displaystyle{ (-1)}\)-ynek, co jest równoznaczne, z tym, że suma wyrazów w jednym z tych podciągów jest mniejsza lub równa \(\displaystyle{ -1}\), co było do udowodnienia
