Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

решение первой задачи

Первая задача Международной математической олимипиады - традиционно самая легкая из шести. В этом году я смог ее решить. И наверное смогу объяснить решение.

Задача 1. Дано целое число n >= 100. Ваня написал числа n, n+1, . . . , 2n на n+1 карточке, каждое по одному разу. Затем он перемешал колоду из этих карточек и разделил её на две стопки. Докажите, что хотя бы одна из двух стопок содержит две карточки, сумма чисел на которых — точный квадрат.

Объяснение. Возьмем например n=100. У нас есть карточки со всеми числами от 100 до 200 включительно. Суммы двух карточек соответственно могут быть от 100+101 = 201 до 199+200 = 399. В этом промежутке есть несколько точных квадратов, а именно квадраты чисел от 15 до 19: 225, 256, 289, 324, 361. Каждый из этих пяти точных квадратов может в принципе быть суммой двух карточек.

Предположим, мы положили карточку 100 в одну стопку. Тогда карточка 125 не может быть в той же стопке, потому что 100+125 = 225, точный квадрат. Значит, 100 и 125 идут в разные стопки. 100 и 156, например - тоже. Значит, 125 и 156 должны быть вместе в одной стопке. Если бы их сумма была точным квадратом, то мы бы уже получили противоречие, т.е. доказали невозможность разложить по двум стопкам, чтобы не было суммы-квадрата в одной из них. Но это не так, 129+156 это не точный квадрат. Но может если мы дальше будем таким образом определять, какие карточки должны быть в разных стопках, а какие из-за этого - в одинаковых, рано или поздно придем к противоречию. Задача требует доказать, что это всегда будет так, причем не только для промежутка от 100 до 200, но и если карточки например все числа от 200 то 400, или от 1000 до 2000, короче от любого числа до него же, но в два раза больше, начиная со 100.

Подсказка. Если начать с маленьких n, например n=4, то утверждение неверно. Попробуйте разбить по стопкам числа 4,5,6 итд., до тех пор, пока сможете удержаться от того, чтобы сумма двух карточек в одной стопке была квадратом. До 19 точно можно довести. Попытайтесь почувствовать, что именно мешает положить число в ту или иную стопку чаще всего.

Не читайте дальше, если хотите решать самостоятельно.

[Spoiler (click to open)]

Идея 1. Рассмотрим разности между релевантными квадратами. Например n=100 квадраты 225,256,289,324,361, разности между каждым и предыдущим 31, 33, 35, 37. Если например число 100 дополняет до квадрата 225 число 125, то то же самое 125 дополнит 100+31 до следующего квадрата 225+31=256. Почему это важно? Потому что если 100 и 131 сидят в разных стопках, то для 125 теперь нет места. И следовательно, 100 и 131 должны быть в одной стопке, а также 100 и 133, 100 и 135, 100 и 137. Это верно и если начать не с 100, а с других чисел (лишь бы аналог "125" оставался в границах между 100 и 200).

Идея 2. С одной стороны, пользуясь разностью 33, 100 и 133 должны быть в одной стопке. С другой стороны, пользуясь разностью 31, 102 и 133 должны быть в одной стопке. Значит, 100 и 102 в одной стопке, и двигаясь дальше, 104 106 и так далее (в определенных границах). Собирая так числа вместе, можно надеяться придти к противоречию.

Решение для n=100. На карточках написаны числа от 100 до 200. Возьмем половину от первого четного квадрата в промежутке между 200 и 400: 256/2 = 128. Мы стремимся доказать, что 126, 128 и 130 все в одной стопке, и тогда 126+130 = 256 доказывает невозможность разделить на стопки.

Начинаем с 126: 126 + 198 = 324 (квадрат), и 163 + 198 = 361 (квадрат), значит 126 и 163 в разных стопках (разность 37). 163+161=324 и 128+161=289, значит 163 и 128 в разных стопках (разность 35). Вывод, 126 и 128 вместе. Теперь повторям то же самое, но прибавляем не 198 и 161, а на два меньше: 128+196=324, 165+196=361, 165+159=324, 130+159=289 и получаем, что 128 и 130 вместе. Доказательство окончено.

