26. Доказательство достаточности получается непосредственным обобщением на случай основания b обычного доказательства. Доказательство необходимости разбивается на две части. Если для некоторого п число /3ti+i больше J2k<nkPk, то для малых б число 0П+1 - б не допускает такого представления. Если /Зп+i < sumk<nCkPk для всех п, но равенство выполняется не всегда, то можно показать, что для некоторого х существуют два представления (см. Transactions of the Royai Society of Canada, series III, 46 (1952), 45-55).

27. Доказательство вьшолняется индукцией по п. Если п четно, то должно быть ео > О и искомый результат получается по индукции, так как п/2 имеет единственное представление такого типа. Если п нечетно, то должно быть ео = О и задача сводится к представлению числа -(п-1)/2. Если это последнее равно либо О,, либо 1, то, очевидно, существует только один способ решения задачи. В противном случае по индукции доказывается, что число имеет единственное представление.

[Отсюда следует, что любое положительное целое число имеет ровно два таких представления с убывающим порядком ео > ei > ••• > е»: одно - счетным t, другое - с нечетным t.j

28. Доказательство может быть выполнено, как и в упр. 27. Обратите внимание, что а + Ы представляет собой произведение 1 + г и некоторого комплексного целого числа тогда и только тогда, когда а+Ь четное. Такое представление неявно связано с "кривой дракона", описанной в ответе к упр. 18.

29. Достаточно доказать, что любую совокупность {Го,Т1,Г2,...}, удовлетворяющую свойству В, можно получить с помощью "стягивания" некоторой совокупности {So, Si, S2,...}, где So = {0,1,... ,b - 1}, и что все элементы множеств Si, S2, ... кратны 6.

При доказательстве последнего утверждения можно считать, что 1 € Го и существует наименьший элемент Ь > 1, такой, что b То. Индукцией по п докажем, что если пЬ Го, то пб-f 1, пб-f 2, ..., nb + b- 1 не принадлежат никакому из множеств Г,; если же пб е Го, то же самое верно и для чисел пЫ- 1, ..., пб -f 6 - 1. Тогда искомой совокупностью будет Si = {пб I пб € Го}, S2 = Ti, 5з = Гг и т. д., откуда следует результат.

Если пб Го, то пб = to + ti Н----, где ti, <2, • • кратны б. Следовательно, to < rib

кратно б. По индукции {to + k) + ti+t2-\----есть представление числа пЬ + к при О < /с < б,

поэтому пЬ + к Tj для любого j.

Если пб € Го и О < < б, то to+ti+- . Равенство tj = nb+k не может выполняться для

j > 1, иначе пб-f 6 имело бы два представления (Ь-к)-\-----\-{пЬ+к)-\----= (пб)-)-----1-6-)----.

По индукции to mod b = к. Из представления пЬ = {to - к) + ti -i----следует to = nb + к.

[См. Nieuw Archief voor Wiskunde (3) 4 (1956), 15-17. Конечный результат получен P. А. Мак-Магоном (Р. А. MacMahon), Combinatory Anaiysis 1 (1915), 217-223.]

30. (а) Пусть Aj -множество чисел п, в представлении которых не содержится б; тогда согласно свойству единственности п & Aj тогда и только тогда, когда п + bj Aj. Следовательно, п € Aj тогда и только тогда, когда п + 2bjbk € Aj П Ак. Пусть т - количество целых чисел п € AjDAk, таких, что О < п < 2bjbk. Значит, в том же интервале найдется ровно т целых чисел, принадлежащих Aj, но не принадлежащих Ак, и ровно т, не принадлежащих ни Aj, ни Ак; поэтому 4т = 2bjbk. Следовательно, bj и bk не могут быть нечетными одновременно. Однако одно из них, разумеется, нечетно, так как нечетные числа допускают представление в бинарном базисе.

(b) Согласно п. (а) можно так перенумеровать числа Ь, чтобы Ьо было нечетным, а 61, 62, ... - четными. Тогда ряд 561, 562, ... должен также образовывать базис и эту процедуру можно повторить.

(c) Если имеется бинарный базис, то для представления числа ±2" (для больших п) при достаточно больших к необходимо получить и положительные, и отрицательные dk. Доказательство обратного утверждения приводится в следующем алгоритме.

51. [Начальная установка.] Установить <- 0.

