Задача
Дьявол предлагает Человеку сыграть в следующую игру. Сначала Человек платит некоторую сумму s и называет 97 троек {i, j, k}, где i, j, k – натуральные числа, не превосходящие 100. Затем Дьявол рисует выпуклый 100-угольник A1A2...A100 с площадью, равной 100, и выплачивает Человеку выигрыш, равный сумме площадей 97 треугольников AiAjAk. При каком наибольшем s Человеку выгодно согласиться?
Решение
Решение 1: Лемма. Пусть T множество из не более чем n – 3 треугольников, вершины которых выбираются из вершин выпуклого n-угольника БикЮ P = A1A2...A100. Тогда можно раскрасить вершины P в три цвета так, что вершины каждого цвета образуют непустое множество подряд идущих вершин P и множество T не содержит треугольников с разноцветными вершинами.
Доказательство. Индукция по n. База. При n = 3 утверждение верно, так как T пусто.
Шаг индукции. Пусть n > 3. Если A1An не является стороной никакого треугольника из T, покрасим A1 и An в два разных цвета, а остальные вершины в третий цвет.
Пусть A1An является стороной хотя бы одного треугольника из T. Образуем множество U, удалив из T все такие треугольники и заменив в остальных An на A1. Используя предположение индукции для многоугольника Q = A1A2...An–1 и множества U, раскрасим вершины Q. Теперь, раскрасив An в тот же цвет, что A1, получим искомую раскраску P. Пусть Дьявол строит раскраску, соответствующую названным Человеком тройкам, и рисует выпуклый 100-угольник P площади 100, вписанный в окружность так, что все вершины P цвета i лежат на дуге ci с градусной мерой ε°, а середины дуг c1, c2 и c3 образуют правильный треугольник. Если ε стремится к нулю, то площади всех названных Человеком треугольников, а значит, и их сумма тоже стремятся к нулю.
Решение 2: Для каждой тройки {i, j, k} запишем в вершину Ai количество сторон, покрытых углом AjAiAk (оно не зависит от выбора 100-угольника), то же сделаем с вершинами Aj и Ak. Сумма записанных чисел для одной тройки равна 100, поэтому общая сумма всех чисел равна 97·100, а значит, в какой-то вершине (скажем, A1) сумма чисел не больше 97; это значит, что есть сторона AkAk+1, не содержащая A1 и такая, что ни один из углов с вершиной в A1 не покрывает эту сторону. Теперь Дьявол может, нарисовав 100-угольник, в котором вершины A2, ..., Ak–1 близки к Ak, а вершины Ak+2, ..., A100 близки к Ak+1, сделать площади всех 97 треугольников, а значит, и их сумму сколь угодно малой.
Ответ
При s = 0.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь