Alberts ir pierakstījis virkni \(a_1, a_2, \ldots, a_{2026}\), kurā katrs no skaitļiem \(1, 2, \ldots, 2026\) parādās tieši vienu reizi. Kristīne vēlas noteikt šo virkni, veicot vairākus gājienus, pēc kuriem Alberts viņai sniedz informāciju. Vienā gājienā Kristīne uz lapas uzraksta skaitļus no \(1\) līdz \(2026\) un dažus no tiem savieno ar līnijām tā, ka katrs skaitlis ir savienots ar ne vairāk kā vienu citu skaitli. Pēc tam viņa iedod šo lapu Albertam. Tad Alberts uz citas lapas uzraksta skaitļus no \(1\) līdz \(2026\) un katram skaitļu pārim \(i\) un \(j\), kurus Kristīne savienoja ar līniju, viņš savieno ar līniju skaitļus \(a_i\) un \(a_j\). Beigās viņš iedod šo lapu Kristīnei. Kāds ir mazākais gājienu skaits, kas nepieciešams, lai Kristīne varētu noteikt Alberta sākotnējo virkni?
Atbilde ir \(n=2\).
Pēc viena gājiena Kristīne nekādi nevar ar pārliecību noteikt Alberta virkni. Proti, ja uz Alberta lapas ir savienoti skaitļi \(a_i\) un \(a_j\), tad Kristīne nevar zināt, kurš no tiem ir \(a_i\) un kurš ir \(a_j\).
Pierādīsim, ka Kristīne vienmēr var ar pārliecību noteikt Alberta virkni pēc diviem gājieniem, tāpēc minimālais nepieciešamais gājienu skaits ir tieši \(2\). Pirmajā gājienā Kristīne savieno pārus \(3\)-\(4\), \(5\)-\(6\), ..., \(2025\)-\(2026\). Otrajā gājienā Kristīne savieno pārus \(2\)-\(3\), \(4\)-\(5\), ..., \(2024\)-\(2025\).
Pamatosim, ka pēc šiem diviem gājieniem Kristīne zina skaitļus \(a_1, a_2\) un \(a_{2026}\). Patiešām, skaitlis \(a_1\) ir vienīgais, kas nebija savienots ar nevienu citu skaitli ne pirmajā, ne otrajā gājienā. Skaitlis \(a_2\) ir vienīgais, kas tika savienots ar kādu citu skaitli tikai otrajā gājienā, bet skaitlis \(a_{2026}\) ir vienīgais, kas tika savienots ar kādu citu skaitli tikai pirmajā gājienā.
Tālāk Kristīne zina arī \(a_3\), jo pēc otrā gājiena šis skaitlis ir savienots ar \(a_2\). Savukārt skaitlis \(a_4\) pirmajā gājienā bija savienots ar \(a_3\), tāpēc Kristīne zina arī \(a_4\). Turpinot šādi spriest, Kristīne nosaka visus pārējos skaitļus no \(a_1\) līdz \(a_n\); \((n+1)\)-ajā solī viņa nosaka \(a_{n+1}\), jo šis skaitlis tieši vienā no apmaiņām bija savienots ar \(a_n\), un, atkarībā no skaitļa \(n\) paritātes, viņa zina arī, kurā no apmaiņām tas notika.