LIII Международная Математическая Олимпиада

[Dave]

LIII Международная Математическая Олимпиада.
Мар-дель-Плата, Аргентина, июль 2012.

День первый.
1. Дан треугольник $ABC$; точка $J$ является центром вневписанной окружности, соответствующей вершине $A$. Эта вневписанная окружность касается отрезка $BC$ в точке $M$, а прямых $AB$ и $AC$ - в точках $K$ и $L$ соответственно. Прямые $LM$ и $BJ$ пересекаются в точке $F$, а прямые $KM$ и $CJ$ - в точке $G$. Пусть $S$ - точка пересечения прямых $AF$ и $BC$, а $T$ - точка пересечения прямых $AG$ и $BC$.

Докажите, что точка $M$ является серединой отрезка $ST$.


2. Дано целое число $n \geqslant 3$ и действительные положительные числа $a_2,a_3,\dots,a_n$, удовлетворяющие соотношению $a_2a_3 \cdots a_n=1$. Докажите, что

$$(a_2+1)^2(a_3+1)^3\dots(a_n+1)^n>n^n.$$

3. Два игрока $A$ и $B$ играют в игру Угадай-ка. Правила этой игры зависят от двух положительных целых чисел $k$ и $n$, и эти числа известны обоим игрокам.

В начале игры $A$ выбирает целые числа $x$ и $N$ такие, что $1\leqslant x \leqslant N$. Игрок $A$ держит число $x$ в секрете, а число $N$ честно сообщает игроку $B$. После этого игрок $B$ пытается получить информацию о числе $x$, задавая $A$ вопросы следующего типа: за один вопрос $B$ указывает по своему усмотрению множество $S$, состоящее из целых положительных чисел (возможно, это множество уже было указано в одном из предыдущих вопросов) и спрашивает игрока $A$, принадлежит ли число $x$ множеству $S$. Игрок $B$ может столько вопросов, сколько он хочет. На каждый вопрос игрока $B$ игрок$A$ должен сразу ответить да или нет, при этом ему разрешается соврать столько раз, сколько он хочет; единственное ограничение состоит в том, что из любых $k+1$ подряд идущих ответов хотя бы один ответ должен быть правдивым.

После того, как $B$ задаст столько вопросов, сколько он сочтет нужным, он должен указать множество $X$, содержащее не более чем $n$ целых положительных чисел. Если $x$ принадлежит $X$, то $B$ выиграл; иначе $B$ проиграл. Докажите, что:

1. Если $n \geqslant 2^k$, то $B$ может гарантировать себе выигрыш.
2. Для всякого достаточно большого $k$ найдется целое число $n \geqslant 1{,}99^k$, при котором $B$ не сможет гарантировать себе выигрыш.

Привел в соответствие с официальным русским текстом // zhoraster

[zhoraster]

(Оффтоп)

Я предлагал назвать по-русски игру Ври, да не завирайся; по-моему, это совершенно в точку, но не назвали. По-украински игрок $A$ женского пола, как в оригинале, а игра называется Ти ж мене пiдманула (ты ж мэнэ пидманула).

[arqady]

Dave в сообщении #594282 писал(а):

2. Дано целое число $n \geqslant 3$ и действительные положительные числа $a_2,a_3,\dots,a_n$, удовлетворяющие соотношению $a_2a_3 \cdots a_n=1$. Докажите, что

$$(a_2+1)^2(a_3+1)^3\dots(a_n+1)^n>n^n.$$

Помогает старая как мир идея: для $x>0$ верно $(1+x)^n\geq\frac{n^nx}{(n-1)^{n-1}}$

[xmaister]

Dave в сообщении #594282 писал(а):

2. Дано целое число $n \geqslant 3$ и действительные положительные числа $a_2,a_3,\dots,a_n$, удовлетворяющие соотношению $a_2a_3 \cdots a_n=1$. Докажите, что

$$(a_2+1)^2(a_3+1)^3\dots(a_n+1)^n>n^n.$$

