Числовой треугольник
Вот такая интересная задача была предложена в 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}\]](/wp-content/ql-cache/quicklatex.com-235ec21fccd6d606f3e00e7f7b86f4d4_l3.png "Rendered by QuickLaTeX.com")
где каждое число — сумма чисел, которые стоят над ним (в каждой следующей строке на одно число меньше, чем в предыдущей, и в последней строке находится только одно число). Докажите, что последнее число делится на 1993.
Этот числовой треугольник чем-то напоминает треугольник Паскаля. Однако он перевернут основанием вверх, и числа в нем стоят другие. В действительности кроме треугольника Паскаля известны и другие числовые треугольники. Например, треугольники Люка, Каталана, Трибоначчи, Фибоначчи (о них можно узнать здесь, а о числах Каталана см. здесь). Эти треугольники хорошо изучены и нашли свое применение.
Решение задачи 1. Сначала я приведу решение, которое предложено авторами задачи.
Запишем элементы первой строки как
![\[a_0,a_1,a_2,\ldots,a_{1993}.\]](/wp-content/ql-cache/quicklatex.com-74534c5479e8581e8486185dc2ee6107_l3.png "Rendered by QuickLaTeX.com")
Тогда элементы второй строки запишутся как
![\[a_0+a_1,a_1+a_2,a_2+a_3,\ldots,a_{1992}+a_{1993},\]](/wp-content/ql-cache/quicklatex.com-1978d8001a4e75d61eb7fa2d4a6d55fb_l3.png "Rendered by QuickLaTeX.com")
а элементы четвертой строки будут равны
![\[a_0+2a_1+a_2,a_1+2a_2+a_3,a_2+2a_3+a_4,\ldots\]](/wp-content/ql-cache/quicklatex.com-25deca950ec7302082e8a691b18e99b1_l3.png "Rendered by QuickLaTeX.com")
Предположим, что первые два элемента 
-ой строки 
выражаются через элементы первой строки следующим образом:
![\[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},\]](/wp-content/ql-cache/quicklatex.com-39e46c22486478da0b874a60363a2ecf_l3.png "Rendered by QuickLaTeX.com")
![\[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}.\]](/wp-content/ql-cache/quicklatex.com-9b46359ee85422b609da7e1a56637af4_l3.png "Rendered by QuickLaTeX.com")
Тогда первый элемент следующей строки будет равен (здесь пользуемся свойством 2 чисел 
и тем, что 
):
![\[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,\]](/wp-content/ql-cache/quicklatex.com-c8baafb73ebba2a5e1a459374e4acf14_l3.png "Rendered by QuickLaTeX.com")
что и доказывает справедливость нашего предположения.
Последний элемент треугольника — это элемент 
, стоящий в 
-й строке. Поэтому он равен
![\[a_{1994,0}=C_{1993}^0\cdot0+C_{1993}^1\cdot1+C_{1993}^2\cdot2+\ldots+C_{1993}^{1993}\cdot1993 .\]](/wp-content/ql-cache/quicklatex.com-0c534d9de78d58ee4116b0a9234ba6c2_l3.png "Rendered by QuickLaTeX.com")
Так как 
— простое число, то для любого 
делится на , следовательно, и кратно .
Решение 2. Честно говоря, решение, приведенное на странице олимпиады, мне не понравилось. Поэтому приведу еще свое решение, которое мне нравится больше (может быть, потому что оно мое 
).
Перепишем данный числовой треугольник, поставив на место каждого числа его же или число, сравнимое с данным по модулю :
![\[\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}\]](/wp-content/ql-cache/quicklatex.com-655ffb4af0d474c5e7e21f836a5d92ed_l3.png "Rendered by QuickLaTeX.com")
Очевидно, что треугольник симметричен (с точностью до знака) относительно прямой, проходящей через его нижнюю вершину. А на самой этой прямой могут стоять только нули, поскольку любое число на ней равно сумме двух противоположных чисел. Следовательно, в вершине стоит нуль, а это и значит, что число в вершине делится на .
1 Корнеев В.Ф.:
Там не рассмотрены числа Стирлинга первого и второго рода. (Дж. Стирлинг – анг. математик 1692-1770)
……………………
- числа первого рода. Я не могу здесь приводить их рекуррентного соотношения. Свойства
1) Диагональные элементы равны единице.
2) Элементы первого столбца с точностью до знака есть факториалы.
3) Правая поддиагональ состоит из биномиальных коэффициентов, взятых со знаком минус.
4) Сумма чисел произвольной строки, начиная со 2-й, равна 0.
- числа второго рода.
[Ответить]
30 Ноябрь 2011, 21:052 Елизавета Александровна Калинина:
Да, согласна, тоже красивые числовые треугольники. Спасибо, что напомнили.
[Ответить]
30 Ноябрь 2011, 21:383 Алексей Д.:
Как вариант рассуждений:
Пусть в n-ой строке числового треугольника суммы симметричных элементов строки кратны 1993 (если в строке нечетное число элементов, то центральный элемент кратен 1993),тогда
во-первых, сумма всех элементов этой строки кратна 1993,
во-вторых, суммы симметричных элементов (n+1)-ой строки кратны 1993, так как они составятся из сумм симметричных элементов n-й строки
Так как первая строка числового треугольника удовлетворяет указанному условию, то и во всех строках треугольника суммы симметричных элементов будут кратны 1993, следовательно, сумма всех элементов для каждой строки (в том числе и последней) кратна 1993
[Ответить]
4 Декабрь 2011, 15:254 Елизавета Александровна Калинина:
Да, Алексей, все так.
Мне непонятно только, почему вариант с биномиальными коэффициентами основной. Видимо, в испанских школах проходят бином Ньютона, а может, сочетания, но не проходят сравнения…
[Ответить]
5 Декабрь 2011, 20:015 Иван:
Статья мне очень интересна (спасибо!), но вот ссылки в “треугольники Люка, Каталана, Трибоначчи, Фибоначчи (о них можно узнать здесь” – не работает. А очень нужна!
[Ответить]
Геннадий Reply:
Декабрь 16th, 2018 at 15:52
Треугольник Каталана (Дика) можно посмотреть здесь
http://eremin.xyz/dyck/some-dynamics/
и здесь
http://eremin.xyz/dyck/modified-triangle/
[Ответить]