59-я Международная Математическая Oлимпиада Румыния, Клуж-Напока, 2018 год

Антипаскалевым треугольником, назовём таблицу в виде равностороннего треугольника, заполненную числами так, что каждое число, кроме чисел, стоящих в нижней строке, равно модулю разности двух чисел, стоящих непосредственно под ним. Ниже приведён пример антипаскалева треугольника с четырьмя строками, в котором встречаются все целые числа от 1 до 10. $$\begin{array}{ c@{\hspace{4pt}}c@{\hspace{4pt}} c@{\hspace{4pt}}c@{\hspace{2pt}}c@{\hspace{2pt}}c@{\hspace{4pt}}c } & & & 4 & & & \\ & & 2 & & 6 & & \\ & 5 & & 7 & & 1 & \\ 8 & & 3 & & 10 & & 9 \\ \end{array}$$ Существует ли антипаскалев треугольник с 2018 строками, в котором встречаются все целые числа от 1 до $1 + 2 + 3 + \ldots + 2018$?

Комментарий/решение

Ответ — нет, треугольника АнтиПаскаля с требуемыми свойствами не существует.

Пусть n = 2018 и N = 1 + 2 + · · · + n. Для каждого числа d, не вошедшего в нижнюю строку, нарисуйте стрелку от d к большему из двух чисел под ним (т. е. если d = a − b, нарисуйте

г → а). Это создает ориентированный лес (который выглядит как удар молнии).

Рассмотрим направленный путь, начинающийся из верхней вершины A. Начиная с первого числа, он увеличивается не менее чем на 1 + 2 + · · · + n, поскольку приращения на каждом шаге пути различны; поэтому должно соблюдаться равенство, и, таким образом, путь сверху заканчивается в N = 1 + 2 + · · · + n со всеми числами {1, 2, . . . , n} находиться рядом. Пусть Б будет этим

позиция.

Рассмотрим двух левых/правых соседей X и Y конечной точки B. Предположим, что B

справа от середины нижней стороны и завершите равносторонний треугольник как показано на вершине C. Предположим, что удар молнии из C попадает в нижнюю часть точки D. По построению, она проходит не менее ⌊n/2 − 1⌋ шагов. Но приросты должны быть не менее n+1, n+2, ... поскольку 1,2,...,n близки к пути молнии A → B. Тогда число в D не меньше

(n + 1) + (n + 2) + · · · + (n + (⌊n/2 − 1⌋)) > 1 + 2 + · · · + n для n ≥ 2018, противоречие.