Zadání XXXII. ročníku

1. V tomto příkladu můžeme použít například zobrazení \(f\), které každé číslo \(n\in\N\) pošle na množinu všech jeho přirozených dělitelů, tzn. \(f(n)=\{d\in\N ~|~ d|n\}\subset P(\N)\). Největší prvek takovéto množiny bude zřejmě \(n\) samotné, což implikuje injektivitu. Fakt, že je zobrazení \(f\) izotonní, pak plyne z tranzitivity dělitelnosti, neboli pokud \(y|z\) a \(x|y\), pak i \(x|z\). Dělitelé čísla \(y\) jsou tedy také dělitelé čísla \(z\) a dostáváme \(f(y)\subseteq f(z)\).

2. Tady můžeme použít například uspořádání \((\N,\geq)\), tzn. jednička bude v tomto uspořádání největší a řetězec bude pokračovat dolů. Chceme tedy dokázat, že neexistuje injektivní izotonní zobrazení \((\mathbb{N}, |) \to (\N,\geq)\). Nejmenším prvkem \((\mathbb{N}, |)\) je \(1\) a bez ohledu na to, kam ji pošleme, pro zachováni izotonie by se všechny ostatní prvky musely zobrazit do \(\{f(1), \dots, 3, 2, 1\}\). Chceme tedy zobrazit nekonečnou množinu na množinu konečnou, což je ve sporu s injektivitou.

Některá řešení byla spíš jen rozepsaná, než špatně. Řekla bych tedy, že jste si s touto úlohou všichni skvěle poradili!

Je-li uspořádaná množina prázdná, pak má právě jednu podmnožinu, prázdnou, a ta nemá supremum. Dále tedy předpokládejme, že uspořádaná množina je neprázdná, označme ji \(U\). Tvrzení dokážeme sporem. Předpokládejme, že existuje neprázdná podmnožina \(A\), jejíž supremum neexistuje. Podmnožinou uspořádané množiny \(U\) je dozajista i prázdná množina. Z předpokladu je různá od \(A\) a má supremum. Množina horních závor prázdné množiny je celá množina \(U\), supremum je nejmenší horní závora, z čehož tedy získáváme, že množina \(U\) má nejmenší prvek, označme si ho \(x\). Následují dvě možnosti, množina \(A\) buď prvek \(x\) obsahuje, nebo ne.

1. \(x \in A\). Pokud by \(x\) byl jediný prvek množiny \(A\), pak by také byl jejím supremem, my však předpokládáme, že množina \(A\) supremum nemá. Musí obsahovat tedy minimálně další prvek. Uvažme množinu \(\tilde{A} = A \\ {x}\). Množina horních závor \(\tilde{A}\) se odebráním nejmenšího prvku od \(A\) nemohla změnit. Protože však víme, že neexistuje nejmenší horní závora \(A\), pak neexistuje ani nejmenší horní závora \(\tilde{A}\), získáváme tedy další podmnožinu \(U\), jejíž supremum neexistuje -> SPOR!

2. \(x \notin A\). Nyní vytvořme množinu \(\hat{A} = A \cup {x}\). Kdyby množina horních závor \(A\) obsahovala prvek \(x\), pak by i měla nejmenší prvek a tedy supremum. Určitě tedy \(x\) nebylo v množině horních závor. Přidáme-li prvek \(x\) k množině \(A\) množina horních závor \(\hat{A}\) bude totožná s \(A\), nebude existovat nejmenší prvek a ani \(\hat{A}\) nebude mít supremum. Což je opět? SPOR!

Musí tedy tato podmnožina být prázdná.

Tentokrát jsem nezvykle udělovala poměrně nízké bodové ohodnocení. Nejčastejší problémem bylo uvědomit si, jak vypadá supremum prázdné množiny. Je to nejmenší prvek celé uspořádané množiny! Práce s množinami je dost těžká, kvůli pojmům, které vypadají zřejmě (uspořádání, nejmenší prvek, maximální prvek), ale v definici můžou dělat spoustu podivností.

Připusťme, že \(M\) má vlastnost ze zadání a zároveň je nekonečná. Sestrojíme posloupnost \((x_i)_{i\in \mathbf{N}}\) následovně: \(x_1=min(M)\), \(x_2=min(M \setminus\{x_1\})\), …, \(x_n=min(M\setminus\{x_1, x_2, ..., x_{n-1}\})\). Tato posloupnost je rostoucí, protože nejmenší prvek množiny se odebráním předchozího nejmenšího prvku ostře zvětší.

