ВсОШ 2024, 11 класс, задача 5
Квартал представляет собой клетчатый квадрат . В новогоднюю ночь внезапно впервые пошёл снег, и с тех пор каждую ночь на каждую клетку выпадало ровно по см снега; снег падал только по ночам. Каждое утро дворник выбирает один ряд (строку или столбец) и сгребает весь снег оттуда на один из соседних рядов (с каждой клетки - на соседнюю по стороне). Например, он может выбрать седьмой столбец и из каждой его клетки сгрести весь снег в клетку слева от неё. Сгребать снег за пределы квартала нельзя. Вечером сотого дня года в город приедет инспектор и найдёт клетку, на которой лежит сугроб наибольшей высоты. Цель дворника - добиться, чтобы эта высота была минимальна. Сугроб какой высоты найдёт инспектор? (А. Солынин)
Ответ. см.
Решение. Будем измерять высоту сугроба в дециметрах. Также будем считать, что сторона одной клетки равна дм, то есть за каждую ночь на клетку выпадает дм снега.
Докажем, что после сотого утра найдётся сугроб высотой не менее дм. Предположим, что такого сугроба нет. Так как дворник в сотое утро полностью сгрёб снег с какого-то ряда, в десяти клетках квадрата снега нет. В каждой из оставшихся клеток, по нашему предположению, не более дм снега, то есть всего снега не больше, чем дм. Однако за ночей суммарно выпало дм снега. Противоречие.
Покажем, как может действовать дворник, чтобы после сотого утра каждый сугроб имел высоту не более дм (то есть в каждой клетке было не более дм снега).
Способ 1. Первые дней дворник сгребает снег из второго столбца в первый, следующие дней дворник сгребает снег из третьего столбца во второй, затем дней из четвёртого в третий, и т. д. Через дней в десятом столбце не будет снега.
Посчитаем, сколько снега стало в столбце через дней. Вечером -го дня в столбце номер не было снега, а в столбце в каждой клетке было по дм снега. На следующий вечер в столбце станет по дм снега в каждой клетке. Затем ещё десять дней количество снега в каждой клетке -го столбца будет увеличиваться на , а затем дней - на . Итого, через дней в каждой клетке столбца будет по
дм снега. В сотую ночь выпадет ещё по дм в каждую клетку. А сотым утром дворник сгребёт снег из десятого столбца в девятый. Таким образом, в каждой клетке будет не более дм снега.
Способ 2. Пусть дворник сгребёт снег из -го столбца в -ый, из -го во -й, ..., из -го в -ый. Тогда вечером девятого дня в первых девяти столбцах будет по дм снега в каждой клетке, а в десятом столбце снега не будет. Затем дворник проделывает аналогичный процесс в обратном порядке: из -го в -ый, из -го в -ый, ..., из -го в первый. Тогда вечером -го дня в клетках последних девяти столбцов будет по дм снега, а в первом столбце не будет снега. Аналогично повторим такие сдвиги (каждый длится дней) ещё раз, и через дней получим в клетках девяти столбцов по дм снега и один крайний столбец пустой. Сотым утром сгребаем снег из этого крайнего в соседний и получаем не более дм снега в каждой клетке.