вот задачка, которую я нашёл в ЖЖ пользователя knop.
(прямую ссылку не даю, т.к. там есть частичный ответ).
99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого. Все мудрецы должны одновременно сообщить (написать на бумажке) цвет своего колпака. Для какого наибольшего значения k можно гарантировать, что не менее k мудрецов могут сделать это правильно? (Разумеется, мудрецы могут заранее — до надевания колпаков — выработать совместно используемую стратегию.)
Здравствуйте, Smal, Вы писали: S>99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого. Все мудрецы должны одновременно сообщить (написать на бумажке) цвет своего колпака. Для какого наибольшего значения k можно гарантировать, что не менее k мудрецов могут сделать это правильно? (Разумеется, мудрецы могут заранее — до надевания колпаков — выработать совместно используемую стратегию.)
А почему так легко или я что-то не понял? 99 мудрецов из 99 (то есть 100%) смогут сделать это правильно. Если на остальных 49 колпаков первого цвета, то 50й первого цвета на отвечающем, если 50, то на отвечающем второй цвет. От количества мудрецов не зависит. Это нынче считается этюдом?
Всё, что нас не убивает, ещё горько об этом пожалеет.
Здравствуйте, Ромашка, Вы писали:
Р>Здравствуйте, Smal, Вы писали: S>>Для какого наибольшего значения k можно гарантировать, что не менее k мудрецов могут сделать это правильно?
Р>k=98, спасибо baily за ошибку в рассуждениях.
Здравствуйте, Smal, Вы писали:
S>Здравствуйте, baily, Вы писали:
S>Как понять кто первые 25? Они ведь не знают свой цвет и, значит, не могут отсчитать 25 мудрецов такого же цвета от начала.
Да, накосячил.
Вот верное решение. Ответ по прежнему — 74. То, что больше быть не может — ясно,
так как 49 мудрецов сразу знают свой цвет, а остальные 50 могут только гадать, поэтому гарантированно не могут получить больше половины в силу симметрии ситуации.
Алгоритм как получить верхнюю грань. Заметим, что такой алгоритм в силу симметрии, спасает всегда ровно 74 человека. Назовем неопределившимся мудрецом того, кто должен гадать в выборе цвета, то есть из тех 50-ти с одинаковым колпаком.
Такой мудрец видит перед собой по 49 человек каждого из цветов, для определенности черного и белого. Он выбирает двух "средних" — 25-го белого по счету и 25-го черного. Считать можно, например, по часовой стрелке. Цвет пишет тот, который оказался ему ближе. Тогда все 50 неопределившихся разобьются на пары и в каждой паре мудрецы выберут разный цвет. В самом деле, без огрнаничения общности, можно считать, что на них колпаки черного цвета. Тогда "средний" черный мудрец для одного будет очевидно "средним" черным для другого. Это и есть пара. При этом их выбор цвета будет противоположным, что тоже ясно ( если,например, первый мудрец в паре выбрал черный, значит, для него был ближе его "средний" черный. Но тогда для второго в паре до первого мудреца идти по другой части стола, где должно сидеть больше белых, то есть уму раньше встретится его "средний" белый. )
Здравствуйте, Smal, Вы писали:
B>>Рассмотрим некоторую раскраску s. Пусть раскраска r(s, i) получается из s сменой цвета колпака у мудреца M(i) на противоположный.
B>>Пусть D(s,i) равна B>>0 если M(i) не гадающий мудрец. B>>Иначе B>>1, если A(s, i) — правильный цвет колпака B>>-1 в противном случае.
B>>Ясно тогда, что B>>2) D(s,i) = — D(r(s,i),i)
S>Это не верно, т.к. если цвет i изменился, что он перестал быть гадающим S>мудрецом. Ведь изменилось соотношение кол-ва колпаков.
Нет, это верно. Если i-гадающий, то он не знает цвет своего колпака. Каков бы цвет на нем ни был, он останется гадающим.
От смены цвета его колпака перестанут быть гадающими другие мудрецы.
Доказательство было многословным, но суть его в двух вещах:
1)Каков бы ни был алгоритм A, он должен для любой раскраски s и мудреца i давать определенное значение
цвета колпака, которое должен выбирать мудрец i — A(s,i). Причем A(s,i) не должно зависеть от s(i) — то есть цвете колпака на i-м мудреце для раскраски i. Это просто определение того, что такое детерминированный алгоритм. Если у нас был бы вероятностный алгоритм, то в силу того, что по условию, мы должны были бы выбирать худший случай, когда погибло бы большинство мудрецов, то наш вероятностный алгоритм можно было бы заменить на детерминированный, на котором этот худший случай достигается.
2) Для фиксированного i, все раскраски, на которых он гадающий разбиваются на пары. В каждой паре лежат раскраски, которое отличаются только цветом колпака на i-м мудреце. Значение A(s,i) для каждой раскраски в паре одинаковы в силу 1, а вот участь мудреца различна. Т.е гадающий мудрец умирает столь же часто, как и выживает, каким бы алгоритмом мы бы не воспользовались.
Здравствуйте, Smal, Вы писали:
S>Здравствуйте, baily, Вы писали:
B>>Да, накосячил.
B>>Вот верное решение. Ответ по прежнему — 74. То, что больше быть не может — ясно, B>>так как 49 мудрецов сразу знают свой цвет, а остальные 50 могут только гадать, поэтому гарантированно не могут получить больше половины в силу симметрии ситуации.
S>Хотелось бы формальное доказательство. Аргумент про симметричность S>слишком общий и не ведёт напрямую к доказательству.
Пусть будет формально. Введем обозначения. s — некоторая раскраска мудрецов, удовлетворяющая условию задачи.
S — множество всех таких раскрасок. M(i) — мудрец с номером i = 1,..., 99 ( считаем, что у стола выбрано начало и порядок обхода ).
Пусть есть алгоритм A, дающий гарантированно выживать более чем половине из 50 гадающих мудрецов.
Это означает, что определена функция A(s, i), принимающая значение цвета колпака, который должен выбрать для себя мудрец M(i) на раскладке s.
Пусть L(s) разница между угадавшими и неугадавшими среди гадающих мудрецов. В силу определения A имеем
1) L(s) > 0
Рассмотрим некоторую раскраску s. Пусть раскраска r(s, i) получается из s сменой цвета колпака у мудреца M(i) на противоположный.
Пусть D(s,i) равна
0 если M(i) не гадающий мудрец.
Иначе
1, если A(s, i) — правильный цвет колпака
-1 в противном случае.
Ясно тогда, что
2) D(s,i) = — D(r(s,i),i)
3) s != r(s,i)
4) S разбивается на пары s, r(s,i)
Пусть D(i) = сумма D(s, i) по всем s. Из 2-4 следует тогда, что
5) D(i) = 0.
Пусть D = сумма D(i) по всем i. Тогда из 4 следует
6) D = 0
С другой стороны, меняя порядок суммирования в опредлении D получаем:
D = сумма по всем s сумм по всем i от D(s, i) = сумма по всем s L(s)
Из 1 следует
7) D > 0
Но 6 и 7 противоречат друг другу. Значит, такого A не существует.
B>>Алгоритм как получить верхнюю грань. Заметим, что такой алгоритм в силу симметрии, спасает всегда ровно 74 человека. Назовем неопределившимся мудрецом того, кто должен гадать в выборе цвета, то есть из тех 50-ти с одинаковым колпаком.
B>>Такой мудрец видит перед собой по 49 человек каждого из цветов, для определенности черного и белого. Он выбирает двух "средних" — 25-го белого по счету и 25-го черного. Считать можно, например, по часовой стрелке. Цвет пишет тот, который оказался ему ближе. Тогда все 50 неопределившихся разобьются на пары и в каждой паре мудрецы выберут разный цвет. В самом деле, без огрнаничения общности, можно считать, что на них колпаки черного цвета.
B>> Тогда "средний" "средним" черный мудрец для одного будет очевидно черным для другого. Это и есть пара.
S>Не смог понять этой фразы. Можете прояснить, как определяется пара?
Еще раз. При фиксированной раскраске s и i определим функцию B(s, i) как j если
мудрец M(j) имеет черный цвет и является средним черным мудрецом для i. То есть если между M(i) и M(j) сидят по обе стороны одинаковое количество мудрецов.
Аналогично определим функцию W(s,i) для среднего белого мудреца.
Алгоритм A зададим следующим образом: A(s,i) = Black если B(s, i) ближе к i чем W(s,i) если считать от i по часовой стрелке.
В противном случае A(s,i) = White.
Допустим, что цвет гадающих мудрецов черный. Если цвет белый, то рассуждения аналогичны.
Тогда ясно, что если мудрец M(i) гадающий, то B(s, B(s,i)) = i.
То есть черные мудрецы разобъются на пары по отношению эквивалентности В.
При этом имеем, что A(s,i) и A(s,B(s,i)) имеют разные значения.
Здравствуйте, meier13, Вы писали:
M>Выбираем главного мудреца, далее те мудрецы которые видят 49 на 49, считают сколько черных колпаков от главного до самого себя(по часовой стрелки) они видят, если это число четное называем черный, если нечетное белый, итого всегда ровно 74 мудреца ответят правильно.
не пройдет. Предположим, что будет 50 с белым колпаком, сидящих подряд, начиная от главного мудреца. Тогда все они выберут черный цвет и умрут
Здравствуйте, Smal, Вы писали:
S>Добрый день,
S>вот задачка, которую я нашёл в ЖЖ пользователя knop. S>(прямую ссылку не даю, т.к. там есть частичный ответ).
S>99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого. Все мудрецы должны одновременно сообщить (написать на бумажке) цвет своего колпака. Для какого наибольшего значения k можно гарантировать, что не менее k мудрецов могут сделать это правильно? (Разумеется, мудрецы могут заранее — до надевания колпаков — выработать совместно используемую стратегию.)
S>Александр.
Предполагаю, что, сидя за столом, сигналами обмениваться они не могут. Тогда 74 гарантированно могут выжить. 49 мудрецов знают цвет своенго колпака точно.Остальные 50 могут только гадать. Так как посадка за столом дает некоторое упорядочение, то им надо заранее договориться только, от какого мудреца вести отсчет и в каком направлении. Тогда 50 неопределившихся получат однозначный порядковый номер. Первые 25 пишут один цвет, остальные — другой.
Здравствуйте, Smal, Вы писали:
M>>Плюс не тебе, это я ответ Ромашки хотел оценить, но после логина промахнулся.
S>Оценить, что Ромашка не понял условия?
Оценить, что он с юмором отнёсся к неполному условию. В условии не сказано, что они не знают какого цвета 50, а какого 49 (впрочем, обратного тоже не сказано). Т.е. каждый додумывает условие как хочет.
Здравствуйте, monax, Вы писали:
M>Оценить, что он с юмором отнёсся к неполному условию. В условии не сказано, что они не знают какого цвета 50, а какого 49 (впрочем, обратного тоже не сказано). Т.е. каждый додумывает условие как хочет.
В условии всё корректно написано:
Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого.
Из этой фразы не следует даже, что они заранее знали какие это будут цвета.
А додумывать условие не нужно. Представьте, что я бы задачку по планиметрии задал, а Вы бы мне написали:
"В условии не сказано, что все треугольники не равносторонние (впрочем, обратного тоже не сказано). Т.е. каждый додумывает условие как хочет."
Здравствуйте, Centaur, Вы писали:
S>>>99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого. Р>>А почему так легко или я что-то не понял? 99 мудрецов из 99 (то есть 100%) смогут сделать это правильно. Если на остальных 49 колпаков первого цвета, то 50й первого цвета на отвечающем, если 50, то на отвечающем второй цвет. От количества мудрецов не зависит. Это нынче считается этюдом? C>Ты сидишь за круглым столом в компании 98 других мудрецов и видишь на них 49 белых колпаков и 49 чёрных.
Это если ты один из 50и, а если один из 49и, то отношение 50 к 48. Вся проблема лишь в том, чтобы ответить одновременно. Для этого, к примеру, те кто зняют что они не из 50и — должны поднять правую руку. Как только поднимут все 49, то те кто из 50 узнают что у них колпак другого цвета. Ну и чтобы быть готовым ответить всем, остальные из 50и должны поднять левую руку.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, Smal, Вы писали:
S>вот задачка, которую я нашёл в ЖЖ пользователя knop. S>(прямую ссылку не даю, т.к. там есть частичный ответ). S>99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого. Все мудрецы должны одновременно сообщить (написать на бумажке) цвет своего колпака. Для какого наибольшего значения k можно гарантировать, что не менее k мудрецов могут сделать это правильно? (Разумеется, мудрецы могут заранее — до надевания колпаков — выработать совместно используемую стратегию.)
У мудрецов глаза завязаны?
Если нет, то:
Если ты один из 50и, то ты видишь 49 к 49 мудрецов, а если один из 49и, то отношение 50 к 48. Вся проблема лишь в том, чтобы ответить одновременно. Для этого, к примеру, те кто знают, что они не из 50и — должны поднять правую руку. Как только поднимут все 49, то те кто из 50 узнают что у них колпак другого цвета. Ну и чтобы быть готовым ответить всем, остальные из 50и должны поднять левую руку.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, Smal, Вы писали:
S>Добрый день,
S>вот задачка, которую я нашёл в ЖЖ пользователя knop. S>(прямую ссылку не даю, т.к. там есть частичный ответ).
S>99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого. Все мудрецы должны одновременно сообщить (написать на бумажке) цвет своего колпака. Для какого наибольшего значения k можно гарантировать, что не менее k мудрецов могут сделать это правильно? (Разумеется, мудрецы могут заранее — до надевания колпаков — выработать совместно используемую стратегию.)
S>Александр.
Написать цвет колпака соседа справа и отдать ему свою бумажку
Ну, а если серьезно, то, например, договариваются так: каждый мудрец, который насчитал 50 колпаков одного цвета на своих соседях, пишет на бумажке ответ (понятно, что у него другой цвет). Тогда те, кто не может насчитать 50 колпаков одного цвета, пишут цвет, противоположный колпаку любого уже ответившего.
Здравствуйте, baily, Вы писали:
B>Предполагаю, что, сидя за столом, сигналами обмениваться они не могут. Тогда 74 гарантированно могут выжить. 49 мудрецов знают цвет своенго колпака точно.Остальные 50 могут только гадать. Так как посадка за столом дает некоторое упорядочение, то им надо заранее договориться только, от какого мудреца вести отсчет и в каком направлении. Тогда 50 неопределившихся получат однозначный порядковый номер. Первые 25 пишут один цвет, остальные — другой.
Как понять кто первые 25? Они ведь не знают свой цвет и, значит, не могут отсчитать 25 мудрецов такого же цвета от начала.
Здравствуйте, Mr.Delphist, Вы писали:
MD>Написать цвет колпака соседа справа и отдать ему свою бумажку
Да, это весёлое решение, но к сожалению они так сделать не могут.
MD>Ну, а если серьезно, то, например, договариваются так: каждый мудрец, который насчитал 50 колпаков одного цвета на своих соседях, пишет на бумажке ответ (понятно, что у него другой цвет). Тогда те, кто не может насчитать 50 колпаков одного цвета, пишут цвет, противоположный колпаку любого уже ответившего.
Они одновременно пишут на бумажке и не знают ответы других. Да и не понятно как понять кто угадывает свой цвет, а кто знает.
Здравствуйте, Smal, Вы писали:
S>Здравствуйте, Mr.Delphist, Вы писали:
MD>>Написать цвет колпака соседа справа и отдать ему свою бумажку
S>Да, это весёлое решение, но к сожалению они так сделать не могут.
MD>>Ну, а если серьезно, то, например, договариваются так: каждый мудрец, который насчитал 50 колпаков одного цвета на своих соседях, пишет на бумажке ответ (понятно, что у него другой цвет). Тогда те, кто не может насчитать 50 колпаков одного цвета, пишут цвет, противоположный колпаку любого уже ответившего.
S>Они одновременно пишут на бумажке и не знают ответы других. Да и не понятно как понять кто угадывает свой цвет, а кто знает.
Здравствуйте, Ромашка, Вы писали:
S>>99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого.
Р>А почему так легко или я что-то не понял? 99 мудрецов из 99 (то есть 100%) смогут сделать это правильно. Если на остальных 49 колпаков первого цвета, то 50й первого цвета на отвечающем, если 50, то на отвечающем второй цвет. От количества мудрецов не зависит. Это нынче считается этюдом?
Ты сидишь за круглым столом в компании 98 других мудрецов и видишь на них 49 белых колпаков и 49 чёрных.
Здравствуйте, Ромашка, Вы писали:
Р>Здравствуйте, Smal, Вы писали: S>>99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого. Все мудрецы должны одновременно сообщить (написать на бумажке) цвет своего колпака. Для какого наибольшего значения k можно гарантировать, что не менее k мудрецов могут сделать это правильно? (Разумеется, мудрецы могут заранее — до надевания колпаков — выработать совместно используемую стратегию.)
Р>А почему так легко или я что-то не понял? 99 мудрецов из 99 (то есть 100%) смогут сделать это правильно. Если на остальных 49 колпаков первого цвета, то 50й первого цвета на отвечающем, если 50, то на отвечающем второй цвет. От количества мудрецов не зависит. Это нынче считается этюдом?
Заранее неизвестно каких колпаков сколько. Т.е. может быть 50/49, а может быть 49/50. Можно считать, что и цвета колпаков заранее неизвестны.
Здравствуйте, monax, Вы писали:
M>Здравствуйте, Smal, Вы писали:
S>>вот задачка, которую я нашёл в ЖЖ пользователя knop. S>>(прямую ссылку не даю, т.к. там есть частичный ответ).
M>Плюс не тебе, это я ответ Ромашки хотел оценить, но после логина промахнулся.
Здравствуйте, Smal, Вы писали:
S>вот задачка, которую я нашёл в ЖЖ пользователя knop. S>(прямую ссылку не даю, т.к. там есть частичный ответ).
S>99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого. Все мудрецы должны одновременно сообщить (написать на бумажке) цвет своего колпака. Для какого наибольшего значения k можно гарантировать, что не менее k мудрецов могут сделать это правильно? (Разумеется, мудрецы могут заранее — до надевания колпаков — выработать совместно используемую стратегию.)
Я правильно понимаю, что им сначала надевают колпаки, а потом они рассаживаются. Или нет?
Здравствуйте, Smal, Вы писали:
S>99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого. Все мудрецы должны одновременно сообщить (написать на бумажке) цвет своего колпака. Для какого наибольшего значения k можно гарантировать, что не менее k мудрецов могут сделать это правильно? (Разумеется, мудрецы могут заранее — до надевания колпаков — выработать совместно используемую стратегию.)
Стратегия простая, те, кто видит 49/49 сдвигают колпак на затылок, а те, кто 49/50 на лоб (вариант — прищуривают левый/правый глаз). Тогда k=99
Если обмен информацией условиями задачи запрещен — k=49. Это те мудрецы которые видят 50 колпаков противоположного цвета и наверняка знают свой. У каждого из остальных 50 всего лишь шансы 50/50.
Здравствуйте, Ziaw, Вы писали:
Z>Здравствуйте, Smal, Вы писали:
Z>Стратегия простая, те, кто видит 49/49 сдвигают колпак на затылок, а те, кто 49/50 на лоб (вариант — прищуривают левый/правый глаз). Тогда k=99
Обмениваться информацией, конечно, нельзя.
Z>Если обмен информацией условиями задачи запрещен — k=49. Это те мудрецы которые видят 50 колпаков противоположного цвета и наверняка знают свой. У каждого из остальных 50 всего лишь шансы 50/50.
Z>В чем этюд-то? Логика прямолинейная.
Значит в худшем случае угадают 49?
Утверждается, что можно предложить стратегию, при которой гарантированно угадает больше, чем 49.
Здравствуйте, Vain, Вы писали:
V>Здравствуйте, Centaur, Вы писали:
S>>>>99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого. Р>>>А почему так легко или я что-то не понял? 99 мудрецов из 99 (то есть 100%) смогут сделать это правильно. Если на остальных 49 колпаков первого цвета, то 50й первого цвета на отвечающем, если 50, то на отвечающем второй цвет. От количества мудрецов не зависит. Это нынче считается этюдом? C>>Ты сидишь за круглым столом в компании 98 других мудрецов и видишь на них 49 белых колпаков и 49 чёрных. V>Это если ты один из 50и, а если один из 49и, то отношение 50 к 48. Вся проблема лишь в том, чтобы ответить одновременно. Для этого, к примеру, те кто зняют что они не из 50и — должны поднять правую руку. Как только поднимут все 49, то те кто из 50 узнают что у них колпак другого цвета. Ну и чтобы быть готовым ответить всем, остальные из 50и должны поднять левую руку.
Информацией после надевания колпаков обмениваться нельзя.
Это не указано явно в условиях, но без этого этюд — не этюд.
Здравствуйте, Vain, Вы писали:
V>Здравствуйте, Smal, Вы писали:
S>>вот задачка, которую я нашёл в ЖЖ пользователя knop. S>>(прямую ссылку не даю, т.к. там есть частичный ответ). S>>99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого. Все мудрецы должны одновременно сообщить (написать на бумажке) цвет своего колпака. Для какого наибольшего значения k можно гарантировать, что не менее k мудрецов могут сделать это правильно? (Разумеется, мудрецы могут заранее — до надевания колпаков — выработать совместно используемую стратегию.) V>У мудрецов глаза завязаны?
Нет.
V>Если нет, то: V>Если ты один из 50и, то ты видишь 49 к 49 мудрецов, а если один из 49и, то отношение 50 к 48. Вся проблема лишь в том, чтобы ответить одновременно. Для этого, к примеру, те кто знают, что они не из 50и — должны поднять правую руку. Как только поднимут все 49, то те кто из 50 узнают что у них колпак другого цвета. Ну и чтобы быть готовым ответить всем, остальные из 50и должны поднять левую руку.
Нельзя обмениваться информацией. Иначе всё очевидно.
Здравствуйте, baily, Вы писали:
B>Да, накосячил.
B>Вот верное решение. Ответ по прежнему — 74. То, что больше быть не может — ясно, B>так как 49 мудрецов сразу знают свой цвет, а остальные 50 могут только гадать, поэтому гарантированно не могут получить больше половины в силу симметрии ситуации.
Хотелось бы формальное доказательство. Аргумент про симметричность
слишком общий и не ведёт напрямую к доказательству.
B>Алгоритм как получить верхнюю грань. Заметим, что такой алгоритм в силу симметрии, спасает всегда ровно 74 человека. Назовем неопределившимся мудрецом того, кто должен гадать в выборе цвета, то есть из тех 50-ти с одинаковым колпаком.
B>Такой мудрец видит перед собой по 49 человек каждого из цветов, для определенности черного и белого. Он выбирает двух "средних" — 25-го белого по счету и 25-го черного. Считать можно, например, по часовой стрелке. Цвет пишет тот, который оказался ему ближе. Тогда все 50 неопределившихся разобьются на пары и в каждой паре мудрецы выберут разный цвет. В самом деле, без огрнаничения общности, можно считать, что на них колпаки черного цвета.
B> Тогда "средний" "средним" черный мудрец для одного будет очевидно черным для другого. Это и есть пара.
Не смог понять этой фразы. Можете прояснить, как определяется пара?
B> При этом их выбор цвета будет противоположным, что тоже ясно ( если,например, первый мудрец в паре выбрал черный, значит, для него был ближе его "средний" черный. Но тогда для второго в паре до первого мудреца идти по другой части стола, где должно сидеть больше белых, то есть уму раньше встретится его "средний" белый. )
Здравствуйте, Smal, Вы писали:
V>>Если нет, то: V>>Если ты один из 50и, то ты видишь 49 к 49 мудрецов, а если один из 49и, то отношение 50 к 48. Вся проблема лишь в том, чтобы ответить одновременно. Для этого, к примеру, те кто знают, что они не из 50и — должны поднять правую руку. Как только поднимут все 49, то те кто из 50 узнают что у них колпак другого цвета. Ну и чтобы быть готовым ответить всем, остальные из 50и должны поднять левую руку. S>Нельзя обмениваться информацией. Иначе всё очевидно.
Пропустил часть про бумажку. Тогда всё очевидно, 49 ошибиться не могут — они видят несимметрию и могут определить свой цвет, таким образом, остальные 50 — видят симметрию и свой цвет определить не могут. Следовательно, остается выбрать стратегию угадывания для остальных 50и. А вот тут хз, вроде 50 на 50 очевидно, но может есть ещё какие стратегии.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Выбираем главного мудреца, далее те мудрецы которые видят 49 на 49, считают сколько черных колпаков от главного до самого себя(по часовой стрелки) они видят, если это число четное называем черный, если нечетное белый, итого всегда ровно 74 мудреца ответят правильно.
Здравствуйте, Smal, Вы писали:
S>Хотелось бы формальное доказательство. Аргумент про симметричность S>слишком общий и не ведёт напрямую к доказательству.
Ну что? Последнее приведенное доказательство попонятней? Или расписать подробней?
Здравствуйте, Vain, Вы писали:
V>Здравствуйте, Smal, Вы писали:
V>>>Если нет, то: V>>>Если ты один из 50и, то ты видишь 49 к 49 мудрецов, а если один из 49и, то отношение 50 к 48. Вся проблема лишь в том, чтобы ответить одновременно. Для этого, к примеру, те кто знают, что они не из 50и — должны поднять правую руку. Как только поднимут все 49, то те кто из 50 узнают что у них колпак другого цвета. Ну и чтобы быть готовым ответить всем, остальные из 50и должны поднять левую руку. S>>Нельзя обмениваться информацией. Иначе всё очевидно. V>Пропустил часть про бумажку. Тогда всё очевидно, 49 ошибиться не могут — они видят несимметрию и могут определить свой цвет, таким образом, остальные 50 — видят симметрию и свой цвет определить не могут. Следовательно, остается выбрать стратегию угадывания для остальных 50и. А вот тут хз, вроде 50 на 50 очевидно, но может есть ещё какие стратегии.
Здравствуйте, baily, Вы писали:
B>Пусть будет формально. Введем обозначения. s — некоторая раскраска мудрецов, удовлетворяющая условию задачи. B>S — множество всех таких раскрасок. M(i) — мудрец с номером i = 1,..., 99 ( считаем, что у стола выбрано начало и порядок обхода ). B>Пусть есть алгоритм A, дающий гарантированно выживать более чем половине из 50 гадающих мудрецов.
B>Это означает, что определена функция A(s, i), принимающая значение цвета колпака, который должен выбрать для себя мудрец M(i) на раскладке s.
B>Пусть L(s) разница между угадавшими и неугадавшими среди гадающих мудрецов. В силу определения A имеем
B>1) L(s) > 0
B>Рассмотрим некоторую раскраску s. Пусть раскраска r(s, i) получается из s сменой цвета колпака у мудреца M(i) на противоположный.
B>Пусть D(s,i) равна B>0 если M(i) не гадающий мудрец. B>Иначе B>1, если A(s, i) — правильный цвет колпака B>-1 в противном случае.
B>Ясно тогда, что B>2) D(s,i) = — D(r(s,i),i)
Это не верно, т.к. если цвет i изменился, что он перестал быть гадающим
мудрецом. Ведь изменилось соотношение кол-ва колпаков.
Т.е. верно D(s,i) * D(r(s,i),i) = 0.
S>>Не смог понять этой фразы. Можете прояснить, как определяется пара?
B>Еще раз. При фиксированной раскраске s и i определим функцию B(s, i) как j если B>мудрец M(j) имеет черный цвет и является средним черным мудрецом для i. То есть если между M(i) и M(j) сидят по обе стороны одинаковое количество мудрецов. B>Аналогично определим функцию W(s,i) для среднего белого мудреца.
B>Алгоритм A зададим следующим образом: A(s,i) = Black если B(s, i) ближе к i чем W(s,i) если считать от i по часовой стрелке. B>В противном случае A(s,i) = White.
B>Допустим, что цвет гадающих мудрецов черный. Если цвет белый, то рассуждения аналогичны. B>Тогда ясно, что если мудрец M(i) гадающий, то B(s, B(s,i)) = i. B>То есть черные мудрецы разобъются на пары по отношению эквивалентности В.
До сюда всё понятно.
B>При этом имеем, что A(s,i) и A(s,B(s,i)) имеют разные значения.
Здравствуйте, baily, Вы писали:
B>>>Ясно тогда, что B>>>2) D(s,i) = — D(r(s,i),i)
S>>Это не верно, т.к. если цвет i изменился, что он перестал быть гадающим S>>мудрецом. Ведь изменилось соотношение кол-ва колпаков.
B>Нет, это верно. Если i-гадающий, то он не знает цвет своего колпака. Каков бы цвет на нем ни был, он останется гадающим. B>От смены цвета его колпака перестанут быть гадающими другие мудрецы.
А, чёрт =) Поспешил с выводами. Всё правильно. Поздравляю — Ваше решение полное.
С уважением, Александр
Re: Ещё одна задача о мудрецах
От:
Аноним
Дата:
18.07.12 06:25
Оценка:
Я думаю этот тот тип задач где надо начинать с малого. Если взять 3 мудреца, то ответ у меня получился 2. Надо называть цвет соседа справа или цвет соседа слева. Пока думаю как продолжить на 5. =)
