Тема Курчатов

Клетчатые задачи на Курчатове

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

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

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

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

Подтемы раздела курчатов

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

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

Задача 1#68030

Таблица $101×101$ покрашена в несколько цветов (каждая клетка — ровно в один цвет) так, что в любом квадрате $2 ×2$ присутствуют клетки не более чем трёх различных цветов. Какое наибольшее количество цветов могло быть использовано?

Источники: Курчатов-2023, 11.6 (см. olimpiadakurchatov.ru)

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

Подсказка 1

Раз у нас в каждом квадрате 2 на 2 не более трех различных цветов, то в каждом из них есть цвет, клеток которого хотя бы две в квадрате. Может, тогда стоит рассмотреть сколько может быть квадратов, в котором хотя бы две клетки конкретного цвета?

Подсказка 2

Попробуйте пойти таким путем: для начала найдите 4 квадратика, в которых по одной клетке такого цвета (а возможно их меньше, но считайте что 4), А после оцените кол-во квадратиков, в которых хотя бы 2 клетки этого цвета с помощью разного подсчета кол-ва клеток этого цвета во всех квадратиках)

Подсказка 3

В итоге выйдет хорошая оценочка на кол-во квадратиков, в котором конкретного цвета хотя бы 2. А теперь вспоминаем, что у нас все квадратики такие, что в них есть цвет, которого хотя бы два. Остается посчитать кол-во квадратов, предположить что цветов всего C, и пользоваться оценкой)

Подсказка 4

Если немного сложно пользоваться полученной оценкой, то попробуйте сложить все полученные оценки для всех цветов, а также вспомнить, что сумма всех кол-в клеток конкретного цвета - это кол-во всех клеток)

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

Оценка. Сначала сформулируем и докажем следующую лемму:

Лемма. Пусть $ki$ — количество клеток некоторого цвета $i.$ Тогда существует не более $2(ki− 1)$ квадратов $2× 2,$ в которых клеток этого цвета хотя бы $2.$

Доказательство. Прежде всего отметим, что каждая клетка этого цвета находится в четырех квадратах $2× 2.$ Внимательный читатель заметит, что эти квадраты могут выходит за границы доски, но поскольку мы оцениваем количество квадратов $2 ×2,$ в которых клеток этого цвета хотя бы $2$ сверху (даже если при оценке некоторые такое квадраты выходят за доску, то все равно оценка справедлива), то это замечание не повлияет на доказательство. Рассмотрим самую левую клетку этого цвета, находящуюся на самой нижней горизонтали доски, в которой есть этот цвет. Понятно, что квадрат, в котором эта клетка является правой верхней, не может больше содержать клеток этого цвета. Аналогично для самой правой клетки нижнего ряда (которая, вообще говоря, может совпадать с самой левой клеткой этого ряда) квадрат, в котором она является левой верхней, не может больше содержать клеток этого цвета. Такие же рассуждения можно провести с самым верхним горизонтальным рядом (который, опять же, может совпадать с самым нижним). Таким образом, есть хотя бы $4$ квадрата $2× 2,$ в которых присутствует только одна клетка цвета $i.$

Теперь рассмотрим все квадраты $2× 2,$ которые содержат цвет $i.$ Так как каждая клетка этого цвета находится в четырех квадратах, то суммарно в них находятся $4ki$ клеток цвета $i$ (некоторые из квадратов, возможно, выходят за границы таблицы). Пусть количество квадратов, в которых хотя бы две клетки этого цвета, равно $k.$ Тогда, так как есть хотя бы $4$ квадрата $2× 2,$ в которых присутствует только одна клетка цвета $i,$ то получим:

2 ⋅k +4 ≤4ki

k≤ 2(ki− 1)

Пусть количество цветов равно $C.$ Существует ровно $2 100 = 10000$ квадратов $2× 2,$ которые накладывают условие на цвета. Тогда для каждого квадрата $2×2$ должен найтись цвет, клеток которого в нём хотя бы $2,$ а из всего $10000,$ то просуммируем количество квадратов $2× 2,$ в которых клеток цвета $i$ хотя бы $2$ для всех $i$ и оценим их количество сверху, пользуясь леммой:

C ∑ (2ki− 2)≥ 10000 i=1

Но так как каждая клетка покрашена в один цвет:

C∑ ki = 1012 i=1

Значит,

∑C (2ki− 2)= 2⋅1012− 2C ≥ 10000 i=1

C ≤ 1012 − 1002= 5201 2

Пример. Рассмотрим все возможные вертикальные полоски. В первой из них покрасим все клетки в различные цвета. Во второй - в один и тот же новый цвет. В третьей - снова все клетки в новые различные цвета, потом снова в один новый цвет и так далее. При этом клеток в полосках с нечётным номером всего $51⋅101= 5151,$ а полосок с чётным номером ровно $50,$ поэтому различных цветов ровно $5201.$ Также понятно, что в любом квадрате $2× 2$ встретятся две клетки из вертикальной полоски с чётным номером. Значит, они будут одинакового цвета, т. е. цветов в каждом квадрате $2× 2$ будет не больше $3$ (на самом деле, ровно $3).$

