Киевские отборы на Всеукраинскую олимпиаду 2007

[RIP]

dm писал(а):

1. Пусть $a$, $b$, $c$~--- длины сторон некоторого треугольника.
Доказать неравенство:

$$2<\frac{a+b}{c}+\frac{b+c}{a}+\frac{c+a}{b}-\frac{a^3+b^3+c^3}{abc}\le3.$$

Неравенство легко преобразуется к очевидному

$$0<xyz\leqslant\frac18(x+y)(x+z)(y+z),$$

где $x=p-a,y=p-b,z=p-c,p$ - полупериметр.

Добавлено спустя 2 часа 53 минуты 56 секунд:

dm писал(а):

11 класс

1. а) Пусть $a$, $b$, $c$~--- действительные числа, для которых
$a+b+c=0$. Доказать, что: $a^3+b^3+c^3>0$ тогда и только тогда,
когда $a^5+b^5+c^5>0$. б) Пусть $a$, $b$, $c$, $d$~---
действительные числа, для которых $a+b+c+d=0$. Доказать, что:
$a^3+b^3+c^3+d^3>0$ тогда и только тогда, когда $a^5+b^5+c^5+d^5>0$.

а) это частный случай б) при $d=0$.
Обозначим $x=b+c,y=a+c,z=a+b$. Тогда $a=\frac{-x+y+z}2,b=\frac{x-y+z}2,c=\frac{x+y-z}2,d=-\frac{x+y+z}2$ и

$$a^3+b^3+c^3+d^3=-3xyz,\ a^5+b^5+c^5+d^5=-\frac52xyz(x^2+y^2+z^2)$$

[RIP]

dm писал(а):

4. На летние каникулы 2007 года приехали отдыхать дети в лагерь.
Каждая девочка посмотрела влюбленным взглядом на каждого мальчика,
которого знала, а каждый мальчик влюбленным взглядом~--- на девочек,
которых не знает. Сколько было в лагере детей, если всего было
влюбленных взглядов 143, а детей~--- не более 40.

Решать не хочется, просто условие понравилось.

dm писал(а):

9 класс
2. $ab+ac+bc\le 3ab$, $a,b,c>0$. Доказать, что $a^3+b^3+c^3\ge a+b+c$.

Опечатка. Должно быть $ab+ac+bc\leqslant3abc$. Тогда $\frac3{\frac1a+\frac1b+\frac1c}\geqslant1$, значит, $\frac{a+b+c}3\geqslant1$, значит, $\frac{a^3+b^3+c^3}3\geqslant\left(\frac{a+b+c}3\right)^3\geqslant\frac{a+b+c}3$

[La|Verd]

RIP писал(а):

Тогда $\frac3{\frac1a+\frac1b+\frac1c}\geqslant1$, значит, $\frac{a+b+c}3\geqslant1$

Что-то я не понял как из первого следует второе... как-то слишком лихо в знаменателе числа попереворачивали...

[Trius]

просто неравенство между средним арифметическим и гармоническим

[La|Verd]

Trius писал(а):

просто неравенство между средним арифметическим и гармоническим

Спасибо) Теперь все ясно.

[RIP]

dm писал(а):

I тур (3.02.2007)
11 класс

4. Назовем перестановку $\tau$ набора чисел $(1,2,\ldots,n)$
<<кубической>>, если $\tau(\tau(\tau(x)))=x$. Обозначим количество
подобных перестановок $a_n$. Доказать, что $a_{2007}$ делится нацело
на $3^{335}$.

Подстановка $\tau$ является кубической тогда и только тогда, когда в разложении в произведение независимых циклов все циклы имеют длину $1$ или $3$. Поэтому $a_n=a_{n-1}+(n-1)(n-2)a_{n-3}$ (отдельно рассматриваются подстановки, оставляющие $n$ на месте и все остальные). Кроме того, $a_1=a_2=1, a_3=3$.
Если $a_{3n}\equiv a_{3n+1}\equiv_{3n+2}\equiv0\pmod{3^k}$, то $a_{3(n+2)}\equiv a_{3(n+2)+1}\equiv a_{3(n+2)+2}\equiv0\pmod{3^{k+1}}$ (проверяется с помощью рекуррентного соотношения). При $n=1$ можно взять $k=1$, поэтому при $n=\frac{2007}3$ можно взять $k=\frac{n+1}2=335$.

Интересно оценить снизу наиб. степень $3$, на которую делится $a_n$. Я умею доказывать, что $3^{k_n}|a_n$, где $k_n=\lfloor\frac n3\rfloor+\lfloor\frac n9\rfloor-\lfloor\frac{2n}9\rfloor$.

Если взять $a_0=1$ и $f(x)=\sum\limits_{n=0}^{\infty}\frac{a_n}{n!}x^n$, то $f'(x)=(1+x^2)f(x)$, значит, $f(x)=\exp(x+x^3/3)$.
Обозначим $g(x)=\exp(\sum\limits_{n=0}^{\infty}\frac{x^{3^n}}{3^n})=\exp(x+x^3/3+x^9/9+\ldots)$.