Вроде бы запилил...
Рассмотрим набор $1+x,1,1,1,\ldots ,\frac1{1+x}$, тогда $(2+x)^2\cdot\ldots\cdot \left(1+\frac{1}{x+1}\right)^n\ge 2^{\frac{n(n+1)}{2}-1}$ при $x\ge 0$. Для наборов вида $1+x,1,1 \ldots a_{k+1},a_{k+2},\ldots ,a_{n}$, $x\ge 0,a_i <1,i=k+1,\ldots ,n$ получаем существование набора $1+x,1,1\ldots, b_n, b_n<1$, такой что $(2+x)^2\cdot\ldots\cdot (1+a_{k+1})^{k+1}\cdot \ldots\cdot (1+a_n)^n\ge (2+x)^2\cdot\ldots\cdot \left(1+b_n\right)^n$. Аналогичным образом для произвольного набора $1+x_1,\ldots ,1+x_k, a_{k+1},\ldots a_n$ получим существование набора $1+x,1,1,\ldots ,\frac1{1+x}$. Отсалось доказать, что $2^{\frac{n(n+1)}{2}-1}>n^n$.

[xmaister]

(Оффтоп)

griboedovaa в сообщении #594414 писал(а):

адача под ноиером 2,чтл в ней олиириадного?не компетентное жюри имхо

Наверное, в условиях соревнования, и на таких задачах затупить можно...

[Dave]

День второй.
4. Найдите все функции $f \colon \mathbb Z \to \mathbb Z$ такие, что для всех $a+b+c=0$ :

$$f(a)^2+f(b)^2+f(c)^2=2f(a)f(b)+2f(b)f(c)+2f(c)f(a).$$

5. Пусть $ABC$ - треугольник с $\angle BCA = 90 \textdegree$ и $D$ - основание высоты, опущенной из вершины $C$. Пусть $X$ - некоторая точка внутри отрезка $CD$. $K$ - точка на отрезке $AX$ такая, что $BK=BC$. Аналогично, $L$ - точка на отрезке $BX$ такая, что $AL=AC$. Пусть также $M$ - точка пересечения $AL$ и $BK$.
Докажите, что $MK=ML$.

6. Найдите все натуральные числа $n$, для которых существуют неотрицательные целые числа $a_1,a_2,\dots,a_n$ такие, что:

$$\frac 1 {2^{a_1}} + \frac 1 {2^{a_2}} + \dots + \frac 1 {2^{a_n}} = \frac 1 {3^{a_1}} + \frac 2 {3^{a_2}} + \dots + \frac n {3^{a_n}} = 1.$$

[Профессор Снэйп]

По задаче 4 нарыл следующее.

1) Полагаем $a = b = c = 0$, получаем $3f(0)^2 = 6f(0)^2$, откуда $f(0) = 0$.

2) Полагаем $c = 0$ и $b = -a$, получаем $f(a)^2 + f(-a)^2 = 2f(a)f(-a)$, $(f(a) - f(-a))^2 = 0$ и $f(a) = f(-a)$.

3) Полагаем $b = -(a+1)$, $c = 1$. Получаем... $f(a+1)^2 - 2f(a+1)(f(a) + f(1)) + (f(a) - f(1))^2 = 0$. Рассматриваем это дело как квадратное уравнение для $f(a + 1)$. Его дискриминант равен $16f(1)f(a)$. Отсюда $f(1)f(a)$ всегда неотрицательно и является полным квадратом. В частности, функция $f$ определена с точностью до знака и можно считать, что $f(x) \geqslant 0$ для всех $x \in \mathbb{Z}$.

Будем думать дальше...

[Tanechka]

Я сначала сделала 2 шага предыдущего поста, потом получила, что $f(2a)=4f(a)$, а затем подставила $b=na$, а $c=-(n+1)a$ (использовала то, что $f(na)=tf(a)$). В итоге, после решения квадр. уравнения отсносительно $c$ получилось, что, если $f(na)=tf(a)$, то $f((n+1)a)=(\sqrt{t}\pm 1)^2 f(a)$. В совокупности с $f(2a)=4f(a)$ мы обнаруживаем всю квадратную сущность этой функции.

[Профессор Снэйп]

Tanechka в сообщении #594618 писал(а):

...потом получила, что $f(2a)=4f(a)$...

Там, на самом деле, получается, $f(2a) = 4f(a) \vee f(2a) = 0$.

[Tanechka]

Профессор Снэйп в сообщении #594621 писал(а):

