Kolika způsoby jde nakreslit domeček jedním tahem?

Kombinatoriku jsme už sice měli, ale tohle mě docela zmátlo. Je na to nějaký vzorec, nebo nezbývá nic jiného, než vzít tužku a papír a kreslit si to? :DD

PS: Úkol to není, jen mě to zajímá. :)

Upravil/a: Frogman

Odpovědět

Zajímavá 0 před 3281 dny

Sledovat Nahlásit

Diskuze: 1 příspěvek, nejnovější před 3275 dny

Odpovědi

Kepler

Já mám naučený jen jeden. Může se ale začít za prvním úhlem a tak pokračovat dál. Směr je vždy stejný. Počítat se mi to nechce, radši bych si to kreslil. Ty máš ale starosti! 🙂

1 před 3281 dny

0 Nominace Nahlásit

klumprt

Asi tak před patnácti lety jsme to počítali, ale teď si pamatuju už jen to, že se musí začít v jednom spodním rohu a skončí se v druhém. A pozor na automorfismy, tzn. spočítej jen cesty z jednoho rohu. Cest z druhého rohu totiž bude úplně stejně.

1 před 3281 dny

0 Nominace Nahlásit

J_K

V každém rohu mohu začít ve směru každé úsečky, t.j. třemi směry. Tedy včetně automorfismů 3*4=12
Začít v průsečíku úhlopříček nelze.

1 před 3275 dny

0 Nominace Nahlásit

wakedown

Domeček je Eulerova jednotažka a existují 2 uzly (podstava domečku), které mají lichý stupeň, tj. vede do/z nich lichý počet úseček. Zbylé uzly mají sudý stupeň. Tedy kreslení domečku musí začít v jednom vrcholu v podstavě a skončit v druhém vrcholu podstavy. (jinak bys vjel do lichého vrcholu a pak by nebylo z něj jak vyjet).
Navíc, jestli tedy máme začít v jednom vrcholu v podstavě a skončit v tom druhém, stačí to spočítat pro jeden vrchol a vynásobit 2. (je to zrcadlově symetrické) Takže to jsem udělal pomocí „brute force“ a výsledek je 2×43, tedy 86 možností.

Tady je ještě výčet všech možností:
X – začni v levém spodním rohu domečku
Y- začni v pravém spodním rohu domečku
U/D/L/R – jdi nahoru/dolů/doleva/doprava
E – jdi uhlopříčkou na „severozápad“
A – jdi uhlopříčkou na „severovýchod“
B – jdi uhlopříčkou na „jihovýchod“
C – jdi uhlopříčkou na „jihozápad“

XUABLBLAD
XUABLBUCR
XUABCRERD
XUABCRULB
XUABDERCR
XUABDLALB
XURECBUCR
XURECBLAD
XURCREABD
XURCRUECB
XURDEABCR
XURDLAECB
XUBLALABD
XUBUECRCL
XUBULABCL
XALDREABD
XALDRUECB
XALABDLUB
XALABDEDR
XALBLUABD
XALBUECDR
XAECDRULB
XAECDRERD
XAECRDLUB
XAECRDEDR
XAECBULDR
XAECBLURD
XADLURECB
XADLUABLB
XADEABLDR
XADERECDR
XREDALABD
XREDAECRD
XRERCUABD
XRERECDAD
XREABLDAD
XREABCURD
XRUCUABLB
XRUCURECB
XRULABCUB
XRULDAECB
XRUECRCUB
XRUECDALB
YUECRCRED
YUECRCUBL
YUECBLALD
YUECBLURC
YUECDALBL
YUECDRERC
YULABCUBL
YULABCRED
YULBLAECD
YULBLUABC
YULDAECBL
YULDREABC
YUCRERECD
YUCUABLBR
YUCURECBR
YERDLAECD
YERDLUABC
YERECDRUC
YERECDADL
YERCRUECD
YERCUABDL
YEABDLURC
YEABDLALD
YEABLDRUC
YEABLDADL
YEABCURDL
YEABCRULD
YEDRULABC
YEDRUECRC
YEDAECRDL
YEDALABDL
YLADERECD
YLADEABLD
YLALBUECD
YLALABDED
YLAECRDED
YLAECBULD
YLUBUECRC
YLUBULABC
YLURECBUC
YLURDEABC
YLUABLBUC
YLUABDERC

0 před 1425 dny

0 Nominace Nahlásit

Diskuze k otázce

Dochy

J_K: Myslím, že se mýlíš. Klasický domeček bude čtverec s úhlopříčkama a trojúhelníkem nahoře jako střechou. Začít můžeš jen v levém nebo pravém rohu. pokud bys začel v některém horním rohu musel by ses do toho samého rohu vrátit a nepokryl bys lichý počet čar z dolních rohů.
Už jsem našel 6 možností když uvažuju pouze start z levého dolního do pravého dolního a pak pravého horního rohu (6 možností které navazují na takto popsanou situaci). Zrcadlově je to dalších 6 možností a pak odhadem tak 4 násobek bude pro jiný postup v prvních dvou tazích (hrubý odhad, netestoval jsem)

před 3275 dny Odpovědět Nahlásit

Nový příspěvek

Zajímavé otázky v kategorii Věda