VJIMC 2013

[xmaister]

Привет! Выкладываю задачи второй категории VJIMC 2013. Первой выложу чуть позже. Итак, задачи:

1. Пусть $S_n$- сумма первых $n$ простых чисел. Докажите, что между $S_n$ и $S_{n+1}$ лежит квадрат целого числа.

2. Дан $n$- мерный куб. Любые две вершины соединены отрезком. Найдите число различных точек пересечения этих отрезков, исключая сами вершины.

3. Докажите, что не существует многолчнеа с целыми коэфициентами, такого что $P(\sqrt[3]{5}+\sqrt[3]{25})=\sqrt[3]{5}+5$.

4. Пусть $\mathcal{F}$- семейство функций непрерывных функций $f:[0,1]\to\mathbb{R}$, обладающих следующим свойством:

$$\left|\int\limits_{0}^{x}\frac{f(t)}{\sqrt{x-t}}dt\right|\le 1$$

. Вычислить $\sup\limits_{f\in\mathcal{F}}\left|\int\limits_{0}^{1}f(x)dx\right|$

-- 12.04.2013, 16:11 --

Первая категория:

1. Функция $f:[0,\infty)\to\mathbb{R}$ дифференцируема, ограничена и $f\cdot f'\ge\cos x$. Докажите, что не существует $\lim\limits_{x\to\infty}f(x)$ не существует.

2. Даны две матрицы $A$ и $B$ размера $10\times 10$, где $a_{ij}=b_{ij}+1$. $A^3=0$, докажите, что $\mathrm{det}(B)=0$.

3. Дано конечное множество $S$ целых чисел. Докажите, что существует число $c$ для каждого такого $S$, такое что количество $k$ для которых $f(k)\in S$, где $f$- полином с целыми коэффициентами, не являющийся константой не превосходит $\max\deg f$ или $c$.

4. Вычислить сумму:

$$\sum\limits_{0\le j\le k} {k \choose j}^2\cdot {n+2k-j\choose 2k}$$

[nnosipov]

1. Из неравенств $k^2 \leqslant S_n<S_{n+1} \leqslant (k+1)^2$ следует, что $n\ln{n} \sim p_{n+1}=S_{n+1}-S_n \leqslant 2k+1$ и $k \leqslant \sqrt{S_n} \sim n\sqrt{\ln{n}}$. При больших $n$ эти неравенства противоречат друг другу.

3. Пусть $\theta=\sqrt[3]{5}$, $\varepsilon$ --- кубический корень из единицы. Кроме равенства $P(\theta+\theta^2)=\theta+5$, имеем равенство $P(\varepsilon\theta+\varepsilon^2\theta^2)=\varepsilon\theta+5$. Вычитая и затем деля, получим, что дробь

$$ \frac{(\theta+5)-(\varepsilon\theta+5)}{(\theta+\theta^2)-(\varepsilon\theta+\varepsilon^2\theta^2)}=\frac{1}{1-\varepsilon^2\theta} $$

должна быть целым алгебраическим числом. Но это не так, поскольку

$$ \frac{1}{(1-\varepsilon^2\theta)(1-\varepsilon\theta)(1-\theta)}=-\frac{1}{4}. $$

[TOTAL]

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

2. Даны две матрицы $A$ и $B$ размера $10\times 10$, где $a_{ij}=b_{ij}+1$. $A^3=0$, докажите, что $\mathrm{det}(B)=0$.

$B^3$ равна сумме семи матриц, ранг каждой из которых не больше 1.

[Shadow]

(Оффтоп)

В первой для удобства все нечетные числа считать простыми

[sup]

4. Искомый супремум равен $2/\pi$. Достигается на последовательности гладких приближений к функции $\frac {1}{\pi \sqrt t}$. Для доказательства, что это действительно супремум, достаточно умножить неравенство на $\frac {1}{\pi \sqrt {1 -x}}$ и проинтегрировать от 0 до 1. Поменяв порядок интегрирования, получим нужное неравенство.

[Sonic86]

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

2. Дан $n$- мерный куб. Любые две вершины соединены отрезком. Найдите число различных точек пересечения этих отрезков, исключая сами вершины.

$\sum\limits_{k=2}^n2^{n-k}C_n^k=3^n-2^{n-1}(n+2)$

[xmaister]

nnosipov в сообщении #709055 писал(а):

1. Из неравенств $k^2 \leqslant S_n<S_{n+1} \leqslant (k+1)^2$ следует, что $n\ln{n} \sim p_{n+1}=S_{n+1}-S_n \leqslant 2k+1$ и $k \leqslant \sqrt{S_n} \sim n\sqrt{\ln{n}}$. При больших $n$ эти неравенства противоречат друг другу.

