1. domácí úloha z MIN401, jaro 2022
Zadání. Nechť n > k > 2 jsou přirozená čísla. S n-úhelníkem A0AiA2 ... An_i, jehož vrcholy jsou obarveny žlutě nebo modře, hrajeme následující hru. Jedním tahem je povoleno změnit barvu u A; po sobě jdoucích vrcholů. Nechť na začátku hry je bod A0 žlutý a ostatní jsou modré. Pro které vrcholy Ad lze po konečném počtu tahů dosáhnout toho, že Ad je žlutý a ostatní vrcholy jsou modré? Svou odpověď zdůvodněte.
(1) Je-li (n, k) > 2 nebo (n,k) = 2 a k = 0 mod 4 lze obarvit vrchol Ad žlutě a ostatní modře, právě když d je násobkem čísla (n, k) modulo n.
(2) Je-li (n, k) = 1 nebo (n,k) = 2 a k = 2 mod 4 lze pro všechna d obarvit vrchol Ad žlutě a ostatní modře.
Důkaz. Prvně ukážeme, že výše popsaná obarvení lze uskutečnit.
1. V libovolném obarvení lze změnit barvu nejprve u vrcholů A0, Ai,..., Ak_i a potom u vrcholů Ai, A2, ■ ■ ■, Ak. Těmito dvěma tahy dojde ke změně barvy u vrcholů A0 a Ak. Tento postup lze opakovat pro počáteční bod Ak, potom A2k atd. Proto z původního obarvení Aq žlutý, ostatní modré dostaneme obarvení Ad žlutý, ostatní modré pro všechna d, která jsou násobky čísla k modulo n. Platí
2. Ukážeme, že je-li (n, k) = 2, lze změnit obarvení čtyř bodů za sebou. Nechť jsou na začátku všechny body modré. Změníme obarvení prvně u Aq,Ai, ... ,Ak_i a pak u A2, A3,..., Ak+1. Nyní jsou A0, Ai, Ak, Ak+1 žluté a ostatní modré. Protože (n, k) = 2, můžeme změnit barvy dvou bodů, jejich číselné značení se liší o sudé číslo. Toto aplikujeme na body A2 a Ak, A3 a Ak+Í. Tímto postupem dosáhneme toho, že budou žluté body A0, Ai, A2, A3 a ostatní modré. Změnili jsme barvu čtyř po sobě jdoucích bodů.
3. Nechť (n, k) = 2 a k = 4/ + 2. Uvažujme výchozí postavení vrchol A0 žlutý, ostatní modré. Po čtveřicích změníme obarvení A2, A3,..., Ak_2, Ak_\ na žluté. Těchto bodů je totiž k — 2 = 4/. Nyní stačí změnit obarvení k bodů A0, Ai, A2,..., Ak_\. Tím dosáhneme situace, kdy je vrchol A\ žlutý a ostatní modré. Je jasné, že tímto postupem můžeme obarvit každý vrchol Ad žlutě a ostatní modře.
Nyní ukážeme, že jiná obarvení uskutečnit nelze.
4. Nechť (n, k) > 2. Pro každé i, 0 < i < (n, k) — 1 definujeme podmnožinu vrcholů n-úhelníka takto:
Tyto množiny jsou aspoň tři a jejich disjunktní sjednocení je množina všech vrcholů. Množina M0 má na začátku právě jeden žlutý vrchol, a to A0. Ostatní množiny mají pouze modré body. Při každém tahu se v každé množině změní obarvení právě k/(n, k) bodů. Tedy pro 0 < d < (n, k) se není možné dostat do situace, že Md má právě jeden vrchol, a to Ad žlutý, zatímco další množiny Mi pro i ^ 0 mají všechny vrcholy modré.
5. Konečně pro (n,k) = 2 a k = 4/, máme pouze dvě množiny M0 a M\. Při každém tahu změníme obarvení sudého počtu 21 vrcholů v každé z nich. Tedy není možné dosáhnout stavu, aby M\ měla právě jeden žlutý vrchol. □
Výsledek.
{lk
Mi = {Ad, d = i   mod (n, k)}.