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

задан 25 Мар '14 12:45

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

У этой задачи наверняка есть какое-то красивое решение, но семизначных натуральных чисел, содержащих только 0 и 1 в десятичной записи, всего 64, поэтому задачу можно решить и перебором.
А перебор говорит, что единственный ответ - это 1000000.

ссылка

отвечен 25 Мар '14 13:24

@chameleon: Извините пожалуйста, а не проще перебрать четырехзначные числа, которые содержат только 0 и 1, их всего 8 штук, возводить их в квадрат и убедиться, что только 1000 в квадрате даст семизначное число также состоящее только из 0 и 1.

(25 Мар '14 13:48) serg55

@serd55: а почему не может так оказаться, что 4-значное число состоит из каких-то других цифр, но при возведении в квадрат получаются только цифры 0 и 1? Я думаю, тут другое рассуждение надо применять, основанное на алгоритме извлечения корня. Это пока только идея как можно избежать прямого перебора. Позже попробую её как-то оформить, если получится.

(25 Мар '14 13:55) falcao

@falcao: Я эту задачу решал так: самое большее семизначное число, состоящее из 1 и 0 это 1111111, корень из него 1054,09. Таким образом 4-х значные числа могут находиться только в интервале от 1000 до 1054. А нас будут интересовать числа которые хотя бы на конце дают 0 или 1. Таких чисел не очень много: 1000; 1001; 1010; 1011; 1019; 1020; 1021; 1029; 1030; 1031; 1039; 1040; 1041; 1049; 1050; 1051. Сразу бросается в глаза, что квадраты всех чисел, начиная с 1019 при содержат не только 1 и 0. Значит остаётся проверить первые 4 числа. Подойдет только 1000. Можно так решать или нет? С уважением.

(27 Мар '14 12:46) serg55

@serg55: да, по такому принципу решать, конечно, можно. Коль скоро рассмотрены все случаи, и ничего не упущено, то такое решение является математически правильным, и, скажем, на олимпиаде должно быть засчитано в качестве верного.

Другое дело, если мы хотим придумать какое-то другое решение, не основанное на переборе и на вычислениях. Это представляет интерес само по себе.

P.S. Я про эту задачу забыл -- хорошо, что напомнили. Сейчас попробую придумать что-нибудь. Если получится, то напишу.

(27 Мар '14 12:50) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×3,929

задан
25 Мар '14 12:45

показан
1722 раза

обновлен
27 Мар '14 12:50

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

по почте:

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

по RSS:

Ответы

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

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