Математический кружок

Занятие 1. За минимум вопросов

1. Я задумал целое число от 1 до 16. Разрешается задавать мне вопросы вида «Твое число больше такого-то?»
а) Как угадать задуманное число за 4 вопроса?
b) Можно ли наверняка отгадать это число за 3 вопроса? Ответ

2. Я задумал целое число от 1 до 100. Разрешается задавать мне вопросы, на которые можно ответить только «Да» или «Нет» (игра «Данетки»).
а) Как угадать задуманное число за 7 вопросов?
b) Можно ли наверняка отгадать это число за 6 вопросов? Ответ

3. Есть 65 одинаковых с виду монет. Из них 64 настоящих – весом ровно в 1 г, и одна фальшивая – весом 0,9 г. На точных электронных весах можно узнать вес любой группы монет. За какое наименьшее число взвешиваний можно наверняка выявить фальшивую монету? Ответ

4. Есть 9 одинаковых с виду монет. Из них 8 настоящих – весят одинаково, и одна фальшивая – легче настоящей. За какое наименьшее число взвешиваний на чашечных весах без гирь можно наверняка выявить фальшивую монету? Ответ

5. Есть несколько одинаковых с виду монет. Из них все, кроме одной, настоящие – весят одинаково, а одна фальшивая – легче настоящей. При каком количестве монет можно наверняка выявить фальшивую монету за 3 взвешивания на чашечных весах без гирь? Ответ

6. а) Есть 17 карт. Зритель загадывает одну из них. Фокусник раскладывает все карты не более чем на 4 стопки и узнает у зрителя, в какой стопке оказалась задуманная карта. Докажите, что он всегда может определить задуманную карту за 3 вопроса, а двух вопросов может и не хватить.
b) При каком наибольшем количестве карт можно наверняка определить задуманную карту за 3 вопроса? Ответ

7. В пятиугольнике проведены все стороны и диагонали. Я загадал один из этих отрезков. За какое наименьшее число вопросов можно наверняка угадать его при игре в "Данетки"? Ответ

8. На занятии присутствуют 5 мальчиков и 3 девочки. Я загадал одного мальчика и одну девочку. а) Как отгадать загаданных за 4 вопроса при игре в "Данетки"?
b) Докажите, что 3 вопросов может и не хватить.

9. Я загадал двоих из 7 присутствующих. За какое наименьшее число вопросов можно наверняка угадать обоих при игре в "Данетки"? Ответ

10*. На складе лежит 81 деталь, промаркированные первым или вторым сортом. Детали одинакового сорта весят одинаково, и каждая деталь второго сорта немного легче детали первого сорта. Известно, что ровно одна из деталей промаркирована неправильно. Покажите, что ее можно наверняка выявить за 4 взвешивания на чашечных весах без гирь.

11*. Среди 5 монет – ровно одна фальшивая: она отличается по весу от остальных, но неизвестно – легче или тяжелее. Требуется выявить ее на чашечных весах без гирь и узнать, легче она или тяжелее настоящей. Какое наименьшее число взвешиваний для этого наверняка хватит? Ответ

Стокгольм, 18 сентября 2004 г

Дополнительные задачи

12. Повар выложил на сковородку восемь котлет по кругу (по часовой стрелке), причем каждая следующая выкладываемая котлета была на 10 граммов тяжелее предыдущей. Когда котлеты поджарились, повар обнаружил, что забыл, с какой котлеты он начинал выкладывать. Помогите ему найти самую тяжелую котлету за наименьшее число взвешиваний на чашечных весах без гирь.

13. Из 4 монет одна фальшивая – но неизвестно, легче она или тяжелее настоящей. Кроме того, есть еще пятая монета – заведомо настоящая. За какое наименьшее число взвешиваний на чашечных весах без гирь можно определить фальшивую монету и выяснить, легче она или тяжелее? Ответ

14. Среди 7 шаров два радиоактивных. Можно проверять на радиоактивность кучку из любых шаров. За какое наименьшее число проверок можно найти оба радиоактивных шара? (Измеритель радиоактивности не показывает уровня радиации, а только выдает ответ «в данной кучке шаров нет радиоактивных» или «в данной кучке шаров есть радиоактивные») Ответ