Комбинаторика на ММО: графы, турниры, логика, конструктивы
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
На каждой из 99 карточек написано действительное число. Все 99 чисел различны, а их общая сумма иррациональна. Стопка из 99 карточек
называется неудачной, если для каждого натурального 
от 1 до 99 сумма чисел на 
верхних карточках иррациональна. Петя
вычислил, сколькими способами можно сложить исходные карточки в неудачную стопку. Какое наименьшее значение он мог
получить?
Источники:
Подсказка 1
Это задача на оценку. Чтобы ее получить, стоит сначала придумать пример.
Подсказка 2
Попробуйте взять одну карточку с иррациональным числом. Где тогда должна находиться эта карточка в неудачной стопке?
Подсказка 3
Ее надо положить сверху, способов разложить остальные 98 карточек — (98!). Осталось только доказать эту оценку.
Подсказка 4
Попробуйте разбить все перестановки на 98! групп, подумав про циклические перестановки.
Подсказка 5
В каждой группе стопки будут получаться друг из друга циклической перестановкой. Докажите, что внутри каждой группы будет хотя бы одна неудачная стопка.
Подсказка 6
Попробуйте представить каждую группу в виде круга, по которому расставлены 99 данных чисел. Тогда каждая стопка будет иметь вид aᵢ, … , a₉₉, a₁, … , aᵢ₋₁.
Подсказки 7
Попробуйте идти по кругу, начиная с a₁, пока сумма чисел по пройденной дуге не даст рациональное число. Когда это произойдет — повторите со следующего числа.
Подсказка 8
А что произойдет, если мы совершим 100 шагов? Можно ли воспользоваться принципом Дирихле?
Пример. Возьмём одну карточку с иррациональным числом и 
карточек с рациональными (например, 
Тогда в
неудачной стопке карточка с иррациональным числом должна быть сверху, при этом остальные карточки можно расставить любым из 
способов, так как для любого натурального 
число 
иррационально.
Оценка. Разобьём все перестановки карточек на 
групп, в каждой из которых одна стопка получается из другой циклической
перестановкой (очевидно, внутри одной группы ровно 
перестановок). Достаточно показать, что внутри каждой группы будет хотя бы
одна неудачная стопка.
Предположим, что нашлась группа без неудачных стопок. Её можно представить в виде круга, по которому расставлены карточки
тогда стопки из группы будут иметь вид
Начнём идти от карточки с числом 
по часовой стрелке до тех пор, пока сумма чисел по пройденной дуге 
не даст
рациональное число. Далее начнём идти от 
до тех пор, пока сумма пройденных чисел не станет рациональной, и так далее. Так,
совершив 
шагов, по принципу Дирихле мы начнём отсчитывать сумму от одной и той же карточки дважды, а, значит, мы обернули
круг целое число раз, получив в сумме рациональное число, следовательно, сумма всех чисел на самом деле рациональна —
противоречие.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