Ответ:

$5201$

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

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

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

Задача 2#73406

В каждой клетке квадратной таблицы размером $200×200$ написали по действительному числу, по модулю не превосходящему $1.$ Оказалось, что сумма всех чисел равна нулю. Для какого наименьшего $S$ можно утверждать, что в какой-то строке или каком-то столбце сумма чисел заведомо окажется по модулю не превышающей $S?$

Источники: Курчатов-2019, 10.5 (см. olimpiadakurchatov.ru)

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

Сначала покажем, что $S < 100$ не подойдет. Разделим таблицу на четыре квадрата $100 ×100.$ Правый верхний квадрат заполним числами $+1,$ а левый нижний - числами $− 1.$ Остальные клетки заполним нулями. Легко видеть, что в каждой строке и в каждом столбце сумма равна $± 100.$

Теперь покажем, что $S = 100$ подходит. Предположим, что для некоторой таблицы это не так, то есть суммы во всех её строках и столбцах оказались либо больше $100,$ либо меньше $− 100.$ Заметим, что можно менять местами строки в таблице, не нарушая это свойство и условие задачи.

Поменяем местами строки так, чтобы их суммы убывали сверху вниз. Разделим таблицу на две половины $100× 200,$ верхнюю и нижнюю. Заметим, что либо в верхней половине все строки имеют положительную сумму, либо в нижней - все отрицательную. Тогда в одной из половин сумма по модулю больше $10000.$ Так как общая сумма всех чисел равна нулю, то в другой половине сумма такая же по модулю и противоположная по знаку.

Теперь отсортируем столбцы так, чтобы их суммы убывали слева направо. (Суммы в строках при этом не поменяются.) Аналогично, суммы в правой и в левой половине таблицы оказались по модулю больше $10000.$

Разобьем таблицу на четыре квадрата $100 ×100,$ суммы в них обозначим за $A,B,C,D :$


$A$	$B$

$C$	$D$

A + B > +10000 A + C > +10000 C + D< −10000 B + D <−10000

Заметим, что

2|A|+2|D|≥2A − 2D = (A + B)+(A +C )− (B+ D)− (C+ D)> 40000.

Это означает, что одно из чисел $A$ или $D$ по модулю превосходит $10000.$ Но в каждом из соответствующих квадратов всего $10000$ клеток, и числа в них по модулю не превосходят $1.$ Противоречие.

Ответ:

$100$

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

Задача 3#73405

Натуральные числа $1,2,...,64$ записаны в клетках таблицы $8×8$ так, что для всех $k =1,2,3,...,63$ числа $k$ и $k+1$ находятся в соседних по стороне клетках. Каково максимальное значение возможной суммы чисел на главной диагонали?

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

Оценка. Раскрасим клетки таблицы в шахматном порядке так, чтобы клетки на выбранной главной диагонали были белыми. Не умаляя общности, можно считать, что единица стоит не выше диагонали. Найдем максимальное значение наименьшего числа, попавшего на диагональ. Поскольку соседние числа стоят в клетках разного цвета, а белых клеток под диагональю находится всего $12,$ то одно из чисел от $1$ до $26$ обязательно попадает на диагональ. Остальные числа на диагонали гарантированно имеют одну четность, поэтому их сумма не превосходит суммы четных чисел от $52$ до $64.$ В итоге заключаем, что для суммы чисел на диагонали есть оценка сверху:

26 +52+ 54+56+ 58+ 60 +62+ 64= 432.

Пример подходящей расстановки:

$PIC$

Ответ:

$432$

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

Задача 4#83238

Последовательность различных клеток $a ,a ,...,a 1 2 k$ клетчатого квадрата $n× n$ называется циклом, если, во-первых, $k ≥4$ , и, во-вторых, клетки $aj$ и $aj+1$ являются соседними по стороне при всех $j =1,2,...,k$ (считаем при этом, что $ak+1 = a1$ ). Множество $X$ клеток квадрата назовём разделяющим, если в любом цикле есть хотя бы одна клетка из множества $X$ . Найдите наименьшее вещественное число $C$ такое, что для любого натурального числа $n≥ 2$ в квадрате $n×n$ существует разделяющее множество из не более чем $2 C⋅n$ клеток.

Источники: Лига победителей - 2017, старшая лига (10 класс) и в том же условии Курчатов - 2018, задача 11.5

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

Для построения примера разделяющего множества, в котором не более чем $n2∕3$ клеток, раскрасим все клетки в три цвета по диагоналям: первую диагональ - в первый цвет, вторую - во второй, третью - в третий, четвертую - опять в первый, и так далее.

$PIC$

Любой цикл из клеток, как легко видеть, пересекает как минимум три соседних диагонали и, следовательно, содержит клетки всех трех цветов. Клеток одного из цветов будет не более $n2∕3$ , и этот цвет можно использовать в качестве разделяющего множества.

Оценка. Покажем, что никакое $C < 1∕3$ не подходит.

