ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 73715
Темы:    [ Теория игр (прочее) ]
[ Двоичная система счисления ]
[ Логарифмические неравенства ]
[ Предел последовательности, сходимость ]
Сложность: 8+
Классы: 10,11
В корзину
Прислать комментарий

Условие

Двое играют в такую игру. Один задумывает натуральное число n, а другой задаёт вопросы типа «верно ли, что n не меньше x» (число x он может выбирать по своему усмотрению) и получает ответы «да» или «нет». Каждой возможной стратегии T второго игрока сопоставим функцию fT(n), равную числу вопросов (до отгадывания), если было задумано число n. Пусть, например, стратегия T состоит в том, что сначала задают вопросы: «верно ли, что n не меньше 10?», «верно ли, что n не меньше 20?», ... до тех пор, пока на какой-то вопрос «верно ли, что n не меньше 10(k + 1)» не будет дан ответ «нет», а затем задают вопросы «верно ли, что n не меньше 10k + 1», «верно ли, что n не меньше 10k + 2» и так далее. Тогда fT(n) = a + 2 + (na)/10, где a последняя цифра числа n, то есть fT(n) растёт примерно как n/10.

а) Предложите стратегию, для которой функция fT растёт медленнее.

б) Сравнивая две стратегии, удобно для произвольной стратегии Т вместо функции fT ввести функцию fT, значение которой для любого натурального числа n равно наибольшему из чисел fT(k), где k пробегает значения от 1 до n. Оцените снизу fT для произвольной стратегии T.

Решение

Пусть сначала n – не любое натуральное число, а заключено в промежутке

1 n N,

где N – заданное число. Тогда задача о минимизации максимального числа вопросов для отгадывания n известна.

Наилучшая в этом смысле стратегия, назовем ее Sn , состоит в том, что каждый новый вопрос делит промежуток значений, которые еще может принимать неизвестное пока число n , на две равные (или отличающиеся на 1 ) части. Именно, если мы уже знаем, что

a n < b,

то надо задать вопрос: "верно ли, что n "? Стратегия Sn описана.

