ИТМО - задания по годам → .09 ИТМО 2023

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

Если то их синусы различны и положительны.

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

1) Синусы получаются такие же, как и для в том же порядке.

2) В этом случае и получаются такие же, как и для в том же порядке, а меняет знак, т.е. получается другой набор чисел.

3) В этом случае Однако что не совпадает ни с ни с так как больше каждого из них.

4) В этом случае Однако что не совпадает ни с ни с так как отрицательно.

5) В этом случае Однако что не совпадает ни с ни с так как больше каждого из них.

6) В этом случае Однако что не совпадает ни с ни с так как отрицательно.

Таким образом, единственная возможность получить те же 3 синуса, это случай 1), в котором порядок синусов также совпадает.

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

Пусть — середина ребра тогда Т.к. — куб, по теореме Пифагора из прямоугольного получаем

— середина а — середина следовательно, как средняя линия квадрата равна т.е. равна Т.к. — куб, по теореме Пифагора из прямоугольного получаем

Пусть — середина ребра тогда Т.к. сфера вписана в каркас куба значит, точками касания являются середины рёбер. Следовательно, используем теорему о касательной и секущей

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

Отсюда

При этом, чтобы это равенство обращалось в равенство, должно выполняться

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

Отсюда

При этом, чтобы это равенство обращалось в равенство, должно выполняться

Таким образом,

При этом оба неравенства не могут обращаться в равенство одновременно, следовательно

равнобедренный, поэтому Накрест лежащие углы равны: . Значит,

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

Значит, или как односторонний угол. Это один из ответов.

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

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

Замечание. Как же найти такой цикл, не считая вручную все значений до него? Во-первых, уже , что явно нам намекает, когда мы снова встретим единицу (по сути мы каждый раз умножаем дробную часть на 2, поэтому можно сразу сделать вывод, что на шаге, поскольку за столько же шагов результат возведётся в квадрат по модулю ). Во-вторых, уже на шестом шаге мы получим , поэтому далее можно попробовать идти по кратным шести индексам, чтобы быстрее добраться до . Почему вообще всё это имеет смысл? Потому что делится и на 6, и на 33, и на 66 — именно в них мы и ждём больше всего увидеть цикл, чтобы задача после этого решилась быстро и легко.

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

Докажем теперь, что меньше 120 закрашенных клеток не может быть.

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

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

Сравним числа и

Пусть то есть В каждом столбце присутствуют хотя бы 6 синих клеток. Из взятого в качестве предположения неравенства следует, что в каком-то столбце количество красных клеток хотя бы от количества синих, то есть хотя бы 5, поэтому общее количество закрашенных клеток в данном столбце хотя бы 11, откуда и, следовательно, Если и оценка доказана. Предположим, тогда то есть не превосходит 10.

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

Поскольку значит Значит, в каком-то столбце присутствуют хотя бы то есть хотя бы 7 красных клеток, откуда

Поскольку в каком-то столбце присутствуют хотя бы то есть хотя бы 8 красных клеток, откуда

Поскольку значит, Значит, в каком-то столбце присутствуют хотя бы то есть хотя бы 9 красных клеток, откуда

Поскольку значит, Значит, в каком-то столбце присутствуют хотя бы то есть хотя бы 11 красных клеток, откуда

Поскольку значит, Значит, в каком-то столбце присутствуют хотя бы то есть хотя бы 15 красных клеток, откуда Отсюда получаем, что что противоречит доказанному ранее.

Аналогично разбираем случай, когда то есть В каждой строке присутствуют хотя бы 5 красных клеток. Из взятого в качестве предположения неравенства следует, что в какой-то строке есть хотя бы 6 синих клеток, то есть общее количество закрашенных клеток в данной строке хотя бы 11, откуда и, следовательно, Если и оценка доказана. Предположим, тогда то есть не превосходит 10.

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

Поскольку в какой-то строке присутствуют хотя бы то есть хотя бы 8 синих клеток, откуда

Поскольку значит Значит, в какой-то строке присутствуют хотя бы то есть хотя бы 10 синих клеток, откуда Отсюда получаем, что что противоречит доказанному ранее.

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

Если один из наших делителей — само число , а второй — некоторое число и , то мы получаем

Чем больше, тем и само больше.

Наименьшее такое, что является делителем 100, это 3. При таком получаем .

Если же нет среди двух наших делителей, то , откуда .

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

Вася будет действовать так: если Петя убирает строку, Вася убирает столбец, и наоборот. Таким образом, оставшиеся фишки всегда будут образовывать квадрат. Так будет продолжаться, пока оставшиеся фишки не образуют квадрат После этого Петя убирает две фишки, а Вася — две оставшиеся.