Страниц: 1 ... 3 4 [5]
  Печать  
Автор Тема: Ещё раз о мудрецах  (Прочитано 26225 раз)
0 Пользователей и 1 Гость смотрят эту тему.

Задачу придумал сам - навеяло. Является по сути компиляцией нескольких задач Smiley
У Шаха М мудрецов и он решил узнать насколько они умны.
Он собрал их и показал им образцы колпаков К разных цветов (К<М).
Он сказал что каждому мудрецу будет надет колпак с одним из этих К цветов, каждый мудрец будет видеть колпаки других.
Будут использованы все цвета.
Все мудрецы будут сидеть в одном зале и смотреть друг на друга. Ни говорить, ни жестикулировать нельзя.
Те, из мудрецов, которые готовы назвать свой цвет, могут молча выйти из Зала и назвать свои цвета Шахине, которая зафиксирует ответ. А Шах будет сидеть в зале и засечёт время по Главным часам шахства, которые тоже в зале и видны всем.
Часы - обычные цифровые часы с часами и минутами.
Мудрецам предлагается посовещаться между собой некоторое время, после чего процедура начнётся и пойдёт отсчёт времени.
Смогут ли мудрецы определить цвет своего колпака?
Соображают они очень и очень быстро.

Лев
Из мудрейших мудрейший
*****
Offline Offline

Сообщений: 2906

СПАСИБО
-вы поблагодарили: 1229
-вас поблагодарили: 1166


Искренне Ваш...


Просмотр профиля Email
Ответ #60 : Июль 22, 2013, 03:45:28 �

Господа, простите за скудоумие, объясните подробней решение с использованием "принципа четности" для 7 цветов и 100 мудрецов, а то мне все кажется, что имеет место "жестикуляция" - видимо что-то не дошло  Undecided
Записан

В действительности все не так, как на самом деле
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #61 : Июль 22, 2013, 06:00:09 �

Господа, простите за скудоумие, объясните подробней решение с использованием "принципа четности" для 7 цветов и 100 мудрецов, а то мне все кажется, что имеет место "жестикуляция" - видимо что-то не дошло  Undecided
Что именно Вы имеете в виду? Просто дайте ссылку на постинг.
Записан
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #62 : Июль 22, 2013, 06:02:47 �

Что-то не очень устраивает меня пока мое решение. Buka, скажите, а при вашем способе решения возможно ли рассмотреть вариант с 40 М и больше чем 20 цветами - даже, допустим, имеется палитра из 100 разных цветов и на всех 40 М будут какие-либо 40 цветов из 100?
Да, Питер Пен. Если, конечно, я сам не ошибаюсь Smiley
Ведь задачу придумал я сам. И когда излагал условие, то последний вариант у меня в голове ещё не был Smiley
Записан
Лев
Из мудрейших мудрейший
*****
Offline Offline

Сообщений: 2906

СПАСИБО
-вы поблагодарили: 1229
-вас поблагодарили: 1166


Искренне Ваш...


Просмотр профиля Email
Ответ #63 : Июль 22, 2013, 06:19:36 �

Как я понимаю, часы в условии задачи остаются.
Если М>К, то на каждого из М-(M-K) распределяется "ответственность" за один из цветов (К). Из этих М через небольшой промежуток времени (допустим, 1 мин.) встают те, кто видит четное число колпаков с "вмененным" ему цветом. При этом за это время каждый из всех М подсчитывает цвета колпаков его коллег. Поэтому, когда встают "ответственные" М (если соблюдается условие, чтобы встать) каждый понимает, какого цвета на нем колпак. Если по истечении этого времени никто из "ответственных" М не встал, значит нет четности наблюдаемых им цветов. И в этом случае тоже каждый М понимает какого цвета на нем колпак.

Вот этот пост. Ответственные мудрецы и временные цвета меня запутали вконец Smiley
Я так понимаю, вставать не уходя нельзя - это жестикуляция.
К тому же, при предварительном сговоре мудрецы еще без колпаков.

И вот, допустим, я ответственный мудрец (вдвойне смелое допущение) вижу четность вмененного мне цвета, время подошло - мне вставать? Если вставать, то какой цвет говорить?
Последнее редактирование: Июль 22, 2013, 06:21:29 от Лев Записан

В действительности все не так, как на самом деле
BIVES
Умник
****
Offline Offline

Сообщений: 687

СПАСИБО
-вы поблагодарили: 53
-вас поблагодарили: 272


Просмотр профиля
Ответ #64 : Июль 22, 2013, 11:29:39 �

Пусть всего 2 цвета и нет цвета который одет только на одного мудреца.
Делаем так: идут отвечать те, кто видят четное число колпаков, того цвета, который одет на мудреца, который стоит первым.
Если вышло четное число мудрецов, то на первом мудреце колпак такого цвета, как и на вышедших и он идет отвечать с ними.
Если вышло нечетное число мудрецов, то на первом мудреце колпак такого цвета, как на тех, которые остались.

Можно обобщить на любое количество цветов  (<501), если нет цвета который одет только на одного мудреца.
Последнее редактирование: Июль 22, 2013, 11:55:54 от BIVES Записан
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #65 : Июль 22, 2013, 11:57:18 �

Как я понимаю, часы в условии задачи остаются.
Если М>К, то на каждого из М-(M-K) распределяется "ответственность" за один из цветов (К). Из этих М через небольшой промежуток времени (допустим, 1 мин.) встают те, кто видит четное число колпаков с "вмененным" ему цветом. При этом за это время каждый из всех М подсчитывает цвета колпаков его коллег. Поэтому, когда встают "ответственные" М (если соблюдается условие, чтобы встать) каждый понимает, какого цвета на нем колпак. Если по истечении этого времени никто из "ответственных" М не встал, значит нет четности наблюдаемых им цветов. И в этом случае тоже каждый М понимает какого цвета на нем колпак.
Вот этот пост. Ответственные мудрецы и временные цвета меня запутали вконец Smiley
Я так понимаю, вставать не уходя нельзя - это жестикуляция.
К тому же, при предварительном сговоре мудрецы еще без колпаков.

И вот, допустим, я ответственный мудрец (вдвойне смелое допущение) вижу четность вмененного мне цвета, время подошло - мне вставать? Если вставать, то какой цвет говорить?
Это - решение предложенное Питером Пеном и оно мне понравилось.
Итак, есть М мудрецов и К<М цветов. К мудрецам поручено следить каждому за одним из К цветов и встать в первую минуту, если он видит чётное кол-во колпаков порученного ему цвета.
Вас интересует, как этот ответственный  мудрец узнает - а какой же на нём самом цвет.
Отвечаю.
1. Он знает всех К-1 ответственных мудрецов, цвета колпаков на них и цвета, за которые они ответственны.
2. Это значит, что он знает, что если на мудреце М1 колпак цвета Х а он ответственен за цвет У, то если он видит истинное кол-во колпаков цвета У, а если на мудреце М2 колпак цвета Ц и он ответственен за цвет Ц, то вместо чёта он видит нечёт и наоборот.
3. Таким образом наш ответственный мудрец, обозрев положение К-1 ответственного мудреца (встал или сидит) и цвет его колпака знает истинную чётность этих К-1 цветов.
4. Он её сравнивает с чётностью этих цветов, которую он видит. И если найдётся цвет, видимая чётность которого отличается от истинной (а таких цветов может быть не более 1-го) - то это цвет его колпака.
5. Если же ни один из К-1 цветов не имеет видимой чётности, отличной от истинной, это значит, что цвет, за которым наблюдает наш ответственный мудрец - и есть цвет его колпака.
6. Для не ответственных мудрецов - ещё проще - они судят по всем К цветам.

Эти пользователи сказали вам СПАСИБО :

Лев

За это сообщение 1 пользователь сказал спасибо!
Записан
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #66 : Июль 22, 2013, 12:08:04 �

Пусть всего 2 цвета и нет цвета который одет только на одного мудреца.
Делаем так: идут отвечать те, кто видят четное число колпаков, того цвета, который одет на мудреца, который стоит первым.
Если вышло четное число мудрецов, то на первом мудреце колпак такого цвета, как и на вышедших и он идет отвечать с ними.
Если вышло нечетное число мудрецов, то на первом мудреце колпак такого цвета, как на тех, которые остались.

Можно обобщить на любое количество цветов  (<501), если нет цвета который одет только на одного мудреца.
Судя по всему, Вы придумали метод сортировки, нашли "печку"...
Обобщите это, но конкретно - на три-четыре цвета, поскольку мне пока не понятно обобщение. Даже при условии ограничения на отсутствие уникального цвета. Кстати, 0 - число чётное. Smiley
Но у меня - другое решение
Записан
BIVES
Умник
****
Offline Offline

Сообщений: 687

СПАСИБО
-вы поблагодарили: 53
-вас поблагодарили: 272


Просмотр профиля
Ответ #67 : Июль 22, 2013, 12:24:46 �

Пусть всего 3 цвета и нет цвета который одет только на одного мудреца.
Делаем так: выходят те, кто видят четное число колпаков, того цвета, который одет на мудреца, который стоит первым.

