Loading [MathJax]/extensions/TeX/mathchoice.js

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


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

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

  0
1 года 2 месяца назад #

Пусть S обозначает уникальный набор целых чисел такой, что nS2n=d

Пусть количество цифр d до десятичной точки равно χ. В результате d<2χ+1. Рассмотрим число v, полученное взятием первых χ+ цифр числа d, где χ. Обратите внимание, что v=2d2=d{2d}2У нас есть v2=d+{2d}24{2d}d21

В двоичном формате d не имеет цифр после десятичной точки. Второе слагаемое выше строго меньше 1/4, и, следовательно, в его двоичном виде первые цифры 2 после десятичной точки равны нулю. Третий член меньше 12χ2, поэтому в его двоичном виде первые цифры χ2 равны нулю.

Так как 2χ2 и второе слагаемое меньше третьего, то v2 имеет как минимум χ2 бит после набора десятичной точки. к одному. Теперь мы будем использовать следующую лемму:

Лемма: Предположим, что m — рациональное число, имеющее конечное двоичное разложение. Далее, пусть S — мультимножество целых чисел такое, что nS2n=mТогда |S|s2(m).

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

Обратите внимание, что s2(v2)χ2. Более того, мы можем записать v2 как: uS,u22u+u>v,u,vS2u+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.

  0
1 года 2 месяца назад #

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

  0
1 года 2 месяца назад #

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

  0
1 года 2 месяца назад #

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

  0
1 года 2 месяца назад #

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