Разделы 
Дополнительно
Задача по математике - 3600
2019-06-12 
На клетчатой бумаге нарисован прямоугольник $ABCD$, стороны которого лежат на линиях сетки, причем $AD$ в $k$ раз больше $AB$ ($k$ - целое число). Рассматриваются всевозможные пути, проходящие по линиям сетки и кратчайшим образом ведущие из $A$ в $C$. Докажите, что среди этих путей таких, в которых первое звено лежит на $AD$, в $k$ раз больше, чем таких, в которых первое звено лежит на $AB$.
Решение:
Пусть дан прямоугольник $ABCD$ на клетчатой бумаге размерами $m \times n$ клеток (рис.). Обозначим количества кратчайших путей, ведущих из вершин $B_1, D_1, B_2, D_2$ и $A_2$ в $C$ по линиям сетки, через $b_1, d_1, b_2, d_2$ и $a_2$ соответственно. Утверждение задачи состоит в том, что $\frac{d_1}{b_1} = \frac{n}{m}$. Докажем его индукцией по $m + n$, причем сразу для любого, не обязательно целого, отношения $\frac{n}{m} = k$. Начало индукции ($m = 1$ или $n = 1$) очевидно. Будем считать, что $m > 1, n > 1$. По предположению индукции, примененному к прямоугольникам меньших размеров $(m - 1) \times n$ и $m \times (n - 1)$,
$\frac{a_2}{b_2} = \frac{n}{m-1}$ и $\frac{d_2}{a_2} = \frac{n-1}{m}$.
Поэтому
$\frac{d_1}{b_1} = \frac {d_2 + a_2}{b_2 + a_2} = \frac {d_2/a_2 + 1}{b_2/a_2 + 1} = \frac { \frac{n-1}{m} + 1}{ \frac{m-1}{n} + 1} = \frac{n}{m}$.
По существу в решении этой задачи доказаны равенства
$C_{m+n-1}^{m-1} = n C_{m+n-1}^m$ (в нашей задаче $n = km$).
Зная формулу для чисел $C_n^m$, их нетрудно проверить; но можно, наоборот, использовать эти равенства для вывода общей формулы для «чисел сочетания» $C_n^m$.
На клетчатой бумаге нарисован прямоугольник $ABCD$, стороны которого лежат на линиях сетки, причем $AD$ в $k$ раз больше $AB$ ($k$ - целое число). Рассматриваются всевозможные пути, проходящие по линиям сетки и кратчайшим образом ведущие из $A$ в $C$. Докажите, что среди этих путей таких, в которых первое звено лежит на $AD$, в $k$ раз больше, чем таких, в которых первое звено лежит на $AB$.
Решение:
Пусть дан прямоугольник $ABCD$ на клетчатой бумаге размерами $m \times n$ клеток (рис.). Обозначим количества кратчайших путей, ведущих из вершин $B_1, D_1, B_2, D_2$ и $A_2$ в $C$ по линиям сетки, через $b_1, d_1, b_2, d_2$ и $a_2$ соответственно. Утверждение задачи состоит в том, что $\frac{d_1}{b_1} = \frac{n}{m}$. Докажем его индукцией по $m + n$, причем сразу для любого, не обязательно целого, отношения $\frac{n}{m} = k$. Начало индукции ($m = 1$ или $n = 1$) очевидно. Будем считать, что $m > 1, n > 1$. По предположению индукции, примененному к прямоугольникам меньших размеров $(m - 1) \times n$ и $m \times (n - 1)$,
$\frac{a_2}{b_2} = \frac{n}{m-1}$ и $\frac{d_2}{a_2} = \frac{n-1}{m}$.
Поэтому
$\frac{d_1}{b_1} = \frac {d_2 + a_2}{b_2 + a_2} = \frac {d_2/a_2 + 1}{b_2/a_2 + 1} = \frac { \frac{n-1}{m} + 1}{ \frac{m-1}{n} + 1} = \frac{n}{m}$.
По существу в решении этой задачи доказаны равенства
$C_{m+n-1}^{m-1} = n C_{m+n-1}^m$ (в нашей задаче $n = km$).
Зная формулу для чисел $C_n^m$, их нетрудно проверить; но можно, наоборот, использовать эти равенства для вывода общей формулы для «чисел сочетания» $C_n^m$.
