Раздел: Документация
0 ... 65 66 67 68 69 70 71 ... 117 4 1 1- 6 ---3 Четное тасованиеЧетное тасование внутрьповерх 3 4 5 4 5 Нечетное тасованиеНечетное тасование внутрьповерх Рис. 14.1. Тасования внутрь и поверх для четного и нечетного числа карт с исходным расположением 1, 2,3,... сверху вниз. что тг может быть записана в виде тгО) = 2х (mod 2к + 1), это, напоминаем, означает, что 7г(х) - 2х - точное кратное 2к + I1. В этом случае тг(х) будет равно либо 2х, либо 2х ~ (2к + 1). Обратите внимание, что, поскольку это перестановка мест, мы сразу знаем, что повторение того же самого тасования приведет к ПМ, полученной выполнением тг дважды: ir2{x) = ir(ir(x)) = тт(2х) = 4х (mod 2k + 1).(14.3) Таким образом, здесь карта, занимавшая в начале до тасования место х, в конце после двух тасований окажется на месте 4х (mod 2k + 1). Проверьте это непосредственно для случая п = 6. Какое минимальное число раз необходимо повторить это тасование при п=6, чтобы карты вернулись в первоначальное положение? Свойства обозначения = mod п, которые нам нужны, суть: если а ~Ь и с = d, то (i) а ± с = Ь ± d и (ii) ас = bd. В частности, если а ~ Ь, то аТ = Ьг для любого целого г > 0. Чтобы показать, как соединять перестановки в М-файле, М-файл rifuel.m повторяет тасование внутрь для четного и любое число раз. Изучите этот М-файл: позже вам придется внести в него изменения. Заметьте, в частности, что он использует sort , чтобы распечатать окончательный порядок карт по их значениям, поскольку именно это мы хотим знать. Воспользуйтесь им, чтобы узнать минимальное число тасований 14 карт, необходимое для восстановления их исходного порядка. Теперь взгляните на М-файл rifiela.m . Здесь последовательно вычисляются степени 2 и приводятся по mod 2&+1, т.е. вычисляется остаток от деления результата на 2к + 1. Возьмите к = 7; полученное значение г должно совпадать с числом тасований внутрь 14 карт, рассмотренным выше. Это объясняется следующим образом. Повторением рассуждений, приводящих к формуле (14.3), мы находим, что перестановка мест для г повторных тасований есть перестановка 7ГГ, обладающая свойством, что для любого места х кг{х)=2Тх (mod 2*;+ 1). Отсюда следует, что если 2r ~ 1, то каждая карта возвращается на ее исходное место! Обратно, если каждая карта возвращается на ее исходное место, то, в частности, карта на 1-м месте возвращается на 1-е место, так что 2Г = 1. Таким образом, наименьшее число повторных тасований, возвращающих все карты в первоначальное положение, есть наименьшее г, для которого 2Г Е 1 (mod 2k + 1). Это наименьшее число называется порядком тасования или порядком перестановки, описывающей тасование. (Терминология, конечно, весьма неудачная, поскольку перечисление элементов перестановки (их порядок) говорит о значениях на картах сверху вниз.) Воспользуйтесь rifflela.m, чтобы найти это наименьшее г для всех четных чисел от 40 до 52 включительно. Повторите сделанный выше анализ для других трех случаев. Ввиду небольших различий дадим по этому поводу некоторые указания. 14-2.2. Четные тасования поверх Здесь имеется и = 2к карт, но теперь 1 идет поверх первой, и после одного тасования карты упорядочиваются по значениям так: l,fc + l,2,A--2,3,fc+3,... , к,2к Взгляните на рис. 14.1 для к = 3. Проверьте, рассмотрев, например, п - 6, п = 10, что перестановка мест в этом случае есть тг, где 7r(j) = 2х - 1 (mod 2к - 1) при 1 < х < 2к - 1, тогда как тг(2£) = 2к. Имеется одна дополнительная сложность: для х - к новое место есть 2к- 1, а не 0. Таким образом, при вычислении тг{х) мы берем остаток от деления 2х - 1 на 2к - 1, но, поскольку нет места 0, остаток 0 означает место 2к - 1. Чтобы облегчить это, для вас была написана специальная функция remm.m. Она делает то же, что и rem, за исключением остатка 0. Таким образом, remm(19,ll) дает 8, но remm(22,ll) и гетт(11,11) дают 11. Сперва, используя функцию готтлп, модифицируйте rif Uel.ni, чтобы он работал в случае четного тасования поверх. Вам надо изменить г-цикл, чтобы он продолжался только до 2fc - 1, и вставить store(2*k)=2*k; это делается после окончания i-цикла, но до команды position perm=store. Назовите ваш модифицированный М-файл riffle2.niH воспользуйтесь им, чтобы проверить, что 52 карты возвращаются к первоначальному упорядочиванию после всего лишь восьми тасований поверх. Сравните полученное с числом тасований внутрь для 52 карт, найденным вами выше с помощью rifflela.m? Далее, детализируйте следующий набросок доказательства, чтобы показать, что число тасований поверх, требуемое для возврата 2к карт на их исходные места, есть наименьшее г, для которого 2Г = 1 (mod 2k - 1). Приводим набросок доказательства. Заметьте, что карта, находившаяся вначале на месте 2&, там и останется после любого числа тасований поверх, поэтому мы исключим х = 2к из дальнейшего рассмотрения. Как и прежде, объединяемые тасования равносильны перемножаемым перестановкам мест, так что два тасования дают перестановку мест 7Г2, где тг2(а:)-= 2(2л: - 1) - 1 = Ах - 3 (mod 2k - 1). По индукции получаем, что для г тасований ПМ равна ттг , где irT(x) = 2rx- (2Г - 1) (mod 2k - 1). 0 ... 65 66 67 68 69 70 71 ... 117
|
