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

[avva]

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

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

Comments

[livelight]

> Первая задача Международной математической олимипиады - традиционно самая легкая из шести

На мой взгляд, вторая гораздо легче: берём n=1, а потом по индукции добавляем по одному новому xn и смотрим, что добавилось слева и справа.

[avva]

Не работает так по-моему.

[shufel]

Вторую полностью решили 16 человек из всех участников (первую - 286, третью - 15, шестую - 37).
Так что точно не легче.

[southwest]

Кто победил-то в Олимпиаде?

[chuka_lis]

не совсем понятно, почему при произвольном размешивании и делении стопок, допустим, по 50 карточек в каждой, должно работать вот это предположение:
"Предположим, мы положили карточку 100 в одну стопку. Тогда карточка 125 не может быть в той же стопке, потому что 100+125 = 225, точный квадрат. Значит, 100 и 125 идут в разные стопки. 100 и 156, например - тоже"

на мой взгляд, если Ваня размешал карточки без специальной укладки, то нет никаких обязательных причин ("тогда"), чтобы в одной стопке не лежали 100 и 125 -это ведь вероятностный процесс.
ну и аналогичное к "доказательствам". карточки "не должны", распределиться только потому что есть разницы между точными квадратами из их числе.
а могут быть хоть все потенциально в одной стопке, хоть ни одной.

[livelight]

Никто не говорил, что в каждой стопке по 50 карточек. Более того, карточек заведомо нечётное число.

[chuka_lis]

тем более.

[avva]

Нам надо доказать, что неважно, как распределились карты по двум стопкам - все равно будут две карты в одной стопке с суммой, равной квадрату. Поэтому если например в одной стопке оказались 100 и 125, то это конечно может быть так, но тогда мы "закончили": вот она, сумма 225, и уже не надо продолжать доказательство.

Поэтому я когда я все время говорю "100 не может быть в одной стопке с 125" или "100 обязан быть в одной стопке с 102", это такое сокращение, имеется в виду на самом деле "если это так, то всё легко, наша работа окончена, поэтому давайте предположим, что это не так, и докажем, что в таком случае все равно найдется другая какая-то пара карточек".

[emhanik]

Пусть (q+1)^2 <= n+1 < (q+2)^2
Из n>=100 следует q>=9
Представим квадраты в виде сумм:
(2q)^2 = (2q^2 - 1) + (2q^2 + 1)
(2q - 1)^2 = ((2q^2 - 1) - (4q - 1)) + (2q^2 + 1)
(2q + 1)^2 = (2q^2 + 1) + ((2q^2 + 1) + (4q - 1))
Покажем, что все внешние слагаемые содержатся среди карточек, т.е. принадлежат отрезку [n, 2n]
Из n+1 < (q+2)^2 следует
((2q^2 - 1) - (4q - 1)) - n > (2q^2 - 4q) - (q^2 + 4q + 3) = q(q-8)-3
Это выражение положительно, так как q >= 9
Из n+1 >= (q+1)^2 следует
2n - ((2q^2 + 1) + (4q - 1)) >= 2(q^2 + 2q) - (2q^2 + 4q) = 0
Получаем оценку внешних слагаемых:
n < (2q^2 - 1) - (4q - 1) < 2q^2 - 1 < 2q^2 + 1 < (2q^2 + 1) + (4q - 1) <= 2n
Допустим, ни в одной стопке нет двух карточек, дающих в сумме точный квадрат.
Пусть (2q^2 - 1) лежит в первой стопке. Тогда (2q^2 + 1) во второй. Тогда ((2q^2 - 1) - (4q - 1)) и ((2q^2 + 1) + (4q - 1)) лежат в первой. Но сумма последних - точный квадрат.

[anonymous]

Пусть a = 2m2 - 4m, b = 2m2 + 1, c = 2m2 + 4m.
Тогда a + b = (2m - 1)2, a + c = (2m)2, b + c = (2m + 1)2.
Нужно найти такое натуральное m, что n ≤ a < b < c ≤ 2n, то есть √(n/2+1)+1 ≤ m ≤ √(n+1)-1.
При 99 ≤ n ≤ 126 подойдёт m = 9.
При n ≥ 107 выполняется √(n+1) - √(n/2+1) ≥ 3, а значит, существует хотя бы одно целое m в искомом интервале.

[anonymous]

Для некоторых меньших n также существует подходящее m:
(n = 48): m = 6,
(63 ≤ n ≤ 70): m = 7,
(80 ≤ n ≤ 96): m = 8.

Для трёх значений n треугольников нет, но есть циклы длины 5:
(n = 49): 49, 51, 70, 74, 95;
(n = 71): 71, 73, 96, 100, 125;
(n = 97): 97, 99, 126, 130, 159 и 97, 99, 157, 132, 192.

Для остальных n граф двудольный.

[livelight]

Супер решение!

[anonymous]

Я тоже нашёл это решение (независимо), к нему приходишь стандартными шагами если искать простейший случай невозможности: 3-цикл на 3х подряд идущих квадратах.

2ю часть решения можно проще:

m решает задачу для n в интервале:
m2 + 2m <= n <= 2m2 - 4m

при m >= 9 интервалы для m и m + 1 перекрываются.