Matematické Fórum

Toothless · 27. 10. 2015 19:09

Představte si šachovnici 6x8 polí, kde každé pole je černé nebo bílé. Otázka zní, kolik bílých polí může být v poli za těchto podmínek:

1)Dvě bílá pole budou označena jako start a cíl.

2)Mezi těmito dvěma poli musí být cesta po bílých polích, kde každý "krok" může vést z jednoho pole na sousední, ale ne diagonální.

3)Takováto cesta musí být jen jedna(tedy žádné větvení atp.).

4)Nesmí být žádná bílá pole mimo cestu.

Kolik bílých polí může být? Dal by se problém zobecnit pro jakkoliv velké "šachovnice"? Prosím o jednoduchou odpověď (na úrovni základní školy). Děkuji.

jelena · 27. 10. 2015 20:24

Zdravím,

pro pořádek - můžeš, prosím, upřesnit, že nejde o žádný aktuální soutěžní úkol, ani o domácí úlohu, jinak - viz pravidla. Jak jsi k úloze přišel? Děkuji za upřesnění.

K samotnému textu úlohu - mám rozumět, že start a cíl musí být umístěn tak, aby umožnil z desky odejít (nebo to není podstatné)? Předpokládám, že nejde o klasické šachovnicové uspořádání. V názvu je "nejdelší cesta" - tedy za vyřešení se požaduje skutečně důkaz, že navržená cesta bude nejdelší? Děkuji za další upřesnění.

Toothless · 27. 10. 2015 21:41

O opouštění plochy nejde. Jak jsem k úloze přišel: Učím se programovat v jazyce Scratch a tvořil jsem hru na podobné ploše jako je v této úloze, kde černá pole tvoří stěny. Zajímalo mě, jaká nejdelší cesta existuje proto, že součástí programu má být algoritmus, který najde cestu přes dané pole, a potřeboval jsem vědět, s jakou největší délkou má počítat. Nakonec jsem pro jistotu dal několik polí navíc, ale když jsem se nudil, začal jsem o tom problému zase přemýšlet, ale na nic jsem nepřišel.

Ještě k zadání: Vidím, že to nebylo jednoznačné, jde doopravdy o nejdelší cestu.

jelena · 27. 10. 2015 23:56

↑ Toothless:

děkuji za upřesnění, k návrhu řešení nic nemám, snad to ale bude přehlednější pro kolegy.

Eratosthenes · 28. 10. 2015 08:17

ahoj ↑ Toothless:,

asi jsem něco nepochopil, protože zatím na tom nemám co řešit:

//forum.matweb.cz/upload3/img/2015-10/16641_SACH.png

jelena · 28. 10. 2015 10:02

↑ Eratosthenes:

Zdravím, toto asi neplatí dle návrhu zadání - pokud začnu nahoře vlevo (start), udělám krok napravo, hned mohu pokračovat krok dolu, ještě jeden dolu a nalevo - jsem v cíli. Jelikož kolega úlohu formuloval samostatně, možná ještě je třeba doladit něco v zadání (+ jak se bude dokazovat, že je nalezeno to správné řešení). Já to mám ovšem jednoduché - s ohledem na všechny chybějící vlastnosti + venku je pěkně, třeba toho využit.

Eratosthenes · 28. 10. 2015 10:35

ahoj ↑ jelena:,

>> hned mohu pokračovat krok dolu

To mohu, ale podle zadání nemusím. Naopak - kolega hledá nejdelší cestu - viz ↑ Toothless:

jelena · 28. 10. 2015 11:11

↑ Eratosthenes:

asi nemohu: "3)Takováto cesta musí být jen jedna(tedy žádné větvení atp.).", toto ale je možnost větvení - tak?

Stýv · 28. 10. 2015 12:27

Toothless napsal(a):
Zajímalo mě, jaká nejdelší cesta existuje proto, že součástí programu má být algoritmus, který najde cestu přes dané pole, a potřeboval jsem vědět, s jakou největší délkou má počítat.

použij algoritmus, kterej bude fungovat pro libovolně dlouhou cestu. jinak horní odhad pro délku cesty je samozřejmě 6*8=48, což je ve světě počítačů směšně malý číslo, takže bych se hledáním nějakého přesnějšího odhadu vůbec nezdržoval

zdenek1 · 28. 10. 2015 13:16

Co toto?
//forum.matweb.cz/upload3/img/2015-10/34548_pic.png

check_drummer · 28. 10. 2015 14:11

↑ Toothless:
Ahoj,
nechápu pár věcí, např.:
a) "... kolik bílých polí může být v poli ..."? Pole v poli...? Co myslíš přesně polem a co celou tou větou?
b) Uvažujeme "standardně" obarvená pole této šachovnice a nebo si to barvení polí nějak volíme sami?
c) "Mezi těmito dvěma poli musí být cesta po bílých polích,.." - znamená to, že musí být cesta pouze po bílých polích? Pokud opravdu pouze - pak nelze provést legální krok (jsme-li na standardně obarvené šachovnici a nesmíme dělat diagonální kroky). A pokud nikoli pouze, pak je ta informace dost matoucí (a zbytečná)...
d) "Takováto cesta musí být jen jedna" - co to znamená a jak to souvisí s větvením? Nemáš na mysli, že postupujeme tak, že se nesmíme vracet na již jednou navštívená pole?
Děkuji za objasnění

check_drummer · 28. 10. 2015 14:12

↑ Stýv:
To je otázka, ověřit, že graf na 48 vrcholech obsahuje Hamiltonovskou kružnici dá i počítači dost zabrat. :-)

jelena · 28. 10. 2015 16:41

↑ zdenek1:

Joan Miro a Vasarely tiše pláčou v koutě :-) Tak jsem také měla, ale kde je důkaz?

↑ check_drummer:

kolega něco upřesňoval na moji otázku v dalším příspěvku - není to šachovnice, ale obdélník rozdělený pomoc čar na čtverečky, každý čtvereček můžeš obarvit bílou nebo černou barvou.

Učím se programovat v jazyce Scratch a tvořil jsem hru na podobné ploše jako je v této úloze, kde černá pole tvoří stěny

tedy spíš chodba (není to ani labyrint - není větvení) - bíla je cesta, černá je zeď. Tedy podle mne ovlivní umístění startu a cíle, jinak cca jako kolegové (jen kolega ↑ Eratosthenes: by měl mít větší mezery mezi jednotlivými řádky.

Zdravím.

Honzc · 29. 10. 2015 07:17 — Editoval Honzc (31. 10. 2015 09:37)

↑ Toothless:
Jestli jsem úlohu dobře pochopil jde ti o to (při respektování podmínek) stanovit největší počet bílých polí v "matici" mxn.
Podle mě se maximální počet bílých polí vypočítá (protože píšeš, že budeš programovat, předpokládám, že víš co je to operace div - celočíselné dělení)
Předpokládejme, že matici $m\times n$ uspořádáme tak, že $m\le n$
Pak platí: pro $m\,-\,\text{liché}$ $b_{max}=\frac{(m+1)n}{2}+((m-1)\,\text{div} \,2)$
a pro $m\,-\,\text{sudé}$ $b_{max}=\frac{(n+1)m}{2}+((n-1)\,\text{div} \,2)$

Autor skryl část textu. Zobrazit/skrýt!

Toothless · 01. 11. 2015 16:18

Několik věcí k ujasnění:

1) "Větvení" je vágní, za to se omlouvám. Myšleno je, že nesmí existovat víc různých cest ze startu do cíle.

2) "Pole v poli" Ve velkém poli je 6x8 menších políček(něco jako šachovnice).

3) Nejde o šachovnicové obarvení, cílem je právě vhodné obarvení najít.

4) "Jen jedna cesta" Myšleno je to, že když vytvoříme obarvení, nemohou být dva(nebo více) způsoby, jak se dostat ze startu do cíle jen po bílých polích(tj. nemůže být žádná cesta široká dvě políčka, a nikde se nesmí chodba dělit).

5) Jazyk Scratch je naprostý základ(vlastně to není programovací jazyk, příkazy jsou předpřipravené a spojují se, nic se nepíše). Jestli jsem to pochopil, celočíselné dělení znamená, že zahodíme zbytek, je to tak?

6) Chvíli jsem něco hledal, a našel jsem jednu možnost se 31 bílými poli(nemůžu to sem dát, nevím, jak přidat tabulku).

Je to už aspoň trochu pochopitelné?

Honzc · 02. 11. 2015 08:05 — Editoval Honzc (02. 11. 2015 16:44)

