Украинские отборы на ММО-2012

[zhoraster]

temp03 в сообщении #572775 писал(а):

Но это оказалось наоборот.

Ничего удивительного, учитывая, что $\frac{(x+1)^3-(x+1)}{x^3-x}\to 1,x\to\infty$.

[Dave]

3.2. (По которой все участники отбора набрали в сумме 0 баллов).

Если рассматривать всевозможные расположения (наборы) $m$ чисел $\pm 1$ на окружности, то можно определить операцию суммирования таких наборов как выполнение произведения между парами соответствующих элементов. Заметим, что для любого набора $\alpha$: $\alpha+\alpha=0$, где $0$ - набор, состоящий из одних единиц.
Если перед каждым шагом Андрей будет поворачивать окружность на одно число против часовой стрелки, чтобы умножать приходилось всегда одну и ту же пару чисел, то преобразование $f$, производимое над набором, будет всегда одинаковым линейным преобразованием, $f(\alpha+\beta)=f(\alpha)+f(\beta)$. Это преобразование однозначно обратимо, $g$ - обратное к нему преобразование, которое также будет линейным. По индукции легко доказать, что и любая суперпозиция $g^i$ также будет линейной.
Будем рассматривать всевозможные многочлены с целыми коэффициентами от переменной $x$ и операции над ними, обращая внимание только на чётность коэффициентов получающихся многочленов. Так, к примеру, многочлены $x^m+2x+1$ и $x^m-1$ будут считаться эквивалентными (далее между ними будем просто писать знак равенства).
Мы можем также формально каждому такому многочлену $P(x)=\sum_i a_ix^i$ поставить в соответствие преобразование наборов $W_P(\eta)$, определённое по формуле

$$W_P(\eta)=\sum_i a_ig^i(\eta),$$

где преобразование $g^0$ не изменяет набор, как и умножение набора на $1$, а умножение на $0$ превращает набор в вышеописанный нулевой набор. Можно проверить, что для любого набора $\eta$ из $n$ чисел $\pm 1$ справедливо тождество

$$W_{D_n}(\eta)=0, \eqno(1)$$

где $D_n(x)=x^n+x+1$.
Если $\tau_n$ - начальный набор из $n$ чисел $-1$, то условие перехода его в себя после $k$ шагов можно записать как $W_{H_k}(\tau_n)=0$, где $H_k(x)=x^k+1$. Отсюда будет следовать, что

$$H_k(x) \equiv R(x)D_n(x) \eqno(2)$$

для некоторого многочлена $R(x)=\sum_i r_ix^i$. Нам нужно доказать, что

$$W_{H_{2^k-1}}(\tau_{2^n-1})=0. \eqno(3)$$

Это будет следовать из $(1)$ и $(2)$, если рассмотреть многочлен $S(x)=\sum_i r_i(x^{2^n}+x^2+x)^{2^i}$. С одной стороны, этот многочлен равен $C(x)(x^{2^n}+x^2+x)$, для некоторого многочлена $C(x)$, с другой - воспользовавшись тождеством $(P+Q)^{2^m}=P^{2^m}+Q^{2^m}$, справедливым (по модулю $2$) для любых многочленов $P$ и $Q$ и неотрицательного целого числа $m$, и $(2)$, можно получить, что $S(x)=x^{2^k}+x$. Деля равенство $x^{2^k}+x=C(x)(x^{2^n}+x^2+x)$ на $x$, применяя преобразование $W$, соответствующее каждой из частей, к $\tau_{2^n-1}$, учитывая $(1)$ для $n'=2^n-1$ и то, что умножение многочленов соответствует суперпозиции соответствующих преобразований $W$, получим $(3)$.
Если интересно, то могу написать более подробное решение.

[zhoraster]

Да, так она и решается. Подробнее см. у Бартольди.

[hippie]

#2.2

Обозначим $g(m,\ u)$ количество слов языка Муму, в которых ровно $m$ букв М и ровно $u$ букв У, и которые при этом заканчиваются на М.
Слово языка Муму, заканчивающееся на У может быть получено либо приписыванием к любому слову в конце буквы У, либо приписыванием к слову, заканчивающемуся на М, буквосочетания МУ. Поэтому $f(m,\ u)-g(m,\ u) = f(m,\ u-1)+g(m-1,\ u-1),$ т.е. $f(m,\ u)-f(m,\ u-1) = g(m,\ u)+g(m-1,\ u-1).$
Таким образом, доказываемое равенство переписывается в виде: $g(m,\ u)+g(m-1,\ u-1) = g(2u+1-m,\ u)+g(2u-m,\ u-1).$

