Тема КОМБИНАТОРИКА

Клетчатые задачи

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела комбинаторика

Разделы подтемы Клетчатые задачи

Раскраски

Разбиение доски на части

Подсчеты в клетчатых задачах

Увидеть граф (переформулировки)

Клетчатые разрезания, периметры и площади

Формула Пика

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 81#74743Максимум баллов за задание: 7

Натуральные числа $a,b,c$ и $d$ таковы, что $ab= cd,a⁄= c.$ Клетчатый прямоугольник составили из нескольких прямоугольников $a× b$ ( $a$ строчек и $b$ столбцов) и нескольких прямоугольников $c× d$ ( $c$ строчек и $d$ столбцов).

Один из прямоугольников $a× b$ потерялся, а вместо него нашёлся еще один прямоугольник $c×d.$ Докажите, что теперь из всех имеющихся прямоугольников, не поворачивая их, составить тот же клетчатый прямоугольник уже не удастся.

Показать доказательство

Предположим, что можно. Разберём два случая:

Случай $1.$ Пусть $b >d.$ Занумеруем столбцы полученного прямоугольника и закрасим все столбцы с номерами вида $kb +1$ в красный цвет. Ясно, что любой прямоугольник $a× b$ покрывает ровно $a$ красных клеток, а любой прямоугольник $c× d$ покрывает либо $c,$ либо $0$ красных клеток. После потери одного прямоугольника $a× b$ количество красных клеток, покрываемых этими прямоугольниками, уменьшилось на $a.$ Следовательно, эти $a$ клеток должны быть покрыты прямоугольниками $c× d.$ Как мы выяснили ранее, такие прямоугольники покрывают либо $0,$ либо $c$ красных клеток, то есть $a$ кратно $c.$ Но мы предположили, что $b> d,$ а значит $c >a$ (из равенства $ab =cd$ ). Таким образом, $a$ не может делиться на $c.$ Противоречие.

Случай $2.$ Если $b<d,$ то $a >c.$ Занумеруем строки и покрасим строки с номерами $ka+1$ в красный цвет. Далее по аналогичным рассуждениям получим, что $b$ кратно $d.$ Снова пришли к противоречию.

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 82#74831Максимум баллов за задание: 7

Может ли Саша расставить в таблицу $18× 25$ различные нечётные трёхзначные числа так, чтобы любая пара чисел, где одно делится на другое, стояла в соседних по стороне клетках?

Показать ответ и решение

Отметим, что всего нечетных трехзначных чисел $450.$ Также, $18× 25= 450,$ что означает, что каждое из чисел обязано присутствовать в таблице. Предположим противное – пусть числа можно расставить указанным способом. Тогда рассмотрим число $111.$ Числа $333$ и $999$ обязаны соседствовать с ним по стороне клетки, так как они оба на него делятся. Тогда они не соседствуют друг с другом. С другой стороны, 999 делится на 333, а значит они напротив должны иметь общую сторону – противоречие.

Ответ:

Не может

Ошибка.
Попробуйте повторить позже

Задача 83#74834Максимум баллов за задание: 7

В каждой клетке доски $100× 99$ ( $100$ строк и $99$ столбцов) написана одна из букв А, Б или В таким образом, что выполняются следующие условия:

Каждая буква встречается ровно $3300$ раз.
Ни в каких двух соседних по стороне клетках не записаны одинаковые буквы.
Любой квадрат $2× 2$ содержит все три буквы А, Б, В.

Докажите, что в каждой строке ровно $33$ буквы А.

Показать доказательство

Вместо букв будем записывать остатки при делении на $3:0,1$ или $2.$
Лемма. Для соседних двух строк $S$ и $T$ верно, что одна получается из другой изменением всех остатков на одну и ту же величину.
Доказательство леммы. Достаточно проверить, что разность между числами одного столбца внутри квадрата $2 ×2$ одна и та же. Обозначим остатки в квадратике $2×2$ как на рисунке.


$a$	$b$

$c$	$d$

Возможны два случая: $a= d,$ a $b$ и $c$ — оставшиеся остатки, и $b= c,$ а $a$ и $d$ — оставшиеся остатки.
Разберём первый случай. В нём $a,b$ и $c$ — три различных остатка. Тогда очевидно, что $c− a$ и $d − b$ дают одинаковые остатки при делении на $3,$ так как их разность $c+ b− a− d,$ что даёт такой же остаток при делении на $3,$ как и $c+ b+a,$ а это $0+1+ 2,$ что делится на $3.$ Второй случай рассматривается аналогично.
Перейдём к решению задачи. Предположим, что в первой строке $k$ нулей, $m$ единиц и $n$ двоек. Тогда все строки могут быть трёх видов, кроме указанного ещё могут быть строчки с $k$ двойками, $m$ нулями, $n$ единицами или с $k$ единицами, $m$ двойками, $n$ нулями. Заметим, что если мы выкинем по одной строчке каждого вида, то остатков в таблице по-прежнему будет поровну. Такими операциями можно добиться того, что останутся строки одного или двух видов. Если остался только один вид, то очевидно, что $k= m= n.$ Разберём случай, когда осталось два вида. Можно считать, что это строки первого ( $k$ нулей, $m$ единиц и $n$ двоек) и второго вида ( $k$ двоек, $m$ нулей, $n$ единиц).
Предположим, что не все $k,m,n$ равны. Тогда среди них есть число, большее $33.$ Можно считать, что это $k.$ Будем использовать, что в оставшейся таблице нулей, единиц и двоек поровну. Поскольку $k >33,$ в строчках первого вида нулей больше трети, а значит в строчках второго вида должно быть меньше трети, то есть $m< 33.$ Но тогда в строчках первого вида меньше трети единиц, значит, в строчках второго вида должно быть больше трети единиц, то есть $n> 33.$ Но тогда двоек больше трети во всех строчках, а значит и во всей таблице. Противоречие. Значит, $k= m =n.$

Ошибка.
Попробуйте повторить позже

Задача 84#74835Максимум баллов за задание: 7

Доска в форме правильного шестиугольника со стороной $n$ разрезана на правильные треугольники со стороной $1.$ Треугольники раскрашены в чёрный и белый цвета так, что соседние по стороне треугольники имеют разный цвет. Ладья, стоящая в клетке, бьёт вдоль направлений, параллельных сторонам шестиугольника. На доске расставили $2n$ небьющих друг друга ладей. Докажите, что ровно половина из них стоит на белых треугольниках.

Показать доказательство

Обозначим вершины шестиугольника в порядке обхода по часовой стрелке $ABCDEF,$ где $A$ — нижняя левая вершина. Пронумеруем строки каждого направления числами от $1$ до $2n,$ где строка номер $1$ прилегает к стороне $AB,CD$ или $EF$ соответственно. Для каждого треугольника-поля посчитаем сумму трёх координат — номеров строчек, в которых он расположен.
Будем считать, что высота треугольников на картинке равна $1$ и чёрные треугольники смотрят вершиной вверх. Выберем чёрный треугольник и заметим, что для его верхней вершины сумма расстояний до сторон $AB,CD$ и $EF$ фиксирована и равна высоте треугольника, образованного пересечением прямых $AB,CD$ и $EF,$ то есть равна $3n.$ Действительно, в пересечении этих прямых лежит равносторонний треугольник, и известно, что сумма расстояний от любой внутренней точки равностороннего треугольника до его сторон равна высоте этого треугольника. Расстояние от ребра черного треугольника, параллельного $CD,$ до $CD$ на $1$ больше, чем от верхней вершины, а до $EF$ и $AB$ от соответствующих ребер такое же, как и от верхней вершины. Вспомнив, как определялись координаты треугольника, получаем, что сумма его трёх координат равна $3n+ 1.$ Для белого треугольника, выбирая вершину, смотрящую вниз, и рассуждая аналогично, получаем, что сумма его трёх координат равна $3n +2.$
Пусть ладей на чёрных полях $k,$ тогда на белых ладей $2n− k.$ Посчитаем сумму координат всех ладей двумя способами: по ладьям и по рядам. Учтем, что во всех рядах стоит ровно по одной ладье, поскольку ладей столько же, сколько рядов, и они друг друга не бьют:

