Atrisinājums

Apzīmēsim krāsas ar \(0;\ 1;\ 2\). Pierādīsim vispirms divas lemmas.

Lemma 1. Ja trīs no četrām sekojošām virsotnēm ir vienā krāsā, tad var panākt, lai tās visas būtu ceturtās virsotnes krāsā, nemainot citu virsotņu krāsojumu.

Pietiek apskatīt divus gadījumus:

\(1110 \rightarrow 1122 \rightarrow 1002 \rightarrow 2202 \rightarrow 2112 \rightarrow 0012 \rightarrow 0000\);

\(1011 \rightarrow 1221 \rightarrow 0021 \rightarrow 0000\)

Lemma 2. Jebkuras četras sekojošas virsotnes var nokrāsot vienā krāsā.

Sadalām virsotnes divos blakus virsotņu pāros un panākam, lai katrā pārī krāsas būtu vienādas. Ja tās visas vienādas, viss OK. Pretējā gadījumā rīkojamies pēc shēmas \(1122 \rightarrow 1002 \rightarrow 2202 \rightarrow 2112 \rightarrow 0012 \rightarrow 0000\).

Saskaņā ar 2.lemmu var panākt, lai \(A_{1}A_{2}A_{3}A_{4}\) būtu vienā krāsā, pieņemsim \(0\), un arī \(A_{5}A_{6}A_{7}A_{8}\) būtu vienā krāsā. Ja arī \(A_{5}A_{6}A_{7}A_{8}\) ir krāsā \(0\), nogaidām. Ja nē, apskatām \(A_{4}A_{5}~A_{6}A_{7}\). Pēc 1.lemmas varam panākt, ka \(A_{4}A_{5}A_{6}A_{7}\) ir krāsā \(0\). Līdzīgi pievienojot pa \(3\) virsotnēm, iegūstam, ka \(A_{1}A_{2} \ldots A_{997}\) ir krāsā \(0\). Apskatām \(A_{998}A_{999}A_{1000}A_{1}\). Pārkrāsojam tās vienā krāsā (2. lemma). Ja tā ir krāsa \(0\), viss kārtībā. Pieņemsim, ka tā ir krāsa \(1\). Apskatām \(A_{997}A_{998}A_{999}A_{1000}\) un saskaņā ar 1. lemmu pārkrāsojam tās krāsā \(0\). Tagad \(A_{1}\) ir krāsā \(1\), citas virsotnes krāsā \(0\). Tagad pakāpeniski pārkrāsojam krāsā \(1\) virsotnes \(A_{2}A_{3}A_{4};\ A_{5}A_{6}A_{7};\ \ldots;\ A_{998}A_{999}A_{1000}\), lietojot 1.lemmu.

Ievērosim, ka pieļautie gājieni \(01 \rightarrow 22;\ 10 \rightarrow 22;\ 02 \rightarrow 11;\ 20 \rightarrow 11;\ 12 \rightarrow 00;\ 21 \rightarrow 00\) saglabā visu numuru summas atlikumu, dalot ar \(3\). Bet šis atlikums vienāds ar galā iegūtās krāsas numuru, jo \(1000x \equiv(\bmod 3)\). No šejienes seko otrais apgalvojums.