↑ Toothless:
Píšeš "Jestli jsem to pochopil, celočíselné dělení znamená, že zahodíme zbytek, je to tak?" - ano pochopil jsi to dobře, i když lépe je napsat, že zahodíme desetinnou část výsledku dělení.
A teď mám já prosbu.
Docela by mě zajímala ta cesta s 31 bílými poli.
Vykašli se na tabulku a dej se souřadnice černých polí.
Domluva:
Řádky popiš odshora dolů písmeny A-F (A,B,C,D,E,F)
Sloupce očísluj zleva doprava čísly 1-8
Pak levý horní roh má popis (souřadnice) A1
Takhle popiš kde jsou černá pole.
Např. u mého druhéhoo obrázku 3x4 jsou černá pole na: A2,B2,B3

A nebo to napiš takto:
Můj první obrázek 6x8 (B značí bílá, A černá)
B B B B B A B B
B A A A B A B A
B A B A B A B B
B A B A B B A B
B A B A A B A B
B B B A A B B B

Po editu:
6x8 jde opravdu najít cestu dlouhou 31 - viz níže.

Autor skryl část textu. Zobrazit/skrýt!

Pak tedy obecný vzorec pro matici mxn bude:
Pro $m,n\,\text{sudé}$
$b_{max}=\frac{m\cdot n+m+n}{2}$ -tohle ještě opravím (není úplně dobře)
jinak
$b_{max}=(m\cdot n+m+n-1)\,\text{div}\,2$

Toothless

Pro 31 bílých:
Černá:

E1
B2
C2
E2
G2
B3
E3
G3
B4
D4
E4
F4
G4
B5
C5
G5
E6

Nebo:

B B B B A B B B
B A A B A B A B
B A B B A B A B
B A B A A A A B
B A A B B B A B
B B B B A B B B

Děkuju za pomoc.
Poznámka:Mám dojem, že jsem našel i 32, ale pak jsem to někam založil. Snad to najdu.

[EDIT: Písmena a čísla mám nahoře prohozeně, čísla značí vrstvy(řady)]

[EDIT 2: Mám 32! (viz dole)]

32 bílých:

B B B B A B B B
B A A B A B A B
B B A B B B A B
A B B A A A A B
B A A B B B A B
B B B B A B B B

Nebo:

B B B B A B B B
B A A B B B A B
B A B A A A B B
B A B A B B B A
B A B A B A A B
B B B A B B B B

[EDIT 3: Viděl jsem ještě ve skrytém textu pro pole 4x6 jedno na 16, ale našel jsem na 17:]

17 bílých pro 4x6:

B B B A B B
B A B A A B
B A B B A B
B B A B B B

Honzc · 03. 11. 2015 11:02

↑ Toothless:
4x6 jsem také udělal na 17
a dokonce když zkombinuješ 2 4x6 - jeden 17, duhý 15 dostaneš 6x8 - 32.
viz níže:

Autor skryl část textu. Zobrazit/skrýt!

Matematické Fórum

#1 27. 10. 2015 19:09

Nejdelší cesta v obdélníku

#2 27. 10. 2015 20:24

Re: Nejdelší cesta v obdélníku

#3 27. 10. 2015 21:41

Re: Nejdelší cesta v obdélníku

#4 27. 10. 2015 23:56

Re: Nejdelší cesta v obdélníku

#5 28. 10. 2015 08:17

Re: Nejdelší cesta v obdélníku

#6 28. 10. 2015 10:02

Re: Nejdelší cesta v obdélníku

#7 28. 10. 2015 10:35

Re: Nejdelší cesta v obdélníku

#8 28. 10. 2015 11:11

Re: Nejdelší cesta v obdélníku

#9 28. 10. 2015 12:27

Re: Nejdelší cesta v obdélníku

Toothless napsal(a):

#10 28. 10. 2015 13:16

Re: Nejdelší cesta v obdélníku

#11 28. 10. 2015 14:11

Re: Nejdelší cesta v obdélníku

#12 28. 10. 2015 14:12

Re: Nejdelší cesta v obdélníku

#13 28. 10. 2015 16:41

Re: Nejdelší cesta v obdélníku

#14 29. 10. 2015 07:17 — Editoval Honzc (31. 10. 2015 09:37)

Re: Nejdelší cesta v obdélníku

#15 01. 11. 2015 16:18

Re: Nejdelší cesta v obdélníku

#16 02. 11. 2015 08:05 — Editoval Honzc (02. 11. 2015 16:44)

Re: Nejdelší cesta v obdélníku

#17 02. 11. 2015 16:59 — Editoval Toothless (02. 11. 2015 19:54)

Re: Nejdelší cesta v obdélníku

#18 03. 11. 2015 11:02

Re: Nejdelší cesta v obdélníku

Zápatí