2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Обойтись без перебора в олимпиадной арифметической задаче
Сообщение11.04.2017, 09:43 
Аватара пользователя


01/12/11

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

Официальное решение сводится к тому, чтобы перебрать квадраты чисел 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, и без всякого там перебора.
Будьте любезны, оцените.
Заранее спасибо!

 Профиль  
                  
 
 Re: Обойтись без перебора в олимпиадной арифметической задаче
Сообщение11.04.2017, 13:31 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Обойтись без перебора в олимпиадной арифметической задаче
Сообщение11.04.2017, 14:19 


11/04/17
15
Согласен с 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 в квадрат для проверки.

 Профиль  
                  
 
 Re: Обойтись без перебора в олимпиадной арифметической задаче
Сообщение11.04.2017, 14:58 
Заслуженный участник


11/05/08
32166
al12345 в сообщении #1208639 писал(а):
$n^2/11=a0b --> a+b=11$ и
дальше всё-таки лучше перебор. Ведь двузначных квадратов совсем немного: $16,\ 25,\ 36,\ 49,\ 64,\ 81$. Дальше ничего считать не надо -- сразу видно, что нолик получается только из $64$.

 Профиль  
                  
 
 Re: Обойтись без перебора в олимпиадной арифметической задаче
Сообщение11.04.2017, 16:44 
Аватара пользователя


01/12/11

8634
svv в сообщении #1208627 писал(а):
Эта задача есть в книжке Перельмана «Занимательная алгебра». Она называется «Номер автомашины».
...

(Оффтоп)

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

 Профиль  
                  
 
 Re: Обойтись без перебора в олимпиадной арифметической задаче
Сообщение11.04.2017, 19:38 


11/04/17
15
ewert в сообщении #1208649 писал(а):
дальше всё-таки лучше перебор.


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

 Профиль  
                  
 
 Re: Обойтись без перебора в олимпиадной арифметической задаче
Сообщение11.04.2017, 20:58 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
Перельмана не читал, но одобряю.
$\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. Тут я вынужден признать, что два варианта рассмотреть придётся :D

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

В принципе здесь то же самое, но вот в этом переходе:
al12345 писал(а):
$n^2=4(mod 9)$ --> n=2 или 7 (mod 9),
как мне кажется, сидит неявный перебор.

 Профиль  
                  
 
 Re: Обойтись без перебора в олимпиадной арифметической задаче
Сообщение11.04.2017, 23:11 


11/04/17
15
worm2 в сообщении #1208784 писал(а):

В принципе здесь то же самое, но вот в этом переходе:
al12345 писал(а):
$n^2=4(mod 9)$ --> n=2 или 7 (mod 9),
как мне кажется, сидит неявный перебор.


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

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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group