IMC 2013

[Dave]

По 5-й задаче.

Теорема. Каково бы ни было множество $\mathfrak D \subseteq \mathbb N$, существует такая последовательность комплексных чисел $\{a_n\}_{n=1}^{\infty}$, что ряд $\sum\limits_{n=1}^{\infty} {a_n^d}$ сходится при $d \in \mathfrak D$ и расходится при $d \notin \mathfrak D$.
Более того, какова бы ни была последовательность комплексных чисел $\{b_n\}_{n=1}^{\infty}$, существует такая последовательность $\{a_n\}_{n=1}^{\infty}$, что $\sum\limits_{n=1}^{\infty} {a_n^d}=b_d$ при $d \in \mathfrak D$ и $\dfrac 1 {e^{ib_d}} \sum\limits_{n=1}^{\infty} {a_n^d}=+\infty$ (т.е. ряд уходит в бесконечность в заданном направлении) при $d \notin \mathfrak D$.

Доказательство. Пусть $\delta_{ij} = \begin{cases} 1, & i=j \\ 0, & i \ne j \end{cases}$ - символ Кронекера. Вначале докажем следующую лемму.

Лемма. Каковы бы ни были натуральные числа $d$ и $n$, $d \leqslant n$, а также действительное число $\varepsilon >0$ и комплексное число $z$, cуществует такой набор комплексных чисел $x_1,x_2,\dots,x_m$, что при $1 \leqslant k \leqslant n$:

$$\sum_{i=1}^m {x_i^k}=\delta_{kd} \, z ,$$

и, кроме этого, при $1 \leqslant r<m$:

$$\left| \sum_{i=1}^r {x_i^k} \right| < \delta_{kd}|z|+\varepsilon .$$

Доказательство леммы. Решим систему уравнений

$$\begin{cases} x_1+x_2+\dots+x_n=I_1 \\x_1^2+x_2^2+\dots+x_n^2=I_2 \\ \qquad \qquad \; \; \dots \\x_1^n+x_2^n+\dots+x_n^n=I_n ,\end{cases}$$

где $I_k = \delta_{kd} \, z$. Корни этой системы всегда существуют над полем комплексных чисел, они будут корнями соответствующего многочлена $n$-й степени, коэффициенты которого можно выразить, например, по формулам Ньютона-Жирара через известные значения $I_k$ симметрических многочленов от $x_i$. Пусть $\alpha=\max\limits_{i=1}^n {|x_i|}$. Подберём $m \in \mathbb N$ так, чтобы $\frac 1 {\sqrt[d]m} \alpha < \min \{1, \frac \varepsilon n\}$ и возьмём $\beta=\frac 1 {\sqrt[d]m}$. Тогда набор $\beta x_1,\beta x_2,\dots,\beta x_n$, записанный $m$ раз подряд, обладает требуемыми свойствами. $\Box$

Теперь выберем последовательность $\varepsilon_n \to 0$ и, пользуясь леммой, будем строить последовательность $\{a_n\}_{n=1}^{\infty}$ пошагово. $n$-й шаг состоит из таких частей:
а) "Загрязнители". Берутся все числа $d \leqslant n$, не принадлежащие $\mathfrak D$ (если таковые есть) и для каждого из них применяется лемма с $\varepsilon=\varepsilon_n \; \text{и} \; z=e^{ib_d}$. Полученные наборы $x_1,x_2,\dots,x_m$ последовательно добавляются в $\{a_n\}_{n=1}^{\infty}$.
б) "Ликвидатор". Если $n \in \mathfrak D$, то применяется лемма с $d=n, \; \varepsilon=\varepsilon_n \; \text{и} \; z=b_n-\sum_i {a_i^n}$, где сумма берётся по всем $a_i$, ранее добавленным в последовательность. Если $n \notin \mathfrak D$, то эта часть пропускается.

