Comments 25
А им не всё равно в каком кольце вычисления проводить ? Что Z_2, что Z_7 - какая разница ?
Они же мегамозги, им все равно. Но моя просьба - привести подробное решение
А какая нафиг разница ? То же самое что и там. Красный == 0, Оранжевый == 1, Желтый == 2, Зелёный == 3, Голубой == 4, Синий == 5, Фиолетовый == 6. Суммируешь всё колпаки перед тобой по модулю 7, запоминаешь, слушаешь всех остальных, как они число говорят - вычитаешь его из того что запомнил (опять-таки по модулю 7), когда до тебя дошла очередь - называешь (и надеешься на лучшее). Заметим что ошибка одного кномика "вышибает" из седла его самого (если он не последний - тут он наоборот иногда может спастись) и стоящего перед ним, после чего всё опять стабилизируется...
Вот уж чего-чего, а решение этой задачи если (знать решение предыдущей) - тривиально... В той ещё нужно подумать (необычно то что полгнома в среднем мы таки теряем: обычно в задачах с гномиками/заключёнными/etc выживают все), а здесь... чистая техника...
Вот уж чего-чего, а решение этой задачи если (знать решение предыдущей) - тривиально... В той ещё нужно подумать (необычно то что полгнома в среднем мы таки теряем: обычно в задачах с гномиками/заключёнными/etc выживают все), а здесь... чистая техника...
Дополнение. Называть нужно минус то, что запомнил. То есть Красный == 0, Оранжевый == 6, Жёлтый == 5, Зелёный == 4, Голубой == 3, Синий == 2, Фиолетовый == 1. Иначе на срастётся. В предыдущей задаче x==-x :-)
Что, собственно, обозначает что большая часть будет убита ибо называть-то им нужно цвет, а не минус цвет - то есть в первоначальном подсчёте нужно все цвета инвертировать, а не во время ответа. Мдаа... дьявол, как водится, в деталях... Если бы это была реальная задача - меня б уже съели...
Поэтому я и привел задачу, решение которой собственно на поверхности, так как известно решение ее более узкого аналога. Но хотел именно услышать полное и подробное решение.
То есть ты хочешь отловить людей, которые никогда не делают off-by-one-error и будут аккуратно расставлять все точки над ё. Ну может в этом и есть какой-то смысл. Я обычно оставляю такие вещи на тестовый прогон или тестовый запуск. Хотя, конечно, если тестовый запуск $1'000'000 стоит...
В общем в "Я умный" это как-то не вписывается. Скорее в "Я дотошный"...
В общем в "Я умный" это как-то не вписывается. Скорее в "Я дотошный"...
этот кое-кто даже потом не стал кому-то другому расписывать подробнее. ну да ладно.
propovednik, Вы подали нормальную идею:
делаем отдельный блог с названием, которое звучит примерно так: "Моему ребенку задали в школе (университете, ПТУ, я/с) задачку. Не можем решить. Помогите!". Жаль только кармы не хватает, а может и не жаль :) ну и в этот блог транслировать задачи с braingames.ru или из любого другого места и решать их сообща. хотя из предыдущего поста было понятно, что Вы вроде как решили задачу и вы только восхитились решением. Когда я решил эту задачу, мой восторг вообще не знал границ. :)
Вообще, не скрою, что кое-где я бы не отказался от обсуждения некотрых задач отсюда с каким-либо мегамозгом, среди множества слишком легких и известных, иногда есть экземпляры, достойные внимания. А кое-где я просто, скажем, не силен :(
З.Ы. вообще наметилась тенденция, однако... тот пост немножко минусонули, этот тоже... похоже, что спасение мегамозгов, совсем не глобальная задача, куда важнее померятся... э-э-э... кхм-м-м-м... браузерами :)))
propovednik, Вы подали нормальную идею:
делаем отдельный блог с названием, которое звучит примерно так: "Моему ребенку задали в школе (университете, ПТУ, я/с) задачку. Не можем решить. Помогите!". Жаль только кармы не хватает, а может и не жаль :) ну и в этот блог транслировать задачи с braingames.ru или из любого другого места и решать их сообща. хотя из предыдущего поста было понятно, что Вы вроде как решили задачу и вы только восхитились решением. Когда я решил эту задачу, мой восторг вообще не знал границ. :)
Вообще, не скрою, что кое-где я бы не отказался от обсуждения некотрых задач отсюда с каким-либо мегамозгом, среди множества слишком легких и известных, иногда есть экземпляры, достойные внимания. А кое-где я просто, скажем, не силен :(
З.Ы. вообще наметилась тенденция, однако... тот пост немножко минусонули, этот тоже... похоже, что спасение мегамозгов, совсем не глобальная задача, куда важнее померятся... э-э-э... кхм-м-м-м... браузерами :)))
Так я не понял. Можно сделать так, что бы был убит только один? Или для этого первый должен назвать число вместо цвета и быть убитым?
говорить цвет колпака впереди стоящего МегаМозга
Меня всегда смущала в подобных задачах линейность ожидаемого решения.
Похоже, эта и предыдущая задачи – осовремененные праправнучки вот этой:
Сидели три старца. И спорили, кто из них самый умный. Подошел человек, достал три белых и два черных колпака и сказал:
- Закройте глаза, сейчас я надену вам на голову колпаки, кто догадается какого цвета колпаки, тот и есть самый умный.
Старцы закрыли глаза, человек надел на их головы три белых колпака, а черные спрятал в сумку, и сказал, чтоб старцы открыли глаза. Они некоторое время смотрели друг на друга, а потом один из них изрёк:
- Цвет моего колпака белый!
Как он пришел к такому выводу?
Похоже, эта и предыдущая задачи – осовремененные праправнучки вот этой:
Сидели три старца. И спорили, кто из них самый умный. Подошел человек, достал три белых и два черных колпака и сказал:
- Закройте глаза, сейчас я надену вам на голову колпаки, кто догадается какого цвета колпаки, тот и есть самый умный.
Старцы закрыли глаза, человек надел на их головы три белых колпака, а черные спрятал в сумку, и сказал, чтоб старцы открыли глаза. Они некоторое время смотрели друг на друга, а потом один из них изрёк:
- Цвет моего колпака белый!
Как он пришел к такому выводу?
Нет, не совсем, да обе эти задачи про колпаки, это верно. Но суть их разная, и методы решения - тоже различные.
опять же не совсем понимаю, что именно Вас смущает в "прямолинейности ожидаемого решения"?
насколько мне помниться 95% задач школьного (да и не только) курса, как раз имеют то самое "прямолинейное решение"... разве нет? А остальные 5% - это олимпиадные, либо задачи на "автомат" на экзамене :)))
Однако прямолинейность решения, в данном случае, не делает задачу неинтересной.
да, кстати, я, честно говоря, не совсем понял, что Вы имеете ввиду под "прямолинейностью", то что задачу можно формализовать и превратить в чисто математическую задачу? Так вот в задаче про белые и черные колпаки, мой путь решения был отнюдь не прямолинейным, а к такому математической формализации я пришел уже только после того как решил задачу.
P.S. не пишу ответ на предложенную Вами задачу, потомучто хабра-propovednik уже делал мне однажды такое замечание. и как мы там говорили в детстве: кто знает - не отвечайте! :)
опять же не совсем понимаю, что именно Вас смущает в "прямолинейности ожидаемого решения"?
насколько мне помниться 95% задач школьного (да и не только) курса, как раз имеют то самое "прямолинейное решение"... разве нет? А остальные 5% - это олимпиадные, либо задачи на "автомат" на экзамене :)))
Однако прямолинейность решения, в данном случае, не делает задачу неинтересной.
да, кстати, я, честно говоря, не совсем понял, что Вы имеете ввиду под "прямолинейностью", то что задачу можно формализовать и превратить в чисто математическую задачу? Так вот в задаче про белые и черные колпаки, мой путь решения был отнюдь не прямолинейным, а к такому математической формализации я пришел уже только после того как решил задачу.
P.S. не пишу ответ на предложенную Вами задачу, потомучто хабра-propovednik уже делал мне однажды такое замечание. и как мы там говорили в детстве: кто знает - не отвечайте! :)
Еще одна вариация на тему (придумал час назад, сам пока не решил).
Подлые оккупанты разошлись не на шутку, и поэтому они решили усложнить задачу, они взяли бесконечность (счетное множество) МегаМозгов , поставили их в колонну друг за другом, так, что каждый предыдущий видит всех последующих. На на этот раз они поняли, что смысла в разных цветах нет и взяли колпаки двух цветов (черного и белого), надели их на МегаМозгов, так, что каждый МегаМозг не видит свой колпак. Начиная с самого последнего (того, который видит всех кроме себя) у каждого МегаМозга по очереди спрашивают цвет его шляпы, если он ошибается, его убивают. Но как всегда МегаМозги заранее договорились, как минимизировать число убитых. О чем договорились МегаМозги?
Вопрос: можно ли обойтись одним убитым, т.е. существует ли стратегия, при которой каждый мозг кроме первого при его очереди сможет правильно назвать цвет своего колпака? (что, очевидно, эквиваленто, можно ли обойтись конечным числом жертв).
Соответственно, привести пример стратегии или доказать невозможность оной.
Подлые оккупанты разошлись не на шутку, и поэтому они решили усложнить задачу, они взяли бесконечность (счетное множество) МегаМозгов , поставили их в колонну друг за другом, так, что каждый предыдущий видит всех последующих. На на этот раз они поняли, что смысла в разных цветах нет и взяли колпаки двух цветов (черного и белого), надели их на МегаМозгов, так, что каждый МегаМозг не видит свой колпак. Начиная с самого последнего (того, который видит всех кроме себя) у каждого МегаМозга по очереди спрашивают цвет его шляпы, если он ошибается, его убивают. Но как всегда МегаМозги заранее договорились, как минимизировать число убитых. О чем договорились МегаМозги?
Вопрос: можно ли обойтись одним убитым, т.е. существует ли стратегия, при которой каждый мозг кроме первого при его очереди сможет правильно назвать цвет своего колпака? (что, очевидно, эквиваленто, можно ли обойтись конечным числом жертв).
Соответственно, привести пример стратегии или доказать невозможность оной.
Кстати, интересно, надо будет подумать, единственные нюансы:
ВСЕХ он точно не увидит, их же бесконечно... правильней сказать "он может увидеть каждого".
либо ограничить видимость N штуками вперед.
то что множество счетное это и так понятно :)
"(что, очевидно, эквивалентно, можно ли обойтись конечным числом жертв)" уж если конечным можно обойтись, то и одним тоже, это почти наверняка.
ВСЕХ он точно не увидит, их же бесконечно... правильней сказать "он может увидеть каждого".
либо ограничить видимость N штуками вперед.
то что множество счетное это и так понятно :)
"(что, очевидно, эквивалентно, можно ли обойтись конечным числом жертв)" уж если конечным можно обойтись, то и одним тоже, это почти наверняка.
На счет счетности пояснил на всяк. случай :)
Не, если ограничить видимость N штуками, то очевидно, что не обойтись без бесконечного жертв (первый тогда может в своем послании содержать лишь информацию о конечном числе игроков, а каждый следующий не может давать доп. информацию т.к. должен уже называть лишь свою шляпу), подразумевается именно бесконечная видимость. Поэтому вопрос по сути может ли послание первого содержать информацию о бесконечности впереди него (по другому: существует ли функция от бесконечной последовательности 0 и 1 в множество (0,1), которая при смене любой цифры в последовательности меняет свое значение).
Не, если ограничить видимость N штуками, то очевидно, что не обойтись без бесконечного жертв (первый тогда может в своем послании содержать лишь информацию о конечном числе игроков, а каждый следующий не может давать доп. информацию т.к. должен уже называть лишь свою шляпу), подразумевается именно бесконечная видимость. Поэтому вопрос по сути может ли послание первого содержать информацию о бесконечности впереди него (по другому: существует ли функция от бесконечной последовательности 0 и 1 в множество (0,1), которая при смене любой цифры в последовательности меняет свое значение).
я вот тут что подумал... Можно представить всех ММ, точнее их колпаки, в виде бесконечно десятичной дроби, типа 0,101010111011000110010.......
тогда два варианта:
1. число будет рациональным
2. иррациональным
в первом случае это означает, что таки с какого-то момента появится период. тогда можно попробовать как-то передать последующим информацию об этом. Если получится, то тогда мы обойдемся конечным числом жертв.
во втором случае, если число иррациональное, скорее всего не получится обойтись конечным числом жертв.
хотя например число 0,101001000100001000001.... иррациональное, но в нем прослеживается закономерность, и её тоже можно как-то передать. но получается уже не общее решение, а куча мелких частных решений.
тогда два варианта:
1. число будет рациональным
2. иррациональным
в первом случае это означает, что таки с какого-то момента появится период. тогда можно попробовать как-то передать последующим информацию об этом. Если получится, то тогда мы обойдемся конечным числом жертв.
во втором случае, если число иррациональное, скорее всего не получится обойтись конечным числом жертв.
хотя например число 0,101001000100001000001.... иррациональное, но в нем прослеживается закономерность, и её тоже можно как-то передать. но получается уже не общее решение, а куча мелких частных решений.
ну и потом... если количество умерщвляемых ММ будет таки бесконечно, то умрет и спасется их одинаковое число... а это уже не по мегамозговски... Это уже задачи для Гигамозгов, или даже Терамозгов :)
и еще, первому, для того чтобы проанализировать бесконечную последовательность, понадобиться бесконечное число времени, кроме некоторых вырожденных случаев...
поэтому он будет бесконечно долго тупить и умрет своей смертью :), или от голода :). Соответственно право тупить перейдет к следующему ММ.
Кстати, не отвечать на вопрос - это тоже способ передать информацию. только поможет ли это как то?
поэтому он будет бесконечно долго тупить и умрет своей смертью :), или от голода :). Соответственно право тупить перейдет к следующему ММ.
Кстати, не отвечать на вопрос - это тоже способ передать информацию. только поможет ли это как то?
Позвольте! Наши МегаМозги принмают решения мгновенно и обладают бесконечной памятью. Относительно рациональной - не сильно помогает, т.к. вероятность рациональной дроби = 0 (хотя тоже пытался найти какое-нить красивое решение через представление в виде числа). Вопрос именно в том, можно ли так все сорганизовать, чтобы умер все тот же незадачливый первый гипермозг, но его послания хватило всем последующим. Не отвечать на вопрос - это все равно, что третий цвет колпака, здесь как собаке 5й нос.
Относительно 1го коммента - думал где-то позожим образом: разбить все последовательности на классы, отличающиеся конечным числом разрядов, в каждом классе задать значение на угад для одной последовательности, а для других значения посчитать на основе четности (если отличается на четную сумму цифр, то то же число). Таким образом, каждый мегамозг, зная всю последовательность кроме него сможет сказать, 0 он или 1 (т.к. значения послания 1го в этих случаях отличаются). Правда проблема в том, что пока не придумал, что это за классы и действительно ли такое разбиение возможно.
Относительно 1го коммента - думал где-то позожим образом: разбить все последовательности на классы, отличающиеся конечным числом разрядов, в каждом классе задать значение на угад для одной последовательности, а для других значения посчитать на основе четности (если отличается на четную сумму цифр, то то же число). Таким образом, каждый мегамозг, зная всю последовательность кроме него сможет сказать, 0 он или 1 (т.к. значения послания 1го в этих случаях отличаются). Правда проблема в том, что пока не придумал, что это за классы и действительно ли такое разбиение возможно.
Простите, а почему бы каждому МегаМозгу не назвать цвет колпака, одетого на стоящего перед ним? Они же в линеечку выстроены, верно? Тогда вероятность смерти первого будет 1/количество цветов, а каждого последующего — 0. Видимо, я неверно понимаю условия, или невнимательно читаю комментарии… Мне это кажется оптимальным вариантом — мы же не знаем, что колпаков поровну всех цветов использовано, их и не может быть поровну, если число людей не делится нацело числом цветов.
Правда есть ещё один вариант, основанный на предположении, что колпаки одеваются не произвольным образом, а каким-то одним человеком, который заранее видит все колпаки. Тогда он внесёт некоторую предопределённость в расположение цветов, и оно отклонится от статистически случайного. Конечно, наш МегаМозг даже под дулом (уж чего там на него направлено) сможет проанализировать созданные детскими проблемами разводящего последовательности цветов и увеличить свои шансы на выживание. Но тогда нужно заранее условиться о том, как первый предупредит следующего.
Правда есть ещё один вариант, основанный на предположении, что колпаки одеваются не произвольным образом, а каким-то одним человеком, который заранее видит все колпаки. Тогда он внесёт некоторую предопределённость в расположение цветов, и оно отклонится от статистически случайного. Конечно, наш МегаМозг даже под дулом (уж чего там на него направлено) сможет проанализировать созданные детскими проблемами разводящего последовательности цветов и увеличить свои шансы на выживание. Но тогда нужно заранее условиться о том, как первый предупредит следующего.
Sign up to leave a comment.
Продолжаем решать «простые» задачи