Нижегородский файловый портал
RSS - каналы
Главное меню
Категории каталога
Мои статьи [5]
Школа покера [5]
Софт [40]
Радиолюбителям и электрикам [8]
Интернет [167]
Система [89]
Комплектующие ПК [47]
Безопасность [56]
Программирование [18]
Веб-дизайнеру [5]
Игры [6]
Полезные советы [24]
Кулинария [1]
Телефония [10]
Мобильник [17]
Планшеты [14]
Медицина [5]
Работа [4]
Домашнему мастеру [0]
Строительство и ремонт [19]
Для сада и огорода [2]
Юмор и приколы [12]
Интересное [114]
Пластики [3]
Разное [238]
Мини-чат
Правила мини-чата



Мини-чат в окне
Погода в Нижнем
Яндекс.Погода
Главная » Статьи » Интересное

Занимательная задача про гномов и людоеда


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


"На следующее утро - сказал он, я построю вас в колонну и в случайном порядке надену на вас шапки двух цветов (красный и синий). Начиная с последнего в колонне, я буду спрашивать, какого цвета его шапка. Того, кто назовет цвет своей шапки правильно - отпущу, тех кто назовет неправильный цвет - того съем. Вы будете видеть всех тех, кто стоит впереди и слышать ответы тех, кто сзади. Но цвет своей шапки никто не видит. Говорить можно только одно слово – «красный» или «синий», иначе съем всех сразу".

Соотношение красных и синих шапок гномы не могут знать. Никакие дополнительные сигналы подавать нельзя (интонацией, паузами в ответах и т.п.).

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

Вопрос: какой способ придумали гномы?



ОТВЕТ
Ход рассуждений

Простые решения, когда каждый гном, к примеру, называет цвет шапки впередистоящего, не годиться. В этом случае гномы через одного будут знать свой цвет, а другие должны будут жертвовать собой ради спасения впередистоящего. Это не годиться.

Давайте на минуту представим, что ограничений на общение между гномами нет. Первый же гном сможет остальным озвучить всю последовательность цветов шапок. Но ему, увы, помочь никто не сможет: его шапку вообще никто не видит. Остальные гномы без вариантов должны говорить только цвета своих шапок – иначе решение не будет достигнуто. Только первый гном может позволить себе роскошь передать остальным некий код-отгадку, с помощью которой они смогут выжить.

Итак, только первый гном, который видит всех стоящих впереди, может зашифровать какую-то информацию для остальных. Но что можно зашифровать, если вариантов ответов только 2: «красный» или «синий»?

Дело в том, что передавать всю последовательность и не надо. Каждый следующий гном обладает той же информацией, что и все остальные: он видит шапки впереди стоящих и слышит ответы предыдущих коллег по несчастью. Из той информации, которую ему сообщит самый первый гном (а ведь он видел всех оставшихся) надо вычленить информацию которой обладает об остальных текущий гном чтобы вычислить цвет своей шапки.

В двух вариантах ответов можно зашифровать, например, «четный» и «нечетный». Далее, примем красный цвет  равный 1, а синий будет 0. Первый гном суммирует цвета шапок всех остальных, используя этот код. И результат сообщает вслух (например, красный – «четный», «синий» - нечетный – у гномов есть вся ночь, чтобы договориться об этом).

Второй гном, услышав шифр, так же суммирует всех стоящих впереди. Если результат совпадает с тем, что сказал первый гном, значит цвет его шапки не повлиял на общую сумму. Стало быть, это «ноль» - синий. Если результат изменился, значит это «единица» - красный.

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

Этот способ позволяет выжить N-1 гному. Общее количество гномов при этом не имеет значения, задача решается для любого N. Самый первый гном не обязательно погибает: с вероятностью 50% шифр может совпасть с цветом его шапки и тогда он останется жив и здоров.

P.S. Говорят, эту задачу предлагают на собеседовании в Microsoft
Добавил: Админ-21NN | Просмотров: 7712 | Комментарии: 1 | Рейтинг: 5.0/3


Обратите Ваше внимание на другие статьи:

Уважаемые пользователи, пожалуйста, оставляйте комментарии! Нам очень важно Ваше мнение!
Всего комментариев: 1
01.05.2012 Спам
прикольная задачка!мне она чем то напомнила задачу о быстроногом Ахилле и ползущей черепахе

Добавлять комментарии могут только зарегистрированные пользователи.

    
Меню пользователя
Аватар гостя

Приветствуем Вас, Гость

Логин:
Пароль:
Поиск по сайту
Поиск по названию
Поиск по тегам
Горячие темы форума
Зарабатываем деньги
Детская игра Подарки...
Тест скорости подклю...
кое что о Windows
Кто ты, человек?
Новая валюта портала
Все о сексе
"Что мешает нам...
Культура
Афоризмы
Лучшие 13 анекдотов ...
как защитить свой ко...
поговорим о софте
восстановление данны...
Я ненавижу Дом-2
Волга-Телеком
Кулинария "Кокт...
Стол заказов
Жалобы
С Днем Победы!!!
Прикольные картинки
С праздником Пасхи !...
Статистика
Новых за месяц: 138
Новых за неделю: 43
Новых вчера: 8
Новых сегодня: 3
Всего: 5377
Из них:
Администраторов: 3
$$$-Модераторов: 1
Модераторов: 3
Прокураторов: 3
-----------------
далее:
Проверенных: 247
Пользователей: 2885
Новичков: 1942
Заблокированных: 100
-----------------
Из всех пользователей:
Мужчин и парней: 4212
Женщин и девушек: 1164
Именинники
Поздравляем с Днем рожденья:

MagicMan(30), Akser(23), lenadomash(28), kondrahin(39), aviva(53), МокрыйДжо(37), Капибар(29), Baybakov(39), Лесник00(34), volsoft(29)
Режим ON-LINE
Онлайн всего: 4
Гостей: 4
Пользователей: 0

Сейчас на портале:
Наша кнопочка
Нижегородский файловый портал

HTML-код кнопки:
Реклама
Размещение рекламы

Яндекс.Метрика
Регистрация сайта в каталогах, раскрутка и оптимизация сайта, контекстная реклама Ремонт холодильников в Нижнем Новгороде

Copyright © BankRemStroy © 2009-2017