Международная Математическая Oлимпиада — решение первой задачи
Дано целое число n > 100. Ваня написал числа n, n+ 1, . . . , 2n на n+ 1 карточке, каждое по одному разу. Затем он перемешал колоду из этих карточек и разделил её на две стопки. Докажите, что хотя бы одна из двух стопок содержит две карточки, сумма чисел на которых — точный квадрат.
Предположим, у нас есть карточки со всеми целыми числами от 100 до 200 включительно. Из этого следует, что суммы двух карточек могут быть от 100 + 101 = 201 до 199 + 200 = 399. В этом промежутке есть несколько точных квадратов, а именно, квадраты чисел от 15 до 19: 225, 256, 289, 324, 361. Каждый из этих пяти точных квадратов может быть суммой двух карточек.
Представим, что мы положили карточку 100 в одну стопку. Тогда карточки с числами 125, 156 и 189 не могут быть в той же стопке, потому что 100 + 125 = 225, 100 + 156= 256, 100 + 189 = 289 — точные квадраты. Значит, 100 и 125, а также 156 и 189 идут в разные стопки. Значит, 125 и 156 должны быть вместе в одной стопке. Если бы их сумма была точным квадратом, то мы бы уже получили противоречие, т.е. доказали невозможность разложить по двум стопкам, чтобы не было суммы-квадрата в одной из них. Но, может, если мы дальше будем таким образом определять, какие карточки должны быть в разных стопках, а какие из-за этого — в одинаковых, рано или поздно придем к противоречию. Задача требует доказать, что это всегда будет так, причем не только для промежутка от 100 до 200, но и если карточки например все числа от 400 то 800, или от 1000 до 2000, от любого числа до него же, но в два раза больше(n, n+ 1, . . . , 2n), начиная со 100, так как n > 100.
Рассмотрим разности между релевантными квадратами: 225, 256, 289, 324 и 361 — разности между ними: 31, 33, 35 и 37.
Например n = 100, тогда n, число 100, дополняет до квадрата 225 число 125, число 125 дополнит 100 + 31 до следующего квадрата 225 + 31 = 256. Если числа 100 и 131 будут находится в разных стопках, то для числа 125 теперь нет места ни в одной из них. Следовательно, 100 и 131 должны быть в одной стопке, а также 100 и 133, 100 и 135, повторяя последовательность между разностями рассмотренных квадратов. Но, с одной стороны, пользуясь разностью 33, 100 и 133 должны быть в одной стопке. С другой стороны, пользуясь разностью 31, 102 и 133 должны быть в одной стопке. Значит, 100 и 102 в одной стопке, и так далее, продолжая находиться в определенной границе.
Начнем с числа 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 вместе, Q.E.D. (аббревиатура от лат. quod erat demonstrandum — «что и требовалось доказать»).