Взмолился Иван-царевич: «Отдай ты мне, Кощей Бессмертный, Василису Прекрасную». Отвечал Кощей: «Хорошо, Иван-царевич. Но прежде помоги мне открыть мой сундук с золотом. Запер я его на ключ, ключ положил в сейф, а пароль от сейфа забыл. Помню только, что пароль - это наибольшее натуральное число, в записи которого нет цифр 0 и 5, все цифры различны, а произведение любых двух рядом стоящих цифр делится на 3. Помогите Ивану-царевичу вызволить Василису Прекрасную - запишите верный пароль от сейфа.

Для решения задачи составим число, удовлетворяющее следующим условиям: 1. В записи числа нет цифр 0 и 5. 2. Все цифры различны. 3. Произведение любых двух соседних цифр делится на 3. Чтобы произведение двух цифр делилось на 3, хотя бы одна из них должна быть кратна 3. Цифры, кратные 3 (без учета 0), это 3, 6 и 9. Остальные цифры — 1, 2, 4, 7, 8 — не делятся на 3. Значит, между любыми двумя "некратными" цифрами должна стоять "кратная" цифра. Так как мы ищем наибольшее натуральное число, нужно использовать как можно больше цифр. Доступные цифры: {1, 2, 3, 4, 6, 7, 8, 9}. Всего 8 цифр. "Некратные" цифры (5 штук): 1, 2, 4, 7, 8. "Кратные" цифры (3 штуки): 3, 6, 9. Чтобы расположить 5 некратных цифр, нам нужно как минимум 4 кратные цифры между ними (например: N K N K N K N K N). Но у нас всего 3 кратные цифры. Значит, максимально возможная длина числа ограничена. Мы можем чередовать максимум 3 некратные и 3 кратные цифры. Максимальное количество цифр — 6 (например: K N K N K N или N K N K N K). Поскольку мы хотим наибольшее число, первой цифрой должна быть самая большая из доступных (9). Схема для самого длинного числа (6 цифр): 9 - (некратная) - 6 - (некратная) - 3 - (некратная). Чтобы число было наибольшим, на позиции "некратных" ставим самые большие оставшиеся цифры: 8, 7, 4. Получаем число: 986734. Проверим условие: произведения соседних пар (9*8=72, 8*6=48, 6*7=42, 7*3=21, 3*4=12) делятся на 3. Все условия соблюдены. Ответ: 986734