По каждому слову (состоящему из ровно $m$ букв М и ровно $u$ букв У, и при этом заканчивающемуся на М), можно построить слово (состоящее из ровно $(2u+1-m)$ букв М и ровно $u$ букв У, и при этом заканчивающееся на М), следующим образом:
Если в начале исходного слова стоит М, то её удаляем, иначе — добавляем;
Если между $k$-й и $(k+1)$-й по счёту буквами У в исходном слове стоит $a_k$ букв М, то в построенном слове между ними стоит $(2-a_k)$ букв М.
Такое преобразование устанавливает взаимно однозначное соответствие между (словами языка Муму, в которых ровно $m$ букв М и ровно $u$ букв У, и которые при этом заканчиваются на М) и (словами языка Муму, в которых ровно $(2u+1-m)$ букв М и ровно $u$ букв У, и которые при этом заканчиваются на М).

Таким образом $g(m,\ u) = g(2u+1-m,\ u) и g(m-1,\ u-1) = g(2u-m,\ u-1),$ а, следовательно, и $g(m,\ u)+g(m-1,\ u-1) = g(2u+1-m,\ u)+g(2u-m,\ u-1).$

[zhoraster]

Ну что, осталось четвертый тур порешать? (Первую задачу даже не предлагаю )

[Dave]

2.2. Требуемое соотношение следует из двух таких:

$$f(m,u)=f(m,u-1)+f(m-1,u-1)+f(m-2,u-1), \; \forall u \geqslant 2, \, 2 \leqslant m \leqslant 2u \eqno(1)$$

$$f(2u-m,u)=f(m,u), \; \forall u \geqslant 1, \, 0 \leqslant m \leqslant 2u \eqno(2)$$

Оба они получаются, если любое слово в языке Муму записать как

$$\underbrace{\text{М..М}}_{a_0} \text{У} \underbrace{\text{М..М}}_{a_1} \text{У} \underbrace{\text{М..М}}_{a_2} \cdots \text{У} \underbrace{\text{М..М}}_{a_{u-1}} \text{У} \underbrace{\text{М..М}}_{a_u},$$

где все $a_i$ - целые числа от $0$ до $2$, кроме крайних двух, которые могут быть только $0$ или $1$, буква У в каждой группе ровно одна, $m=\sum\limits_{i=0}^n a_u$. $(1)$ получается, если мы распишем $f(m,u)$, выбрасывая крайнюю справа букву У вместе с предшествующей ей группой из $a_{u-1}$ букв М. $(2)$ же получается, если рассмотреть взаимно-однозначное соответствие между наборами $(a_0,a_1,\dots,a_{u-1},a_u)$, задающим слово из группы, соответствующей паре $(m,u)$ и $(1-a_0,2-a_1,\dots,2-a_{u-1},1-a_u)$, задающим слово из группы, соответствующей паре $(2u-m,u)$.

[zhoraster]

Приблизительно так, с точностью до замены У на М и наоборот.

[Dave]

zhoraster в сообщении #573056 писал(а):

Приблизительно так, с точностью до замены У на М и наоборот.

Так и не понял, где у меня ошибка. Или это замечание относилось к доказательству hippie?

Кстати, предлагаю всем желающим доказать, что

$$f(m,u)=\sum_a C_{u-1}^a C_{a+2}^{m-a},$$

где суммирование идёт по всем целым $a$, а биномиальный коэффициент $C_n^i$ считается равным нулю, если хотя бы одно из чисел $n$, $i$, $n-i$ отрицательно.

[zhoraster]

Все ок, это меня проглючило.

[Dave]

4.2.
Предполагается, что $m>1$, иначе доказывать нечего.
Пусть $n=km^{d+1}$. Каждое число $a \in \{1,2,\dots,n\}$ единственным образом представляется в виде

$$a=1+b_0+b_1m+b_2m^2+\ldots+b_dm^d+cm^{d+1},$$

где $b_i$ и $c$ - целые числа, $0 \leqslant b_i < m$, $0 \leqslant c < k$ ($b_i$ - младшие цифры в записи числа $a-1$ в системе счисления с основанием $m$). Тогда $a$ нужно отнести ко множеству с номером $(b_0+b_1+b_2+\ldots+b_d) \pmod m + 1$.
Для доказательства обозначим $M=\{0,1,2,\dots,m-1\}$, возьмём любую степень $t \leqslant d$, любое число $i \in M$ (индекс любого из множеств разбиения, уменьшенный на $1$) и рассмотрим сумму $t$-х степеней всех чисел, попавших в это множество:

