Тема : Кодирование чисел. Системы счисления

B7 (повышенный уровень, время – 2 мин)

• 
  принципы кодирования чисел в позиционных системах счисления
  
• 
  чтобы перевести число, скажем, 12345_N, из системы счисления с основанием в десятичную систему, нужно умножить значение каждой цифры на в степени, равной ее разряду:
  

• 
  последняя цифра записи числа в системе счисления с основанием – это остаток от деления этого числа на
  
• 
  две последние цифры – это остаток от деления на , и т.д.
  

Решите уравнение .
Ответ запишите в шестеричной системе счисления. Основание системы счисления указывать не нужно.

1. 
   удобнее всего перевести все числа в десятичную систему, решить уравнение и результат перевести в шестеричную систему
   
2. 
   получаем
   
3. 
   уравнение приобретает вид , откуда получаем
   
4. 
   переводим 15 в шестеричную систему счисления:
   
5. 
   ответ: 23.
   

6. 
   если запись числа в системе счисления с основанием N заканчивается на 0, то это число делится на N нацело
   
7. 
   поэтому в данной задаче требуется найти наименьшее натуральное число, которое делится одновременно на 3 и на 5, то есть, делится на 15
   
8. 
   очевидно, что это число 15.
   

9. 
   поскольку запись в системе счисления с основанием N заканчивается на 1, то остаток от деления числа 67 на N равен 1, то есть при некотором целом имеем
   

10. 
    следовательно, основание N – это делитель числа 66
    
11. 
    с другой стороны, запись числа содержит 4 цифры, то есть
    
12. 
    выпишем кубы и четвертые степени первых натуральных чисел, которые являются делителями числа 66:
    

13. 
    видим, что из этого списка только для числа N = 3 выполняется условие
    
14. 
    таким образом, верный ответ – 3.
    
15. 
    можно сделать проверку, переведя число 67 в троичную систему 67₁₀ = 2111₃
    

1. 
   поскольку запись в системе счисления с основанием N заканчивается на 3, то остаток от деления числа 381 на N равен 3, то есть при некотором целом имеем
   

2. 
   следовательно, основание N – это делитель числа
   
3. 
   с другой стороны, запись числа содержит 3 цифры, то есть
   
4. 
   неравенство дает (так как )
   
5. 
   неравенство дает (так как )
   
6. 
   таким образом, ; в этом диапазоне делителями числа 378 являются числа
   
   • 
     9, при получаем запись числа
     
   • 
     14, при получаем запись числа
     
   • 
     18, при получаем запись числа
     
7. 
   наибольшим из приведенных чисел – это 18 (можно было сразу искать подбором наибольший делитель числа 378, начиная с 19 «вниз», на уменьшение)
   
8. 
   таким образом, верный ответ – 18.
   

• 
  вспомним алгоритм перевода числа из десятичной системы в систему с основанием (см. презентацию), из него следует, что младшая цифра результата – это остаток от деления исходного числа на , а две младших цифры – это остаток от деления на и т.д.
  
• 
  в данном случае , остаток от деления числа на должен быть равен 11₄ = 5
  
• 
  потому задача сводится к тому, чтобы определить все числа, которые меньше или равны 25 и дают остаток 5 при делении на 16
  

1. 
   общий вид чисел, которые дают остаток 5 при делении на 16:
   

2. 
   среди всех таких чисел нужно выбрать те, что меньше или равны 25 («не превосходят 25»); их всего два: 5 (при ) и 21 (при )
   
3. 
   таким образом, верный ответ – 5, 21 .
   

Возможные ловушки и проблемы: выражение «не превосходящие » означает «меньшие или равные », а не строго меньшие остаток, состоящий из нескольких цифр (здесь – 114), нужно не забыть перевести в десятичную систему найденные числа нужно записать именно в порядке возрастания, как требуется

1. 
   переведем 25 в четверичную систему счисления: 25 = 121₄, все интересующие нас числа не больше этого значения
   
2. 
   из этих чисел выделим только те, которые заканчиваются на 11, таких чисел всего два:
   это 11₄ = 5 и 111₄ = 21
   
3. 
   таким образом, верный ответ – 5, 21 .
   

Возможные ловушки и проблемы: есть риск случайно «забыть» какое-то число или найти «лишнее» (в данном случае – большее 25) можно сделать ошибки при переводе чисел из четверичной системы в десятичную или вообще «забыть» перевести

• 
  здесь обратная задача – неизвестно основание системы счисления, мы обозначим его через
  
