13. (1.909090 ... )-io = (0.090909 ... )-io = .

14. 113 2 1 [5 - 4i] 113 2 1

-4+2t

[5-4i]

113 2 1 112 0 2 12 12 3 113 2 1 113 2 1

0 1 0 3 1 1 2 0 1

[9 - 40i

-4-8г

l+2i

Рис. A-6. Фундаментгшьная область

15. [- тг] прямоугольник справа (рис А-6). для мнимочетверичных чисел.

16. Соблазнительно попробовать сделать это самым простым способом, предписав реализацию переносов по правилу 2 = (1100),-i, но это приведет к непрекращающейся процедуре (зацикливанию) при попытке добавления единицы к числу (lllOl)i-i = -1.

В приведенном ниже решении предлагаются четыре алгоритма (для сложения и вычитания 1 и г). Если а - строка из нулей и единиц, то полагается, что а - такая строка из нулей и единиц, что {a)i-i - {Q)i-\ + 1. Аналогичным образом определяются

а , q, а путем замещения +1 соответственно на -1, +i и -г. Тогда

(aOf =q1;

(axlf = ахО. (al)- =аО.

(аО)~=а1; (q1)- = ао.

Здесь х означает О или 1 и цепочки при необходимости дополняются слева нулями. Все эти процедуры очевидным образом заканчиваются. Таким образом, любое число вида а + Ы с целыми аи Ь представимо в системе по основанию i - 1.

17. Нет (вопреки упр. 28); число -1 не представимо в этой системе. Это можно доказать, построив соответствующее множество S, как на рис. 1. Имеем представления -г = (0.1111...)i+i,i = (100.1111...)i+i.

18. Пусть So - множество точек (a70605a4a3a20ioo)i-i, в котором каждое о*, есть О или 1. (Поэтому множество So состоит из 256 внутренних точек, отмеченных на рис. 1, после 16-кратного увеличения.) Покажем сначала, что множество S замкнутое. Пусть 2/1,2/2,... - произвольная последовательность точек множества S. Имеется

где каждое апк принадлежит So- Построим дерево, вершинами которого будут наборы (aui,... ,Опг) для 1 < г- < п, причем одна вершина является родителем, если она является по отношению к этой вершине начальным поднабором. Согласно теореме о бесконечных деревьях (теорема 2.3.4.ЗК) это дерево имеет бесконечный путь (01,02,03,...); соответственно E*.>i о»-16~* есть предельная точка множества {2/1,2/2, • • •}, принадлежащая S.

В соответствии с ответом к упр. 16 все числа вида (o-l-6i)/16* представимы, если о и 6 целые. Поэтому при действительных х и у и к > 1 число Zk = ([16*ж] + [16*j/Jt)/16* для некоторых целых тип принадлежит S + т + ni. Можно показать, что всякая представимая точка вне S должна принадлежать множеству S + т + пг при (т, п) ф (О, 0). Соответственно, если \х\ и \у\ фиксированы и к достаточно велико, получаем, что z/t £ 5 и Ит/с юо Zk = X + уг принадлежит множеству S.

[В. Мандельброт (В. Mandelbrot) назвал множество S двуглавым драконом, подметив, что оно, по существу, формируется путем объединения двух "кривых дракона" (см. книгу

Fractals: Form, Chance, and Dimension (San Francisco; Freeman, 1977), 313-314, в которой Мандельброт установил, что размерность границы равна 21gx к. 1.523627, где х =

1 + 2х~ ~ 1.69562. Другие свойства кривой дракона описаны в статье С. Davis and D. Е. Knuth J. Recr. Math. 3 (1970), 66-81, 133-149. Множества S систем счисления по основаниям {0,1} и другим комплексным основания.м построены и проанализированы Д. Гоффином (D. Goffinet) в АММ 98 (1991), 249-255.]

В статье I. Katai and J. Szabo, Acta Scient. Math. 37 (1975), 255-260, показано, что основание -d + i приводит к системам счисления с цифрами {0,1,..., d}. Другие свойства таких систем исследовались У. Дж. Гильбертом (W. J. Gilbert) в Canadian J. Math. 34 (1982), 1335-1348; Math. Magazine 57 (1984), 77-81. В. Нортон (V. Norton) предложил еще одну интересную систему счисления по основанию 2 + i с цифрами {0,1, г,-1,-i} [Math. Magazine 57 (1984), 250-251]. С системами счисления, основанными на более общих целых числах, можно ознакомиться в работах I. Katai and В. Kovacs, Acta Math. Acad. Sci. Hung. 37 (1981), 159-164, 405-407; Acta ath. Hung. 58 (1991), 113-120; A. Petho, Studia Scient. Math. Hung. 27 (1992), 169-172.

19. Если m > и или m < /, то найдем такое а & D, что т = а (по модулю 6); искомое представление будет представлением т = (т - а)/Ь, за которым следует а. Заметим, что т > и принадлежит интервалу I < т < т; т < I принадлежит т < т < и, поэтому алгоритм конечен.

[При b = 2 решения нет. Представление будет единственным тогда и только тогда, когда О € jD; неоднозначное представление появится, например, когда D = {-3,-1,7}, b = 3, так как (а)з = (3773а)з. Нетрудно показать, что при 6 > 3 имеется точно 2*" решающих множеств D, в которых о < 6 для всех а е D. Далее, множество D = {О, 1,

2 - аЬ", 3 - «зб", • • •, b - 2 - Cb-ib", 6-1-6"} порождает единственное представление для всех 6 > 3 и п > 1, где любое Cj есть О или 1. См. Proc. IEEE Symp. Сотр. Arith. 4 (1978), 1-9; JACM 29 (1982), 1131-1143.]

20. (a) О.Ш ... = 1.888 ... = 18.7 = Щ-111 •• = •• = 1843MII ... имеет девять представлений, (b) D - дробная часть .oioa ..., которая всегда принимает значения между -1/9 и +71/9. Пусть X имеет десять или более D - десятичных представлений. Тогда для достаточно большого к число lOx имеет десять представлений, отличающихся цифрами, которые расположены левее десятичной точки: 10*" = щ + /i = • • = пю + /ю, где любое fj есть D - дробная часть. Ввиду единственности представления целых чисел числа rij различны, скажем, ni < • • < пю; следовательно, пю - щ > 9, но это число принадлежит интервалу Д - /ю > 9 > 71/9 - (-1/9). Таким образом, мы пришли к противоречию, что и доказывает справедливость утверждения, (с) Любое число вида О.оюа ..., где любое aj есть -1 или 8, равно l.oiOj ... при aj = + 9 (более того, оно имеет еще 6 представлений iS.aioj ... и т. д.).

21. Такое представление можно получить, используя метод, аналогичный предложенному в тексте раздела для перевода в уравновешенную троичную систему счисления.

В отличие от систем, рассмотренных в упр. 20, нуль может быть представлен бесчисленным количеством способов, которые получаются в результате умножения на степень десять суммы + Efe>i(~4) • 10~* (или из такого же представления, но с противоположными знаками цифр). Представлениями единицы служат l - *, 5 + 5*, 5 - 3 - 1, 5 - 4 + 1*, 50 - 45 - 3 - *, 50 - 45 - 4 + * и др., где if = (±4i)(10- +10" + •••)• [АММ 57 (1950), 90-93.]

22. Полагая, что имеется приближение бп ... 6160 с погрешностью ЕГ=о Ю* - х > 10~, где t > О, покажем, как уменьшить ошибку примерно в 10~ раз. (Процесс может быть начат с любого приближения, для которого ЕГ=о*1* далее через конечное количество итераций ошибка станет меньше е.) Просто выбираем т > п настолько

большим, чтобы десятичное представление числа - 10"q имело единицу в позиции 10 и не имело единиц в позициях 10"", 10", ..., 10". Тогда 10"q + (некоторая подходящая сумма степеней 10 между 10"" и 10") + Ек=о"10 и ELolO* - 10".

23. Пусть множество 5 = {E/c>i "fc"* <ik € D} замкнуто (как в упр. 18), следовательно, оно измеримо. Так как 65 =~[jaeD( + ): имеем 6р(5) = fi(bS) < 12аев/( + S) = Eo€d/() ~ bfi{S), и поэтому должно быть справедливо р((а + 5) П (о + 5)) = О, если а ф а D. Тогда множество Г - множество меры нуль, если О € D, так как множество Г является объединением множеств вида 6*(п + ((о + 5) П (а + 5))), а ф а, каждое из которых - меры нуль. С другой стороны, как отмечал К. А. Брэкк (К. А. Вгакке), каждое вещественное число (в системе счисления, рассмотренной в упр. 21) имеет бесконечное количество представлений.

[Множество Т не может быть пустым, поэтому вещественные числа не могут быть записаны как счетное объединение замкнутых, разомкнутых и граничных множеств (см. АММ 84 (1977), 827-828; более детальный анализ приводится в работе Petkov§ek, АММ 97 (1990), 408-411). Если множество D состоит из элементов, меньших 6, то множество представлений чисел по основанию Ь и цифры из множества D имеют меру нуль. Если множество D состоит из элементов, больших, чем Ь, и из вещественных чисел, то оно имеет бесконечную меру.]

24. {2о • 10* + а I О < а < 5,0 < а < 2} или [Ъа! • 10* + а О < а < 5, О < о < 2} для /с > 0. [Р. Л. Грэхэм (R. L. Graham) показал, что не существует другого множества целых цифр, удовлетворяющих этим свойствам. Эндрю Одлыжко (Andrew Odlyzko) доказал, что ограничение в рассмотрении множеств целых чисел излишне в том смысле, что если два наименьших элемента множества D являются О и 1, то все цифры должны быть целыми.

Доказательство. Пусть 5 = {Et<o I } -множество "дробных частей" и пусть А = {{an .. оо)ь I а/с € D} -множество "полных чисел". Тогда [О.. оо) = UieA-( + 5) и (ж+5) П (ж + 5) при X ф х е X имеет меру нуль. Получим (О .. 1) С 5 и докажем индукцией по т, что (т.. m + 1) С Жт + 5 для некоторого Хт € X. Пусть Жт € А таково, что для любого б > О мера (т. .т + е)П {Хт + 5) положительна. ТЪгда Хт < т и Хт должно быть целым независимо от величины перекрытия множеством xmi множества Жт +5. Если

Хт > О, ТО из ТОГО, ЧТО (гП - Жт . - Жт + 1) П 5 И.меет ПОЛОЖИТеЛЬНуЮ меру, ПО ИНДуКЦИИ

следует, что эта мера равна 1 и (т.. m + 1) С Жт + 5, так как множество 5 замкнутое. При Хт = .0 и (т .. m + 1) 2 5 мы должны получить т < хт < т + 1 для любого хт € X, где (т .. хт) С 5; но тогда 1 + 5 перекрывает хт + 5. (См. Ргос. London Math. Soc. (3) 18 (1978), 581-595.)]

Примечание. Если снять ограничение О € D, возникнет много других достаточно интересных ситуаций, в частности {1,2,3,4,5,6,7,8,9,10}, {1,2,3,4,5,51,52,53,54,55} и {2,3,4,5,6,52,53,54,55,56}. Если же допустить наличие отрицательных цифр, то при помощи метода, описанного в упр. 19, можно найти много других решений задачи, а также множества, содержащие необычные числа наподобие {-1,0,1, 2,3, 4, 5,6, 7,18}, которые не удовлетворяют оговоренным условиям. Появляются предпосылки для поиска изящных решений для множеств с отрицательными цифрами.

25. Положительное число, представление которого по основанию Ь содержит т последовательных цифр (6- 1), расположенных справа от разделяющей точки, должно иметь вид с/6" + (6"" - б)/6""", где с и п - неотрицательные целые числа и О < б < 1. Поэтому, если u/v имеет такой вид, значит, равенство 6"""и = 6"си+6"и-би выполнено. Следовательно, ви есть целое число, кратное 6"". Однако О < < и < 6"". (При О < о < 6 - 1 могут встречаться произвольно длинные ряды цифр ааааа, например, в представлении чисел а/(6-1).)