Можно доказать, что максимальное число вопросов для отгадывания числа n N при использовании Sn равно ]log _2 N[ , где ]l[ означает наименьшее целое число, не меньшее l .

Ответим теперь на вопрос (б). Докажем, что для любой стратегии T и любого числа n

f'T(n) ]log _2 N[.


Доказательство. Пусть задано натуральное N , и неизвестное число n находится в промежутке от 1 до N . Пусть

2m-1<N 2m.

Тогда наибольший промежуток P1 значений, которые еще может принимать n после первого вопроса, строго больше 2m-2 (Разумеется, мы считаем, что "Злой Рок" (см."Квант" #8, 1972 г., с.4) помнит про свои обязанности.) , наибольший промежуток P2 , в котором может находиться n после второго вопроса, больше 2m-3 , и так далее. По индукции получаем, что наибольший промежуток Pm-1 , в котором может находиться n после m-1 -го вопроса, больше 1 . Значит, максимальное число вопросов (при наиболее неблагоприятных ответах) не меньше, чем

Займемся вопросом (а)задачи M180. Пусть мы задали несколько вопросов типа "верно ли, что n x " и получали ответы "да": число n все время оказывалось больше или равно очередному x . Ясно, что следующее x надо взять больше всех уже употребленных (иначе этот вопрос будет лишним).

Таким образом, в начале игры надо все время увеличивать x – до тех пор, пока в первый раз загадавший не скажет "нет". Пусть x1<x2<x3<... – последовательность, которую угадывающий решил называть, пока не получит первый ответ "нет". Она должна быть бесконечной, так как n может оказаться сколь угодно большим.

Пусть теперь наступил второй этап игры: на k -й вопрос загадавший в первый раз ответил "нет". Таким образом,

xk-1 n<xk.

Дальше можно применить стратегию, аналогичную описанной выше стратегии Sn , делить оставшийся промежуток все время пополам. Очевидно, при этом будет потрачено до ]log _2 (xk-xk-1)[ вопросов.

Предположим, что на втором этапе игры, т.е. после первого ответа "нет", мы именно так и играем. Остается выбрать монотонно возрастающую последовательность xk , чтобы полностью определить стратегию.

Разберем три конкретных стратегии, отличающиеся лишь выбором последовательности xk .

1. Стратегия T1 : xk=10k . Тогда, как указано в условии, fT(n) растет примерно как .

2. Стратегия T2 : xk=2k . Тогда число вопросов на первом этапе не больше ]log _2 n[ , а число вопросов на втором этапе не больше ]log _2 [ . Всего получается примерно 2log _2 n вопросов.

3. Стратегия T3 : xk=22k . Теперь число вопросов на первом этапе резко уменьшилось. В самом деле, пусть

Тогда число вопросов на первом этапе игры равно k и не превышает

k log _2 log _2 n+1,

что при больших n значительно меньше, чем log _2 n . На втором этапе мы потратим приблизительно
log _2 (22k-22k-1) log _2 22k=2k

вопросов. Хорошо это или плохо? Это зависит от числа n . Оказывается, для наибольших n в промежутке(eq:180.2) эта стратегия значительно лучше, чем для наименьших n в том же промежутке.

Пусть n=22k-1 .

Тогда

fT3(n) log _2 log _2 n+2k log _2 n+log _2 log _2 n.


При больших n второе слагаемое значительно меньше первого, и отношение fT3(n) к нижней оценке log _2 n (см.формулу(eq:180.1)) близко к 1 .

Пусть теперь n=22k-1 . Тогда величина fT3(n) – такая же, а выраженная через n она составляет

fT3(n) log _2 log _2 n+2k 2log _2 n+log _2 log _2 n,

т.е. примерно вдвое превышает нижнюю оценку(eq:180.1). Таким образом, для этих значений n стратегия T3 ничем не лучше стратегии T2 .

Это положение иллюстрируется графиком на рис.7. На этом графике красная линия условно изображает доказанную выше нижнюю оценку: log _2 n (график носит качественный, эскизный характер и не претендует на точность).

Ступенчатая черная линия изображает график функции fT3(n) . Эта функция постоянна на каждом промежутке вида(eq:180.2). К концу такого промежутка нижняя оценка почти догоняет ее, но тут fT3(n) скачком увеличивается и делается примерно вдвое больше.

Возникает вопрос: существует ли такая стратегия T4 , для которой fT4(n) при всех n не слишком сильно отличается от нижней оценки? (Предположительный график fT4(n) приведен синим пунктиром.)

Сейчас мы опишем стратегию T4 такую, что

т.е. относительное превышение fT4(n) над нижней оценкой log _2 n при больших n стремится к нулю.

Первый этап игры, как и прежде, определяется последовательностью чисел

xk=22k.

Пусть на k -й вопрос мы в первый раз получили ответ "нет", откуда
22k-1 n< 22k.


Опишем стратегию T4 для второго этапа игры. Припишем каждому n в промежутке(eq:180.2) "вес", равный . Будем теперь задавать вопросы так, чтобы делить примерно пополам не количество значений, которые еще может принимать n , а сумму их весов.

Подсчитаем примерно, сколько вопросов уйдет на отгадывание произвольного n в промежутке(eq:180.2). Положим m=22k-1 . Вначале сумма весов примерно равна

Если мы отгадаем n , то доведем сумму весов до величины . Значит, сумма весов уменьшится примерно в n ln n раз. Предположим, что нам каждый раз удавалось делить ее точно вдвое. Тогда было затрачено

log _2 n ln n=log _2 n+log _2 ln n log _2 n

вопросов (второе слагаемое при больших n значительно меньше первого). Поскольку сумму весов, как правило, точно разделить пополам не удастся, число вопросов фактически несколько больше. Можно показать (но это уже сложнее), что она все же не превышает
log _2 n+const log _2 log _2 n

вопросов. (Здесь const означает постоянное число, которое мы не оценивали.) Прибавляя сюда число вопросов на первом этапе игры, мы только увеличиваем коэффициент во втором слагаемом. Таким образом, мы построили стратегию, которая позволяет отгадать любое n не более чем за
log _2 n+const log _2 log _2 n

вопросов.

Легко показать, что эта функция удовлетворяет условию(eq:180.3), которое мы и обещали выполнить.

Источники и прецеденты использования

журнал
Название "Квант"
год
Год 1972
выпуск
Номер 12
Задача
Номер М180

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .