Лесная дача

*

Категория: 
Сложность: 

На рисунке изображена лесная дача, разделённая просеками на квадратные кварталы:

Пунктирной линией обозначен один из путей по просекам от точки A до точки B. Сколько всего существует различных путей такой же длины по просекам от точки A до точки B ?

Подсказка

Это задача эквивалентна задаче о нахождении числа восьмибуквенных последовательностей определённого вида.

Решение

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

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

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

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

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

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

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

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




Комментарии

дофига)

8-12-12edy spune: am downloadat placa video de pe saitu de mai susu spus de tocilau ii dau sa se instaleze se instaleaza si la jumate im ida erare asa :setup was unable to fidomncponents that can be installed on your current of software configuration .Please make sure your have the reguired hardware or software ce inseamna asta ma ajutati va rog +37V-a ajutat acest raspuns?

Добавить комментарий

Plain text

  • Запрещены тэги HTML.
  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Строки и параграфы переносятся автоматически.
Type the characters you see in this picture. (verify using audio)
Type the characters you see in the picture above; if you can't read them, submit the form and a new image will be generated. Not case sensitive.