Tanechka в сообщении #594618 писал(а):

...потом получила, что $f(2a)=4f(a)$...

Там, на самом деле, получается, $f(2a) = 4f(a) \vee f(2a) = 0$.

Мы $f(1)$ можем принять за любое целое число, а из него получать все остальные. То, что $f(0) = 0$ мы использовали только в выводе вашего второго пункта.

[Профессор Снэйп]

Tanechka в сообщении #594624 писал(а):

Мы $f(1)$ можем принять за любое целое число, а из него получать все остальные.

Не понял Вашего возражения. Покажите, как выводится $f(2a) = 4f(a)$. Я не вижу препятствий к тому, что $f(1) = 1$ и $f(2) = 0$. Также не вижу препятствий к тому, что $f(1) = 1$ и $f(2) = 4$. Почему $f(2)$ однозначно выводится из $f(1)$?

Так же не вижу, почему $f(1)$ может быть произвольным.

-- Чт июл 12, 2012 12:36:41 --

У меня получилось $f(a+1) = f(a) + f(1) \pm 2\sqrt{f(a)f(1)}$. Теперь сделаем так:

$$ f(a) &= f(-a) = f(-a-1+1) = f(-a-1) + f(1) \pm 2\sqrt{f(-a-1)f(1)} = f(a+1) + f(1) \pm 2\sqrt{f(a+1)f(1)} $$

Получается, $f(a+1)$ выражается из $f(a)$ по тому же закону, по которому $f(a)$ выражается из $f(a+1)$. Правда, там плюс-минус... Сейчас ещё формулки подёргаю.

[Tanechka]

Подставим $a$, $a$ и $-2a$:

$f(a)^2+f(a)^2+f(2a)^2=2f(a)^2+4f(a)f(2a)

Или $f(2a)=0$ или $f(2a)=4f(a)$.

Если первый вариант, то при $n=2$ $t=0$, если второй - то при $n=2$ $t=2$.

[Профессор Снэйп]

Tanechka в сообщении #594633 писал(а):

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

Вы уж выражайтесь точнее. Сначала Вы написали, что возможен лишь один вариант. Теперь вроде как признаёте, что возможны оба. Я Вас правильно понимаю?

-- Чт июл 12, 2012 12:46:33 --

Профессор Снэйп в сообщении #594626 писал(а):

Сейчас ещё формулки подёргаю.

Ага, надо на знаки и порядок посмотреть. Я вроде как уже писал, что функцию $f$ можно считать неотрицательной. Тогда если в первом выражении плюс, то во втором минус. И наоборот.

-- Чт июл 12, 2012 12:49:53 --

А, ну вот и всё! Складываем два равенства, корни с противоположными знаками уходят. Получаем $f(1) = 0$. И далее $f(a+1) = f(a)$ для произвольного $a$. Значит, $f$ тождественно нулевая, других вариантов нет. Уррра!!!

-- Чт июл 12, 2012 12:56:49 --

Как-то чересчур замудрёно до ответа в задаче 4 дошёл. Надо теперь подумать о простом изящном решении.

[Tanechka]

Если $f(2a)=0$. Сумма трёх целых чисел равна 0. Нетрудно заметить, что найдётся хотя бы одно чётное число (пусть будет $c$). Тогда всё что остаётся от первоначального равенства, это:

$$f(a)^2+f(b)^2=2f(a)f(b)$$

Или:

$$f(a)^2+f(b)^2-2f(a)f(b)=0 \Rightarrow (f(a)-f(b))^2=0$$

Мы вольны выбирать любые переменные одной чётности, значит $f(a)=C$ для всех нечётных $a$. Вот вам одна функция!
Остался случай если $f(2a)=4f(a)$. Но я его долго буду писать... Пожалуй я его потом опишу...

[Профессор Снэйп]

Tanechka в сообщении #594642 писал(а):

Остался случай если $f(2a)=4f(a)$. Но я его долго буду писать...

Э, пардон. Случаев не $2$, а бесконечно много. Для одних $a$ может выполняться $f(2a) = 4f(a)$, для других $f(2a) = 0$.

Впрочем, я ведь уже доказал, что $f \equiv 0$, так что оба варианта одинаковы. Или Вы не согласны с тем, что $f$ тождественно нулевая?