Kavics Kupa 2024 5/h. feladat
(Feladat azonosítója: kk_2024_05fh )
Témakör: *Kombinatorika

A Minótaurusz visszatér. A labirintus a négyzetrácson egy 23 × 23 rácsnégyzetből álló négyzet, melynek oldalsó falai a négyzet kerületének összes rácsponttól rácspontig terjedő szakaszából áll. Ezen kı́vül a téglalapon belül szintén van néhány rácsponttól rácspontig terjedő szakasz méghozzá úgy, hogy a téglalap bármely egységnégyzetéből bármelyik másikba pontosan egyféleképpen lehet eljutni, leszámı́tva azokat az utakat, amelyek valamelyik egységnégyzeten többször is áthaladnak. A Minótaurusz most valamelyik egységnégyzetbe áll. Egy lépésben átléphet egy szomszédos négyzetbe, ha a két négyzet között nincsen fal. (Két négyzet szomszédos, ha van közös oldaluk.) Legalább hány lépésre van szüksége, hogy minden egységnégyzetbe eljusson egyszer, függetlenül a labirintus alakjától és attól, hogy honnan indul? (A Minótaurusz minden esetben ismeri, hogy hogyan néz ki a labirintusa.)



 

Végeredmény: $ 1034 $