China TST 2004

[СОКАКУ]

k \geq 2, 1 < n_1 < n_2 < \ldots < n_k и a,b-натуральные числа удовлетворяют условию
\prod^k_{i=1} \left( 1 - \frac{1}{n_i} \right) \leq \frac{a}{b} < \prod^{k-1}_{i=1} \left( 1 - \frac{1}{n_i} \right)
доказать неравенство \prod^k_{i=1} n_i \geq (4 \cdot a)^{2^k - 1}.

[ddn]

Интересно, а зачем здесь $b$?

[Руст]

Он наверное забыл сказать, что (a,b)=1 (a/b - несократимое представление рационального числа). Только всё равно утверждение в таком виде неверное. По видимому надо менять неравенство на противоположное, тогда о несократимости можно не волноваться.

[СОКАКУ]

Вообще то наличие пробелов в условии очевидно. Потому я в точности скопировал условие, что бы посмотреть как его можно покрутить. Видимо неравенство действительно выполняеться в другую сторону( иначе не обьяснить отсутствия условий на a,b)

[СОКАКУ]

Отличная новость: нашёл эту задачу в другом источнике,и предлагаю вам правильную формулировку
k \geq 2, 1 < n_1 < n_2 < \ldots < n_k и a,b-натуральные числа удовлетворяют условию
\prod^k_{i=1} \left( 1 - \frac{1}{n_i} \right) \leq \frac{a}{b} < \prod^{k-1}_{i=1} \left( 1 - \frac{1}{n_i} \right)
доказать неравенство \prod^k_{i=1} n_i \leq (4 \cdot a)^{2^k - 1}.

[ddn]

СОКАКУ писал(а):

Отличная новость: нашёл эту задачу в другом источнике,и предлагаю вам правильную формулировку
k \geq 2, 1 < n_1 < n_2 < \ldots < n_k и a,b-натуральные числа удовлетворяют условию
\prod^k_{i=1} \left( 1 - \frac{1}{n_i} \right) \leq \frac{a}{b} < \prod^{k-1}_{i=1} \left( 1 - \frac{1}{n_i} \right)
доказать неравенство \prod^k_{i=1} n_i \leq (4 \cdot a)^{2^k - 1}.

Для существования целых $a$, требуемых условием, необходимо и достаточно,
чтобы $\prod_{i=1}^{k-1}\left(1-\frac{1}{n_i}\right)-\prod_{i=1}^k\left(1-\frac{1}{n_i}\right)\geqslant\frac{1}{b}$,
или $\frac{1}{b}\leqslant\frac{1}{n_k}\prod_{i=1}^{k-1}\left(1-\frac{1}{n_i}\right)$, или $n_k\leqslant b\prod_{i=1}^{k-1}\left(1-\frac{1}{n_i}\right)$.
Очевидно, такие целые $a$ есть $0<b\prod_{i=1}^k\left(1-\frac{1}{n_i}\right)\leqslant a<b\prod_{i=1}^{k-1}\left(1-\frac{1}{n_i}\right)<b$, то есть они натуральные.

Тогда $\prod^k_{i=1}n_i \leqslant n_1\prod_{i=2}^{k}\left(b\prod_{j=1}^{i-1}\left(1-\frac{1}{n_j}\right)\right)\leqslant n_1\cdot b\left(1-\frac{1}{n_1}\right)a^{k-2}<$,
учитывая $n_1<n_2\leqslant b\left(1-\frac{1}{n_1}\right)$ продолжим
$<b^2\left(1-\frac{1}{n_1}\right)^2a^{k-2}\leqslant\frac{1}{\left(1-\frac{1}{n_2}\right)^2}a^k\leqslant$,
если $n_i$ - натуральные, то $2\leqslant n_1$ и $3\leqslant n_2$ и продолжим
$\leqslant\frac{9}{4}a^k<4^1\cdot a^k<(4\cdot a)^{2^k-1}$,
ибо $1<2^k-1$ и $k<2^k-1$ при $k\geqslant 2$.
То есть $\prod_{i=1}^kn_i<(4\cdot a)^{2^k-1}$.

[СОКАКУ]

ddn писал(а):

$\leqslant\frac{9}{4}a^k$,

Я так понимаю это ваша лучшая оценка, но если{n_i=i+1} и a=1,b=k+1. Тогда что (k+1)!\leqslant\frac{9}{4}

Добавлено спустя 9 минут 32 секунды:

ddn писал(а):

Тогда $\prod^k_{i=1}n_i \leqslant n_1\prod_{i=2}^{k}\left(b\prod_{j=1}^{i-1}\left(1-\frac{1}{n_j}\right)\right)\leqslant n_1\cdot b\left(1-\frac{1}{n_1}\right)a^{k-2}<$.

Совершенно не понятно почему a может ограничевать сверху {n_i}.( видно что именно так вы и поступали).Левое неравенство в условии ,совершенно очевидно, не верно для каждого i . Хотя конечно ошибки на этом не заканчиваются.

[ddn]

СОКАКУ писал(а):

ddn писал(а):

$\leqslant\frac{9}{4}a^k$

Я так понимаю это ваша лучшая оценка, но если $n_i=i+1$ и $a=1$, $b=k+1$. Тогда что $(k+1)!\leqslant\frac{9}{4}$