Если вышли мудрецы с двумя цветами колпаков, то на первом мудреце колпак такого цвета, как и на оставшихся и они идут отвечать первыми. На вышедших колпаки двух цветов, поэтому дальше решение как для двух цветов (для сортировки цвет колпака первого из вышедших).

Если вышли мудрецы с одним цветом колпаков, то на первом мудреце колпак такого же цвета и он идет отвечать вместе с ними. На оставшихся колпаки двух цветов, поэтому дальше решение как для двух цветов (для сортировки цвет колпака первого из оставшихся).

На счет нуля не понял в чем проблема ?
Записан
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #68 : Июль 22, 2013, 13:44:33 �

Пусть всего 3 цвета и нет цвета который одет только на одного мудреца.
Делаем так: выходят те, кто видят четное число колпаков, того цвета, который одет на мудреца, который стоит первым.

Если вышли мудрецы с двумя цветами колпаков, то на первом мудреце колпак такого цвета, как и на оставшихся и они идут отвечать первыми. На вышедших колпаки двух цветов, поэтому дальше решение как для двух цветов (для сортировки цвет колпака первого из вышедших).

Если вышли мудрецы с одним цветом колпаков, то на первом мудреце колпак такого же цвета и он идет отвечать вместе с ними. На оставшихся колпаки двух цветов, поэтому дальше решение как для двух цветов (для сортировки цвет колпака первого из оставшихся).

На счет нуля не понял в чем проблема ?
Если у вышедших - колпаки двух цветов, то у них уже нет возможности свести задачу к задаче с двумя цветами. У них нет ещё одной системы отсчёта времени.
Насчёт нуля - нет никакой проблемы. Я думал, что может это Вам как-то поможет. Но можете проигнорировать эту реплику, если это Вам не важно.
Последнее редактирование: Июль 22, 2013, 13:47:12 от buka Записан
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #69 : Июль 22, 2013, 17:05:08 �

Если не будет возражений, завтра выложу решение в общем виде.
Записан
Лев
Из мудрейших мудрейший
*****
Offline Offline

Сообщений: 2906

СПАСИБО
-вы поблагодарили: 1229
-вас поблагодарили: 1166


Искренне Ваш...


Просмотр профиля Email
Ответ #70 : Июль 24, 2013, 02:12:26 �

Спасибо. Перечитал тему еще раз, все стало на места.

С нетерпением ждем решения в общем виде
Записан

В действительности все не так, как на самом деле
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #71 : Июль 24, 2013, 11:32:31 �

Итак приступим.
Сначала рассмотрим общий случай, когда цветов > 2, а затем отдельно случай с двумя цветами. Как ни странно, но он - сложнее Smiley
1. Введём некоторые термины:
а) ИЧЦ - Истинный/е Чётный/е Цвет/а - цвет/а тех колпаков, которых чётное кол-во. Напр. 6 синих, 8 жёлтых, 4 красных - это ичц
б) ИНЧ - истинный/е нечёт. цвет/а - понятно, думаю
в) ВЧЦ, ВНЧ - видимые чётные/нечётные цвета - цвета, видимые как чётные/нечётные в глазах мудрецов;
г) ИЧЧ - истинная чётность чётных цветов - общее число различных чётных цветов может быть чётным (ИЧЧ =0) и нечётным(ИЧЧ=1)
д) ВЧЧ - видимая Чётность чётных цветов - аналогично
е) ИКЧ(х) - истинная кратность чётных цветов по модулю х. ИКЧ(2) - это и есть ИЧЧ
ж) ВКЧ(х) - видимая кратность чётных цветов.

