Эта задача была найдена на пачке бумаги HP copy-paper. Задача довольно интересная. Смотрите сами.
Пусть функция 
, отображающая множество натуральных чисел в множество натуральных чисел, удовлетворяет условиям:
1. 
,
2. 
,
3. 
для любого натурального 
.
Найдите эту функцию.
В действительности на пачке бумаги была несколько другая задача. Приведу ее здесь тоже.
Требуется найти максимальное значение 
при 
.
Отсюда для желающих возникают вопросы:
1. Каков ответ в этой задаче?
2. Откуда возникло ограничение 
?
3. Почему HP напечатала эту задачу на упаковке своей бумаги?
Я вам честно признаюсь: я не знаю ответа на второй и третий вопросы. Поэтому большая просьба к тем, у кого есть какая-нибудь информация по этому поводу, ее сообщить. Буду очень признательна.
Показать решение
Перепишем третье условие несколько иначе:
![\[f(2n+1)=f(2n)+1=f(n)+1 .\]](http://hijos.ru/wp-content/ql-cache/quicklatex.com-bb4261b3cf89e9f4b72a444e16983665_l3.png "Rendered by QuickLaTeX.com")
И теперь мы видим, что исходное число удобно представить в двоичной системе счисления. Пусть
![\[n=\overline{a_0a_1a_2\ldots a_k}_2.\]](http://hijos.ru/wp-content/ql-cache/quicklatex.com-719091b32c6e9b1988255623166fc8ee_l3.png "Rendered by QuickLaTeX.com")
Тогда имеем
![\[f(n)=f(\overline{a_0a_1a_2\ldots a_k}_2)=f(\overline{a_0a_1a_2\ldots a_{n-1}0}_2)+a_n=\]](http://hijos.ru/wp-content/ql-cache/quicklatex.com-4ecdb39686c546dde74c961a72085b49_l3.png "Rendered by QuickLaTeX.com")
![\[=f(\overline{a_0a_1a_2\ldots a_{n-1}}_2)+a_n=\ldots=a_0+a_1+\ldots+a_n.\]](http://hijos.ru/wp-content/ql-cache/quicklatex.com-d93870a2de1a0312865e745cde74e387_l3.png "Rendered by QuickLaTeX.com")
Таким образом, значение равно сумме цифр в двоичной записи числа .
И теперь легко назвать максимальной значение
*** QuickLaTeX cannot compile formula:
f(n)<span class="ql-right-eqno"> </span><span class="ql-left-eqno"> </span><img src="http://hijos.ru/wp-content/ql-cache/quicklatex.com-4a0d84315da46f1497d5bfd3232b02ac_l3.png" height="1" width="1" class="ql-img-displayed-equation quicklatex-auto-format" alt="\[при\]" title="Rendered by QuickLaTeX.com"/>1\le n\le 1994
*** Error message:
Cannot connect to QuickLaTeX server: Operation timed out after 39807 milliseconds with 0 bytes received
Please make sure your server/PHP settings allow HTTP requests to external resources ("allow_url_fopen", etc.)
These links might help in finding solution:
http://wordpress.org/extend/plugins/core-control/
http://wordpress.org/support/topic/an-unexpected-http-error-occurred-during-the-api-request-on-wordpress-3?replies=37
. Для этого переведем в двоичную систему счисления:
![\[1994=\overline{11111001010}_2.\]](http://hijos.ru/wp-content/ql-cache/quicklatex.com-9b29d19c7509b12afb940c7505b03631_l3.png "Rendered by QuickLaTeX.com")
И очевидно, что число, в двоичной записи которого максимальное количество единиц, не превосходящее запишется следующим образом: 
. И максимальное значение функции при данных ограничениях равно 
.
Источник: http://mathnexus.wwu.edu/archive/problem/detail.asp?ID=247
1 Корнеев В.Ф.:
Вы все свои статьи пишете после 12 ночи по московскому времени?
[Ответить]
18 Июль 2012, 2:252 disputant:
1994, уверен, год публикации задачи где-то. Откуда ее уже передирали, не задумываясь…
Задачу я где-то недавно видел, насколько мне помнится, где-то в каких-то не то олимпиадных задачах по программированию, не то в чем-то очень похожем…
Забавно, что на первый взгляд (не сейчас, тогда, когда видел на каком-то сайте) мне показалось, что это решение задачи Иосифа – там соотношения похожи, но не те:
[Ответить]
18 Июль 2012, 10:013 disputant:
P.S. Не напомните, как в комментариях правильно формулы вставлять?…
[Ответить]
18 Июль 2012, 10:024 Елизавета Александровна Калинина:
1: Статьи пишу в разное время, причем вовсе не факт, что в тот день, когда они выложены
Просто как-то по сложившейся изначально традиции продолжаю выкладывать их в одно время 
Да, мой комментарий опять не добавился Вам на сайт
2: Да, возможно. Но вообще странно, что в HP не задумались, а просто передрали… Мне казалось, что этот год как-то должен быть связан с самой компанией. Однако нигде ничего об этом не нашла…
3: Вот тут краткое пособие по вставке формул: http://hijos.ru/nabor-formul-v-latex/
[Ответить]
18 Июль 2012, 11:59