Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

№96

Предлагаемая задача не входит в тематический конкурс. Результат учитывается только в основном Маpафоне.

Конкурсная задача №96 (6 баллов)

Двое играют в такую игру:
С помощью идеального генератора случайных чисел выбирают натуральное число из интервала 1..10100. Если выпавшее число свободно от квадратов, первый игрок платит второму 200 рублей, в противном случае второй игрок платит первому 300 рублей. И т.д.
Кому выгодна такая игра?

Решение

Приведу решение Владислава Франка. Правда, вывод заменен на противоположный :)

Докажем, что игра выгодна второму игроку.
Для этого достаточно показать, что среди первых N=10100 натуральных чисел более 60% свободно от квадратов.

Лемма.
Среди чисел от 1 до N примерно N/a кратны a (отличие настоящего количества от этого не больше 1, причем оно может отличаться только в меньшую сторону).

Очевидно.

Следствие 1.
Среди чисел от 1 до N не более N/a1 + N/a2 +…+ N/ak кратны хотя бы одному из чисел ai.

Доказательство. Следует из предыдущей леммы. Для каждого ai чисел не более, чем N/ai, и это без учета того, что некоторые числа могут быть посчитаны больше одного раза.

Следствие 2.
Если ai попарно взаимно просты, то количество чисел, не кратных ни одному из них среди чисел от 1 до N примерно N(1-1/a1)…(1-1/ak), причем отличается от этого выражения не более, чем на 2k.

Доказательство. Применим формулу включения-исключения. Каждое слагаемое после раскрытия скобок как раз дает количество чисел, делящихся на некоторый набор из 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 балла


 

 


Страница: [[marathon:problem_96]]

marathon/problem_96.txt · Последние изменения: 2009/02/13 22:32 (внешнее изменение)
Powered by DokuWiki  ·  УКЦ ВГПУ 2006