мозголомки

[х]

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

[НекрЫсь]

будем считать первым того гнома, который не видит ни одного другого гнома (то есть стоит к ним спиной), и последним того гнома, который видит всю сотню (то есть стоит последним). К которому первым подходит людоед?
_________________
Dum spiro - spero
Spero, ergo sum

[х]

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

[Эрик М. Кауфман]

Я правильно всё понял? Гномики стоят в затылок друг другу, гномоед подходит к последнему в колонне. Если тот отвечает неправильно, то гномоед его съедает и спрашивает следующего. Если тот отвечает правильно, то остается в живых и уходит, а гномоед всё равно спрашивает следующего, так?

А можно уточняющие вопросы?

1. Гномик, стоящий перед тем, которого спрашивают, слышит его ответ?
2. Гномик, стоящий последним, хорошо видит колпачки всех гномиков, стоящих впереди? Он может их сосчитать?
3. У гномиков была возможность заранее договориться?

Кажется, у меня есть теоретически интересная идея, позволяющая выжить в худшем случае 99 гномикам... Но она получается сложная в практическом исполнении — поэтому важны детали, о которых я спросил.
_________________
Конечно, я — засасывающая черная дыра хаоса... Но все-таки... я довольно классный!
(с) Хэнк Моуди

Если не встанешь на какую-либо сторону, то становишься врагом для всех.
(с) Раде Шербеджия

[НекрЫсь]

Кажется я улавливаю твою мысль.
_________________
Dum spiro - spero
Spero, ergo sum

[х]

[Эрик М. Кауфман]

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

Что-то я после "Смурфиков" как-то прям искренне запереживал об этих гномиках!
_________________
Конечно, я — засасывающая черная дыра хаоса... Но все-таки... я довольно классный!
(с) Хэнк Моуди

Если не встанешь на какую-либо сторону, то становишься врагом для всех.
(с) Раде Шербеджия

[Эрик М. Кауфман]

Вроде, всё получается!

Значит, так. Предположим, я — один из гномиков, стоящих в колонне (не первый и не последний). Мне жизненно необходимо узнать цвет своего колпачка. В данной ситуации для этой жизненно важной цели я могу опереться только на два источника информации: цвет и количество колпачков впередистоящих (которые я вижу) и цвет колпачка позадистоящего (про который я слышу). Учитывая условие, согласно которому колпачки надеты хаотично, этого явно мало. Есть еще очень полезный квант информации: цветов колпачков всего два. Стало быть, есть только два варианта: на мне может быть либо черный, либо красный колпачок. Как же мне найти способ ТОЧНО узнать, какой колпачок на мне? Причем так, чтобы этим же способом мог воспользоваться КАЖДЫЙ гномик, а не через одного — как получается в случае с вариантом, при котором каждый гномик называет цвет колпачка впередистоящего?

Итак, если я не намерен тупо стоять и надеяться на удачу (а я не намерен!), то мне нужно понять, как я могу воспользоваться имеющейся информацией для решения задачи. Еще раз расклад. Я вижу цвет и количество колпачков впереди стоящих — но это мне никак не поможет, так как колпачки, согласно условию, надеты хаотично. Цветов всего два — но это мне тоже никак не поможет, потому как по тому же самому условию на мне может быть как черный, так и красный колпачок. Значит, имеющейся изначально информации для спасения недостаточно. Но есть еще один момент: информация, которую я получу непосредственно перед тем, как сам окажусь перед необходимостью отвечать.

О чем это я? А вот о чем: перед тем как Гномоед подойдет непосредственно ко мне, я узнаю цвет колпачка гномика, который стоял позади, так как я услышу его ответ и, насколько я понял, узнаю результат. (Допустим, позадистоящий гномик отвечает: "Красный". Если он остается в живых, значит, на нем был красный колпачок. Если Гномоед его съедает, — насколько я понимаю, мне не потребуется оглядываться, чтобы это узнать, — значит, на нем был черный колпачок. И, соответственно, наоборот.) Вот теперь стоит задуматься: какой бы еще один дополнительный квант информации помог бы мне, исходя из имеющейся информации, узнать, какой колпачок на мне?

