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

---

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

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

---

Задача 60351  (#02.017)

Тема:   [ Принцип Дирихле (прочее) ]

Сложность: 2 Классы: 6,7

Докажите, что среди москвичей есть два человека с равным числом волос, если известно, что у любого человека на голове менее одного миллиона волос.

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

Решение

---

Задача 60352  (#02.018)

Темы:   [ Принцип Дирихле (прочее) ] [ Классическая комбинаторика (прочее) ]

Сложность: 2+ Классы: 7,8,9

В мешке 70 шаров, отличающихся только цветом: 20 красных, 20 синих, 20 жёлтых, остальные – чёрные и белые.
Какое наименьшее число шаров надо вынуть из мешка, не видя их, чтобы среди них было не менее 10 шаров одного цвета?

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

Решение

---

Задача 60353  (#02.019)

Темы:   [ Принцип Дирихле (прочее) ] [ Системы точек и отрезков (прочее) ]

Сложность: 3 Классы: 7,8

Некоторые точки из данного конечного множества соединены отрезками. Докажите, что найдутся две точки, из которых выходит поровну отрезков.

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

Решение

---

Задача 60354  (#02.020)

Тема:   [ Принцип Дирихле (прочее) ]

Сложность: 4- Классы: 8,9,10

Имеется  2k + 1  карточек, занумерованных числами от 1 до  2k + 1.  Какое наибольшее число карточек можно выбрать так, чтобы ни один из извлечённых номеров не был равен сумме двух других извлечённых номеров?

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

Решение

---

Задача 60355  (#02.021)

Тема:   [ Шахматные доски и шахматные фигуры ]

Сложность: 3 Классы: 7,8

Какое наибольшее число королей можно поставить на шахматной доске так, чтобы никакие два из них не били друг друга?

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

Решение

---

Страница: 1 2 3 4 >> [Всего задач: 16]      

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