Matematické Fórum

Freedy · 24. 08. 2014 01:13

Dobrý večer,

na většině mobilech se používá bezpečností gesto, které se musí zadat, aby dotýčný uživatel získal přístup k dalším funkcím. Vypadá většinou takto, 9 teček, mezi kterýma musíte nakreslit čáru jež vám odemkne telefón:
//forum.matweb.cz/upload3/img/2014-08/35054_bezpecnostnigesto.jpg
Jakmile se dostanete do jednoho bodu, už se cestou zpátky v daném bodě znovu nezachytíte.

Jen pro zpřesnění, když si označím jednotlivé body jako

A B C
D E F
G H I

Tak když začnu v bodě E, pokračuji do bodu I a poté do bodu A tak platí: $|AI|=2\sqrt{2}$ Čili výsledná délka bude $|EI|+|AI|=1+2\sqrt{2}$ protože se cestou zpátky cesta nezastaví v E ale projde skrz něj. Pokud bych šel z bodu A do bodu I tak bych prošel bodem E a délka by byla $|AE| + |EI| = 1+1$ což je méně než předchozí délka.

A teď k moji otázce, jak lze tímto způsobem propojit všech 9 bodů, aby výsledná čára byla co nejdelší?

Jen zkoušením jsem dospěl k něčemu jako: E I A H C D F G B. Výsledná délka by byla:
$\sqrt{2}+2\sqrt{2}+\sqrt{5}+\sqrt{5}+\sqrt{5}+2+\sqrt{5}+\sqrt{5}=2+3\sqrt{2}+5\sqrt{5}\approx 17,422$
Mě teda zajímá, jestli existuje nějaká delší cesta.

Nevím jestli někdo bude vůbec reagovat na takovouhle blbost, ale docela mě zajímalo jaká nejdelší cesta lze vytvořit mezi 9 body s těmito podmínkami.

Děkuji

jelena · 24. 08. 2014 09:14

Zdravím,

většinu takových mobilů jsem viděla :-) Osobně používám takový nezlomný zázrak. Řekla bych, že Tvůj problém naleží k problému hamiltonovského grafu s tím, že ještě přidáváš podmínku vzdálenosti uzlů v geometrickém smyslu. Přesunu do Zajímavých pro SŠ.

Xellos · 24. 08. 2014 10:30 — Editoval Xellos (24. 08. 2014 10:56)

↑ Freedy:

Myslim ze neexistuje. Tu je to vcelku lahke, lebo nemas vela roznych vzdialenosti a len 2 najdlhsie (uhlopriecky), a inak mozes pouzit vela skoro najdlhsich.

Priblizne dokaz: E nas nuti pouzit aspon jednu vzdialenost $\le \sqrt{2}$ ; treba dokazat ze obe uhlopriecky nie su optimalne, ze 0 tiez nie je optimalna a potom ze zvysne vzdialenosti nemozu byt vsetky $\sqrt{5}$ . Konstrukciu uz mame.

Ako hovori ↑ jelena:, hladame najdlhsiu Hamiltonovsku cestu v kompletnom grafe na $n$ vrcholoch. Ak su vzdialenosti vseobecne, treba na presne vyratanie exponencialne vela casu, neviem ako pri euklidovskych vzdialenostiach.

Freedy · 24. 08. 2014 12:18

Zkoušel jsem hledat delší cestu, ale jaksi jsem se na žádnou delší nedostal, takže by teoreticky mohla být nejdelší, ale není to jisté.

Xellos napsal(a):
treba dokazat ze obe uhlopriecky nie su optimalne

Jak to myslíš, nejsou optimální? Lze použít obě dvě uhlopříčky, ale bylo by to nevýhodné, protože poté by tě to přinutilo udělat jednu menší délku, což by se v součtu nevyplatilo.

Každopádně pokud neexistuje delší cesta, tak nemám další dotazy. Děkuji :)

mák · 25. 08. 2014 21:08

Zdravím,
zkusil jsem použít metodu hrubé síly a vyšlo mi (jedna z možností):

Code:

B,H,A,I,D,F,G,C,E

Délka trasy je $3\,\sqrt{5}+5\,\sqrt{2}+4=17.77927174436484$
Snad jsem to dobře spočítal :-)

Kluzz · 26. 08. 2014 16:16

Máš tam navíc $\sqrt{2}$ , bod E se započítá hned na začátku (místo B-H je B-E-H)

Xellos · 26. 08. 2014 21:52

Freedy napsal(a):
Xellos napsal(a):
treba dokazat ze obe uhlopriecky nie su optimalne
Jak to myslíš, nejsou optimální? Lze použít obě dvě uhlopříčky, ale bylo by to nevýhodné, protože poté by tě to přinutilo udělat jednu menší délku, což by se v součtu nevyplatilo.

A to znamena ze nie su optimalne.

Matematické Fórum

#1 24. 08. 2014 01:13

Nejdelší kombinace

#2 24. 08. 2014 09:14

Re: Nejdelší kombinace

#3 24. 08. 2014 10:30 — Editoval Xellos (24. 08. 2014 10:56)

Re: Nejdelší kombinace

#4 24. 08. 2014 12:18

Re: Nejdelší kombinace

Xellos napsal(a):

#5 25. 08. 2014 21:08

Re: Nejdelší kombinace

Code:

#6 26. 08. 2014 16:16

Re: Nejdelší kombinace

#7 26. 08. 2014 21:52

Re: Nejdelší kombinace

Freedy napsal(a):

Xellos napsal(a):

Zápatí