Метод спуска, индукция и последовательное конструирование в ТЧ
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Дано натуральное 
Докажите, что все его делители, кроме, быть может, одного, можно разбить на пары, в каждой из которых одно
число будет делиться на другое.
Подсказка 1
Нередко задачи на существование решаются конструктивно. Проблема в том, что предъявление конструкции в этом случае бывает слишком громоздким и неудобным для описания. Что может помочь сделать его проще?
Подсказка 2
Рекурсивное определение или индукция. Давайте разберемся с некоторыми простыми случаями, когда разбиение на пары легко задается. Например, решите задачу в случае, если существует простое число, степень вхождения которого в n, нечетно.
Подсказка 3
Обозначим данное простое за p, тогда разбиение на пары (dp^{2k}, dp^{2k+1}), при всех делителях d свободных от p и чисел 2k, что 2k+1 не превосходит степени вхождения p в n, является корректным. Разбиение на пары в остальных случаях (когда степени вхождения всех простых в n четны) будем строить индуктивно.
Решим задачу индукцией по количеству простых делителей в натуральном числе 
Пусть
Перед этим докажем, что если какое-то из 
нечётное, то все делители числа разбиваются на пары данным образом. Действительно,
каждому делителю 
в который число 
входит в четной степени, можем поставить в пару число 
При этом, каждому делителю,
степень вхождения числа 
в которое нечетна, будет поставлено пару оно же, деленное на 
тем самым каждый делитель будет
участвовать ровно в одной паре.
База индукции при 
выполняется, поскольку в любой паре делителей один из них делится на другой.
Докажем переход индукции. Если каждое 
чётное, то делители числа 
разбиваются на пары, поскольку число 
входит в него в нечетной степени. Остальные делители имеют вид
Все делители числа 
быть может, кроме одного, по индукционному предположению можно разбить на пары
требуемым образом, тогда, домножив все делители на 
получим корректное разбиение на пары делителей данного
вида.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
