Zadanie
Keď Slavo v úlohe 8 našiel telku, skúsil ju spustiť. Na programe Jedinečné Obrazové Juchuchú (JOJ) premietajú novú reality šou, Zámená dám. Prebieha na šachovnici \(8 \times 8\). Na začiatku sú v prvom rade dámy v bielych KMS tričkách a v ôsmom rade sú dámy v modrých kms tričkách. Následne sa dámy hýbu v ťahoch (ako šachové dámy), v každom ťahu sa pohne práve jedna dáma, farby tričiek hýbajúcich sa dám sa striedajú. Aký je minimálny počet ťahov, po ktorom budú v prvom rade všetky dámy s modrými a v ôsmom rade všetky dámy s bielymi KMS tričkami?
Riešenie je 23. Každé správne riešenie má obsahovať konštrukciu na 23, no a dôkaz, že to nejde na menej.
Dôkaz že to nejde na menej: Ako prvé vyriešme iba dámy v rohoch. Je jasné, že na menej ako 4 ťahy nevieme tieto dámy umiestniť na druhú stranu – každá dáma sa predsa musí aspoň raz pohnúť. Taktiež tieto dámy nejdú vymeniť iba na 4 ťahy, pretože niektorá z nich sa musí pohnúť ako prvá, no ale v tejto fáze nemôže prísť až na druhú stranu šachovnice – jediné dve miesta, kam by mohla dôjsť, sú predsa zabrané. Na 5 ťahov to už ale ide – označme si políčka šachovnice ako na obrázku. Potom stačí pohnúť dámami takto: \(A1\mapsto B2\), \(A8\mapsto A1\), \(H1\mapsto A8\), \(H8\mapsto H1\), \(B2\mapsto H8\).
Teraz si popárujme zvyšné dámy – spravme dvojice dám tak, že jedna dvojica bude oproti sebe (dámy sú inej farby). Hlavná myšlienka je táto: tieto dve dámy potrebujú spolu určite aspoň tri ťahy aby sa dostali na cielenú druhú stranu. Prečo? Jedna z nich sa musí pohnúť ako prvá, no ale jediné miesto kam sa vie dostať na druhej strane jedným ťahom je práve to miesto, kde stojí tá druhá dáma. Inak povedané, jedna z nich sa musí uhnúť tej druhej, ale nemôže sa posunúť až na druhú stranu šachovnice. Teda aspoň jeden krok spravia navyše.
Keď si to spočítame, štyri rohové dámy spravia aspoň 5 ťahov, zvyšných 6 dvojíc každá spraví aspoň tri ťahy, spolu \(5+6\cdot 3=23\).
Konštrukcia na 23: rohové dámy posunieme ako sme opisovali pred tým. Štvoricu dám oproti sebe presunúť síce nejde, lebo by sa musela jedna farba pohnúť dva krát po sebe. Po chvíľke hrania sa zistíme, že to ale spraviť nasledovne:
\(B8\mapsto F4\), \(B1\mapsto B8\), \(C8\mapsto G4\), \(C1\mapsto C8\), \(D8\mapsto B6\), \(D1\mapsto D8\).
\(G4\mapsto D1\), \(G1\mapsto C5\), \(F4\mapsto C1\), \(F1\mapsto B5\), \(G8\mapsto G1\), \(E1\mapsto G3\),
\(E8\mapsto E1\), \(B5\mapsto E8\), \(B6\mapsto B1\), \(G3\mapsto G8\), \(F8\mapsto F1\), \(C5\mapsto F8\).
Pekne to graficky znázornil účastník Lukáš Gáborik na tomto odkaze.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.