Добрый день,

вот задачка, которую я нашёл в ЖЖ пользователя knop.
(прямую ссылку не даю, т.к. там есть частичный ответ).

99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого. Все мудрецы должны одновременно сообщить (написать на бумажке) цвет своего колпака. Для какого наибольшего значения k можно гарантировать, что не менее k мудрецов могут сделать это правильно? (Разумеется, мудрецы могут заранее — до надевания колпаков — выработать совместно используемую стратегию.)

Александр.

Здравствуйте, Smal, Вы писали:

S>Добрый день,

S>вот задачка, которую я нашёл в ЖЖ пользователя knop.
S>(прямую ссылку не даю, т.к. там есть частичный ответ).

S>99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого. Все мудрецы должны одновременно сообщить (написать на бумажке) цвет своего колпака. Для какого наибольшего значения k можно гарантировать, что не менее k мудрецов могут сделать это правильно? (Разумеется, мудрецы могут заранее — до надевания колпаков — выработать совместно используемую стратегию.)

S>Александр.

Предполагаю, что, сидя за столом, сигналами обмениваться они не могут. Тогда 74 гарантированно могут выжить. 49 мудрецов знают цвет своенго колпака точно.Остальные 50 могут только гадать. Так как посадка за столом дает некоторое упорядочение, то им надо заранее договориться только, от какого мудреца вести отсчет и в каком направлении. Тогда 50 неопределившихся получат однозначный порядковый номер. Первые 25 пишут один цвет, остальные — другой.

Здравствуйте, 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>Они одновременно пишут на бумажке и не знают ответы других. Да и не понятно как понять кто угадывает свой цвет, а кто знает.

Ага, невнимательно прочитал условие:

должны одновременно сообщить

Здравствуйте, Mr.Delphist, Вы писали:

Ясно. Значит, решения в данном случае нет.

Здравствуйте, Smal, Вы писали:
S>99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого. Все мудрецы должны одновременно сообщить (написать на бумажке) цвет своего колпака. Для какого наибольшего значения k можно гарантировать, что не менее k мудрецов могут сделать это правильно? (Разумеется, мудрецы могут заранее — до надевания колпаков — выработать совместно используемую стратегию.)

А почему так легко или я что-то не понял? 99 мудрецов из 99 (то есть 100%) смогут сделать это правильно. Если на остальных 49 колпаков первого цвета, то 50й первого цвета на отвечающем, если 50, то на отвечающем второй цвет. От количества мудрецов не зависит. Это нынче считается этюдом?

Здравствуйте, Smal, Вы писали:

S>вот задачка, которую я нашёл в ЖЖ пользователя knop.
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, Вы писали:

M>>Плюс не тебе, это я ответ Ромашки хотел оценить, но после логина промахнулся.

S>Оценить, что Ромашка не понял условия?

Оценить, что он с юмором отнёсся к неполному условию. В условии не сказано, что они не знают какого цвета 50, а какого 49 (впрочем, обратного тоже не сказано). Т.е. каждый додумывает условие как хочет.

Здравствуйте, monax, Вы писали:

M>Оценить, что он с юмором отнёсся к неполному условию. В условии не сказано, что они не знают какого цвета 50, а какого 49 (впрочем, обратного тоже не сказано). Т.е. каждый додумывает условие как хочет.

В условии всё корректно написано:

Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого.

Из этой фразы не следует даже, что они заранее знали какие это будут цвета.

А додумывать условие не нужно. Представьте, что я бы задачку по планиметрии задал, а Вы бы мне написали:
"В условии не сказано, что все треугольники не равносторонние (впрочем, обратного тоже не сказано). Т.е. каждый додумывает условие как хочет."

Здравствуйте, Smal, Вы писали:

S>вот задачка, которую я нашёл в ЖЖ пользователя knop.
S>(прямую ссылку не даю, т.к. там есть частичный ответ).

S>99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого. Все мудрецы должны одновременно сообщить (написать на бумажке) цвет своего колпака. Для какого наибольшего значения k можно гарантировать, что не менее k мудрецов могут сделать это правильно? (Разумеется, мудрецы могут заранее — до надевания колпаков — выработать совместно используемую стратегию.)

