Задача. Эксперементальный пост

> Первые семеро кодируют количество черных шапок у остальных 93 мудрецов. Они могут посчитать количество черных впереди себя и точно назвать свой цвет.
> UPD Белая - 0, черная -1. 93 мудреца остануться в живых

Ох уж эти программисты с бинарным мЫшлением. Можно больше.
Если что, это была подсказка.

2Yalt. Согласен

Можно еще троично закодировать: Белый - 0, черный - 1, Сатрапы! - 2. Тогда 95 выжевет :-)
Или десятерично: двое по цифре крикнут

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

Аксакал в чёрной шапке за три дня бы получил тепловой удар:)

>>>> Первые семеро кодируют количество черных шапок у остальных 93 мудрецов. Они могут посчитать количество черных впереди себя и точно назвать свой цвет.
>>>> UPD Белая - 0, черная -1. 93 мудреца остануться в живых
>>>
>>> Ох уж эти программисты с бинарным мЫшлением. Можно больше.
>>> Если что, это была подсказка.
>>>
>>> 2Yalt. Согласен
>>
>> Договорились кодировать шапки впереди стоящих по системе:
>> - чёрная = 2 балла
>> - белая = 1 балл
>> Последний считает сумму и в случае чётного результата говорит "белая", нечётного - "чёрная". С вероятностью 1/2 погибает.
>>
>> Предпоследний считает по той же системе и понимает, отличается его результат (чёт/нечет) от последнего или нет. Если отличается - то говорит "белая", если нет - "чёрная". Он спасён.
>>
>> Остальные запоминают сказанное ранее и "меняют чёт на нечет" мысленно, если задний сказал "белая" и не меняют, если задний сказал "чёрная"
>>
>> Результат - 99 спасенных гарантированно и 1 с вероятностью 50/50
>
> Ришпект и уважуха! Действительно, зачем количество знать, достаточно четность

Спасибо.

Впрочем, упдатэ: если за чёрные шапки начислять по 0 баллов (= "считать только количество белых шапок впереди"), алгоритм в принципе не меняется. Видимо, я ступил из-за позднего времени.

>> Вот вам ещё про шапки:
>
>> Для самых умных та же задача, но с шапками трёх разных цветов.
>
> решение аналогично предыдущему, только кодировка другая.
>
> Например, каждая чёрная шапка стоящих впереди: 0, белая: 1, бурая: 2.
> Тогда последний мудрец выживает с вероятностью 1/3, остальные выживают.
>
> И ещё интересное дополнение - если кто-то из мудрецов ошибся, остальные слышат, как его "секирнули" и делают поправку в уме.
>

Две белых = 1 бурая. Не пойдет

> UPD Неправильно думаю, а ты правильно. Необязательно ж по четности свою шапку определять, по модулю 3 можно, хотя и сложнее это делать в уме :-)

Правильно. Так любое простое количество цветов можно кодировать, хоть 97.

А если усложнить задачу:

Шапок 2 вида.
Сколько мудрецов погибнет, если последний из них, зная, что играет "в русскую рулетку", от злости назвал неверный ответ?

Могут ли мудрецы, ещё оставшиеся в живых, это вычислить, и как-то скорректировать?
И каков их оптимальный алгоритм по борьбе с "предателями" в рядах играющих?

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

> Ты же сам писал. Как только казнят второго мудреца остальные скорректируют свой ответ на противоположный. Так как шапок всего 2, то этого достаточно.

Ты прав ) спасибо за интересную загадку

> У нас еще осталась нерешенной про числа на бумажках ))

Как вам такой вариант?


Первый: А
Второй: Б

Когда А говорит "не знаю" - это означает только то, что у А не 1 (иначе бы он знал, что у Б - 2)

Когда Б говорит "и я не знаю" - это означает, что у Б не 1 (иначе он знал бы, что у А - 2), и не 2 (т.к. у числа 2 соседи - числа 1 и 3, а поскольку у А не 1, тогда бы Б знал, что у А - 3). Никаких других выводов пока не следует.

Тогда А говорит "знаю" - это возможно в следующих вариантах:
i: у А - 2, поскольку у Б в таком случае однозначно 3
ii: у А - 3, поскольку у Б в таком случае однозначно 4

