Республиканская олимпиада по математике, 2022 год, 9 класс

Дана таблица $35 \times 35$, в клетках которой случайным образом расставлены числа от 1 до 49, причем каждое число $i$ использовалось $i$ раз. Из таблицы наудачу удаляются некоторые клетки, после чего она распадается на связные по сторонам клетчатые многоугольники. Из них выбирается один с наибольшей площадью (если таких несколько, то берется случайный). Какое наибольшее количество клеток можно было удалить из таблицы, чтобы некоторое число гарантированно встретилось в выбранном многоугольнике хотя бы 15 раз. ( Конаныхин А. )

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

наибольшее

пусть $k$ это кол-во удаляемых клеток.

При $k\geq35$ убрав 18ый ряд и какие то еще, получается, что $max S\leq595$ , заметим что максимальная площадь у многоугольника без 15 повторении некого числа $=1+2+3+\dots+14+14+\dots+14=595$, т.е при $k\geq35$ не гарантировано.

Методом забора при $k=34$ мы можем отколоть максимально 561 клеток , у оставшегося многоугольника площадь будет $\geq630 >596$