38-я Балканская математическая олимпиада. 2021 год

У Ангела есть склад, на котором изначально находится 100 куч по 100 кусков мусора в каждой. Каждое утро Ангел выполняет ровно одно из следующих действий:
   (a) Он очищает каждый кусок мусора из одной кучи.
   (b) Он очищает по одному кусочку мусора из каждой кучи.
   Однако каждый вечер на склад пробирается демон и выполняет ровно одно из следующих действий:
   (a) Он добавляет по одному куску мусора в каждую непустую кучу.
   (b) Он создает новую кучу с одним куском мусора.
   В какое первое утро Ангел может гарантировать, что очистил весь мусор со склада?

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

198.

Доказательство: после первого утра останется 99 групп по 99 мусора. Мы видим, что после того, как демоны и ангелы движутся вместе, мы получаем 3 возможных результата.

1. Есть -1 стопка

2. Из каждой кучи -1 мусор.

3. 1 и 2 вместе взятые.

Поскольку у нас 99 стопок и 99 групп, и каждые 2 хода по крайней мере 1 из них уменьшается на 1 (как только кто-то набирает 0, игра заканчивается), мы видим, что это занимает максимум 99*2 - 1 ходов. Следовательно, верхняя граница равна (99*2-1)+1 = 198.

Нижняя граница: первые 98 раз дьявол добавляет 1 ко всем группам, а затем всегда добавляет новую группу.

Я думаю, что это работает, но может быть где-то ошибка.