Разберём оба:
i: если у Б - 3, то по условиям задачи у А либо 2, либо 4. Но в случае, если бы у А было 4, он (А) бы не смог однозначно ответить, что знает, какое число у Б. Значит, если у Б - 3, А это знает, то у А - 2, и Б тоже это знает.

ii: Если у Б - 4, то по условиям задачи у А либо 3, либо 5. Если бы А затруднился с ответом, это бы означало, что у А 5, а так как ему однозначно ясно, что у Б - 4, то у А - 3.

Таким образом, правильный ответ: подобный диалог возможен, если у А:2, у Б:3 или у А:3, у Б:4

>> У нас еще осталась нерешенной про числа на бумажках ))
>
> Как вам такой вариант?

Первый, прежде, чем сказать что-то, уже думает, что второй молчит, стало быть у второго уже не 1, а у первого не 2 еще до начала разговора )). Правда такая логика приводит к бесконечности ((

> А если так:
>
> У двух людей есть бумажки с написанными на них натуральными числами. Каждый знает только свое число, но знает, что число другого отличается на единицу. Диалог:
>
> — Я не знаю, какое у тебя число.
> —И я не знаю, какое у тебя число.
> —Тогда я знаю, какое у тебя число.
> —Тогда и я знаю, какое у тебя число.
>
> Какие числа у них на бумажках?

Камрад, уточни, пожалуйста, условие - первый должен начинать диалог по правилам задачи, или он уже сделал выводы из молчания второго до начала диалога?

> Камрад, уточни, пожалуйста, условие - первый должен начинать диалог по правилам задачи, или он уже сделал выводы из молчания второго до начала диалога?

Условие дано полностью.

Поскольку правильный ответ уже прозвучал, я лучше сразу напишу правильное решение.

Первый (П): — Я не знаю какое у тебя число (У первого число больше единицы, в противном случае он знал бы число второго)
Второй (В): — И я не знаю, какое у тебя число (У второго число больше единицы, в противном случае он знал бы число первого, т.о. для его числа существует два нат. числа, отличных на единицу)
П: — Тогда я знаю, какое у тебя число (для его числа существует только одно нат. число, отличное на единицу, для которого существует два нат. числа, отличных на единицу. Т.е. для другого числа существет только одно отличное на единицу нат. число. Нат. число, для которого существет только одно отличное на единицу нат. число — 1, и значит, число второго — 3, первого, соответственно — 2)
Пользуясь логикой ответа Первого, Второй узнает его число.

Все просто :)))

> Пост, пожалуй, удался! Через недельку еще запощу задачку ))

Респект )

>> Условие дано полностью.
>> Все просто :)))
>
> Со всем уважением ) Но.
>
> Если у первого 3, а у второго 4 - то тоже всё сходится.
> Дело в том, что второй (В), сообщая, что "не знает" - дополнительно "расписывается" в том, что у него и не 2.
>
> Обоснование - если бы у него было 2, то он, зная, что у П не 1, _знал_ бы, что у П - 3, ведь разница между числами единица.
>
> Так что, и П-2, В-3, правильный ответ - и П-3, В-4.

Во-во, я так же решил[censored]

> Ты просто подставь варианты ответа 3 и 4, и проверь. Если бы у Первого было 3, как бы он стал утверждать, что знает число Второго? Ведь и 4, и 2 (числа, отличные от 3 на единицу) имеют нат. числа, отличные на единицу от них. Значит, у Первого 2 варианта, и однозначного ответа он дать не может.
>
> Мне кажется так.

Аргументирую )
П: не знаю твоё число. (= у меня не 1, т.к. иначе я бы знал, что у тебя 2)
В: и я не знаю твоё число (= у меня не 1, т.к. иначе я бы знал, что у тебя 2. И! У меня не 2, т.к. если бы у меня было 2, то я бы сказал "знаю", потому что у первого не 1, а значит - 3

Как-то так.

> А про еврея я сразу почти угадал, у меня первый вопрос в голове который возник: "А это каг О_о? по одной трубе и один не запачкался"

[смотрит с уважением]

>> И! У меня не 2, т.к. если бы у меня было 2, то я бы сказал "знаю", потому что у первого не 1
>
> Ты доказал, почему у Первого не может быть 3. Верно. Только три-то не у Первого, а у Второго. У Первого — 2.

Тьфу ты. Так, еще раз :)

Ты доказал, почему у Второго не может быть 2. Так ведь никто не говрит, что у Второго — 2.

>> Какие же это аксакалы, если им понадобилось целых три дня для ответа?
>
> У меня тоже этот вопрос самым первым возник.

Если б я сформулировал задачу сухо, то пост привлек бы меньше внимания. Я ненадолго притворился маленьким троллем ))

>>> Какие же это аксакалы, если им понадобилось целых три дня для ответа?
>>
>> У меня тоже этот вопрос самым первым возник.
>
> Если б я сформулировал задачу сухо, то пост привлек бы меньше внимания. Я ненадолго притворился маленьким троллем ))

Настоящий аксакал не спешит, а всё взвесит перед ответом)

> Правильно. Так любое простое количество цветов можно кодировать, хоть 97.

Почему только простое? Этот принцип подходит вообще для любого числа цветов.

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

А все начиналось с безобидной задачки ))

Так, у меня вопрос. Я нихера не понял с вашим кодированием шапок в "секир-башке", объясните по каким ключевым словам гуглить)))

> Так, у меня вопрос. Я нихера не понял с вашим кодированием шапок в "секир-башке", объясните по каким ключевым словам гуглить)))

Объясняю популярно:

1) Если 100-й мудрец видит перед собой 50 чёрных шапок, а 99-й - 49, то из этой информации 99-й может сделать логичный вывод, что на нём чёрная шапка (или белая, если он тоже видит 50 чёрных шапок).

2) Но нам не обязательно знать точное число шапок, чтобы сделать правильный вывод. Достаточно знать чётность. То есть, 100-й видит чётное число шапок, а 99-й - нечётное --> на 99-м чёрная шапка. Именно эту чётность кодирует 100-й мудрец, который первым отвечает на вопрос палача. Например ответ "чёрный" означает, что он видит перед собой чётное число чёрных шапок (потому что созвучно и проще запомнить), а ответ "белый" означает, что он видит нечётное число чёрных шапок.

3) Теперь 99-й, посчитав число чёрных шапок перед собой и сопоставив с "кодом" 100-го, определяет цвет своей шапки. Далее 98-й, на основе кода и цвета шапки 99-го вычисляет свой цвет и называет его. И так далее вплоть до первого. Все правильно называют цвет своей шапки. Только 100-й, который называл не цвет своей шапки, а кодировал число чёрных шапок, может с вероятностью 50% погибнуть.

4) На практике конкретный мудрец реализует примерно такой алгоритм:
- Встаёт на своё место в колонне.
- Считает число чёрных шапок перед собой. Если оно чётное, то он держит в уме слово "чёрный", если нечётное - "белый"
- Если слышит сзади слово "белый", то он ничего не делает. Если слышит слово "чёрный", то меняет запомненное слово с чёрного на белое и наоборот.
- На вопрос палача отвечает то слово, которое держит сейчас в уме.
- Секир-башка Профит.

5) Строго математически, чётность/нечётность означает остаток от деления на 2. Чётное значит 0, начётное - 1. Таким образом используя остаток от деления на другие числа можно решать задачу для любого числа цветов шапок. Цвета шапок кодируются следующим образом:

2 цвета 0, 1
3 цвета 0, 1, 2
4 цвета 0, 1, 2, 3
и так далее.

Мудрец считает сумму цветов перед собой и делит на число цветов, остаток запоминает.
Например, для 4 шапок получает сумму 147, остаток которой от деления на 4 равен 3. А стоящий перед ним мудрец насчитал 145, остаток 1. Очевидно, что 3-1 = 147-145 = 2. Цвет шапки переднего мудреца номер 2, он говорит "цвет номер 2". Следующий мудрец насчитал 142, остаток 2. Его расчёт выглядит так: 3 (код) - 2 (цвет шапки сзади стоящего) - 2 (свой остаток) = -1 ==3, так как наша числовая шкала четырёхзначная 0 1 2 3 0 1 2 3 0 1 2 3, или другими словами тройка - остаток от деления -1 на 4. Значит на этом мудреце шапка "цвета номер 3". и так далее для любого числа мудрецов и цветов.

Ситуация с дураками и предателями разобрана выше. Не очень подробно, но, надеюсь, понятно.