Видим, что построенная таким образом последовательность удовлетворяет требованиям теоремы. Действительно, если $n_d$ - количество членов в $\{a_n\}$ после $d$-го шага и $d \in \mathfrak D$, то на $d$-м шаге будет получена требуемая (конечная) сумма для $d$-х степеней, а далее любой отрезок $\sum\limits_{i=n_d+1}^r {a_i^d}$, будет состоять из отрезков, дающих нули и последнего отрезка, сумма в котором по модулю не превосходит $\varepsilon_{q_r}$, где $n_{q_r-1} \leqslant r < n_{q_r}$, $q_r \to \infty$ при $r \to \infty$. Если же $d \notin \mathfrak D$, то при $n_{q_r-1} \leqslant r < n_{q_r}$, $q_r \geqslant d$ в сумме $\sum\limits_{i=n_{q_r-1}+1}^r {a_i^d}$ находятся $q_r-d$ или $q_r-d+1$ отрезков, сумма в каждом из которых равна $e^{ib_d}$, несколько отрезков с нулевой суммой, а также последняя часть с суммой, не превосходящей по модулю $|e^{ib_d}|+\varepsilon_{q_r}$. Первое слагаемое постоянно, а второе стремится к нулю при $r \to \infty$, т.к. $q_r \to \infty$. $\blacksquare$

[Dave]

День 2:

5. Рассмотрим круглое ожерелье с нанизанными на него $2013$ бусинками. Каждая бусинка может быть раскрашена или в зелёный, или в белый цвет. Раскраска ожерелья называется хорошей, если среди любых $21$ последовательных бусинок есть хотя бы одна зелёная. Докажите, что количество хороших раскрасок ожерелья нечётно.
(Две раскраски, которые отличаюся некоторыми бусинками, но могут быть получены одна из другой вращением или переворотом ожерелья, считаются разными).

[Whitaker]

xmaister в сообщении #753501 писал(а):

День 2:
2. Пусть $p,q$-взаимно простые положительные. Докажите, что $\sum\limits_{k=0}^{pq-1}(-1)^{[\frac{k}{p}]+[\frac{k}{q}]}=0$, если $pq$- четно и $1$, если $pq$- нечетно.$ []$- целая часть.

Я попробовал вроде так: Так как в исходной задаче $k$ пробегает полную неотрицательную систему вычетов по модулю $pq$, то $k=px+qy$, где $x, y$ пробегают полные системы вычетов по модулям $q$ и $p.$ Тогда

$$\left[\frac{k}{p}\right]+\left[\frac{k}{q}\right]=x+\left[\frac{qy}{p}\right]+\left[\frac{px}{q}\right]+y=\left[\frac{(p+q)x}{q}\right]+\left[\frac{(p+q)y}{p}\right]$$

Заметим, что $\text{gcd}(q+p,p)=\text{gcd}(q+p,q)=1.$ Следовательно, $(p+q)x$ и $(p+q)y$ пробегает полные системы вычетов по модулям $q$ и $p$. Тогда искомая сумма равна

$$\sum \limits_{x}(-1)^{\left[\frac{rx}{q}\right]}\sum \limits_{y}(-1)^{\left[\frac{ry}{p}\right]},$$

где $r=p+q$, а $x$ и $y$ пробегают полные системы вычетов по модулям $q$ и $p.$
Дальше что-то не получается

[Sonic86]

Whitaker в сообщении #753749 писал(а):

Я попробовал вроде так: Так как в исходной задаче $k$ пробегает полную неотрицательную систему вычетов по модулю $pq$, то $k=px+qy$, где $x, y$ пробегают полные системы вычетов по модулям $q$ и $p.$ Тогда

$$\left[\frac{k}{p}\right]+\left[\frac{k}{q}\right]=x+\left[\frac{qy}{p}\right]+\left[\frac{px}{q}\right]+y=\left[\frac{(p+q)x}{q}\right]+\left[\frac{(p+q)y}{p}\right]$$

Там же не классы вычетов. Вместо $k=px+qy$ будет $k=px+qy-pqR_k$ для какого-то целого $R_k$. Тогда
$\left[\frac{k}{p}\right]+\left[\frac{k}{q}\right]=x+y+\left[\frac{qy}{p}\right]+\left[\frac{px}{q}\right]-pR_k-qR_k$
Если $p,q$ взаимно просты, то либо только одно из них четно, либо оба нечетны.

