Версия для печати
Убрать все задачи

---

Числа a, b, c таковы, что уравнение  x³ + ax² + bx + c = 0  имеет три действительных корня. Докажите, что если  –2 ≤ a + b + c ≤ 0,  то хотя бы один из этих корней принадлежит отрезку  [0, 2].

   Решение

---

На столе лежат n спичек  (n > 1).  Двое игроков по очереди снимают их со стола. Первым ходом игрок снимает со стола любое число спичек от 1 до  n – 1,  а дальше каждый раз можно брать со стола не больше спичек, чем взял предыдущим ходом партнер. Выигрывает тот, кто взял последнюю спичку. Найдите все n, при которых первый игрок может обеспечить себе выигрыш.

   Решение

---

Окружность с центром O вписана в треугольник ABC и касается его сторон AB, BC и AC в точках E, F и D соответственно. Прямые AO и CO пересекают прямую EF в точках M и N. Докажите, что центр окружности, описанной около треугольника OMN, точка O и точка D лежат на одной прямой.

   Решение

---

Даны два квадратных трёхчлена, имеющих корни. Известно, что если в них поменять местами коэффициенты при x², то получатся трёхчлены, не имеющие корней. Докажите, что если в исходных трёхчленах поменять местами коэффициенты при x, то получатся трёхчлены, имеющие корни.

   Решение

---

Существует ли такой квадратный трёхчлен P(x) с целыми коэффициентами, что для любого натурального числа n, в десятичной записи которого участвуют одни единицы, число P(n) также записывается одними единицами?

   Решение

---

Даны 19 карточек. Можно ли на каждой из карточек написать ненулевую цифру так, чтобы из этих карточек можно было сложить ровно одно 19-значное число, кратное на 11?

   Решение

---

Последовательность (a_n) задана условиями a₁= 1000000 , a_n+1=n[]+n . Докажите, что в ней можно выделить бесконечную подпоследовательность, являющуюся арифметической прогрессией.

   Решение

---

На совместной конференции партий лжецов и правдолюбов в президиум было избрано 32 человека, которых рассадили в четыре ряда по 8 человек. В перерыве каждый член президиума заявил, что среди его соседей есть представители обеих партий. Известно, что лжецы всегда лгут, а правдолюбы всегда говорят правду. При каком наименьшем числе лжецов в президиуме возможна описанная ситуация? (Два члена президиума являются соседями, если один из них сидит слева, справа, спереди или сзади от другого.)

   Решение

---

Четырехугольник ABCD описан около окружности. Биссектрисы внешних углов A и B пересекаются в точке K , внешних углов B и C – в точке L , внешних углов C и D – в точке M , внешних углов D и A – в точке N . Пусть K₁ , L₁ , M₁ , N₁ – точки пересечения высот треугольников ABK , BCL , CDM , DAN соответственно. Докажите, что четырехугольник K₁L₁M₁N₁ – параллелограмм.

   Решение

---

AA₁ и BB₁ – высоты остроугольного неравнобедренного треугольника ABC. Известно, что отрезок A₁B₁ пересекает среднюю линию, параллельную AB, в точке C'. Докажите, что отрезок CC' перпендикулярен прямой, проходящей через точку пересечения высот и центр описанной окружности треугольника ABC.

   Решение

---

В языке жителей Банановой Республики количество слов превышает количество букв в их алфавите. Докажите, что найдется такое натуральное k , для которого можно выбрать k различных слов, в записи которых используется ровно k различных букв.

   Решение

---

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

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

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

   Решение

Темы:    [ Теория игр (прочее) ] [ Двоичная система счисления ] [ Логарифмические неравенства ] [ Предел последовательности, сходимость ]

Сложность: 8+ Классы: 10,11

Прислать комментарий

Условие

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

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

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

Решение

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

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

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

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

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

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

f'_T(n) ]log _{_}2 N[.

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

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

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

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

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

x_k-1 n<x_k.
Дальше можно применить стратегию, аналогичную описанной выше стратегии S_n , делить оставшийся промежуток все время пополам. Очевидно, при этом будет потрачено до ]log _{_}2 (x_k-x_k-1)[ вопросов.

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

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

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

2. Стратегия T² : x_k=2^k . Тогда число вопросов на первом этапе не больше ]log _{_}2 n[ , а число вопросов на втором этапе не больше ]log _{_}2 [ . Всего получается примерно 2log _{_}2 n вопросов.

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

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

k log _{_}2 log _{_}2 n+1,
что при больших n значительно меньше, чем log _{_}2 n . На втором этапе мы потратим приблизительно
log _{_}2 (22^k-22^k-1) log _{_}2 22^k=2^k
вопросов. Хорошо это или плохо? Это зависит от числа n . Оказывается, для наибольших n в промежутке(eq:180.2) эта стратегия значительно лучше, чем для наименьших n в том же промежутке.

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

Тогда

f_T³(n) log _{_}2 log _{_}2 n+2^k log _{_}2 n+log _{_}2 log _{_}2 n.

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

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

f_T³(n) log _{_}2 log _{_}2 n+2^k 2log _{_}2 n+log _{_}2 log _{_}2 n,
т.е. примерно вдвое превышает нижнюю оценку(eq:180.1). Таким образом, для этих значений n стратегия T³ ничем не лучше стратегии T² .

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

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

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

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

т.е. относительное превышение f_T⁴(n) над нижней оценкой log _{_}2 n при больших n стремится к нулю.

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

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

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

Подсчитаем примерно, сколько вопросов уйдет на отгадывание произвольного n в промежутке(eq:180.2). Положим m=22^k-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), которое мы и обещали выполнить.

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