Matematické Fórum

Nejde to. Hezký důkaz nemám, na to je asi potřeba znalost teorie grafů nebo dobrý nápad, ani jedno nemám. Takže ošklivý důkaz:

Zavedu si souřadnice, vodorovně doprava x, svisle dolů y, takže (x,y)=(1,1) bude výchozí pozice, (4,4) pozice, do které se musíme dostat přes všechny klíče, abychom mohli k princezně na (6,4) přes dveře na (5,4).

Bez újmy na obecnosti (díky symetrii) předpokládejme, že první krok je doprava na (2,1). Zajímavé jsou body (2,2) a (3,3), to jsou jediné body, přes které mohu procházet z "horního pravého trojúhelníku" (šešt čtverců nad hlavní diagonálou, dále píšu N jako "Nahoře") do "dolního levého trojúhelníku" (pod hlavní diagonálou, dále píšu D jako "Dole") nebo opačně. Po prvním kroku jsem tedy v N. Při putování mohou nastat tři možnosti, jak budu procházet body (2,2) a (3,3):

1) Na oba se dostanu z N a pokračuji z nich zase do N. Je zřejmé, že se nijak nemůžu dostat do D, takže tato varianta nemůže vést k řešení.


2) Jedním z nich nejprve projdu z N do D a pak druhým projdu z D do N. Rozdělím to na dvě varianty:

2.a) z N do D projdu bodem (2,2). Když jsem v něm, musím pokračovat na (1,2), jinak bych se tam už později nedostal (byla by to "slepá ulička"). Pak mám jedinou možnost na (1,3). Poté musím na (1,4), jinak bych se tam zase později nedostal. Pak jdu na (2,4). Nyní mám dvě možnosti - jít na (2,3) nebo na (3,4). Ani jedna ale není použitelná, protože z obou bodů musím pokračovat na (3,3) a už se později nedostanu do D, abych vybral ten druhý bod.

2.b)  z N do D projdu bodem (3,3). Když jsem v něm, musím pokračovat na (3,4), jinak bych se tam už později nedostal (nemohu projít přes (4,4), tam se musím dostat později z N). Pak mám jedinou možnost na (2,4). Poté musím na (1,4), jinak bych se tam zase později nedostal. Pak jdu na (1,3). Nyní mám dvě možnosti - jít na (2,3) nebo na (1,2). Ani jedna ale není použitelná, protože z obou bodů musím pokračovat na (2,2) a už se později nedostanu do D, abych vybral ten druhý bod.


3) Jedním projdu z N do D a druhým z D do D. Nebo nejprve jedním projdu z N zpět do N a pak druhým z N do D. Rozebrání této varianty přenechám laskavému čtenáři jako cvičení.

Napadl me jiny dukaz, zavedme souradnice stejne jako BrozekP, princ tedy stoji na policku [1, 1]. Protoze se princ muze pohybovat jen nahoru, dolu, doleva nebo doprava, soucet souradnic se pri kazdem kroku zmeni o 1, to znamena z licheho cisla na sude nebo naopak. Protoze se princ nemuze vracet na ctverecky na kterych uz byl, musi sebrat 15 klicu v 15 krocich a dostat se na policko [4, 4], odkud muze s klicemi za princeznou. Soucet souradnic se tedy pri jeho ceste zmeni 15*, 15 je liche cislo, proto bude princ po 15 krocich urcite na policku s lichym souctem souradnic. Proto je nemozne aby skoncil na policku [4, 4], a dostal se za princeznou.