Олимпиада имени Леонарда Эйлера 2022-2023 учебный год, I тур регионального этапа

В клетках таблицы $10\times 10$ расставлены натуральные числа 1, 2, $\ldots$, 99, 100. Назовём уголком фигуру, которая получается удалением одной клетки из квадрата $2\times 2$. Назовем уголок хорошим, если число в его клетке, граничащей по сторонам с двумя другими, больше чисел, стоящих в этих двух других клетках. Каково наибольшее возможное число хороших уголков? (Каждый уголок учитывается независимо от того, как он расположен по отношению к другим, разные уголки могут частично накладываться). ( А. Голованов )

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

Ответ: 162

Оценка:

Разобьем доску на квадраты 4*4. Рассмотрим такой квадрат: в нем макс 2 хороших уголков (если будет хотя бы 3, то найдутся два соседних хороших, пусть а1 и а2, но из определения хороших уголков a1>a2 и а2>а1, противоречие). Поэтому, эти 2 уголка являются противоположными углами квадрата.

Рассмотрим количество хороших уголков, образованных из клеток, взятых с разных квадратов. Хорошое клетки - клетки, которые являются центром хотя бы одного хорошего уголка. Хорошие клетки, находящиеся в уголках изначальной таблицы, образуют 1 хороший уголок. Хорошие клетки по бокам, но не в углах, образуют макс 2 хороших уголка. Все остальные хорошие клетки образуют макс 4 хороших уголка.

Теперь посчитаем макс количество хороших уголков во всей таблице:

При нашем макс случае 2 хорошей клетки будут в углах, на каждой боковой стороне по 4, все остальные 32 клетки ни по бокам, ни в углу: 2*1 + 4*4*2 + 32*4 = 2 + 32 + 128 = 162

Пример:

каждый квадрат 4*4 раскрасим так:

черный белый

белый черный

где черная клетка - любое число большее 50, и белая клетка - любое число меньшее или равное 50.

...

...

...