Processing math: 54%

Республиканская олимпиада по математике, 2013 год, 10 класс


Две черепахи одновременно выходят из точки с координатами (0,0) и на каждом шагу одновременно переходят на одну из целочисленных координат вверх или вправо (то есть из (x,y) в (x+1,y) или в (x,y+1)). Сколько существует способов им добраться до точки (n,n), если последний раз они встречались только в точке (0,0)? ( Д. Елиусизов )
посмотреть в олимпиаде

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

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

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

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

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

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

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

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

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

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