Jelikož \(M\) je nekonečná, můžeme v tomto procesu pokračovat libovolně dlouho, a posloupnost bude tedy také nekonečná. Protože každé \(x_i\) je prvek \(M\), tvoří prvky posloupnosti podmnožinu \(M\), a ta tedy musí mít největší prvek. To je ovšem spor s tím, že je nekonečná a rostoucí. Žádný prvek \(x_m\) nemůže být největším prvkem, protože \(x_{m+1}\) je větší.

Plno z vás si s úlohou poradilo skvěle! Někteří jste se moc fixovali na to, že \(M\) je množina reálných čísel, všimněte si, že to vůbec nebylo zásadní!

Jedno z možných řešení, převzato od Pavla Hyánka:

1. Definujme zobrazení \(i,j\) předpisem: \[\forall n \in \mathbb{N}, i(n) := n,\] \[\forall q \in \mathbb{Q}, j(q) := \begin{cases} 1, & \text{když } q < 1 \\ \lceil q \rceil, & \text{jinak} \end{cases}\]

Obě zobrazení jsou zjevně izotonní a zároveň pro každé \(n \in \mathbb{N}\) platí \(i(n) = j(n) = n\), tedy je jejich složení identita.

2. Pro spor předpokládejme, že taková dvojice zobrazení existuje.

Zaměřme se na zobrazení \(j\), které je z \(\mathbb{R}\) do \(\mathbb{Q}\), je izotonní a musí být surjektivní, aby složení \(i\) a \(j\) mohla být identita.

Uvažme libovolné posloupnosti \(A = (a_n)_{n=0}^\infty, B = (b_n)_{n=0}^\infty\) racionálních čísel, kde \(A\) je ostře rostoucí, \(B\) je ostře klesající a obě mají stejnou iracionální limitu \(L\).

Ze surjektivnosti \(j\) musí existovat posloupnosti reálných čísel \(C = (c_n)_{n=0}^\infty, D = (d_n)_{n=0}^\infty\) takové, že pro všechna přirozená \(n\) platí \(j(c_n) = a_n, j(d_n) = b_n\).

Máme že každý prvek \(A\) je menší než \(L\) je menší než každý prvek \(B\), a proto z izotónnosti \(j\) je každý prvek \(C\) menší nebo roven každému prvku \(D\). Proto nutně existuje nějaké \(m\), které je větší nebo rovno všem prvkům \(C\) a menší nebo rovno všem prvkům \(D\).

Co ale může být \(j(m)\)? Z izotónnosti \(j\) je to větší nebo rovno všem prvkům \(A\) a menší nebo rovno všem prvkům \(B\). Jediné reálné číslo, co toto splňuje je, z toho jak jsme zvolili \(A\) a \(B\) právě \(L\). To není racionální, tudíž \(j(m)\) není racionální a dostáváme spor s tím, že \(j\) je \(\mathbb{R} \to \mathbb{Q}\), jak jsme chtěli, tedy takové řešení neexistuje.

Pouze 3 z vás se do této poměrně náročné úlohy pustili. Ale všichni tři vyřešili úlohu zcela správně. Super!

Nejprve sestrojíme kolmice k tečnám \(t_1\) a \(t_3\), které procházejí středy kružnic. Vzniknou tak poloměry \(S_1C\), \(S_1B\), \(S_2A\), \(S_2B\), přičemž platí \(S_1C=S_1B=r_1,\qquad S_2A=S_2B=r_2\).

Označme velikosti úhlů \(|CAS_1|=\beta, |DAS_2|=\alpha\). Podívejme se nyní na pravoúhlé trojúhelníky \(\triangle S_1CA\) a \(\triangle S_1BA\). Oba mají společnou přeponu \(S_1A\) a zároveň platí \(S_1C=S_1B=r_1\). Jedná se tedy o shodné trojúhelníky podle věty \(Ssu\), a proto \(|BAS_1|=|CAS_1|=\beta\). Analogicky dostáváme pro pravoúhlé trojúhelníky \(\triangle S_2DA\) a \(\triangle S_2BA\) jejich shodnost, ze které plyne \(|BAS_2|=|DAS_2|=\alpha\).

Dostáváme tedy \(2\alpha+2\beta=180^\circ\), a tudíž \(\boxed{\alpha+\beta=90^\circ}\).

Stejnou úvahu můžeme provést také pro spodní část náčrtku. Analogicky získáme \(|S_1ES_2|=90^\circ\).

Čtyřúhelník \(AS_1ES_2\) má tedy dvojici protilehlých úhlů \(|S_1AS_2|=90^\circ\) a \(|S_1ES_2|=90^\circ\), jejichž součet je \(|S_1AS_2|+|S_1ES_2|=180^\circ\).

