Loading [MathJax]/jax/output/SVG/jax.js

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


Натурал d саны толық квадрат емес. Натурал n саны үшін s(n) арқылы d \,санының екілік жүйедегі жазылуында алдыңғы n цифрлардың арасында кездесетін бірліктер санын белгілейміз (мұнда екілік жүйедегі үтірге дейінгі цифрлар да есептелінеді). Барлық натурал nA үшін s(n)>2n2 болатындай натурал A санының табылатынын дәлелдеңіз. ( 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В приведенном выше представлении мы используем ровно (s(χ+)+12) степени двойки. Таким образом, из леммы получаем (s(χ+)+12)χ2Запишем N=χ+. Из вышеизложенного следует (s(N)+1)2>2N4χ2Из этого легко видно, что s(N)>2N2 для всех больших N.

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

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

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

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

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

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

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

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