ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66524
Тема:    [ Примеры и контрпримеры. Конструкции ]
Сложность: 4
Классы: 5,6,7
В корзину
Прислать комментарий

Условие

Ваня придумывает число из неповторяющихся цифр без нулей – пароль для своего телефона. Пароль работает так: если, не отрывая палец от экрана, последовательно соединить отрезками точки, соответствующие цифрам пароля, телефон разблокируется. При этом телефон не позволяет соединять отрезком две точки, между которыми есть третья: если Ваня соединит, например, 1 и 3, телефон "подумает", что Ваня вводит 1-2-3.

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

Помогите Ване придумать пароль подлиннее. В ответе напишите сам пароль и нарисуйте ту единственную линию, которую можно получить из этих цифр.


Решение

Пароль 12769 удовлетворяет Ваниным требованиям. Посмотрим, как можно соединить без самопересечений его цифры. Цифру 7 с какой-то цифрой соединить надо, это может быть либо 2, либо 6. Пусть, например, мы провели отрезок 7-6. Теперь 9 можно соединить только с 6. Далее неизбежно надо провести отрезки 7-2 и 2-1, и мы получаем линию, изображённую на рисунке. Если бы мы сначала вместо 7-6 провели 7-2, линия получилась бы та же самая. Таким образом, эта линия единственна.

Комментарий. Интересно, что устраивающий Ваню пароль из четырёх цифр придумать невозможно. Не существует и пароля из шести и более цифр. Пятизначных паролей возможно восемь: 12769, 96721, 14389, 98341, 32947, 74923, 78163, 36187. Впрочем, линии для всех восьми паролей одной и той же формы, а отличаются только поворотом, симметрией или направлением вычерчивания.

Ответ

Например, 12769. См. рисунок.

Источники и прецеденты использования

олимпиада
Название Математический праздник
год
Год 2020
класс
Класс 6
задача
Номер 6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .