Matematické Fórum

Renata 89 · 23. 04. 2014 20:13

Prosím o radu jak správně tento příklad vyřešit nikoliv experimentem ale pomocí "vysokoškolské matematiky". předem děkuji.

Tzv. „perfektním zamícháním“ nazveme zamíchání takové, že balíček rozdělíme na horní a dolní polovinu a promícháme tak, že vždy vezmeme nejspodnější kartu z dolní poloviny a na ni položíme nejspodnější kartu z horní poloviny, a to opakujeme, dokud nepoužijeme všechny karty. Na konci tedy budeme mít balíček, kde nahoře zůstane horní karta z horního balíčku a dole dolní karta z dolního balíčku. Kolikrát musíme balíček „perfektně zamíchat“, abychom dostali původní uspořádání? Počítejte s tím, že balíček má 32 navzájem odlišných karet.

Andrejka3 · 23. 04. 2014 21:17

↑ Renata 89:
Ahoj,
možná to má souvislost s řádem jisté permutace z $S_{32}$ .

Renata 89 · 23. 04. 2014 21:38

↑ Andrejka3:↑ Renata 89:↑ Renata 89:↑ Renata 89:↑ Renata 89: $S_{32}$

Obecné algebraické řešení je těžké. Provést pokus a zjistit, že stačí 5 zamíchání, byl zcela správný postup. Pokusím se přesto nastínit důkaz řešení pro 32 karet: Očíslujme si karty shora dolů 0, 1, 2, ... , 31 a proveďme jedno zamíchání. Vši-mně-me si, že karta na pozici i se přesunula na pozici 2i, popř. 2i - 31, pokud byla v dolní části balíčku.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

0 16 1 17 2 18 3 19 4 20 5 21 6 22 7 23 8 24 9 25 10 26 11 27 12 28 13 29 14 20 15 31

Sledujme pozice karty 1, ta bude postupně na pozicích 1, 2, 4, 8, 16, 1. Čtyři zamíchání tedy nemohou stačit -- teď už nám zbývá dokázat jen, že pět zamíchání už stačit bude.

Tvrdím, že pro každou kartu po n-tém zamíchání platí, že je na pozici 2n · i - 31 · k, kde k je nějaké přirozené číslo a i je původní pozice karty. Pokud je to pravda (a ono je), pak po pátém zamíchání je karta na pozici 32 · i - 31 · k, kde k je nějaké přirozené číslo. To upravíme na i + (31 · i - 31 · k). Tento druhý sčítanec musí být přirozené číslo, tedy i ≥ k. Pokud by i > k, pak by nová pozice karty byla větší než 31, ale taková pozice neexistuje. Tedy i = k, tento sčítanec je 0, a karta je po pátém zamíchání na pozici i.

Mam toto řešení ale nevím jak se dá příjít na 2n · i - 31 · k (a k je jaké přirozené číslo??)

Andrejka3 · 23. 04. 2014 22:06

↑ Renata 89:
Ještě taky nevím, ale zdá se mi zajímavé tohle:
1) vezmeme si kartu z dolní poloviny: dejme tomu, že má pod sebou n karet. Po jednom zamíchání má pod sebou kolik karet?
2) vezmeme si kartu z horní poloviny: dejme tomu, že má nad sebou n karet. Po jednom zamíchání má nad sebou kolik karet?

Andrejka3 · 24. 04. 2014 14:06

Už jen tři kroky a dostali bychom obecné algebraické řešení.

jelena · 05. 05. 2014 13:12

↑ Andrejka3:

Zdravím,

kolegyně by chtěla pokračovat v diskusi, ale neví, jak to tady funguje (ve svém smyslu pro pozoruhodné jevy (c) se ponořuji do hlubokých úvah, jak by to mělo fungovat jinak, než pokračováním :-) děkuji.

vanok · 05. 05. 2014 14:40

Poznamka ( nahradzuje malu abstrakciu):
Prechod z prvej postupnosti
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
ku tejto druhej
0 16 1 17 2 18 3 19 4 20 5 21 6 22 7 23 8 24 9 25 10 26 11 27 12 28 13 29 14 30 15 31

sa robi ako zuby na pilke.
Tento processus treba zopakovat tri krat este.... a potom pozorovat.

Brano · 05. 05. 2014 15:22 — Editoval Brano (06. 05. 2014 14:54)

Ked to chces napisat pomocou modula, tak je to pomerne jednoduche takto:

Karta s poziciou $k\in\{0,...,30\}$ sa po jednom zamiesani dostane na poziciu $2k \mod 31$ - t.j. zvysok $2k$ po deleni $31$ . (Karta na pozicii $31$ sa po celu dobu nehybe, tak ju mozme ignorovat.) Teda po $n$ zamiesaniach je na pozicii $2^nk\mod 31$ .

Teraz si staci vsimnut, ze $2^5=32=1\mod 31$ cize aj $2^5k=32k=k\mod 31$ - pre lubovolne $k\in\{0,...,30\}$ cize vsetky karty sa dostanu na svoje povodne miesto.

PS:

Renata 89 napsal(a):
Prosím o radu jak správně tento příklad vyřešit nikoliv experimentem ale pomocí "vysokoškolské matematiky".

Experiment v tom zmysle ako ho uvadzas v OP je dokonale legalny prostriedok vysokoskolskej matematiky, ci je uz v uvodzovkach, alebo nie. :-)

EDIT: pridana mala oprava a jedno dovysvetlenie

Matematické Fórum

#1 23. 04. 2014 20:13

Míchání karet

#2 23. 04. 2014 21:17

Re: Míchání karet

#3 23. 04. 2014 21:38

Re: Míchání karet

#4 23. 04. 2014 22:06

Re: Míchání karet

#5 24. 04. 2014 14:06

Re: Míchání karet

#6 05. 05. 2014 13:12

Re: Míchání karet

#7 05. 05. 2014 14:40

Re: Míchání karet

#8 05. 05. 2014 15:22 — Editoval Brano (06. 05. 2014 14:54)

Re: Míchání karet

Renata 89 napsal(a):

Zápatí