11. 1, 2, 3, 5, 10, 20, (23 или 40), 43; 1, 2, 4, 8, 9, 17, (26 или 34), 43; 1, 2, 4, 8, 9, 17, 34, (43 или 68), 77; 1, 2, 4, 5, 9, 18, 36, (41 или 72), 77. Если бы любой из двух последних путей имелся в дереве, n = 43 было бы невозможно, поскольку дерево должно содержать либо 1, 2, 3, 5, либо 1, 2, 4, 8, 9.

12. Такое дерево невозможно, поскольку 1{п) ф Г(гг) для некоторых п.

13. Для случая 1 используйте цепочку типа 1, за которой следует 2+ + 2+* + 2* + 2, либо воспользуйтесь методом множителя. Для случая 2 используйте цепочку типа 2, за которой следует 2++ + 2+ + 2" + 2*. Для случая 3 используйте либо цепочку типа 5, за которой следует 2 + 2*- либо метод множителя. Для случая 4 n = 135 2, так что можно использовать метод множителя.

14. (а) Легко убедиться, что шаги г - 1 иг - 2 не являются малыми. Это позволяет считать, что шаг г - 1 является малым, а шаг г- 2 - нет. Если с = 1, то A(ar-i) = A(ar-)t), так что А; = 2; а поскольку 4 < v{ar) = i/(ar-i)+i/(ar-fc) -1 < i(ar-i)+l, имеем v{ar-\) > 3, делая шаг г - 1 звездным (чтобы цепочка ао, ai, ..., Ог-з, Or-i не включала только один малый шаг). Тогда Or-i = аг-2 + Ог-? для некоторого д, и, если заменить аг-2, Or-i, Яг на аг-2, 2аг-2, 2аг-2 + ar-q = Ог, получится другая цепочка-контрпример, в которой шаг г является малым. Однако это невозможно. С другой стороны, если с > 2, то 4 < v{ar) < u{ar-i) +v{ar-k) - 2 < i/(or-i); следовательно, i/(ar-i) = 4, v{ar-k) = 2 и с = 2. Это легко приводит к невозможной ситуации, возникающей в результате рассмотрения шести типов из доказательства теоремы В.

(Ь) Если A(ar-fc) < m - 1, имеем с > 3, так что и{аг-к) + i/(ar-i) > 7 согласно (22); поэтому как и{аг-к), так и 1/(0-1) оба > 3. Все малые шаги должны быть < г - к, а А(аг-*:) = т - к + 1. Если к > 4, необходимо иметь с = 4, А; = 4, 1/(0-1) = v{ar-4) - 4. Таким образом, Or-i > 2"4-2"-Ч2""2 „ a,. i должно быть равно 2"4-2"-Ч2"-Ч2"- но из аг-4 > \аг-\ вытекает, что Or-i = 8аг-4. Значит, А; = 3 и a-i > 2™ 4- 2"". Поскольку Ог-2 < 2™ и Ог-з < 2™~, шаг г - 1 должен быть удвоением, однако шаг г - 2 не является удвоением, так как Or-i ф 4аг-з. Кроме того, поскольку и{аг-з) > 3, г - 3 является звездным шагом и из аг-2 = аг-з 4- аг-ъ должно следовать, что аг-ъ = 2-2 Поэтому необходимо получить аг 2 = аг-з+аг-4. Как и в подобном случае, рассмотренном в тексте раздела, единственная возможность заключается в том, чтобы выполнялось Ог-4 = 2ГП-2 2-3, Ог-з = 2-2 -ь 2"- 4- 2+ + 2\ a.-i = 2" -Ь 2-\ + 2 -Ь 2-+, но и это невозможно.

15. Ахим Фламменкамп (Achim Flammenkamp) [Diplomarbeit in Mathematics (Bielefeld University, 1991), Part 1] показал, что все числа n с A(n) + 3 = 1{п) < Г{п) имеют вид 2-* 4- 2 + 2" 4- 2 2, где А > В > С > JD > £ и В + £ = С + £); более того, они точно описываются как не соответствующие ни одному из восьми шаблонов (здесь е < 1):

2 2*- -f- 2 -f- 2- -f- 22"2-4 2"* + 2*~ + 2 + 2 + 2~

2 2 4- 22~*+з -f. 2+~ -f. 23+-2 2* + 2-° -f- 2*"*+ 4. 2 -f- 2°++~*

2 + 2 + 2- 4- 2 4- 2-\ 2" + 2-b 2-= + 2 + 2- >

