МАЛЫЙ МЕХМАТ МГУ

Кружок 8 класса

Занятие 11. Сколько будет 2×2, или Системы Счисления

Системой счисления с основанием p называется способ записи чисел «с использованием p штук цифр: 0, 1, 2, …, (p-1)». Так, если a₀, a₁, a₂, …, a_n — цифры, то запись (a_n a_{n − 1}… a₁ a₀)_p означает записанное в p-ичной (то есть с основанием p; оно обозначается нижним индексом) системе число a_n· pⁿ + a_{n − 1}· p^{n − 1} + … + a₁· p + a₀. При p = 10 мы получим хорошо знакомую нам десятичную систему счисления, и основание 10, как правило, не указывается. Если p > 10, то цифры больше 9 заключают в скобки, чтобы отличить от многозначного числа. Например, (123)₁₂₈ = 123, 1(23)₁₂₈ = 1·128 + 23 = 151, (12)3₁₂₈ = 12·128 + 3 = 1539, 123₁₂₈ = 1·128² + 2·128 + 3 = 16643. Иногда, если таких цифр не очень много (например, в 16-ичной системе счисления), их обозначают латинскими буквами: (10) = A, (11) = B, (12) = C, (13) = D, (14) = E, (15) = F.

Естественным образом возникает вопрос о том, как переводить числа из одной системы счисления в другую. Чтобы перевести число из произвольной системы счисления в десятичную систему, надо просто применить определение системы счисления. Например, 127₈ = 1· 8² + 2· 8 + 7· 8⁰ = 64 + 16 + 7 = 87₁₀. Несколько сложнее переводить число из десятичной системы счисления в какую-нибудь другую. Пример приведен после задачи №1. Чтобы перевести число из одной недесятичной системы счисления в другую недесятичную систему, можно сначала перевести его в десятичную систему счисления, а уже из нее в окончательную.

Предупреждение: ответы к задачам могут содержать опечатки!

1.

Запишите

1)

1814₉ в десятичной системе счисления;

2)

101001₂ в десятичной системе;

3)

42163 в семеричной системе;

4)

666₈ в десятичной системе;

5)

1845 в тринадцатеричной системе;

6)

(10)9(11)₁₂ в десятичной системе;

7)

1566₇ в пятеричной системе;

8)

287₁₆ в четверичной системе;

9)

122111₃ в девятеричной системе;

10)

110110000011₂ в шестнадцатеричной системе.

Ответ Пример

Ответ. 1) 1814₉ = 1390;
2) 101001₂ = 41;
3) 42163 = 2336327;
4) 666₈ = 438;
5) 1845 = (10)(11)(12)₁₃;
6) (10)9(11)₁₂ = 1559;
7) 1566₇ = 636 = 10021₅;
8) 287₁₆ = 647 = 22013₄;
9) 122111₃ = 472=574₉;
10) 110110000011₂ = 3459 = (13)83₁₆.

Пример. Решим пункт 7 этой задачи. Сначала переведем число 1566₇ в десятичную систему счисления: 1566₇ = 1· 7³ + 5· 7² + 6· 7 + 6 = 343 + 245 + 42 + 6 = 636. Теперь число 636 надо представить в виде 636 = a₄ · 5⁴ + a₃ · 5³ + a₂ · 5² + a₁ · 5 + a₀. В этом разложении участвуют степени пятерки только от 0 до 4: 5⁴ = 625 < 636 < 3125 = 5⁵. Поделим 636 на 5⁴ = 625 с остатком. Неполное частное будет равно коэффициенту a₄, а остаток — a₃ · 5³ + a₂ · 5² + a₁ · 5 + a₀ (подумайте, почему). Деление можно производить в столбик. Находим, что 636 = 1·625 + 11. Таким образом, a₄ = 1. Теперь 11 будем делить с остатком на 5³ = 125. Ясно, что неполное частное будет равно 0, а остаток 11. Значит, a₃ = 0. Деля 11 на 25, вновь получим остаток 11 и неполное частное a₂ = 0. Далее, 11 = 2·5 + 1, откуда a₁ = 2, a₀ = 1. Записываем окончательный результат: 636 = 1 · 5⁴ + 0 · 5³ + 0 · 5² + 2 · 5 + 1 = 10021₅.

В системах счисления с произвольным основанием, как и в десятичной системе, можно выполнять сложение и умножение в столбик. Делается это соверщенно так же, как нас учили в начальной школе. Только следует помнить о количестве цифр в системе и вовремя переносить единицы в старший разряд. Например, 2₆ + 5₆ = 7₁₀ = 1· 6₁₀ + 1₁₀ = 11₆; 2₄ × 3₄ = 6₁₀ = 1· 4₁₀ + 2₁₀ = 12₄ и т.д. Но: 9₁₆ + 6₁₆ = 15₁₀ = (15)₁₆ = F₁₆. Чтобы сложить или перемножить два числа, записанные в разных системах счисления, надо сначала перевести их в одну систему счисления.

2.

Вычислите в столбик:

а)

1010011₂ + 1110110₂, 11011011₂ + 1011111₂;

b)

122121₃ + 212012₃, 1011202₃ + 112022₃;

c)

304234₅ + 211234₅, 34421214₅ + 11402342₅;

d)

102341₇ + 203114₇, 321₇ + 321₄.

Ответ

Ответ. a) 11011011, 100111010; b) 1111210, 1201001; c) 1021023, 101324111; d) 305355, 3123₄ = 432₇ = 219.

3.

Вы в начальной школе изучали таблицу умножения в десятичной системе счисления. Составьте таблицу умножения для систем счисления с основаниями 2, 3 и 5.

Ответ

Ответ.

