Условие
Найдите наибольшее шестизначное число, кратное 5, любые две соседние цифры которого отличаются на 1.
Подсказка
Соседние цифры отличаются на 1 — как при этом чередуется их чётность?
За k шагов цифра может измениться не больше чем на k: сможете ли вы дойти от первой цифры до последней?
Выбирайте цифры слева направо — каждый раз наибольшую из возможных.
Показать ответ
898765
Пошаговое решение
- Разбираемся с окончанием
Число делится на 5, когда последняя цифра 0 или 5. Значит, на последнем (шестом) месте стоит 0 или 5.
- Замечаем чередование чётности
Соседние цифры отличаются на 1, поэтому из двух соседних цифр одна чётная, а другая нечётная: на 1-м, 3-м и 5-м местах стоят цифры одной чётности, на 2-м, 4-м и 6-м — другой. Кроме того, за каждый шаг вправо цифра меняется ровно на 1, поэтому цифры, между которыми k шагов (например, 1-я и 6-я — пять шагов), отличаются не больше чем на k.
- Выбираем первую цифру
Попробуем первую цифру 9. Она нечётная, тогда на шестом месте стоит чётная цифра, то есть 0. Но от 9 до 0 за пять шагов не дойти: цифра уменьшится не больше чем на 5. Значит, первая цифра не 9. Возьмём 8: она чётная, на шестом месте тогда нечётная цифра 5, и от 8 до 5 за пять шагов дойти можно.
- Выбираем остальные цифры слева направо
Каждую следующую цифру берём как можно большей, следя, чтобы до пятёрки на шестом месте можно было дойти. Второе место: 9 (от 9 до 5 за четыре шага дойти можно). Третье: 8 — единственная цифра, отличающаяся от 9 на 1. Четвёртое: 9 или 7; от 9 до 5 за два шага не дойти (9−5=4>2), поэтому 7. Пятое: 8 или 6; от 8 до 5 за один шаг не дойти, поэтому 6. Шестое: 5. Получаем 898765.
- Проверяем
Соседние цифры: |8−9|=1, |9−8|=1, |8−7|=1, |7−6|=1, |6−5|=1. 898765:5=179753 — число кратно 5.
Ответ: 898765