данное множество представляет собой "существенно ориентированное дерево". Что в таком случае является корнем и дугами этого ориентированного дерева?

2. [20] Покажите, что «ели допускается вращение тетрадных типов, то рещение существует всегда.

► 3. [М23] Если можно покрыть верхний правый квадрант плоскости с помощью заданного бесконечного множества тетрадных типов, то всегда ли можно покрыть ими всю плоскость?

4. [М25] (Задача X. Ванга.) Шесть тетрадных типов (2) позволяют получить тороидальное рещение этой задачи покрытия плоскости, т. е. рещение, в котором некоторый прямоугольный фрагмент, а именно - (3), будет повторяться чо всей плоскости.

Предположим без доказательства, что для каждого покрытия плоскости с помощью тетрадных типов существует тороидальное рещение, в котором применяются эти тетрадные типы. Используйте данное предположение вместе с леммой о бесконечном дереве для создания алгоритма, с помощью которого для заданных спецификаций любого конечного множества тетрадных типов можно определить за конечное число щагов, существует ли способ покрытия плоскости этими тетрадными типами.

5. [М40] Покажите, что, используя 92 показанных ниже тетрадных типа, можно покрыть плоскость, но при этом не существует тороидального решения в смысле, указанном в упр. 4.

Для упрощения спецификации 92 типов прежде всего введем некоторые условные обозначения. Введем такие "основные коды".

[4 типа] [21 тип] [22 типа]

[45 типов]

Тогда тетрадные типы будут иметь следующий вид. а{а,Ь,с, d}

/3{Y{B,U,Q}{P,T}, {B,U,D,Q}{P,S,T}, K{B,U,Q}} 7{{{X, B}{L, P, S, T},R}{B, Q}, J{L, P, S, T}} 5{X{L, P, 5, T}{B, Q), Y{B, U, Q}{P, Г}, N{a, b, c, d}, J{L,P,S,T}, K{B,U,Q}, {R,L,P,S,T}{B,U,D,Q}}

Эти сокращения означают, что основные коды нужно представить покомпонентно во всех указанных сочетаниях и рассортировать по алфавиту внутри каждого компонента. Например, сокращение

0Y{B,U,Q}{P,T}

обозначает шесть таких тетрадных типов: /ЗУБР, /3YUP, 0YQP, /ЗУВТ, J3YUT, J3YQT. Тип /3YQT после покомпонентного умножения соответствующих друг другу компонентов (где умножение на пропущенный компонент обозначает умножение на единицу) примет вид

(3,4,2,1)(Г,Г, , )(Q,Q, , )( , ,T,T) = (3Qr,4Qr,2T,lT).

Предполагается, что он соответствует показанному справа тетрадному типу, в четырех частях которого вместо чисел используются символьные строки. При этом два тетрадных типа могут располагаться рядом только при совпадении строк соприкасающихся частей.

