AOP_Tom1 (1021736), страница 110
Текст из файла (страница 110)
При этом нельзя отделаться от границы просто за счет сдвига верхнего правого квадранта вниз и влево, так как сдвиг имеет смысл выполнять только на конечную величину. Вот как выглядит доказательство Ванга. Из существования решения для покрытия правого верхнего квадранта следует, что для любого п существует способ покрытия квадрата 2п х 2п. Множество всех решений задачи покрытия квадратов с четной длиной сторон образует ориентированное дерево, если дети каждого решения х размера 2п х 2п являются решениями размера (2п+ 2) х (2п+ 2), которые могут быть получены путем окаймления решения х.
Корнем такого дерева является решение размера 0 х О, его детьми — решение размера 2 х 2 и т, д. Каждый узел имеет только ограниченное количество детей, так как в задаче покрытия плоскости предполагается, что для покрытия может использоваться только конечное множество тетрадных типов. Следовательно, согласно лемме о бесконечном дереве существует бесконечный путь к корню.
Это значит, что существует способ покрытия всей плоскости (хотя, возможно, его не так уж просто будет найти!). Описание дальнейшего развития исследований в области тетрадного покрытия плоскости можно найти в прекрасной книге Б. Грюнбаума и Дж. К. Шепарда [Тйт8з аль РаССегпз Ьу В. СгйпЬашп апс( О. С. 8ЬерЬвтб (Ргеешап, 1987), СЬарСег 11). данное множество представляет собой "существенно ориентированное дерево". Что в таком случае является корнем и дугами этого ориентированного деревау 2. [20) Покажите, что если допускается вращение тетрадных типов, то решение суШествует всегда. 3.
[Мйб[ Если можно покрыть верхний правый квадрант плоскости с помощью заданного бесхонечнога л|ножества тетрадных типов, то всегда ли можно покрыть ими всю плоскость? 4. [М25[ (Задача Х. Ванга.) Шесть тетрадных типов (2) позволяют получить тороидальное решение этой задачи покрытия плоскости, т. е. решение, в котором некоторый прхмоугольный фрагмент, а именно — (3), будет повторяться ио всей плоскости. Предположим без доказательства, что для каждого покрытия плоскости с помощью тетрадных типов существует тороидальное решение, в котором применяются эти тетрадные типы.
Используйте данное предположение вместе с леммой о бесконечном дереве для создания алгоритма, с помощью которого для заданных спецификаций .чюбого конечного множества тетрадных типов можно определить за конечное число шагов, существует ли способ покрытия плоскости этими тетрадными типами. 5. [М40) Покажите, что, используя 92 показанных ниже тетрадных типа, можно покрыть плоскость, но при этом не существует тороидального решения в смысле, указанном в упр.
4. Для упрощения спецификации 92 типов прежде всего введем некоторые условные обозначения. Введем такие "основные коды". а=(1,2,1,2) Д=(34,2, 1) у=(2,1,3,4) а = (б), В, Р, Л) Ь = (,, б., Р) с = ((), б), Т, 5) Ж=(У,,Х, ) з =(В,(У,,Х) К=(, УЛ, В) Л=(,,Л,Л) В=(,,б, В) Р=(,,Р,Р) Т=(,,Т,Т) Х=(,,Х,Х) 1 =(1;У,, ) и=(бгЬг,, ) В=(П,В,, ) Тогда тетрадные типы будут иметь следующий внд. б =(4, 3,4, 3) д = (,,Я,Т) В=(...
) Я=(,,Я)Я) Я=ЮЮ, ) а(а,Ь,с,4) Д(У(В,ПУ)(Р,Т), (В,и,П,д)(Р,В,Т), К(В,Ьг,4)Ц -~(((Х, В) (В, Р, Я, Т), Л)(В, Я),,У(Т., Р,Б, Т)) б(Х(Е, Р, Я, Т) (В, Я), У(В, ПЯ) (Р, Т), К(а, Ь, с, 4), ,У(Г.,Р,Я,Т), К(В,(У,с)), (Л,б,,Р,Я,Т)[В,У,Р,11)) [45 типов] Эти сокращения означают, что основные коды нужно представить покомпонентно во всех указанных сочетаниях н рассортировать по алфавиту внутри каждого компонента. Напри- мер, сокращение ДУ(В, и, Ц)(Р, Т» (3,4,2,Ц(У1;, )(11,д,, )(,,Т,Т) =(3дУ4ЦУгт,1Т) Предполагается, что он соответствует показанному справа тетрадному типу в четырех частях которого вместо чисел используются символьные строки При этом два тетрадных типа могут располагаться рядом только при сов- падении строк соприкасающихся частей.
31)У 2Т 17 4ЯУ обозначает шесть тахих тетрадных типов; ДУВР, ДУВР, ДУВР, 0УВТ, ДУСТ, ДАТ, Тип ДАТ после покомпонентного умножения соответствующих друг другу компонентов (где умножение на пропущенный компонент обозначает умножение на едннипу) примет вид !3-тетрцлой называется тетрадный тип, если в его спецификации указанного выше вида содержится Э. Начиная поиск решения этой задачи, обратите внимание, что слева и справа от 8-тетрады должны»гахрдиться о-тетрады, снизу и сверху — б-тетралы. Справа от аа-тетрады должны располагаться рКВ, »ЭКЬГ или ЭКЯ, за которыми должна следовать об-тетрада, и т. д.
(Это построение является упрощенной версией построения, предложенного Робертом Бергером (ВоЬег» Вегбег), который доказал, что общая задача из упр. 4 без учета неправильного предположения не может быть разрешена. См. Мешо1гэ Атег. Ма»Ь. 5ос. 66 (1966).) 6. (МЭЭ) (Задача Отто Шрайера (Омо БсЬге!ег).) В своей знаменитой статье (№епв' АгсЫеб гоог И'!э)гил»(е (2) 15 (1927), 212-216) Б. Л. Ван дер Варден (В.
1 . тап г)ег Жаегдеп) доказал следующую теорему. Если Й н т — положительные целые числа н если есть Й множеств 5»,...,5» положятельных целых чисел н каждое положительное целое число принадлежит по кралней мере одному из этих множеств, то хотя бы одно нз множеств 5, содержит арифметическую прогрессию длины гп.
(Это значит, что существуют такие целые числа а н б ) 9, что а + б, а + 2б,, а + тб находятся в множестве 5,.) Если возможно, попробуйте использовать этот результат и лемму о бесконечном дереве для доказательства следующего, более "сильного", результата. Еслн Ь н т — положительные целые чгггла, то существует такое !»7, что если есть Ь множеств 5»,..., 5» целых чисел, причем каждое значение между 1 и А» включено по крайней мере в одно из этих множеств, то хотя бы одно из множеств Я! содержит арифметическую прогрессию длины и». Интересное описание Ван дер Вардена о том, как было найдено доказательство данной теоремы, можно найти в книге Яги»!!еэ !и Риге МаГЬешамсэ, еф Ьу Ь. М»гэйу (Аса»1еоис Ргеээ, 1971), 251-260. 7.
(МЭ0) Если это возможно, используя теорему Ван дер Вардена из упр. б и лемму о бесконечном дереве, докажите следующее утверждение. Если Ь вЂ” положительное целое число и имеется Ь множеств Ям...,5» целых чисел, причем каждое положительное целое число включено по крайней мере в одно из этих множеств, то хотя бы одно нз множеств 5 содержит бесконечно длинную арифметическую прогрессию. 8. (МЭУ) (Задача Дж.
Б. Крускала (Л. В. Кгпв)»а1).) Если Т и Т' — конечные и упорядоченные деревья, пусть Т С Т' обозначает, что Т можно вложить в Т' так, как в упр. 2зй2-22. Докажите, что если Т», Тю Т», ... — бесконечная последовательность деревьев, то существуют такие целые числа Э < Ь, что Т! С Т».
(Иначе говоря, докажите, что можно построить бесконечную последовательность деревьев. в которой ни одно дерево не содержит построенных ранее деревьев этой последовательности. Данный факт можно использовать для доказательства того, что некоторые алгоритмы должны Завершиться за конечное число шагов.) в2.3.4.4. Перечисление деревьев. Некоторые наиболее поучительные примеры применения математической теории деревьев для анализа алгоритмов связаны с формулами подсчета количества различных деревьев того нли иного типа.
Например, если поставить вопрос о том, сколько различных ориентированных деревьев можно построить, используя четыре неразличимые вершины, то получится, что возможны только следующие четыре типа деревьев В первой из рассматриваемых здесь задач перечисления деревьев определим количество а„структурно различных ориентированных деревьев с и вершинами. Очевидно, что а~ = 1. Если и > 1, то дерево имеет корень и поддеревья.
Допустим, что существует и поддеревьев с одной вершиной, ~з — с двумя вершинами и т. д. Тогда можно выбрать уа деревьев из аь возможных деревьев с к вершинами аь+уь — 1 способами, так как в подобном случае допускаются повторения (см. упр. 1.2.6 — 60). Исходя из этого, получаем следующее: Рассмотрим производящую функцию А(з) = 2 „а„т" с ав — — О.
Находим, что нз тождества и уравнения (2) следует, что А(г)— (1 в)а~(1 т2)ая(1 зз)аз Этим выражением для А(х) не очень удобно пользоваться, так как оно содержит бесконечное произведение и коэффициенты амат,... в правой части. Более элегантный способ представления А(з) предлагается в упр. 1. Он позволяет получить значительно более эффективную формулу для подсчета значений а„(см. упр, 2) и фактически может использоваться для описания асимптотического поведения а„ для больших и (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
