Раздел: Документация
0 ... 66 67 68 69 70 71 72 ... 117 Следовательно, если 2r = 1, то 7ГГ каждую карту возвращает в начальное положение, так как тгг(х)~х для всех х. Наоборот, если каждая карта возвращается в начальное положение, то возвращается и карта, находившаяся на 2-м месте, так что 2Г+1 - 2Г + 1 = 2, т.е. 2r = 1. Таким образом, наименьшее число тасований поверх, возвращающее каждую карту в исходное положение, есть наименьшее г, для которого 2r = 1 (mod 2к - 1). Воспользуйтесь доказанным и riffle2a.m (подправленным rifflela.ni), чтобы найти наименьшее число тасований поверх, возвращающих каждую карту в исходное положение, для каждого четного и = 2к от 40 до 52 включительно. 14-2.3. Колоды с нечетным числом карт Если число карт нечетно, скажем 2к + 1, то после деления колоды надвое одна часть содержит к карт, а другая - к + 1 карту. Обе части тасуются внахлест так, что верхняя и нижняя карты части, содержащей к -f 1 карту, становятся верхней и нижней картами объединенной колоды (к + 1 карта «накрывает» к карт). Имеется два варианта: часть с к картами содержит карты со значениями 1,... ,к (тасование внутрь), либо карты со значениями к+2,.., 2к+1 (тасование поверх). Взгляните на рис. 14.1 для случая к =2. Проверьте, что соответствующие перестановки мест задаются выражениями тг(х) = 2х (mod 2к + 1) и 7г(х) = 2х - 1 (mod 2k + 1). (14.4) Переделайте riiflel.m под эти два случая (пусть это будут М-файлы riffle3.mn riffle4.m)H найдите наименьшее число тасований внутрь и поверх, которое возвращает 15 картам их исходный порядок. Заметьте, что вместо rem. га вам лучше применить гетто.т, чтобы исключить случай с нулевым остатком. Покажите, что как для тасований внутрь, так и для тасований поверх, наименьшее число тасований, возвращающих карты в исходное положение, есть наименьшее значение г, для которого 2Т = 1 (mod 2k + 1). Примените rifflela.m, чтобы найти наименьшее число г для колод с нечетным числом карт при и = 2к + 1 от 39 до 51 включительно. 14-2.4- Тасования внахлест и снятия для колод с нечетным числом карт Имеется очень интересное явление, связанное с колодами из нечетного числа карт, которое мы рассмотрим здесь теоретически. Не нужно ничего вычислять, но вы можете написать какой-нибудь иллюстративный М-файл, если, конечно, захотите. Снятие колоды есть циклическая перестановка, т. е. она сохраняет «циклическое» упорядочивание карт, которое получается, если расположить карты по кругу. Например, если с колоды 1, 2, 3, 4, 5 снять 3 карты сверху, то новое упорядочивание по значениям будет иметь вид 4, 5, 1, 2, 3. Если эти числа записаны по кругу, то их порядок будет тот же, что и вначале. В общем случае, для и карт, объясните на примерах, почему снятие с карт сверху дает перестановку мест п - с+ 1,п - с + 2,... ,п- 1,п, 1,2,... ,п - с- 1,п - с. Обозначим эту перестановку через <7С, так что ас(х)=х - с (mod п). Теперь предположим, что и - нечетное и равно 2k + 1. В соответствии с формулами (14.4) идеальное тасование внахлест и карт дается перестановкой мест it, где -к(х) = 2х или 2х - 1 (mod п). Покажите, что в обоих случаях 7Г(7С = 02с ?Г. Здесь мы просто перемножаем перестановки самым обычным образом, так что 7г(сгс(а;)) = <72с(тг(а;)) (modn) для всехх. Покажите, что обе части сравнимы с 2х - 2с по mod п. Объясните, почему отсюда следует, что последовательность тасований, в которой тасования внахлест перемешаны со снятиями, можно заменить последовательностью, в которой сначала идут тасования внахлест, а затем снятия. Более того, вполне понятно, что многократное последовательное снятие колоды равносильно одному снятию. Таким образом, последовательность тасований внахлест и снятий имеет ПМ вида (Т7ГГ7ГГ 1 . . .7Г1, где а - какое-то снятие колоды, a TTj - тасования (внутрь или поверх). Теперь мысленно вернемся к наименьшему числу г, указывающему, сколько тасований и - 2к + 1 карт, например, внутрь нужно сделать, чтобы они вернулись к их исходному порядку (§14.2.3). Предположим, что г тасований внутрь (для этого г) перемежаются с несколькими снятиями колоды. Из сказанного выше следует, что итоговая перестановка мест может быть представлена в виде атгг, 14.3.Циклы Подобно всем другим, перестановки мест, соответствующие тасованиям внахлест, можно разложить на непересекающиеся циклы. Для вас написан М-файл, делающий разложения для четных тасований внутрь: он называется riff lei с. т. Он выводит циклы и их длины. Воспользуйтесь riff lelc.m иизвестным фактом, что порядок перестановки равен НОК длин ее непересекающихся циклов, чтобы проверить результаты, полученные вами для четных чисел от 40 до 52 в §14.2.1. Для каждого четного числа выпишите длины циклов и НОК. Обратите внимание, что 52 карты обладают особым свойством: четное тасование внутрь является единственным циклом. Какое следующее четное число обладает этим свойством? 14.4.Грубые тасования внахлест (быстрые тасования) Ц.Л. Одно быстрое тасование Если только вы не сверхискусны, идеальное тасование внахлест не подвластно вам. Поэтому мы рассмотрим здесь, как можно смоделировать тасование внахлест для обычного человека, которое мы будем называть грубым тасованием внахлест или быстрым тасованием (см. рис. 14.2). Чтобы определиться с понятиями, рассмотрим четное число карт, п = 2к, которые вначале разбиты на две части из где а - снятие колоды. Откуда следует, что сейчас карты циклически упорядочены так же, как и в начале? Покажите, что то же самое справедливо и для тасований поверх. Немного труднее доказать, что то же самое выполняется и для любой смеси (из г) тасований внутрь и поверх, лишь бы их было г. (Набросок доказательства приведен ниже в § 14.5.) Таким образом, тасования внахлест и снятия колоды являются очень неэффективным способомрандомизации колоды с нечетным числом карт: они всегда возвращаются на исходные места после довольно небольшого числа тасований. Кстати, в случае колод с четным числом карт все по-другому. Можно показать, что подходящим выбором последовательности тасований внахлест и снятий колоды можно получить любую из и\ перестановок п = 2к карт, так что тасования внахлест и снятия колоды являются эффективным способом рандомизации колод с четным числом карт. 0 ... 66 67 68 69 70 71 72 ... 117
|
