Обойтись без перебора в олимпиадной арифметической задаче

[Ktina]

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

Официальное решение сводится к тому, чтобы перебрать квадраты чисел 33, 44,..., 99.

Не думаю, что это хорошая идея - тратить на подобный перебор драгоценное время, которого на олимпиаде и так в обрез.

Во-первых, нечётные числа можно сразу же отбросить, поскольку если бы две последние цифры квадрата нечётного числа были одинаковыми, такой квадрат оканчивался бы на две нечётные цифры, что невозможно.

Следовательно, осталось перебрать только три числа - 44, 66 и 88.

Но и этого можно избежать!
Ведь квадраты чисел 44 и 66 оканчиваются на 6, следовательно, последние две цифры тоже не могут быть одинаковыми (квадраты не кончаются на 66, иначе давали бы остаток 2 при делении на 4).

Итак, методом элиминации мы пришли к единственно правильному варианту: 88.
Осталось лишь возвести его в квадрат и получить 7744, и задача решена.

Кстати, можно даже и 88 в квадрат не возводить, ведь 88 лежит между 80 и 90, значит, первые две цифры его квадрата - либо 66, либо 77, либо 88, но 66 и 88 невозможны по модулю 9 (6644 даёт остаток 2, а 8844 - 6).

Итак, ответ 7744, и без всякого там перебора.
Будьте любезны, оцените.
Заранее спасибо!

[svv]

Эта задача есть в книжке Перельмана «Занимательная алгебра». Она называется «Номер автомашины».
Решение Перельмана Вы назвали бы переборным.

Всё классно, только: часто в попытке избежать перебора мы заменяем некий объём однородных шагов на сравнимый объём разнородных шагов. Меняем, так сказать, цикл на разветвлённое дерево. Всегда ли оправданно сокращение на три фразы ценой добавления двух уровней?

[al12345]

Согласен с svv - один перебор заменен на другой, причем ценой усложнения решения.

Совсем без перебора тоже можно.

$n^2 = aabb$
$n^2/11=a0b --> a+b=11$ и $n^2=4(mod 9)$ --> n=2 или 7 (mod 9)
n = 11k --> k = 1 или 8, 1 не подходит. Итого: 88, если известно, что решение есть. Если неизвестно - придется возвести 88 в квадрат для проверки.

[ewert]

al12345 в сообщении #1208639 писал(а):

$n^2/11=a0b --> a+b=11$ и

дальше всё-таки лучше перебор. Ведь двузначных квадратов совсем немного: $16,\ 25,\ 36,\ 49,\ 64,\ 81$. Дальше ничего считать не надо -- сразу видно, что нолик получается только из $64$.

[Ktina]

svv в сообщении #1208627 писал(а):

Эта задача есть в книжке Перельмана «Занимательная алгебра». Она называется «Номер автомашины».
...

(Оффтоп)

У меня где-то есть эта книжка, когда-то привезённая ещё из СССР Уже минут 40 ищу, и никак не могу найти. То ли дело мобильник потерять, просто звонишь на него - и все дела.

[al12345]

ewert в сообщении #1208649 писал(а):

дальше всё-таки лучше перебор.

Так просили не как лучше, а без перебора :)

[worm2]

Перельмана не читал, но одобряю.
$\overline{aabb} = 11(100a+b)$. Условие делимости $100a+b$ на 11 (вспоминаем признак делимости на 11) даёт $b=11-a$.
$m^2=9a+1$ ($m$ — это корень из искомого квадрата, делённый на 11).
$9a=(m+1)(m-1)$. Поскольку $m+1$ и $m-1$ не могут одновременно делиться на 3, значит одно из них делится на 9. Тут я вынужден признать, что два варианта рассмотреть придётся

-- Вт апр 11, 2017 23:02:56 --

В принципе здесь то же самое, но вот в этом переходе:

al12345 писал(а):

$n^2=4(mod 9)$ --> n=2 или 7 (mod 9),

как мне кажется, сидит неявный перебор.

[al12345]

worm2 в сообщении #1208784 писал(а):

В принципе здесь то же самое, но вот в этом переходе:

al12345 писал(а):

$n^2=4(mod 9)$ --> n=2 или 7 (mod 9),

как мне кажется, сидит неявный перебор.

Вам кажется. Никакого перебора при вычислении корня по модулю нет, так как известно количество корней и корни - это +-2(mod 9).

В общем случае перебора тоже нет - элементарная теория чисел.

Только не говорите, что иногда корней бывает больше - это тоже всем известно.

Если перебор - это выбор одного из корней, то да, он есть.