Решение. Американская тасовка (#147)
Пусть в колоде чётное количество N карт. Пронумеруем все карты снизу вверх от 1 до N. Запишем для произвольной карты с номером n, на какую позицию она переместится после одной тасовки.
Если карта находится в нижней половине, то есть n ≤ N/2, то она займёт позицию с номером 2n – 1 после тасовки. Действительно, по определению тасовки между каждой парой соедних карт в нижней половине в результате смешения появится новая карта из верхней половины. То есть перед картой с номером n появится n – 1 карта, увеличивая её позицию до n + n – 1 = 2n – 1 (см. рисунок 1)
Если карта с номером n находится в верхней половине, то в результате тасовки она кладётся поверх карты с номером n – N/2 из нижей половины. Таким образом её позиция после тасовки будет 2(n – N/2) = 2n - N
Тасовка – это перестановка на N элементах. Как известно, любая перестановка является суперпозицией циклов. Найдём эти циклы с учётом установленного выше правила для случая 52 карт.
1: [1]
8: [2, 3, 5, 9, 17, 33, 14, 27]
8: [4, 7, 13, 25, 49, 46, 40, 28]
8: [6, 11, 21, 41, 30, 8, 15, 29]
8: [10, 19, 37, 22, 43, 34, 16, 31]
8: [12, 23, 45, 38, 24, 47, 42, 32]
2: [18, 35]
8: [20, 39, 26, 51, 50, 48, 44, 36]
1: [52]
Проверим, что сумма длин циклов равна N.
Искомое количество тасовок равно наименьшему общему кратному длин всех циклов. В нашем случае это 8.