k⋅(3n +1)+ (2n − k)⋅(3n +2)= 3⋅ 2n(2n-+1) 2

или $k= n,$ что и требовалось.

Ошибка.
Попробуйте повторить позже

Задача 85#74884Максимум баллов за задание: 7

Квадрат $5× 5$ покрывают по клеточкам несколькими $Z$ -тетрамино (четырёхклеточные фигурки в виде буквы $Z$ ) так, что никакая клетка не покрыта более чем двумя фигурами. При этом $Z$ -тетрамино не вылезают за границы квадрата. Какое наименьшее количество клеток квадрата может остаться непокрытыми ни одной фигуркой?

Подсказки к задаче

Подсказка 1

Давайте просто попробуем начать перебирать раскраски, но "по-умному". Шахматная здесь бесполезна, потому что всегда в фигурке 2 чёрные и 2 белые клетки. В полосатой раскраске тоже придётся рассматривать неприятные случаи. А какую раскраску можно применить, чтобы в нашей фигурке все цветы были различные?

Подсказка 2

Верно, давайте покрасим в горошек с четырьмя цветами нашу доску. Тогда каждый цвет будет присутствовать по одному разу в фигурке. А как же применить условие про максимальное покрытие одной клетки? Попробуйте рассмотреть цвета, которых наибольшее и наименьшее количество на доске.

Подсказка 3

Ага, наибольшее количество одноцветных клеток 9 штук, причём мы знаем, что в каждой фигурке все цвета. А наименьшее число клеток четыре. Но ведь тогда получается противоречие с условием задачи о покрытии клеток не более чем двумя фигурками. Осталось только придумать пример, и победа!

Показать ответ и решение

$PIC$

Оценка. Раскрасим доску в $4$ цвета, как на рисунке выше: в первой строчке слева направо $1,2,1,2,1,$ во второй $3,4,3,4,3,$ в третьей снова $1,2,1,2,1$ и так далее. Заметим, что в каждой $Z$ -тетрамино все клетки разных цветов.

Предположим, что все клетки цвета $1$ покрыты хотя бы $1$ раз. Тогда всего $Z$ -тетрамино не меньше $9.$ То есть на $4$ клетки цвета $4$ суммарно приходится $9$ покрытий. Тогда какая-то из этих $4$ клеток покрыта больше $2$ раз — противоречие. Значит, есть хотя бы одна непокрытая клетка.

Пример. Расположим $8$ $Z$ -тетрамино (каждое тетрамино выделено своим цветом) в два слоя как на рисунке выше, чтобы все клетки, кроме центральной, были покрыты хотя бы $1$ раз (два разных цвета в треугольниках, разделённых диагональю, означают, что клетка покрыта двумя тетрамино).

Ответ:

$1$

Ошибка.
Попробуйте повторить позже

Задача 86#74886Максимум баллов за задание: 7

Прямоугольник $a×b$ можно разрезать на несколько прямоугольников, каждый из которых является или горизонтальным прямоугольником $1× m,$ или вертикальным прямоугольником $n ×1.$ Докажите, что тогда прямоугольник $a ×b$ можно разрезать или только на прямоугольники $1× m,$ или только на прямоугольники $n× 1.$

Подсказки к задаче

Подсказка 1

Если a делится на n, то составить разбиение не составит труда. А если не делится, попробуем доказать, что b делится на m. Попробуем поработать с остатками.

Подсказка 2

Попробуем красить в зависимости от остатка по модулю n и сделаем какое-нибудь покрытие. А что если добавить новый цвет?

Подсказка 3

Пусть в разрезании участвуют l прямоугольников n*1 . Перекрасим все клетки, покрытые этими прямоугольниками в n+1 цвет. можно ли посчитать количество клеток каждого цвета? Помним, что мы можем разбить остаток доски на прямоугольники 1*m!

Показать доказательство

Если $a$ делится нацело $n,$ то можно разделить всё только на прямоугольники $n× 1.$ Их будет $bk$ штук, если обозначить $k =[a∕n]= a∕n.$

Если $a$ даёт остаток $r⁄= 0$ при делении на $n,$ то обозначим так же $k= [a∕n]$ и покажем, что $b$ делится нацело на $m.$

Пронумеруем строки сверху вниз и покрасим строку в цвет остатка её номера по модулю $n.$ Тогда на доске $b(k+ 1)$ клеток каждого цвета $i∈{1,2,...,r}$ и $bk$ клеток каждого цвета $j ∈ {r +1,...,n}.$

Рассмотрим произвольное разрезание на прямоугольники. Пусть в разрезании участвуют $l$ прямоугольников $n×1.$ Перекрасим все клетки, покрытые этими прямоугольниками в $(n+ 1)$ -ый цвет. Каждый из прямоугольников $n× 1$ содержит по одной клетке каждого из $n$ цветов. Тогда на доске $b(k+ 1)− l$ клеток каждого цвета $i∈ {1,2,...r}$ и $bk− l$ клеток каждого цвета $j ∈{r+ 1,...,n},$ которые покрыты фигурами $1 ×m.$

Заметим, что каждая из фигур покрывает клетки фиксированного цвета. Тогда $b(k+ 1)− l$ кратно $m$ и $bk− l$ кратно $m.$ Наконец, $(b(k+ 1)− l)− (bk− l)= b$ кратно $m.$ Значит, в этом случае можно разделить всё на прямоугольники $1× m.$

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 87#75300Максимум баллов за задание: 7

У Васи есть словарь, состоящий из нескольких стобуквенных слов, содержащих только буквы $A$ и $B.$ В каждую клетку таблицы $100× 100$ Вася хочет вписать либо букву $A,$ либо букву $B$ так, чтобы каждый столбец таблицы был словом из словаря при чтении сверху вниз, и каждая строка таблицы была словом из словаря при чтении слева направо. Чему равно наименьшее натуральное число $m$ такое, что если в словаре есть не менее $m$ различных слов, то Вася заведомо сможет заполнить таблицу нужным образом, независимо от того, какие слова находятся в словаре?

Подсказки к задаче

Подсказка 1

Для начала давайте попробуем построить пример на как можно больше слов в словаре, чтоб таблицу составить было нельзя. Для этого попробуйте рассмотреть слова с определённым началом.

Подсказка 2

Давайте рассмотрим слова, которые начинаются на букву A, кроме слова из 100 букв A. Можно ли для таких слов составить таблицу?

Подсказка 3

Правильно, нельзя! А сколько же слов в этом словаре?

Подсказка 4

Верно, 2⁹⁹ - 1! Теперь попробуйте доказать, что для словаря из 2⁹⁹ слов всегда можно составить таблицу. Для начала разберемся со словами из 100 одинаковых букв. Если в словаре такое слово присутствует, то можно ли составить таблицу?

Подсказка 5

Ага, можно! Просто возьмем и заполним таблицу буквами этого слова. Теперь давайте забудем про слова из 100 одинаковых букв. Попробуйте разбить оставшиеся слова на пары так, чтобы если мы возьмем два слова из любой из этих пар, то таблицу мы сможем составить.

Подсказка 6

Попробуйте рассмотреть пары слов, которые получаются заменой всех букв B на A, а всех букв A на B.

Показать ответ и решение

Рассмотрим следующий словарь из $299− 1$ слов: все слова, начинающиеся с буквы $A,$ кроме слова из 100 букв $A.$ Тогда Вася не сможет заполнить таблицу. Действительно, в верхней строке будет какое-то слово, содержащее букву $B,$ но тогда в столбце с этой буквой слово должно начинаться на $B.$

