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

Question 1

Задача Задача №1786554

А

Аноним

09 октября 2024 15:26 · публичный вопрос

А

Аноним 09 октября 2024 15:26

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

Answer

Давайте разберем задачи Петя и Васи по порядку, чтобы понять, у кого из них больше способов.

Задача Пети: Петя считает количество путей из левого нижнего узла клетчатого квадрата 10 на 10 в правый верхний узел, при условии, что он может двигаться только вправо и вверх, и не поднимается выше главной диагонали.

Для нахождения количества таких путей можно использовать комбинаторный подход. Путь от точки (0, 0) до точки (10, 10) включает 10 шагов вправо и 10 шагов вверх, всего 20 шагов. Однако, чтобы не подниматься выше главной диагонали, потребуется считать только такие маршруты, которые следуют определенным правилам.

Количество таких путей можно найти с помощью чисел Каталана. Формула для n-го числа Каталана выглядит следующим образом: \[ C_n = \frac{1}{n+1} \binom{2n}{n} \] В нашем случае \( n = 10 \). Подставляем в формулу: \[ C_{10} = \frac{1}{10+1} \binom{20}{10} = \frac{1}{11} \cdot \frac{20!}{10!10!} \]

Вычислим это значение: \[ C_{10} = \frac{1}{11} \cdot \frac{20 \times 19 \times 18 \times 17 \times 16 \times 15 \times 14 \times 13 \times 12}{10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1} = \frac{14307150}{11} = 13037895. \]

Задача Васи: Вася расставляет числа от 1 до 20 в прямоугольнике 2 на 10 так, чтобы в каждой строке и в каждом столбце числа шли по возрастанию. Это аналогично задаче о комбинациях. Для каждой строки мы можем выбрать по 10 чисел из 20.

Количество способов сделать это можно рассчитать с помощью биномиальных коэффициентов: \[ \text{Количество способов} = \binom{20}{10}. \] Биномиальный коэффициент будет равен: \[ \binom{20}{10} = \frac{20!}{10!10!} = 184756. \]

Теперь сравним количества:

У Пети: \( C_{10} = 16796 \)
У Васи: \( \binom{20}{10} = 184756 \)

Таким образом, количество способов у Васи значительно больше, чем у Пети.

В итоге можно сказать, что больше способов получилось у Васи!

Question 2

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

Answer

Давайте разберем задачи Петя и Васи по порядку, чтобы понять, у кого из них больше способов. **Задача Пети:** Петя считает количество путей из левого нижнего узла клетчатого квадрата 10 на 10 в правый верхний узел, при условии, что он может двигаться только вправо и вверх, и не поднимается выше главной диагонали. Для нахождения количества таких путей можно использовать комбинаторный подход. Путь от точки (0, 0) до точки (10, 10) включает 10 шагов вправо и 10 шагов вверх, всего 20 шагов. Однако, чтобы не подниматься выше главной диагонали, потребуется считать только такие маршруты, которые следуют определенным правилам. Количество таких путей можно найти с помощью чисел Каталана. Формула для n-го числа Каталана выглядит следующим образом: \[ C_n = \frac{1}{n+1} \binom{2n}{n} \] В нашем случае \( n = 10 \). Подставляем в формулу: \[ C_{10} = \frac{1}{10+1} \binom{20}{10} = \frac{1}{11} \cdot \frac{20!}{10!10!} \] Вычислим это значение: \[ C_{10} = \frac{1}{11} \cdot \frac{20 \times 19 \times 18 \times 17 \times 16 \times 15 \times 14 \times 13 \times 12}{10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1} = \frac{14307150}{11} = 13037895. \] **Задача Васи:** Вася расставляет числа от 1 до 20 в прямоугольнике 2 на 10 так, чтобы в каждой строке и в каждом столбце числа шли по возрастанию. Это аналогично задаче о комбинациях. Для каждой строки мы можем выбрать по 10 чисел из 20. Количество способов сделать это можно рассчитать с помощью биномиальных коэффициентов: \[ \text{Количество способов} = \binom{20}{10}. \] Биномиальный коэффициент будет равен: \[ \binom{20}{10} = \frac{20!}{10!10!} = 184756. \] Теперь сравним количества: - У Пети: \( C_{10} = 16796 \) - У Васи: \( \binom{20}{10} = 184756 \) Таким образом, количество способов у Васи значительно больше, чем у Пети. В итоге можно сказать, что больше способов получилось у Васи!