Покажите что $%2N+\lfloor \log_2(N-1) \rfloor < n \le 2N+2+\lfloor \log_2(N) \rfloor \Rightarrow N=2^{k-1}+\lfloor \frac{n-2^k-k}{2}\rfloor$% где $%2^k+k \le n \le 2^{k+1}+k$% . При натуральных $%N,n,k$%

задан 25 Апр '17 18:56

10|600 символов нужно символов осталось
1

По условию, $%N\ge2$%, откуда далее $%n\ge5$% и $%k\ge2$%. Для начала рассмотрим случай, когда $%N=2^m$% является степенью двойки. В этом случае $%2^{m+1}+m\le n\le2^{m+1}+m+2$%, то есть число $%n$% может три значения. Если $%n=2^{m+1}+m$%, то $%k=m$%. Тогда $%n-2^k-k=2^m$%, и равенство $%N=2^{m-1}+2^{m-1}=2^m$% верно. Если $%n=2^{m+1}+m+1$%, то $%k=m+1$%, и $%n-2^k-k=0$%. При $%n=2^{m+1}+m+2$% снова $%k=m+1$%, и далее $%n-2^k-k=1$%. В обоих этих случаях формула для $%N$% даёт верный результат $%2^m$%.

Теперь пусть $%N$% степенью двойки не является, и $%2^m < N < 2^{m+1}$%. Здесь обе целых части логарифма равны $%m$%. Имеем неравенство $%2N+m+1\le n\le2N+m+2$%; для $%n$% возможно два значения. Поскольку $%2^{m+1}+m+1 < n < 2^{m+2}+m+2$%, в обоих случаях имеем $%k=m+1$%. Получается, что $%n-2^k-k$% равно $%2(N-2^m)+r$%, где $%r=0,1$%. Целая часть половины этой величины равна $%N-2^m$%, и в сумме с $%2^{k-1}=2^m$% это даёт $%N$%, что и требовалось проверить.

Условие оставляет ощущение некоторой искусственности, хотя я допускаю, что оно могло возникнуть в процессе решения какой-то отдельной задачи.

ссылка

отвечен 26 Апр '17 1:06

Да вы правы, там отдельная красивая задача http://dxdy.ru/topic6037.html Первое двойное неравенство это фактически неявная формула дающая общий ответ на ту задачу. Второе двойное неравенство и уравнение аналогично являются "неявной формулой" ответа

Собственно вторая "формула" выглядит попроще первой и у ребят с форума она возникла как-то сама собой, чуть ли не устно. А вот нам пришлось изрядно потрудиться чтобы формально все это доказать(а ведь сначала еще надо додуматься что есть простая формула). Вот я интересуюсь есть ли какой-то естественный способ связать вторую формулу с той задачей

(26 Апр '17 1:53) abc

На самом деле есть формула еще проще: $%2N+\lfloor \log_2(N-1) \rfloor < n \le 2N+2+\lfloor \log_2(N) \rfloor \Leftrightarrow N=\lfloor \frac{n-k}{2}\rfloor$% Но она из той же серии. Вот можно до такого додуматься взглянув на эти логарифмы?

(26 Апр '17 2:01) abc
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×29

задан
25 Апр '17 18:56

показан
307 раз

обновлен
26 Апр '17 2:04

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru