20-я Международная Жаутыковская олимпиада по математике, 2024 год
Комментарий/решение:
Пусть $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$.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.