Loading [MathJax]/extensions/TeX/mathchoice.js

Математикадан республикалық олимпиада, 2012-2013 оқу жылы, 10 сынып


Екі тасбақа бір уақытта координатасы (0,0) нүктеден шығып, әр жүрісте бір уақытта бір бүтін координатаға оңға немесе жоғары қарай жүреді (яғни (x,y) нүктесінен (x+1,y) немесе (x,y+1) нүктесіне). Егер тасбақалар соңғы рет (0,0) нүктесінде кездескен болса, олар (n,n) нүктесіне қанша әдіспен жете алады? ( Д. Елиусизов )
посмотреть в олимпиаде

Комментарий/решение:

  7
3 года назад #

Решение: Рассмотрим любые два путя из (0,0) в (n,n).

Один из них будет начинаться с и заканчиваться ,

а другой будет начинаться с и заканчиваться .

То есть это два путя вида (1,0)(n,n1) и (0,1)(n1,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 класса)

  1
3 года назад #

ASDF, можете если не сложно, прояснить, что означает запись вида \dbinom{a}{b}^c

  6
3 года назад #

\dbinom{a}{b}=C_{a}^{b}, а c это просто возведение в степень.