• 
  поскольку последняя цифра числа – 2, основание должно быть больше 2, то есть
  
• 
  вспомним алгоритм перевода числа из десятичной системы в систему с основанием (см. презентацию), из него следует, что младшая цифра результата – это остаток от деления исходного числа на
  

1. 
   итак, нужно найти все целые числа , такие что остаток от деления 23 на равен 2, или (что то же самое)
   

2. 
   сложность в том, что и , и неизвестны, однако здесь нужно «играть» на том, что это натуральные числа
   
3. 
   из формулы (*) получаем , так что задача сводится к тому, чтобы найти все делители числа 21, которые больше 2
   
4. 
   в этой задаче есть только три таких делителя: и
   
5. 
   таким образом, верный ответ – 3, 7, 21 .
   

Возможные ловушки и проблемы: нужно учесть, что основание системы счисления должно быть больше любой цифры числа, поэтому делитель не подходит (должно быть ) числа нужно записывать в ответе в порядке возрастания, как требуется по условию

• 
  неизвестно основание системы счисления, мы обозначим его через
  
• 
  пока будем считать, что запись числа 31 в системе с основанием состоит из трех цифр, причем две младшие (11) нам даны, а одну (обозначим ее через ) нужно найти:
  

• 
  можно показать, что при большем количестве разрядов эта формула также верна, то есть, число 31 можно представить как при некотором целом ; например, для числа с пятью разрядами получаем:
  

1. 
   итак, нужно найти все целые числа , такие что
   

2. 
   сложность в том, что и , и неизвестны, однако здесь нужно «играть» на том, что это натуральные числа
   
3. 
   из формулы (**) получаем , так что задача сводится к тому, чтобы найти все делители числа 30 и отобрать только те из них, для которых уравнение (**) разрешимо при целом , то есть, – целое число
   
4. 
   выпишем все делители числа 30, большие или равные 2: 2, 3, 5, 6, 10, 15, 30
   
5. 
   из всех этих делителей только для 2, 3, 5 и 30 значение – целое число (оно равно соответственно 7, 3, 1 и 0)
   
6. 
   таким образом, верный ответ – 2, 3, 5, 30.
   

1. 
   запишем первое и последнее число в заданном диапазоне в системе счисления с основанием 5:
   

2. 
   заметим, что оба они содержат цифру 2, так что, 2 цифры мы уже нашли
   
3. 
   между 20₅ и 32₅ есть еще числа
   

4. 
   в них 5 цифр 2 (в числе 22₅ – сразу две двойки), поэтому всего цифра 2 встречается 7 раз
   
5. 
   таким образом, верный ответ – 7.
   

Возможные ловушки и проблемы: нужно не забыть, что в системе счисления с основанием 5 старшая цифра – 4, то есть, вслед за 245 следует 305 помните, что нужно определить не количество чисел, в которых есть двойка, а количество самих двоек можно не обратить внимание на то, что в числе 225 цифра 2 встречается 2 раза

1. 
   переведем все указанные числа в систему счисления с основанием 5:
   

2. 
   считаем цифры 2 – получается 7 штук
   
3. 
   таким образом, верный ответ – 7 .
   

1. 
   обозначим через неизвестное основание системы счисления, тогда запись числа 30 в этой системе имеет вид
   

2. 
   вспомним алгоритм перевода числа из системы счисления с основанием в десятичную систему: расставляем сверху номера разрядов и умножаем каждую цифру на основание в степени, равной разряду:
   

3. 
   поскольку запись трехзначная, , поэтому
   
4. 
   с другой стороны, четвертой цифры нет, то есть, в третьем разряде – ноль, поэтому
   
5. 
   объединяя последние два условия, получаем, что искомое основание удовлетворяет двойному неравенству
   

6. 
   учитывая, что – целое число, методом подбора находим целые решения этого неравенства; их два – 4 и 5:
   

7. 
   минимальное из этих значений – 4
   
8. 
   таким образом, верный ответ – 4 .
   

1. 
   выполним п.1-4 так же, как и в предыдущем варианте решения
   
2. 
   найдем первое целое число, куб которого больше 30; это 4, так как
   

3. 
   проверяем второе неравенство: , поэтому в системе счисления с основанием 4 запись числа 30 трехзначна
   
4. 
   таким образом, верный ответ – 4 .
   

1. 
   нас интересуют числа от 1 до 30
   