Известна
Лемма (Дворк) Пусть $h(x)\in1+x\mathbb{Q}_p[[x]]$. Тогда $h(x)\in1+x\mathbb{Z}_p[[x]]\qquad\Longleftrightarrow\qquad\frac{h(x^p)}{h(x)^p}\in1+px\mathbb{Z}_p[[x]]$.

Здесь $p$ - простое число, $\mathbb{Q}_p$ - поле $p$-адических чисел, $\mathbb{Z}_p$ - кольцо целых $p$-адических чисел.
Поскольку $\frac{g(x^3)}{g(x)^3}=\exp(-3x)\in1+3x\mathbb{Z}_3[[x]]$, то $g(x)=\sum\limits_{n=0}^{\infty}b_nx^n$, где $b_n\in\mathbb{Z}_3$.

$$f(x)=g(x)\exp(-x^9/9-x^{27}/{27}-\ldots),$$

следовательно,

$$\frac{a_n}{n!}=\sum_{n_1+\sum_{k=2}^{\infty}3^kn_k=n}b_{n_1}\frac{(-1)^{n_2+n_3+n_4+\ldots}}{3^{2n_2+3n_3+4n_4+\ldots}n_2!n_3!n_4!\ldots}$$

Каждое слагаемое справа содержит в знаменателе тройку в степени не выше

$$2n_2+3n_3+4n_4+\ldots+\sum_{k=1}^{\infty}\left\lfloor\frac{n_2+n_3+n_4+\ldots}{3^k}\right\rfloor\leqslant\left\lfloor\frac{2n}9\right\rfloor+\sum_{k=1}^{\infty}\left\lfloor\frac{n}{3^{k+2}}\right\rfloor$$

Следовательно, $\nu_3(a_n)\geqslant\lfloor\frac n3\rfloor+\lfloor\frac n9\rfloor-\lfloor\frac{2n}9\rfloor$

[Хорхе]

Ну это слишком круто... Там индукцией доказывается совместное утверждение про делимость для последовательных троек. 335, конечно, мало, получается то ли 669, то ли 668.

[RIP]

Хорхе писал(а):

Ну это слишком круто... Там индукцией доказывается совместное утверждение про делимость для последовательных троек. 335, конечно, мало, получается то ли 669, то ли 668.

А вот и нет. Для $n$ кратных $9$ мой показатель $\frac{2n}9$ точный, т.е. $3^{446}||a_{2007}$ (это "видно" из моего док-ва, если его кто-то понял ).
Судя по численным расчетам первых нескольких членов, надо рассматривать цепочки из $9$ последовательных членов, и вроде можно найти наиб. степень тройки, которая равна $\frac{2n}9+\alpha_n$, где $\alpha_n$ периодическая с (наим.) периодом $9$, но меня ну уж очень ломает всё это проверять

Добавлено спустя 25 минут 30 секунд:

Похоже, что

$$\alpha_0=0,\alpha_1=-2/9,\alpha_2=-4/9,\alpha_3=1/3,\alpha_4=10/9,\alpha_5=-1/9=0,\alpha_6=8/3,\alpha_7=13/9,\alpha_8=2/9.$$

Добавлено спустя 13 минут 58 секунд:

По $p$-адическим числам очень рекомендую книжку Koblitz N. — p-adic numbers, p-adic analysis, and zeta-functions. В частности, лемма Дворка - это лемма 3 на стр.93.

[Руст]

RIP писал(а):

А вот и нет. Для $n$ кратных $9$ мой показатель $\frac{2n}9$ точный, т.е. $3^{446}||a_{2007}$ (это "видно" из моего док-ва, если его кто-то понял ).
Судя по численным расчетам первых нескольких членов, надо рассматривать цепочки из $9$ последовательных членов, и вроде можно найти наиб. степень тройки, которая равна $\frac{2n}9+\alpha_n$, где $\alpha_n$ периодическая с (наим.) периодом $9$, но меня ну уж очень ломает всё это проверять

Похоже, что

$$\alpha_0=0,\alpha_1=-2/9,\alpha_2=-4/9,\alpha_3=1/3,\alpha_4=10/9,\alpha_5=-1/9=0,\alpha_6=8/3,\alpha_7=13/9,\alpha_8=2/9.$$

RIp. Мне кажется, что ты ошибаешься. Если бы через девять шагов степень 3, на которую делится последовательность увеличивалось на 2, то это можно было бы вывести элементарными выкладками. Однако это у меня не получилость. Гарантированно увеличивается на 1 при шаге 6. Точные выкладки получились существенно расходящими от твоей формулы. Максимальное отклонение в верхнюю сторону при n=105 искомая величина 33 (по формуле 23), в нижнюю началось отклонение при n=603, максимальное при n=1989 и n=2006. Соответственно a(2006) делится всего на 426 ую степень, а искомая величина a(2007) делится на 429-ую степень согласно моим расчётам.

[RIP]

Если Вы про формулу

$$\left\lfloor\frac n3\right\rfloor+\left\lfloor\frac n9\right\rfloor-\left\lfloor\frac{2n}9\right\rfloor,$$

