Здесь больше нет рекламы. Но могла бы быть, могла.

Автор Тема: Задачка про гномов.  (Прочитано 19262 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Мёнин

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

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

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

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

Оффлайн Wintera

  • Властелин носков
  • Ветеран
  • *****
  • Пол: Женский
    • Просмотр профиля
Задачка про гномов.
« Ответ #1 : 22/01/2013, 07:44:45 »
Ну, как минимум, правильный ответ известен из книги "Хоббит"  ;D

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

upd. Да, а ещё число гномов не должно быть кратно номеру первого согласного гнома. Иначе они впадут в бесконечный цикл и не договорятся.
« Последнее редактирование: 22/01/2013, 07:46:57 от Wintera »
Уж если приходит цунами,
Веди себя как подобает -
Беги и ори во всю глотку.

Оффлайн Исхэ

  • Пользователь
  • **
  • Пол: Женский
  • эксцентричная ихтиофауна
    • Просмотр профиля
Задачка про гномов.
« Ответ #2 : 22/01/2013, 09:15:55 »
О, задачки про гномов  :)
Мне когда-то вот такую подкидывали:
Цитировать
Тролль поймал N гномов и посадил их в Черную Яму. Туда же он бросил N колпаков, некоторые из которых были красные, а некоторые черные. И приказал гномам их надеть (гномы в темноте не видят, у кого какого цвета колпак).
Потом тролль предложил своим пленникам веселую игру. Он по очереди вытаскивает гномов из ямы и предлагает угадать цвет своего колпака. Если угадает - буден отпущен, если нет - съеден.
Важное дополнение: вытаскиваемый гном видит своих товарищей, они же его -нет; но слышат его ответ троллю.
Вопрос: как должны отвечать гномы, чтобы спаслось максимальное их число?
- в ответ на что я придумала свою:
Цитировать
...и вот гномы додумались до решения, и бедолага тролль остался голодным. Стало ему обидно до чертиков, что какие-то гномы его перехитрили. Тогда он пошел и поймал еще сто гномов, посадил их в Страшную Черную Яму и задумался: как бы этих съесть так, чтобы интеллектуальное удовольствие от того тоже получить, не гастрономическое онли. Посмотрел он на пищащих в яме гномов, захихикал и сказал:

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

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

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

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

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

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

Вопрос: как им это удалось?)
...А как подъидут езуиты и начнут неудобьпонятныя своя силлогисмы, сиречь премудрость аквинову да скоттову, злохитростно всевати - что тогда? Не иное что, как шатание ума, парение, любомудрстование со всеконечным отпадением от веры.

Оффлайн Мёнин

  • кристофер-толкинист
  • Мафия
  • **********
  • Пол: Мужской
  • посмотри в глаза чудовищ
    • Просмотр профиля
Задачка про гномов.
« Ответ #3 : 22/01/2013, 14:51:40 »
upd. Да, а ещё число гномов не должно быть кратно номеру первого согласного гнома. Иначе они впадут в бесконечный цикл и не договорятся.
Это необходимое, но не достаточное условие: см. на 11 или 14 гномов.

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

Цитировать
Тут тролль задумался и сказал: "Нет, если кто-нибудь из вас ошибется, я всех съем, так и знайте". И ушел.
Верно. Решение для потери одного гнома было бы слишком простым.
Впрочем, оно и так не сложное — проще, чем для предыдущей задачки.
« Последнее редактирование: 22/01/2013, 15:08:01 от Мёнин »

Оффлайн Wintera

  • Властелин носков
  • Ветеран
  • *****
  • Пол: Женский
    • Просмотр профиля
Задачка про гномов.
« Ответ #4 : 24/01/2013, 19:16:34 »
upd. Да, а ещё число гномов не должно быть кратно номеру первого согласного гнома. Иначе они впадут в бесконечный цикл и не договорятся.
Это необходимое, но не достаточное условие: см. на 11 или 14 гномов.

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

Уж если приходит цунами,
Веди себя как подобает -
Беги и ори во всю глотку.