Я правильно понимаю, что им сначала надевают колпаки, а потом они рассаживаются. Или нет?

Здравствуйте, B0FEE664, Вы писали:


BFE>Я правильно понимаю, что им сначала надевают колпаки, а потом они рассаживаются. Или нет?

Нет. Они сначала сели, а потом им надели колпаки.

Здравствуйте, Smal, Вы писали:

S>99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого. Все мудрецы должны одновременно сообщить (написать на бумажке) цвет своего колпака. Для какого наибольшего значения k можно гарантировать, что не менее k мудрецов могут сделать это правильно? (Разумеется, мудрецы могут заранее — до надевания колпаков — выработать совместно используемую стратегию.)

Стратегия простая, те, кто видит 49/49 сдвигают колпак на затылок, а те, кто 49/50 на лоб (вариант — прищуривают левый/правый глаз). Тогда k=99

Если обмен информацией условиями задачи запрещен — k=49. Это те мудрецы которые видят 50 колпаков противоположного цвета и наверняка знают свой. У каждого из остальных 50 всего лишь шансы 50/50.

В чем этюд-то? Логика прямолинейная.

Здравствуйте, Smal, Вы писали:

S>Здравствуйте, baily, Вы писали:

S>Как понять кто первые 25? Они ведь не знают свой цвет и, значит, не могут отсчитать 25 мудрецов такого же цвета от начала.

Да, накосячил.

Вот верное решение. Ответ по прежнему — 74. То, что больше быть не может — ясно,
так как 49 мудрецов сразу знают свой цвет, а остальные 50 могут только гадать, поэтому гарантированно не могут получить больше половины в силу симметрии ситуации.

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

Такой мудрец видит перед собой по 49 человек каждого из цветов, для определенности черного и белого. Он выбирает двух "средних" — 25-го белого по счету и 25-го черного. Считать можно, например, по часовой стрелке. Цвет пишет тот, который оказался ему ближе. Тогда все 50 неопределившихся разобьются на пары и в каждой паре мудрецы выберут разный цвет. В самом деле, без огрнаничения общности, можно считать, что на них колпаки черного цвета. Тогда "средний" черный мудрец для одного будет очевидно "средним" черным для другого. Это и есть пара. При этом их выбор цвета будет противоположным, что тоже ясно ( если,например, первый мудрец в паре выбрал черный, значит, для него был ближе его "средний" черный. Но тогда для второго в паре до первого мудреца идти по другой части стола, где должно сидеть больше белых, то есть уму раньше встретится его "средний" белый. )

Здравствуйте, Ziaw, Вы писали:

Z>Здравствуйте, Smal, Вы писали:

Z>Стратегия простая, те, кто видит 49/49 сдвигают колпак на затылок, а те, кто 49/50 на лоб (вариант — прищуривают левый/правый глаз). Тогда k=99

Обмениваться информацией, конечно, нельзя.

Z>Если обмен информацией условиями задачи запрещен — k=49. Это те мудрецы которые видят 50 колпаков противоположного цвета и наверняка знают свой. У каждого из остальных 50 всего лишь шансы 50/50.

Z>В чем этюд-то? Логика прямолинейная.

Значит в худшем случае угадают 49?
Утверждается, что можно предложить стратегию, при которой гарантированно угадает больше, чем 49.

Здравствуйте, Centaur, Вы писали:

S>>>99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным – другого.
Р>>А почему так легко или я что-то не понял? 99 мудрецов из 99 (то есть 100%) смогут сделать это правильно. Если на остальных 49 колпаков первого цвета, то 50й первого цвета на отвечающем, если 50, то на отвечающем второй цвет. От количества мудрецов не зависит. Это нынче считается этюдом?
C>Ты сидишь за круглым столом в компании 98 других мудрецов и видишь на них 49 белых колпаков и 49 чёрных.
Это если ты один из 50и, а если один из 49и, то отношение 50 к 48. Вся проблема лишь в том, чтобы ответить одновременно. Для этого, к примеру, те кто зняют что они не из 50и — должны поднять правую руку. Как только поднимут все 49, то те кто из 50 узнают что у них колпак другого цвета. Ну и чтобы быть готовым ответить всем, остальные из 50и должны поднять левую руку.