Matematické Fórum

nordec · 07. 03. 2010 18:43

Pořeboval bych poradit s tímto příkladem:
Uvažme šachovnici n×n pro liché n. Dokažte, že ať začnete kdekoliv, není možné proskákat koněm
celou šachovnici a vrátit se zpět na začátek, přičemž navštívit každé políčko právě jednou. Jinými
slovy: Uvažme graf, jehož vrcholy jsou jednotlivá políčka šachovnice a dva vrcholy jsou spojené
hranou, právě když je mezi nimi možné táhnout koněm. Dokažte, že pro lichý rozměr takový graf
nemá Hamiltonovskou kružnici.

Stýv · 07. 03. 2010 20:16

víš, že kůň skáče vždycky z bílýho políčka na černý a naopak?;)

nordec · 07. 03. 2010 21:07

To mě nenapadlo, pod šachovnicí jsem si představil jen čtvercovou síť, ta degenerace...
Pomůže to nějak? Proskákat šachovnici koněm lze obrovským množstvím způsobů, jak poznám bez vyzkoušení, že to zrovna pro tahle n nejde?

petrkovar · 07. 03. 2010 21:10

↑ Stýv:A jak to je pro $n=1$ ?

petrkovar · 07. 03. 2010 21:13

↑ nordec:Nápověda: nic nemusím zkoušet. Něčeho si pro n>1 všimnu a hned je neexistence hamiltonovského cyklu jasná. Jen zbývá domyslet, co všechno pro černobílou šachovnici platí.

nordec · 07. 03. 2010 22:53

↑ petrkovar:
První, čeho jsem si pro lichá n všimnul, je stejná barva prvního i posledního políčka, ať v řádku nebo sloupci. Všechny čtyři okraje šachovnice vypadají stejně. Asi tam platí ještě něco jiného, protože zatím mi není jasné, proč by tam hamiltonovská kružnice být nemohla, ale nic dalšího mě nenapadá...

Stýv · 07. 03. 2010 23:16

když začnu na bílé... na jakém poli budu po n^2 skocích?;)

nordec · 08. 03. 2010 10:59

Pro lichá n bude n^2 taky liché, z toho vychází, že na černém. Ale pro uzavření kružnice musí skončit, kde začal a to je na bílém. => SPOR, pro lichá n nikdy hamiltonovskou kružnici nedostaneme.
Ten důkaz je jednodušší, než jsem myslel, skutečně stačí si nečeho všimnout a pak dát 1 a 1 dohromady. Všem mockrát díky.

kayn · 13. 05. 2010 13:19

Nevítě někdo, pro která n*n sudá existuje Hamiltonovská kružnice pro koně? A proč?

Kondr · 20. 05. 2010 23:46

↑ kayn: http://en.wikipedia.org/wiki/Knight%27s … 7s_Theorem

Matematické Fórum

#1 07. 03. 2010 18:43

Hamiltonovská kružnice

#2 07. 03. 2010 20:16

Re: Hamiltonovská kružnice

#3 07. 03. 2010 21:07

Re: Hamiltonovská kružnice

#4 07. 03. 2010 21:10

Re: Hamiltonovská kružnice

#5 07. 03. 2010 21:13

Re: Hamiltonovská kružnice

#6 07. 03. 2010 22:53

Re: Hamiltonovská kružnice

#7 07. 03. 2010 23:16

Re: Hamiltonovská kružnice

#8 08. 03. 2010 10:59

Re: Hamiltonovská kružnice

#9 13. 05. 2010 13:19

Re: Hamiltonovská kružnice

#10 20. 05. 2010 23:46

Re: Hamiltonovská kružnice

Zápatí