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

---

Двое играют в такую игру. Один задумывает натуральное число 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.

   Решение

Страница: << 1 2 [Всего задач: 9]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями  

---

Задача 98247

Темы:   [ Десятичная система счисления ] [ Логарифмические неравенства ] [ Целая и дробная части. Принцип Архимеда ] [ Приближения чисел ]

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

Рассматривается последовательность, n-й член которой есть первая цифра числа 2ⁿ.
Докажите, что количество различных "слов" длины 13 – наборов из 13 подряд идущих цифр – равно 57.

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

Решение

---

Задача 73715

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

Сложность: 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.

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

Решение

---

Задача 73775

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

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

По заданному ненулевому x значение x⁸ можно найти за три арифметических действия: x² = x · x, x⁴ = x² · x², x⁸ = x⁴ · x⁴, а x¹⁵ — за пять действий: первые три — те же самые, затем x⁸ · x⁸ = x¹⁶ и x¹⁶ : x = x¹⁶. Докажите, что

а) x¹⁶ можно найти за 12 действий (умножений и делений);

б) для любого натурального n возвести x в n-ю степень можно не более чем за 1 + 1,5 · log₂n действий.

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

Решение

---

Задача 105071

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

Сложность: 5- Классы: 10,11

Докажите, что первые цифры чисел вида 2²ⁿ образуют непериодическую последовательность.

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

Решение

---

Страница: << 1 2 [Всего задач: 9]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями