Тема: Задачка про гномов.

[Мёнин›]

"Гномы размножаются спорами. Ведь стоит двум гномам чего-нибудь не поделить, и сразу вокруг гномов становится тьма-тьмущая." — Красная Книга Западных Приколов.

Математическая задачка.

Гномы сидят вокруг стола и обсуждают, должны ли они взять Бильбо. Обсуждение подчинено следующим правилам:
— Гномы не доверяют хоббиту. В начале все гномы настроены против.
— Гномы спокойно обсуждают этот вопрос. Они высказывают своё мнение по очереди, например, все по одному по часовой стрелке, никого не пропуская.
— Гномы добрые в душе, и, если два гнома перед говорящим сказали "против", он готов дать хоббиту шанс и голосует "за".
— Гномы солидарны в хороших делах, так что, если два гнома сказали "за", то третий сидящий также говорит "за".
— Гномы убеждены в своих взглядах, так что в остальных случаях они мнения не меняют.
— Гномы останавливают обсуждение, когда за один круг никто из них не сменит своего мнения. Берут Бильбо они только в том случае, если все проголосовали "за".

Сколько было гномов, если их было больше десяти, но не более пятнадцати, а Бильбо они взяли с собой?

[Wintera›]

Ну, как минимум, правильный ответ известен из книги "Хоббит" 

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

upd. Да, а ещё число гномов не должно быть кратно номеру первого согласного гнома. Иначе они впадут в бесконечный цикл и не договорятся.

[Исхэ›]

О, задачки про гномов 
Мне когда-то вот такую подкидывали:

Тролль поймал N гномов и посадил их в Черную Яму. Туда же он бросил N колпаков, некоторые из которых были красные, а некоторые черные. И приказал гномам их надеть (гномы в темноте не видят, у кого какого цвета колпак).
Потом тролль предложил своим пленникам веселую игру. Он по очереди вытаскивает гномов из ямы и предлагает угадать цвет своего колпака. Если угадает - буден отпущен, если нет - съеден.
Важное дополнение: вытаскиваемый гном видит своих товарищей, они же его -нет; но слышат его ответ троллю.
Вопрос: как должны отвечать гномы, чтобы спаслось максимальное их число?

- в ответ на что я придумала свою:

...и вот гномы додумались до решения, и бедолага тролль остался голодным. Стало ему обидно до чертиков, что какие-то гномы его перехитрили. Тогда он пошел и поймал еще сто гномов, посадил их в Страшную Черную Яму и задумался: как бы этих съесть так, чтобы интеллектуальное удовольствие от того тоже получить, не гастрономическое онли. Посмотрел он на пищащих в яме гномов, захихикал и сказал:

"У кого-то из вас определенно перепачкан лоб. Как минимум у одного из сотни. Вот что я сделаю. Я оставлю вас в яме, но закрывать ее сверху не буду, так, что вы сможете видеть друг друга. А вы, если вы такие умные, будете сидеть и думать, у кого из вас лоб перепачкан. Разговаривать запрещено. Условные знаки подавать запрещено. И раз в десять минут я буду подходить и спрашивать, не желает ли кто из вас пойти вымыть лоб.

Если кто желает - он должен МОЛЧА встать и пойти мыться.  Если кто не желает - пускай продолжит сидеть.  Поскольку вас сто штук, то я приду ровно сто раз и сто раз спрошу.

Вам запрещено предварительно о чем-то договариваться, кто хоть слово скажет, того я тут же съем. Если встанет кто-нибудь с чистым лбом, его я тоже съем. И если после сотого моего вопроса кто-то с грязным лбом останется сидеть, его я тоже съем. А если вы все угадаете верно, то я вас отпущу".

Тут тролль задумался и сказал: "Нет, если кто-нибудь из вас ошибется, я всех съем, так и знайте". И ушел.

А надо заметить, он не врал про испачканные лбы, гномы и впрямь изрядно перемазались в своей яме. Но у некоторых из них лбы были все-таки чистыми. И стали гномы раздумывать, глядя друг на друга, как бы им остаться живыми.

Раз подошел тролль к яме - и никто не встал и не пошел мыть лоб. Второй раз подошел - и никто не встал. И так продолжалось ровно до N-ного раза, когда все N гномов с испачканными лбами встали и пошли мыться. А все, у кого был чистый лоб, остались сидеть и сидели до тех пор, пока не пришел тролль в сотый раз и не отпустил всех на свободу, потому что ничего ему более не оставалось.

Вопрос: как им это удалось?)

[Мёнин›]

upd. Да, а ещё число гномов не должно быть кратно номеру первого согласного гнома. Иначе они впадут в бесконечный цикл и не договорятся.

Это необходимое, но не достаточное условие: см. на 11 или 14 гномов.

Вопрос: как должны отвечать гномы, чтобы спаслось максимальное их число?

Задача известная, про мудрецов и людоедов обсуждали на Толкин.ру ещё.
Общее решение есть для любого количества заранее известных цветов. Спасаются все гномы, кроме первого отвечающего, которому может повезти, а может и нет.

и вот гномы додумались до решения, и бедолага тролль остался голодным.

Ну почему голодным. Первого он должен был съесть.

Тут тролль задумался и сказал: "Нет, если кто-нибудь из вас ошибется, я всех съем, так и знайте". И ушел.

Верно. Решение для потери одного гнома было бы слишком простым.
Впрочем, оно и так не сложное — проще, чем для предыдущей задачки.

[Wintera›]

upd. Да, а ещё число гномов не должно быть кратно номеру первого согласного гнома. Иначе они впадут в бесконечный цикл и не договорятся.

Это необходимое, но не достаточное условие: см. на 11 или 14 гномов.

Понятное дело, что недостаточное, соображалось навскидку.
Если более точно, то выходит, что решение не будет отрицательным 1) в случае, если общее число гномов N=k*m + 1, где k - порядковый номер гнома, который скажет "да", после того, как все предыдущие сказали "нет", m - любое натуральное число; 2) и только в том случае, если число гномов, после которого тот, кто сказал "нет" в прошлом круге, передумает и скажет "да", не больше двух (в противном случае "переломить" ход голосования не удастся).