$$\sum_{c=0}^{k-1} \; \sum_{\{b_0,b_1,b_2,\dots,b_d \in M \mid (b_0+b_1+b_2+\ldots+b_d)\!\!\!\!\!\pmod m = i\}} (1+b_0+b_1m+b_2m^2+\ldots+b_dm^d+cm^{d+1})^t.$$

Докажем, что внутренняя сумма от $i$ не зависит (тогда и внешняя тоже), зафиксировав любое значение $c$ и обозначив $z=1+cm^{d+1}$. Тогда внутренняя сумма равна

$$\sum_{\{b_0,\dots,b_d \in M \mid (b_0+\ldots+b_d)\!\!\!\!\!\pmod m = i\}} (z+b_0+b_1m+b_2m^2+\ldots+b_dm^d)^t=$$

$$=\sum_{\{b_0,\dots,b_d \in M \mid (b_0+\ldots+b_d)\!\!\!\!\!\pmod m = i\}} \sum_{\{u,t_0,\ldots,t_d \geqslant 0 \mid u+t_0+\ldots+t_d=t\}} \frac {t!} {u!t_0! \ldots t_d!} z^ub_0^{t_0}(b_1m)^{t_1}(b_2m^2)^{t_2}\ldots(b_dm^d)^{t_d}=$$

$$=\sum_{\{u,t_0,\ldots,t_d \geqslant 0 \mid u+t_0+\ldots+t_d=t\}} \frac {t!} {u!t_0! \ldots t_d!} z^um^{t_1+2t_2+\ldots+dt_d} \sum_{\{b_0,\dots,b_d \in M \mid (b_0+\ldots+b_d)\!\!\!\!\!\pmod m = i\}} b_0^{t_0}b_1^{t_1}b_2^{t_2} \ldots b_d^{t_d}.$$

Здесь, опять же, доказываем, что внутренняя сумма от $i$ не зависит при каждом фиксированном наборе чисел $u$ и $t_j$, "пришедших" из внешней суммы - тогда и внешняя сумма от $i$ не зависит. Т.к. $t \leqslant d<d+1$, то среди чисел $t_0,\dots,t_d$ будет как минимум одно, равное нулю - пусть $t_q=0$. Тогда внутренняя сумма просто разбивается в произведение независимых сумм, ибо $b_q$ всегда дополнит, причём единственным образом, любой набор остальных чисел $b_j$ до нужной суммы $i$ по модулю $m$:

$$\sum_{\{b_0,\dots,b_d \in M \mid (b_0+\ldots+b_d)\!\!\!\!\!\pmod m = i\}} b_0^{t_0}b_1^{t_1}b_2^{t_2} \ldots b_d^{t_d}=\sum_{\{b_0,\dots,b_d \in M \mid (b_0+\ldots+b_d)\!\!\!\!\!\pmod m = i\}} \prod_{j \in [0,d], j \ne q} b_j^{t_j}=$$

$$=\{b_q=(i-b_0-\ldots-b_{q-1}-b_{q+1}-b_d) \pmod m\} =\sum_{\{(b_j \in M),j \in [0,d],j \ne q\}} \prod_{j \in [0,d], j \ne q} b_j^{t_j}=\prod_{j \in [0,d], j \ne q} \sum_{b=0}^{m-1} b^{t_j}.$$

Итак, какую бы степень $t$, не превосходящую степень многочлена $P$, мы не взяли, суммы чисел, возведённых в эту степень, по разным множествам $A_i$ будут одинаковыми. Домножив каждую такую сумму на коэффициент при соответствующей степени многочлена $P$ и сложив по всем $t$, получим требуемое утверждение о равенстве $S(A_i)$.

(Оффтоп)

Кстати, коэффициенты многочлена вовсе не обязаны быть целыми для справедливости утверждения. Похоже, это был трюк "для отвода глаз" и он полностью удался, учитывая, что 12 участников набрали в сумме всего 3 балла по этой задаче.

Построенное разбиение, конечно же, не является единственным при $m>2$. Можно определять индекс множества как $(r_0b_0+r_1b_1+r_2b_2+\ldots+r_db_d) \pmod m + 1$, где $r_i$ - любые целые числа, взаимно-простые с $m$.

[zhoraster]

Это совпадает с конструкцией автора, хотя он то же самое строил по индукции. Только подходящее утверждение индукции надо взять: чтобы набор множеств подходил для всех многочленов этой или меньшей степени. В принципе, конструкция становится более понятной, если взять $m=2$ и $n=2^{d+1}$: следующее множество получается из предыдущего дописыванием к нему его инвертированной копии. То есть множества выглядят так (о - одно, х - второе; для удобства степени двойки я отделил палочками):
o|x|xo|xoox|xooxoxxo|xooxoxxooxxoxoox
и так далее

