Автор Тема: Ещё раз о мудрецах  (Прочитано 26223 раз)
buka
Гений
*****
Offline Offline

Сообщений: 960



Просмотр профиля
« : Июль 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 » Записан