LV.AMO.2007.8.5 lv
Kvadrāts sastāv no \(9 \times 9\) rūtiņām, kas izkrāsotas šaha galdiņa kārtībā; stūra rūtiņas ir melnas. Figūriņu novieto melnajā rūtiņā. Ja figūriņa ir kādā rūtiņā \(A\), tad ar vienu gājienu to var pārvietot uz jebkuru rūtiņu, kam ar \(A\) ir kopīgs stūris, bet ne kopīga mala. Kāds ir mazākais iespējamais gājienu skaits, ar kuru var apstaigāt visas melnās rūtiņas, dažās no tām varbūt ieejot vairākas reizes? Sākuma rūtiņa automātiski skaitās apstaigāta. Ar pēdējo gājienu nav obligāti jāatgriežas sākuma rūtiņā. Spēlētājs var izvēlēties figūriņas sākuma pozīciju.
Atrisinājums
Atbilde: \(48\) gājieni.
Risinājums. Tas, ka ar \(48\) gājieniem pietiek, redzams 12.zīm.
Pierādīsim, ka ar mazāk gājieniem nepietiek. Kopā jāieiet \(40\) melnās rūtiņās (pavisam to ir \(41\)). Melnajās rūtiņās, kas 13.zīm. attēlotas ar krustiņu, var ieiet tikai no tām rūtiņām, kas apzīmētas ar aplīšiem; krustiņu ir \(25\), aplīšu - \(16\). Šķirojam divas iespējas:
(A) maršruts sākas "krustiņā". Tad jāieiet \(24\) krustiņos. Tāpēc vismaz \(24-16=8\) reizes jāieiet aplītī, kurā jau ir būts (lai būtu, no kurienes ieiet visos krustiņos). Tāpēc pavisam jāveic vismaz \(40+8=48\) gājieni.
(B) maršruts sākas aplītī. Tad jāieiet \(25\) krustiņos. Vienā no tiem ieiet no sākuma pozīcijas; lai realizētu atlikušās \(24\) ieiešanas, atkal vajag vismaz \(24-16=8\) "liekus" gājienus, un kopējais gājienu skaits ir vismaz \(40+8=48\).