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

$\textit{Anti-Pascal үшбұрышы}$ ол келесі ереже бойынша сандардан құралған теңбүйірлі үшбұрышты орналастыру: төменгі қатардың сандарынан басқа, әрбір сан дереу төмен тұрған екі санның айырмасының модуліне тең. Мысалы, төрт қатардан тұратын және 1-ден 10-ға дейін барлық бүтін сандар кездесетін осындай anti-Pascal үшбұрышы келтірілген: $$\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+\cdots+2018$ санға дейін барлық бүтін сандар кездесетіндей anti-Pascal үшбұрышы бар ма?

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

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

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