Математикадан облыстық олимпиада, 2021 жыл, 11 сынып

Бастапқыда өлшемi $2021 \times 2021$ болатын тақтаның барлық ұяшықтары ақ түстi болсын. Арман мен Бақытжан келесi ойын ойнайды. Бастапқыда Арман $n$ ұяшықтарды қызыл түске бояйды. Содан кейiн Бақытжан 1011 қатарды және 1011 бағанды таңдап, таңдалған қатарлар мен бағандардағы барлық ұяшықтарды қара түске бояйды. Кем дегенде бiр қызыл ұяшық қалса Арман жеңедi, әйтпесе Бақытжан жеңедi. Бақытжан қалай әрекет ететiнiне қарамастан, Арман қандай ең кiшi $n$ үшiн өзiне жеңiске жетуге кепiлдiк бере алады?

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

Давайте будем считать что Арман закрашивает один диагональ и несколько кавдратиков. То Бахытжан своим первом ходом должен перекрашивать $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$