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

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

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

Ответ:n=3064342

На доске в общем $2021^2$ клеток.Бахытжан выбирает 1011 строк и 1011 столбцов чтобы их перекрасить в черный цвет.Когда он выбирает 1011 столбцов он закрашивает 2021*1011 клеток.И когда выбирает 1011 строк то уже закрашивает 1010*1011 клеток.Так как в первом он уже закрасил из 2021 клеток каждой строки 1011,ведь когда он закрашивает столбцы то при этом закрашиваются и клетки строк.Значит в первом также закрасились 2021-1011 клеток строки каждого выбранного столбца.Значит в общем Бахытжан закрасил 1011*3031=(1011*2021)+(1011*1010).Из общего количества клеток отнимаем закрашенные клетки и добавляем 1 клетку.Тогда количество этих клеток будет самым минимальным n когда Арман гарантирует себе победу,независимо от того,как будет действовать Бахытжан.

Неверно, ответ: n = 3033

Всё просто. То, что черных клеток всего 1011*3031 не означает, что красных клеток обязательно должно быть больше. При грамотном распределении можно обойтись и 3032 красными клетками.

В черный цвет будет закрашено всего 1011 столбов и 1011 строк, значит нужно минимальное количество красных клеток которые будут служить "жертвой" для Бахытжана и ещё одна которая "выживет". Сначала стоит просто закрасить в красный всю диагональ начиная с левого верхнего угла до правого нижнего. Итого потребуется всего 2021 красных клеток, которые послужат "жертвой". Но этого недостаточно ведь даже добавив ещё одну точку, она всё равно может быть покрашена в черный цвет. Значит надо ещё, закрасим полу-диагональ начиная с левого нижнего угла до центра(которая уже закрашена), это поможет "зафиксировать" всё, всего потребуется 3021=2021+1010. Но и этого недостаточно, ведь центральная красная клетка не имеет соседа по столбу или строке, значит останется ещё один столбец или строка которые смогут закрасить ещё несколько клеток. Значит в конце надо просто поставить две произвольных клеток на верхней правой четверти доски так, что они не должны делить одну и ту же строку или столб.

Итого потребуется 3033=2021+1010+2

Не уверен, что правильно, но если заметили ошибку или что-то не поняли, напишите

Признаю, что тут много воды, но я попытался объяснить максимально понятно

Тут есть официальное решение:

https://drive.google.com/drive/folders/1Gzqq3u9CE8589mWW25VFolh8gmu85d5m

Занимательно, что эту задачу даже один межнар по всей видимости не решил. Смотрите результаты области:

https://docs.google.com/document/d/1bz3GrFtLfNPs7FSUdtP52JauEV_kQuxi/edit

Сам Фетхуллах - 9 баллов за 1 тур - скорее всего он полностью решил только третью задачу. На каждую задачу на той области давали по одному часу.

