Математикадан республикалық олимпиада, 2012-2013 оқу жылы, 10 сынып
Екі тасбақа бір уақытта координатасы (0,0) нүктеден шығып, әр жүрісте бір уақытта бір бүтін координатаға оңға немесе жоғары қарай жүреді (яғни (x,y) нүктесінен (x+1,y) немесе (x,y+1) нүктесіне). Егер тасбақалар соңғы рет (0,0) нүктесінде кездескен болса, олар (n,n) нүктесіне қанша әдіспен жете алады?
(
Д. Елиусизов
)
посмотреть в олимпиаде
Комментарий/решение:
Решение: Рассмотрим любые два путя из (0,0) в (n,n).
Один из них будет начинаться с ↑ и заканчиваться →,
а другой будет начинаться с → и заканчиваться ↑.
То есть это два путя вида (1,0)⇝(n,n−1) и (0,1)⇝(n−1,n). Таких пар путей у нас \dbinom{2n-2}{n-1}^2.
Найдем количество пар таких пересекающихся путей. Для этого рассмотрим биекцию которая "меняет местами" часть пути начиная с первого пересечения этих путей. По итогу кол-во пар таких пересекающихся путей равно кол-ву пар путей вида (1,0)\rightsquigarrow (n-1,n) и (0,1) \rightsquigarrow (n,n-1). Таких путей \dbinom{2n-2}{n-2}^2.
Откуда ответ \dbinom{2n-2}{n-1}^2-\dbinom{2n-2}{n-2}^2.
(Рисунок присутствует на этой же задаче 11 класса)
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.