20-я Международная Жаутыковская олимпиада по математике, 2024 год

Натуральное число $d$ не является точным квадратом. Для каждого натурального числа $n$ обозначим через $s(n)$ количество единиц среди первых $n$ цифр двоичной записи числа $\sqrt d$ (цифры до запятой тоже учитываются). Докажите, что существует такое натуральное $A$, что при всех натуральных $n\geqslant A$ выполнено неравенство $s(n)>\sqrt{2n}-2$. ( Navid Safaei )

Комментарий/решение

Пусть $S$ обозначает уникальный набор целых чисел такой, что $$\sum \limits_{n \in S} 2^n = \sqrt{d}$$

Пусть количество цифр $\sqrt{d}$ до десятичной точки равно $\chi$. В результате $\sqrt{d} < 2^{\chi+1}$. Рассмотрим число $v$, полученное взятием первых $\chi+\ell$ цифр числа $\sqrt{d}$, где $\ell \geq \chi$. Обратите внимание, что $$v = \frac{ \lfloor 2^{\ell} \sqrt{d} \rfloor}{2^{\ell}} = \sqrt{d} - \frac{ \{ 2^{\ell } \sqrt{d} \} }{2^{\ell}}$$ У нас есть $$v^2 = d + \frac{\{2^{\ell} \sqrt{d}\}^2} {4^{\ell}} - \frac{\{2^{\ell} \sqrt{d}\} \sqrt{d} }{2^{\ell-1}}$$

В двоичном формате $d$ не имеет цифр после десятичной точки. Второе слагаемое выше строго меньше $1/4^{\ell}$, и, следовательно, в его двоичном виде первые цифры $2\ell$ после десятичной точки равны нулю. Третий член меньше $\frac{1}{2^{\ell-\chi-2}}$, поэтому в его двоичном виде первые цифры $\ell-\chi-2$ равны нулю.

Так как $2\ell \geq \ell-\chi-2$ и второе слагаемое меньше третьего, то $v^2$ имеет как минимум $\ell-\chi-2$ бит после набора десятичной точки. к одному. Теперь мы будем использовать следующую лемму:

Лемма: Предположим, что $m$ — рациональное число, имеющее конечное двоичное разложение. Далее, пусть $S$ — мультимножество целых чисел такое, что $$\sum \limits_{n \in S} 2^n = m$$ Тогда $|S| \geq s_2(m)$.

Доказательство: Это легко доказать. Хотя $S$ состоит из двух одинаковых элементов, мы можем объединить их и уменьшить размер $S$ на один. Поскольку окончательное множество $S$ должно быть в точности двоичным разложением $m$, мы получаем, что $|S| \geq m$, как заявлено.

Обратите внимание, что $s_2(v^2) \geq \ell-\chi-2$. Более того, мы можем записать $v^2$ как: $$\sum \limits_{u \in S, u \geq -\ell} 2^{2u} + \sum \limits_{u > v \geq -\ell , u, v \in S} 2^{u+v+1}$$ В приведенном выше представлении мы используем ровно $\binom{s(\chi+\ell) + 1}{2}$ степени двойки. Таким образом, из леммы получаем $$\binom{s(\chi+\ell) + 1}{2} \geq \ell-\chi-2$$ Запишем $N = \chi + \ell$. Из вышеизложенного следует $$(s(N)+1)^2 > 2N-4\chi-2$$ Из этого легко видно, что $s(N) > \sqrt{2N} - 2$ для всех больших $N$.

Здравствуйте вы можете объяснить 2 часть решения ?не понял что вы делаете

Можете переформулировать где именно вы не поняли

Там где вы доказываете что S>= s2

Чел типо понял решение