flaass: экстрасенс. мыслию по древу.

экстрасенс. мыслию по древу.

Долгожданное строгое изложение верхней оценки.

Итак. Игра наша, в общем виде, такова:
Служителю дают колоду из n карт, каждая одной из b мастей.
Для простоты предположим, что любая из b^n последовательностей разрешена (впоследствии увидим, что это мало что меняет).
Каждую рубашку служитель помечает одним из a символов, a < b.

Предположим, что экстрасенс со служителем изобрели методу, с гарантией позволяющую ошибиться не более cn раз.
Что означает "изобрели методу"? - 1. что для любой колоды длины n служитель точно знает, как ее пометить; и 2. что для любого начального отрезка помеченной колоды (уже вскрытого), и для любой возможной при этом начальном отрезке следующей метки, экстрасенс точно знает, какую из b мастей назвать.
Представим эту методу в виде корневого дерева. Вершинами его будут служить все возможные начальные отрезки помеченной колоды. Корнем - пустой отрезок. Листьями - все b^n возможных колод, с нанесенными на них "по методе" пометками. Сыновьями вершины будут все ее возможные продолжения на одну карту (проверка на понимание: у каждой вершины не более ab сыновей).
Чего не хватает? - правила угадывания. Его мы представим на том же дереве, покрасив каждое ребро в черный (угадал) или белый (не угадал) цвет. Проверка на понимание (очень важная!): из каждой вершины выходит не более a черных, и не более a(b-1) белых ребер.
Что означает теперь, что "метода гарантирует не более cn ошибок"? - что в любом из b^n путей от корня к листьям имеется не более cn белых ребер.

А теперь забудем про происхождение дерева и запомним лишь его очевидные свойства:
- корневое дерево высоты n, все его листья на уровне n, и всего их b^n;
- из каждой вершины на следующий уровень идет не более ab ребер;
- из них не более a черных и не более a(b-1) белых;
- каждый сквозной путь содержит не более cn белых ребер.

И кайф в том, что этих условий достаточно, чтобы (на этот раз совершенно строго) провести вывод нижней оценки на c - то есть верхней оценки на число гарантированных угадываний - "по

garvej@ljю" :)

Арифметика опущена; потом напишу.

(Добавить комментарий)

a_konst@lj
2004-03-12 20:41 (ссылка)

Те дискуссии мне сознательно открывать не хочется, потому что не теряю мылси сам придумать решение с 25 :)

а вот это прочитал.
если детей у вершины "не более ab", а не "ровно b" (как я понял было сперва), то как листьев может быть ровно b^n????

что-то в этом дереве таинственное и загадочное.
надо его порисовать для случаев типа b = n = 3, a = 2 :)

между двумя ребрами соседних уровней может быть только одно ребро? Или может быть больше?

(Ответить) (Ветвь дискуссии)

flaass@lj
2004-03-12 23:06 (ссылка)

Дерево, конечно, будет неоднородным. Форма его зависит от того, по какому правилу служитель расставляяет метки. "Не больше ab" - это все, что мы можем гарантировать. Ну, и еще "не меньше 1" везде, кроме конечных точек - потому что, по построению, каждая внутренняя вершина дерева достраивается до возможной последовательности. И все-таки ab, а не b, потому что мы смотрим и на метки тоже.

(Ответить) (Уровень выше) (Ветвь дискуссии)

a_konst@lj
2004-03-13 09:30 (ссылка)

И все-таки я совершенно не понимаю, что представляют собой узлы и ребра дерева.
Для начала договоримся о базовом:
дерево - граф без циклов. в частности, между любыми двумя узлами не более одного ребра.
в нашем случае граф "проградуированный". Высотой n+1, с уровнями от 0 до n. листья (узлы без связаннях вершин ниже уровнем) есть только на n-м уровне.

До сих пор мне ясно.
теперь то что неясно:
1) сколько узлов на промежуточных уровнях?
2) что собсно означают узлы? узлы на k-м уровне - это все возможные расположения ТОЛЬКО мастей или для некоторых начальных отрезков мастей введено по несколько узлов, отличающихся наборами пометок?
3) Что собсно означает ребро между двумя узлами? Просто "отрезок, соотв-щий нижнему узлу, содержит в себе отрезок, соотв-щий верхнему узлу"?
4) цвет ребра означает только "угадал/не угадал", точнее, дает ли алгоритм, по которому действует "экстраценс", правильный ответ. Но сам по себе никак не кодирует САМОЙ (отдельно взятой) пометки ни на этом уровне, ни на предыдущих.
Иначе говоря - раскраска есть свойство алгоритма.

О, самый важный вопрос - топология ( НЕ РАСКРАСКА, а именно структура!) дерева хависит от "метода угадывания"? или дерево универсально, а мы анализируем только всевозможные раскраски?

Постарайтесь пожалуйста изложить максимально формально, без упрощений "на пальцах".

(Ответить) (Уровень выше)

jedal@lj
2004-03-12 21:56 (ссылка)

Здорово. Правда я пока не понимаю, почему белых ребер выходит не более a(b-1) (оценка на черные ребра мне понятна).
Кстати, почему мы можем считать, что любая из bⁿ последовательностей разрешена? Казалось бы, это испортит нам верхнюю оценку.

(Ответить) (Ветвь дискуссии)

flaass@lj
2004-03-12 23:01 (ссылка)

Каждое белое ребро - одно из продолжений, при которых масть не угадана, т.е. одна из b-1 не совпавших с догадкой Э. Итак, на каждую метку по не более чем b-1.

А про разрешенные последовательности - на этой стадии нам уже пофиг, какие они именно, важно лишь число. Можно (и нужно, на самом деле) решать для произвольного заданного числа листьев N, а потом уже приравнивать его чему надо.

(Ответить) (Уровень выше) (Ветвь дискуссии)

	jedal@lj 2004-03-13 00:25 (ссылка)
	И правда понятно. (Ответить) (Уровень выше)

a_konst@lj
2004-03-13 09:40 (ссылка)

кстати, еще вопрос.
куда девается в этом дереве информация, полученная из рубашки самой верхней карты?

кажется до меня что-то начинает доходить :)
Как я понял, дерево зависит от метода. и кодирует только цепочки, возможные для этого метода. Тогда, ясно, что листьев только b^n - каждому расположению мастей соотв-ет только одно расположение меток (именно это одначает "метод").

только все-таки непонятно - ведь на k-м шаге экстрасенс знает k отметок и только k-1 масть... И этому шагу соотв-ет узел на k-1 уровне? Тогда проблемы с корнем у дерева...
он же на нулевом уровне.. но уже есть a вариантов.

Что-то тут не так.. или я все еще торможу.

(Ответить)