 |
Betka: Pokud táhnu katru k, uloží se na k-tou pozici, pak není možné tuto změnit jinou, než větší kartou.
Před kartou k je k-1 karet z nich alespoň jedna musí být větší, než karta k.
A)Pokud je mezi nimi alespoň jedna karta větší, než k, pak ji táhnu nejpozději po (k-1)! krocích, ta se pak zařadí na svou pozici r>k, proces opakuji pro r a tak dále, dokud nebude nakonci posloupnosti největší číslo, jehož pozici nelze změnit jinou kartou, tím získáme k-1 karet, z nichž žádná nemá číslo větší, než k a mezi kterými je jednička.(Případně je možné, že na jedničku narazíme dříve)
B)Pokud je mezi nimi jednička, pak ji táhnu nejhůře po (k-1)! krocích, protože pokud z k-1 karet táhnu jednu získám nové k´, to může být přemístěno jedině číslem větším, největší číslo v balíčku, kde není žádné číslo větší k je k-1, to se zařadí před k a nemůže být zbývajícími kartami posunuto, protože největší zbývající číslo je k-2.
Pak se mi tedy nutně musí posloupnost řadit od největšího po nejmenší, nebo najdu jedničku dříve.
Hádám, že důkaz matematickou indukcí by byl přehlednější a mnohem elegantnější. |