9-тетрадой называется тетрадный тип, если в его спецификации указанного выше вида содержится р. Начиная поиск решения этой задачи, обратите внимание, что слева и справа от 9-тетрады должны находиться q-тетрады, снизу и сверху - (5-тетрады. Справа от аа-тетрады должны располагаться РКВ, j3KU или j3KQ, за которыми должна следовать аб-тетрада, и т. д.

(Это построение является упрощенной версией построения, предложенного Робертом Бергером (Robert Berger), который доказал, что общая задача из упр. 4 без учета неправильного предположения не может быть разрешена. См. Memoirs Amer. Math. Soc. 66 (1966).)

► 6. [M23} (Задача Отто Шрайера (Otto Schreier).) В своей знаменитой статье [Nieuw Archiefvoor Wiskunde (2) 15 (1927), 212-216] Б. Л. Ван дер Варден (В. L. van der Waerden) доказал следующую теорему.

Если к и т-положительные целые числа и если есть к множеств Si,...,Sk положительных целых чисел и каждое положительное целое число принадлежит по крайней мере одному из этих множеств, то хотя бы одно из множеств Sj содержит арифметическую прогрессию длины т.

(Это значит, что существуют такие целые числа а и J > О, что а -\- 5, а -\- 25, ..., а -Ь mS находятся в множестве Sj.) Если возможно, попробуйте использовать этот результат и лемму о бесконечном дереве для доказательства следующего, более "сильного", результата.

Если к и т - положительные целые числа, то существует такое Л, что если есть к множеств Si,... ,Sk целых чисел, причем каждое значение между 1 и N включено по крайней мере в одно из этих множеств, то хотя бы одно из множеств Sj содержит арифметическую прогрессию длины т.

Интересное описание Ван дер Вардена о том, как было найдено доказательство данной теоремы, можно найти в книге Studies in Pure Mathematics, ed. by L. Mirsky (Academic Press, 1971), 251-260.

► 7. [M30] Если это возможно, используя теорему Ван дер Вардена из упр. 6 и лемму о бесконечном дереве, докажите следующее утверждение.

Если к - положительное целое число и имеется к множеств Si,... ,Sk целых чисел, причем каждое положительное целое число включено по крайней мере в одно из этих множеств, то хотя бы одно из множеств Sj содержит бесконечно длинную арифметическую прогрессию.

* 8. [М39} (Задача Дж. Б. Крускала (J. В. Kruskal).) Если Т и Т-конечные и упорядоченные деревья, пусть Т С Т обозначает, что Т можно вложить в Г так, как в упр. 2.3.2-22. Докажите, что если Ti, Тг, Тз, ... -бесконечная последовательность деревьев, то существуют такие целые числа j < к, что Tj С Тк. (Иначе говоря, докажите, что можно построить бесконечную последовательность деревьев, в которой ни одно дерево не содержит построенных ранее деревьев этой последовательности. Данный факт можно использовать для доказательства того, что некоторые алгоритмы должны завершиться за конечное число шагов.)

*2.3.4.4. Перечисление деревьев. Некоторые наиболее поучительные примеры применения математической теории деревьев для анализа алгоритмов связаны с формулами подсчета количества различных деревьев того или иного типа. Например, если поставить вопрос о том, сколько различных ориентированных деревьев можно построить, используя четыре неразличимые вершины, то получится, что

возможны только след}ющие четыре типа деревьев:

в первой из рассматриваемых здесь задач перечисления деревьев определим количество а„ структурно различных ориентированных деревьев с п вершинами. Очевидно, что Oi = 1. Если п > 1, то дерево имеет корен?? и поддеревья. Допустим, что существует ji поддеревьев с одной вершиной, -с двумя вершинами и т. д. Тогда можно выбрать jk деревьев из возможных деревьев с к вершинами

ак + Зк - 1 jk

способами, так как в подобном случае допускаются повторения (см. упр. 1.2.6-60). Исходя из этого, получаем следующее:

для П > 1. (2)

«1 +31

Зп-1

ji+2J2 + ---=n-\

Рассмотрим производящую функцию A{z) = Ylnnz" с «о = 0. Находим, что из тождества

1 fa+j-V

{l-Z)

и уравнения (2) следует, что

"• " il-z){l-Z)Цl-zЗ)...

Этим выражением для A{z) не очень удобно пользоваться, так как оно содержит бесконечное произведение и коэффициенты «1,02,... в правой части. Более элегантный способ представления A{z) предлагается в упр. 1. Он позволяет получить значительно более эффективную формулу для подсчета значений а„ (см. упр. 2) и фактически может использоваться для описания асимптотического поведения а„ для больших п (см. упр. 4). Таким образом, получаем

A{z) =z + z + 2z + z" + + 20г -f- 48г + Wbz

+ 286г+ 719г°-ь 18421-f-(4)

Теперь, когда число ориентированных деревьев найдено, интересно было бы определить количество структурно различных свободных деревьев с п вершинами. Существует только два различных свободных дерева с четырьмя вершинами, а именно

так как два первых и два последних дерева (1) будут тождественны, если не принимать во внимание направление.