|
||||||||||||||||||
|
Содержание№96Предлагаемая задача не входит в тематический конкурс. Результат учитывается только в основном Маpафоне. Конкурсная задача №96 (6 баллов)
Двое играют в такую игру: Решение Приведу решение Владислава Франка. Правда, вывод заменен на противоположный :)
Докажем, что игра выгодна второму игроку.
Лемма. Очевидно.
Следствие 1. Доказательство. Следует из предыдущей леммы. Для каждого ai чисел не более, чем N/ai, и это без учета того, что некоторые числа могут быть посчитаны больше одного раза.
Следствие 2. Доказательство. Применим формулу включения-исключения. Каждое слагаемое после раскрытия скобок как раз дает количество чисел, делящихся на некоторый набор из ai с ошибкой не больше 1. А слагаемых 2k. Доля чисел, не кратных 22, 32,…, 192, составляет минимум (1-1/4)(1-1/9)…(1-1/361) = 0.614233541… от всех, причем поправка не превышает 28 = 256. Непосредственно вычисляем, что доля чисел, кратных одному из квадратов простых между 23 и 239 не превышает 1/232 + 1/292 +…+ 1/2392 = 0.00947961700… Доля чисел, кратных одному из остальных квадратов простых, не превышает суммы остальных обратных к квадратам простых. Она, в свою очередь, не превышает сумму всех обратных квадратов начиная с 240, то есть Pi2/6 минус начальная сумма ряда, что составляет примерно 0.00417535930… Окончательно, количество свободных от квадратов составит не меньше, чем (0.6142335409 - 0.00417535931)*10100 - 256 > 0.6*10100, что и требовалось. Обсуждение Более аккуратный подсчет показывает, что доля чисел, свободных от квадратов, примерно равна 0.6079275. Награды За правильное решение задачи 96 Андрей Халявин получает 6 призовых баллов, Виктор Филимоненков и Алексей Извалов - по 4 призовых балла. Влад Франк (который при правильном ходе решения отдал таки предпочтение не тому игроку) получает 5 призовых баллов. Эстетическая оценка задачи - 3.9 балла
|
|||||||||||||||||
|
||||||||||||||||||
|