У Гены есть 50 ящиков, пронумерованных числами от 1 до 50. 49 из них пустые, а в одном лежат апельсины. Чебурашка получит апельсины, если отгадает, в каком из ящиков они лежат, для этого он может написать пачку записок с вопросами, требующими ответа «да» или «нет». Гена перемешивает записки в пачке и, не оглашая вслух вопросов, честно отвечает на все. Как узнать наверняка, в каком из ящиков лежат апельсины? Какое наименьшее количество записок для этого нужно?

задан 11 Май '15 22:48

10|600 символов нужно символов осталось
3

Пусть изготовлено $%m$% записок. Единственная информация, которая далее может быть извлечена из ответов -- это количество ответов "да" и "нет". Положительных ответов может быть 0, 1, ... , $%m$% -- всего $%m+1$% случай. Их должно быть достаточно для того, чтобы различить 50 разных ситуаций -- по числу ящиков, в одном из которых находятся апельсины. Отсюда $%m+1\ge50$%, то есть $%m\ge49$%.

Приведём пример с 49 записками. Первая: "верно ли, что номер ящика с апельсинами больше 1?". Вторая: "верно ли, что номер ящика с апельсинами больше 2?". И так далее. Записка номер 49: "верно ли, что номер ящика с апельсинами больше 49?".

Легко видеть, что количество ответов "да", увеличенное на единицу, совпадает с номером ящика. Действительно, если апельсины лежат, скажем, в 13-м ящике, то на вопросы из первых 12 записок будет дан ответ "да", а на все остальные -- нет. Это же верно для общего случая. В каком порядке идут ответы, мы не знаем, но по количеству положительных ответов всё легко определяется.

ссылка

отвечен 12 Май '15 1:14

А как же элементарная сортировка делением? на вопросы же не наложено ограничение... выставили ящики в линию. Строим независимый от порядка задания вопрос: раздели ящики пополам, если не делится оставь справа на 1 больше, встань по середине, апельсины в одном из ящиков справа? и половина отсеялось не зависимо от ответа...

(12 Май '15 2:27) Isaev

@Isaev: здесь отличие от классической задачи угадывания одного числа из 50 состоит в том, что Чебурашка не знает, на какие вопросы ему отвечает Гена. Можете попробовать, например, сделать 2 записки для случая 4 ящиков. Я их перемешаю и дам какие-то ответы, а Вы попробуете угадать ящик.

(12 Май '15 2:36) falcao

Здесь ещё не совсем понятно, остаются ли ответы в порядке, котором он отвечал, или снова перемешиваются.

(12 Май '15 10:05) Isaev

@Isaev: последнее обстоятельство роли не играет, потому что в любом случае известно только количество ответов "да" и "нет".

(12 Май '15 16:19) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×378
×234
×60
×40

задан
11 Май '15 22:48

показан
1206 раз

обновлен
12 Май '15 16:19

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru