«
»

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

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}=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} 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

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

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