Лесная дача

Каждый путь по просекам от точки A до точки B состоит из 4 горизонтальных и 4 вертикальных отрезков единичной длины. Каждому такому пути можно поставить в соответствие «слово», состоящее из 4 букв «Г» (от слова «горизонтальный») и 4 букв «В» (от слова «вертикальный»). Например, пути, приведённому на рисунке, соответствует слово «ГВГВГВГВ».

Ясно, что между всеми такими словами и всеми кратчайшими маршрутами от точки A до точки B существует взаимно однозначное соответствие: каждому пути соответствует какое-то одно слово, и каждому слову соответствует какой-то один путь. Таким образом, задача сводится к определению количества различных слов, составленных из 4 букв «Г» и 4 букв «В». Те, кто хоть немного знаком с комбинаторикой, знают, что это количество равно числу сочетаний из 8 по 4. Для остальных можно привести следующее несложное решение.

Предположим сначала, что все буквы «Г» и все буквы «В» являются различными (их можно обозначить Г₁, Г₂, ..., В₃, В₄). Тогда на первое место в любом восьмибуквенном слове можно поставить любую из 8 имеющихся букв, на второе место — любую из 7 оставшихся букв, и так далее. Всего таких слов будет

8 × 7 × 6 × ... × 3 × 2 × 1 = 40320.

(Произведение всех натуральных чисел от 1 до n называется «n-факториал» и обозначается «n!». Таким образом, последнее выражение может быть записано так: 8! = 40320.)

Однако те слова, которые получаются друг из друга только перестановкой букв «Г», на самом деле одинаковы. Буквы Г₁, Г₂, Г₃ и Г₄ можно переставлять 4! способами (доказательство аналогично приведённому выше: на первое место можно поставить любую из 4 букв «Г», на второе — любую из 3 оставшихся, и так далее). Значит, всё множество из 8! слов разбивается на группы по 4! слов, причём все слова в каждой из этих групп отличаются друг от друга только только перестановками букв «Г». Таким образом, отождествляя слова, отличающиеся лишь перестановкой букв «Г» (но не «В»), мы получим 8! / 4! = 1680 слов.

Далее, отождествляя слова, отличающиеся только перестановкой букв «В», мы получаем 8! / (4! · 4!) = 70 различных слов.

Таким образом, существует лишь 70 различных слов, составленных из 4 букв «Г» и 4 букв «В». Значит, кратчайших путей по просекам от точки A до точки B тоже существует всего 70.