Задачу придумал сам - навеяло. Является по сути компиляцией нескольких задач
У Шаха М мудрецов и он решил узнать насколько они умны.
Он собрал их и показал им образцы колпаков К разных цветов (К<М).
Он сказал что каждому мудрецу будет надет колпак с одним из этих К цветов, каждый мудрец будет видеть колпаки других.
Будут использованы все цвета.
Все мудрецы будут сидеть в одном зале и смотреть друг на друга. Ни говорить, ни жестикулировать нельзя.
Те, из мудрецов, которые готовы назвать свой цвет, могут молча выйти из Зала и назвать свои цвета Шахине, которая зафиксирует ответ. А Шах будет сидеть в зале и засечёт время по Главным часам шахства, которые тоже в зале и видны всем.
Часы - обычные цифровые часы с часами и минутами.
Мудрецам предлагается посовещаться между собой некоторое время, после чего процедура начнётся и пойдёт отсчёт времени.
Смогут ли мудрецы определить цвет своего колпака?
Соображают они очень и очень быстро.
zhekas
Гений-Говорун
 Offline
Сообщений: 1035
СПАСИБО
-вы поблагодарили: 34
-вас поблагодарили: 487
|
 |
� Ответ #15 : Июль 16, 2013, 17:10:10 � |
|
Подумайте ещё Допустим, что Шах надел на них 20 синих колпаков, 50 красных, а остальные цвета - ещё в большем количестве . То есть, меньше всего синих колпаков, затем - красных и т,д. В рамках данного алгоритма сократить время (дискретное время) невозможно. |
|
|
|
|
Записан
|
|
|
|
zhekas
Гений-Говорун
Offline
Сообщений: 1035
СПАСИБО
-вы поблагодарили: 34
-вас поблагодарили: 487
|
|
� Ответ #16 : Июль 16, 2013, 17:33:11 � |
|
Подумайте ещё Допустим, что Шах надел на них 20 синих колпаков, 50 красных, а остальные цвета - ещё в большем количестве . То есть, меньше всего синих колпаков, затем - красных и т,д. В рамках данного алгоритма сократить время (дискретное время) невозможно. И вот почему. Они могут начать с большего времени (например с 15-ой минуты), если: а) Уверены, что меньшего количества колпаков (чем 15) одного цвета нет б) Уверены, что остальные уверены в этом. С а) проблем не возникнет. Тепер по пункту б) 1) мудрец насчитал 19 синих 50 красных и т.д. он уверен, что меньше 19 колпаков одного цвета нет. Он вполне предполагает, что всвете его подсчета кто-то (назовём его второй мудрец) насчитает 18 синих (один из этих 19). 2) Соответственно этот второй мудрец вполне может предположить, что кто-то (третий мудрец) насчитает 17 синих. 3) Соответственно этот третий мудрец вполне может предположить, что кто-то (четверты мудрец) насчитает 16 синих. и т.д. по нисходящей. |
|
|
|
|
Записан
|
|
|
|
Tim
Гений-Говорун
Offline
Сообщений: 1079
СПАСИБО
-вы поблагодарили: 128
-вас поблагодарили: 1148
|
|
� Ответ #17 : Июль 16, 2013, 17:33:30 � |
|
Может чего недопонимаю, а как при 20 красных и 20 синих, выберут красный и синий. И красный и синий видит по 19 колпаков. Прошло 19 минут. И что?
|
|
|
|
|
Записан
|
|
|
|
zhekas
Гений-Говорун
Offline
Сообщений: 1035
СПАСИБО
-вы поблагодарили: 34
-вас поблагодарили: 487
|
|
� Ответ #18 : Июль 16, 2013, 17:38:17 � |
|
Может чего недопонимаю, а как при 20 красных и 20 синих, выберут красный и синий. И красный и синий видит по 19 колпаков. Прошло 19 минут. И что?
Синий видит 19 синих и 20 красных. Поэтому на 20-й минуте он выйдет зная, что он синий Аналогично красный |
|
|
|
|
Записан
|
|
|
|
Tim
Гений-Говорун
Offline
Сообщений: 1079
СПАСИБО
-вы поблагодарили: 128
-вас поблагодарили: 1148
|
|
� Ответ #19 : Июль 16, 2013, 17:40:28 � |
|
Да, понял, вопрос снимается
|
|
|
|
|
Записан
|
|
|
|
Tim
Гений-Говорун
Offline
Сообщений: 1079
СПАСИБО
-вы поблагодарили: 128
-вас поблагодарили: 1148
|
|
� Ответ #20 : Июль 16, 2013, 17:45:46 � |
|
Подумайте ещё Допустим, что Шах надел на них 20 синих колпаков, 50 красных, а остальные цвета - ещё в большем количестве . То есть, меньше всего синих колпаков, затем - красных и т,д. В рамках данного алгоритма сократить время (дискретное время) невозможно. И вот почему. Они могут начать с большего времени (например с 15-ой минуты), если: а) Уверены, что меньшего количества колпаков (чем 15) одного цвета нет б) Уверены, что остальные уверены в этом. С а) проблем не возникнет. Тепер по пункту б) 1) мудрец насчитал 19 синих 50 красных и т.д. он уверен, что меньше 19 колпаков одного цвета нет. Он вполне предполагает, что всвете его подсчета кто-то (назовём его второй мудрец) насчитает 18 синих (один из этих 19). 2) Соответственно этот второй мудрец вполне может предположить, что кто-то (третий мудрец) насчитает 17 синих. 3) Соответственно этот третий мудрец вполне может предположить, что кто-то (четверты мудрец) насчитает 16 синих. и т.д. по нисходящей. А вы не усложняете? меньше 18 как могут насчитать? |
|
|
|
|
Записан
|
|
|
|
zhekas
Гений-Говорун
Offline
Сообщений: 1035
СПАСИБО
-вы поблагодарили: 34
-вас поблагодарили: 487
|
|
� Ответ #21 : Июль 16, 2013, 17:58:43 � |
|
Подумайте ещё Допустим, что Шах надел на них 20 синих колпаков, 50 красных, а остальные цвета - ещё в большем количестве . То есть, меньше всего синих колпаков, затем - красных и т,д. В рамках данного алгоритма сократить время (дискретное время) невозможно. И вот почему. Они могут начать с большего времени (например с 15-ой минуты), если: а) Уверены, что меньшего количества колпаков (чем 15) одного цвета нет б) Уверены, что остальные уверены в этом. С а) проблем не возникнет. Тепер по пункту б) 1) мудрец насчитал 19 синих 50 красных и т.д. он уверен, что меньше 19 колпаков одного цвета нет. Он вполне предполагает, что всвете его подсчета кто-то (назовём его второй мудрец) насчитает 18 синих (один из этих 19). 2) Соответственно этот второй мудрец вполне может предположить, что кто-то (третий мудрец) насчитает 17 синих. 3) Соответственно этот третий мудрец вполне может предположить, что кто-то (четверты мудрец) насчитает 16 синих. и т.д. по нисходящей. А вы не усложняете? меньше 18 как могут насчитать? Ещё раз Первый насчитал 19. Он вправе считать что ситуация когда кто-то насчитал 18 вполне реальна. А если она реальна. То почему, тот, кто предположительно насчитал 18 не вправе предположить, что кто-то из 18 насчитал 17? |
|
|
|
|
Записан
|
|
|
|
Tim
Гений-Говорун
Offline
Сообщений: 1079
СПАСИБО
-вы поблагодарили: 128
-вас поблагодарили: 1148
|
|
� Ответ #22 : Июль 16, 2013, 18:12:23 � |
|
Все сидят в одном зале и видят всех, кроме себя. Минимум, которые видит любой синий 19. Он не знает своего колпака в начальный момент времени и может предположить, что любой из синих оценит нижнюю границу в 18. Но почему, кто-то из синих должен оценить ее в 17, если видит перед собой минимум 19 колпаков?
|
|
|
|
|
Записан
|
|
|
|
zhekas
Гений-Говорун
Offline
Сообщений: 1035
СПАСИБО
-вы поблагодарили: 34
-вас поблагодарили: 487
|
|
� Ответ #23 : Июль 16, 2013, 18:18:26 � |
|
Но почему, кто-то из синих должен оценить ее в 17, если видит перед собой минимум 19 колпаков?
Потому что, с точки зрения того самого "первого мудреца" необязательно что все видят 19 колпаков. О семнадцати думает предполагаемый первым мудрецом второй мудрец, который насчитал 18 |
|
|
|
|
Записан
|
|
|
|
zhekas
Гений-Говорун
Offline
Сообщений: 1035
СПАСИБО
-вы поблагодарили: 34
-вас поблагодарили: 487
|
|
� Ответ #24 : Июль 16, 2013, 18:21:56 � |
|
Минимум, которые видит любой синий 19.
Это откуда знать "первому мудрецу" |
|
|
|
|
Записан
|
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #25 : Июль 16, 2013, 20:58:21 � |
|
Подумайте ещё Допустим, что Шах надел на них 20 синих колпаков, 50 красных, а остальные цвета - ещё в большем количестве . То есть, меньше всего синих колпаков, затем - красных и т,д. В рамках данного алгоритма сократить время (дискретное время) невозможно. В рамках данного - невозможно. Но у Вас ведь светлая голова, zhekas, мне до неё - далеко (это не комплимент). Постарайтесь выйти за рамки данного алгоритма. Задача имхо, становится очень интересной. |
|
|
|
|
Записан
|
|
|
|
Питер Пен
Свой человек
Offline
Сообщений: 335
СПАСИБО
-вы поблагодарили: 92
-вас поблагодарили: 117
|
|
� Ответ #26 : Июль 17, 2013, 00:43:09 � |
|
«Синие» могут помочь другим. Допустим, если «синие» поняли, что они синие, то они могут сидеть еще лишнюю минуту, чтобы дать понять «красным», что их четное число. Тогда «красные» могут выйти уже и на следующей минуте после «синих». Но если следующих за «красными» тоже четное число, то «красные» сидят не 1 мин. после синих, а 2 мин.
|
|
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #27 : Июль 17, 2013, 01:27:55 � |
|
Или, например, договориться выходить в начале минуты или в конце Тепло Подумайте, что ещё можно сделать, играя на чётности |
|
|
|
|
Записан
|
|
|
|
zhekas
Гений-Говорун
Offline
Сообщений: 1035
СПАСИБО
-вы поблагодарили: 34
-вас поблагодарили: 487
|
|
� Ответ #28 : Июль 17, 2013, 11:19:14 � |
|
Или, например, договориться выходить в начале минуты или в конце Тогда каждая следующая группа мудрецов с наименьшим (на данный момент) колпаков будет выходить на следующей минуте после предыдущей. только "синие" будут ждать всё свое вермя (20 мин). |
|
|
|
|
Записан
|
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #29 : Июль 17, 2013, 14:00:06 � |
|
Или, например, договориться выходить в начале минуты или в конце Тогда каждая следующая группа мудрецов с наименьшим (на данный момент) колпаков будет выходить на следующей минуте после предыдущей. только "синие" будут ждать всё свое вермя (20 мин). Да Но я вижу ещё один вариант  Этот вариант хорошо работает, когда много мудрецов и мало цветов. Но сама фишка - не в этом варианте (он - принципиально другой), а в том обсуждении, которое я предвижу после того, как этот вариант будет назван. Повторяю: вариант с трюком Могу дать наводку, если захотите. |
|
|
|
|
Записан
|
|
|
|
|
