** Идеи решений **


Задание А. "ПИК-Лото"
Эта задача для частных случаев хорошо известна. Так, например, для n = 3, k = 2 решение описано в книге А. Л. Брудно и Л. И. Каплана “Московские олимпиады по программированию” (М., Наука, 1990, с. 188-191). В этом издании показано (и это легко проверить экспериментально!), что, например, прогноз 100 сбывается в среднем втрое чаще (то есть, встречается раньше в последовательности шариков), чем 001, а шансы для прогноза 011 вдвое ниже, чем у прогноза 001 (здесь нумерация цветов шариков ведется от нуля). Таким образом, возможное решение могло быть основано на проведении эксперимента для определения лучшего ответа на прогноз соперника или на аккуратном теоретическом исследовании задачи. Образцом такого исследования может являться книга известных ученых Р. Грэхема, Д. Кнута и О. Паташника “Конкретная математика” (М., Мир, 1998, с.438-448).


Задание B. "Шифровка"
Один из вариантов решения сводится к последовательной подстановке кода пробела на позиции с 1 по 32 в массиве символов. Предварительно следует несколько раз выбирать случайные массивы замен, остановившись на том из них, где количество очков максимально. Тогда, анализируя количество угаданных букв, можно точно определить, какие именно буквы угаданы. Далее, не трогая угаданные буквы, повторяем эту же процедуру до тех пор, пока результат не станет равным 33. Понятно, что пробелом мы тестируем только те буквы, про которые еще ничего точно не знаем.
Когда все буквы угаданы, то, получая очередную букву, передаем массив замен без изменений.
Лучшие программы дополнительно учитывали частотное распределение букв и их сочетаний для русского языка, а также контролировали недопустимые их комбинации. Например, в русском языке нет предлога "Щ" или сочетания "УЬ". Во всяком случае, среди решений попадались такие, где в массивах констант заданы сотни (а может быть и тысячи) буквосочетаний.


Задание C. "Роботы"
Эта задача была популярной в шестидесятые годы. В классическом варианте она называется задачей о синхронизации цепи стрелков. Стрелки должны произвести одновременно залп. Командует стрелками генерал, который вскрывает секретный пакет. По этой задаче можно порекомендовать книгу М. Минского “Вычисления и автоматы” (М., Мир, 1971, с.46-48., с.335).
Основная идея заключается в организации посылки по цепи двух видов сигналов, распространяющихся с разной скоростью. Например, если один сигнал распространяется втрое быстрее другого, то отразившись от правого края, он встретится с другим на середине. Далее, следует организовать аналогичные сигналы внутри каждой из половинок. Доказано, что число тактов не может быть меньше, чем 2*n-2.
На самом деле мы сознательно изменили задачу, введя перечень ограничений. В этом случае, по-видимому, можно пытаться создать такие управляющие таблицы для синхронизации всех роботов, которые при заданных ограничениях на количество роботов, порождают более быстрое решение, нежели универсальное.
Замена стрелков на роботов была связана с тем, чтобы не дать заметного преимущества тем, кто будет искать решение в Интернете. Интересно, что жюри позже проверило, действительно ли такой поиск был бы продуктивным. Оказалось, что сочетание "синхронизация цепи стрелков" встречается в сети несколько раз. В одном из случаев это оказалась программа госэкзамена по специальности 220100, а в остальных вариантах все пути вели к публикации в журнале "Мир ПК" (Любченко В.С. Задача Майхилла для Microsoft Visual C++ 5.0 (о синхронизации процессов в среде Windows) //Мир ПК. 2000. N2). Автор публикации, рассматривая эту задачу, предлагает решение, число состояний в котором фактически зависит от длины цепи стрелков.
Два рыбинских участника нашли универсальные решения, одно из которых можно взять здесь.

В. Пинаев
г. Рыбинск