Matematické Fórum

madla26 · 03. 04. 2015 19:02

Ahoj, nevíte náhodou, jak vyřešit následující úlohu?

//forum.matweb.cz/upload3/img/2015-04/80466_cesty.jpg

Kolika různými způsoby lze naplánovat cestu tak, abychom šli po všech silnicích, ale po žádné nešli víc než jednou.

jelena · 05. 04. 2015 11:38

Zdravím,

úloha je z některého testu SCIO (řekla bych, že jsem už toto zadání viděla, ale nevybavím, bohužel, kde)? Mne nenapadá jiná možnost, než jen použit pravidlo součinu a součtu a projít cesty "ručně":

a) bez užití velkých oblouků mám 2(AB), 2(BC), 3(CD), tedy dle pravidla součinu 2*2*3 možností, nebo (pravidlo součtu
b) použití velkého oblouku AC a k tomu 2(AB), 2(BC) cestou k A a potom zpět (pokud jsem zvolila jednu možnost ze 2, potom na cestě zpět volím 2. možnost, dokončím 3(CD), tedy 2*2*3.

další (opět pravidlo součtu) bych měla mít velký oblouk AC, jednu ze 3 (CD), 2 ze 3 (CD) na cestu zpět k C, opět dojit na A a opačnou cestou (kterou jsem dosud nepoužila k D. Obdobně s velkým obloukem BC. Vždy předpokládám začátek v A, konec v D

Ale uvažuji, zda není přehlednější způsob, než to "ruční", tak snad kolegové, nebo se vzpomene, kde bylo řešení. Děkuji.

Eratosthenes · 05. 04. 2015 14:10

zdravím ↑ jelena:,

Řešení určitě nelze rozložit a) bez použití velkých oblouků b) použití jednoho oblouku...

Jestliže by tam totiž velké oblouky nebyly, musel bych začít cestu v C a skončit v D (nebo naopak). Ale ony tam jsou, takže musím začít v A a skončit v B (anebo naopak)...

jelena · 05. 04. 2015 16:28

↑ Eratosthenes:

Zdravím Vás a děkuji, já jsem to pochopila špatně (?), že mám dojit z A do D, ne, že mám použit při jedné výpravě všechny cesty (to je pravda, v zadání to tak je, že všechny). A potom to je jedno, kde začnu a kde bude konec cesty (tedy podle Vás začít v A a končit v B)? Děkuji.

zdenek1 · 05. 04. 2015 16:40

↑ jelena:
Musíš začít v A a skončit v B (nebo obráceně). Jinak se to nedá projít.

Kdybys začala např. v D, tak musíš z D dvakrát odejít a dvakrát přijí, takže bys musela v D i skončit.
Jenže A má lichý počet cest, takže přijdeš - odejdeš - přijdeš a musíš skočit v A.
Což je spor.

Stejný argument bude platit i pro začátek v C.

Jediná bezesporná možnost je začít v A a skončit v B (nebo obráceně).

Protože každou cestu A - blablabla - B můžu otočit, stačí spočítat tyto cesty a vynásobit dvěma.
A to se bude asi muset udělat "ručně".

jelena · 05. 04. 2015 19:34

↑ zdenek1:

:-) ale zas něco musím, až dojdu domů, tak musím umývat schody a vstupní prostory, tak to musím a "ručně".

Protože každou cestu A - blablabla - B můžu otočit, stačí spočítat tyto cesty a vynásobit dvěma.
A to se bude asi muset udělat "ručně".

když jsem (nesprávně) uvažovala ↑ návrh:, tak jsem uvažovala i nějakou tabulku "vstupů" a "výstupů" pro jednotlivé uzly, ale nevím, zda by to bylo použitelné. Ručně to (ani s tabulkou, ani bez) nezvládnu.

Děkuji a zdravím.

byk7 · 05. 04. 2015 22:20 — Editoval byk7 (06. 04. 2015 02:11)

Překresleme si naše bludiště do následující podoby.
//forum.matweb.cz/upload3/img/2015-04/63491_forum.png .
Označme $P,Q,R$ postupně počty cest s počátečním bodem $A$ , (koncovým $B$ ) a naznačenými směry na obrázcích

Pak podle mě je počet všech možných cest roven výrazu $2(6P+3Q+12R)$ .

Edit: Spočítat $P,Q,R$ se mi moc nedaří. Pravděpodobně na to půjde nasadit BEST theorem, ale nevím jak.