6. Петя считает все пути из левого нижнего узла клетчатого квадрата 10 × 10 в правый верхний, идущие по линиям сетки вправо или вверх и не поднимающиеся выше главной диагонали. Его друг Вася расставляет в прямоугольнике 2 × 10 числа от 1 до 20 так, чтобы в каждой строке и в каждом столбце числа шли по возрастанию. У кого количество способов получилось больше? Выберите ответ: «Пети», «Васи» или «Поровну».

Путь Пети содержит 10 шагов вправо и 10 шагов вверх; условие о диагонали задаёт пути Каталана. Их число равно \(C_{10}=\frac{1}{11}\binom{20}{10}=16796\).

Расстановки Васи — это таблицы формы 2 × 10, в которых числа возрастают слева направо и сверху вниз. По формуле крюков их число равно \(\frac{20!}{\prod_{j=1}^{10}(11-j)(12-j)}=16796\); это также число Каталана \(C_{10}\).

Число способов одинаково.

Ответ: поровну.