Иннополис - задания по годам → .09 Иннополис 2023

Для начала заметим, что в каждом квадрате должно быть по две клетки каждого цвета. Рассмотрим раскраску самой верхней строки квадрата. Предположим, что в ней есть какие-то две соседние клетки одинакового цвета. Тогда, рассмотрев квадрат содержащий эти клетки, получим, что две клетки под ними должны быть противоположного цвета. Если теперь сдвинуть этот квадрат на одну клетку вправо, получим, что в левом столбце две клетки противоположного цвета, поэтому и в правом столбце клетки тоже должны быть противоположного цвета. Сдвигая этот квадрат аналогично вправо и влево, получим, что вторая строка должна быть противоположна (по цветам) первой.

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

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

Обозначим количество подходящих раскрасок первой строки за Тогда количество подходящих раскрасок всей доски будет равно Действительно, в первой строке будет либо чередование цветов ( варианта), либо где-то встретятся две клетки одинакового цвета. Во втором случае всё остальное определяется однозначно, а в первом всё определяется раскраской первого столбца (если и в первой строке, и в первом столбце не будет двух стоящих рядом клеток одного цвета, то с помощью последовательного рассмотрения квадратов мы получим, что раскраска должна быть шахматной).

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

В первом случае разобьём все клетки на пары подряд идущих. На месте каждой пары может быть либо блок из двух одинаковых клеток, либо пара разных клеток. По набору мест блоков и цвету самой левой клетки цвета всех остальных клеток определяются однозначно. Таким образом, вариантов в этом случае В случае, когда первые клетки блоков располагаются на чётных позициях, есть всего мест для блоков, и цвета всех клеток также определяются наборами мест блоков и цветом самой левой клетки. В этом случае вариантов При этом те варианты, где блоков вообще нет, мы посчитали дважды. Таких вариантов (когда цвета чередуются). Значит,

Получаем ответ:

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

Для этого будем последовательно рисовать их. Сначала проведем прямые и они лежат в одной плоскости т.к. пересекаются в точке Прямая пересекает в точке а прямую — в точке поэтому она также лежит в плоскости Наконец, прямая пересекает прямую в точке а прямую — в точке так что и она лежит в плоскости

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

Заметим, что

Так как числа и взаимно просты, то кратно тогда и только тогда, когда кратно Поскольку — простое, согласно малой теореме Ферма

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

Если делится на то

Значит, делится на а значит, и на что и требовалось.

В обратную сторону: если кратно то рассмотрим Воспользуемся алгоритмом Евклида, т.е. свойством НОД

Теперь

Повторяя эти действия, убеждаемся, что в конце получается число

Если не делится на то

Значит, — не минимальное натуральное число, при котором кратно — противоречие. Значит, кратно что и требовалось доказать.

Пусть — элементарные симметрические многочлены и Воспользуемся формулой Ньютона

Докажем, что Предположим, что существуют такие взаимно простые в совокупности , что отличен от Докажем, что тогда имеют общий делитель, больший 1. В самом деле, из формул Ньютона следует, что при разложении через моном, не содержащий и с точностью до знака имеет вид Поэтому если делит и делит то делит

При отличном от у чисел есть общий делитель, больший 1. Пусть — простой множитель, входящий в этот делитель. Тогда делит откуда (без ограничения общности) делит a. Но тогда делит и делит т.е. (без ограничения общности) делит Наконец, из того, что делит получаем, что делит Значит, но по условию — противоречие.

Итак, Набор реализует набор — набор — Для возьмем простое число и положим Тогда и не делит откуда

Рассмотрим нарисованные окружности как плоский мультиграф (граф с кратными ребрами между вершинами): вершины – точки пересечений, ребра – дуги нарисованных окружностей, ограниченные точками пересечений. В такой интерпретации круглосторонники — это все грани этого графа, кроме «внешней» (т.е. части плоскости, лежащей вне всех окружностей).

Пусть нарисованы ровно окружностей. Согласно формуле Эйлера для плоских графов,

где — число вершин графа, — число ребер, а — – число граней (включая внешнюю).

Так как каждая пара окружностей пересекается ровно в двух своих уникальных точках, то число вершин

Так как каждая вершина – это точка пересечения ровно двух окружностей, то наш граф является регулярным степени (то есть в каждую вершину входят ровно ребра). Поскольку каждое ребро соединяет две вершины, общее число ребер

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

Значит, число круглосторонников

Найти наименьшее такое, что — значит найти наименьшее натуральное решение неравенства

Решив, получаем, что наименьшее равно соответственно

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

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

Это невозможно, — следовательно, неверно предположение, что все круглосторонники ограничены не менее чем дугами. Поэтому обязательно найдется круглосторонник, ограниченный менее чем дугами, что и требовалось доказать.