52. [Выполнить?] Если п = О, завершить выполнение алгоритма.

53. [Выбрать.] Если число п четное, установить п <- п/2; иначе - включить в представление 2dk и установить п <- (п - dk)/2.

54. [Увеличить к.] Увеличить fe на 1 и перейти к шагу S2.

На шаге S3 приведенного алгоритма \п\ уменьшается до тех пор, пока не выполнится равенство п = -dk; следовательно, алгоритм должен завершиться.

(d) Две итерации шагов S2-S4 алгоритма приводят к преобразованию 4т -> тп, Am + 1 -> m + 5, 4m + 2 -> m + 7, 4m + 3 -> m - 1. Рассуждая, как в упр. 19, остается только показать, что алгоритм завершит работу при - 2 < п < 8; все остальные значения числа п сдвигаются в этот интервал. Для данного интервала имеем следующую структуру дерева: 3 -1 -2 ->6->8->2->-7->0и4->1->5->6. Таким образом, 1 = 7 2° - 13 • 2 + 7 2 - 13 • 2 - 13 • 2* - 13 • 2 + 7 • 2°.

Примечание. Выбор do, di, da, ... = 5, -3, 3, 5, -3, 3, ... также дает бинарный базис. Более подробно с этим вопросом можно ознакомиться в работах Math. Сотр. 18 (1964), 537-546; А. D. Sands, Acta Math. Acad. Sci. Hung. 8 (1957), 65-86.

31. (Cm. относящиеся к этому вопросу упр. 3.2.2-11, 4.3.2-13, 4.6.2-22.)

(a) Умножая числитель и знаменатель на подходящую степень 2, можно полагать, что и = (.. .u2UiUo)2 и V = (... i;2«;i«;o)2, где vo = I, являются 2-адическими целыми числами. Для определения w можно прибегнуть к следующему вычислительному методу, используя для целого числа (un-i ... «0)2 = и mod 2" обозначение и" (п > 0).

Пусть Wo = Uo и = wq. Для п = 1, 2, ... полагаем, что найдено целое число w" = (wn-i... wo)2, такое, что u" = uw" (по модулю 2"). Тогда u(+ = (по модулю 2"). Поэтому можно положить Wn = о или 1 в соответствии с тем, чему равно число («("+ - «;("+1)ад(")) mod2+i: нулю или 2".

(b) Найдем наименьшее целое число fe, такое, что 2* = 1 (по модулю 2п + 1). Тогда 1/(2п + 1) = т/(2* - 1) для некоторого целого числа т, 1 < m < 2*"". Пусть а есть fe-разрядное двоичное представление для т; тогда в двоичной системе число {О.ааа... )2, умноженное на 2п + 1, равно (0.111...)2 = 1, а в 2-адической системе {... ааа)2, умноженное на 2п + 1, равно (... 111)2 = -1.

(c) Если и рационально, скажем, и = m/(2n), где п - нечетное и положительное число, то 2-адическое представление числа и периодично, так как множество чисел с периодическим разложением содержит -1/п и замкнуто относительно операций изменения знака, деления на 2 и сложения. Наоборот, если для всех N > р соблюдается un+x = un, то 2-адическое представление числа (2- - 1)2"** и есть целое число.

(d) Квадрат любого числа вида (... ujui 1)2 имеет вид (... 001)2, поэтому сформулированное условие является необходимым. Достаточность доказывается наличием следующей процедуры вычисления v = у/п для случая, когда п mod 8 = 1.

HI. [Начальная установка.] Установить m 4- (п - 1)/8, к <- 2, vo <- 1, Vi <г- О, v <г- 1.

(При выполнении этого алгоритма получим v = {vk-i viVo)2 и v = п - 2*m.) Н2. [Преобразования.] Если m четно, установить Vk -«г- О, т <г- т/2. В противном

случае установить Vk <- 1, т <- (т - v - 2*~)/2, v <- v + 2. ИЗ. [Приращение А;.] Увеличить А; на 1 и вернуться к шагу Н2.

32. Более общий результат опубликован в журнале Math. Сотр. 29 (1975), 84-86.

33. Пусть Кп -множество всех таких п-разрядных чисел, что А:„ = \Кп\. Если множества S и Г ЯВЛЯЮТСЯ произвольными конечными множествами целых чисел, можно утверждать, что для некоторого целого числа х S ~ Т при S = Т + х, и можно записать kn{S) = \1Сп (S), где 1С„ (S) -семейство всех подмножеств Кп, принадлежащих ~ S. При п = О выполняется

кп(3) = О, однако 5 < 1, так как нуль является единственным 0-разрядным числом. При п > I и S = {si,..., Sr} имеем

ICn{S)= У и {{tib + ai,...,trb + ar}\

0<j<b (ai,...,ar)

{ti,...,tr} e Kn-ii{isi+j-ai)/b\ 1 <i<r})},

