Найди все пути. Уровень 2. Дима и Катя живут в городе, где все улицы образуют квадраты. Сколькими разными способами Дима может попасть к Кате в гости, если он всегда выбирает дорогу вправо или вверх?

Решение:

Эта задача решается с помощью комбинаторики. Представим город в виде сетки. Диме нужно пройти от одной точки до другой, двигаясь только вправо или вверх. Для простоты будем считать, что Дима начинает в нижнем левом углу, а Катя — в верхнем правом. Пусть для задачи Дима проходит 4 шага вправо и 4 шага вверх, чтобы попасть к Кате.

1. Для первого случая (картинка 1):

Диме нужно пройти 5 шагов вправо и 1 шаг вверх. Общее количество шагов — 6. Количество способов равно количеству способов выбрать, на каких 5 шагах из 6 он пойдет вправо (или на каком 1 шаге он пойдет вверх).

Это можно рассчитать по формуле сочетаний: C(n, k) = n! / (k! * (n-k)!)

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

C(6, 5) = 6! / (5! * (6-5)!) = 6! / (5! * 1!) = (6 * 5!) / (5! * 1) = 6

2. Для второго случая (картинка 2):

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

C(4, 2) = 4! / (2! * (4-2)!) = 4! / (2! * 2!) = (4 * 3 * 2 * 1) / ((2 * 1) * (2 * 1)) = 24 / (2 * 2) = 24 / 4 = 6

Ответ: 1) 6 способами, 2) 6 способами.