Распечатать запись Распечатать запись

Числовой треугольник

Вот такая интересная задача была предложена в 1993 году на олимпиаде школьников по математике в Испании.

Рассмотрим числовой треугольник

\begin{tabular}{c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c} 0&&1&&2&&3&&4&&\ldots&&1991&&1992&&1993\\<br />
&1&&3&&5&&7&\ldots&\ldots&&\ldots&&3983&&3985&\\<br />
&&4&&8&&12&\ldots&\ldots&\ldots&\ldots&\ldots&&&7968&&\\<br />
&&&&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&&<br />
\end{tabular}

где каждое число — сумма чисел, которые стоят над ним (в каждой следующей строке на одно число меньше, чем в предыдущей, и в последней строке находится только одно число). Докажите, что последнее число делится на 1993.

Этот числовой треугольник чем-то напоминает треугольник Паскаля. Однако он перевернут основанием вверх, и числа в нем стоят другие. В действительности кроме треугольника Паскаля известны и другие числовые треугольники. Например, треугольники Люка, Каталана, Трибоначчи, Фибоначчи (о них можно узнать здесь, а о числах Каталана см. здесь). Эти треугольники хорошо изучены и нашли свое применение.

Решение задачи 1. Сначала я приведу решение, которое предложено авторами задачи.

Запишем элементы первой строки как

a_0,a_1,a_2,\ldots,a_{1993}.

Тогда элементы второй строки запишутся как

a_0+a_1,a_1+a_2,a_2+a_3,\ldots,a_{1992}+a_{1993},

а элементы четвертой строки будут равны

a_0+2a_1+a_2,a_1+2a_2+a_3,a_2+2a_3+a_4,\ldots

Предположим, что первые два элемента p-ой строки b_{p,0} b_{p,1} выражаются через элементы первой строки следующим образом:

b_{p,0}=C_{p-1}^0a_0+C_{p-1}^1a_1+C_{p-1}^2a_2+\ldots+C_{p-1}^{p-1}a_{p-1},

 b_{p,1}=C_{p-1}^0a_1+C_{p-1}^1a_2+C_{p-1}^2a_3+\ldots+C_{p-1}^{p-1}a_{p}.

Тогда первый элемент следующей строки будет равен (здесь пользуемся свойством 2 чисел C_n^k и тем, что C_p^0=C_{p+1}^0=C_{p-1}^{p-1}=C_p^p=1):

b_{p+1,0}=C_{p}^0a_0+C_p^1a_1+C_p^2a_2+\ldots+C_p^pa_p,

что и доказывает справедливость нашего предположения.

Последний элемент треугольника — это элемент a_{1994,0}, стоящий в 1994-й строке. Поэтому он равен

a_{1994,0}=C_{1993}^0\cdot0+C_{1993}^1\cdot1+C_{1993}^2\cdot2+\ldots+C_{1993}^{1993}\cdot1993 .

Так как 1993 — простое число, то для любого k<1993

C_{1993}^k делится на 1993, следовательно, и a_{1994,0} кратно 1993.

Решение 2. Честно говоря, решение, приведенное на странице олимпиады, мне не понравилось. Поэтому приведу еще свое решение, которое мне нравится больше (может быть, потому что оно мое ;) ).

Перепишем данный числовой треугольник, поставив на место каждого числа его же или число, сравнимое с данным по модулю 1993:

\begin{tabular}{c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c}<br />
0&&1&&2&&3&\ldots&996&&-996&&\ldots&-2&&-1&&0\\<br />
&1&&3&&5&&\ldots&&0&&\ldots&-5&&-3&&-1&\\<br />
&&4&&8&&\ldots&\ldots&1991&&-1991&\ldots&&-8&&-4&&\\<br />
&&&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&&&<br />
\end{tabular}

Очевидно, что треугольник симметричен (с точностью до знака) относительно прямой, проходящей через его нижнюю вершину. А на самой этой прямой могут стоять только нули, поскольку любое число на ней равно сумме двух противоположных чисел. Следовательно, в вершине стоит нуль, а это и значит, что число в вершине делится на 1993.

Комментариев: 4

  1. 1 Корнеев В.Ф.:

    Там не рассмотрены числа Стирлинга первого и второго рода. (Дж. Стирлинг – анг. математик 1692-1770)
    \begin{tabular}{rrrrrr}<br />
 1&&&&&\\<br />
-1&1&&&&\\<br />
 2& -3& 1&&&\\<br />
-6&11&-6&1&&\\<br />
24& -50& 35& -10&  1&\\<br />
-120& 274& -225& 85& -15&  1<br />
\end{tabular}
    ……………………
    - числа первого рода. Я не могу здесь приводить их рекуррентного соотношения. Свойства
    1) Диагональные элементы равны единице.
    2) Элементы первого столбца с точностью до знака есть факториалы.
    3) Правая поддиагональ состоит из биномиальных коэффициентов, взятых со знаком минус.
    4) Сумма чисел произвольной строки, начиная со 2-й, равна 0.
    \begin{tabular}{cccccc}<br />
1&&&&&\\<br />
1 & 1&&&&\\<br />
1 & 3 & 1&&&\\<br />
1 & 7&  6&  1&&\\<br />
1& 15& 25& 10&  1&\\<br />
1& 31& 90& 65& 15&  1<br />
\end{tabular}
    - числа второго рода.

    [Ответить]

  2. 2 Елизавета Александровна Калинина:

    Да, согласна, тоже красивые числовые треугольники. Спасибо, что напомнили.

    [Ответить]

  3. 3 Алексей Д.:

    Как вариант рассуждений:
    Пусть в n-ой строке числового треугольника суммы симметричных элементов строки кратны 1993 (если в строке нечетное число элементов, то центральный элемент кратен 1993),тогда
    во-первых, сумма всех элементов этой строки кратна 1993,
    во-вторых, суммы симметричных элементов (n+1)-ой строки кратны 1993, так как они составятся из сумм симметричных элементов n-й строки
    Так как первая строка числового треугольника удовлетворяет указанному условию, то и во всех строках треугольника суммы симметричных элементов будут кратны 1993, следовательно, сумма всех элементов для каждой строки (в том числе и последней) кратна 1993

    [Ответить]

  4. 4 Елизавета Александровна Калинина:

    Да, Алексей, все так.

    Мне непонятно только, почему вариант с биномиальными коэффициентами основной. Видимо, в испанских школах проходят бином Ньютона, а может, сочетания, но не проходят сравнения…

    [Ответить]

Оставьте свой отзыв

Добавить изображение