СПбГУ 2021, 10-11 классы, задача 1
( баллов) В некоторых клетках полоски поставлено по одной фишке. В каждую из пустых клеток записывается число, равное модулю разности количества фишек слева и справа от этой клетки. Известно, что все записанные числа различны и отличны от нуля. Какое наименьшее количество фишек может быть расставлено в клетках?
Ответ
Ответ: .
Решение. Пусть — количество расставленных фишек. Заметим, что числа в пустых клетках лежат в диапазоне от до и имеют одинаковую четность. Поэтому таких чисел может быть не более . Значит, количество пустых клеток не превосходит , иначе расставленные в них числа будут повторяться. Тогда
Покажем, что значение реализуется. Нам подойдет расстановка
где единицами обозначены фишки, а нулями — пустые клетки. При этом на месте нулей окажутся следующие числа:
Замечание. Приведенная в решении реализация не единственна. Например, подойдет и такая:
Ей соответствуют следующие числа: