логические задачки, про дядек в колпаках Опции

[мисс_граффити]

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

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

итак.

1.
Три мудреца спорили, кто из них самый мудрый. Поймали прохожего и предложили рассудить их. Прохожий достал из кармана 3 черных и 2 белых колпака, предложил мудрецам закрыть глаза и надел на каждого черный колпак, а белые спрятал. Когда мудрецы открыли глаза, он сказал: "Кто из вас определит, какого цвета на нем колпак, тот и выиграл". Мудрецы долго думали, и наконец один ответил. Как он определил?

2.
Поймали кучу народа и решили расстрелять. Однако каждому дали шанс выжить: их поставили "паровозиком" (каждый видит стоящих перед ним, но не видит стоящих за ним) и надели на каждого белый или черный колпак. Кто угадывает цвет - остается жить. Отвечать начинают с последнего (который видит всех). Говорить можно только одно слово - "черный" или "белый".
Дядьки посовещались и разработали такую методику, что в худшем случае умирал один человек (последний), а в лучшем все оставались живы. Что они придумали?

[Michael_Rybak]

Спойлер (Показать/Скрыть)

кроме "нормального" решения второй задачи, я придумал еще такое: громкостью голоса сообщать следующему его цвет

[мисс_граффити]

Спойлер (Показать/Скрыть)

типа тихо - белый, громко - черный? не пойдет )))
а вообще обе решил?

уточнение к условию: человеки друг друга напрямую не слышат (но ответы и их результаты узнают).
то есть присвистывания, шепелявения, притопы-прихлопы и прочее не допустимы

[Rus1]

А нельзя ли во второй задачи ввести мораторий на смертную казнь - тогда вообще никого не расстреляют

[Michael_Rybak]

типа тихо - белый, громко - черный? smile.gif не пойдет smile.gif)))
а вообще обе решил?

Почему - не пойдет. Как раз жизненно

Да, обе. Первая - ужасно древняя вообще, так что я ее решил еще, наверное, классе в 6м. Вторую сравнительно недавно.


Сообщение отредактировано: Michael_Rybak - 26.10.2006 13:47

[Lapp]

Что касается первой задачи, то она бьет все рекорды популярности - нет возможности вспомнить, когда и где я слышал ее впервые, но раз в несколько месяцев она всплывает снова. Здесь, на Форуме, она тоже была (как минимум один раз). Это не делает ее менее интересной, конечно . В ней есть один очень тонкий момент, я бы с удовольствием обсудил его, когда появится решение. Сейчас же пока я не открывал скрытый текст, так как не хочу проспойлить себе вторую задачу случайно..

А вот вторую задачу я вижу впервые (или прочно забыл). Если честно, я в некотором ступоре. Сначала я подумал что-то типа громкости или тона (а точнее - скорость выдвания ответа: быстро отвечает - белый, долго думает - черный) но если верно это:

уточнение к условию: человеки друг друга напрямую не слышат (но ответы и их результаты узнают).
то есть присвистывания, шепелявения, притопы-прихлопы и прочее не допустимы

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

[мисс_граффити]

можно конечно и скрытый текст почитай - там решений пока нет.
про один бит и невозможность сообщить 2 цвета - абсолютно правильно.
первую я тоже видела давно, а вторая попалась совсем недавно. Точнее, мне ее дали на защиту лабы по ООП (говорю ж - у преподов с кафедры новое хобби - поиздеваться на Юлькой У всех спрашивали что-то вроде "чем динамическое наследование отличается от статического". ) Но разместила обе, хотелось их в паре. Потому что все, кто знает решение одной, пытаются по аналогии решать вторую

Сообщение отредактировано: мисс_граффити - 26.10.2006 12:39

[Lapp]

и скрытый текст почитай - там решений пока нет.

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

"чем динамическое наследование отличается от статического"

- это и есть наводящий вопросик? Хорошо, напряжем ыщо разок свою деревяшку. Но смею предположить, что все же тут без подвоха не обошлось..

[мисс_граффити]

нет, задача к ООП не имеет никакого отношения ))))
вообще.
чистая логика.

а на наводящий вопросик я собиралась отвечать, а не задавать....
Если давать подсказки... Да ты, в принципе, своим переходом от черного/белого к 1/0 (истине/лжи) наполовину решил задачу

[Malice]

Спойлер (Показать/Скрыть)

по 2-ой:
Будем считать, что речь идет о 1/0, а не о белый/черный, так проще.
Первый чел должен сообщить всем некую инфу, вычитая из которой ответы предыдущих можно получить нужный результат.
Учитывая, что сказать можно только 1 или 0, то он должен сказать сумму всех колпаков по модулю 2.
Следующий, тоже считает эту сумму вместе с ответами все предыущих ораторов, и получает свой цвет.
И так далее.
Пробуем:
Было так 10101100.
1. считает, кого видит (0+1+0+1+1+0+0), получает 1, говорит "1" (повезло )
2. Считает, кого видит (1+0+1+1+0+0) получает 1, 1+ предыдущий 1, говорит "0"
3. (0+1+1+0+0) получает 0, 0+0+1=1, говорит "1"
4. (1+1+0+0) получает 0, 0+1+0+1=0, говорит "0"
5. (1+0+0) получает 1, 1+0+1+0+1=1, говорит "1"
6. (0+0) получает 0, 0+1+0+1+0+1=1, говорит "1"
7. (0) получает 0, 0+1+1+0+1+0+1=0, говорит "0"
8. ксорит всех, 0+0+1+1+0+1+0+1=1, говорит "0"
Фух, все вроде..

[Lapp]

а на наводящий вопросик я собиралась отвечать, а не задавать....

Не привыкла ощущать ся в роли Профессора? Пора начинать..

Да ты, в принципе, своим переходом от черного/белого к 1/0 (истине/лжи) наполовину решил задачу

Ой ли?..

[Michael_Rybak]

Рыбак, нарочно запутываешь?

Есть немного

А наводящий вопрос: что знает второй с конца? И что может дать ему бит первого с конца, соответственно.

[Lapp]

Господа, перед скрытым текстом пишите, пожалуйста, что в нем. Ну, не полностью, конечно , а типа: решение 1-й задачи, или решение второй. И скрывать их лучше по отдельности..

Спойлер (Показать/Скрыть)

Вот, например, я осмеливаюсь предложить некий довольно weird вариант решения 2-й задачи..
Они придумали, что задний говорит цвет переднего (ну что тут еще придумаешь??). Но суть в том, что в условии есть информация, что способ сработал. Это означает (в сочетании со скзанным мной выше), что "куча народу" исчислялась двумя человеками
Угадал?..

Ой, клинн!..
все, понял. Наводящий вопрос Рыбака сработал

PS
предыдущий мой ответ - неверен

[мисс_граффити]

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

[Malice]

то есть твое решение - одно из возможных. существует еще несколько (чуть-чуть отличающихся).
сам догадаешься?

Спойлер (Показать/Скрыть)

Первый может считать не сумму по модулю 2, а считать, например, колво черных колпаков, если кол-во четно, то 0, иначе 1. Но суть та же и результаты в вычислениях тоже. Это имеешь в виду?

[мисс_граффити]

2Malice

Спойлер (Показать/Скрыть)

В общем, они могут использовать любую ф-цию 2 переменных, таблица истинности которой состоит из двух нулей и двух единиц

[Malice]

2мисс_граффити
Согласен
А вообще, когда-то давно я подписывался в фидо на эху ru.algorithm (вроде так), там тоже очень часто встречались интересные задачи. Жаль дома это умерло уже, может на работе осталось что-то. Хотя в инете где-то должно все сохраняться. Блин, или это ru.golovolomka..

Сообщение отредактировано: Malice - 26.10.2006 15:25