Processing math: 100%

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


Антипаскалевым треугольником, назовём таблицу в виде равностороннего треугольника, заполненную числами так, что каждое число, кроме чисел, стоящих в нижней строке, равно модулю разности двух чисел, стоящих непосредственно под ним. Ниже приведён пример антипаскалева треугольника с четырьмя строками, в котором встречаются все целые числа от 1 до 10. 42657183109 Существует ли антипаскалев треугольник с 2018 строками, в котором встречаются все целые числа от 1 до 1+2+3++2018?
посмотреть в олимпиаде

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

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