Podle věty o obvodovém čtyřúhelníku je tedy čtyřúhelník \(AS_1ES_2\) tětivový, tudíž mu lze opsat kružnice.

Dobrá práce, s úlohou jste si naprostá většina poradila perfektně.

Začněme nejprve menším čtvercem. Zajímat nás bude zejména úhel, který svírají dva jeho dotýkající se body se středem kružnice - tedy úhel \(ASB\).

Strana \(|SB|=R\), \(|VB| = R\sin10^\circ\), proto úhel \[\sin VSB = \frac{|VB|}{|SB|} = \frac{ R\sin10^\circ}{R} = \sin10^\circ,\] tedy \(|\angle VSB| = \arcsin(\sin 10^\circ) = 10^\circ\). Dva vrcholy menšího čtverce tedy svírají se středem kružnice úhel \(20^\circ\). Rozdělíme si proto čtverec na \(360/20 = 18\) dílů, tam se budou dotýkat vrcholy čtverce.

Analogicky spočítejme úhel \(ASB\) pro větší čtverec.

\[\sin VSB = \frac{|VB|}{|SB|} = \frac{R \sin 30^\circ}{R} = \sin 30^\circ ,\] tedy \(|\angle VSB| = \arcsin(\sin 30^\circ) = 30^\circ\). Dva vrcholy většího čtverce proto svírají se středem kružnice úhel \(60^\circ\). Vrcholy čtverce se budou dotýkat vepsanému šestiúhelníku.

Popišme si pár prvních bodů, kam se zobrazí obarvený vrchol.

Obarvený vrchol většího čtverce bude střídat tři zvýrazněné vrcholy kam postupně bude vepisovat čísla se stejný zbytkem \(\mod 3\). Obarvený vrchol menšího čtverce zase bude postupně střídat 9 obarvených vrcholů, kam bude vepisovat čísla se stejným zbytkem \(\mod 9\). Tzn.

v bodě označeným teď 1,1 budou pro malý čtverec čísla kongruentní s 1 mod 9, tedy \(1, 10, 19, 28, \dots\), pro velký čtverec zase čísla \(1, 4, 10, \dots\), budou se tu shodovat ve všech indexech, který tu zanechá malý čtverec,

v bodě označeným 3,7 budou pro malý čtverec čísla kongruentní s 7 mod 9, tedy \(7, 16, 25, 34, \dots\), pro velký čtverec zase čísla \(3, 6, 9, \dots\), nebudou se tu shodovat nikdy,

v bodě označeným 2,4 budou pro malý čtverec čísla kongruentní s 4 mod 9, tedy \(4, 13, 21, 30, \dots\), pro velký čtverec zase čísla \(2, 5, 8, \dots\), nebudou se tu shodovat nikdy.

Potkat se stejným číslem se proto mohly pouze v počátečním vrcholu a to s indexy 1, 10, a napotřetí s indexem 19.

Vzhledem však k nejasnosti zadání (rychlosti čtverce) je samozřejmě možné počítat i s variantou, že na indexu nezáleží, jde jen o to, který bod bude jako třetí obarven oběma barvami. V tomto případě by pak řešením byl bod označený 3,7.

Všichni jste se s úlohou skvěle poprali. Nejčastější chyba bylo zapomenutí posunutí indexů o výchozí pozici prvního potkání. Navíc kvůli nejednoznačnosti zadání se uznávala dvě různá řešení jako správná.

Označme vzdálenost mezi Finťou a Ňoumou jako \(d\). Chceme, aby se potkali, tedy aby nastalo \(d = 0\). Všimněme si, že nezáleží na tom, kdo se pohybuje – důležitá je pouze jejich vzájemná vzdálenost, která se v \(i\)-tém kroku změní o \(\pm 2^{i-1}\).

Sudá vzdálenost

V prvním kroku se vzdálenost změní o \(1\), tedy ze sudé se stane lichá. V každém dalším kroku se mění o \(2, 4, 8, \ldots\), tedy vždy o sudé číslo. Součet nebo rozdíl lichého a sudého čísla je vždy lichý, takže vzdálenost zůstane lichá navždy. Protože \(0\) je sudé číslo, nemohou se Finťa s Ňoumou nikdy potkat.

Lichá vzdálenost

Předpokládejme, že provádíme celkem \(n\) kroků o \(1, 2, 4, \ldots, 2^{n-1}\) schodech. Každý krok přičte nebo odečte příslušný počet schodů od \(d\). Označme \(P\) součet kroků, které provedeme směrem k sobě, a \(Q\) součet kroků směrem od sebe. Platí: \[P + Q = 1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1.\] Jedná se o n-tý součet geometrické řady, kde \(a=1\) a \(q=2\). Počáteční vzdálenost \(d\) lze vyjádřit jako: \[d = P - Q = P - (2^n - 1 - P) = 2P - (2^n - 1).\]

