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

Каков минимальный размер набора целых чисел, обладающего таким свойством?

задан 25 Сен '17 23:41

изменен 25 Сен '17 23:44

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

Достаточно выяснить, сколько различных остатков от деления на 100 могут давать квадраты. Достаточно брать числа от 0 до 99. Далее, 99 заменяется на -1, 98 на -2 и так далее, и их квадраты повторятся. Остаются числа от 0 до 50. Их 51, то среди них есть кратные 10, и в квадрате они дают остаток 0. Поэтому значений меньше.

Теперь найдём точное значение. По модулю 4 квадраты дают в остатке 0 или 1. По модулю 25, достаточно рассматривать числа списка от 0 до 12. Можно исключить кратные 5, то есть 5 и 10. Останется 11 чисел. Можно вручную проверить, что остатки у этих квадратов будут все разные. Но можно рассуждать и так: остатка 0 уже не повторится, а если x^2 и y^2 дают одинаковые остатки при 0 < x < y < 13, то (y+x)(y-x) делится на 25. Оба сомножителя на 5 делиться не могут, и никакой не делится на 25, так как сумма y+x не больше 23. Значит, повторений нет.

Два значения mod 4 и 11 значений mod 25 дают 22 значения mod 100. Они все реализуются ввиду китайской теоремы об остатках.

Значит, минимальный набор состоит из 23 чисел.

ссылка

отвечен 25 Сен '17 23:59

@falcao, всё, что Вы рассказали правильно, но не совсем! Про 51 число не возражаю, но в книге С.А. Генкина почему-то 52 числа, на мой взгляд, это ошибочка. Искомый минимальный набор содержит 22 числа, а не 23, (это тоже ошибочка, но уже Ваша). Установить этот факт можно вручную, не зная китайской теоремы об остатках. Достаточно внимательно рассмотреть таблицу квадратов от 1 до 50, и убедится, что таблица содержит ровно 22 варианта остатков от деления на сто, включая ноль. Если же нуля нет, то есть два одинаковых остатка из 21.

(26 Сен '17 19:04) kipot_l

@kipot_l: пока что не вижу никакой ошибки. Вариантов 22, и если взять их, то совпадений не будет, и никакая разность квадратов не делится на 100.

Насчёт 52 чисел: думаю, это был расчёт на самое простое применение принципа Дирихле -- вариантов ведь 51, если не анализировать повторение нулей.

(26 Сен '17 19:24) falcao

@falcao, я немного подумал и пришёл к выводу, что Вы правы, - надо взять именно 23 числа. Но ручной способ перебора 50 остатков мне кажется веселее, числа х и 50 - х дают одинаковые остатки (!), плюс особенности чисел 5, 15, 25, ... и 10, 20, 30, ... Таблицу квадратов культурные школьники знают наизусть!

(26 Сен '17 19:54) kipot_l

@kipot_l: перебор, конечно, вещь часто интересная и приятная -- особенно с таблицей квадратов. Но я сознательно стремился его избежать даже по модулю 25, приводя соображения об отсутствии совпадений.

Наизусть, как мне кажется, "принято" было знать таблицу где-то до 32. Скажем, я её всегда помнил и часто этим пользовался, но значений типа 43^2 или 47^2, честно говоря, в памяти уже не держал.

(26 Сен '17 20:14) falcao

@falcao, задача оказалась интересна тем, что использовать в ней самое простое применение принципа Дирихле оказалось как-то уж очень скушно и неправильно. Есть обобщённый принцип Дирихле, когда в каждой клетке может сидеть (сидит) известное, но различное количество кроликов, в данном случае это 4 кролика, за исключением цифр 0 и 5, когда это 10 кроликов.

(26 Сен '17 20:20) kipot_l
1

@falcao, у меня же не совсем прямой перебор... Вместо х и 100-х предлагается рассмотреть х и 50-х, остатки у них при делении на 100 также одинаковые.

(26 Сен '17 20:24) kipot_l

@kipot_l: я вижу здесь применение самого обычного принципа Дирихле, так как повторы "персонально" учитываются.

(26 Сен '17 20:25) falcao

@kipot_l: я не обратил внимание на это замечание насчёт 50-x. А это важно, так как перебор значений до 25 в самом деле возможен "по памяти", то есть такой способ однозначно становится наиболее предпочтительным.

(26 Сен '17 21:37) falcao
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×10
×4

задан
25 Сен '17 23:41

показан
529 раз

обновлен
26 Сен '17 21:37

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

по почте:

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

по RSS:

Ответы

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

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