ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 64573
Тема:    [ Теория алгоритмов (прочее) ]
Сложность: 3+
Классы: 6,7,8
В корзину
Прислать комментарий

Условие

Мама испекла пирожки – три с рисом, три с капустой и один с вишней – и выложила их на блюдо по кругу (см. рис.). Потом поставила блюдо в микроволновку подогреть. На вид все пирожки одинаковые. Маша знает, как они лежали, но не знает, как повернулось блюдо. Она хочет съесть пирожок с вишней, а остальные считает невкусными. Как Маше наверняка добиться этого, надкусив как можно меньше невкусных пирожков?


Решение

  Понятно, что за одно надкусывание Маша справиться с задачей не сможет. Если Маша, например, попробовала пирожок с капустой, то она не в состоянии определить, какой именно из трёх ей достался, а поэтому не сможет с уверенностью найти пирожок с вишней. Покажем, как Маша справится с задачей за два надкусывания.
  Пусть Маша надкусила пирожок, а он оказался не с вишней, а с капустой. Тогда она может попробовать пирожок, лежащий через один от него по часовой стрелке. Если это пирожок с вишней, то Маша добилась своего, если с рисом, то искомый пирожок между надкусанными, а если снова с капустой, то надо брать следующий по часовой стрелке, и это точно будет пирожок с вишней.
  Если первый пирожок будет с рисом, Маша может действовать аналогично, но двигаться против часовой стрелки.

Замечания

1. Подобным образом Маша может действовать и при большом числе "невкусных" пирожков. Пусть на блюде лежит N холодных пирожков с капустой, потом пирожок с вишней и снова N пирожков с рисом. Маша может заметить средний пирожок с капустой (а если N чётно, то любой из двух средних) и запомнить, сколько пирожков от него надо отсчитать по часовой стрелке, чтобы взять пирожок с вишней. Когда пирожки согреются, Маша пробует один пирожок. Пусть ей не повезло, и он оказался с капустой. Маша тогда может представить себе, что она попробовала тот самый средний пирожок, и отсчитать от него сколько нужно. Если она и впрямь угадала, ей достанется вишня, если же нет, то она поймёт, оказалась ли она ближе к желанному пирожку, чем выбранный средний, или дальше от него. В любом случае неопределенность уменьшилась вдвое: после одной пробы у Маши "под подозрением" осталось не больше половины пирожков с капустой.

2. Много интересного о задачах на количество информации можно узнать из книги К.А. Кнопа "Взвешивания и алгоритмы: от головоломок к задачам" (М., МЦНМО, 2011).

3. 7 баллов.

Источники и прецеденты использования

олимпиада
Название Математический праздник
год
Год 2014
класс
Класс 6
задача
Номер 5

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .