Ошибка.
Попробуйте повторить позже
В какое наименьшее количество цветов можно раскрасить натуральные числа от до так, чтобы никакие два различных числа одного цвета не давали в произведении точный квадрат?
Рассмотрим произвольное число не превосходящее Представим в виде где — число, свободное от квадрата или равное (будем говорить, что имеет свободное от квадрата число ).
Покажем, что если два числа и в произведении дают квадрат и имеют свободные от квадрата числа и то Пусть это не так. Тогда либо существует такое простое число что не кратно а — кратно или наоборот. Но в таком случае входит в разложение в чётной степени, а в разложение — в нечётной или наоборот. Следовательно, не квадрат, противоречие.
Из вышеописанных рассуждений также следует, что если и — квадраты, то — также квадрат.
Теперь ясно, что все числа от до разбиваются на группы чисел с одинаковым свободным от квадрата числом. То есть любые два числа из одной группы в произведении дают квадрат, а любые два из разных — не дают.
Узнаем количество чисел в самой большой группе. Числа из произвольной группы в порядке возрастания выглядят так: — свободное от квадрата или равное В силу упорядочивания но тогда количество чисел в группе не превосходит
Найдём максимальное значение Мы знаем, что откуда Таким образом,
Значит, количество чисел в самой большой группе не больше Такая группа есть: Значит, нам хватит цветов, потому что мы можем в каждой группе раскрасить числа в разные цвета. Если же количество цветов меньше то в самой большой группе будут два числа одного цвета.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное обучение
в Школково
Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!