Заказ по олимпиадной математике: пароль без пересечений
Ваня придумывает число из неповторяющихся цифр без нулей – пароль для своего телефона. Пароль работает так: если, не отрывая палец от экрана, последовательно соединить отрезками точки, соответствующие цифрам пароля, телефон разблокируется. При этом телефон не позволяет соединять отрезком две точки, между которыми есть третья: если Ваня соединит, например, 1 и 3, телефон "подумает", что Ваня вводит 1-2-3.
Ваня хочет, чтобы при вводе пароля линия движения пальца не пересекала сама себя. А ещё чтобы перестановкой цифр пароля ни в каком порядке, кроме обратного, нельзя было получить другую такую линию. Например, пароль 1263 Ване не нравится, так как линия 6-3-2-1 другая, но тоже не имеет самопересечений.
Ваня придумал пароль 723 (см. рис.). Эти три цифры — 2, 3 и 7 — действительно никакой другой линией соединить нельзя. Жаль только, что пароль такой короткий.
Помогите Ване придумать пароль подлиннее. В ответе напишите сам пароль и нарисуйте ту единственную линию, которую можно получить из этих цифр.

Показать ответ
Например, 12769. См. рисунок.

Разобрать решение
Пароль 12769 удовлетворяет Ваниным требованиям. Посмотрим, как можно соединить без самопересечений его цифры. Цифру 7 с какой-то цифрой соединить надо, это может быть либо 2, либо 6. Пусть, например, мы провели отрезок 7-6. Теперь 9 можно соединить только с 6. Далее неизбежно надо провести отрезки 7-2 и 2-1, и мы получаем линию, изображённую на рисунке. Если бы мы сначала вместо 7-6 провели 7-2, линия получилась бы та же самая. Таким образом, эта линия единственна. Комментарий. Интересно, что устраивающий Ваню пароль из четырёх цифр придумать невозможно. Не существует и пароля из шести и более цифр. Пятизначных паролей возможно восемь: 12769, 96721, 14389, 98341, 32947, 74923, 78163, 36187. Впрочем, линии для всех восьми паролей одной и той же формы, а отличаются только поворотом, симметрией или направлением вычерчивания.
Обсуждение
0Комментариев пока нет.