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, противоречие.

Если будет найдена ошибка был бы очень признателен! Решение получилось каким то легким и я сомневаюсь в его верности, в любом случае к решению.

\[\]

Возьмем $ M_i $ как максимальное и $m_i$ как минимально число с ряда $i.$ Заметим что $:$

\[M_{i+1}-m_{i+1}\geq M_i \ \ \to \ \ M_{i+1} \geq M_i + m_{i+1} \ \ \to \ \ M_{2018} \geq \sum \limits_{i=1}^{2018} m_i \ ( \ M_1 = m_1 \ ) \]

\[ \sum \limits_{i=1}^{2018} i \geq M_{2018} \geq \sum \limits_{i=1}^{2018} m_i \geq \sum \limits_{i=1}^{2018} i \ \ \to \ \ M_{i+1} - m_{i+1} = M_i\]

Значит $ M_{i+1}, m_{i+1}$ являются соседними элементами с $M_i$ сверху. Для последнего ряда $:$

\[ e_1 \quad e_2 \quad \dots \quad e_j \quad M_{2018} \quad m_{2018} \quad e_{j+3} \quad \dots \quad e_{2017} \quad e_{2018}\]

Также $:$

\[ j \quad \lor \quad 2016-j \geq \left \lceil \dfrac{2018 - 2}{2} \right \rceil = 1008\]

Можно взять антипаскалевый треугольник с основанием $1008.$ Отбросим остальные элементы, переобозначим $M_i, m_i$ и для нашего нового треугольника $:$

\[ M_{i+1}-m_{i+1} \geq M_i \ \ \to \ \ \dfrac{2019\cdot 2018}{2} > M_{1009} \geq \sum \limits_{i=1}^{1008} m_i \geq \sum \limits_{i=2019}^{3026}i > \dfrac{2019\cdot 2018}{2}\]

Следовательно это невозможно