$\prod_{i=1}^k\left(1-\frac{1}{n_i}\right)=\prod_{i=1}^k\frac{i}{i+1}=\frac{1}{k+1}$,
$\prod_{i=1}^{k-1}\left(1-\frac{1}{n_i}\right)=\prod_{i=1}^k\frac{i}{i+1}=\frac{1}{k}$,
$\frac{a}{b}=\frac{1}{k+1}$
Хм...

СОКАКУ писал(а):

ddn писал(а):

Тогда $\prod^k_{i=1}n_i \leqslant n_1\prod_{i=2}^{k}\left(b\prod_{j=1}^{i-1}\left(1-\frac{1}{n_j}\right)\right)\leqslant n_1\cdot b\left(1-\frac{1}{n_1}\right)a^{k-2}<$.

Совершенно не понятно почему a может ограничивать сверху {n_i}.( видно что именно так вы и поступали).Левое неравенство в условии ,совершенно очевидно, не верно для каждого i. Хотя конечно ошибки на этом не заканчиваются.

Этот вывод опирался на:
$n_i\leqslant b\prod_{j=1}^{i-1}\left(1-\frac{1}{n_j}\right)\leqslant a$ при $i\geqslant 3$.
Теперь вижу, что в условии $\prod_{i=1}^k\left(1-\frac{1}{n_i}\right)\leqslant\frac{a}{b}$ неравенство стоит для фиксированного $k$, а не любого $k\geqslant 2$ (иначе условие противоречиво).
То есть $b\prod_{j=1}^{i-1}\left(1-\frac{1}{n_j}\right)\leqslant a$ применимо лишь для $i=k+1$.


Тогда идем первоначальным путем
$\prod^k_{i=1}n_i \leqslant n_1\prod_{i=2}^{k}\left(b\prod_{j=1}^{i-1}\left(1-\frac{1}{n_j}\right)\right)=n_1b^{k-1}\prod_{j=1}^{k-1}\left(1-\frac{1}{n_j}\right)^{k-j-1}\leqslant$
$\leqslant\left(1-\frac{1}{n_1}\right)b^k\left(1-\frac{1}{n_k}\right)\prod_{j=1}^{k}\left(1-\frac{1}{n_j}\right)^{k-j-1}\leqslant\left(1-\frac{1}{n_1}\right)a^k\left(1-\frac{1}{n_k}\right)\prod_{j=1}^{k}\left(1-\frac{1}{n_j}\right)^{-j-1}<$

где $\left(1-\frac{1}{n_j}\right)^{-j-1}=e^{-(j+1)\ln\left(1-\frac{1}{n_j}\right)}<e^{\frac{j+1}{n_j-1}}$, так как
$\frac{1}{n}=\frac{1}{n}\cdot\frac{1}{1}<-\ln(1-\frac{1}{n})=\int\limits_{1-\frac{1}{n}}^{1}\frac{dx}{x}<\frac{1}{n}\cdot\frac{1}{1-\frac{1}{n}}=\frac{1}{n-1}$ при $n>1$

$<a^k\left(1-\frac{1}{n_1}\right)\left(1-\frac{1}{n_k}\right)e^{\sum\limits_{j=1}^{k}\frac{j+1}{n_j-1}}\leqslant a^ke^{k+\sum\limits_{j=1}^{k}\frac{1}{j}}<ka^ke^{k+1}=$
$=(e\cdot\sqrt[k]{ek}\cdot a)^k\leqslant(e\cdot e\cdot a)^k<(4^{\frac{1}{\ln(2)}}\cdot a)^k<(4\cdot a)^{2^k-1}$

учли еще, что $n_j\geqslant j+1$, $\sum\limits_{j=1}^{k}\frac{1}{j}<1+\ln(k)$, $\sqrt[k]{ek}\leqslant\sqrt[1]{e}=e$ и $\frac{k}{\ln(2)}<2^k-1$


Еще моя ошибка в том, что условие
$\prod_{i=1}^{k-1}\left(1-\frac{1}{n_i}\right)-\prod_{i=1}^k\left(1-\frac{1}{n_i}\right)\geqslant\frac{1}{b}$,
в действительности лишь достаточно (но не необходимо) для существования $a$, требуемых условием.
Оно лишь гарантирует их наличие, но требуемые $a$ могут существать (и существуют, как показал Ваш пример) и при $\prod_{i=1}^{k-1}\left(1-\frac{1}{n_i}\right)-\prod_{i=1}^k\left(1-\frac{1}{n_i}\right)<\frac{1}{b}$
(в вашем примере $...-...=\frac{1}{k(k+1)}<\frac{1}{k+1}=\frac{1}{b}$).

Неравенство $\prod^k_{i=1} n_i \leq (4 \cdot a)^{2^k - 1}$, таким образом, доказано для более узкой области значений $(a,b)$, чем требуется.
Если данное неравенство и верно при $\prod_{i=1}^{k-1}\left(1-\frac{1}{n_i}\right)-\prod_{i=1}^k\left(1-\frac{1}{n_i}\right)<\frac{1}{b}$,
то его доказательство существенно усложняется дискретностью значений $a$.
Думаю, без глубоких теорем теории чисел здесь ничего не доказать.

[Руст]

Мне кажется надо доказать $n_i\le (4a)^{2^{i-1}}$ по индукции. Вроде можно получить более точные оценки.