где внутреннее объединение представляет собой полные последовательности цифр (oi,... ...,аг), удовлетворяющих условию Oj = Si + j (по модулю 6) при 1 < i < г. Потребуем для однозначности определения индексов в этой формуле, чтобы ti - tii = (si - ai)/b - (sj- - Oi)/6 при 1 < i < i < r. Согласно принципу включения и исключения получаем k„{S) = Eo<j<i. Era>i(~l)"~V(i")j)> где f(S,m,j) - количество множеств целых чисел, которые могут быть выражены в виде {tib + ai,... ,trb + аг} описанным выше способом применительно к тп различным последовательностям (oi,...,ar), причем выражение суммируется по всем выборкам из тп различных последввательностей (oi,...,ar). Для полученных т различных последовательностей (of,... ,Ог) при 1 < I < тп количество таких множеств равно A;n i({(si +j -af)/b 1 < г < г, 1 < i < тп}). Итак, имеем набор множеств T{S), таких, что

k„iS)= Е CTfcn-i(r),

t€t(S)

где каждое ст есть целое число. Более того, если множество Т е T{S), то его элементы близки к элементам множества S и имеем

minT > (min5 - maxD)/6 и шахГ < (шах5 + 6 - 1 - min D)/6.

Таким образом, получены рекуррентные соотношения для последовательностей множеств {kn{S)), в которых множество 5 порождает подмножества целых чисел [1..и + 1] (в обозначениях упр. 19). Последовательность {кп) появляется в процессе формирования этих рекуррентных соотношений, так как кп = kn{S) для любого элемента множества 5. Коэффициенты Ст могут быть вычислены через несколько начальных значений kn{S), так что можно получить систему уравнений для определения производящих функций ks{z) = Ekn{S)z" = [S<1] -1-2 j:j,g7-(5)CTA:T(2) (см. J. Algorithms 2 (1981), 31-43).

Налример, при D = {-1,0,3} и 6 = 3 имеем I = - и u = , так что искомыми множествами 5 являются {0}, {0,1}, {-1,1} и { - 1,0,1}. Соответствующие соотношения для п < 3 имеют вид (1, 3, 8, 21), (0,1, 3, 8), (О, 0,1, 4) и (О, О, О, 0). Итак, получено

ko{z) = l+z{3ko{z) - koi{z)), ko2{z) = 2(A:oi(2) + 02(2)),

A;oi(2) = 20(2), /1012(2) = 0

и k{z) = 1/(1 - З2 -f 2=). Тогда кп = F2„+2 и kn{{Q,2}) = Fin-l - 1.

34. Существует единственная цепочка Qn символов {1,0,1}, такая, что п = (Qn)2 и в Qn нет ни ведущих нулей, ни последовательных ненулевых элементов: qq пусто; в противном

случае Q2n = QnO, Q4n + 1 = CKnOl, Q4n-1 = QnOl. ЛюбуЮ ЦеПОЧКу, СОДержащуЮ П,

можно преобразовать в Qn при помощи сжатия iT 01, Tl ОТ, 01... И 10... ОТ, ОТ... тт То ... 01 и добавления или исключения ведущих нулей. Так как операции сжатия не увеличивают количество цифр, отличных от нуля, то в Qn содержится наименьшее количество. [Advances in Computers 1 (1960), 244-260.] Количество i(n) ненулевых цифр в Qn -это количество единиц в обычном представлении, перед которыми сразу же помещается либо нуль, либо подстрока 00(10)*" 1 для некоторого А: > 0.

Обобщение для систем представления по основанию 6 > 2 предложено Й. фон цур Гатеном (J. von zur Gathen), ComputationaJ Complexity 1 (1991), 360-394.