В данном случае от метода "реши сам" и метода "посчитай сам" перейду к методу "подсмотри у соседа"
Единственное - нужно ключевые слова знать
Этап 0. Основные определения и ключевые слова.
Теперь, по-научному. Дан n-мерный гиперкуб (с записью вершины вида БББЧЧБ, можно ноликами и единицами, но не буду чтобы не отклоняться от таблицы; количество колпаков - размерность).
Расстоянием между двумя вершинами назовем количество несовпадающих колпаков.
Шаром радиуса 1 от точки назовем множество вершин (последовательностей колпаков), отстоящих от данной не более, чем на 1.
Таких будет не ровно 1+n.
Перейдем к задаче.
Этап 1. Расстановка стрелок
Ребром будем соединять две соседние вершины. Именно ребро и видит мудрец, и ему нужно понять, пасовать или нарисовать на ребре стрелку, означающую, что он определяется и называет свой колпак таким, чтобы общее расположение было в точке, куда ведет стрелка.
Итак, на некоторых ребрах нарисованы стрелки.
При данных колпаках (в данной точке) мудрецы выигрывают, если ни одной стрелки ИЗ этой вершины не идет (т.е. никто НЕ сказал неверно) и если хотя бы одна стрелка идет В вершину (кто-то ответил верно).
Рассмотрим множество проигрышных вершин. Они же - страшные
Будем считать, что из каждой такой вершины ВСЕ ребра нарисованы со стрелками ИЗ данной вершины (если не нарисованы - нарисуем или перерисуем, новых проигрышных вершин при этом не добавится).
Этап 2.Что такое покрытие куба шарами радиуса 1 и почему нужно именно оно.
Во все вершины, которые не являлись проигрышными, должна привести хотя бы одна стрелка, т.е. эти вершины должны лежать в шаре радиуса 1 относительно какой-то проигрышной вершины.
Итак, задача. Какое наименьшее количество вершин в кубе размерности n нужно выделить, чтобы все остальные лежали в шаре радиуса 1 относительно какой-либо выделенной. Это и называется покрытием.
Этап 3. Научные результаты или подсматриваем у соседа здесь.
Наша задача - найти 1 - x/2^n, где x - количество таких вот шаров, покрывающих куб.
Тут будет небольшая
ссылка на одну презентацию.
Слайд 4:
Kt(n, 1) := minimum size of covering of 1-balls in Qn.
Ага, он нам и нужен
Главное - не перепутать covering и packing.
Покрытие - это чтобы каждая вершина лежала в шаре (шары могут пересекаться). Нужно именно оно.
Упаковка - чтобы шары не пересеклись (обычно исследуется в статьях именно она, ибо в данном случае в двоичном коде можно исправлять ошибки. Но нам она не нужна.)
Слайд 8 (часть 2):
Binary case (EIS, CHLL; P, EPY)
n 1 2 3 4 5 6 7 8 9 10 11
K2(n, 1) 1 2 2 4 7 12 16 32 ≤ 57 ≤ 105 ≤ 180
Вот она, вот она рыба моей мечты! Язь здоровеееенный!
Итого, ответы:
4 мудреца: 1- 4/16= 3/4
5 мудрецов: 1 - 7/32 = 25/32
6 мудрецов: 1 - 12/64 = 26/32 = 13/16
7 мудрецов: 1 - 16/128 = 7/8 (канонически)
8 мудрецов: также, 7/8
9 мудрецов и далее - данная презентация из курса лекций 2006 года даёт ответ в виде "больше, чем столько-то", но точного ответа, кроме канонических чисел, она не знает. Вот так вот
P.S> При усложнении задачи с увеличением количества цветов колпаков возникает проблема что если колпаков более 2х, то покрытие единичными шарами не является тем инструментом, который нам нужен для победы
](./images/smilies/bang.gif "Brick wall"){kind=small}
