«
»

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

30 Ноябрь 2011, 0:05

Вот такая интересная задача была предложена в 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\\ &1&&3&&5&&7&\ldots&\ldots&&\ldots&&3983&&3985&\\ &&4&&8&&12&\ldots&\ldots&\ldots&\ldots&\ldots&&&7968&&\\ &&&&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&& \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}={\sf C}_{p-1}^0a_0+{\sf C}_{p-1}^1a_1+{\sf C}_{p-1}^2a_2+\ldots+{\sf C}_{p-1}^{p-1}a_{p-1},\]

    \[b_{p,1}={\sf C}_{p-1}^0a_1+{\sf C}_{p-1}^1a_2+{\sf C}_{p-1}^2a_3+\ldots+{\sf C}_{p-1}^{p-1}a_{p}.\]

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

    \[b_{p+1,0}={\sf C}_{p}^0a_0+{\sf C}_p^1a_1+{\sf C}_p^2a_2+\ldots+{\sf 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

{\sf 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} 0&&1&&2&&3&\ldots&996&&-996&&\ldots&-2&&-1&&0\\ &1&&3&&5&&\ldots&&0&&\ldots&-5&&-3&&-1&\\ &&4&&8&&\ldots&\ldots&1991&&-1991&\ldots&&-8&&-4&&\\ &&&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&\ldots&&& \end{tabular}\]

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

Теги: , ,
Рубрика: Разные задачи  |  Отзывы (RSS)  |  Трекбек

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

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

    Там не рассмотрены числа Стирлинга первого и второго рода. (Дж. Стирлинг – анг. математик 1692-1770)

        \[\begin{tabular}{rrrrrr} 1&&&&&\\ -1&1&&&&\\ 2& -3& 1&&&\\ -6&11&-6&1&&\\ 24& -50& 35& -10& 1&\\ -120& 274& -225& 85& -15& 1 \end{tabular}\]

    ……………………
    - числа первого рода. Я не могу здесь приводить их рекуррентного соотношения. Свойства
    1) Диагональные элементы равны единице.
    2) Элементы первого столбца с точностью до знака есть факториалы.
    3) Правая поддиагональ состоит из биномиальных коэффициентов, взятых со знаком минус.
    4) Сумма чисел произвольной строки, начиная со 2-й, равна 0.

        \[\begin{tabular}{cccccc} 1&&&&&\\ 1 & 1&&&&\\ 1 & 3 & 1&&&\\ 1 & 7& 6& 1&&\\ 1& 15& 25& 10& 1&\\ 1& 31& 90& 65& 15& 1 \end{tabular}\]

    - числа второго рода.

    [Ответить]

    30 Ноябрь 2011, 21:05

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

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

    [Ответить]

    30 Ноябрь 2011, 21:38

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

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

    [Ответить]

    4 Декабрь 2011, 15:25

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

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

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

    [Ответить]

    5 Декабрь 2011, 20:01

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

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