И вот что мне пришло в голову: сосчитав все колпачки какого-нибудь одного цвета, я мог бы точно узнать, черный я или красный, если бы... точно знал, сколько осталось колпачков какого-нибудь одного цвета! Причем интересно, что достаточно знать количество колпачков только одного цвета. Например, я точно знаю, что черных колпачков осталось, допустим, 51. Я пересчитываю черные колпачки: если их 50 — значит оставшийся 1 черный колпачок на мне! Если же их 51 — значит, на мне красный колпачок, так как цветов всего два. Как же найти возможность узнать, сколько осталось колпачков какого-нибудь одного цвета? Да еще и так, чтобы этим способом мог воспользоваться каждый гномик?!

Вчера я думал именно в эту сторону и пытался придумать код, которым гномики могли бы передавать по цепочке информацию о количестве колпачков одного цвета. Но подспудно уже вчера понимал, что всего двух имеющихся вариантов ответа — "черный" или "красный" — явно недостаточно для такого кода. А значит, передавать информацию о количестве, которое, к тому же, постоянно уменьшается, явно нереально.

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

И тогда возникла блестящая мысль воспользоваться цветными фишками из коробки "Наша игротека"! Вот ведь воистину — лучше один раз увидеть, чем сто раз представить... И что вы думаете? Как только я расставил в хаотичном порядке десяток колпачков двух цветов, как решение просто бросилось в глаза!!!

Оказывается, совсем необязательно знать ТОЧНОЕ КОЛИЧЕСТВО колпачков одного цвета! Достаточно знать — ЧЕТНОЕ оно или НЕЧЕТНОЕ! Допустим, я точно знаю, что количество черных колпачков — четное. Тогда я просто смотрю вперед: если я вижу четное количество черных колпачков — значит, на мне красный. Если нечетное — значит, на мне черный.

Теперь главный вопрос: может ли КАЖДЫЙ гномик в колонне, исходя из имеющейся вышеописанной информации, опираясь на услышанный ответ предыдущего гномика и его результат, определить четность/нечетность количества колпачков одного цвета?! ДА, черт побери, МОЖЕТ!!! Догадались, как? Правильно — для этого нужен еще один маленький квант информации: узнать изначальную четность/нечетность одного цвета — и следить, как она меняется в процессе ответов позадистоящих гномиков!

Последний вопрос: откуда же взять этот единственный, жизненно необходимый квант информации?! И вот тут-то на первый план и выходит героический ПЕРВЫЙ гномик — вернее, последний в колонне гномик, к которому Гномоед подходит ПЕРВЫМ! Ему, бедняге, неоткуда взять необходимый квант, так как с него начинается наша цепочка... Но он-то и станет тем героем, который даст необходимую информацию всем впереди стоящим гномикам! Важно только, чтобы гномики могли заранее договориться о том, какую именно информацию им даст первый спрашиваемый гномик — но, как я специально уточнил, таковая возможность у гномиков была. А поскольку гарантированно спасти гномика, первым отвечающего на вопрос Гномоеда, нет, он может только полагаться на удачу — его шансы 50/50. А значит, он вполне может дать остальным гномикам информацию о четности какого-либо одного цвета.

Что ж, окончательный план спасения таков. Гномики договорились заранее, что первый гномик, которого спросит Гномоед, прежде чем ответить, внимательно посмотрит вперед и подсчитает количество черных и красных колпачков. После этого он громко назовет тот цвет, количество которого ЧЕТНОЕ. Допустим, первый гномик называет ЧЕРНЫЙ цвет.

Теперь, независимо от того, съели первого гномика или нет, второй гномик пересчитывает черные колпачки впереди себя. Если он видит ЧЕТНОЕ количество — значит, на нем КРАСНЫЙ колпачок. Если НЕЧЕТНОЕ — значит, ЧЕРНЫЙ. Таким образом, второй гномик СПАСЕН!

Третьему гномику придется поднапрячься чуть-чуть посильнее. Итак, он запомнил, что количество черных колпачков было ЧЕТНОЕ. Теперь он внимательно следит за ответом второго гномика. Если второй гномик сказал "КРАСНЫЙ" — значит, количество черных колпачков осталось ЧЕТНЫМ, и тогда третий гномик смотрит вперед и рассуждает точно так же, как и второй. Если же второй сказал "ЧЕРНЫЙ" — значит, количество черных колпачков стало НЕЧЕТНЫМ, и в этом случае третий гномик, сосчитав количество черных колпачков впереди себя, рассуждает инверсионно второму: если он видит ЧЕТНОЕ количество — значит, на нем ЧЕРНЫЙ колпачок. Если НЕЧЕТНОЕ — значит, КРАСНЫЙ! Таким образом, гарантированно спасен и третий гномик!

Ну, а остальным гномикам остается только внимательно слушать ответы позадистоящих гномиков и следить за изменением четности/нечетности количества колпачков черного цвета — и рассуждать точно так же, как третий гномик... И ничего не перепутать!

Итак, как можно видеть, при данном решении задачи гарантированно будут спасены 99 гномиков. А если первый гномик родился в колпачке и ему повезет угадать свой цвет — то и все 100!

Да, как я и предполагал еще вчера, решение несколько сложновато для практического исполнения. Но с другой стороны, захочешь жить — научишься хорошо считать! Так что я верю в математические способности наших гномиков!
_________________
Конечно, я — засасывающая черная дыра хаоса... Но все-таки... я довольно классный!
(с) Хэнк Моуди

Если не встанешь на какую-либо сторону, то становишься врагом для всех.
(с) Раде Шербеджия

[х]

так всё ужасно в этом мире, но хоть гномики спасены!!!!!ура мурзилкам!!!

[НекрЫсь]

Блестяще! Вот что значит долгая практика на "Кучемале"!
И отличное изложение. Перельман-Маковецкий нервно курят в углу, братья Гарднеры аплодируют.
_________________
Dum spiro - spero
Spero, ergo sum

[Эрик М. Кауфман]

Спасибо на добром слове — знаю, что уж ты-то точно зря не похвалишь! А мое спасибо за практику не только "Куче мале" в "Мурзилке", но и "Ума палате" в "Пионере", и не помню как называвшимся страницам в "Календаре школьника", и "Психологическому практикуму" в "Науке и жизни", и книжке "Кентерберийские головоломки"!

Рад, что изложение тоже заслужило одобрение, — я боялся, что будет много и непонятно... Но старался, чтобы было "коротко и ясно"!

Которые Перельман с Маковецким, я понял, — вон они у меня на полочке, между прочим, рядышком стоят и нервно курят! А у Мартина Гарднера есть брат?! Урри Гарднер?!!
_________________
Конечно, я — засасывающая черная дыра хаоса... Но все-таки... я довольно классный!
(с) Хэнк Моуди

Если не встанешь на какую-либо сторону, то становишься врагом для всех.
(с) Раде Шербеджия

[НекрЫсь]

У него есть лучше... У него есть великий с моей точки зрения однофамилец!

Урри, как мы помним был как раз наоборот - братом, но не однофамильцем. Я тут посчитал объемы и взмок - три главы ХНБ это по объему чуть ли не пол-романа в современном издательском понимании. Эрго, целое произведение потянет на четыре тома...
_________________
Dum spiro - spero
Spero, ergo sum

[Эрик М. Кауфман]

А, черт побери, Эрл Стэнли? Ну конечно!

А ты собрался издавать "Хуже не будет"?! ВАУ!

P.S.: Чуть не забыл! Отдельное спасибо вот этим милым синим анти-на'ви, вдохновившим меня на миссию по спасению гномиков!

Некрысь, между прочим, второй слева — это ты!


_________________
Конечно, я — засасывающая черная дыра хаоса... Но все-таки... я довольно классный!
(с) Хэнк Моуди

Если не встанешь на какую-либо сторону, то становишься врагом для всех.
(с) Раде Шербеджия

[НекрЫсь]

Приятно познакомиться. В чем сходство, склад характера или неравнодушие к копытным?

Я его собрался хотя бы распечатать...

И это еще не считая владельцев особняка Гарднеров...
_________________
Dum spiro - spero
Spero, ergo sum

[НекрЫсь]

А вот про "Нашу игротеку" приятно было услышать. До сих пор храню, и не оставляю надежды освоить хасами-шоги. Мы тут за "Заколдованной" разговорились о воспитании детей, о том, что многие дети и в шестом классе в солдатики играют... а потом посмотрели обо что облокачиваемся и расхохотались...
_________________
Dum spiro - spero
Spero, ergo sum