МАЛЫЙ МЕХМАТ МГУ

Кружок 9-11 классов

Количество информации. 12 февраля 2011 года

Сначала сосчитай, потом угадывай!

1.

Паша загадал натуральное число от 1 до 8. Витя хочет отгадать его, задавая Паше вопросы, на которые тот отвечает „да” либо „нет”. Как должен действовать Витя, чтобы отгадать загаданное число за 3 вопроса?

2.

Паша загадал число от 1 до 10. Докажите, что Вите не хватит трёх вопросов для того, чтобы угадать это число.

Решение 1-е Решение 2-е

Решение 1-е. („последовательное”) Проследим, сколько возможностей для загаданного числа остается после ответов Паши. Каким бы ни был первый вопрос Вити, до него всего 10 вариантов, поэтому после ответа может остаться не менее 5 вариантов. Каким бы ни был второй вопрос, после ответа на него может остаться не менее 3 вариантов, а после третьего — не менее 2. Но это и значит, что после трёх ответов Вите не удалось угадать число.

Решение 2-е. („взгляд сверху”) Предположим, что Вите как-то удалось составить набор вопросов, решающих задачу: для второго вопроса он, возможно, заготовил 2 варианта — для ответов „да” и „нет” на первый вопрос, для третьего — 4 варианта. Теперь есть 8 вариантов развития событий, которые мы для краткости назовем „наборами ответов”. Например, набор ответов „да, нет, да” означает, что на первый вопрос был дан ответ „да”. Далее Витя задал второй вопрос, приготовленный для случая ответа „да”, получил ответ „нет”, задал третий вопрос, приготовленный для случая ответов „да, нет” и получил на него ответ „да”. Теперь он обязан назвать задуманное число, поэтому каждому набору ответов должно соответствовать не более одного числа (иначе мы с Витей не решили задачу). Но такое невозможно: чисел больше, чем наборов ответов. Противоречие.

3.

a) В орфографическом словарике 128 страниц, на каждой из них по 64 слова. Паша открыл словарь на случайной странице и загадал случайное слово с этой страницы. Сможет ли Витя угадать его за 13 вопросов? b) В англо-русском словарике 80 страниц, на каждой из них по 50 слов. Паша открыл словарь на случайной странице и загадал случайное слово с этой страницы. За какое наименьшее число вопросов Витя сможет заведомо угадать его?

4.

Паша загадал натуральное число A от 1 до 8. Витя называет любое натуральное число X, и Паша отвечает, верно ли, что X делится на A. Помогите Вите угадать A после трёх таких вопросов.

5.

Есть колода из 36 карт, из которых задумана одна. Разрешается разложить карты на стопки с разным числом карт и спросить, в какой из стопок задуманная карта. Как найти задуманную карту за два таких вопроса?

6.

Задача-шутка. В этой задаче Паша может отвечать на вопросы „да”, „нет” или „не знаю”. Он загадал число — 1, 2 или 3. Придумайте вопрос, ответ на который позволит Вите угадать это число.

Во всех следующих задачах используются чашечные весы с двумя чашками без стрелок. Они показывают, равны ли веса на разных чашках, и если нет, то какой больше.

7.

Из 27 монет одна фальшивая. За какое минимальное число взвешиваний можно найти фальшивую монету, если известно, что она легче настоящих?

8.

Решая предыдущую задачу, Паша положил в первом взвешивании на каждую чашу весов не по 9 монет. Докажите, что ему не хватит трех взвешиваний для определения фальшивой монеты.

9.

Из девяти внешне одинаковых монет 7 весят по 2 г, одна — 1 г, и еще одна — 4 г. Как за 3 взвешивания на двухчашечных весах без гирь найти 4-граммовую монету?

10.

В ряд лежат 8 монет, при этом из левых четырёх одна фальшивая и из правых четырех тоже одна фальшивая (обе фальшивые легче настоящих и равны по весу друг другу). За два взвешивания найдите, сколько настоящих монет лежит между парой фальшивых (сами фальшивые монеты определять не обязательно).