Если $p,q$ нечетны, то $p+q$ четно и тогда все-таки
$\left[\frac{k}{p}\right]+\left[\frac{k}{q}\right]\equiv x+y+\left[\frac{qy}{p}\right]+\left[\frac{px}{q}\right]\pmod 2$
И исходная сумма $S(p,q)$ раскладывается в произведение сумм:
$S(p,q)=\sum\limits_{x=0}^{p-1}(-1)^{\left[x\frac{p+q}{q}\right]}\sum\limits_{y=0}^{p-1}(-1)^{\left[y\frac{p+q}{p}\right]}$
Первая сумма равна 1. Слагаемое, соотв-ее $k=0$ равно $0$, а при $k\neq 0$ в силу взаимной простоты $p,q$ и четности $p+q$ все числа $\left[k\frac{p+q}{q}\right]$ нецелые и $\left[k\frac{p+q}{q}\right]+\left[(q-k)\frac{p+q}{q}\right]\equiv [t]+[-t]\equiv 1\pmod 2$, поэтому сумма соотв-их слагаемых в сумме равна нулю, т.е. вся сумма равна 1.
Аналогично 2-я сумма равна 1.

Если $p$ четно, а $q$ нечетно, то вектор значений $w_q(k), k=0,...,pq-1$ значений $\left[\frac{k}{q}\right]\pmod 2$ центрально антисимметричен (ЦАС, т.е. $w_q(pq-1-k)=1-w_q(k)$), а вектор значений $w_p(k), k=0,...,pq-1$ центрально симметричен (ЦС). $\text{ЦАС + ЦС = ЦАС}$, $\text{ЦАС}$ содержит одинаковое число нулей и единиц, потому сумма $\sum\limits_{k\in\text{ЦАС}} (-1)^{w(k)}=0$

Можно попробовать вычислить и без взаимной простоты $p,q$ (например, $S(2p,2q)=2S(p,q)$) А еще это напоминает одно из доказательств квадратичного закона взаимности, хотя, видимо, связи нет.

[bot]

без взаимной простоты будет $ gcd(p,q)^2$ в нечетном случае и нуль - в четном.

[dm]

Предварительные резы (после первой координации, до второй): http://www.artofproblemsolving.com/Foru ... 9&t=518200

отсортированные по фамилиям и суммам http://www.mediafire.com/download/xh92w ... 13res3.zip

отсортированные по университетам http://www.mediafire.com/download/lex04 ... 3res3_.zip

[mihailm]

(Оффтоп)

Поизучал результаты - на первом командном месте очевидно Физтех, на втором смотря как считать.
С абсолютным индивидуальным тоже вопросов нет - Владимир Брагин
Набираю значит в поисковике Брагин Владимир, мехмат
Получаю:

Цитата:

Подведены итоги олимпиады кафедры дискретной математики
Общий зачет
1 место Горинов Евгений 304
2 место Харитонов Михаил 203
3 место Беляков Сергей 102
Брагин Владимир 202

На международке то выступать проще!)))

[denisart]

mihailm в сообщении #753881 писал(а):

(Оффтоп)

Поизучал результаты - на первом командном месте очевидно Физтех, на втором смотря как считать.
С абсолютным индивидуальным тоже вопросов нет - Владимир Брагин
Набираю значит в поисковике Брагин Владимир, мехмат
Получаю:

Цитата:

Подведены итоги олимпиады кафедры дискретной математики
Общий зачет
1 место Горинов Евгений 304
2 место Харитонов Михаил 203
3 место Беляков Сергей 102
Брагин Владимир 202

На международке то выступать проще!)))

(Оффтоп)

Тут другие результаты.

[mihailm]

(Оффтоп)

denisart в сообщении #753884 писал(а):

Тут другие результаты.

Да, точно!
Но я не обманывал, вот моя ссылка http://www.math.msu.ru/news/?nid=9ca3c75c4687ad4dfbb2047d83aea2ec
Понял, там 2011 год

