Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

ММ60

Конкурсная задача ММ60 (12 баллов)

Триша Тройкин, Петя Пятаков и Сёма Семак пытаются сконструировать собственный генератор псевдослучайных чисел. Для этого они взяли натуральные числа a и m (одни и те же у всех троих) и выстраивают последовательность по правилу:

xn+1 = xna (mod m).

Начав с некоторого x1, Триша посчитал x2, x3 и x4. Но x4 оказалось равно x1. Тогда он взял другое (не встречавшееся ранее) число в качестве x1. Но последовательность опять зациклилась на третьем шаге. Треья попытка привела Тришу к тому же результату.

Петя совершил пять попыток подобрать x1. Но всякий раз получал новые циклы длины 5. Наиболее упорным оказался Сёма. Он совершил семь попыток. И получил семь циклов длины 7.

При каком наименьшем m могла возникнуть такая ситуация?

Решение

… можно посмотреть здесь.

Ответ: n = 4851

Обсуждение

Оба конкурсанта, приславших свои решения этой задачи, не нашли наименьшего подходящего m. Не смог сделать этого и ведущий Марафона, предложивший задачу. Я ошибочно считал наименьшим m = 6699. Этот же вариант ответа был и у Владислава Франка. И лишь после подведения итогов шестого тура Марафона, в который входила задача № 60, Барух Зив указал мне на мою оплошность.

Приведенное решение не отталкивается напрямую от системы сравнений
xa3 == x (mod m)
ya5 == y (mod m)
za7 == z (mod m)},
продиктованной ситуацией именно этой задачи, а претендует на некоторую универсальность.
Его очевидным образом можно приспособить для моделирования любых конечных унаров, в том числе, содержащих «хвосты» любой «длины» и «ветвистости». Например, глубина (расстояние до цикла) элемента b в принятых ранее обозначениях определяется как минимум целых неотрицательных h таких, что bi + hai >= mi для всех i.

Чуть подробнее про общую задачу можно прочитать здесь

Награды

За решение этой задачи Владислав Франк получает 12 призовых баллов. Виктор Филимоненков (найденное им m - существенно больше) получает 10 баллов.

Эстетическая оценка задачи - 4 балла —-

 

 


Страница: [[marathon:problem_60]]

marathon/problem_60.txt · Последние изменения: 2018/11/30 05:45 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006