Matematické Fórum

↑ Kondr:

moc ti děkuji za tvé řešení. sic ho vůbec nechápu jelikož jsme ještě něbrali hamiltonovskou kružnici a tak nevím co to je a jak se s ní pracuje ale snad to nějak pochopím. kdyby si měl čas třeba náhodou mi nějak stručně vysvětlit tu kružnici a podrobně celý postup řešení byl bych ti velice moc vděčný. Ale i tak moc díky.

↑ Kondr:

super díky tvému výkladu jsem to pochopil. Moc ti děkuju, jsem ti dlužníkem. Díky

Nemám čas rozepisovat každý krok, takže prosím napiš, kde jsi se ztratil:
1)Uvažujeme ten graf
2)Zjistíme, že se ta šachovnice dá koněm přeskákat tak, že projdeme všechna pole a vrátíme se na výchozí
3)Tohle přeskákání nám určuje kružnici, která prochází všechny vrcholy grafu
4)Na té kružnici jsou 4 koně a alespoň jedno volné místo
5)To nám umožňuje koně cyklicky posunout (tam kde byl první, bude druhý, tam kde druhý, bude tetí,...,tam kde čtvrtý, bude první).
6)Podle toho, v jakém pořadí koně na kružnici stáli, nám stačí udělat jeden nebo dva cyklické posuny.

Napiš které kroky jsou ti jasné.

Kůň = jezdec. Šachy jsem nikdy nehrál "na úrovni", takže té figurce říkám občas humpolácky kůň, ikdyž to šachistům možná rve uši :o)

ad 3) Za názvy vrcholů v grafu zvolím jejich souřadnice. To, že šachovnici lze přeskákat znamená, že v grafu existuje kružnice

    |-- (1,1)--(2,3)--(3,1)--(4,3)--(2,2)--(4,1)--(3,3)--(2,1)--(1,3)--(3,2)--|
   |                                                                                                        |
   -------------------------------------------------------------------------------------

graf kromě kružnice obsahuje i další hrany, ale ty nás nezajímají.

ad 5) Teď vrcoly odpovídající polím, na nichž stojí jezdci, přejmenujeme na A, B, C, D, jedno z volných polí na kružnici označme E. Bez újmy na obecnosti to udělám tak, aby ty vrcholy byly na té kružnici v abecedním pořadí. Pak kůň z D doskáče do E, kůň z C do D, atd, tím se cyklicky posunou.

↑ Kondr:
zdarec ja vim uz zase ale at si ten graf kreslim jak jen to jde porad mi to neni jasne. Nejak porad nedokazu pochopit tu cyklickou zamenu v te kruznici. Nechapu prosim pomozte.

↑ Kondr:
temi spojnicemi myslis ty souradnice co jsi vypsal? nebo co? zkusim si to.

↑ turcovsky:No že musí být dáno nějaké pravidlo, jak se mají jezdci pohybovat, je jasné. A dá se čekat, že to pravidlo bude jednoduché, např. "po kružnici ve smyslu chodu hodinových ručiček". Hamiltonovaká kružnice by nám zajistila, že toto pravidlo bude takto jednoduché.

Zjistil jsem ale, že mám v řešení zásadní chybu! Kružnice není Hamiltonovská, prochází jen deseti z 12 vrcholů. Pokud jsou všichni jezdci na této kružnici, řešení zůstává stejné. Pokud ne, je potřeba ho mírně upravit tak, že koně co nejsou na kružnici se na ni na začátku přemístí a na konci z ní koě opačné barvy skočí zpátky.

↑ turcovsky:To spíš já jsem se měl omluvit, páč jsem tě celou dobu přesvědčoval o správnosti řešení, které správné nebylo. Jsem rád že jsem pomohl.