Решение задач с применением треугольника Паскаля

Олимпиадная задача: Имеется сеть дорог. Из точки, А выходят 2¹⁰⁰⁰. Половина идет по направлению 1, половина — по направлению т. Дойдя до первого перекрестка, каждая группа разделяется: половина идет по направлению 1, половина по направлению т. Такое же разделение происходит на каждом перекрестке. Сколько людей придет в каждый из перекрестков тысячного ряда?

Заметим, прежде всего, что мы пока не знаем, имеет ли задача решение, т. е. может ли движение людей происходить так, как требует условие задачи. Ведь если на какой-то перекресток, на котором предстоит очередное деление людского потока пополам, придет нечетное число людей, то движение застопорится. Следовательно, чтобы задача имела решение, необходимо и достаточно, чтобы в каждый перекресток любого из первых тысячи рядов, от нулевого до девятьсот девяносто девятого, пришло четное число людей. Мы убедимся, что это так, решая задачу.

Начнем с того, что введем обозначения для количества людей, прошедших через каждый перекресток нашей сети дорог. Будем нумеровать перекрестки каждого ряда слева направо, начиная с нулевого; перекрестки n-го ряда, следовательно, будут нумероваться от 0-го до n-го. Число людей, прошедших через k-й перекресток n-го ряда, обозначим H^k_n. Поскольку пока еще неизвестно, имеет ли задача решение, мы не можем быть уверены, что все числа Н^k_n существуют, т. е. что существует каждое из чисел H^k_n при любом n от 0 до 1000 и любом k от 0 до n. Некоторые из них, во всяком случае, существуют. Так, в силу введенных обозначений H⁰₀=2¹⁰⁰⁰

Посмотрим теперь, как связаны между собой числа H^k_n(k=0,1,2…, n) и H^k_n(k=0,1,2,…, n+1).

При условии, что все они существуют. Изучая эту связь, мы сможем затем установить, что все числа H^k_n при 1000 >= n действительно существуют. Рассмотрим n-й и (n+1)-й ряды перекрестков и соединяющие их участки дорог; против каждого перекрестка поставим обозначение соответствующего числа людей.

Количество людей, вышедших из 0-го перекрестка n-го ряда (т.е. Н⁰_n), разделится пополам, и одна половина придет в 0-й перекресток (n+1)-го ряда; поэтому.

Другая половина от Н°n придет в 1-й перекресток (n+1)-го ряда и там соединится с.

половиной людей, вышедших из 1-го перекрестка n-го ряда, т. е. с половиной Н¹_n. Поэтому.

И вообще, количество людей, пришедших на k-й перекресток (n+1)-го ряда, слагается из половины количества людей, вышедших из (k-1)-гo перекрестка n-го ряда. Эта половина равна, А половина количества людей, вышедших из k-гo перекрестка n-го ряда, равна таким образом,.

Но должно выполняться условие.

Наконец, число людей, пришедших на (n+1)-й перекресток (n+1)-го ряда,.

равно половине числа людей, вышедших из n-го перекрестка n-го ряда:

Эти соотношения позволяют установить, что задача действительно имеет решение. В самом деле, из равенств (2)-(4) вытекает, что если при каком-либо фиксированном n все числа n-го ряда: Н⁰_n, Н¹_n,…, Нⁿ_n — существуют и делятся на 2а, то числа (n+1)-го ряда: Н⁰_n+1, Н¹_n+1,…, Нⁿ⁺¹_n+1 — существуют и делятся на а. Поэтому, поскольку все числа 0-го ряда (а их всего одно Н⁰₀) существуют и делятся на 2¹⁰⁰⁰, то все числа 1-го ряда Н⁰₁, Н¹₁, существуют и делятся на 2⁹⁹⁹; все числа 2-го ряда Н⁰₂, Н¹₂ Н²₂ существуют и делятся на 2⁹⁹⁸,…; все числа 999-го ряда Н⁰₉₉₉, Н¹₉₉₉,…, Н⁹⁹⁹₉₉₉ существуют и делятся на 2; все числа 1000-го ряда Н⁰₁₀₀₀, Н¹₁₀₀₀,…, Н¹⁰⁰⁰₁₀₀₀ существуют (и делятся на 1).

Соотношения (2)-(4) не только доказывают существование решения задачи, но и показывают, как из строчки чисел Н⁰_n, Н¹_n,…, Нⁿ_n получается строчка Н⁰_n+1, Н¹_n+1,…, Нⁿ⁺¹_n+1

Применяя последовательно эти соотношения, начиная с нулевой строки, мы в принципе можем вычислить значения H^k_n для всех 501 501 перекрестков, содержащихся в рядах до тысячного включительно, в частности, для всех перекрестков тысячного ряда, и тем самым решить задачу. Так, для первых рядов непосредственным вычислением находим:

Аналогично находим числа остальных рядов до 1000-го.

Мы решили задачу без применения свойств треугольника Паскаля. Однако это довольно легко можно сделать. Зная свойства таблицы, при помощи, так называемой операции Паскаля, можно установить, что решениями задачи будут являться все члены 1000-й строки треугольника:

С⁰₁₀₀₀, С¹₁₀₀₀, С²₁₀₀₀,…, С¹⁰⁰⁰₁₀₀₀.