Докажем, если в $D$ не менее $99 2$ слов, то Вася сможет заполнить таблицу. Если в $D$ есть слово из ста букв $A,$ то можно заполнить всю таблицу только буквами $A.$ Аналогично с $B.$ Разобьем все остальные слова на пары: слово и инверсное ему (то есть получающееся заменой всех $A$ на $B$ и всех $B$ на $A$ ). Пар $99 2 − 1,$ а слов в словаре $99 2 .$ Следовательно, найдутся два слова из одной пары. Пусть это слова $w$ (начинается с $A$ ) и $-- w$ (начинается с $B$ ). Запишем в верхнюю строку слово $w.$ Далее в каждом столбце, если он начинается с $A$ запишем $w,$ если он начинается с $B,$ запишем $-- w.$ Нетрудно проверить, что во всех строках также будут записаны $w$ или $-- w.$

Ответ:

$299$

Ошибка.
Попробуйте повторить позже

Задача 88#75917Максимум баллов за задание: 7

На клетках $c3$ и $h7$ стоят белая и черная ладьи. Двое по очереди, начиная с белых, двигают ладью своего цвета на любое число клеток по горизонтали или вертикали. Запрещается ходить ладьей под бой другой ладьи и останавливаться на клетке, на которой эта ладья уже была ранее. Тот, кто не может сделать ход, проиграл. Кто выигрывает при правильной игре?

Подсказки к задаче

Подсказка 1

Попробуем создать симметричную стратегию. Для этого можно разбить строки и столбцы на пары. Как это можно сделать?

Подсказка 2

Верно! Разбиваем вертикали, объединяя c и h в пару и горизонтали, объединяя третью и седьмую в пару. А что произошло с клетками?

Подсказка 3

Конечно, они тоже разбились на пары: парная клетка лежит на пересечений парной вертикали и парной горизонтали к тем, в которых находится данная клетка. Какую стратегию может применить второй игрок?

Показать ответ и решение

Разобьём вертикали на пары, поместив при этом вертикали $c$ и $h$ в одну пару. Также разобьём на пары горизонтали, поместив при этом $3$ -ю и $7$ -ю в одну пару. Тогда и клетки разобьются на пары: парная клетка лежит на пересечении парной горизонтали и парной вертикали. Ладьи на парных клетках друг друга не бьют. Стратегия второго: на любой ход первого отвечать ходом в парную клетку. Это возможно: если первый сделал ход ладьёй из одной клетки в другую, то эти клетки лежат в одном ряду. Но тогда парные к ним клетки лежат в парном ряду, и ход ладьёй между ними тоже возможен. Таким образом, всегда после хода второго все непосещённые клетки будут состоять из указанных пар, и второй всегда будет попадать на непосещённую клетку. Значит, именно первый когда-то не сможет сделать ход и проиграет.

Ответ:

Второй

Ошибка.
Попробуйте повторить позже

Задача 89#79254Максимум баллов за задание: 7

Дано неотрицательное число $C.$ В каждой клетке квадрата $n× n$ сидит жук. Для каждой пары жуков посчитали расстояние между ними. После этого каждый жук переполз в одну из соседних по стороне клеток, причем в каждой клетке снова сидит ровно $1$ жук. Для каждой пары жуков снова посчитали расстояние между ними. Оказалось, что для каждого натурального $n$ количество не изменившихся расстояний не меньше $4 Cn .$ Чему может быть равно $C?$

Показать ответ и решение

Докажем, что для любого натурального $n$ найдутся хотя бы $n2 8$ пар жуков, расстояния между которыми не изменилось. Пронумеруем строки сверху вниз, а столбцы слева направо числами $1,2,3,...,n.$ Построим ориентированный граф, вершинами которого будут клетки доски. Будем проводить ребро из клетки $K$ в клетку $L,$ если жук переполз из клетки $K$ в клетку $L.$ По условию из каждой вершины построенного графа выходит ровно $1$ ребро, и в каждую вершину графа входит ровно $1$ ребро. Значит, граф разбивается на циклы (некоторые циклы могут быть длины $2$ ). Рассмотрим один из таких циклов. Заметим, что он поровну раз переходит из строчки $i$ в строчку $i+1$ и обратно. Значит, и всего ребер из строки в строку $i+1$ и обратно будет поровну. В частности, количество жуков, сдвинувшихся влево, равно количеству жуков, сдвинувшихся вправо. Аналогичные рассуждения можно провести и со столбцами. Обозначим количество жуков, сдвинувшихся влево через $a,$ количество жуков, сдвинувшихся вправо — через $b.$ Понятно, что $2 a +b= n ∕2.$ Заметим, что расстояние между жуками, сдвинувшимися в одном направлении, не изменилось. Тогда уже имеем $a(a− 1) b(b− 1) 2⋅---2--+ 2⋅---2--$ подходящих пар. Для $i= 1,2,3,...,n− 1$ обозначим через $ai$ количество жуков, сместившихся из строчки $i$ в строчку $i+1,$ через $bi$ — количество жуков, сместившихся из столбца $i$ в столбец $i+ 1.$ Тогда $a1+ a2+ ...+an−1 = a,b1 +b2+ ...+ bn−1 = b.$ Заметим, что между жуком, перешедшим из строчки $i$ в строчку $i+ 1$ и жуком, перешедшим из строчки $i+ 1$ в строчку $i,$ расстояние не изменилось (и тех, и других ровно $ai$ ). Тогда нашли еще

a21+ a22+...+a2n−1+ b21+b22+ ...+ bn−1 ≥ a2+-b2 n− 1

подходящих пар. То есть всего нужных нам пар не меньше, чем

a(a−-1) b(b−-1) a2+b2- --n- 2 2 n2 --n- (a-+b)2 n2 --n- n4 n2 2 + 2⋅ 2 + n − 1 =n − 1(a + b)− 2 ≥n − 1 ⋅ 2 − 2 = n − 1 ⋅8 − 2 =

n4 n4− 4n2(n− 1) n4 (n− 2)2 n4 = 8-+ -----8------= 8-+ n2⋅--8---≥ -8

Поймем, в каких случаях расстояние между жуками не изменяется. Пусть разность между абсциссами жуков равна $x,$ а разность между ординатами равна $y.$ Тогда после передвижений квадрат расстояния между жуками может быть равен $x2+ y2,$ (если жуки движутся в одном направлении), либо $x2+(y+ 2)2$ или $(x+2)2+ y2$ (если жуки движутся в противоположных направлениях), что нам не походит, либо $(x +1)2+ (y+ 1)2,$ что нам также не подходит, также как и $(x− 1)2+ (y− 1)2,$ либо $(x +1)2+(y− 1)2$ или наоборот. В последнем случае имеем $2y+1 − 2x+ 1= 0,$ откуда $x =y +1$ или наоборот.

Предположим, что существует $C > 1 8$ такое, что для любого натурального $n$ и любых действиях жуков количество пар с не изменившимся расстоянием не меньше $4 Cn .$ Пусть $n$ делится на $4.$ Разобьем доску на квадраты $2×2$ и раскрасим эти квадраты в шахматном порядке. Пусть в черных квадратах жуки будут смещаться горизонтально, оставаясь при этом внутри их квадратов, а в белых — аналогично, только жуки будут смещаться вертикально. Заметим, что из предыдущего абзаца и непосредственной проверки следует, что для фиксированного жука есть ровно $2 n∕4− 1+ n∕2$ жуков, расстояние от которых до выбранного жука не изменилось (жуки,стоящие на клетках того же цвета, сместившиеся в том же направлении, а также жуки, стоящие, поменявшиеся с выбранным строками). Итого, все подходящих пар ровно $2 2 4 3 n-⋅(n∕4−-1+-n∕2) = n-+ n-−-2, 2 8 4$ что меньше $Cn2$ при достаточно больших $n$ для любого $C > 1 , 8$ откуда $1 C ≤ 8.$

Ответ:

$C ≤ 1 8$

Ошибка.
Попробуйте повторить позже

Задача 90#89869Максимум баллов за задание: 7

За какое наименьшее число операций можно перекрасить в чёрный цвет белую доску $100× 100,$ если за одну операцию можно перекрасить в противоположный цвет любые 99 клеток любой горизонтали или любой вертикали?

Источники: СПБГОР - 2023, 11.4 (см.pdmi.ras.ru)

Подсказки к задаче

Подсказка 1

Задача вида «оценка + пример», поэтому хочется понять ответ. Какой не очень сложный пример можно придумать?

Подсказка 2

Покрасить в чёрный первые 99 клеток в каждом столбце, после этого останется белой только последняя строка. Будем называть «операцией» перекрашивание всех клеток в строке кроме данной. Что будет, если применить операцию для каждой клетке в последней строке?

Подсказка 3

Конечно, вся доска станет чёрной, что и требовалось.
Но просто считать «операции» сложно. Хочется их разбить на несколько типов. Например, что будет если применить операцию к двум клеткам из одной строки?

Подсказка 4

Перекрасятся только эти две выбранные клетки. Тогда можно объединить в такие операции в пары в строках и в столбах. Пусть после этого осталось p ходов в строчках и q ходов в столбцах. Какие простые ограничения можно сразу сделать для p и q?

Подсказка 5

p, q ≤ 100, так как в противном случае найдётся две клетки в одной строке или столбе, которые можно объединить в пару. Что будет, если одно из чисел равно 100? Рассмотрите несколько случаев для значения второго числа. А когда оба не более 99?
Важно понимать, что после p ходов в строках и q в столбцах оставшиеся клетки перекрашиваются однозначно операциями для пар клеток, а отсюда можно получить нижнюю оценку на количество ходов.

Подсказка 6

Также полезно понимать, могут ли p и q быть разной чётности, может ли тогда вся доска стать чёрной?

Показать ответ и решение

Оценка.

Будем говорить, что выполнили операцию в клетке, если перекрасили все 99 клеток в строке или столбце кроме данной. Пусть были операции над строками в клетках $a1,a2,...,an$ и над столбцами $b1,b2,...,bk$ .

Отметим два факта:

1.: Количество операций четно, ведь операция меняет четность числа черных клеток, тогда достаточно показать, что $n +k ≥199$ .
2.: Порядок выполнения операций не влияет на конечный результат перекрашивания.

Если дважды к одной клетке в строке применить операцию, то ничего не изменится, поэтому можно считать, что таких ходов нет. Аналогично для столбцов. Если в строчке применить операцию к двум различным клеткам, то результатом этих двух ходов будет перекрашивание рассматриваемых клеток. Будем выделять пары таких ходов в столбцах и строках, обозначим такую пару ходов как операцию I-го типа (пусть их будет $r$ штук). Пусть после этого осталось $p$ ходов в строчках (обозначим как операцию II-го типа), $q$ ходов в столбцах (обозначим как операцию III-го типа) Отметим, что $p,q ≤100$ , так как в противном случае найдётся две клетки в одной строке или столбе, которые можно объединить в операцию I-го типа. Тогда хотим доказать, что

p+q +2r≥ 199

Рассмотрим несколько случаев:

1.

$p,q ≤ 99$

Тогда клеток НЕ находящихся в столбцах и строках, где были операции II-го или III-го типа $(100− p)⋅(100 − q)$ , а любая операция I-го типа перекрашивает не более двух клеток, тогда всего ходов хотя бы

p+ q+ 2⋅ (100−-p)(100− q)= 1002− 99(p+q)+ pq = 199+ (99 − p)(99− q)≥199 2

2.

$p =100,q =0$

После выполнения операций II-го типа останется ровно 100 белых клеток. $q = 0$ , значит, операций III-го типа нет, тогда для перекрашивания белых клеток понадобиться хотя бы 50 операций I-го типа. Получаем, что всего операций не меньше, чем $(100+2 ⋅50)= 200$ .

3.

$p =100,q ≥2$

После операций II-го типа останется ровно 100 белых клеток, причём по одной в каждой строке. После выполнения операций III-го типа белых клеток останется хотя бы $99q− 100$ (так как в каждом из q столбцов перекрашивается по 99 клеток, все они чёрные, кроме, может быть, 100 белых клеток, тогда после применения операции белыми станут хотя бы $99q − 100$ ). Тогда потребуется еще хотя бы $99q− 100$ ходов, значит, всего шагов не менее

100+ q+99q− 100 ≥200

4.

$p =100,q$ : — нечётное.

Этот случай невозможен по чётности количества ходов.

Случаи для $q = 100$ аналогичны случаям для $p =100$ .

_________________________________________________________________________________________________________________________________________________________________________________

Пример.

Выполним операцию III-го типа ко всем клеткам из первой строки. Это 100 ходов. Далее применим операцию I-го типа к парам из клеток первой строки (на пары разобьем последовательно , то есть 1-ая и 2-ая клетки, 3-яя и 4-ая, $...$ , 99-ая и 100-ая). Это ещё $2 ⋅50 =100$ ходов. Итого 200.

Ответ: 200

Ошибка.
Попробуйте повторить позже

Задача 91#92129Максимум баллов за задание: 7

В каждой клетке квадрата $10×10$ сидит жук. Для каждой пары жуков посчитали расстояние между ними. После этого каждый жук переполз в одну из соседних по стороне клеток, причем в каждой клетке снова сидит ровно $1$ жук. Для каждой пары жуков снова посчитали расстояние между ними. Докажите, что хотя бы $1200$ расстояний не изменились.

Подсказки к задаче

Подсказки 1

При каком естественном условии расстояние между жуками не изменится после их перемещения?

Показать доказательство

Пронумеруем строки сверху вниз, а столбцы слева направо числами $1,2,3,...,10.$ Построим ориентированный граф, вершинами которого будут клетки доски. Будем проводить ребро из клетки $K$ в клетку $L,$ если жук переполз из клетки $K$ в клетку $L.$ По условию из каждой вершины построенного графа выходит ровно $1$ ребро, и в каждую вершину графа входит ровно $1$ ребро. Значит, граф разбивается на циклы (некоторые циклы могут быть длины $2).$ Рассмотрим один из таких циклов. Заметим, что он поровну раз переходит из строчки $i$ в строчку $i+ 1$ и обратно. Значит, и всего ребер из строки в строку $i+ 1$ и обратно будет поровну. В частности, количество жуков, сдвинувшихся влево, равно количеству жуков, сдвинувшихся вправо. Аналогичные рассуждения можно провести и со столбцами. Обозначим количество жуков, сдвинувшихся влево через $a,$ количество жуков, сдвинувшихся вправо — через $b.$ Понятно, что $2 a+ b= 10∕2= 50.$ Заметим, что расстояние между жуками, сдвинувшимися в одном направлении, не изменилось. Тогда имеем хотя бы

a(a− 1) b(b− 1) (a+ b)2 2 ⋅--2---+ 2⋅--2---= a2 +b2− a− b≥ --2---− (a+ b)=1250− 50 =1200

пар жуков, расстояние между которыми не изменилось.

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 92#94344Максимум баллов за задание: 7

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

Подсказки к задаче

Подсказка 1

Заметим, что любая клетка левого верхнего квадрата (n-1)×(n-1) является вершиной какого-то прямоугольника с тремя точками вне левого верхнего квадрата (n-1)×(n-1). Как тогда можно оценить количество раскрасок этого квадрата?

Подсказка 2

Верно, для любой изначальной раскраски квадрата n×n можно получить любую раскраску левого верхнего квадрата (n-1)×(n-1), например таких, где он весь белый. Таких существует 2²ⁿ⁻¹, а значит, ответ не более, чем это число. Будем теперь доказывать, что 2²ⁿ⁻¹ раскрасок, которые не получаются друг из друга, существуют. Рассмотрим произвольную строку или столбец. Какой инвариант для неё существует?

Подсказка 3

Верно, чётность. Для различных раскрасок n×n, при которых верхний левый (n-1)×(n-1) белый различаются какие-то клетки, а значит, в чётность в некоторой строке или столбце. Потому их нельзя получить друг из друга.

Показать ответ и решение

Покажем, что при $k >22n−1$ существует две эквивалентные раскраски. Покажем, что любую раскраску разрешёнными операциями можно перевести в раскраску, в которой верхний левый квадрат $(n− 1)× (n− 1)$ — белый. Действительно, для каждой клетки в квадрате $(n− 1)×(n− 1)$ можно подобрать $3$ клетки, лежащие вне него так, чтобы они образовывали необходимий прямоугольник. Таким образом, мы можем перекрасить любую клетку. А так как раскрасок, в которых верхний левый квадрат $(n − 1)× (n − 1)$ — белый, $2n−1 2 ,$ то по принципу Дирихле найдутся две совпадающих раскраски. Тогда две соответствующие исходные раскраски можно перевести друг в друга.

Покажем, что все $2n−1 2$ раскрасок, в которых верхний левый квадрат $(n − 1)× (n − 1)$ — белый, нельзя перевести друг в друга операциями. Заметим, что чётность количества чёрных клеток в $i$ -м столбце — инвариант. Аналогичное утверждение верно для строк. А так как в выбранных раскрасках левый верхний квадрат $(n− 1)×(n− 1)$ — белый, покраска оставшихся строки и столбца определяет четность количества чёрных клеток во всех строках и столбцах.

Ответ:

$22n−1$

Ошибка.
Попробуйте повторить позже

Задача 93#101707Максимум баллов за задание: 7

Некоторую клетчатую фигуру Вася разбил на $L$ -тетрамино ( $4$ -клеточные фигуры в виде буквы $L$ ), а Петя — на доминошки (прямоугольники из двух клеток). Могло ли в Петином разбиении вертикальных доминошек оказаться ровно на $50$ больше, чем горизонтальных?

Подсказки к задаче

Подсказка 1

Когда мы видим некоторую клетчатую задачу, у нас есть несколько базовых идей, в духе раскраски, подсчёта двумя способами и прочее. Если мы предполагаем, что нам здесь надо использовать раскраску, то нам нужно, чтобы наша раскраска по некоторому параметру отличала бы тетраминошку и доминошку. К примеру, поэтому шахматная не подойдёт. Какую же тогда нам раскраску выбрать и что вообще мы планируем красить? Как нам тогда использовать это отличие по данному параметру для решения?

Подсказка 2

Удачным здесь будет раскрасить столбцы/строки в шахматной раскраске каждый. То есть первый — черный, второй — белый и так далее. Какой параметр тогда отличает доминошки от тетраминошек? А может он и разные доминошки отличает?

Подсказка 3

Параметр разности чёрных и белых клеток подходит в данной задаче, так как на вертикальных он равен +-2, на горизонтальных 0, а на тетраминошках равен +-2. Это значит, что мы теперь можем предположить противное из условия, понять, сколько у нас есть каждого типа фигурок и попытаться прийти к противоречию. Ровно для противоречия мы и ввели раскраску. Как связано количество фигурок разного типа? Что это дает с учётом нашего параметра?

Подсказка 4

Количество тетраминошек в 2 раза меньше, чем доминошек. Значит, если у нас n горизонтальных, n + 50 вертикальных, тогда тетраминошек n + 25. Значит, сумма чисел +-2 в количестве n + 25 штук равна сумме чисел +-2 в количестве n + 50 штук. В чём же противоречие?

Показать ответ и решение

Покрасим столбцы фигуры, чередуясь, в черный и белый цвета.

Пусть в Петином разбиении $n$ горизонтальных домино и $n+50$ вертикальных домино. Тогда в Васином разбиении $n +25$ тетрамино. Горизонтальные домино содержат одну черную клетку и одну белую и вносят вклад 0 в разность количества черных и белых клеток фигуры. А каждая вертикальная доминошка и каждая $L$ -тетраминошка вносит вклад $± 2$ в эту разность.

Но тогда если мы посчитаем разницу черных и белых клеток в фигуре через доминошки и через тетраминошки, то получим, что сумма $n +50$ чисел $± 2$ равна сумме $n +25$ чисел $±2$ , чего быть не может по модулю 4.

Ответ: нет

Ошибка.
Попробуйте повторить позже

Задача 94#101757Максимум баллов за задание: 7

Клетки доски $n× n$ покрашены в черный и белый цвет. Известно, что для каждой черной клетки в «кресте» из строчки и столбца, на пересечении которых она находится, не менее $2k$ $(k< n)$ белых клеток. Какое наибольшее количество клеток доски могут быть черными?

Подсказки к задаче

Подсказка 1

Давайте придумаем некоторый пример. Интуитивно мы хотим, чтобы в нем для каждой черной клетки количество белых, находящихся в ее кресте, было как можно более приближено к 2k. Можно ли придумать пример, когда для всех черных клеток это число равно 2k?

Подсказка 2

Да, пусть в первой строчке белыми будут клетки 1, 2, …, k, во второй — 2, 3, …, k+1 (то есть на каждой следующей строчке сдвигаем все на 1 вправо, возможно, с переносом в начало). Сколько черных клеток получается при такой раскраске?

Подсказка 3

В каждой строке количество белых клеток равно k, а значит, во всей доске kn, следовательно, количество черных клеток при такой раскраске равно n²-nk. Давайте докажем, что это наибольшее число клеток.

Подсказка 4

Мы хотим получить оценку на количество черных клеток. При этом достаточно показать, что количество белых клеток всегда по крайней мере nk. Предположим, что в строчках стоят a_1, a_2, …, a_n белых клеток, а в столбцах — b_1, b_2, ...., b_n белых клеток. Заметим, что в i-строке пересечении с n-a_i столбцами у неё стоят черные клетки. Значит, в каждом из этих столбцов не менее 2k-a_i белых клеток. Просуммируем такие величины по всем строкам. Дайте оценку сверху на количество посчитанных раз фиксированной белой клетке из j-столбца.

Подсказка 5

Заметим, что белую клетку из j-ого столбца мы посчитали не более n-b_j раз. То есть имеем неравенство (n-a_1)(2k-a_1)+(n-a_2)(2k-a_2)+...+(n-a_n)(2k-a_n) ≤ b_1(n-b_1)+b_2(n-b_2)+...+b_n(n-b_n). Наша цель --- отойти от использования переменных a_1, …, a_n, b_1, …, b_n и перейти к количеству белых клеток s=a_1+a_2+...+a_n. Для этого преобразуйте исходное неравенство.

Подсказка 6

После преобразований мы получим 2n^2k-2(n+k)(a_1+a_2+...+a_n)+a_1^2+a_2^2+...+a_n^2+b_1^2+b_2^2+....+b_n^2 ≤ 0. Как мы можем оценить снизу сумму квадратов через сумму переменных? Это нужно, чтобы окончательно перейти к неравенству, в котором будут фигурировать только переменный n, k и s.

Подсказка 7

По неравенству между средним квадратичным и арифметическим, мы имеем a_1^2+a_2^2+...+a_n^2 <= (a_1+a_2+...+a_n)^2/n. То есть мы можем переписать неравенство в виде 2n^2k-2(n+k)(a_1+a_2+...+a_n)+ (a_1+a_2+...+a_n)^2/n+ (b_1+b_2+...+b_n)^2/n = 2(s^2/n - (n+k)s+n^2k) ≤ 0. Теперь у нас есть все, чтобы получить оценку на количество s белых клеток.

Подсказка 8

Для этого достаточно показать, что s^2/n ≥ sk - nk^2. Докажите данное неравенство и поставьте его в полученную на предыдущем шаге оценку.

Показать ответ и решение

Оценка. Предположим, что в строчках стоят $a ,a,...,a 1 2 n$ белых клеток, а в столбцах — $b ,b ,...,b 1 2 n$ белых клеток. Рассмотрим $i$ -ую строку. Заметим, что в пересечении с $n− ai$ столбцами у неё стоят черные клетки. Значит, в каждом из этих столбцов не менее $2k− ai$ белых клеток. Просуммируем такие величины по всем строкам. Заметим, что белую клетку из $j$ -ого столбца мы посчитали не более $n − bj$ раз. То есть имеем неравенство

n∑ ∑n (n − ai)(2k− ai)≤ bi(n− bi) i=1 i=1

Раскрыв скобки и перенеся все в левую сторону, а также воспользовавшись тем, что

∑n n∑ ai = bi i=1 i=1

имеем

( ) ( ) ( ) 2 ∑n n∑ 2 n∑ 2 2n k− 2(n+ k) i=1ai + i=1ai + i=1bi ≤ 0

По неравенству между средним квадратическим и арифметическим, имеем

∑n 1(∑n )2 ∑n 1 (∑n )2 a2i ≥n ai ; b2i ≥ n bi i=1 i=1 i=1 i=1

Тогда

(∑n ) 2( n∑ )2 2n2k− 2(n +k) ai + n ai ≤ 0 i=1 i=1

Обозначим количество белых клеток через

∑n s= i=1 ai

Тогда после сокращения на $2$ получаем

s2− (n +k)s+ n2k ≤0 n

С другой стороны, по неравенству между средним арифметическим и геометрическим, имеем

s2 ∘ s2---- n-+ nk2 ≥2 n-⋅nk2 = 2sk

То есть

2sk− (n +k)s+ n2k − k2n≤ 0

откуда получаем

s ≥ kn(n−-k)= kn n− k

Пример. Пусть в первой строчке белыми будут клетки $1,2,...,k,$ во второй — $2,3,...,k +1,$ …(то есть на каждой следующей строчке сдвигаем все на $1$ вправо, возможно, с переносом в начало). Таким образом, в каждой строчке и в каждом столбце будет ровно $k$ белых клеток. Оставшиеся клетки будут черными, в кресте каждой из них будет ровно $k+k = 2k$ пустых клеток.

$PIC$

Ответ:

$n2− nk$

Ошибка.
Попробуйте повторить позже

Задача 95#104642Максимум баллов за задание: 7

Плиточник Аркадий получил заказ переложить плитку на дне бассейна размером $6× 6$ плиток, так чтобы все плитки имели цвет $3.$ Изначально на дне бассейна лежат плитки трех разных цветов как на рисунке. Аркадий работает так: выбирает две соседние по стороне плиточки, разбивает их и заменяет плитку цвета $1$ на плитку цвета $2,$ плитку цвета $2$ — на плитку цвета $3,$ плитку цвета $3$ — на плитку цвета $1.$ Какое наименьшее число плиток он может испортить прежде чем выполнит заказ?

$PIC$

Показать ответ и решение

Заметим, что на дне имеется $12$ плиток цвета $1.$ Каждую из них нужно перекрасить дважды, притом за одно перекрашивание перекрашивается не более одной такой плитки. Значит, нужно хотя бы $12⋅2= 24$ перекрашивания.

Построим пример. Давайте рассмотрим трёхклеточный уголок, у которого в концах стоят $2,$ а в середине — $1.$ Ясно, что за два перекрашивания его можно превратить в уголок с тремя тройками. Теперь рассмотрим квадрат $2×2,$ состоящий из уголка, у которого в центре стоит $2,$ а по краям единицы, и клетка с $3.$ Его тоже можно перекрасить так, чтобы он состоял из троек. Давайте сначала перекрасим одну доминошку с $1$ и $2.$ Потом перекрасим доминошку с этой же единицей и тройкой. Теперь дважды перекрасим доминошку с другой единицей и тройкой (которая после предыдущего перекрашивания стала единицей). Осталось разбить дно на такие фигуры. Давайте занумеруем клетки по вертикали и горизонтали числами от $0$ до $5.$ Тогда можно взять уголки с центральными клетками в $(0,0),(3,0),(0,3),(3,3)$ и квадратики с нижней левой клеткой в координатах $(1,1),(1,4),(4,1),(4,4).$

Ответ:

$24$

Ошибка.
Попробуйте повторить позже

Задача 96#118948Максимум баллов за задание: 7

Для какого наименьшего натурального $n$ квадрат $4× 4$ можно разрезать на $n$ прямоугольников с периметрами $1,2,3,...,n?$ Стороны прямоугольников параллельны сторонам квадрата и могут иметь произвольные длины.

Показать ответ и решение

Оценка. Предположим, что можно разрезать для $n ≤8.$ Пусть периметр прямоугольника равен $p.$ Тогда сумма его сторон $a+ b= p∕2.$ Тогда $√-- 2 ab≤ p∕2,$ откуда площадь прямоугольника не больше $2 p∕16.$ То есть суммарная покрываемая площадь прямоугольников не больше, чем

1 2 2 2 16(1 +2 + ...+ n) ≥4⋅4

Заметим, что при $n =8$ данное неравенство не выполнено, откуда $n ≥ 9.$

Пример. Как на рисунке. Клеточки квадрата имеют сторону $14.$

$PIC$

Ответ:

$n =9$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 97#118959Максимум баллов за задание: 7

Даны натуральные числа $k< n.$ Клетки доски $n× n$ покрашены в черный и белый цвет. Известно, что для каждой черной клетки в «кресте» из строчки и столбца, на пересечении которых она находится, не менее $2k$ белых клеток. Какое наибольшее количество клеток доски могут быть черными?

Показать ответ и решение

(n − a1)(2k− a1)+(n− a2)(2k− a2)+ ...+ (n− an)(2k− an)≤b1(n− b1)+ b2(n− b2)+ ...+ bn(n− bn)

Раскрыв скобки и перенеся все в левую сторону, а также воспользовавшись тем, что $a +a + ...+ a = b +b + ...+ b, 1 2 n 1 2 n$ имеем

2 2 2 2 2 2 2 2n k− 2(n +k)(a1 +a2+ ...+ an)+ a1+ a2+...+an+ b1+ b2+ ...+ bn ≤ 0

Оценим $a2+a2+ ...+ a2≥ 1(a1+a2+ ...+ an)2. 1 2 n n$ Аналогично

2 2 2 1 2 1 2 b1+b2+ ...+ bn ≥ n(b1+ a2+ ...+bn) = n(a1+a2+ ...+ an)

Тогда

2 2 2 2n k− 2(n+ k)(a1+ a2 +...+an)+ n(a1+a2+ ...+ an)≤ 0

Обозначим количество белых клеток через $x= a1+ a2+...+an.$ Тогда после сокращения на $2$ получаем

2 x-− (n +k)x+ n2k≤ 0 n

С другой стороны $∘ ------ xn2+nk2 ≥2 xn2⋅nk2 = 2xk.$ То есть

2xk− (n +k)x+ n2k − k2n≤ 0

откуда получаем $x≥ knn(n−−kk)= kn.$

Пример. Пусть в первой строчке белыми будут клетки $1,2,...,k,$ во второй — $2,3,...,k+ 1,$ …(то есть на каждой следующей строчке сдвигаем все на $1$ вправо, возможно, с переносом в начало). Таким образом, в каждой строчке и в каждом столбце будет ровно $k$ белых клеток. Оставшиеся клетки будут черными, в кресте каждой из них будет ровно $k+k = 2k$ пустых клеток.