2. Начнём рассуждать.
Допустим у шаха 271 мудрец одетых в 38 цветов из которых 17 - чётные, а остальные 21 - нечётные, т.е. ИЧЧ = 1.
Что видят мудрецы, одетые в истинно чётные цвета? Они видят 16 чётных цветов, а свой и все нечётные они видят как нечётные и их (в их глазах - 22). То есть ВЧЧ(для чётных)=0.
Что видят мудрецы, одетые в истинно нечётные цвета? 18 чётных и 20 нечётных (надеюсь - ясно). То есть ВЧЧ(для нечётных)=0.
Аналогично, если бы шах использовал не 17 чётных цветов, а 18, то ИЧЧ=0, a ВЧЧ(для чётных)=ВЧЧ(для нечётных)=1
Надеюсь, пока понятно - мудрецы видят как бы консистентно наоборот Smiley
3. Казалось бы - тупик, ведь пока всё для них как бы одинаково.
4. Но у этого тупика есть выход Smiley - использовать кратность > 2, в нашем случае - 4.
Естественно для ВКЧ(4) у нас будут 4 значения - 0,1,2 и 3 (остатки по модулю 4 попросту говоря)
Рассмотрим случай с 38 цветами, из которых 17 - чётных.
ВКЧ(4)(для чётных) равно 0 (они видят 16 чётных, 16 на 4 делится без остатка)
А ВКЧ(4)(для нечётных) равно 2 (они видят 18 чётных, 18%4 даёт 2)
Аналогично, если бы шах использовал не 17 чётных цветов, а 18, 
то ВКЧ(4)(для чётных) = 1, а ВКЧ(4)(для нечётных) = 3 (в чём легко убедиться)
И вот на этом можно сыграть.
Сначала рассмотрим "тупую" стратегию, а потом поймём, что её можно даже улучшить. Хоть и тупая тоже неплохая.
5. Тупая стратегия.
5.1 В первую минуту встают те мудрецы, для которых ВКЧ(4)=0. В случае с 17 чётными встанут те, кто видит 16 чётных, в случае с 18 чётными - никто не встанет, в случае с 19 чётными - встанут те, кто видит 20, в случае с 20 чётными - никто не встанет. Во вторую минуту (ели в первую никто не встал) - с ВКЧ(4)=1 и т.д.
5.2. Сконцентрируемся сначала на случае 17, т.е. в первую минуту встанут те, кто видят 16.
Что они увидят среди вставших?
Каждый увидит 16 групп "чётных" мудрецов и ещё откуда-то затесавшуюся группу "нечётных" Smiley Вот на них и будут колпаки его цвета. Надеюсь, объяснять почему - не надо.
5.3. Рассмотрим случай с 19 чётными. В этом случае на первой минуте втанут те, кто видят 20 чётных.
И что они увидят? Каждый увидит, что из этих 20 чётных остался лишь одна группа. И вот цвет этой группы - и есть его цвет.
5.4. Я не буду объяснять, что остальные (не вставшие тоже без труда определят свой цвет.

6. Теперь давайте "причешем" нашу "тупую" стратегию.
Поскольку все мудрецы видят либо чёт, либо нечёт, то на первой минуте могут вставать мудрецы с ВКЧ(4)=0 и 1 - путаницы не будет. А на второй - ВКЧ(4)=2 и 3.
На первый взгляд напрашивается  более радикальный вывод - вообще вставание всегда произойдёт на первой минуте - встанут либо чётные, либо нечётные. И в подавляющем б-ве случаев это действительно так.
Но вернёмся к случаю с 19 чётными. Как я говорил, в этом случае встанут нечётные (те, кто видит 20). Это - верно.
Но если всего 19 цветов и все - чётные? То есть в первую минуту таки должны встать нечётные - но их по-просту не будет Smiley Это надо учесть Smiley Но ничего кардинально это не меняет.

7. У нас остался случай с двумя цветами. Надеюсь вы сами догадаетесь почему в некоторых ситуациях этот случай не впишется в нашу стратегию. Поэтому для этого случая следует применить стратегию BIVES для двух цветов или вообще - любую стратегию с искусственной сортировкой относительно назначенного в качестве "печки" мудреца.

Уффф... Вот, пожалуй и всё

Эти пользователи сказали вам СПАСИБО :

Лев

За это сообщение 1 пользователь сказал спасибо!
Последнее редактирование: Июль 24, 2013, 11:34:19 от buka Записан
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #72 : Август 01, 2013, 01:14:33 �

Если с этим решением Вам ясно, то давайте продолжим.
Усложним задачу ещё немного - уберём шахиню.
У каждого мудреца - пульт (напр. К кнопок разных цветов), куда он вносит ответ, процесс введения ответа (и сам ответ) никому не виден.
После введения ответа мудрец встаёт и уходит.
Короче, трюк со вставанием здесь не проходит.
Итак у нас пока есть две стратегии:
а) традиционная (как в задаче с мудрецами с неверными жёмами)
б) Питера Пена (когда время для первого цвета удваивается зато затем всё очень быстро) - http://nazva.net/forum/in....msg223918.html#msg223918
Ясно, что в одних случаях быстрее будет с а), а в других - с б)
Вопрос такой: зная К и (естественно, М), могут ли мудрецы:
1) выбрать стратегию с более коротким матожиданием времени полного угадывания;
2) выбрать критерий выбора стратегии "на месте", то есть, когда каждый видит колпаки других?
Записан
Страниц: 1 ... 3 4 [5]
  Печать  
 
Перейти в: