20-я Международная Жаутыковская олимпиада по математике, 2024 год
Комментарий/решение:
Пусть S обозначает уникальный набор целых чисел такой, что ∑n∈S2n=√d
Пусть количество цифр √d до десятичной точки равно χ. В результате √d<2χ+1. Рассмотрим число v, полученное взятием первых χ+ℓ цифр числа √d, где ℓ≥χ. Обратите внимание, что v=⌊2ℓ√d⌋2ℓ=√d−{2ℓ√d}2ℓУ нас есть v2=d+{2ℓ√d}24ℓ−{2ℓ√d}√d2ℓ−1
В двоичном формате d не имеет цифр после десятичной точки. Второе слагаемое выше строго меньше 1/4ℓ, и, следовательно, в его двоичном виде первые цифры 2ℓ после десятичной точки равны нулю. Третий член меньше 12ℓ−χ−2, поэтому в его двоичном виде первые цифры ℓ−χ−2 равны нулю.
Так как 2ℓ≥ℓ−χ−2 и второе слагаемое меньше третьего, то v2 имеет как минимум ℓ−χ−2 бит после набора десятичной точки. к одному. Теперь мы будем использовать следующую лемму:
Лемма: Предположим, что m — рациональное число, имеющее конечное двоичное разложение. Далее, пусть S — мультимножество целых чисел такое, что ∑n∈S2n=mТогда |S|≥s2(m).
Доказательство: Это легко доказать. Хотя S состоит из двух одинаковых элементов, мы можем объединить их и уменьшить размер S на один. Поскольку окончательное множество S должно быть в точности двоичным разложением m, мы получаем, что |S|≥m, как заявлено.
Обратите внимание, что s2(v2)≥ℓ−χ−2. Более того, мы можем записать v2 как: ∑u∈S,u≥−ℓ22u+∑u>v≥−ℓ,u,v∈S2u+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.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.