Общее решение для n>=100. Идея та же. Берем первый четный квадрат, который может быть суммой, делим пополам, отнимаем 2 (в решение выше это 256, 128, 126). Доказываем, что это число в одной стопке с +2 и +4, его сумма с +4 это исходный четный квадрат (126+130=256). Единственная причина, по которой это может не получиться, это что числа, которыми нам нужно оперировать, выходят за границы нашего интервала от n до 2n. Интуитивно говоря, раз между суммами карточек от 100 до 200 уместилось четыре квадрата, начиная с четного (256,281,324,361), то для больших n тем более уместится столько. Дальше идет много выкладок, если идея ясна, можно их пропустить.

Чтобы доказать строго, будем плясать от квадратов: пусть первый четный квадрат это (2k)^2=4k^2 (для 256 это k=8). Все четыре квадрата, что нам нужны: 4k^2, 4k^2+4k+1, 4k^2+8k+4, 4k^2+12k+9. Разности между ними: 4k+1, 4k+3, 4k+5. Нижняя граница n никак не больше 2k^2-1 (чтобы могла получиться сумма 4k^2), но чем эта граница меньше, тем "опаснее" для нас, поэтому рассмотрим ситуацию, когда она равна половине предыдущего четного квадрата, (2k-2)^2 = 4k^2 - 8k + 4, и половина этого 2k^2-4к+2. Тогда сумма двух разных карточек все еще не может дать квадрат (2k-2)^2, так что первый четный квадрат в сумме все еще 4k^2. Если мы посмотрим на доказательство случая n=100, то увидим, что самое большое число, которое приходилось добавлять - это от 126 до 324 (т.е. 198, подозрительно близко к максимальному возможному 200). В
наших обозначениях это идти от 2k^2-2 до 4k^2+8k+4, т.е. надо добавить 2k^2+8k+6 (для k=8 это как раз 198, проверка). И нам нужно, чтобы эта добавка не превышала 2n, т.е. 4k^2 - 8k + 4. Неравенство 4k^2 - 8k + 4 >= 2k^2+8k+6 упрощается в k^2-8k >= 1. Мы видим, что для k>8 это всегда верно, так что для всех n>128 утверждение доказано. Если же взять крайний случай k=8, то для самого "опасного" n=2k^2-4к+2=98 неравенство не выполняется, и мы не можем утверждать, что доказали невозможность разделить на две стопки. Но от нас требуется начать с n=100, а не n=98, так что если мы подправим неравенство и дадим "бонус" +4 левой части (верхняя граница не 196, а минимум 200), то получим 4k^2-8k+8 >= 2k^2+8k+6 -> k(k-8) >= -1, что разумеется верно и для k=8. Это доказывает утверждение для всех n от 100 до 128 и завершает доказательство.
Tags: математика
Subscribe

Recent Posts from This Journal

  • новая книга канемана

    "Thinking, Fast and Slow" Даниэля Канемана была опубликована в 2011-м году, десять лет назад, и стала немедленным бестселлером. Канеман ввел в…

  • об истории и исторических книгах

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

  • еще раз о принцессе-невесте

    Пять лет назад я написал о том, что появился пиратский (возможно) перевод "Принцессы-невесты" Уильяма Голдмана, без имени переводчика. И только…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 30 comments

Recent Posts from This Journal

  • новая книга канемана

    "Thinking, Fast and Slow" Даниэля Канемана была опубликована в 2011-м году, десять лет назад, и стала немедленным бестселлером. Канеман ввел в…

  • об истории и исторических книгах

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

  • еще раз о принцессе-невесте

    Пять лет назад я написал о том, что появился пиратский (возможно) перевод "Принцессы-невесты" Уильяма Голдмана, без имени переводчика. И только…