Далее в этом же году... Серебрянная медаль на IMO (https://www.imo-official.org/team_r.aspx?code=KAZ&year=2021)

В прошлом же году была похвальная грамота (https://www.imo-official.org/team_r.aspx?code=KAZ&year=2020)

Официальное решение почти полностью неправильное, в нем пару значимых косяков, которые я (и никто другой, включая автора, насколько мне известно) до сих пор не знаю как исправить. Попробуйте найти ошибки сами.

Задача же адаптирована с этой -https://artofproblemsolving.com/community/c6h1879823p12786342, только вот автор решил сменить 8 на 2021, в то время как адекватное решение существует только для четного случая

вы Сам Фетуллах?

нет он Сам Фетулахах

Это действительно по нормальному не решаемая задача.

Посмотрим на четный случай, то есть когда доска вида $2n\times 2n$, Бахытжан закрашивает в черный по $n$ строк и столбцов.

Пусть $k$ - наименьшее количество красных клеток которых Арману будет достаточно для победы.

В этом случае легко показать, что $k\ge 3n+1$ - если Бахытжан закрашивает какие-то $n$ строк, то в остальных $n$ строках должны быть не менее $n+1$ красных клеток (иначе Б победил), тогда по принципу Дирихле, окажется, что в любых $n$ строках имеется хотя бы одна с не менее чем двумя красными клетками. Возьмем верхние $n$ строк - там найдется строка с не менее чем двумя красными. От перестановки строк выигрышность или проигрышность позиции Армана не меняется - переставим эту строку в самый вверх. Далее перейдем к следующим $n$ строкам (со второй до $n+1$-ой) - делаем то же самое, но строку с не менее чем двумя красными переставляем уже со второй строкой. В конце на таблице, в верхних $n$ строках, в каждой будут не менее 2 красных, значит в верхней половине не менее $2n$ красных, в нижней половине будут не менее $n+1$ красных, т.к. нижняя половина содержит $n$ строк, и в сумме на доске не менее красных $3n+1$.

Затем, это так удачно оказывается, что при четном случае имеется простая конструкция которая сходится с довольно простой оценкой выше и которую можно обобщить для любого $n$.

В разобранном здесь - https://artofproblemsolving.com/community/c6h1879823p12786342, частном случае при $n=4$ в первом решении приводится такой пример $k=3n+1=13$ (в остальных решениях были неправильные примеры):

$$\begin{matrix}X& 0& 0& 0& 0& 0& 0& 0 \\0& X& 0& 0& 0& 0& 0& 0 \\0& 0& X& 0& 0& 0& 0& 0 \\0& 0& 0& X& 0& 0& 0& X \\0& 0& 0& X& X& 0& 0& 0 \\0& 0& 0& 0& X& X& 0& 0 \\0& 0& 0& 0& 0& X& X& 0 \\0& 0& 0& 0& 0& 0& X& X\end{matrix}$$

Можно показать, что такая конструкция обобщается для любой четной доски...

А что же в нечетном случае?

Аналогичная оценка приводит к $k\ge 3n+4$ если доска вида $2n+1\times 2n+1$ и Бахытжан закрашивает по $n+1$ строк и столбцов. Прямо как в первой оценке значения $k$ в официальном решении, из этого выйдет, что в случае $2n+1=2021$ будет $k\ge 3034$. А дальше уже всё - вот так просто найти пример с 3034 красными клетками у Армана нельзя. В официальном решении, приведенный пример с 3035 красными - неправильный. Танцевать вокруг частного случая с доской именно размера $2021$ даже компьютеру бы ушло очень много времени. Единственная надежда - какая-то общая конструкция для всех нечетных случаев.

Рассмотрим случай $2n+1=5$. Грамотным перебором можно получить, что здесь $k\ge 13$. Пример конструкции с 13 красными клетками:

$$\begin{matrix}X& 0& 0& 0& 0 \\0& X& X& X& 0 \\0& 0& X& X& X \\0& X& 0& X& X \\0& X& X& 0& X \end{matrix}$$

Красивая конструкция - одна красная клетка в углу и $N-1$ горизонтальных троек следуют ниже ($N$ - размер доски). Эту конструкцию можно обобщить и она даже будет работать для всех нечетных $N$. В частности, получим, что $k\le 3\cdot 2020+1=6061$ для $N=2021$. У нас теперь не может не появится гипотеза - для нечетной $N$ доски, $k=3(N-1)+1=3N-2$. Однако, к сожалению, гипотеза оказывается неверной - для $N=7$ имеется более оптимальный пример с 16 красными клетками вместо $3N-2=19$:

$$\begin{matrix}X& 0& 0& 0& 0& 0& 0& \\0& X& X& 0& 0& 0& 0& \\0& 0& 0& X& X& 0& 0& \\0& 0& 0& 0& 0& X& X& \\0& 0& X& 0& X& X& 0& \\X& 0& 0& X& 0& 0& X& \\0& X& 0& X& 0& X& 0& \end{matrix}$$

И то, я довольно случайно нашел этот пример, не исключено, что возможно найдется пример с 15 красными клетками.

Для случая $N=7$ мне не удалось найти хоть сколь нибудь красивой конструкции - уже начиная с этой нечетной все становится каким-то очень хаотичным.

Таким образом, какой-то общей для всех нечетных $N$ выигрышной для Армана конструкции - не существует. Решить эту задачу элементарными методами за разумное количество времени - невозможно.

Может это еще один заговор составителей из била? Может они специально вставили на место самой простой первой задачи невозможную? Не заметить неправильность примера с 3035 красными клетками у Армана в официальном решении довольно сложно - значит, наверное, они для вида специально в документ с решениями задач вставили неправильное? Затем они своим сказали, что вот на первую задачу наши поставили нерешенную задачу, а на третьем легкий диофант. Тут объективно третья задача самая легкая. Затем остальные школы тратят огромное количество времени на первую задачу, может быть, через 1-1,5 часа бросят ее и затем попадаются в ловушку - вторая задача на самом деле на порядок сложнее третьей и все небиловцы получают низкие баллы на первом туре. Вот так вот. Других вариантов ведь быть не может.

Давайте будем считать что Арман закрашивает один диагональ и несколько кавдратиков. То Бахытжан своим первом ходом должен перекрашивать $1011$ строк которых перекрашена много квадратиков чем остальных строк. Тогда очевидно что до того Бахытжан не делал свой $2$ ход на доске должен стать как минимум $1012$ красных что бы Арман победил. Потому что если было меньше или равен $1011$ то Бахытжан подкрашивает этих столбец и победил бы. Значить хотя бы в одном строке как минимум две красных. Так как до этого Бахытжан подкрашивал $1011$ строк которых красных больше или равевн других и еще остался одно строка который есть $2$ красных, у каждый под крашенных строк должен быть как минимум $2$. $1011 \cdot 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$