Мы сперва доказали, что $S_n\le\frac{p_{n+1}^2}{4}$, это не слежно. Действительно, для всех $i\in\mathbb{N}$ имеем $p_{i+1}^2-p_i^2=(p_{i+1}-p_i)(p_{i+1}+p_i)>4p_i$. Теперь по индукции $S_n\le \frac{p_{n+1}^2}{4}$. Затем по индукции: пусть $l^2<S_n$- максимальное, тогда $2l+1= 2\sqrt{S_n}+1<2\sqrt{\frac{p_{n+1}^2}{4}}=p_{n+1}+1$. Индукционный переход.

-- 12.04.2013, 19:25 --

nnosipov в сообщении #709055 писал(а):

3. Пусть $\theta=\sqrt[3]{5}$, $\varepsilon$ --- кубический корень из единицы. Кроме равенства $P(\theta+\theta^2)=\theta+5$, имеем равенство $P(\varepsilon\theta+\varepsilon^2\theta^2)=\varepsilon\theta+5$. Вычитая и затем деля, получим, что дробь

$$ \frac{(\theta+5)-(\varepsilon\theta+5)}{(\theta+\theta^2)-(\varepsilon\theta+\varepsilon^2\theta^2)}=\frac{1}{1-\varepsilon^2\theta} $$

должна быть целым алгебраическим числом. Но это не так, поскольку

$$ \frac{1}{(1-\varepsilon^2\theta)(1-\varepsilon\theta)(1-\theta)}=-\frac{1}{4}. $$

А если поэксплуатировать изоморызм $\mathbb{Z}[x]/(x^3-5)\cong \mathbb{Z}[\sqrt[3]{5},\sqrt[3]{25}]$

[xmaister]

sup в сообщении #709102 писал(а):

4. Искомый супремум равен $2/\pi$. Достигается на последовательности гладких приближений к функции $\frac {1}{\pi \sqrt t}$.

Я, на самом деле не понял откуда это следует?

-- 12.04.2013, 20:19 --

Sonic86 в сообщении #709111 писал(а):

$\sum\limits_{k=2}^n2^{n-k}C_n^k=3^n-2^{n-1}(n+2)$

Почему?

[nnosipov]

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

А если поэксплуатировать изоморызм $\mathbb{Z}[x]/(x^3-5)\cong \mathbb{Z}[\sqrt[3]{5},\sqrt[3]{25}]$

А как именно поэксплуатировать?

[BatMan]

Ну скажем, ясно что размрность $\mathbb{Z}[x]/(x^3-5)$ как $\mathbb{Z}$-модуля равна 3. А что насчет первой задачи?

[nnosipov]

BatMan в сообщении #709157 писал(а):

Ну скажем, ясно что размрность $\mathbb{Z}[x]/(x^3-5)$ как $\mathbb{Z}$-модуля равна 3.

Ну, равна. И что дальше?

[BatMan]

Так изоморфизм какбы напрашивается $x^i\mapsto \sqrt[3]{5^i}$... Это доставляет линейую независимость понятно чего.

-- 12.04.2013, 21:04 --

Мне хочется узнать что Вы дуамаете о моих рассуждаениях в перйо задаче... Это единственное в чем я более-менее уверен.

[nnosipov]

BatMan, Вы подробно своё решение напишите. Моё решение Вам понятно? (Я про задачу, где $\sqrt[3]{5}$.)

-- Сб апр 13, 2013 00:08:53 --

BatMan в сообщении #709179 писал(а):

Мне хочется узнать что Вы дуамаете о моих рассуждаениях в перйо задаче... Это единственное в чем я более-менее уверен.

А где Вы об этом писали?

[BatMan]

nnosipov в сообщении #709181 писал(а):

BatMan, Вы подробно своё решение напишите.

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

Мы сперва доказали, что $S_n\le\frac{p_{n+1}^2}{4}$, это не слежно. Действительно, для всех $i\in\mathbb{N}$ имеем $p_{i+1}^2-p_i^2=(p_{i+1}-p_i)(p_{i+1}+p_i)>4p_i$. Теперь по индукции $S_n\le \frac{p_{n+1}^2}{4}$. Затем по индукции: пусть $l^2<S_n$- максимальное, тогда $2l+1= 2\sqrt{S_n}+1<2\sqrt{\frac{p_{n+1}^2}{4}}=p_{n+1}+1$. Индукционный переход.

Ваше решение опирается на фатк, как я понял, коорый следует из теоремы Чебышева $(n\ln n\sim p_n)$? Если его считать изветсным, то все хоккей.

-- 12.04.2013, 21:10 --

nnosipov в сообщении #709181 писал(а):

А где Вы об этом писали?

Выше, рассуждения одинаковые у нас.

[nnosipov]

BatMan в сообщении #709179 писал(а):

Это доставляет линейую независимость понятно чего.

Ничего не понятно. Если, кстати, считать многочлен $P$ имеющим рациональные коэффициенты, то такой существует.