Назовём натуральное число ярденифицированным, если его можно разложить на двузначные натуральные множители.

а) Докажите, что из миллиарда ярденифицированных чисел всегда можно выбрать два, произведение которых является точным квадратом.

б) Насколько мощным может быть множество ярденифицированных чисел, если известно, что никакие два из них не образуют точный квадрат при их перемножении?

задан 21 Янв '18 18:20

10|600 символов нужно символов осталось
1

а) Число раскладывается в произведение степеней простых, не превосходящих 100. Таких простых чисел имеется 25. Если из каждого числа вынести максимальный точный квадрат, то получится не более 2^{25} вариантов в зависимости от чётности/нечётности показателя. Ясно, что 10^9 > 2^{9}4^{9}=2^{27} (оценка совсем грубая). Далее всё следует из принципа Дирихле.

б) Покажем, что все 2^{25}=33554432 вариантов реализуются через произведение двузначных чисел. Надо разобраться со степенями 7, 5, 3, 2. Если 7 в нечётной степени, то заменяем его на 14. Если 5 в нечётной степени присутствует, заменяем на 10. Число 3 в нечётной степени заменим на 27. Далее вместо степени 2 вводим 16 или 32, чтобы обеспечить нужную чётность показателя. Эти 33 с лишним миллиона чисел и дадут максимальную мощность.

ссылка

отвечен 21 Янв '18 19:40

@falcao, большое спасибо!

(22 Янв '18 0:25) Казвертеночка
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,092
×274
×200
×147
×24

задан
21 Янв '18 18:20

показан
293 раза

обновлен
22 Янв '18 0:25

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru