қазақша
русскийОбластная олимпиада по математике, 2021 год, 10 класс
Комментарий/решение:
Ответ: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$
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.