10-я Балканская математическая олимпиада среди юниоровКишинёв, Молдавия, 2006 год

Рассмотрим таблицу размера $2n \times 2n$. Из $i$-ой строки мы удаляем центральные $2(i-1)$ единичных клеток. Какое максимальное количество прямоугольников $2 \times 1$ и $1 \times 2$ могут быть помещены в полученную фигуру так, чтобы они не пересекались и не выходили за границы фигуры?

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

По условию мы убираем 2n(n-1) клеток. Поделим 2nx2n на 4 квадрата nxn. И из этого квадрата убирается n(n-1)/2 квадратов. Ещё из первого , последнего столбца и строки не убираются клетки тогда поставим в середину(2 клетки) нашу фигуру. Тогда у нас с квадрата nxn остается n^2-n(n-1)/2-2 клетки. Если n не четное то мы из оставшихся клеток не можем заполнить (n-3)/2 клеток это доказывается по индукции. Для n четного (n-4)/2 тоже доказывается по индукции. Значит если n четное то мы не можем поставить в итоге n(n - 1)/2+ (n- 4)/2 = (n^2 - 4)/2 клеток для квадрата nxn. Значит мы не можем поставить фигуры максимум на 2(n^2-4) клеток (умножили на 4 что бы был квадрат 2nx2n. Значит мы можем заполнить на 4n^2 - 2(n^2-4) = 2n^2+8 клеток. А вот нашими фигурами (2n^2+8)/2=n^2+4.

Для n не четного:

В квадрате nxn мы не можем поставить n(n-1)/2+ (n-3)/2=(n^2-3)/2 умножим на 4 для целого квадрата 2(n^2-3). Значит мы можем заполнить фигурами 4n^2 - 2(n^2-3) = 2n^2+6 клеток. Делим на 2 что бы узнать максимальное количество фигур выходит n^2+3

Ответ:для не четного n макс. это n^2+3 для четного n макс. это n^2+4

Уважаемый смокинг пожалуйста научитесь пользоваться Латехом а то глазам не приятно читать

Уважаемый хейтер почему вы придрались именно ко мне когда на матоле 40%< расписывают без латеха?

Нет

Не Байан

Почему ваше решение такое же как в официальном ?

Это для тех у кому лень искать официальное решение. А также где то запрещалось расписывать решение как в официальном?

Ну зачем вы расписываете если просто копируете с официального

Все мой решенные задачи это мой только эта задача как вы официальном и я выше сказал причину