=====ММ60=====

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

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

x<sub>n+1</sub> = x<sub>n</sub>a (mod m).

Начав с некоторого x<sub>1</sub>, Триша посчитал x<sub>2</sub>, x<sub>3</sub> и x<sub>4</sub>. Но x<sub>4</sub> оказалось равно x<sub>1</sub>.
Тогда он взял другое (не встречавшееся ранее) число в качестве x<sub>1</sub>. Но последовательность опять зациклилась на третьем шаге. Треья попытка привела Тришу к тому же результату.

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

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


**Решение**

... можно посмотреть {{:marathon:mm60_val.pdf|здесь}}.

Ответ: n = 4851

**Обсуждение**

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

Приведенное решение не отталкивается напрямую от системы сравнений\\
xa<sup>3</sup> == x (mod m)\\
ya<sup>5</sup> == y (mod m)\\
za<sup>7</sup> == z (mod m)},\\
продиктованной ситуацией именно этой задачи, а претендует на некоторую универсальность.\\
Его очевидным образом можно приспособить для моделирования любых конечных унаров, в том числе, содержащих "хвосты" любой "длины" и "ветвистости".
Например, глубина (расстояние до цикла) элемента b в принятых ранее обозначениях определяется как минимум целых неотрицательных h таких, что b<sub>i</sub> + ha<sub>i</sub> >= m<sub>i</sub> для всех i.

Чуть подробнее про общую задачу можно прочитать {{:marathon:unar_repr.pdf|здесь}}

**Награды**

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

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