то я и сам знаю, что она не точна. Это лишь оценка снизу. Однако у меня есть все основания ожидать, что при $n$, делящихся на $9$, она дает точную степень. В Ваши расчеты не могла вкрасться арихметическая ошибка?

Судя по всему, то, что степень тройки растёт быстрее, чем на 1 при шаге 6, существенно использует тот факт, что $a_0=a_1=a_2$. Возможно, поэтому простые выкладки ничего не дают. Но похоже, что по поводу периодичности я всё же погорячился.

[Руст]

RIP писал(а):

Если Вы про формулу

$$\left\lfloor\frac n3\right\rfloor+\left\lfloor\frac n9\right\rfloor-\left\lfloor\frac{2n}9\right\rfloor,$$

то я и сам знаю, что она не точна. Это лишь оценка снизу. Однако у меня есть все основания ожидать, что при $n$, делящихся на $9$, она дает точную степень. В Ваши расчеты не могла вкрасться арихметическая ошибка?

Пусть m(n)=n%9, остаток числа n при делении на 9.
Эта формула точна, когда m(n)<4. Точная формула выглядит так:
$ord_3(a(n))=[\frac{2n-1}{9}]+t(m(n))+ord_3(n+a)$,
где $t(k)=0,k=0,1,2,3,5, \ t(k)=2,k=4,7, \ t(k)=1,k=6,8,
число a является 3-адическим числом (возможно рациональным, скорее всего алгебраическим над Z3 третьей степени).
Моё вычисление даёт a=2082(mod 6561).

[Trius]

Задачи 5-го тура(дополнительного)
1) Для всех положительных $x,y,z$ доказать:
$\frac{xyz}{x^3+y^3+xyz}+\frac{xyz}{y^3+z^3+xyz}+\frac{xyz}{z^3+x^3+xyz}\leq 1$
2) Функия $f:R\to R$ удоволетворяет условиям а) $f(0)=\frac{1}{2}$ б) для некоторого действительного $a$ равенство $f(x+y)=f(x)f(a-y)+f(y)f(a-x)$ исполняется для всех $x,y$. Доказать, что функция - константа.
3) В треугольнике $ABC$ провели высоту $AD$. На окружности, описанной вокруг треугольника $ADB$ взяли точку $X$, а на окружности описанной вокруг треугольника $ACD$ - точку $Y$. При этом точки $D,Y,X$ лежат на одной прямой. Точки $M,N$ -середины $XY$ и $BC$ соответственно. Доказать, что $MN$ и $MA$ перпендикулярны.
4) $P(x)$ - многочлен с целыми коефициентами. Последовательность $a_n$ - такая, что $a_2=P(a_1),a_3=P(a_2),...,a_n=P(a_1)$ Доказать, что $a_1=a_3$

[heap]

1)

$\frac{xyz}{x^3+y^3+xyz}+\frac{xyz}{y^3+z^3+xyz}+\frac{xyz}{z^3+x^3+xyz} \leqslant \frac{xyz}{x^2y+y^2x+xyz}+\frac{xyz}{y^2z+z^2y+xyz}+\frac{xyz}{z^2x+x^2z+xyz} = \frac{z}{x+y+z}+\frac{x}{y+z+x}+\frac{y}{z+x+y} =1$

Добавлено спустя 47 минут 19 секунд:

3)
$ \triangle BAC\sim\triangle XAY \Rightarrow \angle AMX = \angle ANB $
или , что то же самое
$ \angle AMD = \angle AND $
А это означает, что точки A, D, M и N лежат на одной окружности и, поэтому
$ \angle AMN = \angle ADN = \pi /2 $

[heap]

Trius писал(а):

Задачи 5-го тура(дополнительного)
2) Функия $f:R\to R$ удоволетворяет условиям а) $f(0)=\frac{1}{2}$ б) для некоторого действительного $a$ равенство $f(x+y)=f(x)f(a-y)+f(y)f(a-x)$ исполняется для всех $x,y$. Доказать, что функция - константа.

$$ f(a)= \frac 1 2 f(a) + \frac 1 2 f(a) = f(0)f(a-0)+f(0)f(a-0) = f(0+0)=f(0) $$

;

$$f(a- \frac x 2 )=f(0+(a-\frac x 2))=f(0)f(\frac x 2)+f(a-\frac x 2)f(a)=f(\frac x 2)f(a)+f(0)f(a-\frac x 2)=f(\frac x 2+0)=f(\frac x 2)$$

;

$$f(x)=f(\frac x 2+\frac x 2)=f(\frac x 2)f(a-\frac x 2)+f(\frac x 2)f(a-\frac x 2)=f(\frac x 2)f(\frac x 2)+f(a-\frac x 2)f(a-\frac x 2)=f(a)=\frac 1 2$$

[Karnat]

Trius писал(а):

1):) решить уравнение $1+2x+3x^2+4x^3+....+2007x^{2006}=0$

Почти такое же уравнение было на городской(областной) в Севастополе за 8класс в этом году, кстти первым номером