-- Пн май 21, 2012 14:45:36 --

Неравенство осталось. Самая простая задача в 3-м туре, наверное.

[Dave]

zhoraster в сообщении #574070 писал(а):

Это совпадает с конструкцией автора, хотя он то же самое строил по индукции. Только подходящее утверждение индукции надо взять: чтобы набор множеств подходил для всех многочленов этой или меньшей степени. В принципе, конструкция становится более понятной, если взять $m=2$ и $n=2^{d+1}$: следующее множество получается из предыдущего дописыванием к нему его инвертированной копии. То есть множества выглядят так (о - одно, х - второе; для удобства степени двойки я отделил палочками):
o|x|xo|xoox|xooxoxxo|xooxoxxooxxoxoox
и так далее

Самая большая проблема в этой задаче (по крайней мере у меня так было) - не построение или описание конструкции, а доказательство того, что она удовлетворяет условию. Хотелось бы посмотреть, как автор это делал. Хотя, конечно, автору - большой респект, это - типичная олимпиадная задача, ибо решение найти трудно, но само оно - короткое (в моём случае можно было бы закончить первой формулой с двумя суммами а потом сказать, что мы раскрываем скобки по многомерному биному Ньютона и используем то, что хотя бы одно $b_j$ в произведении всегда отсутствует, что даёт возможность избавиться от условия, содержащего $i$ и связывающего остальные индексы суммирования).

zhoraster в сообщении #574070 писал(а):

Неравенство осталось. Самая простая задача в 3-м туре, наверное.

К 3.3 у меня Access denied , я не знаю, что там было. Но вот что решил из 4-го тура.

4.3. Перепишем условие отборности так:

$$\left(\frac 1 {b^2} - 1 \right) \left(\frac 1 {c^2} - 1 \right) \geqslant \left(\frac a {bc} - 1 \right)^2.$$

Имеем такое условие на тройку $a,b,c$, а также на тройку $x,y,z$. Так как все числа - из отрезка $[-1,1]$, то существуют такие неотрицательные числа $b_1, c_1, y_1, z_1$, что $b_1^2=\frac 1 {b^2}-1$, $c_1^2=\frac 1 {c^2}-1$, $y_1^2=\frac 1 {y^2}-1$, $z_1^2=\frac 1 {z^2}-1$. Если мы обозначим $a_1=\frac a {bc}-1$, $x_1=\frac x {yz}-1$, то будем иметь неравенства: $b_1c_1 \geqslant |a_1|$ и $y_1z_1 \geqslant |x_1|$, а доказать нужно:

$$((b_1^2+1)(y_1^2+1)-1)((c_1^2+1)(z_1^2+1)-1) \geqslant ((a_1+1)(x_1+1)-1)^2,$$

что эквивалентно

$$(b_1^2y_1^2+b_1^2+y_1^2)(c_1^2z_1^2+c_1^2+z_1^2) \geqslant (a_1x_1+a_1+x_1)^2.$$

Ясно, что $|a_1x_1+a_1+x_1| \leqslant |a_1x_1|+|a_1|+|x_1| \leqslant b_1c_1y_1z_1+b_1c_1+y_1z_1$ и для завершения доказательства осталось использовать неравенство Коши-Буняковского для векторов $(b_1y_1,b_1,y_1)$ и $(c_1z_1,c_1,z_1)$.

[zhoraster]

Да, описАлся, в 4-м. 3.3 -- это некоторая геометрия, не слишком сложная.

Неравенство действительно сводится к Коши-Буняковскому разными способами. Можно его и штурмовать. Оно родилось из такого факта: если две симметричные матрицы неотрицательно определены, то их поэлементное произведение тоже неотрицательно определено. Более того, есть оценка снизу на определитель поэлементного произведения, которая дает такое обощение.

-- Пн май 21, 2012 21:24:23 --

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

Хотя, конечно, автору - большой респект, это - типичная олимпиадная задача, ибо решение найти трудно, но само оно - короткое (в моём случае можно было бы закончить первой формулой с двумя суммами а потом сказать, что мы раскрываем скобки по многомерному биному Ньютона[...]

По индукции достаточно обычного бинома. Построили множества на предыдущем шаге и размножаем их $m-1$ раз, каждый раз циклически сдвигая по модулю. И оно там выходит как-то само собой.

[zhoraster]

Добавил задачу 3.3.

[nnosipov]

zhoraster в сообщении #599456 писал(а):

Добавил задачу 3.3.

Там опечатка --- вместо "Описанная" должно быть "Вписанная".