Matematické Fórum

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.

našla jsem toto řešení:
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.

nevím jak se dá přijít na 2n · i - 31 · k

a ještě bych toto řešení potřebovala zobecnit nějak pomocí modulo

Předem děkuji za pomoc