В выпуске «Занимательные материалы по теме "Системы счисления"» серии «Информатика» (Библиотечка «Первого сентября») были опубликованы занимательные задачи, связанные с этой темой. В настоящей брошюре приведены также занимательные задачи по теме «Системы счисления», но повышенной сложности (с решениями). Представленные задачи могут быть использованы как на уроках, так и в качестве домашних заданий.
1. Система счисления в... колесе
Радиус колеса автомобиля равен 101х см. Колесо сделало 5000010 оборотов и проехало расстояние в 313х км. Найдите основание x системы счисления, в которой заданы размер радиуса колеса и расстояние.
2. Равенство
В каких системах счисления соблюдается равенство 10р + 10р = 20р?
3. Неравенство
В каких системах счисления 5р + 5р ≠ 10р?
4. Еще одно равенство
В каких системах счисления 5p + 5p = 10p?
5. Возможно ли неравенство?
Существуют ли системы счисления с основаниями p и q, в которых 12p > 21q?
6. Уравнение
В некоторой системе счисления записали уравнение Х6 × 2 = Y5, где Х6 - двузначное число с неизвестной первой цифрой и второй цифрой 6, Y5 - двузначное число с неизвестной первой цифрой и второй цифрой 5. Обе неизвестные цифры (и Х, и Y) не могут быть равны нулю. Определите, в какой системе счисления составлено это уравнение, и найдите все его решения (то есть все пары чисел Х и Y, являющиеся решениями).
7. Двоичное число
Про некоторое двоичное число известно, что в нем:
1) не более 40 цифр;
2) цифры чередуются;
3) количество одной из цифр составляет ровно 52% от общего числа цифр.
Найдите десятичный эквивалент этого числа.
8. О полных квадратах
Существуют ли системы счисления, кроме десятичной, в которых является полным квадратом число?
а) 121;
б) 144;
в) 169;
г) 196.
9. О полных кубах
Существуют ли системы счисления, кроме десятичной, в которых является полным кубом число?
а) 1331;
б) 1728.
10. Повар и пицца
В распоряжении повара имеются перец, лук, грибы, помидоры, морковь и рыба, причем все это можно, по его мнению, добавлять к сыру, чтобы приготовит пиццу (а можно и ничего не добавлять!). Сколько типов пиццы может приготовить повар?
11. Градуировка весов
Есть пружинные весы с крюком, которые нужно отградуировать. Каким должен быть набор гирь-разновесов, который можно использовать для градуировки весов на интервал масс 1, 2, ..., 31 кг, чтобы число гирь в наборе было минимальным? Масса пакета, который будет подвешиваться к крюку и в котором будут размещаться гири, не учитывается.
12. Семь кошельков
Как разложить по семи кошелькам 127 рублевых монет, чтобы любую сумму от 1 до 127 рублей можно было бы выдать, не открывая кошельков (то есть вместе с кошельками)?
13. Банкир и конверты [3]
Некому банкиру нужно было встретиться с важным клиентом, которому он должен выдать наличными заранее неизвестную сумму от 1 до 1 000 000 у.е. Чтобы не тратить время на отсчитывание денег, банкир дал указание своим кассирам заготовить некоторое количество конвертов с деньгами, на которых написаны содержащиеся в них суммы, чтобы потом просто отдать клиенту один или несколько конвертов, в которых и будет содержаться требуемая им сумма.
1. Какое наименьшее количество конвертов необходимо иметь?
2. Какова будет в этом случае полная сумма во всех конвертах?
3. Как, используя подготовленные конверты, набрать требуемую сумму?
14. Серебряная цепочка
В гостиницу приехал путешественник. Выяснилось, что деньги он забыл дома. У него была лишь серебряная цепочка из 7 звеньев. Он договорился с хозяином гостиницы о том, что за каждый день пребывания в гостинице будет расплачиваться одним звеном цепочки. Какое звено цепочки надо аккуратно расцепить, чтобы прожить в гостинице 7 дней и ежедневно расплачиваться с хозяином? (Хозяин может давать сдачу звеньями, полученными им ранее.)
15. Количество цифр в двоичной записи
Установите формулу, определяющую количество цифр в записи десятичного числа А в:
а) в двоичной системе счисления;
б) в q-ичной системе счисления.
16. Кощей Бессмертный и Иван-Царевич
Иван-Царевич попал в плен к Кощею Бессмертному. Тот выдвинул Ивану такие условия. Кощей загадывает три двузначных числа a, b и c. Царевич должен назвать ему три числа X, Y и Z, после чего Кощей сообщит ему сумму aX + bY + cZ. Иван-Царевич должен отгадать задуманные Кощеем числа, иначе ему отрубят голову. Как ему спастись?
17. Пропущенное число
Какое число надо поставить вместо символа «?» в последовательности:
10, 11, 12, 13, 14, 15, 16, 17, 20, 22, 24, 31, 100, ?, 10000.
18. Бедный торговец (старинная задача)1
В лавке бедного торговца вместо гирь было всего 4 камня. Однако с помощью этих камней он на рычажных чашечных весах совершенно правильно взвешивал предметы массой 1, 2, ..., 40 кг. Какого веса были камни?
19. Может ли быть такое?
Один мальчик сказал: «Позавчера мне было 10 лет, а в будущем году мне исполнится 13 лет». Может ли быть такое?
20. А такое?
Один юноша написал: «Позавчера мне было 16 лет, а в будущем году мне исполнится 20». Может ли быть такое?
21. Три вопроса
1. Как, не производя никаких арифметических действий, найти остаток от деления любого двоичного числа на 2?
2. Как проще всего умножить любое двоичное число на 3?
3. Как проще всего умножить любое шестнадцатеричное число на десятичное число 24?
22. Еще раз об Алисе
В знаменитой книге Льюиса Кэрролла «Алиса в стране чудес», в главе 2, автор приводит следующую фразу Алисы, когда она пробует вспомнить то, что знала раньше: «Ой, у меня, наверное, скоро правда голова сломается! А ну-ка проверю, помню я то, что знала, или нет. Значит так: четырежды пять - двенадцать, четырежды шесть - тринадцать, четырежды семь...».
В [4] было показано, что странные утверждения героини книги объясняются тем, что она использовала недесятичные системы счисления (произведение чисел 4 и 5 равно 12 в восемнадцатеричной системе счисления, произведение 4 и 6 = 13 - в системе счисления с основанием 21).
Дальше в книге Алиса утверждала: «Так я до двадцати никогда не дойду!». Попробуйте объяснить, почему девочка не дойдет до двадцати.
23. Последняя цифра
Найдите последнюю цифру числа 250.
24. Количество нулей и количество единиц
Дано двоичное число, состоящее из идущих подряд a единиц, после которых следуют b нулей. Найдите количество нулей n и количество единиц e суммы этого числа и числа 2c.
25. Импульсы с планеты τ-Кита
С планеты τ-Кита поступают импульсы. Получена последовательность сообщений вида:
X[1] = 000100001001010101100001
X[2] = 00010001000010010101010101100001
X[3] = 0001000100010000100101010101010101100001
и т.д.
Выдвинута гипотеза: если сообщения X[i], i = 1, 2, 3, ... подчиняются некоторому простому закону, то на планете живут разумные существа. Разумные ли существа живут на τ-Кита?
26. Об экономичности... систем счисления
Мы привыкли, что понятие «экономичность» применяется к приборам, устройствам и т.п. Но оно связано и с системами счисления. Под экономичностью системы счисления обычно понимается количество чисел, которое можно записать в данной системе с помощью определенного количества знаков. Поясню это на примере.
Чтобы в десятичной системе записать 1000 чисел (от 0 до 999), необходимо 30 знаков (по 10 цифр для каждого из трех разрядов). А, например, в двоичной системе с помощью 30 знаков можно записать 215 различных чисел (т.к. для каждого двоичного разряда нужны только две цифры 0 и 1, то с помощью 30 цифр мы можем записывать числа, содержащие до 15 разрядов). Но 215 > 1000, поэтому, имея 15 двоичных разрядов, можно записать больше различных чисел, чем с помощью трех десятичных. Таким образом, двоичная система более экономичная, чем десятичная.
Но какая из систем счисления самая экономичная? Для ответа на этот вопрос рассмотрим следующую конкретную задачу. Пусть в нашем распоряжении имеется 60 знаков. Мы можем, разбив их на 30 групп по два элемента в каждой, записать с их помощью в двоичной системе любое число, имеющее не больше 30 двоичных разрядов, т. е. в общей сложности 230 чисел. Те же 60 знаков мы можем разбить на 20 групп по три элемента и, пользуясь троичной системой, записать 320 различных чисел. Далее, разбив 60 знаков на 15 групп по четыре элемента в каждой, можно применить четверичную систему и записать 415 чисел и т.д. В частности, воспользовавшись десятичной системой (т.е. разбив все знаки на 6 групп по 10 элементов в каждой), мы могли бы записать 106 чисел, а применив шестидесятеричную систему, можно было бы с помощью 60 знаков записать только 60 чисел.
Посмотрим, какая из возможных здесь систем самая экономичная, т.е. позволяет записать с помощью данных 60 знаков наибольшее количество чисел. Иными словами, речь идет о том, какое из чисел 230, 320, 415, 512, 610, 106, 125, 154, 203, 302, 60 наибольшее.
Предложите своим ученикам получить ответ на обсуждаемый вопрос с помощью электронной таблицы Microsoft Excel или подобной, построив график зависимости перечисленных чисел от основания соответствующей системы счисления (рис. 1).
Рис. 1
27. Задача Иосифа Флавия - частный случай
Задача, которую называют «задачей Иосифа Флавия», основана на легенде о том, что известный историк первого века Иосиф Флавий выжил и стал известным благодаря математической одаренности. В ходе Иудейской войны он в составе отряда из 41 иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека2. Однако Иосиф, наряду с одним из своих единомышленников, счел подобный конец бессмысленным - он быстро вычислил спасительные места в круге, на которые поставил себя и своего товарища.
Эта задача известна у нас в стране как задача о считалке. Во многих играх (прятки и др.), для того чтобы выяснить, кому «водить», кто-либо из играющих произносит недлинный стихотворный текст - считалку. Играющий, на которого попадает последнее слово текста, выходит из круга. Кто последним останется в кругу, тому и водить.
В общем виде задача формулируется так: «По кругу размещены n человек. Задан параметр расчета k, то есть каждый k-й человек будет выбывать из круга. Требуется определить p - порядковый номер человека, который останется в круге последним».
Предложите своим ученикам решить эту задачу для частного случая - когда k = 2. Обращаем внимание на то, что при этом нет необходимости разрабатывать программу на каком-либо языке программирования - задача может быть решена путем рассуждений.
Указания по выполнению. Сначала нужно рассмотреть вариант, когда значение n есть степень двойки, а затем исследовать общий случай.
28. Как узнать номера квартир
В поселке, в котором живут учащиеся, в домах не более 30 квартир. Однажды учитель информатики решил узнать номера квартир каждого из 25 учеников класса. Он может произвести следующую операцию: прочитать список из нескольких (возможно - одного) номеров квартир и попросить ребят, живущих в соответствующих квартирах, поднять руки. Какое минимальное число раз он должен проделать такую операцию, чтобы узнать номер квартиры каждого ученика?
29. Друзья обмениваются новостями
32 друга одновременно узнали 32 новости, причем каждый узнал одну новость. Они сразу же стали звонить друг другу и обмениваться новостями. Каждый разговор длится 1 час. Какое минимальное количество часов необходимо, чтобы все узнали все новости? (Понятно, что во время одного разговора можно передать сколько угодно новостей.)
30. Необычный футбольный матч
Тренер футбольной команды решил провести тренировочную игру своей команды, состоящей из двух вратарей и 20 полевых игроков, следующим образом. Он разбил всех на две «полукоманды». Вратари все время защищают ворота одной и той же половины, а полевых игроков тренер каждые 10 минут переводил из одной «полукоманды» в другую. Успеет ли тренер за один 40-минутный тайм игры добиться того, чтобы любые два полевых футболиста в какой-то из 10-минутных отрезков времени оказались в разных «полукомандах»?
31. Подсчет числа единичных битов
В 16-битной памяти условной ЭВМ записано двоичное число:
| 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
Рис. 2
Другой памяти нет. Имеются также три устройства:
- № 1 - для считывания значений, записанных в нескольких последовательных битах памяти;
- № 2 - для суммирования 1-4-разрядных двоичных чисел (результат может быть 5-разрядным);
- № 3 - для записи 2-5-разрядных двоичных значений (с возможными начальными нулями) в память.
Предложите алгоритм определения количества единичных битов в заданном 16-битном двоичном числе.
1 Обычно эту задачу называют «задачей Баше на взвешивание», потому что она была упомянута в книге Клода Каспара Баше "Problemes plaisans et dekctables" (фр. «Приятные и восхитительные задачи»), опубликованной в 1612 году. Баше спрашивал, какое минимальное количество гирь необходимо для того, чтобы уравновесить любой вес от 1 до 40 фунтов? За 400 лет до Баше ее сформулировал Фибоначчи (Леонардо Пизанский). Этой задачей интересовался Дмитрий Иванович Менделеев в бытность свою управляющим Главной палатой мер и весов в Санкт-Петербурге.
2 По-видимому, предполагалось, что последний должен был убить себя сам.