2 2 2 -f- 22+-* -b 2++- 2*-b 2*-b 2-f-2*""""-*-b 2+"*

16. Z(n) = A(n) 4- v{n) - 1, так что, если n = 2 l{n)IX{n) = 1, но если n = 2*=+ - 1, Z(n)/A(n) = 2.

17. Пусть «1 <••<«(. Удалим все интервалы h, которые можно удалить без изменения объединения JTi U U It- (Интервал (jk - - ik] может быть удален, если jk--i < jk либо ji < J2 < •••и jk+i < ik-i-) Теперь объединим перекрывающиеся интервалы iji - - ii], ---,{jd-- id] в интервал (j ..«] = (ji - -id] v. заметим, что

av <aj,{\ + &y-++-" <ау{\ + 5У-\

поскольку каждая точка (/ ..»] покрывается объединением (j;.. ii] U • • • U (jd id] не более двух раз.

18. Назовем /(т) "хорошей" функцией, если (log/(m))/m -¥ О при т оо. Произвольный полином от т является "хорошим". Произведение хороших функций - хорошая функция. Если д{т) - О и с - положительная константа, то c™*"" -хорошая функция; хороша также и („)), так как с учетом аппроксимации Стирлинга это эквивалентно утверждению g{m)\og{l/g{m)) -у 0.

Теперь заменим каждый член суммы максимальным по s, t, v членом. Обш;ее число членов - хорошее, так же как и (7+„), Cf) 2+" и /3", потому что (t + v)/m -> 0. И наконец (("+ ) < {2т)*(tl < {Aem/tY, где (4е)-хорошая функция. Замеш;ая ( его верхней границей (1 - e/2)m/A(m), показываем, что (m/tY < 2™-~ f(m), где f{m) - хорошая функция. Следовательно, вся сумма меньше, чем а™ для больших т, если а = 2-\ где О < »7 < е.

19. (а) М П ЛГ, М и ЛГ, М Ы ЛГ соответственно; см. 4.5.2-(6), 4.5.2-(7).

(b) f{z)g{z), \cm{f{z),g{z)), gcd(/(z), д(г)). (По тем же причинам, что и в п. (а), потому что нормированные неприводимые полиномы над полем комплексных чисел в точности представляют собой полиномы г - С-)

(c) Законы коммутативности: АЫ В = ВЫ А, A\J В = B\J А, АГ\ В = В Г\ А. Законы ассоциативности: А Ы (В Ы С) = (А Ы В) Ы С, А U (В U С) = (А U В) U С, А П (В П С) = (Л П В) П С. Законы дистрибутивности: А U (В П С) = (А U В) П (А U С), Л П (В U С) = (А П В) и (А П С), А Ы (В и С) = (Л Ы В) и (А Ы С), А Ы (В П С) = (А Ы В) П (А Ы С). Законы идемпотентности: AuA = A, АПА = А. Законы поглош;ения: А U (А П В) = А, АП(АиВ) = А, АП(А1±1В) = А, AU(Al±lB) = AttlB. Законы единицы и нуля: 01±1 А = А, 0иА = А, 0ПА = 0, где 0 обозначает пустое мультимножество. Закон перечисления: А ttl В = (А и В) ttl (А П В). Прочие свойства, аналогичные соответствуюш;им свойствам множеств, вытекают из частичной упорядоченности, определенной правилом А С В тогда и только тогда, когда А П В = А (тогда и только тогда, когда А U В = В).

Примечания. Другие обш;ие применения мультимножеств - нули и полюсы меро-морфных функций, инварианты матриц в канонической форме, инварианты конечных Абелевых групп и т. д. Мультимножества могут быть полезны в комбинаторике и в теории мер. Терминальные строки нециркулярной контекстно-свободной грамматики образуют мультимножество, которое является множеством тогда и только тогда, когда грамматика свободна от неопределенностей. В статье автора в Theoretical Studies in Computer Science, edited by J. D. Ullman (Academic Press, 1992), 1-13, обсуждаются дальнейшие применения к контекстно-свободным грамматикам и вводится операция АПВ, где каждый элемент, который встречается а раз в А и Ь раз в В, встречается в А П В аЬ раз.

Хотя мультимножества появляются в математике достаточно часто, во многих случаях они трактуются неуклюже, поскольку в настоящее время не существует стандартного пути рассмотрения множеств с повторяющимися элементами. Некоторые математики выразили свое мнение о том, что отсутствие адекватной терминологии и обозначений для этой глобальной концепции определенно затрудняет развитие математики. (Мультимножество, конечно, формально эквивалентно отображению множества на неотрицательные .целые числа, но эта эквивалентность имеет слишком малое значение для творческого математического мышления.) Автор обсуждал этот вопрос со многими специалистами в 60-х годах, пытаясь найти приемлемое решение вопроса. Вот некоторые из предлагавшихся для этой концепции названий: список (list), связка (bunch), мешок (bag), куча (heap), проба

(sample), взвешенное множество (weighted set), коллекция (collection*), комплект (suite). Однако все эти они конфликтуют с существующей терминологией, имеют неуместное дополнительное значение или слишком неудобны для произношения и написания. Наконец, стало ясно, что для такой важной концепции необходимо собственное имя, и оно - "мультимножество" (multiset) - было предложено Н. Г. де Брейном (N. G. de Bruijn). Его предложение широко распространилось в 70-х годах и теперь является стандартным термином.

Запись "АЬВ" была выбрана автором, чтобы избежать конфликтов с существующими обозначениями и усилить аналогию с объединением множеств. Для этого нежелательно использовать "А + В", поскольку специалисты в области алгебры приняли А + В как запись для мультимножества {а + 0 а € Аи р.£ В}. Пусть А является мультимножеством неотрицательных целых чисел, а G{z) = Епел"-производящая функция, соответствующая А. (Очевидно, что производящие функции с неотрицательными целыми коэффициентами находятся во взаимно однозначном соответствии с мультимножествами неотрицательных чисел.) Если G{z) соответствует А, а H{z) соответствует В, то G{z) + H{z) соответствует А ttl В, а G{z)H{z) соответствует А + В. Если построить производящие функции Дирихле g{z) = Епел/" ) = Епев/" ° произведение g{z)h{z) будет соответствовать произведению мультимножеств АВ.

20. Тип 3: (So,...,5r) = (Moo,..., Мго) = ({0}, {А}, А}, {А-1, А, А}, {А-\,А-\,А,А,А}, ...,{А + С-3,А + С-З.А + С-1,А + С-А + С - 2}).

Тип 5: (Моо,...,М.о) = ({0}, {А}, {А-1,А}, ...,{А + С-1,А+С}, {А+С-1,А+ С-\,А + С}, ...,{А + С + D-\,A + C + D-\,A + C + D}); (Moi,..., Мп) = (0, ... ,0, 0, 0, {A-hC-2}, {A-hC-hJD-2}), Si = Мой Ma.

21. Пусть, например, и = 2*«+ х = (2(«+"-1)/(2"-1) = 2«"-h •--1-2"-Ь1, у = 2(«+"-Ц. Тогда ху = (22(«+1" - 1)/(2" - 1). Если п = 2*«+"" + ху, имеем 1{п) <A{q + \)u + q + 2 по теореме F, но Г(п) = 4(д + 1)м -Ь 2д 2 согласно теореме Н.

22. Подчеркните все, кроме и - 1 вставок, использованных при вычислении х.

23. Теорема G (подчеркнуто все).

24. Используйте числа (В" - 1)/(В - 1), О < г < г, подчеркнутые, когда подчеркнуто Oj, иснВ-\В-\)1{В-\)тяй<з <t,Q<i< bj+i-bj, 1<к< 1°{В), подчеркнутые, когда подчеркнуто Ск, где Со, ci, ... - /"-цепочка минимальной длины для В. Для доказательства второго неравенства положите В = 2™ и используйте (3). (Второе неравенство редко приводит к улучшению теоремы G, если вообще приводит.)

25. Будем считать, что djt = 1. Используем правило R Ak-i... Ai, где Aj = "XR" если dj =1, и Aj = "R" в противном случае, и где "R" обозначает взятие квадратного корня, а "X"-умножение на х. Например, если у = (.1101101)2, правило выглядит следующим образом: R R XR XR R XR XR. (Существуют бинарные алгоритмы для извлечения квадратного корня, пригодные для использования на аппаратном уровне, время работы которых сравнимо со временем выполнения деления; компьютеры с таким аппаратным обеспечением могли бы таким образом вычислять более общие дробные степени с помощью технологии, описанной в этом упражнении.)

26. Если известна пара {Fk,Fk-i), то имеем {Fk+i,Fk) = (Fk + Fk-i,Fk) и {F2k,F2k-i) = (Fk + 2FkFk-i,Fk + Fk-\), поэтому для вычисления (Fn,F„ i) может быть применен бинарный метод с O(logn) арифметическими операциями. Возможно, лучше применить пары значений {Fk,Lk), где Lk = Fk-i+Fk+i (см. упр. 4.5.4-15); тогда имеем (Fjt+i, Ljt+i) = {{Fk + Lk),{5Fk+Lk)), {F2k,L2k) = {FkLk,Ll - 2{-\f).

* Заметим, что этот термин, хотя и не прижился в математике, широко распространен в программировании, особенно - в объектно-ориентированном. - Прим. перев.