AOP_Tom2 (1021737), страница 184
Текст из файла (страница 184)
Кпвсй Х Несг. Масй. 3 (1970), 66-81, 133-149. Множества Я систем счисления по основаниям (О, 1) и другим комплексньсм основаниям построены и проанализированы Д. Гаффином (Р. Со(бпес) в АММ 98 (1991), 249-255.) В статье 1. Кйсш апс1 Л, БхаЬо, Асса Яс1епс. Масб. 37 (1975), 255 — 260, показано, что основание — 42+1 приводит к системам счислг1шя с цифрами (О, 1,,42~).
Друтие свойства таких систем исследовались У. Дж. Гильбертом (1Ч. Л. С1!Ьегг) в СапааОап Х МаСЬ. 34 (1982), 1335-1348, Масй. Ыабвхгле 57 (1984), 77 — 81. В. Нортон (11. Хоггоп) предложил еще одну интересную систему счисления по основанию 2 + 1 с цифрамн (О, 1,1, -1, — 1) (Ыасй. Мабаг!пе 57 (1984), 250-25Ц. С системами счисления, основанными на более общих целых числах, можно ознакомиться в работах 1. Кйсас ап41 В. Когасв, Асса МасЬ. Асас!. Бей Нипб.
37 (1981), 159 — 164, 405-407; Асга аСЬ. Нилб. 58 (1991), 113 .120; А. Регйо, Бгас)са Бпелг. Ыагб. Нипб. 27 (1992), 169-172. 19. Если т > а или т < 1, то найдем такое а б Р, что т га а (по модулю 6); искомое представление будет представлением ги' = (ги — а)246, за которым следует а. заметим, что т > и принадлежит интервалу 1 < т' < т; ги < 1 принадлежит т < ги' < и, поэтому алгоритм конечен.
(При 6 = 2 решения нет. Представление будет единственным тогда н только тогда, когда 0 б РО неоднозначное представление появится, наприиер, когда Р = ( — 3, — 1,7), Ь = 3, так как (о)2 = (3773а)з. Нетрудно цоказатгч что при 6 > 3 имеется точно 24 решающих множеств Р, в которых ~а) < 6 для всех а б Р.
Далее, множества Р = (О, 1, 2 — 426", 3 — 42Ь", ..., Ь вЂ” 2 — сс 2Ь", 6 — 1 — Ь") порождает единственное представление для всех Ь > 3 и п > 1, где любое с„есть 0 или 1. См. Ргос. ?ЕЕЕ $ушр Сошр, АпСЬ, 4 (1978), 1 — 9; эАСМ 29 (1982), 1131-1143.) 111 1 222 20. (а) 0 111... = 1 888 ... = 18 211 ... = 182.се~в ., = = 182е~зузд~2.111 ... имеет девять представлений. (ь) Р— дробная часть .оса с ..., которая всегда принимает значения между -1/9 и +71/9. Пусть х имеет десять или более Р— - десятичных представлений. Тогда для достаточно большого Ь число 10" х имеет десять представлений, отличающихся цифрами, которые расположены левее десятичной точки: 10 х = и1 + ?"1 = .
= И1е + ?1О, ГдЕ ЛЮбое 71 есть Р— дробная часть. Ввилу единственности представления целых чисел числа и, различны, скажем, и1 « . и,о; следовательно, те — и1 > 9, но это число принадлежит интервалу 71 — 71а > 9 > 71?49 — ( — 1/9). Таким образом, мы пришли к противоречию, что и доказывает справедливость утверждении.
(с) Любое число вида О.асас, где любое а, есть — 1 или 8, равно 1 а',ас... при а,' = а, ч. 9 (более того, оно имеет еще б представлений 18.а1'ас'... и т, д.). 21. Такое представление можно получить, используя метод, аналогичный предложенному в тексте раздела для перевода в уравновешенную троичную систему счисления. В отличие от систем, рассмотренных в упр. 20, нуль может быть представлен бесчисленным количеством спсюобов, которые получаются в результате умножении иа степень ДесЯть сУммы -' + ~ ь>1( — 4-.') 10 " (или нз такого же пРедставлениЯ, но с противоположными знаками цифр).
Представлениями единицы гшужат 1-,' — —,', —,' + —,' ', 5 — 3 — — —, 5 — 4 —, + —,'", 50 — 45 — 3- — — ', 50 — 45 — 4г + —, и др, где 1 ° - 1 1 ° , , 1 1 ° 1 1- 2 2 2 1: 2 г 2 2 3 (х4-.')(10 ' + 10 + ). (АММ 57 (1950), 90.93.) 22. Полагая, что имеется приближение Ь„..
Ь16а с погрешностью 2"„" 6410" — х > 10 где С > О, покажем, как уменьшить ошибку примерно в 10 ' раз. (Процесс может быть начат с любого приближения, для которого 2 1 Ь110 > х; далее через конечное количества итераций ошибка станет меныпе 4.) Просто выбираем т > и настолько большим, чтобы десятичное представление числа — 10'"о имело единицу в позиции 10 ' и не имело единица позициях 10 '~', 10 'л~, ..., 10".
Тогда 10 о+(некоторая подходящая сумма степеней 10 между 1О и 10") + 2„л Ьл10 2 л ебл10 — 10 23. Пусть лгножество 5 = (2 лл, алЬ " [ ал б Р) замкнуто (как в упр. 18), следовательно, оно изллеримо. Так как 65 = () о(а + 5), имеем Ьр(5) = р(Ь5) < ~, р гл(а + 5) = х „во р(5) = Ьр(5), и поэтому должно быть справедливо лл((а + 5) О (а' + 5)) = О, если а ф а' б Р. Тогда множество Т вЂ” множество иеры нуль, если 0 б Р, так как множество Т является объединением множеств вида Ь" (и + ((а + 5) Й (а' + 5))), а Ф а', каждое нз которых — меры нуль. С другой стороны, как отмечал К.
А. Брэкк (К. А. Вгаййе). каждое вещественное число (в системе счисления, рассмотренной в упр. 21) имеет бесконечное количество представлений. [Множество Т не может быть пустым, поэтому вещественные числа не могут быть записаяы как счетное объединение замкнутых, разомкнутых и граничных множеств (см. ЛММ 84 (1977), 827-828; более детальный анализ приводится в работе Ресйогйе1с, АММ 97 (1990), 408-411).
Если множество Р состоит из элеиентов, меньших Ь, то множество представлений чисел по основанию Ь и цифры из множества Р имеют меру нуль. Если множество Р состоит из элементов, ббльших, чем Ь, и из вещественных чисел, то оно имеет бесконечную меру.] 24. (2а 10" + а' [ О < а < 5,0 < а' < 2) или (5а' 10" + а [ 0 < а < 5,0 < а' < 2) для 6 > О. [Р. ей Грэхэм (Е. Е.
Сгабаш) показал, что не существует другого множества целых цифр, удовлетворяющих этим свойствам. Эндрю Олдыжко (Апбгеи 001уейо) доказал, что ограничение в рассмотрении множеств целых чисел излишне в том смысле, что если два наименьших элемента множества Р являются 0 и 1, то все цифры должны быть целыми. Доказательство. ПУсть 5 = (2 лсе алЬ" [ ал б Р) — множество "дРобных частей" и пУсть Х = ((а„... аа)л [ ал б Р) — множество "полных чисел". Тогда [О., оо) = 0е х(х+ 5) и (х+5) О(х + 5) при х Ф х' б Х имеет меру нуль. Получим (О .. 1) С 5 и докажем индукцией по т, что (т .. т + 1) С хм + 5 длЯ некотоРого хм б Х ПУсть хм б Х таково, что длн любого е > 0 меРа (т .. т + е) С1 (хм + 5) пазожллтельна. Твгда х < т и хм должно быть целым независимо от величины перекрытия множеством х1, 1+5 множества х +5.
Если хм > О, то нз того, что (т — х ..т — х +1)715 имеетположительнУю меРУ, по индУкции следует, что эта мера равна 1 и (т.. гп + 1) С хм + 5, так как множество 5 замкнутое. При х = 0 н (т..т+ 1) Я 5 мы должны получить т < х' < т+ 1 для любого х' б Х, где (т .. х' ) С 5; но тогда 1+ 5 перекрывает х',„+ 5. (См. Ргос. Ьолдоо Малй. 5ос. (3) 18 (1978), 581-595.)) Примечание. Если снять ограничение 0 б Р, еоэникнегн иного других достаточно интересных ситуаций, в частности (1, 2, 3,4,5, б, 7, 8,9, 10), (1,2,3,4, о, 51, 52,53,54,55) и (2,3,4,5,0,52,53,54,55,55). Если же допустить наличие отрицательных цифр, то при помощи метода, описанного в упр.
19, можно найти много других решений задачи, а также множества, содержащие необычные числа наподобие (-1,0, 1,2,3,4, 5,0, 7, 18), которые не удовлетворяют оговоренным условинм. Появляются предпосылки для поиска изящных решений для множеств с отрицательными цифрами. 25. Положительное число, представление которого по основанию Ь содержит т последовательных цифр (6 — 1), расположенных справа от разделяющей точки, должно иметь вид с/Ь" + (Ь вЂ” В)/6"т, где с и и — неотрицательные целые числа и 0 < В < 1. Поэтому, если и/о имеет такой вид, значит, равенство Ьм+"о = Ь си+Ь и-Ви выполнено.
Следовательно, Ве есть целое число, кратное Ь . Однако 0 < Ве < е < 6 . (При 0 < а < Ь вЂ” 1 могут встречаться произвольно длинные ряды цифр ааааа, например, в представлении чисел а/(6 — 1).) 26. Доказательство достаточности получается непосредственным обобщением на случай основания 6 обычного доказательства. Доказательство необходимости разбивается на две части. Если для некоторого и число л3л л больше 2 »<„ с»!3», то для малых е число О„,.л — г не допускает такого представления. Если й »л < эигл»й„с»,6» для всех и, но равенство выполняется не всегда, то можно показать, что для некоторого х существуют два представления (см. Тгапзасцопз оУ гЬе йоуа7 Бос!елу оу Салаг(а, эег!еэ П1, 46 (1952), 45-55). 27.
Доказательство выполняется индукцией по и. Если и четно, то должно быть ее > О и искомый результат получается по индукции, так как и/2 имеет единственное представление такого типа. Если п нечетно, то должно быть ее = О и задача сводится к представлению числа -(и — 1)/2. Если это последнее равно либо О, либо 1, то, очевидно, существует только один способ решения задачи.
В противном случае по индукции доказывается, что число имеет единственное представление. [Отсюда следует, что любое положительное целое число имеет ровно деа таких представления с убывающим порядком ее > ел » ел. одно — с.четным 1, другое— с нечетнылл 1,) 26. Доказательство может быть выполнено, как и в упр. 27. Обратите внимание, что а+ Ь! представляет собой произведение 1+ л и некоторого комплексного целого числа тогда и только тогда, когда а+6 четное. Такое представление неявно связано с "кривой дракона", описанной в ответе к упр. 18. 29.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