Ответ:

$n2− nk$

Ошибка.
Попробуйте повторить позже

Задача 98#128454Максимум баллов за задание: 7

Квадрат $100×100$ разбит на квадраты $2× 2.$ Потом его разбивают на доминошки (прямоугольники $1 ×2$ и $2× 1).$ Какое наименьшее количество доминошек могло оказаться внутри квадратов разбиения?

Источники: ВСОШ, ЗЭ, 2023, 10.6 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Нам необходимо сделать оценку снизу, то есть предъявить набор доминошек (возможно, просто доказать его существование), которые точно попадут в квадраты разбиения. Подумайте, как можно "ловить" подобные доминошки?

Подсказка 2:

Находить их в явном виде плохо, это просто не сделать (разбиений на домино очень много). Значит, нужно найти некоторые объекты, которые будут их "детектировать", то есть просто говорить, что они точно есть. Подумаем, какие самые тривиальные детекторы могут быть?

Подсказка 3:

Например, угловые клетки. В каждом углу доски нужная доминошка точно найдётся. Попробуем выделить несколько более высокоуровневые признаки. Почему доминошка, которая задевает угловую клетку, подходит?

Подсказка 4:

Потому что пересекает границу квадрата с нечётной стороной, а все такие границы лежать внутри квадратов разбиения, значит, такие доминошки всегда попадают в квадраты. Хм, что же хочется сделать?

Подсказка 5:

В такие моменты полезно попробовать обобщить идею! Как же будет звучать наше предположение?

Подсказка 6:

Для каждого квадрата с нечётной стороны, который исходит из левого нижнего угла, найдётся доминошка на его границе. Таким образом, мы сможем найти 50 нужных доминошек.

Подсказка 7:

Теперь нужно доказать, что для любого квадрата такая доминошка найдётся. Сделайте это самостоятельно, но скажем следующее: квадраты нечётные, а в доминошке ровно 2 клетки).

Подсказка 8:

Итого, мы нашли 50 требуемых доминошек. Кажется, можно найти больше...

Подсказка 9:

Осознайте, каким образом можно найти ещё 50 доминошек. Итого, есть оценка на 100 доминошек. Может, можно ещё больше?

Подсказка 10:

Спустя несколько попыток Вы, скорее всего, потерпели неудачу. Может, тогда пора переходить к примеру?

Подсказка 11:

Пример за Вами, однако скажем, что он достаточно "однородный"... Успехов!

Показать ответ и решение

Пример. Верхнюю и нижнюю горизонтали разобьём на горизонтальные доминошки — они окажутся в квадратах $2×2.$ Остальной прямоугольник $98× 100$ разобьём на вертикальные доминошки — они не окажутся в квадратах $2 ×2.$

Оценка. Рассмотрим квадраты $A1,$ $A3,...,A99$ размеров $1× 1,$ $3× 3,...,99× 99,$ у которых левый нижний угол совпадает с левым нижним углом исходного квадрата $100 ×100.$ Для каждого из квадратов $Ai$ $(i= 1,3,...,99)$ найдётся доминошка $Xi,$ пересекающая его сторону (поскольку квадраты нечётной площади не разбиваются на доминошки). Легко видеть, что $Xi$ лежит внутри квадратика $2× 2$ из разбиения. Аналогично, рассматривая квадраты $B1,B3,...,B99$ размеров $1×1,$ $3× 3,...,99× 99,$ у которых правый верхний угол совпадает с правым верхним углом исходного квадрата $100× 100,$ находим ещё $50$ нужных нам доминошек $Yj$ ( $j = 1,3,5,...,99).$ Это завершает решение (очевидно, что все доминошки $X1,$ $X3,...,X99,$ $Y1,$ $Y3,...,Y99$ различны).

Ответ:

100

Ошибка.
Попробуйте повторить позже

Задача 99#131038Максимум баллов за задание: 7

Дано натуральное число $n.$ На клетчатой доске $2n× 2n$ расставили $2n$ ладей так, что никакие две не стоят в одной горизонтали или одной вертикали. После этого доску разрезали по линиям сетки на две связных части, симметричных друг другу относительно центра доски. Какое наибольшее количество ладей могло оказаться в одной из частей? (Клетчатая фигура называется связной, если по этой фигуре от любой её клетки можно добраться до любой другой, переходя каждый раз в соседнюю по стороне клетку.)

Источники: ВСОШ, РЭ, 2023, 9.3 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

В подобных задачах часто ответ выражается через переменную и тривиальную константу (0, −1, +1). Навряд ли, ответ будет n + 7 или n + 5, но ничего нельзя говорить наверняка. Начнём с малого. Какую точно оценку мы можем гарантировать?

Подсказка 2:

n можно обеспечить при любом разбиении (банально взять ту часть, где больше). Тогда ответ, скорее всего, будет либо около n, либо около 2n (около — значит ±1 или 0). Если с этими вариантами потерпим крах, будем думать дальше. Итак, хочется проверить сначала более простые случаи. Какой же случай будет самым простым?

Подсказка 3:

Кажется, 2n, потому что чем больше ладей, тем проще получить противоречие. Но ещё не факт, что мы его получим. Попробуем сначала построить пример на 2n.

Подсказка 4:

Спустя несколько попыток вы поймёте, что это гиблый номер. Значит, хотим доказать, что 2n ладей не могут находиться в одной связной части. Вспомним условие на ладьи...

Подсказка 5:

Никакие две ладьи не стоят в одной вертикали или горизонтали. Осознайте, что в каждой вертикали и горизонтали есть ровно одна ладья. Какой тогда способ доказать, что в каждой части не более 2n − 1 ладьи, может оказаться рабочим?

Подсказка 6:

Доказать, что в каждой части есть целиком либо столбец, либо строка. Задача не самая простая. Какие строки и столбцы удобнее всего использовать?

Подсказка 7:

Крайние, ведь за ними следить явно проще, чем за теми, что в центре. А где крайние строки и столбцы, недалеко и до угловых клеток...

Подсказка 8:

С помощью них докажите, что в каждой части есть то, что нам нужно. Не забывайте, про центральную симметричность частей.

Подсказка 9:

Мы поняли, что ладей ≤ 2n − 1. Попробуем же теперь построить пример на 2n − 1...

Подсказка 10:

До него догадайтесь самостоятельно, но скажем одно: диагонали Вам в помощь! Успехов!

Показать ответ и решение

Заметим, что в каждой вертикали и каждой горизонтали стоит ровно по одной ладье.

Покажем сначала, что все $2n$ ладей не могли попасть в одну часть. Пусть $A,B,C,D$ — угловые клетки доски в порядке обхода против часовой стрелки. Из симметрии, $A$ и $C$ должны принадлежать разным частям, как и $B$ и $D.$ Это значит, что либо $A$ и $B,$ либо $A$ и $D$ лежат в одной части, а остальные две клетки — в другой.

Пусть для определённости $A$ и $B$ лежат в части I. Тогда все граничные клетки между ними также должны лежать в части I; действительно, если какая-то такая клетка $X$ лежит в части II, то в ней же лежит какой-то путь из $X$ в $C,$ а в части I лежит какой-то путь из $A$ в $B;$ но эти пути должны иметь общую клетку, что невозможно.

Значит, вся горизонталь между клетками $A$ и $B$ лежит в части I, то есть в ней должна быть хотя бы одна ладья. Аналогично, в части II тоже есть целая горизонталь (между $C$ и $D$ ), а значит, есть ладья. Отсюда и следует требуемое.

$PIC$

