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

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

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

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

Самая большая степень двойки, не превосходящая 100, это . Фокусник в начале должен разбить пришедших на представление на циклы, длины одного из которых равна 64, а длины остальных — меньшие степени двойки, не важно какие. Тогда через 6 минут все шляпы окажутся у своих настоящих владельцев (у некоторых они окажутся раньше, но в этот момент это впервые произойдёт для всех сразу).

Пусть — центр описанной окружности треугольника , лежащий на — центр сферы. Очевидно, — середина . Так как точки и лежат на сфере, перпендикулярно плоскости . С другой стороны, и — это одна и та же прямая, а перпендикулярна плоскости . Значит, плоскости и параллельны, а тетраэдры и подобны.

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

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

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

Значит, объемы тетраэдров составляют

и

а их произведение равно

Чтобы максимизировать эту величину, достаточно максимизировать

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

Радиусы и равны друг другу и высоте трапеции. Из условия про пересечение лучей следует, что — меньшее основание.

Проведём вторую касательную к вписанной окружности треугольника параллельную основаниям трапеции. Обозначим за и точки пересечения этой касательной с отрезками и — трапеция.

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

Более точно, обозначим точки касания окружностей и с основаниями трапеции : пусть и лежат на ( ближе к ), и лежат на ( ближе к ). Кроме того, пусть - точки касания вписанной окружности с соответственно. Кроме того, пусть и - точки касания окружностей и с боковыми сторонами трапеции, и - центры окружностей и вписанной окружности треугольника .

Рассмотрим четырёхугольники и

как соответственные. , прямые.

Значит оставшиеся углы, и также равны. Значит, треугольники и равны. Следовательно, треугольники и также равны, а значит четырёхугольники и равны. Аналогично

Значит,

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

После замены

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

а условие на произведение превращается в

Искомое выражение по формуле перехода и свойствам логарифмов равно

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

не изменится, а сумма дробей

и аналогичная ей (с точностью до перестановки ) сумма дробей

не уменьшатся, так как после приведения к общему знаменателю у получившейся дроби числитель увеличивается при увеличении а знаменатель уменьшается при увеличении

Такими преобразованиями можно превратить три наименьших числа из в единицу, а наибольшее — в при этом наше выражение будет увеличиваться (точнее, заведомо не уменьшаться). Итак, максимальное значение выражения равно

Вырежем из нашего куба куб и разобьём его на 64 куба .

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

В исходном кубе после этого остались кубики на трёх гранях, имеющих общую вершину. Рассмотрим 64 клетки на одной из этих граней, которые не лежат ни на какой из двух других. Они разбиваются на 16 квадратов , в каждом из которых не более трёх закрашенных ячеек. Итого на трёх гранях получаем не более .

У нас остались не рассмотренными 25 ячеек, образующих три ребра исходного куба, сходящиеся в одной вершине. Среди них закрашены не более 24, так как общая ячейка трёх этих рёбер и три её соседних лежат в одном кубике , значит, среди этих четырёх ячеек не более трёх закрашенных.

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

У числа шестнадцать делителей и все они являются делителями числа . Если делится на , то к этим делителям добавляются ещё числа 16,48 и 80 , то есть 120 — это уже как минимум девятнадцатый делитель.

Если делится на , то к исходным шестнадцати делителям добавляются 9,18 и 45 . Если делится на , то к исходным шестнадцати делителям добавляются 25,50 и 75.

Значит, делится на какое-то простое число , кроме 2,3 и 5 . Если это число не превосходит 40 , то числа и являются делителями , меньшими 120 , и мы опять получаем слишком много делителей. Значит, хотя бы 41 , то есть . Заметим, что это число нас как раз устраивает.

Перепишем рекуррентную формулу:

Записав её для вместо получим

откуда

Поскольку то

Значит,

Производная многочлена равна

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

При этом по теореме Ролля между каждыми двумя корнями многочлена находится корень производной, не являющийся при этом корнем многочлена. Поэтому если у многочлена хотя бы 19 корней, то у его производной хотя бы 18 корней, так что суммарно уже 37 различных корней, а это больше 36.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма (доказывать на олимпиаде не требовалось): Если число является корнем многочлена кратности то для производной число является корнем кратности

______________________________________________________________________________________________________________________________________________________

Пример на 18 корней строится так: рассмотрим многочлен

У него и у его производной 18 корней, но есть общий (только общий по лемме, оставшиеся 17 корней находятся между корнями по теореме Ролля). Тогда у 35 корней.

Но при достаточно маленьком (можно взять конкретное ) многочлен будет иметь так же 18 корней и такую же производную, но будет иметь уже 36 корней за счёт того, что перестанеть являться корнем .

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

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

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

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

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

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

Примеров для 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 синих клеток, откуда Отсюда получаем, что что противоречит доказанному ранее.

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

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

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

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

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

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

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

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

Отсюда

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

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

Отсюда

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть

Тогда

Это число может быть рациональным только если откуда

Далее,

Значит,

Отсюда по аналогичным соображениям

Объединив эту систему с ранее полученной, имеем

Возведём первое равенство в квадрат:

Далее вычтем из полученного второе исходное равенство:

Значит, учитывая, что получаем:

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

Число в белой клетке состоит из двух слагаемых: "горизонтального"и "вертикального". Рассмотрим отдельно сумму всех "горизонтальных"и отдельно сумму всех "вертикальных"слагаемых по всей таблице. Если мы максимизируем каждую из этих двух сумм по отдельности, общая сумма также будет наибольшей.

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

Нам нужно максимизировать это выражение, т.е. минимизировать сумму квадратов восьми чисел, сумма которых составляет 23. Как известно, сумма квадратов чисел уменьшается при сближении этих чисел к их среднему арифметическом, поэтому для целых чисел минимум достигается, когда семь из восьми чисел равны 3, а оставшееся равно 2.

Таким образом, мы получаем, что наименьшая возможная сумма "горизонтальных"слагаемых равна

Аналогичную оценку можно получить для суммы "вертикальных"слагаемых, что даёт нам итоговое значение 234.

Осталось убедиться, что существует раскраска таблицы, при которой обе суммы максимальны одновременно, то есть в которой в каждом столбце или строке по 2 или 3 закрашенных клетки.