Математикадан облыстық олимпиада, 2021 жыл, 10 сынып
Комментарий/решение:
Ответ:n=3064342
На доске в общем 20212 клеток.Бахытжан выбирает 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×2n, Бахытжан закрашивает в черный по n строк и столбцов.
Пусть k - наименьшее количество красных клеток которых Арману будет достаточно для победы.
В этом случае легко показать, что k≥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 (в остальных решениях были неправильные примеры):
X00000000X00000000X00000000X000X000XX0000000XX0000000XX0000000XX
Можно показать, что такая конструкция обобщается для любой четной доски...
А что же в нечетном случае?
Аналогичная оценка приводит к k≥3n+4 если доска вида 2n+1×2n+1 и Бахытжан закрашивает по n+1 строк и столбцов. Прямо как в первой оценке значения k в официальном решении, из этого выйдет, что в случае 2n+1=2021 будет k≥3034. А дальше уже всё - вот так просто найти пример с 3034 красными клетками у Армана нельзя. В официальном решении, приведенный пример с 3035 красными - неправильный. Танцевать вокруг частного случая с доской именно размера 2021 даже компьютеру бы ушло очень много времени. Единственная надежда - какая-то общая конструкция для всех нечетных случаев.
Рассмотрим случай 2n+1=5. Грамотным перебором можно получить, что здесь k≥13. Пример конструкции с 13 красными клетками:
X00000XXX000XXX0X0XX0XX0X
Красивая конструкция - одна красная клетка в углу и N−1 горизонтальных троек следуют ниже (N - размер доски). Эту конструкцию можно обобщить и она даже будет работать для всех нечетных N. В частности, получим, что k≤3⋅2020+1=6061 для N=2021. У нас теперь не может не появится гипотеза - для нечетной N доски, k=3(N−1)+1=3N−2. Однако, к сожалению, гипотеза оказывается неверной - для N=7 имеется более оптимальный пример с 16 красными клетками вместо 3N−2=19:
X0000000XX0000000XX0000000XX00X0XX0X00X00X0X0X0X0
И то, я довольно случайно нашел этот пример, не исключено, что возможно найдется пример с 15 красными клетками.
Для случая N=7 мне не удалось найти хоть сколь нибудь красивой конструкции - уже начиная с этой нечетной все становится каким-то очень хаотичным.
Таким образом, какой-то общей для всех нечетных N выигрышной для Армана конструкции - не существует. Решить эту задачу элементарными методами за разумное количество времени - невозможно.
Может это еще один заговор составителей из била? Может они специально вставили на место самой простой первой задачи невозможную? Не заметить неправильность примера с 3035 красными клетками у Армана в официальном решении довольно сложно - значит, наверное, они для вида специально в документ с решениями задач вставили неправильное? Затем они своим сказали, что вот на первую задачу наши поставили нерешенную задачу, а на третьем легкий диофант. Тут объективно третья задача самая легкая. Затем остальные школы тратят огромное количество времени на первую задачу, может быть, через 1-1,5 часа бросят ее и затем попадаются в ловушку - вторая задача на самом деле на порядок сложнее третьей и все небиловцы получают низкие баллы на первом туре. Вот так вот. Других вариантов ведь быть не может.
Давайте будем считать что Арман закрашивает один диагональ и несколько кавдратиков. То Бахытжан своим первом ходом должен перекрашивать 1011 строк которых перекрашена много квадратиков чем остальных строк. Тогда очевидно что до того Бахытжан не делал свой 2 ход на доске должен стать как минимум 1012 красных что бы Арман победил. Потому что если было меньше или равен 1011 то Бахытжан подкрашивает этих столбец и победил бы. Значить хотя бы в одном строке как минимум две красных. Так как до этого Бахытжан подкрашивал 1011 строк которых красных больше или равевн других и еще остался одно строка который есть 2 красных, у каждый под крашенных строк должен быть как минимум 2. 1011⋅2+1012=3034
Допустим, ответ - 3034 . Если бы Арман пропустил одну строчку и нарисовал другие. Затем, согласно принципу Дирихле, одна из строк должна иметь 3 красных. Бахытжан рисует строк за 1010, где есть две красные и одна строка, где 3 красная. 1010⋅2+3=2023
3034−2023=1011, но это невозможно. Потому, если бы осталось 1011 красных, Бахытжан покрасил бы столбец, из которых есть красные, и выиграл бы. Тогда ответ - 3035
Мы знаем, что есть 1012 строк, где каждая из этих строка имеет по крайней мере две красные. Аналогичным образом, существует также столбец в 1012, где каждый из этих столбец имеет по крайней мере два красных. Допустим, Арман уже нарисовал одну диагональ, чтобы было понятно. Затем Арман должен покрасить еще 1012 в красный цвет из разных строк и из разных столбец. Поскольку он уже нарисовал одну диагональ и еще 1012, общая сумма, которую он нарисовал 2023+1012=3035
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.