Loading [MathJax]/jax/output/SVG/jax.js

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


Anti-Pascal үшбұрышы ол келесі ереже бойынша сандардан құралған теңбүйірлі үшбұрышты орналастыру: төменгі қатардың сандарынан басқа, әрбір сан дереу төмен тұрған екі санның айырмасының модуліне тең. Мысалы, төрт қатардан тұратын және 1-ден 10-ға дейін барлық бүтін сандар кездесетін осындай anti-Pascal үшбұрышы келтірілген: 42657183109 2018 қатардан тұратын және 1-ден 1+2++2018 санға дейін барлық бүтін сандар кездесетіндей anti-Pascal үшбұрышы бар ма?
посмотреть в олимпиаде

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

  9
1 года 5 месяца назад #

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

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