Matematické Fórum

Ke druhému příkladu: uvažme neorientovaný graf o 10000 vrcholech, každý odpovídá nějaké čtveřici. Hrana z (a,b,c,d) vede vždy do (b,c,d,a+b+c+d mod 10).
Z Dirichletova principu plyne, že tento graf obsahuje cyklus. Snadno nahlédneme, že v něm není vrchol stupně vyššího nebo nižšího než 2 a jsme hotovi.

Poslední cifra součtu s=a+b+c+d je rovna s mod 10=a+b+c+d mod 10.

Graf s 10 000 vrcholy: pokud dokazujeme něco o iteracích funkce f, hodí se mít graf, jehož vrcholy jsou prvky definičního oboru f a  němž hrany vedou vždy z x do f(x).

Jde to ale popsat i bez grafu: když sledujeme postupně ty čtveřice, tak jednou dostaneme nějakou, kterou už jsme měli (Dirichletův princip). Pokud by to byla nějaká jiná než ta první, znamenalo by to, že existují dvě různé čtveřice, po kterých může následovat. To ale možné není, CBD. (Pokud mi někdo zadá čtveřici, najdu všecky čísla před ní.

Řekněme, že by nám stačilo vyškrtnout 42 čísel. Pak je nejmenší nevyškrtnuté (označme ho m) nejvýše rovno 44. V každé dvojici (a,am), kde
a=2,3,4,...,43,45 musí být jedno vyškrtnuté číslo, což  ale dává 43 vyškrtnutých čísel, spor.

Trik je v tom, že nevím, jaká čísla jsme vyškrtli. Pouze vím, že pokud jsme jich vyškrtli jen 42, pak nám tam zůstalo nějaké "malé". Označme ho m. Pokud by vyškrtnutá čísla byla 2,...,43, bylo by vskutku m=44. Pokud ale vyškrtneme třeba 2,3,5,7,11, 44,... pak bude m=4.
Takže nevím, co je vyškrtnuté, ale nějaké m není, přitom m<45.

Ani nadále nebudu hledat konkrétní čísla, která byla vyškrtnuta. Jenom vím, že pro každé a takové, že 1<a<46, a je různé od m,
je am<=45*44=1980, takže a i am jsou mezi 2 a 1982. Kdyby zůstaly a i am nevyškrtnuty, byla by v nevyškrtané množině trojice
(a,m,am), což nejde. Z každé dvojice (a,am) je tedy vyškrtnuto jedno číslo (nás nezajímá které). Tyto dvojice jsou disjunktní, proto počet vyškrtnutých čísel je alespoň takový, jako počet těchto dvojic. Protože a může procházet od 2 do 45 a nesmí nabýt hodnoty m, je takových dvojic 43, což je spor.

↑ bobik:
Ahoj, koukal jsem, že jsi mi psal meila.
Bohužel, na toto téma jsem krátký, jednak jsem jméno pana Dirichleta slyšel jen tady (ve škole nikoli, kupodivu?) a taky tu jsou jiní borci, kteří to určitě vyřeší :-)