2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: IMC 2013
Сообщение09.08.2013, 15:50 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна
По 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$

 Профиль  
                  
 
 Re: IMC 2013
Сообщение10.08.2013, 00:04 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна
День 2:

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

 Профиль  
                  
 
 Re: IMC 2013
Сообщение10.08.2013, 15:30 
Аватара пользователя


12/01/11
1320
Москва
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.$
Дальше что-то не получается :?

 Профиль  
                  
 
 Re: IMC 2013
Сообщение10.08.2013, 16:37 
Заслуженный участник


08/04/08
8556
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$ :roll: (например, $S(2p,2q)=2S(p,q)$) А еще это напоминает одно из доказательств квадратичного закона взаимности, хотя, видимо, связи нет.

 Профиль  
                  
 
 Re: IMC 2013
Сообщение10.08.2013, 21:46 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: IMC 2013
Сообщение11.08.2013, 13:44 
Экс-админ
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: IMC 2013
Сообщение11.08.2013, 15:37 


19/05/10

3940
Россия

(Оффтоп)

Поизучал результаты - на первом командном месте очевидно Физтех, на втором смотря как считать.
С абсолютным индивидуальным тоже вопросов нет - Владимир Брагин
Набираю значит в поисковике Брагин Владимир, мехмат
Получаю:
Цитата:
Подведены итоги олимпиады кафедры дискретной математики
Общий зачет
1 место Горинов Евгений 304
2 место Харитонов Михаил 203
3 место Беляков Сергей 102
Брагин Владимир 202

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

 Профиль  
                  
 
 Re: IMC 2013
Сообщение11.08.2013, 15:57 
Аватара пользователя


09/12/12
67
Санкт-Петербург
mihailm в сообщении #753881 писал(а):

(Оффтоп)

Поизучал результаты - на первом командном месте очевидно Физтех, на втором смотря как считать.
С абсолютным индивидуальным тоже вопросов нет - Владимир Брагин
Набираю значит в поисковике Брагин Владимир, мехмат
Получаю:
Цитата:
Подведены итоги олимпиады кафедры дискретной математики
Общий зачет
1 место Горинов Евгений 304
2 место Харитонов Михаил 203
3 место Беляков Сергей 102
Брагин Владимир 202

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

(Оффтоп)

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

 Профиль  
                  
 
 Re: IMC 2013
Сообщение11.08.2013, 18:39 


19/05/10

3940
Россия

(Оффтоп)

denisart в сообщении #753884 писал(а):
Тут другие результаты.

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

 Профиль  
                  
 
 Re: IMC 2013
Сообщение13.08.2013, 02:08 
Заслуженный участник
Аватара пользователя


03/12/11
640
Україна
Задача 5 второго дня.

(xmaister)

Не знаю, за что её xmaister невзлюбил :roll: .
Пронумеруем все бусины по часовой стрелке, начиная с какой-то фиксированной, стартуя с номера 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)$.

 Профиль  
                  
 
 Re: IMC 2013
Сообщение13.08.2013, 17:53 
Экс-админ
Аватара пользователя


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

 Профиль  
                  
 
 Re: IMC 2013
Сообщение15.08.2013, 07:47 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: IMC 2013
Сообщение15.08.2013, 08:01 
Экс-админ
Аватара пользователя


23/05/05
2106
Kyiv, Ukraine
Открытие:
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

 Профиль  
                  
 
 Re: IMC 2013
Сообщение15.08.2013, 12:21 
Заслуженный участник


26/06/07
1929
Tel-aviv
Дмитрий, спасибо огромное! Вы, просто, наше всё! :D

 Профиль  
                  
 
 Re: IMC 2013
Сообщение15.08.2013, 17:24 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 39 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group