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

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

Количество информации (30 октября 2010 года)

1.

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

2.

Никита загадал натуральное число от 1 до 1000.

а)

Андрей называет какое-то число, а Серёжа отвечает ему «угадал», «меньше» или «больше». За какое наименьшее число попыток Андрей гарантированно узнает задуманное число?

б)

Стёпа может задавать вопросы, на которые Серёжа отвечает только «да»или «нет». Сколько вопросов понадобится в этом случае?

в)

Может ли Стёпа обойтись таким же количеством вопросов, что и в пункте б), если он обязан задать их все сразу, то есть не использует ответы на предыдущие вопросы при выдумывании следующих?

3.

В русском языке 33 буквы. Нужно сопоставить каждой букве уникальную цепочку из нулей и единиц длины n.

а)

При каком наименьшем n это возможно?

б)

Можно ли закодировать все сочетания из двух букв цепочками нулей и единиц так, чтобы длина цепочки для каждого сочетания была меньше 2n, где n — число из пункта а) (то есть можно ли закодировать двухбуквенные слова более экономно, чем кодируя каждую букву отдельно)?

4.

Два шпиона работают учителями в одной школе. Они передают секретную информацию через классный журнал. На своём уроке первый шпион может поставить каждому из 20 учеников 9^И класса одну из оценок 3, 4, 5. Какое количество информации он передаст таким образом? Например, сможет ли он закодировать точную дату окончания второй четверти?

5.

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

6.

В языке зулусов три буквы: А, Б и В. Когда они, наконец, изобрели телеграф, решено было кодировать тексты следующим образом: А — 00, Б — 01, В — 10, а цепочка 11 означает конец слова. Буква А встречается втрое чаще, чем Б, буква Б — втрое раза чаще, чем В, а средняя длина слова — 13 букв. Используя эти данные, придумайте другой способ кодирования, при котором количество нулей и единиц, передаваемых по телеграфу, в среднем уменьшится (разрешено разные буквы кодировать цепочками разной длины). Посчитайте, во сколько раз.

7.

Имеется одна заведомо настоящая монета и 5 подозрительных, среди которых одна фальшивая (неизвестно, тяжелее она или легче настоящей).

а)

Найдите фальшивую монету за два взвешивания.

б)

Докажите, что если бы подозрительных монет было 6, то пункт а) не имел бы решения.

в)

Среди какого максимального количества монет можно выявить фальшивую за три взвешивания (никаких других монет нет)?