Zasada szufladkowa Dirichleta 3 zadania

[ronek22]

Czołem,
Nie wiem jak formalnie zapisywać udowodnienia do metody szufladkowej, poza tym czasami nie mam pojęcia jak się zabrać za zadanie.

1. Udowodnij, że wśród dowolnych \(\displaystyle{ n+1}\) liczb całkowitych będzie istniała para liczb różniących się o wielokrotność \(\displaystyle{ n}\)

Mamy dane liczby \(\displaystyle{ a_0, a_1, ..., a_n}\)
Tworzymy szufladki, które odzwierciedlają możliwe reszty z dzielenia przez \(\displaystyle{ n}\),
Otrzymujemy szufladki: \(\displaystyle{ 0, 1, ..., n-1}\)
Rozważamy każdą parę: \(\displaystyle{ a_i-a_0}\), będzie \(\displaystyle{ n}\) takich par
Więc mamy \(\displaystyle{ n}\) par i \(\displaystyle{ n}\) szuflad, więc różnica jednej pary musi dać \(\displaystyle{ n}\).

Jednak, nie jestem pewny czy dobrze zrozumiałem zadanie, bierzemy dowolne \(\displaystyle{ n+1}\) liczb całkowitych,
to czy możemy sobie wziąć np. \(\displaystyle{ 1,4,7,9}\), czy muszą być to kolejne liczby czyli \(\displaystyle{ 1,2,3,4,5}\). W pierwszym przypadku nie do końca to się zgadza.

2. Uzasadnij, że wśród dowolnych pięciu punktów należących do wnętrza kwadratu o boku 2 zawsze są dwa punkty odległe o nie więcej niż \(\displaystyle{ \sqrt{2}}\)

3. Udowodnij, że wśród dowolnych \(\displaystyle{ n + 1}\) liczb całkowitych ze zbioru \(\displaystyle{ {1,2,...,2n}}\) istnieje taka, która jest wielokrotnością innej.

[Jan Kraszewski]

Ad 2 Podziel ten kwadrat na cztery kwadraty o boku \(\displaystyle{ 1}\).

JK

[a4karo]

ad 1. Początek ok: teraz pomyśl ile masz liczb i ile masz szufladek. Co to oznacza (tu się uruchamia ZSD). Co możesz powiedzieć o różnicy dwóch liczb, które sa w tej samej szufladce?

Liczby oczywiście mogą byc dowolne, mogą sie też powtarzac.

[arek1357]

W trzecim zauważ, że każdą liczbę od jeden do \(\displaystyle{ 2n}\) możesz zapisać w postaci:

\(\displaystyle{ 2^k(2m+1), 0 \le m \le n-1}\),

i każdą z tych liczb wkładamy do szuflady o numerze \(\displaystyle{ m}\),

czyli dwie liczby znajdą się w jednej szufladzie:

znaczy że dla dwóch liczb \(\displaystyle{ 2m+1}\) będzie takie samo, czyli w praktyce mamy dwie liczby:


\(\displaystyle{ 2^ir}\), oraz\(\displaystyle{ 2^jr}\)

a one są przez siebie podzielne!