Областная олимпиада по математике, 2021 год, 11 класс

Изначально все клетки доски $2021 \times 2021$ белые. Арман и Бахытжан играют в такую игру. Сначала Арман закрашивает $n$ квадратиков в красный цвет. Затем Бахытжан выбирает 1011 строк и 1011 столбцов и перекрашивает все ячейки в выбранных строках и столбцах в чёрный цвет. Арман выигрывает в том случае, если осталась хотя бы одна красная клетка, в противном случае выигрывает Бахытжан. При каком наименьшем $n$ Арман гарантирует себе победу, независимо от того, как будет действовать Бахытжан?

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

Давайте будем считать что Арман закрашивает один диагональ и несколько кавдратиков. То Бахытжан своим первом ходом должен перекрашивать $1011$ строк которых перекрашена много квадратиков чем остальных строк. Тогда очевидно что до того

Бахытжан не делал свой $2$ ход на доске должен стать как минимум $1012$ красных что бы Арман победил. Потому что если было меньше или равен $1011$ то Бахытжан подкрашивает этих столбец и победил бы. Значить хотя бы в одном строке как минимум две красных. Так как до этого Бахытжан подкрашивал $1011$ строк которых красных больше или равен других и еще остался одно строка который есть $2$ красных, у каждый под крашенных строк должен быть как минимум $2$.

$1011 • 2 + 1012 = 3034$

Допустим, ответ - $3034$ . Если бы Арман пропустил одну строчку и нарисовал другие. Затем, согласно принципу Дирихле, одна из строк должна иметь $3$ красных. Бахытжан рисует строк за $1010$, где есть две красные и одна строка, где $3$ красная. $1010 \cdot 2 + 3 = 2023$

$3034 - 2023 = 1011$, но это невозможно. Потому, если бы осталось $1011$ красных, Бахытжан покрасил бы столбец, из которых есть красные, и выиграл бы. Тогда ответ - $3035$

Мы знаем, что есть $1012$ строк, где каждая из этих строка имеет по крайней мере две красные. Аналогичным образом, существует также столбец в $1012$, где каждый из этих столбец имеет по крайней мере два красных. Допустим, Арман уже нарисовал одну диагональ, чтобы было понятно. Затем Арман должен покрасить еще $1012$ в красный цвет из разных строк и из разных столбец. Поскольку он уже нарисовал одну диагональ и еще $1012$, общая сумма, которую он нарисовал $2023 + 1012 = 3035$

Ответ:$3035$