Задача от Hewlett-Packard

18 Июль 2012, 0:04

Эта задача была найдена на пачке бумаги HP copy-paper. Задача довольно интересная. Смотрите сами.

Пусть функция $f$ , отображающая множество натуральных чисел в множество натуральных чисел, удовлетворяет условиям:

1. $f(1)=1$ ,
2. $f(2n)=f(n)$ ,
3. $f(2n+1)=f(2n)+1$

для любого натурального $n$ .

Найдите эту функцию.

В действительности на пачке бумаги была несколько другая задача. Приведу ее здесь тоже.

Требуется найти максимальное значение $f(n)$ при $1\le n\le 1994$ .

Отсюда для желающих возникают вопросы:

1. Каков ответ в этой задаче?
2. Откуда возникло ограничение $1994$ ?
3. Почему HP напечатала эту задачу на упаковке своей бумаги?

Я вам честно признаюсь: я не знаю ответа на второй и третий вопросы. Поэтому большая просьба к тем, у кого есть какая-нибудь информация по этому поводу, ее сообщить. Буду очень признательна.

Показать решение

Перепишем третье условие несколько иначе:

$f(2n+1)=f(2n)+1=f(n)+1 .$

И теперь мы видим, что исходное число удобно представить в двоичной системе счисления. Пусть

$n=\overline{a_0a_1a_2\ldots a_k}_2.$

Тогда имеем

$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=$

$=f(\overline{a_0a_1a_2\ldots a_{n-1}}_2)+a_n=\ldots=a_0+a_1+\ldots+a_n.$

Таким образом, значение $f(n)$ равно сумме цифр в двоичной записи числа $n$ .

И теперь легко назвать максимальной значение

*** 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:
Unknown error

. Для этого переведем $1994$ в двоичную систему счисления:

$1994=\overline{11111001010}_2.$

И очевидно, что число, в двоичной записи которого максимальное количество единиц, не превосходящее $1994$ запишется следующим образом: $\overline{10111111111}_2=\overline{1535}_{10}$ . И максимальное значение функции $f$ при данных ограничениях равно $10$ .

Источник: http://mathnexus.wwu.edu/archive/problem/detail.asp?ID=247

Теги: задача, математика
Рубрика: Разные задачи | Отзывы (RSS) | Трекбек

Комментариев: 4

1 Корнеев В.Ф.:

Вы все свои статьи пишете после 12 ночи по московскому времени?

[Ответить]
18 Июль 2012, 2:25
2 disputant:

1994, уверен, год публикации задачи где-то. Откуда ее уже передирали, не задумываясь…

Задачу я где-то недавно видел, насколько мне помнится, где-то в каких-то не то олимпиадных задачах по программированию, не то в чем-то очень похожем…

Забавно, что на первый взгляд (не сейчас, тогда, когда видел на каком-то сайте) мне показалось, что это решение задачи Иосифа – там соотношения похожи, но не те:

$f(2n)=2f(n)-1$ , $f(2n+1)=2f(n)+1$ …

[Ответить]
18 Июль 2012, 10:01
3 disputant:

P.S. Не напомните, как в комментариях правильно формулы вставлять?…

[Ответить]
18 Июль 2012, 10:02
4 Елизавета Александровна Калинина:

1: Статьи пишу в разное время, причем вовсе не факт, что в тот день, когда они выложены Просто как-то по сложившейся изначально традиции продолжаю выкладывать их в одно время

Да, мой комментарий опять не добавился Вам на сайт

2: Да, возможно. Но вообще странно, что в HP не задумались, а просто передрали… Мне казалось, что этот год как-то должен быть связан с самой компанией. Однако нигде ничего об этом не нашла…

3: Вот тут краткое пособие по вставке формул: http://hijos.ru/nabor-formul-v-latex/

[Ответить]
18 Июль 2012, 11:59

Математика, которая мне нравится

Задача от Hewlett-Packard

Комментариев: 4

1 Корнеев В.Ф.:

2 disputant:

3 disputant:

4 Елизавета Александровна Калинина:

Оставьте свой отзыв

Навигация по сайту

Разделы

Новые комментарии

Хороший книжный магазин

Подписка на обновления сайта

Твиттер