2. 
   сначала определим, сколько цифр может быть в этих числах, записанных в системе счисления с основанием 5
   
3. 
   поскольку , в интересующих нас числах может быть от 1 до 3 цифр
   
4. 
   рассмотрим трехзначные числа, начинающиеся на 3 в системе с основанием 5:
   

5. 
   таким образом, остается рассмотреть только однозначные и двухзначные числа
   
6. 
   есть всего одно однозначное число, начинающееся на 3, это 3
   
7. 
   общий вид всех двузначных чисел, начинающихся на 3 в системе с основанием 5:
   

8. 
   используя эту формулу, находим интересующие нас двузначные числа – 15, 16, 17, 18 и 19
   
9. 
   таким образом, верный ответ – 3, 15, 16, 17, 18, 19 .
   

1. 
   нас интересуют числа от 1 до 30; сначала определим, сколько цифр может быть в пятеричной записи эти чисел
   
2. 
   поскольку , в интересующих нас числах может быть не более 2 цифр (все трехзначные пятеричные числа, начинающиеся с 3, больше 30)
   
3. 
   есть всего одно однозначное число, начинающееся на 3, это 3
   
4. 
   выпишем все пятеричные двузначные числа, которые начинаются с 3, и переведем их в десятичную систему: 30₅ = 15, 31₅ = 16, 32₅ = 17, 33₅ = 18 и 34₅ = 19
   
5. 
   таким образом, верный ответ – 3, 15, 16, 17, 18, 19 .
   

1. 
   Если число в системе с основанием оканчивается на 13, то
   
   1. 
      , потому что в системах с меньшим основанием нет цифры 3
      
   2. 
      это число можно представить в виде , где – целое неотрицательное число
      
2. 
   определим наибольшее возможное с учетом условия . Из уравнения следует .
   
3. 
   очевидно, что чем меньше , тем больше , поэтому значение не превышает
   

4. 
   остается перебрать все допустимые значения (от 0 до ), решая для каждого из них уравнение
   

5. 
   получаем
   
   1. 
      при :
      
   2. 
      при : решения – не целые числа
      
   3. 
      при : и , второе решение не подходит
      
6. 
   таким образом, верный ответ: 4, 68.
   

1. 
   запись числа71 в системе с основанием оканчивается на 13, т.е. в разряде единиц – 3, это значит, что остаток от деления 71 на равен 3, то есть для некоторого целогоимеем
   

2. 
   таким образом, искомые основания – делители числа 68; остается выбрать из них те, которые соответствуют другим условиям задачи
   
3. 
   среди чисел, оканчивающихся на 13 в системе счисления с основанием ,минимальное – это само число ; отсюда найдем максимальное основание:
   

4. 
   остальные числа, окачивающиеся в этой системе на 13, имеют не менее 3-х знаков (,…), т.е. все они больше
   
5. 
   поэтому , следовательно,
   
6. 
   по условию в записи числа есть цифра 3, поэтому (в системах с основанием  3 цифры 3 нет)
   
7. 
   итак: , и при этом – делитель 68; единственное возможное значение (на 5,6,7 и 8 число 68 не делится)
   
8. 
   таким образом, верный ответ: 4, 68.
   

Возможные ловушки и проблемы: на шаге 1 нужно вычесть из числа только число единиц, то есть младшую из двух заданных цифр (в примере – 3) можно забыть рассмотреть двузначное число, записанное заданными в условии цифрами (в примере – 13x ), и пропустить максимальное основание нужно помнить, что максимальная цифра на 1 меньше основания системы счисления 100 в системе с основанием p равно p2

1. 
   Если число в системе с основанием оканчивается на 22, то
   
   1. 
      , потому что в системах с меньшим основанием нет цифры 2
      
   2. 
      это число можно представить в виде , где – целое неотрицательное число
      
2. 
   определим наибольшее возможное с учетом условия . Из уравнения следует .
   
3. 
   очевидно, что чем меньше , тем больше , поэтому значение не превышает
   

4. 
   остается перебрать все допустимые значения (от 0 до ), решая для каждого из них уравнение
   

5. 
   получаем
   
   1. 
      при :
      
   2. 
      при : решения – не целые числа
      
   3. 
      при : и , второе решение не подходит
      
   4. 
      при : решения – не целые числа
      
6. 
   таким образом, верный ответ: 6, 42.
   

1. 
   запись числа 86 в системе с основанием оканчивается на 22, т.е. в разряде единиц – 2, это значит, что остаток от деления 86 на равен 2, то есть для некоторого целогоимеем
   

2. 
   таким образом, искомые основания – делители числа 84; остается выбрать из них те, которые соответствуют другим условиям задачи
   
3. 
   среди чисел, оканчивающихся на 22 в системе счисления с основанием ,минимальное – это само число ; отсюда найдем максимальное основание:
   

4. 
   остальные числа, окачивающиеся в этой системе на 22, имеют не менее 3-х знаков (,…), т.е. все они больше
   
5. 
   поэтому , следовательно,
   
6. 
   по условию в записи числа есть цифра 2, поэтому
   
7. 
   итак: , и при этом – делитель 84; возможные значения (на 5,8 и 9 число 84 не делится)
   
8. 
   переводя число 86 в системы счисления с основаниями , находим, что только для основания 6 запись числа оканчивается на 22 (при делении на 3, 4 и 7 «вторые» остатки не равны 2):
   

   8	6		3				^ Дальше делить нет смысла	8	6		4							8	6		6					8	6		7
   8	4		2	8		3		8	4		2	1			4			8	4		1	4		6		8	4		1	2		7
   	2		2	7		9…			2		2	0			5…				2		1	2		2			2			7		1
   				1								1										2								5

9. 
   таким образом, верный ответ: 6, 42.
   

1. 
   Из условия сразу видно, что искомое основание не меньше 4 (в записи есть цифра 3).
   
2. 
   Если запись числа 94 в некоторой системе счисления с основанием двузначна (94 = 23_x), то справедливо равенство ; нас интересуют натуральные решения этого уравнения, такие что , таких решений нет.
   
3. 
   Предположим, что число четырехзначное. Минимальное допустимое четырехзначное число – 2300_x, где . При минимальном основании () оно равно, поэтому запись нужного нам числа имеет не больше трех знаков.
   
4. 
   На основании (2) и (3) делаем вывод, что число трехзначное, то есть , где – целое неотрицательное число, такое что .
   
5. 
   Максимальное можно определить как решение уравнения (при ); получаем одно из решений – 6,15; поэтому
   
6. 
   Если мы знаем , то определится как ; пробуем подставлять в эту формулу , пытаясь получить
   
7. 
   Минимальное будет при : , а при получается
   
8. 
   Таким образом, верный ответ: 6.
   

1. 
   Несложно выполнить прямое сложение восьмеричных чисел, там быстро обнаруживается закономерность:
   

2. 
   Переведем последнюю сумму через триады в двоичный код (заменяем каждую восьмеричную цифру на 3 двоичных):
   

3. 
   Теперь разбиваем цепочку на тетрады (группы из 4-х двоичных цифр), начиная справа, и каждую тетраду представляем в виде шестнадцатеричной цифры
   

4. 
   Таким образом, верный ответ (третья цифра слева): 2.
   

1. 
   Поскольку в левой и в правой частях есть цифра 5, оба основания больше 5, то есть перебор имеет смысл начинать с .
   
2. 
   Очевидно, что , однако это не очень нам поможет.
   
3. 
   Для каждого «подозреваемого» вычисляем значение и решаем уравнение , причем нас интересуют только натуральные .
   
4. 
   Для и нужных решений нет, а для получаем
   

5. 
   Таким образом, верный ответ (минимальное значение ): 8.
   

1. 
   запись числа 30 в системе с основанием N длиннее, чем в десятичной (4 цифры против двух), поэтому основание N меньше 10
   
2. 
   это дает шанс решить задачу методом подбора, переводя в разные системы, начиная с N = 2 до N = 9
   
3. 
   переводим:
   

4. 
   дальше можно не переводить, поскольку запись 1010₃ удовлетворяет условию: заканчивается на 0 и содержит 4 цифры
   
5. 
   можно проверить, что при N ≥ 4 запись числа 30 содержит меньше 4 цифр, то есть не удовлетворяет условию
   
6. 
   Ответ: 3.
   

1. 
   запись числа 30 в системе с основанием N содержит ровно 4 цифры тогда и только тогда, когда старший разряд – третий, то есть
   

2. 
   первая часть двойного неравенства дает (в целых числах)
   
3. 
   вторая часть неравенства дает (в целых числах)
   
4. 
   объединяя результаты пп. 2 и 3 получаем, что N = 3
   
5. 
   заметим, что условие «оканчивается на 0» – лишнее, ответ однозначно определяется по количеству цифр
   
6. 
   Ответ: 3.