Ptáme se tedy, jakých hodnot může nabývat \(P\) (tj \(d\)). \(P\) je součet libovolné podmnožiny čísel \(\{1, 2, 4, \ldots, 2^{n-1}\}\). Protože tato čísla jsou právě mocniny dvojky, každé celé číslo od \(0\) do \(2^n - 1\) lze jednoznačně zapsat jako součet některých z nich (stejně jako v dvojkové soustavě). Tedy \(P\) může nabýt libovolné hodnoty od \(0\) do \(2^n-1\) a \(d = 2P-(2^n-1)\) může nabývat hodnot \[-(2^n-1),\ \ldots,\ -3,\ -1,\ 1,\ 3, \ \ldots,\ 2^n-1,\] tedy všech lichých čísel v intervalu \([-(2^n-1),(2^n-1)]\). Pro libovolně velké \(n\) pokryjeme libovolně velká lichá čísla.

Finťa s Ňoumou se mohou v konečném počtu kroků potkat právě tehdy, když je jejich počáteční vzdálenost lichá.

Úloha se vám celkově povedla a potěšila mě originalita vašich přístupů — objevila se indukce, rekurze, binární zápis i stromové argumenty. Většina z vás správně odhalila, kdy setkání není možné, náročnější pak bylo tuto nemožnost dokázat a zároveň ukázat, že ve všech ostatních případech setkání skutečně nastat může.

Máme dokázat ekvivalenci, rozdělíme si ji tedy na dvě implikace.

Nejprve předpokládejme, že \(6\) dělí každý z koeficientů \(f\). Můžeme ji tedy vytknout a dostáváme \(f=6\cdot g\) pro nějaký polynom \(g\), který má též celočíselné koeficienty. Zvolme \(n=2\). Potom \(f^n=f^2=(6g)^2=36g^2\). Tento polynom je dělitelný \(36\), tedy zejména \(12\). Opravdu proto existuje \(n\) s takovou vlastností, třeba námi zvolená dvojka.

Naopak nechť existuje \(n\) takové, že \(12\) dělí \(f^n\), tedy \(f^n=12h\) pro nějaký polynom \(h\) s celočíselnými koeficienty. Ukážeme, že potom musí \(6\) dělit každý z koeficientů \(f\).

Nejprve ukažme, že \(6\) musí dělit absolutní člen polynomu \(f\), označme ho \(a_0\). Absolutní člen \(b_0\) polynomu \(f^n\) se bude rovnat \({a_0}^n\) a my víme, že je dělitelný \(12\). Proto prvočísla \(2\) i \(3\) musejí dělit \(a_0\), tedy absolutní člen polynomu \(f\) je dělitelný 6.

Dále si uvědomme, jak budou vypadat ostatní koeficiety \(b_i\) polynomu \(f^n\). Číslo \(b_i\) je koeficientem u mocniny \(x^i\). To vznikne jako součet všech možností, jak vynásobit \(n\) koeficientů polynomu \(f\), aby se součet jejich exponentů rovnal \(i\):

\[b_i=\sum_{j_1+...+j_n=i} a_{j_1}\cdot ... \cdot a_{j_n}.\]

Už jsme ukázali, že \(a_0\) je dělitelné \(6\), dále budeme postupovat induktivně k vyšším mocninám. Předpokládejme tedy, že \(a_i\) jsou dělitelné \(6\) pro všechna nezáporná celá \(i\leq m-1\), a dokažme, že i \(a_m\) je potom dělitelné \(6\).

Využijeme sumu výše pro \(i=mn\). Je-li součet indexů \(j_1+...+j_n=mn\), mohou nastat dvě možnosti: buď jedno z \(j_k\) je menší než \(m\), a tedy z indukčního předpokladu \(a_{j_k}\) je dělitelné \(6\), nebo jsou všechna \(j_k=m\). Koeficient \(b_{mn}\), o němž víme, že je dělitelný \(12\), je tedy součet několika součinů dělitelných \(6\) a součinu \({a_m}^n\). Odtud vidíme, že \({a_m}^n\) musí být dělitelné \(6\), což stejně jako u absolutního členu implikuje, že \(a_m\) je dělitelné \(6\), což jsme měli ukázat.

Dohromady dostáváme, že všechny koeficienty polynomu \(f\) jsou dělitelné \(6\), takže i druhá implikace platí.

Do úlohy se pustili tři odvážní a sešla se tři různá řešení, z nichž jedno bylo stejné jako vzorové. Všichni jste odvedli dobrou práci!