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