Question

Решите пожалуйста , желательно с чертежами и описыванием действий в решении

Answer 1

Ответ:

300 способов проезда

Объяснение:

Для начала заметим, что каждое движение по линии сетки изменяет лишь одну из координат, причем ровно на 1 единицу. Значит, оптимальный путь не может состоять менее чем из $6-0=6$ движений по горизонтали и  $6-0=6$ движений по вертикали. При этом, нетрудно заметить, путь $(0;0)\to(1;0)\to(2;0)\to...\to(6;0)\to(6;1)\to(6;2)\to...\to(6;6)$ состоит ровно из такого числа перемещений. А значит и любой кратчайший путь содержит по 6 движений по вертикали и 6 движений по горизонтали, причем каждое из них (т.к. за одно перемещение координата меняется ровно на 1 единицу) должно увеличивать соответствующую координату.
Окончательно, каждый кратчайший путь состоит из 6 движений вверх и 6 движений направо.

-------------------------------------------------------------------------------

Рассмотрим следующую задачу: найти $G_n$ - число кратчайших путей из $(0;0)$ в $(n;n)$ по линиям сетки.
Рассуждая аналогично, получим, что каждый кратчайший путь состоит из n движений вверх и n движений направо.

Тогда количество таких путей совпадает с числом бинарных векторов длины $2n$ (общее число движений), у которых число 0 и 1 равно $n$ (по $n$ движений каждого вида), т.е. $G_n=C_{2n}^n=\dfrac{(2n)!}{n!n!}$

-------------------------------------------------------------------------------

Тогда всего путей из А в В $G_6$.

Посчитаем число путей, содержащих точку $(2;2)$. Оно равно произведению числа путей от $(0;0)$ до $(2;2)$ и числа путей от $(2;2)$ до $(6;6)$. Первый множитель равен $G_2$, а второй, как нетрудно заметить, $G_{6-2}=G_4$ (выполним параллельный перенос координатных осей так, чтобы точка  $(2;2)$ превратилась в начало координат. Тогда точка  $(2;2)$ превратится в точку $(4;4)$).
Аналогично число путей, содержащих точку $(4;4)$, равно $G_4*G_{6-4}=G_4*G_2$.
После вычитания их из общего числа путей получим

$G_6-G_2*G_4-G_4*G_2=G_6-2*G_2*G_4$ - но здесь два раза были учтены пути, содержащие и точку  $(2;2)$ , и точку  $(4;4)$, а значит к текущему количеству путей нужно прибавить их число.
Аналогичными рассуждениями их количество равно $G_{2-0}*G_{4-2}*G_{6-4}=G_2^3$.

Окончательно, число способов проезда равно $G_6-2*G_2*G_4+G_2^3=\dfrac{12!}{6!6!}-2*\dfrac{4!}{2!2!}*\dfrac{8!}{4!4!}+\left(\dfrac{4!}{2!2!}\right)^3=\\=\dfrac{12*11*10*9*8*7}{6*5*4*3*2}-\dfrac{8*7*6*5}{2}+6^3=11*3*4*7-8*7*3*5+6^3=\\=924-840+216=300$