Pull to refresh

Comments 7

Доказательство свойства номер 3 можно упростить. Надо просто понять, что в обоих играх победа при использовании базовой стратегии случается при выполнении одного и того же условия (максимальная длина цикла в «коробочной перестановке» не превышает 50). Все, свойство доказано — и вовсе не обязательно находить взаимно-однозначное соответствие между множествами A и B.
Если перестановка (i1, i2, ..., i100), описывающая как разложены жетоны по коробкам (в первой коробке лежит жетон с номером i1, во второй — с номером i2, и т.д., в сотой — с номером i100) содержит цикл длины больше 50, то команда, играющая в первоначальную игру и следующая базовой стратегии, проиграет. В то же время команда, играющая в новую игру, при этом же расположении жетонов по коробкам выиграет всё с той же вероятностью около 31,2%.

Победа или проигрыш команды, играющей в новую игру, зависит от того, как выглядит другая перестановка, полученная путём записи номеров обнаруженных участниками жетонов в том порядке, в котором они их находили.

Множество таких перестановок, появление которых означает успешное прохождение командой нового испытания, обозначено как A. Число элементов в этом множестве в точности совпадает с числом перестановок, не содержащих циклов длины больше 50 (множество таких перестановок обозначено как B). Чтобы это показать построено взаимно-однозначное отображение из A в B.

То есть победа в обеих играх, на мой взгляд, не случается при выполнении одного и того же условия — отсутствия в «коробочной перестановке» цикла длины больше 50.

Доказательство свойства 3, скорее всего, можно упростить, только поясните свою идею.
Вы почему-то считаете вторую перестановку случайной и независимой от первой — а это не так. Между ними есть взаимно однозначное соответствие, обусловленное этой самой базовой стратегией.
Команда, которая играет в новую игру, пройдет все те же самые циклы, что и команда, играющая в старую игру при том же раскладе. Единственное отличие — в старой игре каждый цикл будет пройден столько раз, сколько в нем коробок — в новой же игре каждый цикл будет пройден всего один раз. Но сами циклы будут теми же самыми — и их максимальная длина от смены игры также не изменится.
Это верно, если команды, играющие как в первоначальную, так и в новую игру используют одну и ту же стратегию.

Я считаю вторую перестановку случайной и независимой от первой именно потому, что не фиксирую стратегию, которой пользуется команда, играющая в новую игру. С другой стороны, что мешает нам зафиксировать её? Ведь по свойству 2 вероятность победы в новую игру не зависит от алгоритма действий участников.

Таким образом, мы действительно можем условиться, что новое испытание команда проходит, используя базовую стратегию. Тогда очевидно, что условие выигрыша как в первоначальную, так и во вторую игру одно и тоже — как вы и сказали. Доказательство действительно можно упростить, спасибо!
Насколько я понял, Вы считаете, что команда выигрывает только в случае, если случайная перестановка не содержит циклов длины большей половины количества коробок.
Если это так, то это неверный посыл. Смотрите, вот цикл длины 6 в котором команда выигрывает:

(3, 4, 5, 6, 1, 2)
Сорри, я туплю. Начальная точка обеспечивает всё что нужно. Пожалуйста игнорируйте мой пост выше.
Sign up to leave a comment.

Articles