a	1
1	1

b	1	2
1	1	2
2	2	11

c	1	2	3	4
1	1	2	3	4
2	2	4	11	13
3	3	11	14	22
4	4	13	22	31

4.

Вычислите в столбик:

а)

1001₂ × 1010₂;

b)

1221₃ × 2012₃;

c)

1122₃ × 120₃;

d)

1044₅ × 1234₅;

e)

3214₅ × 142₅;

f)

134₅ × 132₄.

Ответ

Ответ. a) 1011010; b) 1122022; c) 220110; d) 1411121; e) 1123043; f) 1320₁₀ = 110220₄ = 20240₅.

5.

Каким должно быть основание p системы счисления, чтобы в ней выполнялись равенства:

а)

4_p + 5_p = 12_p;

b)

8_p + 9_p = 10_p;

c)

2_p + 2_p = 11_p;

d)

3_p × 5_p = 21_p;

e)

5_p × 5_p = 15_p;

f)

2_p × 2_p = 5_p?

Решение

Решение. a) p + 2 = 12_p = 4_p + 5_p = 4 + 5 = 9, откуда p=7. Отсальные пункты решаются аналогично. b) p=17. c) p=3. d) p=7. e) p=20. f) Такой системы нет. Если p>4, то 2_p × 2_p = 4_p, а иначе 2_p × 2_p заведомо не однозначное.

6.

Ваня, Веня, Вася и аля ехали на троллейбусе. От нечего делать Ваня сидел у окна и считал троллейбусные столбы. Веня тоже считал столбы, но на другой стороне дороги.
— Ну и сколько вы насчитали? — спросил Вася, когда они вышли на остановке.
— Я насчитал ровно 100, — ответил Ваня.
— И я насчитал ровно 100, — ответил Веня.
— Не может быть! — усомнился Валя, который увлекался городским транспортом. — У Вани должно быть на 13 столбов больше, я гарантирую это!
— Может! — сказал Вася, увлекавшийся математикой. — Вы же считаете в разных системах счисления!
Определите, в каких системах счисления считали Ваня и Веня, если Валя считал в десятичной.

Ответ Решение

Ответ. p = 7, q = 6.

Решение. Пусть Ваня считал в системе с основанием p, а Веня — в системе с основанием q. Тогда Ваня и Веня насчитали 100_p = p² и 100_q = q² столбов соответственно. Из слов Вали следует, что p² − q² = (p − q)(p + q) = 13, поэтому p − q = 1, p + q = 13. В самом деле, число 13 имеет только делители 1 и 13, а p − q < p + q при натуральных p и q. Следовательно, p = 7, q = 6.

7.

а)

Ваня утверждает, что число делится на 3 тогда и только тогда, когда его запись в двенадцатеричной системе счисления оканчивается на одну из пяти определённых цифр. Прав ли Ваня?

b)

Веня утверждает, что число делится на 9 тогда и только тогда, когда число, образованное двумя последними цифрами в его шестеричной записи, делится на 9. Прав ли Веня?

c)

Валя утверждает, что число делится на 7 тогда и только тогда, когда сумма цифр в его восьмеричной записи делится на 7. Прав ли Валя?

Решение

Решение.

а) (a_n a_{n − 1}… a₁ a₀)₁₂= a_n· 12ⁿ + a_{n − 1}· 12^{n − 1} + … + a₁·12 + a₀. В этой сумме все слагаемые, кроме последнего, заведомо делятся на 3, так что ее делимость на 3 зависит только от последнего слагаемого. Из двенадцати цифр на 3 делятся цифры 0, 3, 6 и 9. Ваня чуть-чуть ошибся: «определённых цифр» не пять, а четыре.

b) Веня прав. Доказывается это аналогично предыдущему пункту. Только надо понимать, что число, образованное двумя последними цифрами, тоже считается записанным в шестеричной записи.

c) Валя прав. (a_n a_{n − 1}… a₁ a₀)₈ − (a_n + a_{n − 1} + … + a₁ + a₀) = a_n·(8ⁿ − 1) + a_{n − 1}·(8^{n − 1} − 1) + … + a₁·(8 − 1). Во всех слагаемых есть множитель 8^k − 1, который обязтельно делится на 7 (убедитесь в этом самостоятельно), поэтому сумма цифр даёт тот же остаток от деления на 7, что и само число.

8.

В 1885 году Витторио Грюнвальд предложил так называемые нега-позиционные системы счисления, то есть системы счисления с основанием p < 0. В такой нега-p-ичной системе используются цифры 0, 1, 2, …, (-p), а число по-прежнему записывается как (a_n a_{n − 1}… a₁ a₀)_p = a_n · pⁿ + a_{n − 1}· p^{n − 1} + … + a₁· p + a₀. Запишите в десятичной системе числа 10 _{− 10}, 1302 _{− 8}, 192 _{− 10}, (13)06 _{− 16}. Будьте внимательны со знаками!

Ответ

Ответ. 10 _{− 10} = − 10, 1302 _{− 8} = − 318, 192 _{− 10} = 12, (13)06 _{− 16} = 2334.

9.

Запишите 666 в нега-десятичной, 1204 в нега-шестнадцатеричной, 1408 в нега-десятичной и 57 в нега-двоичной системах счисления.

Ответ

Ответ. 666 = 746 _{− 10}, 1204 = 554 _{− 16}, 1408 = 19408 _{− 10}, 57 = 1001001 _{− 2}.

10.

Вася утверждает, что число делится на 11 тогда и только тогда, когда сумма его цифр в нега-десятичной записи делится на 11. Прав ли Вася?

Ответ

Ответ. Вася прав. Доказательство аналогично решению задачи 7с.