Question

Сколько существует четырехзначных чисел из цифр 1, 2, 3, 4, делящихся на 9? (некоторые из этих цифр могут отсутствовать, а некоторые повторяться) Декарт стоит в точке (0,0). Он может ходить на единичку вниз, вверх, влево или вправо, но не может повторять свой предыдущий ход. За какое наименьшее количество ходов Декарт может дойти до точки (314, 271)?

Answer 1

1) Если число делится на 9, то его сумма цифр делится на 9.
1134, 1143, 1314, 1341, 1413, 1431, 3411, 3114, 3141,
4113, 4131, 4311 - 12 чисел.
3222, 2322, 2232, 2223 - 4 числа
1224, 1242, 1422, 2124, 2142, 2214, 2241, 2412, 2421,
4122, 4212, 4221 - 12 чисел
Кажется, больше чисел нет. Всего 12+12+4 = 28 чисел.

2) Я уже решал. Наименьший путь составляет 314 + 271 = 585 ходов.
Вот на рисунке несколько путей. Идти нужно только вверх и вправо.

Answer 2

Четырехзначные числа из цифр 1, 2, 3, 4, делящиеся на 9, образуют арифметическую прогрессию с шагом 9. Таким образом, можно составить следующие числа:

1. 1113 2. 1122 3. 1131 4. 1140 5. 1212 6. 1221 7. 1230 8. 1302 9. 1311 10. 1320 11. 1401 12. 1410 13. 2112 14. 2121 15. 2130 16. 2202 17. 2211 18. 2220 19. 2301 20. 2310 21. 3102 22. 3111 23. 3120 24. 3201 25. 3210

Итого, существует 25 четырехзначных чисел из цифр 1, 2, 3, 4, делящихся на 9.

Чтобы найти наименьшее количество ходов, Декарту нужно переместиться из точки (0,0) до точки (314, 271), можно использовать алгоритм поиска в ширину (BFS - breadth-first search).

1. Начальная точка (0,0) помечается как посещенная и добавляется в очередь. 2. Берем первую точку из очереди. 3. Проверяем все 4 возможных направления движения Декарта: вниз, вверх, влево, вправо. 4. Если новая точка находится в пределах допустимого поля и не была посещена ранее, добавляем ее в очередь и помечаем как посещенную. 5. Повторяем шаги 2-4, пока очередь не будет пустой. 6. Когда мы достигаем точки (314, 271), считаем количество шагов.

В данном случае, так как Декарт может ходить только на единичку, каждый его шаг увеличивает одну из координат на 1. То есть, он может перемещаться только вправо или вверх.

Для перемещения из точки (0,0) до точки (314, 271) наименьшее количество шагов будет равно разности между положительными разностями координат, так как нужно сделать столько горизонтальных шагов (вправо), сколько разность абсцисс, и столько вертикальных шагов (вверх), сколько разность ординат.

Разность абсцисс: 314 - 0 = 314 Разность ординат: 271 - 0 = 271

Наименьшее количество шагов: min(314, 271) = 271

Таким образом, наименьшее количество шагов, которые Декарт может сделать, чтобы дойти до точки (314, 271), составляет 271.