Для этого построим граф, вершинами которого являются клетки. Две клетки соединим ребром, если они являются соседними. Получим граф, в котором $n2$ вершин и $2n(n − 1)$ ребер, при этом циклы задачи находятся во взаимно однозначном соответствии с циклами в графе. Требуется удалить несколько вершин так, чтобы в оставшемся графе не было циклов.

Предположим, мы удалили $k <C ⋅n2$ вершин. Если в оставшемся графе нет циклов, то этот граф является объединением деревьев и в нем не более чем $n2− k− 1$ ребро. При этом из каждой удаленной вершины выходило не более 4 ребер, и всего было удалено было не более $4k$ ребер. Таким образом, имеем неравенство

2 2n(n− 1)− 4k≤ n − k− 1,

откуда

(n − 1)2∕3 ≤k <C ⋅n2,

что невозможно при $C < 1∕3$ и достаточно большом $n$ .

Ответ:

$1 3$

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

Задача 5#37484

На клетчатой доске $(2k+ 1)×(2k+ 1)$ расставили $n$ белых и $n$ черных ладей так, что ладьи разных цветов не бьют друг друга. При каком наибольшем $n$ такое возможно?

Источники: Курчатов-2014, 11.3 (см. olimpiadakurchatov.ru)

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

Подсказка 1!

1) Итак, нам нужно оценить возможное количество ладей. Так как мы знаем количество строк и столбцов, было бы логично оценить количество ладей через строки и столбцы, на которых они стоят. Ведь если в строке 1 стоят ладьи, и в столбцах 5 и 7, например, то ладей на больше чем 1*2 ( клетки пересечения столбцов и строк, где замечены ладьи). Пусть белые ладьи заняли a клеток и b столбцов...

Подсказка 2!

2) Ага, оценим белые через ab, а черные через оставшиеся столбцы на оставшиеся строчки, и подумаем, как n соотносится с этими оценками на количество ладей...

Подсказка 3!

3) Ну, конечно! n меньше, чем обе наших оценки. Теперь можно попробовать порасставлять ладей и понять, какую оценку мы хотим доказывать. А можно помедитировать над уравнением, и заметить, что если n меньше чем минимальная из оценок, то максимум n достигается, если обе оценки равны! Давайте доказывать, что максимум будет тогда, когда ab равняется оценке на черные ладьи. Чему же равно ab...

Подсказка 4!

4) Ага, k(k+1)! Тогда обе оценки равны, окажем, что это лучший расклад, и не забудем построить пример!

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

Пусть белые ладьи занимают $a$ строк (то есть нашлось ровно $a$ строк, в которых есть белые ладьи) и $b$ столбцов. Белая и чёрная ладьи не могут стоять в одном столбце или одной строке, потому чёрные занимают не более $2k+ 1− a$ строк и $2k +1− b$ столбцов. Отсюда их количества не превышают соответственно $ab$ и $(2k +1 − a)(2k+ 1− b)$ , при этом легко видеть, что $n ≤min(ab,(2k +1− a)(2k+ 1− b))$ . Далее покажем, что минимум не превышает $k(k+ 1)$ . Действительно, пусть, не умаляя общности $a+ b≤2k +1$ (иначе $2k+ 1− a +2k+ 1− b< 2k +1$ ). Тогда $ab≤k(k+ 1)$ (с уменьшением суммы уменьшается и максимум произведения). То есть $n ≤k(k+ 1)$ . В качестве примера заполним прямоугольник $k× (k +1)$ в левом верхнем углу белыми ладьями, затем отразим доску относительно главной диагонали, а потом заполним тот же прямоугольник чёрными.

Ответ:

$k(k+ 1)$

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

Задача 6#41256

Клетчатая доска $100× 100$ раскрашена в шахматном порядке. Какое наибольшее число черных клеток доски можно отметить так, чтобы не нашлось параллелограмма с вершинами в центрах отмеченных клеток?

Источники: Курчатов-2013, 8-11 (см. olimpiadakurchatov.ru)

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

Подсказка 1!

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

Подсказка 2!

Да, если нашелся параллелограмм, это значит, что в двух разных строках совпали расстояния между двумя какими-то клетками. Подумайте, какие вообще на доске бывают расстояния. И что каждое встречается не более одного раза.

Подсказка 3!

Но в каждой строке их хотя бы сколько? Давайте посмотрим для фиксированной клетки какой-то расстояния и попробуем оценить количество различных расстояний снизу. А затем и построить пример!

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

Рассмотрим расстояния между выбранными клетками в каждой строке. Они могут принимать значения $2,...98.$ При этом если в строке $k$ клеток, то различных расстояний в ней хотя бы $k− 1$ (от крайней клетки до всех). Если в каких-то двух строчках нашлись два равных расстояния, то $4$ точки образуют параллелограмм, потому такого быть не может. Отсюда каждое расстояние встречается не более одного раза (рассматривая только $k− 1$ различных из каждой строки). То есть $∑100 i=1(ki− 1)≤ 49$ — сумма числа расстояний по всем строкам и $∑ ki ≤ 149.$ Осталось привести пример. Для этого выберем все клетки на большой диагонали и на любой из смежных с ней сторон.