Matematické Fórum

↑ FrantaVrabel:
Ahoj.
Tadz je jedna varianta> https://en.wikipedia.org/wiki/15_puzzle

Píše se tam zhruba toto:
V každém tahu se posune vzdálenost prázdného pole od místa, kde má být.
Každý tah -- přehození pozic dvou políček je aplikace transpozice.
Odtud plyne, že pokud součet vzdálenosti prázdného pole a parity permutace celé hry (9 polí) je lichý, pak ta hra nemá řešení.

Údajně platí i obrácená implikace. Proč, to nevím.

Tak konkrétně,
132
456
789
není řešitelná pozice.
- Vzdálenost 9 od místa, kde má být, je 0.
- Permutace celé skládačky odpovídá přehození čísel 2,3. Parita této permutace je 1 (berme to tak, že liché permutace mají paritu 1, sudé 0).
1+0=1 je liché. Do zadané pozice se tudíž nelze dostat z vyřešené pozice (a obráceně).

↑ misaH: Nerozumím otázce. Je tam moc záporů.

↑ misaH:
Aha chápu.

Škoda, že nemám zpětnou reakci. Jestli to bylo příliš složité odůvodnění. Jestli je třeba něco doplnit k důkazu, nebo má někdo jiné vysvětlení. Kdyby někdo věděl, proč platí i ta obrácená implikace, napište sem, nebo mi do PM.

Dík.

↑ Andrejka3:

>> 789 není řešitelná pozice.

to je neřešitelné zcela určitě - devítka tam totiž vůbec není :-)