Исполнитель РОБОТ ходит по клеткам бесконечной вертикальной клетчатой доски,
переходя по одной из команд ВВЕРХ (1), ВНИЗ (2), ВПРАВО (3), ВЛЕВО (4) в
соседнюю клетку в указанном направлении. РОБОТ выполнил следующую программу:
3322331111444.
Укажите наименьшее число команд в программе, приводящей РОБОТа из той же
начальной точки в ту же конечную. Сколько всего таких оптимальных маршрутов
возможно?

Задача связана с оптимизацией пути робота на бесконечной вертикальной клетчатой доске. Рассмотрим, что робот выполняет программу, состоящую из последовательности команд: 3322331111444. Задача состоит в том, чтобы найти наименьшее количество команд, которое приведет робота из той же начальной точки в ту же конечную, а также определить, сколько таких оптимальных маршрутов существует.

Разбор программы

Программа состоит из команд:

• 3 (ВПРАВО) — перемещение вправо.
• 2 (ВНИЗ) — перемещение вниз.
• 1 (ВВЕРХ) — перемещение вверх.
• 4 (ВЛЕВО) — перемещение влево.

Теперь давайте проанализируем, какие изменения происходят в координатах робота.

Предположим, что начальная позиция робота — это точка $(0, 0)$ на клетчатой доске. Каждое движение будет изменять его положение следующим образом:

• 3 (ВПРАВО): увеличивает $x$ на 1.
• 2 (ВНИЗ): уменьшает $y$ на 1.
• 1 (ВВЕРХ): увеличивает $y$ на 1.
• 4 (ВЛЕВО): уменьшает $x$ на 1.

Теперь рассмотрим, как робот перемещается по клетчатой доске, выполняя программу 3322331111444:

1. 3 — вправо: $x \to x + 1$.
2. 3 — вправо: $x \to x + 1$.
3. 2 — вниз: $y \to y - 1$.
4. 2 — вниз: $y \to y - 1$.
5. 3 — вправо: $x \to x + 1$.
6. 3 — вправо: $x \to x + 1$.
7. 1 — вверх: $y \to y + 1$.
8. 1 — вверх: $y \to y + 1$.
9. 1 — вверх: $y \to y + 1$.
10. 1 — вверх: $y \to y + 1$.
11. 4 — влево: $x \to x - 1$.
12. 4 — влево: $x \to x - 1$.

Теперь посчитаем итоговые изменения в координатах:

• Вдоль оси $x$ робот перемещался 4 раза вправо (по команде 3) и 2 раза влево (по команде 4). Это дает итоговое изменение: $$\Delta x = 4 - 2 = 2.$$
• Вдоль оси $y$ робот перемещался 4 раза вверх (по команде 1) и 2 раза вниз (по команде 2). Это дает итоговое изменение: $$\Delta y = 4 - 2 = 2.$$

Итак, итоговое положение робота после выполнения всей программы: $(x, y) = (2, 2)$. То есть робот пришел в точку $(2, 2)$ из начальной точки $(0, 0)$.

Оптимизация пути

Чтобы минимизировать количество команд, нужно учесть, что робот должен двигаться на 2 клетки вправо и 2 клетки вверх. Поэтому минимальный путь будет содержать только эти два типа команд:

• 2 команды вправо (для перемещения на 2 клетки вправо),
• 2 команды вверх (для перемещения на 2 клетки вверх).

Таким образом, наименьшее количество команд для достижения точки $(2, 2)$ из $(0, 0)$ равно 4. Это оптимальный путь, состоящий из 2 команд "вправо" и 2 команд "вверх".

Количество оптимальных маршрутов

Для того чтобы посчитать количество возможных оптимальных маршрутов, нужно выяснить, сколько разных способов можно расположить 2 команды "вправо" и 2 команды "вверх" в последовательности из 4 команд.

Количество таких способов — это число сочетаний, которое вычисляется по формуле:

где $n$ — общее количество команд (в нашем случае 4), а $k$ — количество команд "вправо" (или "вверх", так как их количество одинаково).

Таким образом, количество возможных маршрутов:

Ответ

Наименьшее количество команд в программе, приводящей робота из начальной точки в конечную, равно 4. Всего существует 6 различных оптимальных маршрутов.