Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/mccme/2007/8klass/03.doc Дата изменения: Sat Oct 21 15:07:50 2006 Дата индексирования: Sat Dec 22 18:51:38 2007 Кодировка: koi8-r

Математический кружок МЦНМО
8 класс
3 занятие. Количество информации.
21.10.06
Хулиганы запустили в школу трёх поросят,
на которых были нарисованы номера 1, 2,
4. Хотя поросят быстро поймали,
переполох продолжался: полиция искала
поросенка с номером 3.

1. Хулиганы выпустили в школу несколько поросят. Из секретных источников
стало известно, что в школу выпущено либо 2, либо 3, либо 4 поросёнка.
Одного из хулиганов поймали. Известно, что перепуганный хулиган
отвечает честно. Можно ли, задав хулигану ровно один вопрос, на
который тот ответит "да" или "нет", точно узнать, сколько поросят было
выпущено в школу?

2. Мистер Фикс с помощником показывают фокус по угадыванию числа: Зритель
задумывает число от 1 до 4 и сообщает его помощнику. После этого в
комнату входит Фикс, который должен угадать загаданное число. У
помощника на столе стоят два пустых стакана. Фикс знает, что если,
когда он войдет, оба стакана будут стоять правильно, значит было
загадано число 1. Если левый стакан перевернут дном вверх, - было
загадано 2, если правый перевёрнут, то - 3. Если же оба стакана
перевернуты, то зритель загадал 4. После нескольких опытов Зритель
заявил, что теперь он будет загадывать произвольное число от 5 до 20.
а) Сможет ли Фикс в этой ситуации обойтись 4 стаканами? (Стаканы на
столе обязательно должны стоять в ряд и передвигать стаканы нельзя.
Время передоговориться с помощником у Фикса есть.)
б) Сможет ли Фикс при этих условиях обойтись тремя стаканами?
в) Сколько стаканов понадобится Фиксу для фокуса с угадыванием числа
от 1 до 50?

3. а) Среди 4 монет одна является фальшивой и весит меньше, чем
настоящая. Можно ли за одно взвешивание на чашечных весах без гирь
выявить фальшивую монету?

б) Среди 10 монет одна является фальшивой и весит меньше, чем
настоящая. Можно ли за два взвешивания на чашечных весах без гирь
выявить фальшивую монету?

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

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

4. Хрюша загадал натуральное число от 1 до 50. Степашка может задавать
вопросы, на которые Хрюша отвечает только "да" или "нет". За какое
наименьшее число попыток Степашка гарантированно узнает задуманное
число?

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


6. В русском алфавите 33 буквы. Нужно сопоставить каждой букве уникальную
цепочку из нулей и единиц длины n.
а) При каком наименьшем n это возможно?

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

7. Хулиганы выпустили в школу несколько поросят. Из секретных источников
стало известно, что в школу выпущено либо 2, либо 3, либо 4 поросёнка.
Одного из хулиганов поймали. Известно, что перепуганный хулиган
отвечает честно. Можно ли, задав хулигану ровно один вопрос, на
который тот ответит "да", "нет" или «не знаю», точно узнать, сколько
поросят было выпущено в школу?

8. Хрюша загадал натуральное число от 1 до 20. Степашка пишет свои
вопросы заранее, каждый на отдельном листочке, потом отдаёт их Хрюше.
Хрюша читает вопросы в произвольном порядке и пишет ответ: «да» или
«нет» (в вопросе запрещается ссылаться на другие вопросы). После того,
как Хрюша просмотрел все бумажки, он возвращает их. Степашка по
полученным ответам должен угадать Хрюшино число. Сколько вопросов
необходимо написать Степашке?




Дополнительные задачи к занятию ?3 (Количество информации)

7. Хулиганы выпустили в школу несколько поросят. Из секретных источников
стало известно, что в школу выпущено либо 2, либо 3, либо 4 поросёнка.
Одного из хулиганов поймали. Известно, что перепуганный хулиган
отвечает честно. Можно ли, задав хулигану ровно один вопрос, на
который тот ответит "да", "нет" или «не знаю», точно узнать, сколько
поросят было выпущено в школу?

8. Хрюша загадал натуральное число от 1 до 20. Степашка пишет свои
вопросы заранее, каждый на отдельном листочке, потом отдаёт их Хрюше.
Хрюша читает вопросы в произвольном порядке и пишет ответ: «да» или
«нет» (в вопросе запрещается ссылаться на другие вопросы). После того,
как Хрюша просмотрел все бумажки, он возвращает их. Степашка по
полученным ответам должен угадать Хрюшино число. Сколько вопросов
необходимо написать Степашке?




Дополнительные задачи к занятию ?3 (Количество информации)

7. Хулиганы выпустили в школу несколько поросят. Из секретных источников
стало известно, что в школу выпущено либо 2, либо 3, либо 4 поросёнка.
Одного из хулиганов поймали. Известно, что перепуганный хулиган
отвечает честно. Можно ли, задав хулигану ровно один вопрос, на
который тот ответит "да", "нет" или «не знаю», точно узнать, сколько
поросят было выпущено в школу?

8. Хрюша загадал натуральное число от 1 до 20. Степашка пишет свои
вопросы заранее, каждый на отдельном листочке, потом отдаёт их Хрюше.
Хрюша читает вопросы в произвольном порядке и пишет ответ: «да» или
«нет» (в вопросе запрещается ссылаться на другие вопросы). После того,
как Хрюша просмотрел все бумажки, он возвращает их. Степашка по
полученным ответам должен угадать Хрюшино число. Сколько вопросов
необходимо написать Степашке?