Осталось привести пример, когда в одной из частей расположено $2n− 1$ ладей. Один из возможных примеров устроен так. Рассмотрим диагональ квадрата; в одну часть попадут клетки ниже нее, а также нижняя половина самой диагонали; остальные клетки попадут во вторую часть. Расставим $2n− 1$ ладью в клетки непосредственно под диагональю; тогда они окажутся в одной части. Оставшуюся ладью поставим в пересечение оставшихся строки и столбца. На рисунке указан такой пример при $n =5.$

Ответ:

$2n− 1$

Ошибка.
Попробуйте повторить позже

Задача 100#131943Максимум баллов за задание: 7

С одной стороны теннисного стола выстроилась очередь из $n$ девочек, а с другой — из $n$ мальчиков. И девочки, и мальчики пронумерованы числами от 1 до $n$ в том порядке, как они стоят. Первую партию играют девочка и мальчик с номерами 1, а далее после каждой партии проигравший встаёт в конец своей очереди, а победивший играет со следующим. Через некоторое время оказалось, что каждая девочка сыграла ровно одну партию с каждым мальчиком. Докажите, что если $n$ нечётно, то в последней партии играли девочка и мальчик с нечётными номерами.

Источники: ВСОШ, ЗЭ, 2023, 10.4 (см. olympiads.mccme.ru)

Показать доказательство

Будем изображать турнир в виде таблицы $n×n,$ в которой и столбцы, и строки пронумерованы числами от $1$ до $n.$ Столбцы будут соответствовать девочкам, а строки — мальчикам. Тогда каждая партия задаётся клеткой, координаты которой соответствуют номерам девочки и мальчика, играющих в этой партии. Поставим сначала фишку в клетку $(1,1).$ После победы девочки фишка будет перемещаться вверх, а в случае победы мальчика — вправо. При этом если фишка доходит до края таблицы, то из последней строки при движении вверх она перемещается в первую строку, а из последнего столбца при движении вправо — в первый столбец. Тогда условие задачи равносильно тому, что фишка обошла все клетки таблицы, побывав в каждой ровно по одному разу.

Раскрасим клетки таблицы в $n$ цветов по диагоналям, идущим вправо-вниз: первую диагональ — в первый цвет, вторую — во второй, $...,$ $n$ -ю диагональ — в $n$ -й цвет, а следующие диагонали — снова в цвета с первого по $(n − 1)$ -й. Заметим, что после каждой партии номер цвета клетки, в которой находится фишка, увеличивается на $1$ по модулю $n.$ Так как всего в турнире было проведено $n2$ партий, что кратно $n,$ то в конце фишка находится в клетке $n$ -го цвета, то есть на главной диагонали (далее, говоря «диагональ», мы будем иметь в виду именно эту диагональ). Пусть финальная клетка в маршруте фишки расположена в столбце с номером $m,$ тогда требуется доказать, что число $m$ нечётно.

Из верхней клетки диагонали $n$ фишка не могла пойти вверх, так как уже была в клетке $(1,1).$ Значит, если эта клетка не финальная, то из неё фишка пошла вправо. Тогда и из следующей клетки диагонали она сделала ход вправо, и т.д. до клетки, расположенной в столбце с номером $m − 1.$ Аналогично из клеток диагонали, находящихся в столбцах с номерами от $m + 1$ до $n,$ фишка ходила вверх. Пусть первая клетка диагонали, в которую попала фишка, находится в столбце с номером $k.$ Рассмотрим путь фишки от начальной клетки до неё. Все пути от клеток первого цвета до следующей клетки $n$ -го цвета должны быть такими же, как и рассматриваемый путь, а именно, каждый такой путь получается из другого смещением на вектор $(1,−1).$ Действительно, если бы фишка из клетки $(a− 1,b)$ сделала ход вверх, а из клетки $(a,b− 1)$ — вправо, то в клетку $(a,b)$ она бы не попала, а если из этих клеток она делала ходы вправо и вверх соответственно, то попала бы в одну клетку дважды; поэтому из каждых двух таких клеток фишка делала одинаковые ходы.

$PIC$

Без ограничения общности будем считать, что $k< m.$ Клетки диагонали, находящиеся левее финальной клетки, будем называть левыми, а находящиеся правее — правыми. Пронумеруем левые клетки числами от $1$ до $m − 1,$ а правые — от $1$ до $n− m$ (и те, и другие нумеруем, двигаясь вправо-вниз). Посмотрим, в каком порядке фишка обходила эти клетки. С левых клеток она смещалась на $k$ клеток вправо (поскольку с них в клетку первого цвета она делала ход вправо), а с правых клеток — на $k− 1$ клетку вправо. Значит, для левых клеток нам важен лишь остаток от деления номера на $k,$ а для правых — от деления на $k− 1.$ При этом, если правых клеток меньше $k,$ то можно увеличить $n$ на $2(k − 1),$ добавив $2(k − 1)$ правых клеток; это не повлияет на дальнейшие рассуждения. Для удобства заменим все номера клеток на соответствующие остатки, причём для правых клеток вместо остатка $0$ будем использовать число $k− 1.$

Пусть число $m$ при делении на $k$ даёт остаток $d.$ Тогда первый переход с левых клеток на правые был с числа $0$ на число $k− d,$ и в этот момент все клетки с нулём в левой части были посещены. На диагонали остались только числа от $1$ до $k− 1.$ Дальше цепочка переходов между правыми и левыми клетками выглядит так:

k− d → ⋅⋅⋅→ d.

В этой цепочке каждое число от $1$ до $k− 1$ встречается два раза, начинается она на правых клетках, а заканчивается на левых. Переходы с правых клеток на левые будем называть переходами первого типа, а с левых на правые — второго. Тогда в цепочке $k − 1$ переход первого типа и $k− 2$ перехода второго, и они чередуются.

Докажем, что каждые два числа в цепочке, симметричные относительно её центра, дают в сумме $k.$ Для крайних чисел это верно. Каждые два симметричных перехода имеют один тип, поэтому в них по модулю $k− 1$ (для переходов первого типа) или по модулю $k$ (для переходов второго типа) прибавляется одно и то же число. Значит, сумма следующих двух симметричных чисел (которые ближе к центру цепочки) снова равна либо $1$ по модулю $k− 1,$ либо $0$ по модулю $k.$ Но сумма самих чисел не меньше $2$ и не больше $2k− 2,$ поэтому она может быть равна только $k.$

Предположим, что число $m$ чётно, и рассмотрим два случая.

1) Число $k$ нечётно. Тогда центральный переход в цепочке имеет второй тип. У правой нижней клетки диагонали нечётный номер, поскольку число $n− m$ нечётно, а $k− 1$ чётно. Левая верхняя клетка диагонали тоже имеет нечётный номер, поэтому при переходе первого типа чётность числа меняется. Пусть с числа $1$ переход первого типа происходит на число $2s.$ Тогда по модулю $k− 1$ переходы первого типа выглядят так: $1→ 2s,$ $2 → 2s+1,$ …, $k− 1→ 2s+ k− 2.$ Суммы чисел в этих парах являются последовательными нечётными числами, поэтому при делении на $k− 1$ они дают все нечётные остатки по два раза. В частности, есть переход, в котором сумма чисел равна $1$ по модулю $k− 1.$ Как показано выше, эта сумма равна $k.$ Но тогда для этого перехода симметричный ему тоже имеет первый тип и содержит те же самые числа, то есть один из переходов повторился, чего быть не должно.

2) Число $k$ чётно. Тогда у центрального перехода в цепочке первый тип. Последняя левая клетка имеет нечётный номер, так как число $m − 1$ нечётно, а $k$ чётно. У первой правой клетки тоже нечётный номер, значит, при переходе второго типа чётность числа не меняется. Аналогично первому случаю можно показать, что среди них найдётся переход, пара чисел в котором даёт сумму $k,$ и получаем такое же противоречие.

Следующая подтема