\documentclass[12pt,a4paper]{amsart}
\usepackage[czech]{babel}
\usepackage[utf8]{inputenc}

\textwidth=154mm
\hoffset=-14mm
\voffset=-20mm
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{float}

\usepackage{times}


\newenvironment{zad}{\smallskip\par\noindent {\bf Zadání}.$\,$}{} 
\newenvironment{res}{\smallskip\par\noindent {\bf Důkaz}.$\,$}{\hbox{}\hfill $\Box$}
\newenvironment{vys}{\smallskip\par\noindent {\bf Výsledek}.$\,$}{}
\newenvironment{navod}{\smallskip\par\noindent {\it Návod}.$\,$}{\hbox{}\hfill $\Box$}
\newenvironment{otazka}{\smallskip\par\noindent {\it Otázka}.$\,$\it}{}
\newenvironment{poznamka}{\smallskip\par\noindent {\it Poznámka}.$\,$\it}{}

\def\brem{\begin{poznamka}\rm}
\def\erem{\end{poznamka}}

\def\bot{\begin{otazka}}
\def\eot{\end{otazka}}

\def\ind #1{{\it #1}{\index{#1}}}

\def\R{\mathbb R}
\def \C{\mathbb C}
\def\N{\mathbb N}
\def\vect #1{{\overrightarrow{#1}}}
\def\d{\operatorname{dist}}
\begin{document}
 
\begin{center}
{\bf  1. domácí úloha z MIN401, jaro 2022}
\end{center}
\smallskip


\begin{zad}
Nechť $n\ge k\ge 2$ jsou přirozená čísla. S $n$-úhelníkem $A_0A_1A_2\dots A_{n-1}$, jehož vrcholy jsou obarveny žlutě nebo modře, hrajeme následující hru. Jedním tahem je povoleno změnit barvu u $k$ po sobě jdoucích vrcholů. Nechť na začátku hry je bod $A_0$ žlutý a ostatní jsou modré. Pro které vrcholy $A_d$ lze po konečném počtu tahů dosáhnout toho, že $A_d$ je žlutý a ostatní vrcholy jsou modré?
Svou odpověď zdůvodněte. 
\end{zad}

\smallskip

\begin{vys}
\begin{enumerate}
\item Je-li $(n,k)>2$ nebo $(n,k)=2$ a $k\equiv 0 \mod 4$ lze obarvit vrchol $A_d$ žlutě a ostatní modře, právě když $d $ je násobkem 
čísla $(n,k)$ modulo $n$.
\item Je-li $(n,k)=1$ nebo  $(n,k)=2$ a $k\equiv 2 \mod 4$ lze pro všechna $d$ obarvit vrchol $A_d$ žlutě a ostatní modře.
\end{enumerate}
\end{vys}

 \smallskip

\begin{res}
Prvně ukážeme, že  výše popsaná obarvení lze uskutečnit. 

\parindent 0pt {\bf 1.} V libovolném obarvení lze změnit barvu nejprve u vrcholů $A_0,A_1,\dots, A_{k-1} $ a potom u~vrcholů 
$A_1,A_2,\dots, A_{k}$. Těmito dvěma tahy dojde ke změně barvy u vrcholů $A_0$ a $A_k$. Tento postup lze opakovat pro počáteční bod $A_k$, potom $A_{2k}$ atd. Proto z původního obarvení $A_0$ žlutý, ostatní modré dostaneme obarvení  $A_d$ žlutý, ostatní modré
pro všechna $d$, která jsou násobky čísla $k$ modulo $n$. Platí
$$\left\{lk \mod n; \ l\in \N\cup\{0\}\right\}=\left\{j(n,k)\mod n; j=0,1,2,\dots, \frac{n}{(n,k)}-1\right\}.$$

\parindent 0pt {\bf 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 $A_0, A_1,\dots,A_{k-1}$ a pak u $A_2, A_3,\dots,A_{k+1}$. Nyní jsou $A_0,A_1,A_k,A_{k+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
$A_{2}$ a $A_{k}$, $A_{3}$ a $A_{k+1}$. Tímto postupem dosáhneme toho, že budou žluté body $A_0,A_1,A_2,A_3$ a ostatní  modré.
Změnili jsme barvu čtyř po sobě jdoucích bodů.

\parindent 0pt {\bf 3.}  Nechť $(n,k)=2$ a $k=4l+2$. Uvažujme výchozí postavení vrchol $A_0$ žlutý, ostatní modré. Po čtveřicích změníme obarvení $A_2,A_3,\dots, A_{k-2},A_{k-1}$ na žluté. Těchto bodů je totiž  $k-2=4l$. Nyní stačí změnit obarvení $k$ bodů $A_0,A_1,A_2,\dots, A_{k-1}$. Tím dosáhneme situace, kdy je vrchol $A_1$ žlutý a ostatní modré. Je jasné, že tímto postupem můžeme obarvit každý vrchol $A_d$ žlutě a ostatní modře.

\bigskip

Nyní ukážeme, že jiná obarvení uskutečnit nelze.

 \parindent 0pt {\bf 4.}  Nechť $(n,k)>2$. Pro každé $i$,  $0\le i\le (n,k)-1$ definujeme podmnožinu vrcholů $n$-úhelníka takto:
 $$M_i=\{A_d, d\equiv i \mod(n,k)\}.$$
 Tyto množiny jsou aspoň tři a jejich disjunktní sjednocení je množina všech vrcholů. Množina $M_0$ má na začátku právě jeden žlutý vrchol, a to $A_0$. 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 $M_d$ má právě jeden vrchol, a to $A_d$ žlutý, zatímco další množiny $M_i$ pro $i\ne 0$ mají všechny vrcholy modré.   
 
  \parindent 0pt {\bf 5.} Konečně pro $(n,k)=2$ a $k=4l$, máme pouze dvě množiny $M_0$ a $M_1$. Při každém tahu změníme obarvení
  sudého počtu $2l$ vrcholů v každé z nich. Tedy není možné dosáhnout stavu, aby $M_1$ měla právě jeden žlutý vrchol.   
\end{res}
\end{document}