[Dave]

Задача 5 второго дня.

(xmaister)

Не знаю, за что её xmaister невзлюбил .

Пронумеруем все бусины по часовой стрелке, начиная с какой-то фиксированной, стартуя с номера 1.
Каждое ожерелье, в котором $n$ зелёных бусин, однозначно задаётся набором натуральных чисел $(x_0,x_1,\dots,x_n)$ с двумя дополнительными условиями: $x_0 \leqslant x_n$ и $x_1+x_2+\dots+x_n=2013$, где $x_0$ - номер первой зелёной бусины, а $x_i$, $i>0$ означает количество шагов, которые нужно пройти от $i$-й зелёной бусины до $i+1$-й (или до первой при $i=n$). Раскраска будет хорошей тогда и только тогда, когда все $x_i$ не превосходят $21$. Поэтому нам нужно узнать чётность общего количества таких наборов при всех натуральных $n$.
Пусть $G(t)$ - количество наборов (произвольной длины) натуральных чисел, не превосходящих $21$ и дающих в сумме $t$. При этом мы полагаем $G(0)=1$ и $G(t)=0$ при $t<0$. Перебирая все возможные значения $x_n$ в вышеприведённом описании хороших раскрасок, и замечая, что каждый вариант $x_n=C$ даёт $C$ вариантов выбора $x_0$, получаем, что количество хороших раскрасок равно $\sum\limits_{i=1}^{21} {i \, G(2013-i)}$, что, с точки зрения чётности, эквивалентно

$$G(2012)+G(2010)+\ldots+G(1992). \eqno(1)$$

Перебирая значения последнего числа в наборе в определении $G(t)$, получим, что при $t>0$:

$$G(t)=\sum_{i=1}^{21} {G(t-i)}.$$

Отсюда следует, что при $t>1$:

$$G(t)=G(t-1)+\sum_{i=2}^{21} {G(t-i)}=G(t-1)+\sum_{i=1}^{21} {G(t-(i+1))}-G(t-22)=$$

$$=G(t-1)+\sum_{i=1}^{21} {G((t-1)-i)}-G(t-22)=2G(t-1)-G(t-22).$$

Значит чётность $G(t)$ и $G(t-22)$ совпадает при любом $t>1$. Т.к. $G(0)=G(1)=1$, а $G(t)=0$ при $t<0$, то $G(t)$ при $t \geqslant 0$ нечётно тогда и только тогда, когда $t$ даёт остаток $0$ или $1$ при делении на $22$. $1992=90 \cdot 22 + 12$, поэтому в $(1)$ только $2002$ является таким $t$, откуда и следует нечётность суммы $(1)$.

[dm]

На сайте олимпиады появились задачи и результаты:
http://www.imc-math.org.uk/index.php?ye ... m=problems
http://www.imc-math.org.uk/index.php?ye ... em=results

[arqady]

Наш Йоав Крауз на последней IMO получил бронзу, а здесь - золото и четвёртое место по всем участникам!
Жаль, что в следующем году он уже не может поехать на IMO.

Может, кто знает, участвовал ли Тао в IMC? Теоретически ведь мог.

[dm]

Открытие:
http://youtu.be/Pm4l3QR0rYY

Закрытие:
http://youtu.be/MncylM6I1d4
http://youtu.be/jGWXzDH-PU0
http://youtu.be/pMrOvtHWQR0
http://youtu.be/WQjWfn81KE8

Некоторые фото:
http://vk.com/album5499034_178305129
https://www.facebook.com/dmitry.mitin/m ... 039&type=3

[arqady]

Дмитрий, спасибо огромное! Вы, просто, наше всё!

[Dave]

А что это вообще за "международная" олимпиада такая? Похоже, корейцы и американцы её тупо игнорируют. Да и китайцы там какие-то подозрительные участвовали. Явно не лучшие представители своей страны. Видно какие-то китайские туристы случайно проезжали мимо и решили порешать задачки.
То ли дело IMO.