Элементарная математика
УДК 373:512 ББК 22.14я72 Е.В. Хорошилова Х82 Публикуется по решению редакционно-издательского совета Московского государственного университета имени М.В. Ломоносова Р е ц е н з е н т ы: ЭЛЕМЕНТАРНАЯ В.А. Ильин, академик РАН, зав. кафедрой общей математики. Показать больше
УДК 373:512 ББК 22.14я72 Е.В. Хорошилова Х82 Публикуется по решению редакционно-издательского совета Московского государственного университета имени М.В. Ломоносова Р е ц е н з е н т ы: ЭЛЕМЕНТАРНАЯ В.А. Ильин, академик РАН, зав. кафедрой общей математики факультета вычислительной математики и кибернетики (ВМиК) МГУ; Е.И. Моисеев, академик РАН, декан ВМиК МГУ; А.Б. Будак, доцент ВМиК МГУ; Л.В. Натяганов, доцент механико-математического факультета МГУ; МАТЕМАТИКА П.И. Пасиченко, доцент механико-математического факультета МГУ; В.Н. Деснянский, профессор, зав. кафедрой вычислительной математики МГУ путей сообщения Учебное пособие Хорошилова Е.В. для старшеклассников Х82 Элементарная математика: Учеб. пособие для старшеклассников и аби- туриентов. Часть 1: Теория чисел. Алгебра. – М.: Изд-во Моск. ун-та, и абитуриентов 2010. – 472 с. ISBN 978–5–211–05322–9 (Ч.1) ISBN 978–5–211–05320–5 Учебное пособие предназначено для повторения и систематизации знаний школьника при подготовке к экзаменам Спрятать
- Похожие публикации
- Поделиться
- Код вставки
- Добавить в избранное
- Комментарии
Математики достигли прорыва в изучении «опасной» задачи
Опытные математики советуют новичкам держаться подальше от гипотезы Коллатца. Они называют её песней сирен: попади под её влияние, и можешь уже никогда не добраться до осмысленной работы.
Гипотеза Коллатца, возможно, простейшая из нерешённых задач математики – именно это и делает её такой предательски притягательной.
«Это очень опасная задача. Люди становятся одержимыми ею, при том, что она совершенно невозможна», — сказал Джеффри Лагариас, математик из Мичиганского университета, эксперт по гипотезе Коллатца.
Но в 2019 году один из лучших математиков мира осмелился подступиться к ней, и получил самый значимый из всех результатов, что были достигнуты за несколько десятилетий.
8 сентября 2019 Теренс Тао опубликовал доказательство, где показано, что гипотеза Коллатца, по меньшей мере, «почти» верна «почти» для всех чисел. И хотя результат Тао не является полным доказательством гипотезы, это очень серьёзный прорыв для задачи, не так-то легко раскрывающей все свои секреты.
«Я не ожидал решить задачу полностью, — сказал Тао, математик из Калифорнийского университета в Лос-Анджелесе. – Но у меня получилось сделать больше, чем я ожидал».
Головоломка Коллатца
Лотар Коллатц, вероятно, высказал одноимённую гипотезу в 1930-х годах. Задача звучит, как фокус для вечеринок. Возьмите любое число. Если оно чётное, поделите его на два. Если нечётное, умножьте на три, прибавьте один. Получится новое число. Примените те же правила для него. Гипотеза говорит о том, что произойдёт, если настойчиво повторять этот процесс.
Интуиция подсказывает, что начальный номер влияет на конечный результат. Возможно, некоторые числа в итоге будут уменьшаться до 1. Возможно, другие числа будут увеличиваться до бесконечности.
Однако Коллатц предсказал, что это не так. Он предположил, что если вы начнёте с положительного целого числа, и достаточно долго будете повторять указанную последовательность, то с любого начального числа придёте к 1. А придя к единице, вы попадёте в ловушку правил гипотезы, и войдёте в бесконечную петлю: 1, 4, 2, 1, 4, 2, 1, и так далее, до бесконечности.
С годами многих любителей задач притягивала привлекательная простота гипотезы Коллатца, или «задачи 3х+1», как её ещё называют. Математики проверили уже квинтиллион примеров (это число с 18 нулями), не найдя ни единого исключения из предсказания Коллатца. Вы и сами можете попытаться проверить несколько примеров с любым из множества имеющихся в интернете «калькуляторов Коллатца». В интернете полно необоснованных любительских доказательств гипотезы, авторы которых утверждают, что им удалось её доказать или опровергнуть.
«Вам нужно только уметь умножать на 3 и делить на 2, и вы уже можете начать играться с ней. И это очень заманчиво», — сказал Марк Чамберленд, математик из Колледжа Гриннела, записавший популярное на YouTube видео об этой задаче под названием «Простейшая из невозможных задач».
А вот истинных доказательств немного.
В 1970-х математики показали, что почти все последовательности Коллатца – список чисел, которые вы получаете при повторении процесса – в итоге приходят к числу меньшему, чем начальное. Это было слабое свидетельство того, что почти все последовательности Коллатца приводят к 1, но тем не менее, оно было. И с 1994 года до полученного в 2019 году результата Тао, рекорд по демонстрации минимального значения удерживал Иван Корец. Другие работы сходным образом пытались атаковать задачу, не приближаясь к её главной цели.
«Мы, на самом деле, не понимаем вопроса Коллатца достаточно хорошо, поэтому значительных работ по этому вопросу не было», — сказал Каннан Саундарараджан, математик из Стэнфордского университета, работавший над этой гипотезой.
Тщетность этих попыток привела многих математиков к заключению, что эта гипотеза просто недоступна при текущем уровне знаний, и что им лучше тратить своё время на другие исследования.
«Задача Коллатца известна своей сложностью – настолько, что математики обычно предваряют каждое её обсуждение предупреждением не тратить на неё время», — сказал Джошуа Купер из университета Южной Каролины.
Неожиданный совет
Впервые Лагариас заинтересовался этой гипотезой, будучи студентом, не менее 40 лет назад. Десятилетиями он был неофициальным куратором всего, что с ней связано. Он набрал целую библиотеку связанных с нею работ, и в 2010 опубликовал некоторые из них в виде книги под названием: «Решающий вызов: задача 3х +1».
«Теперь я гораздо больше знаю об этой задаче, и всё равно могу сказать, что решить её невозможно», — сказал Лагариас.
Обычно Тао не тратит своё время на невозможные задачи. В 2006 году он получил Филдсовскую премию, высшую награду по математике, и считается одним из лучших математиков своего поколения. Он привык решать задачи, а не гоняться за воздушными замками.
«Это риски, связанные с профессией математика, — сказал он. – Можно стать одержимым одной из больших известных задач, находящихся за пределами возможностей любого человека, и потерять кучу времени».
Однако у Тао не всегда получается противостоять искушениям из этой области. Каждый год он тратит один-два дня на самые известные из нерешённых задач по математике. С годами он делал несколько подходов и к гипотезе Коллатца, но безуспешно.
Затем в августе анонимный читатель оставил в блоге Тао комментарий. Он предложил попробовать решить гипотезу Коллатца «почти для всех» чисел, не пытаясь полностью доказать её.
«Я не ответил, однако это заставило меня снова задуматься об этой задаче», — сказал Тао.
И он понял, что гипотеза Коллатца была в некотором роде похожа на особые типы уравнений – дифференциальные уравнения в частных производных – появлявшихся в наиболее значительных результатах, полученных им за время его карьеры.
Входы и выходы
Дифференциальные уравнения в частных производных (ДУЧП) можно использовать для моделирования многих из наиболее фундаментальных физических процессов во Вселенной, вроде эволюции жидкостей или прохождении гравитационных волн сквозь пространство-время. Они появляются в ситуациях, когда будущее положение системы – например, состояние пруда через пять секунд после броска в него камня – зависит от вкладов двух или более факторов, типа вязкости и скорости воды.
Казалось бы, у сложных ДУЧП есть мало что общего с таким простым арифметическим вопросом, как гипотеза Коллатца.
Но Тао понял, что у них есть нечто общее. В ДУЧП можно подставить значения, получить другие значения, повторить процесс – и всё это для понимания будущего состояния системы. Для каждого заданного ДУЧП математикам нужно знать, приведут ли начальные значения на входе к бесконечным значениям на выходе, или же уравнения всегда будут выдавать конечные значения, вне зависимости от начальных.
Теренс Тао, вдохновлённый комментарием в своём блоге, достиг крупнейшего за десятилетия прогресса в изучении гипотезы Коллатца
Для Тао эта цель была того же порядка, как и то, всегда ли вы получите одно и то же значение (1) из процесса Коллатца, вне зависимости от начального значения. В результате он понял, что техники изучения ДУЧП могут подойти для изучения гипотезы Коллатца.
Одна особенно полезная техника использует статистический способ изучения долговременного поведения небольшого количества начальных значений (что-то типа небольшого количества начальных конфигураций воды в пруду) и экстраполирует результат на долгосрочное поведение всех возможных начальных конфигураций пруда.
В контексте гипотезы Коллатца представим, что мы начали с большой выборки чисел. Наша цель – изучить, как эти числа ведут себя, когда мы применяем к ним процесс Коллатца. Если почти 100% чисел в выборке приходят к 1 или очень близко к 1, можно заключить, что почти все числа будут вести себя так же.
Но чтобы это заключение было обоснованным, нужно очень тщательно составить выборку. Эта задача похожа на составление выборки участников голосования на выборах президента США. Для тщательного составления выборки из всей популяции нужно использовать взвешенные пропорции для республиканцев и демократов, мужчин и женщин, и так далее.
У чисел есть собственные «демографические» параметры. Нечётные и чётные числа, числа, делящиеся на 3, и числа, отличающиеся друг от друга ещё более хитрыми способами. Создав выборку чисел, можно сделать так, чтобы в неё входили определённые тип чисел, и не входили другие, по взвешенному принципу – и чем лучше вы выберете веса, тем точнее будут ваши умозаключения по поводу всех чисел в целом.
Взвешенный выбор
Задача Тао была гораздо сложнее, чем просто понять, как нужно создавать изначальную выборку чисел с нужными весами. На каждом шагу процесса Коллатца числа, с которыми вы работаете, меняются. Одно очевидное изменение состоит в том, что почти все числа из выборки уменьшаются.
Другое, возможно, менее очевидное изменение состоит в том, что числа могут начать скапливаться в группы. К примеру, можно начать с красивого равномерного распределения чисел от одного до миллиона. Но через пять итераций числа, скорее всего, сконцентрируются на нескольких небольших интервалах числовой прямой. Иначе говоря, можно начать с хорошей выборки, которая через пять шагов будет безнадёжно искажена.
«Обычно можно ожидать, что распределение после итерации будет полностью отличаться от начального», — сказал Тао. Однако ключевой его идеей было то, как можно создать выборку чисел, по большей части сохраняющих свои оригинальные веса в процессе Коллатца.
К примеру, начальная выборка Тао взвешена так, чтобы в ней не было чисел, делящихся на три, поскольку процесс Коллатца всё равно довольно быстро устраняет такие числа. Некоторые другие веса, выбранные Тао, оказываются сложнее. Он отдаёт предпочтение числам, остаток которых от деления на 3 составляет 1, и отходит от чисел, остаток которых от деления на 3 составляет 2.
В итоге выборка, с которой начинает Тао, сохраняет свой характер даже после начала процесса Коллатца.
«Он обнаружил способ продолжить этот процесс так, чтобы после нескольких шагов всё ещё было понятно, что происходит, — сказал Саундарараджан. – Когда я впервые увидел эту работу, я очень обрадовался и решил, что она потрясающая».
Тао использовал свою технику назначения весов, чтобы доказать, что почти все начальные значения – не менее 99% — в итоге приходят к величине, очень близкой к 1. Это позволило ему сделать вывод о том, Что 99% начальных значений, больших, чем квадриллион, в итоге приходят к величинам, меньшим 200.
Это, возможно, самый сильный результат в долгой истории этой гипотезы.
«Это великолепный прорыв в наших знаниях о том, что происходит с этой задачей, — сказал Лагариас. – Это определённо лучший результат за очень долгое время».
Метод Тао почти наверняка не способен добраться до полного доказательства гипотезы Коллатца. Причина в том, что его начальная выборка всё же немного искажается после каждого шага. Искажение будет минимальным, пока в выборке всё ещё содержатся множество разных значений, далёких от 1. Но в процессе Коллатца все числа в выборке начинают стремиться к одному, и небольшое искажение становится всё больше – так же, как небольшая ошибка в подсчётах результата голосования не имеет большого значения в случае крупной выборки, но сильно влияет на результат, когда выборка мала.
Любое доказательство полной гипотезы, скорее всего, будет основано на другом подходе. В итоге, работа Тао одновременно является и триумфом, и предостережением всем интересующимся: как только вам кажется, что вы загнали задачу в угол, она ускользает.
«К гипотезе Коллатца можно подобраться сколь угодно близко, но она всё равно остаётся недостижимой», — сказал Тао.
- гипотеза Коллатца
- загадки
- Занимательные задачки
- Математика
- Научно-популярное
ВВЕДЕНИЕ
Устройства микропроцессорной техники (компьютеры, ноутбуки, сканеры, принтеры, модемы, мониторы, плоттеры и т.д.) основаны на использовании двоичной системы счисления. Однако двоичная система счисления имеет ряд недостатков, которые влияют на скорость работы процессора. Самый существенный из них – это проблематичное представление отрицательных чисел.
В десятичной системе счисления проблем с представлением отрицательного числа нет – мы помечаем их знаком, которые принято называть «минус».Добавление одного знака в десятичной системе счисления к уже имеющимся десяти (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) особой роли не играет. Однако, если добавить к двум уже имеющимся знакам двоичной системы (0, 1) еще один, то количество знаков увеличится в полтора раза!
Одним из способов преодоления проблемы представления отрицательных чисел является использование симметричной (уравновешенной) системы счисления.
В своё время были разработаны и даже выпущены в серию вычислительные машины, работающие на уравновешенной троичной системе счисления (например, ЭВМ «Сетунь», который был разработан в вычислительном центре МГУ в 1959 году). Данный компьютер поразил рациональностью технических решений. Однако его выпуск прекратился в связи с тенденцией использования в интегральных схемах двоичной системы счисления.
В данном учебном пособии будет подробно описана именно уравновешенная троичная система счисления и её преимущества перед другими системами счисления.
О системах счисления
Система счисления — это правила записи чисел и правила выполнения операций над ними.
В течении многих столетий десятичная система счисления показала свои преимущества и постепенно вытеснила другие системы счисления из научной и общекультурной среды.
Однако в информатике наиболее удобной для технической реализации оказалась двоичная система счисления, а для некоторых применений — шестнадцатеричная система счисления. Во времена восьмиразрядных компьютеров, в которых информация передавалась и обрабатывалась порциями по восемь бит, использовалась и восьмеричная система счисления, однако с развитием 16–, 32– и 64–разрядных компьютеров восьмеричная система вышла из употребления.
Двоичная, восьмеричная, десятичная и шестнадцатеричная системы счисления имеют много общего. Фактически они отличаются только основанием системы счисления p = 2, p=8, p=10 или p=16, а также наборов цифр, которые содержат соответственно две, восемь, десять или шестнадцать цифр. В двоичной и восьмеричной системах счисления используются сокращенные наборы цифр 0..1 и 0..7 соответственно, при этом цифры приобретают несколько другие свойства по сравнению с десятичной си-
Пример 1. В двоичной системе счисления следующим числом за числом, состоящим из одной цифры 1, является число 102 .
Пример 2. В восьмеричной системе счисления следующим числом за числом, состоящим из одной цифры 7, является число 108 .
В обоих примерах нижний индекс обозначает основание системы счисления.
В шестнадцатеричной системе счисления приходится изобретать недостающие шесть цифр, и люди решили эту проблему просто — в качестве цифр стали использовать, кроме традиционных 0..9 символы A, B, C, D, E, F.
Что объединяет указанные системы счисления?
Любое целое неотрицательное число можно представить в виде суммы выражений di · p i . Сколько таких выражений потребуется — зависит от величины самого числа и от основания системы счисления p = 2, p = 8, p = 10 или p = 16.
Примечание. Выбор символов не является случайным.Символ d происходит от английского ”digit” – цифра, символ происходит от английского ”power” – степень, символ i происходит от английского ”index” – индекс, порядковый номер.
Для p = 2 число объектов будет записано как:
1 · p 3 +1 · p 2 +0 · p 1 +0 · p 0 ,
1 · 2 3 +1 · 2 2 +0 · 2 1 +0 · 2 0 .
Краткая запись 11002 .
Для p = 8 число объектов будет записано как:
Краткая запись 148 .
Для p = 10 число объектов будет записано как:
Рис. 1: Число, выражающее количество объектов, и записи этого числа в различных системах счисления
1 · 10 1 +2 · 10 0 ,
и это число нам давно знакомо — это 12, которое читается как «двенадцать».В слове «двенадцать» звучит «две над десять», то есть «один десяток и ещё две единицы».
Наконец, для p = 16 число объектов будет записано как С · p 0 , то есть С · 16 0 , то есть просто C 16 . В общем случае используют многоточие, которое указывает, что число слагаемых выражений зависит от ситуации:
di · p i + . + d 2 · p 2 + d 1 · p 1 + d 0 · p 0 .
Такая запись называется развернутойзаписьючисла, а di. d 2 d 1 d 0 — называется краткой или естественной записью числа.
В случае неопределенности в краткой записи числа указывают основание системы счисления, как нижний индекс. 11002 = 148 = 1210 = С 16 — это одно и то же число. Важно то, что каждая из указанных систем счисления позволяет выразить все целые неотрицательные числа 0,1. а также с помощью некоторых ухищрений записать и другие числа. (На самом деле это не совсем так. Оказывается, есть числа, о наличии которых мы знаем, но записать их абсолютно точно в позиционных системах счисления не можем. Такие числа называются трансцендентными. Некоторые из них имеют персональные имена, например, знаменитое π . Обычно мы заменяем их на некоторые приближения, например, 3.14).
Можно рассматривать и системы счисления с другими основаниями: p = 3, p = 4, p = 5, и т.д. В компьютерной технике они не применяются, однако их изучение повышает нашу общую культуру, развивает математические и общеинтеллектуальные способности, и в частности, позволяет увереннее работать с компьютерными системами счисления (двоичная, шестнадцатеричная).
1. Что называется ”системой счисления”?
2. Какая запись числа называется ”развёрнутой”?
3. В чем отличие ”развёрнутой” записи числа от ”краткой”?
4. Как вы думаете, сколько систем счисления существует?
Задачи для повторения
№1. Какая минимальная система счисления может быть у числа d, если:
№2. Напишите развёрнутую запись следующих чисел:
№3. Переведите число d с основанием системы счисления p в десятичную систему счисления, если:
№4. Переведите числа из десятичной системы счисления в двоичную, восьмеричную, шестнадцатеричную системы счисления:
1) 203; 2) 523; 7) 763; 4) 943.
№5. Среди приведённых ниже трёх чисел, записанных в различных системах счисления, найдите максимальное и запишите его в ответе в десятичной системе счисления:
Глава 1. Троичная уравновешенная система счисления
§1. Определение троичной уравновешенной
Выше уже было упомянуто, что кроме традиционных систем счисления (двоичная, восьмеричная, шестнадцатеричная) существует троичная система счисления, которая состоит из трех цифр: 0, 1, 2.
Также троичная система счисления может быть представлена с помощью чисел 1, 0, -1 (для удобства отрицательную единицу будем обозначать с надчеркиванием
( 1 ), чтобы избежать путаницы в арифметических операциях). Данный вид троичной системы счисления называется симметричной или уравновешенной.
Троичная уравновешенная система счисления (3УСС) — это система счисления с основанием три, но использующая для записи числа 1,
Троичная уравновешенная система счисления была представлена Леонардо Пизано Фиббоначи для решения ”задачи о гирях”. Именно решение этой задачи дало троичной симметричной системе счисления альтернативное название ”уравновешенная”.
Чтобы взвесить груз массой 5 кг. необходимо на чашу с ним положить две гири: 1 кг. и 3 кг., а на пустую чашу 9-килограммовую гирю. Его запись: 01 113S
Данный алгоритм можно повторять до достижения наибольшего числа (то есть суммы всех гирь) — 11113S . В десятичной системе это число
Связь обычной системы счисления и уравновешенной объясняется следующим образом.
Некоторое десятичное число X представлено в троичной системе счисления как ( d i . d 2 d 1 d 0 ) 3 , то есть в развернутой записи:
di ·3 p i + . + d 2 · 3 2 + d 1 · 3 1 + d 0 · 3 0 ,
где цифры d 0 , d 1 , d 3 , . di могут принимать значения 0, 1 или 2.
Можно доказать, что 2 · 3 i = 3 i +1 — 3 i . Введем отрицатель-
ное число 1 и обозначим её с верхней чертой 1 . Тогда по-
следнее равенство можно записать в виде: 2 · 3 i = 3 i +1 + 1· 3 i . Отсюда можно сделать вывод, что любое десятичное число можно записать в троичной уравновешенной системе
счисления с помощью 0, 1 и 1 .
В троичной уравновешенной системе счисления можно отобразить не только положительные, но и отрицательные числа. Это является ее большим преимуществом перед другими системами счисления. Алгоритмы перевода десятичных положительных и отрицательных.
Вопросы
1. Что называют ”троичной системой счисления”?
2. Какие виды троичной системы бывают? В чем ихотличие?
3. Дайте определение троичной уравновешенной системе счисления.
4. Как связаны между собой обычная троичная система счисления и уравновешенная?
5. Какое основное преимущество у троичной уравновешенной системы счисления перед другими системами счисления?
§2. Алгоритм перевода числа из десятичной системы счисления в уравновешенную троичную систему счисления
Чаще всего при переводе из десятичной системы счисления в любую другую систему счисления, используют деление столбиком. Альтернативой данного оформления является запись в два столбца. В отличие от деления в столбик, запись в два столбца экономит место в более сложных примерах и уменьшает риск ”потерять” один из остатков.
При переводе десятичного числа в 3УСС, чтобы избежать путаницы с остатками и частными, которые в определенных случаях нужно изменять, будем пользоваться методом деления в два столбца.
Алгоритм перевода d 10 в d 3S
1. Найдем остаток от деления исходного числа на 3. Чтобы это сделать, воспользуемся признаком деления на 3: число делится на 3 тогда и только тогда, когда сумма его цифр делится на
2. Если остаток равен 0 или 1, то записываем частное под исходным числом, а полученный остаток справа от исходного числа, за чертой.
3. Если остаток равен 2, то к исходному чис-
лу d 10 прибавляем 1 и делим (d10 + 1) на 3. В этом случае под исходным числом нужно написать частное от деления (d10 +1) на 3, а справа от исходного числа отрицательную единицу ( 1 ).
4. Повторяем пункт 1, 2, 3 до тех пор, покачастное не станет меньше 3.
5. Получившиеся остатки от деления записываем, начиная с последнего. То есть, в записи d 3S первым числом (если смотреть слева на право) будет самый последний (нижний) остаток.
Пример 1 . Переведите десятичное число 83 в троичную уравновешенную систему счисления.
Решение . При делении 83 на 3, получаем остаток 2. Значит, лучше разделить на 3 не 83, а 84. Частное равно 28, а остаток от деления 1 .
Легко догадаться, что в левом столбце записываются делимые, а в правом — остатки. Вертикальная черта с числом наверху символизирует деление или ту систему счисления, к которой мы переходим. В нашем случае мы переходили к троичной уравновешенной системе счисления, которую в дальнейшем будем обозначать с индексом 3S (от лат. ”symmetrical” — симметричный).
Далее деление осуществляется по простому алгоритму. Не забываем в ответе записывать остатки в обратном порядке.
Пример 2 . Переведите десятичное число -131 в троичную уравновешенную систему счисления.
Решение . Модуль данного числа равен 131. Произведём расчёт по алгоритму, описанному выше, и запишем деление в два столбца:
Число 131 в троичной уравновешенной системе счис-
ления имеет вид — 111011 . Следовательно, −13110 = 1110113S .
Ответ: 1110113S .
Вопросы
1. Как перевести число из десятичной системы счисления в троичную уравновешенную систему счисления?
2. В чем отличие перевода отрицательного десятичного числа в 3УСС от положительного?
Задачи
№6. Переведите десятичное число в уравновешенную троичную систему счисления:
№7. Переведите отрицательное десятичное число в уравновешенную троичную систему счисления:
№8. Даны два числа: A= 41310 и B= 53510 . Какое из приведённых ниже чисел C в уравновешенной троичной системе счисления соответствует неравенству A
3) 11010103S ; 4) 110101103S .
№9. Даны два числа: A= 96310 и B= 101110 . Какое из приведённых ниже чисел C в уравновешенной троичной системе счисления соответствует неравенству B3S ;
3) 11111113S ; 4) 11011113S .
№10. Сколько положительных единиц в уравновешенной троичной записи числа 235710 ?
№11. Сколько отрицательных единиц в уравновешенной троичной записи числа 356910 ?
№12. Сколько значащих нулей в уравновешенной троичной записи числа 221110 ?
№13. Для каждого из приведённых ниже десятичных чисел построили уравновешенную троичную запись. Укажите десятичное число, уравновешенная троичная запись которого содержит три отрицательных единицы.
№14. Для каждого из приведённых ниже десятичных чисел построили уравновешенную троичную запись. Укажите десятичное число, уравновешенная троичная запись которого содержит четыре отрицательных единицы.
№15. В записи числа какой троичной системы (обычной или уравновешенной) цифр может быть меньше? Объясните вашу точку зрения.
§3. Алгоритм перевода числа из троичной уравновешенной системы счисления
в десятичную систему счисления
Алгоритм перевода из ЗУСС в десятичную систему счисления ничем не отличается от перевода любой другой системы счисления в десятичную.
Алгоритм перевода d 3S в d 10
1. Для перевода троичного уравновешенногочисла в десятичную систему счисления необходимо представить его в развернутом виде di · p i + . + d 2 · p 2 + d 1 · p 1 + d 0 · p 0 .
Для этого пронумеруем разряды исходного числа справа налево, начиная с нуля. Так мы найдём i.
2. Запишем исходное число в развёрнутой записи, где i — наибольший номер, d — соответствующий коэффициент (1, 0 или 1 ), а p всегда равно
3. Преобразовав выражение, мы получим искомое десятичной число.
Пример 1 . Переведите число 1111013S в десятичную систему счисления.
Решение. Пронумеруем разряды исходного троичного уравновешенного числа:
i=5, следовательно, наибольшая степень тройки равна
5. Запишем развернутую запись числа 1111013S .
Вопросы
1. Как перевести число из троичной уравновешенной системы счисления в десятичную систему счисления?
Задачи
№16. Переведите из уравновешенной троичной системы счисления в десятичную.
1) 101103S ; 5) 1100113S ; 2) 1001013S ; 6) 1110113S ;
3) 1111013S ; 7) 10110113S ; 4) 1001013S ; 8) 10001113S .
№17 Даны два числа: A= 1111113S и B= 1100013S . Какое из приведённых ниже чисел C в десятичной системе счисления соответствует неравенству C
№18 Даны два числа: A= 110111003S и C= 110110003S . Какое из приведённых ниже чисел B в десятичной системе счисления соответствует неравенству C
№19 Какое неравенство будет верным для чисел A= 21013 ,
№20 Какое неравенство будет верным для чисел A= 15310 ,
№21 Заполните таблицу, в каждой строке которой одно и то же число должно быть записано в разных системах счисления.
№22 Заполните таблицу, в каждой строке которой одно и то же число должно быть записано в разных системах счисления.
№23 Сколько верных неравенств среди перечисленных:
№24 Сколько верных неравенств среди перечисленных:
№25 Какое из чисел 100000013S ; 1013 будет наибольшим? Нужно ли для нахождения наибольшего числа выполнять какие-либо вычисления? Обоснуйте свой ответ.
Тест по главе 1
1. Число 42310 в 3УСС имеет вид:
3) 11111003S ; 4) 11111003S .
2. Число −21710 в 3УСС имеет вид:
4) 1010013S ; 4) 1010013S .
3. Число 11010003S в десятичной системе счисления имеет вид:
4. Число 11110103S в десятичной системе счисления имеет вид: 1) 375;
2) -375; 3) 348; 4) -348.
3) [1] 10010113S ; 4) 10001113S .
3) 111110 [6] [7] [8] S ; 4) 11111103S .
7. Для чисел A= 131 [9] , B= 112213 , C= 1111113S верным неравенством будет:
Глава 2. Арифметические операции в троичной
уравновешенной системе счисления
§4.Операции сложения и вычитания
Правила выполнения арифметических действий над троичными числами определяются арифметическими действиями над одноразрядными троичными числами и аналогичны во всех позиционных системах счисления.
Рассмотрим операции сложения и вычитания для отдельных пар цифр троичной уравновешенной системы счисления.
Таблица сложения уравновешенной троичной системы очевидна. Только при сложении 1+1 и 1 + 1 происходит перенос в старший разряд, и сумма равна 11 и 11 соответственно.
Таблица 1. Сложение в 3УСС
Как и в десятичной системе счисления, сложение троичных чисел начинается с правых (младших) разрядов. Если результат сложения цифр младших значащих разрядов обоих слагаемых не помещается в этом разряде результата, то происходит перенос. Цифра, переносимая в соседний разряд слева, добавляется к его содержимому.
Такая операция последовательно выполняется над всеми разрядами слагаемых от младших до старших.
Пример 1 . Найдите сумму 11101103S и 11110013S .
Решение . Выполним сложение в столбик, используя Таблицу 1.
Ответ : 110011113S .
При выполнении операции вычитания всегда из большего по абсолютной величине вычитается меньшее и ставится соответствующий знак.
В отличие от таблицы сложения, где порядок слагаемых не важен (т. к. от перестановки мест слагаемых сумма не меняется), в таблице вычитания уменьшаемые расположены в первой строке, а вычитаемые в первом столбце.
При вычитании троичных уравновешенных чисел только в двух случаях происходит перенос в старший разряд.
Таблица 2. Вычитание в 3УСС
Пример 2 . Найдите разность 1110113S и 1010013S .
Решение . Выполним вычитание в столбик, используя Таблицу 2.
Ответ : 1010013S .
Стоит отметить, что в предыдущих двух таблицах заключается ещё одно преимущество троичной уравновешенной системы счисления над другими системами счисления. Рассмотрим вычисление суммы в обычной троичной системе счисления.
Таблица 3. Сложение в троичной системе счисления
По таблице видно, что, в отличие от троичной уравновешенной системы счисления, перенос в старший разряд происходит три раза.
Сравним со сложением в двоичной системе счисления:
Таблица 4. Сложение в двоичной системе счисления
где из четырех пар слагаемых в одном происходит перенос в старший разряд. Сравним с Таблицей 1. В Таблице 1 из девяти пар слагаемых только в двух случаях происходит перенос в старший разряд. Это означает, что при сложении в ЗУСС перенос в старший разряд происходит в 2/9 случаев, а в двоичной системе счисления в 1/4 . Так как 1/4 > 2/9 , то троичная система счисления с точки зрения переноса в старший разряд проще.
Очевидно, что в других системах счисления, где основание больше 2, случаев переноса в старший будет еще больше. В этом заключается еще одно преимущество троичной системы счисления.
Вопросы
1. Как выполняется сложение в троичной уравновешенной системе счисления?
2. Как выполняется вычитание в троичной уравновешенной системе счисления?
3. В скольких случаях происходит перенос в старшийразряд при сложении и вычитании в ЗУСС?
4. В чем заключается преимущество операции сложения в ЗУСС?
Задачи
№26. Выполните арифметические операции над числами, которые записаны в уравновешенной троичной системе счисления:
2) 11111 − 11111 ; 3) 111000 + 1101 ; 4) 101111 − 11011 .
№28. Выполните арифметические операции над числами, которые записаны в уравновешенной троичной системе счисления:
1) 1111111 + 1110100 ;
2) 1101000 − 1111111 ;
3) 1101110 + 1111 ; 4) 1001111 − 1010001.
№29. Вычислите в уравновешенной троичной системе
сумму X и Y, если X= 25810 , Y= 1111013S .
№30. Вычислите в уравновешенной троичной системе
сумму X и Y, если X= 1021213 , Y= 11 .
№31. Даны 4 числа, записанные в уравновешенной троичной системе счисления: 111111,101011,101111,101110 .
Сколько среди них чисел, больших, чем 11000103S−1010113S ? В ответе укажите только количество чисел.
№32. Какое из приведённых выражений, записанных в уравновешенной троичной системе счисления, имеет наибольшее значение?
2) 111111 − 111 ; 3) 110010 − 10 ; 4) 1001+11.
№33. Запись числа N в уравновешенной системе счисления содержит четыре числа, второе из которых отрицательное. Запись этого числа в обычной троичной системе счисления состоит из трех чисел. Чему равно число N, если известно, что в десятичной системе счисления, оно заканчивается на 9?
№34. Запись числа N в уравновешенной системе счисления содержит пять чисел, среди которых только одно положительное. Запись этого числа в обычной троичной системе счисления заканчивается на 2. Чему равно число N?
§5.Операции умножения и деления
Операция умножения выполняется с использованием таблицы умножения по обычной схеме, применяемой в десятичной системе счисления с последовательным умножением множимого на очередную цифру множителя.
Важно отметить, что в троичной уравновешенной системе счисления, как и в двоичной, нет переносов в старший разряд. Это отличает её от традиционных систем счисления.
Таблица 5. Умножение в 3УСС
Вычисление произведения двух n-разрядных троичных чисел сводится к формированию частичных произведений по одному на каждую цифру множителя, с их последующим суммированием. Перед суммированием каждое частичное произведение должно быть сдвинуто на один разряд относительно предыдущего.
Пример 1. Найдите произведение 100113S и 1113S .
Решение . Выполним умножение в столбик, используя Таблицу 5.
Операция деления троичных уравновешенных чисел выполняется подобно алгоритму выполнения деления в десятичной системе счисления, однако имеет свои нюансы. Поэтому данную операцию разберем более подробно.
Алгоритм деления в 3УСС
1. Сравниваем по разрядам делимое и делитель. Выделяем неполное делимое.
2. Написав в частном 1, вычитаем делитель изделимого.
3. Сравниваем остаток с делимым. Если остаток больше, то вычитаем из него делитель, предварительно записав ещё одну единицу в частном снизу от предыдущей. Повторяем данный пункт до тех пор, пока остаток не станет меньше делителя. Затем складываем в столбик получившийся ряд чисел.
4. Если остаток меньше делителя, то сносимцифру следующего разряда (если она есть) и получаем второе неполное делимое.
5. Выполняем пункты 2-4 до тех пор, пока вделимом не останется ни одной неснесенной цифры.
На первый взгляд данный алгоритм может показаться сложным, так как он имеет ряд отличий от деления в привычной десятичной системе.
Например, в десятичной системе счисления, получив остаток, больший делителя, мы бы сделали вывод о неправильно найденном частном, так как остаток должен быть строго меньше делителя.
Также в десятичной системе счисления в частном не приходится делать никакие другие операции, в отличие от алгоритма в троичной уравновешенной системе счисления.
Разберём каждый пункт алгоритма на примере.
Пример 2. Найдите частное от деления 111103S на
Решение . Выполним деление в столбик, сперва выделив неполное делимое.
Написав единицу под чертой в частном, выполняем
В результате получается остаток 101 , который больше делителя 111 . Значит, из остатка нужно еще раз вычесть делитель, не забыв написать ещё одну единицу в частном. Единицу записываем не справа от частного, а снизу для удобности выполнения дальнейшего сложения.
Уменьшаем 101 на 111 и приписываем ещё одну 1 в частное, справа от получившейся суммы.
Остаток равен делителю, поэтому отнимаем из остатка делитель и записываем еще единицу в частном под предыдущей.
Остаток занулился. Значит, можно выполнить сложение в частном.
Цифра последнего разряда делимого равна 0, поэтому мы её просто дублируем в частном, справа от получившейся суммы.
Вопросы
1. Как выполняется умножение в троичной уравновешенной системе счисления?
2. Опишите алгоритм деления в 3УСС.
3. В чем особенности алгоритма деления троичныхуравновешенных чисел?
Задачи
№35. Выполните арифметические операции над числами, которые записаны в уравновешенной троичной системе счисления:
№36. Выполните арифметические операции над числами, которые записаны в уравновешенной троичной системе счисления: 1) 10010 · 111 ;
№37. Найдите значение выражения: 10003S+
№38.Найдите значение выражения: 11001 · 11−
№39. Вычислите в уравновешенной троичной системе
произведение X и Y, если X= 1310 , Y= 1113S .
№40. Найдите в уравновешенной троичной системе част-
ное от деления X на Y, если X= 25810 , Y= 111113S .
№41. Даны 4 числа, записанные в уравновешенной троичной системе счисления: 1100 , 1110 , 1011 , 1111 . Сколько среди них чисел, меньших, чем 11011113S : 10113S ?
№42.Какое из приведённых выражений, записанных в уравновешенной троичной системе счисления, имеет наибольшее значение?
№43. Какое из приведённых выражений, записанных в уравновешенной троичной системе счисления, имеет наименьшее значение?
1) 101111 + 11101 ;
Тест по главе 2
1. Значение выражения 1111113S + 101113S : 113S равно:
3) 1111113S ; 4) 1110113S .
2. Значение выражения 11111103S−11103S·11103S равно:
3. Числа X= 11111113S и Y= 66310 сложили. Их сумма равна:
3) 11111113S ; 4) 11111113S .
4. Из числа X= 31410 вычлли Y= 11100013S . Получившаяся разность равна:
3) 1011113S ; 4) 1011113S .
5. Произведение X и Y равно 111011103S . Известно, что X= 7510 . Тогда Y равен:
6. Частное от деления X на Y равно 11103S . Известно, что делитель Y= 37 [10] . Тогда делимое X равно:
3) 10111103S ; 4) 10111103S .
7. Среди перечисленных наибольшим является выражение:
1) [11] [12] 1101103S − 10113S; 2) 1110113S + 111103S ;
3) 111113S · 1003S ; 4) 10110103S : 113S .
8. Среди перечисленных наименьшим является выражение:
2) 11100113S − 1110113S ;
3) 11001 · 1113S ; 4) 1010100 : 113S .
9. Корнем уравнения 1111103S · x = 111010103S
Глава 3. Теория делимости в
§6.Признак делимости на 3 n
Традиционно в школе при делении положительного целого числа n на положительное целое число m с остатком считается, что возможными остатками могут быть 0,1. m -1, в зависимости от n и m . Например, при делении 12 на 3 частное равно 4, остаток равен 0, при делении 13 на 3 частное равно 4, остаток равен 1, при делении 14 на 3 частное равно 4, остаток равен 2, при делении 15 на 3 частное равно 5, остаток снова
Для понимания троичной уравновешенной системы счисления удобнее полагать, что остатки от деления на 3 могут принимать значения -1,0,+1. То есть для тех же чисел при делении 12 на 3 частное равно 4, остаток равен 0, при делении 13 на 3 частное равно 4, остаток равен 1, но при делении 14 на 3 будем считать, что частное
равно 5, а остаток равен -1, при делении 15 на 3 частное равно 5, остаток снова
Как видим, из перечисленных четырёх случаев в трёх ситуациях получили то же, что и было в традиционной схеме, и только в одном случае (для числа 14) мы решили вычислять по другой схеме.
Можно объяснять это так: когда мы работаем с числом 14, то среди чисел, кратных 3, нам ближе идти не вниз к 12, а вверх к 15. Правда, в этом случае у нас фактически получается не остаток, а недостаток, но мы и указываем его со знаком минус.
Это очень похоже на округление чисел. Например, при округлении до целого мы для числа 8.1 идем вниз к 8, а число 8.7 округляем вверх до 9.
Такая точка зрения упрощает и многие доказательства в теории делимости. В ходе выкладок мы в любой момент можем от высказывания «остаток от деления n на m равен -1″перейти к равносильному высказыванию «остаток от деления n на m равен m -1 и наоборот. Это применимо не только к m = 3 , но и к другим m .
Если в десятичной системе счисления можно рассматривать признаки делимости на цифры 2,3,4,5,6,7,8,9, то в троичной уравновешенной системе счисления признаки делимости на цифры -1 или 1 неинтересны. Но в десятичной системе счисления можно рассматривать и признаки делимости на числа, записываемые более чем одной цифры. Правда на практике рассматриваются только признаки делимости на 10 и на 11.
Все мы знаем признаки делимости чисел в десятичной системе счисления. Например, десятичное число делится на 2 тогда и только тогда, когда его последняя цифра является четной (то есть число заканчивается на 0, 2, 4, 6, 8). Десятичное число делится на 3 тогда и только тогда, когда сумма цифр, из которых состоит число, делится на
Признак делимости — это алгоритм, используя который можно сравнительно быстро определить, является ли рассматриваемое число кратным заранее заданному (т.е. делится ли на него без остатка).
В троичной уравновешенной системе счисления также можно рассматривать признаки деления на числа, записанные более чем одной цифрой, например, признак делимости 113S . Однако для понимания, возможно, следует называть эти числа в десятичной системе счисления. При этом возникают полезные аналогии. Например, 4 это число, следующее за основанием троичной уравновешенной системы счисления — числом 3. Это подсказывает, что признак делимости должен быть похож на признак делимости на 11 в десятичной системе счисления.
Очевидно, что основным признаком делимости в троичной системе является признак делимости на 3.
Признак 1 . Троичное уравновешенное число делится на 3 тогда и только тогда, когда последняя цифра в его записи равна 0.
Доказательство . Запишем уравновешенное троичное число в виде:
где xn может быть равно 1, 0 или 1 , а n равно степени тройки. Переведем данное число в десятичную систему счисления:
xn. x 2 x 1 x 0 = 3 n · xn + . +3 2 · x2 +3 1 · x1 +3 0 · x0 .
Число a без остатка делится на b, если каждое слагаемое из суммы a делится на b. То есть число xn. x 2 x 1 x 0 = 3 n · xn + . +3 2 · x2 +3 1 · x1 +3 0 · x0 делится на 3, если каждое слагаемое 3 n · xn
Так как слагаемыми являются степени тройки (не зависимо от того, положительные слагаемые или отрицательные), то 3 n · xn будет делиться на 3. Исключением является последнее слагаемое, так как коэффициент находится в нулевой степени и равен 1.
Отсюда следует, что число xn. x 2 x 1 x 0 делится на 3, если x 0 =0. Что и требовалось доказать.
Пример 1 . Проверить делимость чисел 110113S и 110103S на 3.
Решение . Число 110113S заканчивается на 1, значит,
оно не делится на 3. Проверка: 110113S = 3 4 ·1−3 3 ·1+3 2 · 0 − 3 1 · 1+3 0 · 1 =81-27+0-3+1=52.
Действительно, 52 на 3 без остатка не делится.
Число 110103S заканчивается на 0, значит, оно делится
на 3 без остатка. Проверка: 110103S = 3 4 ·1+3 3 ·1+3 2 ·0+
3 1 · 1+3 0 · 0 =-81-27+0-3+0=111
Действительно, -111 на делится на 3 без остатка.
По такому же принципу проверяется делимость на 9.
Признак 2. Троичное уравновешенное число делится на 9 тогда и только тогда, когда две последних цифры в его записи равны 0.
Доказательство . Доказательство осуществляется по аналогии с доказательством к признаку делимости на 3. Запишем уравновешенное троичное число в виде: xn. x 2 x 1 x 0 ,
где xn может быть равно 1, 0 или 1 , а n равно степени тройки. Переведем данное число в десятичную систему счисления:
xn. x 2 x 1 x 0 = 3 n · xn + . +3 2 · x2 +3 1 · x1 +3 0 · x0 .
Число a без остатка делится на b, если каждое слагаемое из суммы a делится на b. То есть число xn. x 2 x 1 x 0 = 3 n · xn + . +3 2 · x2 +3 1 · x1 +3 0 · x0
делится на 9, если каждое слагаемое 3 n ·xn делится на
Так как слагаемыми являются степени тройки (не зависимо от того, положительные слагаемые или отрицательные), то 3 n · xn будет делиться на 9. Исключением является предпоследнее и последнее слагаемое, которые равны 3 и 1 соответственно.
Отсюда следует, что число xn. x 2 x 1 x 0 делится на 9, если x 0 =0 и x 1 = 0 . Что и требовалось доказать.
Пример 2 . Проверить делимость чисел 10011103S ,
101111003S на 9.
Решение . Число 10011103S заканчивается на один ноль,
значит, оно не делится на 9. Проверка: 10011103S = 3 6 ·1+ 3 3 · 1 − 3 2 · 1+3 1 · 1 = 729+27 − 9+3 =750.
Действительно, 750 на 9 без остатка не делится.
Число 101111003S заканчивается на два нуля, значит,
оно делится на 9 без остатка. Проверка: 101111003S = 3 7 ·
1+3 5 ·1+3 4 ·1−3 3 ·1−3 2 ·1 = 2187+243+81−27−9 =2475
Действительно, 101111003S делится на 9 без остатка.
Не сложно понять принцип делимости на 27, 81 и т.д.
Теорема1. Число, записанное в уравновешенной троичной системе счисления, делится на 3 n , если оно заканчивается на n нулей.
Докажите данную теорему самостоятельно, основываясь на двух предыдущих доказательствах.
Вопросы
1. Что называют признаком делимости?
2. Сформулируйте признаки делимости на 3 и на 9.
3. О чем гласит теорема «Признак делимости на 3 n «?
Задачи
№44. Сформулируйте признак делимости троичного уравновешенного числа на 27 и докажите его.
№45. Сформулируйте признак делимости троичного уравновешенного числа на 243 и докажите его.
№46. Проверьте делимость чисел на 3: 11003S ; 111013S ;
№47. Проверьте делимость чисел на 9: 10013S ; 111003S ;
№48. Используя теорему 1, определите делители чи-
сел: 10111003S ; 111103S ; 10011003S ; 11110003S .
№49. Используя теорему 1, определите делители чи-
сел: 1101003S ; 110110003S ; 11001003S ; 110100003S .
№50. Число, записанное в 3УСС, делится на 3. Также известно, что сумма цифр равна 0. Минимум из скольких цифр состоит это число?
№51. Число, записанное в 3УСС, делится на 9. Известно, что сумма цифр данного числа равна 2. Найдите минимальное число, подходящее под данное описание. Ответ запишите в 3УСС.
№52. Число, записанное в 3УСС, делится на 27. Известно, что количество цифр данного числа равно 6. Найдите минимальное положительное число, подходящее под данное описание. Ответ запишите в 3УСС.
§7.Признаки делимости на 2 и на 6
Признак 3 . Число, записанное в уравновешенной троичной системе счисления, делится на 2 тогда и только тогда, когда сумма его цифр равна четному числу.
Доказательство . Запишем уравновешенное троичное число в виде:
где di может быть равно 1, 0 или 1 , а i равно степени тройки. Переведем данное число в десятичную систему счисления:
di. d 2 d 1 d 0 = 3 i · di + . +3 2 · d2 +3 1 · d1 +3 0 · d0 .
Число делится на 2, если оно является четным. Таким образом,
3 i · di + . +3 2 · d2 +3 1 · d1 +3 0 · d0 разделится на 2, если сумма всех слагаемых является
Четное число получается в двух случаях: при сложении двух нечетных или при сложении четного с четным. В троичной системе счисления среди слагаемых четного числа быть не может, значит, остается только первый вариант.
Отсюда следует, что
3 i · di + . +3 2 · d2 +3 1 · d1 +3 0 · d0 будет четным, если сумма слагаемых тоже равно чет-
ному числу. Что и требовалось доказать.
Пример 1 .Проверить делимость чисел 110113S и 111003S на 2.
Решение . Сумма цифр в записи 110113S равна 2 ( 1 −
1+0+1+1 = 2 ). Число 2 – четное, следовательно, 110113S
делится на 2. Сделаем проверку: 110113S = 3 4 ·1−3 3 ·1+ 3 1 · 1+3 0 · 1 = 81 − 27+3+1 =58. Число 58 делится на 2.
Аналогично и с 111003S .Сумма цифр в записи 111003S равна 1 ( 1 − 1+1+0+0 ). Число 1 является нечетным,
поэтому 111003S не делится на 2. Проверяем: 111003S = 3 4 · 1 − 3 3 · 1+3 2 · 1 = 81 − 27+9 =63. Действительно, 63 не делится на 2.
Признак 4 . Число, записанное в уравновешенной троичной системе счисления, делится на 6 тогда и только тогда, когда оно заканчивается 0 и сумма его цифр равна четному числу.
Данная теорема обобщает в себе признаки делимости на 3 и на 2, что является очевидным, так как 6 делится и на 2, и на 3. Аналогичным образом можно сформулировать признаки делимости на 18, 54 и т.д.
Пример 2 .Проверить делимость чисел 111103S и 1110113S на 6.
Решение . Сумма цифр в записи 110113S равно 4 (1+11+1=2). Число 2 – четное, следовательно, 111103S де-
лится на 2. Также, 111103S заканчивается нулем, значит, оно делится и на 3. Сделаем проверку: 111103S = 3 4 ·1+3 3 ·1−3 2 ·1+3 1 ·1 = 81+27−9+3+1 =102. Число 102 делится на 6.
Аналогично и с 1110113S . Сумма цифр в записи 1110113S равна -1 (1-1-1+0+1-1=-1). Число -1 является нечетным,
поэтому 1110113S не делится на 2. Также данное число не делится на 3, так как оно не заканчивается нулем.
Отсюда следует, что 1110113S не делится на 6. Прове-
ряем: 1110113S = 3 5 · 1 − 3 4 · 1 − 3 3 · 1 + 3 1 · 1 − 3 0 · 1 = 243−81−27+3−1 =137. Действительно, 137 не делится на 6.
1. О чем гласит признак 4?
Вопросы
2. Сформулируйте признак делимости на 2 в десятичной системе счисления. В какой системе счисления проверить делимость на 2 проще: в 3УСС или десятичной?
3. Сформулируйте признак делимости на 6.
Задачи
№53. Сформулируйте признак делимости троичного уравновешенного числа на 18 и докажите его.
№54. Сформулируйте признак делимости троичного уравновешенного числа на 162 и докажите его.
№55. Проверьте делимость чисел на 2: 111113S ; 1011013S ;
№56. Проверьте делимость чисел на 6: 11111103S ; 1011113S ;
№57. Используя теорему 1 и признаки 3, 4 определите
делители чисел: 111103S ; 1111003S ; 111103S ; 1011113S .
№58. Используя теорему 1 и признаки 3, 4 определите
делители чисел: 1101113S ; 11110003S ; 10111013S ; 10111013S .
№59. Число, записанное в 3УСС, делится на 6 и является 5-разрядным. Также известно, что сумма цифр равна 0. Найдите минимальное число, подходящее под данное описание.Ответ запишите в 3УСС.
№60. Число, записанное в 3УСС, делится на 18. Из-
вестно, что сумма цифр данного числа делится на 2. Найдите максимальное число, подходящее под данное описание. Ответ запишите в 3УСС.
№61. Число, записанное в 3УСС, делится на 54. Известно, что количество цифр данного числа равно 5. Найдите минимальное положительное число, подходящее под данное описание. Ответ запишите в 3УСС.
§8.Признаки делимости на 4 и на 8
Признак 5 . Число, записанное в троичной уравновешенной систем счисления, делится на 4 тогда и только тогда, когда разность между суммой цифр, стоящих на четных позициях и суммой цифр, стоящих на нечетных позициях, делится на
Доказательство
Так как 3 = 4−1 , можно считать, что остаток от деления 3 на 4 равен -1. Тогда остаток от деления 3 n = (−1) n , для четных степеней это +1, для нечетных степеней это
d i d i −1 . d 1 d 0
записано в троичной уравновешенной системе счисле-
ния, развернутая его запись будет
d i 3 i + d i −1 3 i −1 + . + d 1 3 1 + d 0 .
Остаток от деления этого числа на 4 будет равен di (−1) i + di−1(−1) i −1 + . + d1(−1) 1 + d0 .
Тогда сумма слагаемых с четными степенями будет равна d 0 + d2 + d4 + . , а сумма слагаемых с нечетными степенями будет равна (−1) · (d1+ d3+ d5+ . ) . Следовательно, разность сумм d 0 +d2+d4+. и d 1 +d3+d5+. при делении на 4 будет иметь тот же остаток, как и исходное число.
Пример 1 . Проверить делимость числа 1110101001113S на 4.
Решение. В числе 1110101001113S сумма цифр на нечетных позициях равна 1+1+1+1+0+1 = 5 , а сумма цифр
на четных позициях равна 1+0+0+0+1+1 = 1 , разность этих чисел 5−1 = 4 , конечно, делится на 4, значит и само
число 1110101001113S делится на 4. Для проверки переве-
дём в десятичную систему счисления: 1110101001113S =
Конечно, признак делимости на 4 в десятичной систем счисления оказался проще, но «для общего развития»интересно познакомиться и с указанным признаком.
Признак 6 . Число dndn −1 . d 1 d 0 , записанное в троичной уравновешенной системе счисления, делится на 8 тогда и только тогда, когда сумма его двузначных чисел S = . + d5d4 + d3d2 + d1d0 делится на 8.
Примечание . Здесь использовано нетрадиционное обозначение — троеточие «и так далее» записано не справа, как обычно, а слева. Это связано с тем, что мы записываем двузначные числа, формируя их справа, от младших разрядов исходного числа. Ситуация зависит от того, является ли n чётным или нет. В случае чётности n начальное слагаемое в сумме S будет число из одной цифры dn , а в случае нечетности n сумма S начинается с дву-
Доказательство
Так как 9 = 8+1 , остатки от деления на 8 всех чисел будут равны 1.
Если число dndn −1 . d 1 d 0 записано в троичной уравновешенной системе счисления, развернутая его запись будет d n 3 n + d n −1 3 n −1 + . + d 1 3 1 + d 0 = (d 1 3 1 + d 0 )+3 2 · (d33 1 +d2)+3 4 ·(d53 1 +d4)+. . Остаток от деления этого числа на 8 будет такой же, как у числа S = d 1 3 1 + d0 +
Пример 2 . Проверить делимость чисел 111013S , 111111113S на 8.
Решение. Для числа 6410 = 111013S (цифры для облегчения подсчета записаны парами с разбивкой пробелами)
сумма S = 1+11+01 = 0 , значит число делится на 8.
Аналогично и для числа 3 8 − 1 = 111111113S сумма
S = 11+11+11+11 = 1111 (здесь все числа записаны в троичной уравновешенной системе счисления). Можно S перевести в десятичную систему счисления, получим 16 и убедиться в делимости на 8. Но можно для S повторить
тот же прием и вычислить новое S = 11+11 = 0 и делимость становится очевидной.
Признаки делимости, сводящие проверку делимости числа к проверке делимости меньшего числа, называются рекуррентными.
Вопросы
1. О чем гласит признак 5?
2. Сформулируйте признак делимости на 4 в десятичной системе счисления. В какой системе счисления проверить делимость на 4 проще: в 3УСС или десятичной?
3. Сформулируйте признак делимости на 8.
4. Какие признаки делимости называются рекуррентными?
Задачи
№62. Проверьте делимость чисел на 4: 1111113S ; 10000103S ;
1101001113S ; 101111003S .
№63. Проверьте делимость чисел на 8: 10010113S ;
111011103S ; 11011113S ; 101111003S .
№64. Используя теорему 1 и известные признаки де-
лимости в 3УСС определите делители чисел: 111110103S ;
№65. Используя теорему 1 и известные признаки де-
лимости в 3УСС определите делители чисел: 1101010003S ;
№66. Число, записанное в 3УСС, делится на 4 и состоит из 6 цифр. Найдите минимальное число, подходящее под данное описание.
№67. Число , записанное в 3УСС, делится на 81 и на 4. Найдите минимальное число, подходящее под данное описание. Ответ запишите в десятичной системе счисле-
№65. Верно ли утверждение о троичном уравновешенном числе: «Если число заканчивается на два нуля, а разность между суммой цифр, стоящих на четных позициях и суммой цифр, стоящих на нечетных позициях, равна нулю, то данное число делится на 36»? Обоснуйте свой ответ.
№65. Верно ли утверждение о троичном уравновешен-
ном числе: «Если количество 1 и 1 равно четному числу, а разность между суммой цифр, стоящих на четных позициях и суммой цифр, стоящих на нечетных позициях, равна нулю, то данное число делится на 8»? Обоснуйте свой ответ.
Тест по главе 3
1. Среди перечисленных чисел на 3 без остатка делятся:
2. Среди перечисленных чисел на 9 без остатка делятся:
3. Среди перечисленных чисел на 2 без остатка делятся:
4. Среди перечисленных чисел на 6 без остатка делятся:
5. Число, отличное от 0 и записанное в 3УСС, делится на 9. Сумма чисел, из которых оно состоит, равно 1.
Минимальное количество разрядов данного числа равно:
6. Число, отличное от 0 и записанное в 3УСС, делится на 18. Минимальное количество разрядов данного числа равно:
7. Число, записанное в 3УСС, делится на 54. Известно, что количество цифр данного числа равно 6. Минимальным положительным числом, подходящим под данное описание, является:
3) 1100003S ; 4) 1100003S .
Проектная деятельность
Данный раздел предназначен для тех, кто хочет научиться приобретать знания самостоятельно, творчески мыслить, выражать свою точку зрения, выдвигать гипотезы и доказывать их, а также находить нестандартные и рациональные решения. В школьные годы научиться этому помогает проектная деятельность.
Школьный проект – это форма исследовательской работы, в процессе которой ученик (или группа учеников) самостоятельно находит информацию по теме работы, изучает ее, делает выводы и предоставляет отчетный материал. Отчетный материал может быть представлен в форме презентации, реферата или доклада.
Основные рекомендации по организации проектной деятельности:
1. При выборе темы необходимо учитывать еёактуальность и степень изученности, а также наличие источников информации в литературе и интернет-ресурсах.
2. Работа начинается с составления плана, вкотором отражаются основные этапы будущего проекта.
3. Определить основную цель проекта и задачи, с помощью которых она будет реализована.
4. Работа завершается подведением итогов исследования, делаются выводы, намечаются перспективы дальнейшего исследования темы.
Ниже приводится рекомендуемый список тем, которые который могут быть выбраны для проектной деятельности.
1. Календарь на год, разработанный в троичной уравновешенной системе счисления.
2. Кодирование в троичный экономный код по алгоритму Хаффмана.
3. Эмулятор первой троичной советской МЦВМ «Сетунь».
4. Троичная счётная машина Томаса Фоулера.
5. Представление дробных чисел в 3УСС и их округление.
[1] . Для чисел A= 1011103S , B= 1010013S , C= −27410 верным неравенством будет:
Известно что следующее равенство является верным 10111 18 56
1. Трехзначное десятичное число оканчивается цифрой 3. Если эту цифру переместить на два разряда влево, то есть так, что с нее будет начинаться запись нового числа, то это новое число будет на единицу больше утроенного исходного числа. Найдите исходное число.
2. Шестизначное число оканчивается цифрой 4. Если эту цифру переставить из конца числа в начало, то есть приписать ее перед первой, не изменяя порядок остальных пяти, то получится число, которое в четыре раза больше первоначального. Найдите это число.
3. Некогда был пруд, в центре которого вырост один лист водяной линии. Каждый день число листьев удваивалось, и на десятый день вся поверхность пруда уже была заполнена листьями лилий. Сколько дней понадобилось, чтобы заполнить листьями половину пруда? Сосчитайте, сколько листьев выросло к концу десятого дня.
4. Этот случай вполне мог иметь место во время «золотой лихорадки». На одном из приисков старатели были возмущены действиями Джо Макдональда – хозяина салуна, принимавшего от них в уплату золотой песок. Очень уж необычными были гири, с помощью которых тот взвешивал золото: 1, 2, 4, 8, 16, 32 и 64 грамма. Джо утверждал, что с помощью такого набора гирь он может взвесить с точностью до грамма любую порцию золотого песка, вес которой не превышает 100 граммов. Прав ли Джо Макдональд? Какой наибольший вес могут «взять» такие гири? Как с помощью названных гирь набрать вес: 25 г, 48 г, 72, 105 г?
5. Найдите такой набор из пяти гирь, чтобы, располагая их на одной чаше весов, можно было бы взвесить с точностью до 1 кг любой груз до 31 кг включительно.
6. Каким наименьшим числом гирь можно взвесить груз от 1 до 63 кг с точностью до 1 кг, помещая гири только на одну чашку весов?
7. Можно ли с помощью трех гирь (1, 3 и 9 кг) взвесить с точностью до 1 кг любой груз до 13 кг включительно, если гири можно располагать на обеих чашах весов, в том числе и на чаше с грузом?
8. Один кладовщик оказался в большом затруднении: заказанный комплект гирь для простых чашечных весов не прибыл в срок, а на соседнем складе лишних гирь не было. Тогда он решил подобрать несколько кусков железа разной массы и временно пользоваться ими как гирями. Ему удалось выбрать такие четыре «гири», с помощью которых можно было бы взвешивать с точностью до 100 г товар от 100 г до 4 кг. Подумайте, какой массы были эти гири?
9. Запишите наибольшее двузначное число и определите его десятичный эквивалент для следующих систем счисления:
1) восьмеричной системы счисления;
2) пятеричной системы счисления;
3) троичной системы счисления;
4) двоичной системы счисления.
10. Запишите наименьшее трехзначное число и определите его десятичный эквивалент для следующих систем счисления:
1) восьмеричной системы счисления;
2) пятеричной системы счисления;
3) троичной системы счисления;
4) двоичной системы счисления.
11. Упорядочите следующие числа по убыванию: 1436, 509, 12223, 10114, 1100112, 1283.
12. В классе 1111002% девочек и 11002 мальчиков. Сколько учеников в классе?
13. У меня 100 братьев. Младшему 1000 лет, а старшему 1111 лет. Старший учится в 1001-м классе. Может ли такое быть?
14. В классе 1000 q учеников, из них 120 q девочек и 110 q мальчиков. В какой системе счисления велся счет учеников?
15. В саду 88 q фруктовых деревьев, из них 32 q яблонь, 22 q груш, 16 q слив и 17 q вишен. В какой системе счисления посчитаны деревья?
16. Было 53 q яблока. После того как каждое из них разрезали пополам, стало 136 q половинок. В системе счисления с каким основанием вели счет?
17. Один мальчик так написал о себе: «У меня 24 пальца, на каждой руке по 5, а на ногах 12». Как это могло быть?
18. Расставьте знаки арифметических операций так, чтобы были верны следующие равенства в двоичной системе счисления:
1) 1100 ? 11? 100 = 100000;
2) 1100 ? 10 ? 10 = 100;
3) 1100 ? 10 ? 10 = 110000;
4) 1100 ? 10 ? 10 = 1011;
5) 1100 ? 11 ? 100 = 0.
19. Как измениться запись P -ичной дроби с нулевой целой частью, если ее разделить на P 2 ?
20. Записать в системе счисления с основанием 234 число 235.
21. Будут ли справедливы признаки делимости натуральных чисел на 2, 3, 5, 9, 10, сформулированные для десятичной системы счисления, и в других P -ичных системах?
22. Число, записанное в десятичной системе счисления, оканчивается цифрой 5. Будет ли оно делиться на 510, если записать его в троичной системе счисления?
23. Существуют ли системы счисления с основаниями p и q , в которых 12 p >21 q ?
24. Для десятичного числа 371 найти систему счисления с основанием p , в которой данное число будет представлено теми же цифрами, но записанными в обратном порядке, то есть 37110 = 173 p .
41. Перевести двоичные числа в восьмеричную систему счисления:
1) 110000110101; 1010101; 0,1010011100100; 0,1111110001;
2)0,1001111100000; 0,1100010; 11100001011001; 1000010101.
42. Перевести двоичные числа в шестнадцатеричную систему счисления:
1) 11011010001; 111111111000001; 0,0110101; 0,11100110101;
2) 10001111010; 100011111011; 0,101010101; 01100110011.
43. Перевести смешанные двоичные числа в восьмеричную и шестнадцатеричную системы:
1) 100010,011101; 1111000000,101; 101010,111001; 100011,111;
2) 101111,01100; 100000111,001110; 101010,0010; 1100011,11.
44. Перевести восьмеричные числа в двоичную систему счисления:
1) 256; 0,345; 24,025; 0,25;
2) 657; 76,025; 0,344; 345,77.
45. Перевести шестнадцатеричные числа в двоичную систему счисления:
1) 1АС7; 0,2D1; 2F,D8C; F0C,FF;
2) FACC; 0,FFD; FDA,12F; DDFF.A.
46. Перевести числа из шестнадцатеричной системы счисления в восьмеричную:
1) А45; 24A,9F; 0,FDD5; F12.0457;
2) A24,F9; 54A; 0,DFD3; 21D,567.
47. Перевести числа из восьмеричной системы счисления в шестнадцатеричную :
1) 774; 765,25; 0,5432; 654,763;
2) 665; 546,76; 0,7654; 432,347.
51. Опишите четверичную систему. Постройте двоично-четверичную таблицу.
54. В спортивном клубе занимаются 340 человек – 155 мальчиков и 141 девочка. В какой системе счисления посчитано количество спортсменов?
55. Во дворе школы учащиеся посадили 237 деревьев и декоративные кустарники. Всего было посажено 1207 саженцев. Сколько кустарников посадили школьники?
56. Переведите данное число из десятичной системы счисления в двоичную:
57. Переведите данное число из десятичной системы счисления в двоичную:
58. Переведите данное число из десятичной системы счисления в двоичную:
59. Переведите данное число из десятичной системы счисления в двоичную:
60. Переведите данное число из десятичной системы счисления в двоичную:
Задачи по теме «Действия над числами в разных системах счисления»
1. 10111011 + 1110011 = 100101110
2. 111011 — 10111 = 100100
3. 7AB + 124 = 8CF
4. 1AF1 + 124 = 1C15
5. 101111 + 10100 = 1000011
6. 1011101 — 110110 = 100111
7. 12C + D45 = E71
8. 1111000 — 100001 = 1010111
9. 11000011 + 1111111 = 101000010
10. Произведите сложение, вычитание, умножение и деление двоичных чисел 10102 и 102.
11. Вычислите сумму двоичного и десятичного чисел 102 + 1010. Представить результат в десятичной системе счисления.
12. Вычислите сумму чисел 112 + 118 + 1110 + 1116. Представить результат в двоичной системе счисления.
13. Вычислите разность чисел 2568 и 778; 1001002 и 10112; ABC16 и FF16
14. Расставьте вместо знаков вопроса знаки арифметических операций так, чтобы было верно следующее равенство в двоичной системе: 1100 ? 11 ? 100 = 100000
20. Выполните вычитание а) 1100112-101012 б) 57438-47148 в) В5116-7 D 16
21. Сложите числа а) 1110112+100112 б) 37438+27148 в) A 6216+78 B 16
22. Выполните вычитание а) 1110112-100112 б) 37438-7148 в) A 6216-8 B 16
28. Выполните вычитание а) 1100112-101012 б) 57438-47148 в) В5116-7 D 16
29. Сложите числа а) 1110112+100112 б) 37438+27148 в) A 6216+78 B 16
30. Выполните вычитание а) 1110112-100112 б) 37438-7148 в) A 6216-8 B 16
31. Выполните сложение: 11001 +101; 11001 +11001; 1001 + 111; 10011 + 101; 11011 + 1111; 11111 + 10011
32. Выполните сложение, вычитание, умножение в двоичной системе счисления: