Цыпкин А.Г., Пинский А.И. Справочное пособие по математике с методами решения задач для поступающих в вузы
Подождите немного. Документ загружается.
538 Г л а в а 16. Элементы матем. логики. Системы счисления
оторое является условием истинности имплиации
α(1) , (>k Ý N) (α(k) º α(k + 1)) º (>n Ý N) (α(n)). (***)
Та а составное высазывание (***) истинно, то утвержде-
ние доазано.
Доажите, что при любом n Ý N:
1. делится на 11.
2. делится на 133.
3. n
5
– n ратно 5.
4. 5 · 2
3n – 2
+ 3
3n – 1
ратно 19.
5. n
7
– n ратно 7.
6. + 1 оанчивается цифрой 7 при n > 1.
7. Доажите, что если n четно, то делит-
ся на 323.
8. Доажите, что число
есть точный вадрат.
П р и м е р 2. Методом математичесой индуции доазать
формулу
1
2
+ 2
2
+ 3
2
+ ... + n
2
= . (*)
Р е ш е н и е. Высазывание α(n), означающее, что формула
(*) имеет место, определено при любом натуральном n.
Высазывание α(1) истинно, та а
1
2
= .
Предположим, что α(k) истинно, т. е. справедлива формула
1
2
+ 2
2
+ 3
2
+ ... + k
2
= .
Выясним, будет ли при этом условии истинно α(k + 1), т. е. бу-
дет ли верна формула
1
2
+ 2
2
+ 3
2
+ ... + (k + 1)
2
= . (**)
6
2n 3–
3
n 1+
3
n 1–
++
11
n 1+
12
2n 1–
+
2
2
n
20
n
16
n
3
n
–1–+
(10
n
10
n 1–
... + 1) (10
n 1+
5) + 1++ +
nn 1+()2 n 1+()
6
---------------------------------------------- -
123⋅⋅
6
-------------------
kk 1+()2 k 1+()
6
---------------------------------------------
k 1+()k 2+()2 k 1+()1+()
6
-----------------------------------------------------------------------------
§ 90. Метод математической индукции 539
При условии истинности высазывания α(k) левую часть
равенства (**) можно представить в виде
+ (k + 1)
2
. (***)
Преобразуем выражение (***):
= .
Заметим, что произведение (k + 2)(2(k + 1) + 1), входящее в
правую часть равенства (**), равно 2k
2
+ 7k + 6.
Таим образом, из истинности α(k) следует истинность
α(k + 1), т. е. для любоо натуральноо k доазана имплиация
α(k) º α(k + 1). Тем самым справедливость формулы (*) уста-
новлена.
Доажите, что для любоо натуральноо n справедливо ра-
венство:
19. 1 + 3 + 5 + ... + (2n – 1) = n
2
.
10. 1
2
+ 3
2
+ 5
2
+ ... + (2n + 1)
2
= .
11. 1 · 2 + 2 · 3 + ... + (n – 1)n = .
12. + + ... + = .
13. 1
3
+ 2
3
+ ... + n
3
= .
14. 1
5
+ 2
5
+ ... + n
5
= .
С помощью метода математичесой индуции удобно доа-
зывать справедливость неоторых неравенств.
Пример 3. Доазать, что при a > –1 справедливо нера-
венство
l 1 + na.
Р е ш е н и е. Проверим, что α(1) истинно. Действительно,
1 + a = 1 + a.
Предположим, что α(k) истинно, т. е.
(1 + a)
k
l 1 + ka.(*)
kk 1+()2 k 1+()
6
---------------------------------------------
k 1+()k(2k 1) 6 k 1+()++[]
6
-------------------------------------------------------------------------------- -
k 1+()2k
2
7k 6++()
6
-----------------------------------------------------------
n 4n
2
1–()
3
-----------------------------
n 1–()nn 1+()
3
------------------------------------------
1
13⋅
-----------
1
35⋅
-----------
1
2n 1–()2n 1+()
--------------------------------------------- -
n
2n 1+
------------------
n
2
n 1+()
2
4
---------------------------- -
n
2
n 1+()
2
2n
2
2n 1–+()
12
--------------------------------------------------------------------- -
(1 a)
n
+
538 Г л а в а 16. Элементы матем. логики. Системы счисления
оторое является условием истинности имплиации
α(1) , (>k Ý N) (α(k) º α(k + 1)) º (>n Ý N) (α(n)). (***)
Та а составное высазывание (***) истинно, то утвержде-
ние доазано.
Доажите, что при любом n Ý N:
1. делится на 11.
2. делится на 133.
3. n
5
– n ратно 5.
4. 5 · 2
3n – 2
+ 3
3n – 1
ратно 19.
5. n
7
– n ратно 7.
6. + 1 оанчивается цифрой 7 при n > 1.
7. Доажите, что если n четно, то делит-
ся на 323.
8. Доажите, что число
есть точный вадрат.
П р и м е р 2. Методом математичесой индуции доазать
формулу
1
2
+ 2
2
+ 3
2
+ ... + n
2
= . (*)
Р е ш е н и е. Высазывание α(n), означающее, что формула
(*) имеет место, определено при любом натуральном n.
Высазывание α(1) истинно, та а
1
2
= .
Предположим, что α(k) истинно, т. е. справедлива формула
1
2
+ 2
2
+ 3
2
+ ... + k
2
= .
Выясним, будет ли при этом условии истинно α(k + 1), т. е. бу-
дет ли верна формула
1
2
+ 2
2
+ 3
2
+ ... + (k + 1)
2
= . (**)
6
2n 3–
3
n 1+
3
n 1–
++
11
n 1+
12
2n 1–
+
2
2
n
20
n
16
n
3
n
–1–+
(10
n
10
n 1–
... + 1) (10
n 1+
5) + 1++ +
nn 1+()2 n 1+()
6
---------------------------------------------- -
123⋅⋅
6
-------------------
kk 1+()2 k 1+()
6
---------------------------------------------
k 1+()k 2+()2 k 1+()1+()
6
-----------------------------------------------------------------------------
§ 90. Метод математической индукции 539
При условии истинности высазывания α(k) левую часть
равенства (**) можно представить в виде
+ (k + 1)
2
. (***)
Преобразуем выражение (***):
= .
Заметим, что произведение (k + 2)(2(k + 1) + 1), входящее в
правую часть равенства (**), равно 2k
2
+ 7k + 6.
Таим образом, из истинности α(k) следует истинность
α(k + 1), т. е. для любоо натуральноо k доазана имплиация
α(k) º α(k + 1). Тем самым справедливость формулы (*) уста-
новлена.
Доажите, что для любоо натуральноо n справедливо ра-
венство:
19. 1 + 3 + 5 + ... + (2n – 1) = n
2
.
10. 1
2
+ 3
2
+ 5
2
+ ... + (2n + 1)
2
= .
11. 1 · 2 + 2 · 3 + ... + (n – 1)n = .
12. + + ... + = .
13. 1
3
+ 2
3
+ ... + n
3
= .
14. 1
5
+ 2
5
+ ... + n
5
= .
С помощью метода математичесой индуции удобно доа-
зывать справедливость неоторых неравенств.
Пример 3. Доазать, что при a > –1 справедливо нера-
венство
l 1 + na.
Р е ш е н и е. Проверим, что α(1) истинно. Действительно,
1 + a = 1 + a.
Предположим, что α(k) истинно, т. е.
(1 + a)
k
l 1 + ka.(*)
kk 1+()2 k 1+()
6
---------------------------------------------
k 1+()k(2k 1) 6 k 1+()++[]
6
-------------------------------------------------------------------------------- -
k 1+()2k
2
7k 6++()
6
-----------------------------------------------------------
n 4n
2
1–()
3
-----------------------------
n 1–()nn 1+()
3
------------------------------------------
1
13⋅
-----------
1
35⋅
-----------
1
2n 1–()2n 1+()
--------------------------------------------- -
n
2n 1+
------------------
n
2
n 1+()
2
4
---------------------------- -
n
2
n 1+()
2
2n
2
2n 1–+()
12
--------------------------------------------------------------------- -
(1 a)
n
+
540 Г л а в а 16. Элементы матем. логики. Системы счисления
Доажем теперь, что истинность α(k + 1) следует из истин-
ности α(k). Умножив обе части неравенства (*) на 1 + a, имеем
(1 + a)
k + 1
l (1 + ka)(1 + a),
или
(1 + a)
k + 1
l 1 + (k + 1)a + ka
2
.
Та а ka
2
l 0, то справедливо неравенство
(1 + a)
k + 1
l 1 + (k + 1)a.
Значит, доазана имплиация α(k) º α(k + 1). Ита, спра-
ведливость исходноо неравенства установлена.
Доажите, что для любоо n Ý N справедливо неравенство:
15. m , если x
i
> 0 (1 m i m n).
16. · · ... <
17. < 1 + + ... + < n.
18. (1 – x
1
)(1 – x
2
) ... (1 – x
n
) l 0,5, если x
i
> 0 (1 m i m n)
и x
1
+ x
2
+ ... + x
n
m 0,5.
19. x
1
x
2
... x
n
m , если x
i
> 0 (1 m i m n) и x
1
+ x
2
+ ...
... + x
n
= a.
20. + + + ... + > .
21. > .
22. Пользуясь тем, что ln (1 + x) < x, доажите неравенство
1 + + + ... + > ln (n + 1).
§ 91. Системы счисления
Здесь мы будем рассматривать тольо та называемые пози-
ционные системы счисления. Напомним, что целое число A
называют записанным в (позиционной) системе счисления с ос-
x
1
x
2
... x
n
+++
n
---------------------------------------------- -
x
1
x
2
...x
n
n
1
2
---
3
4
---
5
6
---
2n 1–
2n
-----------------
1
3n 1+
---------------------- .
n
2
---
1
2
---
1
2
n
1–
----------------
a
n
---
n
1
1
-------
1
2
-------
1
3
-------
1
n
-------
n
4
n
n 1+
------------- -
2n()!
n!()
2
--------------
1
2
---
1
3
---
1
n
---
§ 91. Системы счисления 541
нованием t (или, ороче, в t-ичной системе счисления, де t > 1,
t Ý N), если оно представлено в виде
A =
де 0 m a
i
< t, i = 0, 1, ..., n.
Числа a
0
, a
1
, ..., a
n
называют t-ичными цифрами числа A,
а число t— основанием t-ичной системы счисления.
При t = 10 получаем десятичную систему счисления.
Ясно, что a
0
= A – является остатом от
деления A на t. При делении A на t неполное частное имеет вид
Если разделить ео на t, то в остате полу-
чим a
1
. Поступая далее та же, будем последовательно получать
все цифры числа A в t-ичной системе.
Если число A имеет вид
A = a
n
t
–n
+ a
n – 1
t
–n + 1
+ ... + a
1
· t
–1
,
то для получения цифр этоо числа ео требуется умножать по-
следовательно на t. При первом умножении имеем
At =
здесь a
1
— целое число. Чтобы найти a
2
, следует умножить на t
число At – a
1
; тода a
2
будет следующей цифрой данноо числа.
Поступая та далее, мы будем получать последовательно циф-
ры дробноо числа A в t-ичной записи.
П р и м е р 1. Записать числа 506 и 0,506 в системе счисле-
ния с основанием 4.
Решение. Соласно изложенному выше алоритму, имеем
Записывая подчернутые остати в обратном поряде, по-
лучаем запись числа 506 в четверичной системе счисления:
(506)
10
= (13322)
4
.
506 4
2
126 4
2
31 4
3
74
3
1
a
n
t
n
a
n 1–
t
n 1–
... + a
1
ta
0
,+++
(a
n
t
n
... + a
1
t)+
a
n
t
n 1–
... + a
1
.+
a
n
t
n–1+
a
n 1–
t
n–2+
... + a
1
;++
540 Г л а в а 16. Элементы матем. логики. Системы счисления
Доажем теперь, что истинность α(k + 1) следует из истин-
ности α(k). Умножив обе части неравенства (*) на 1 + a, имеем
(1 + a)
k + 1
l (1 + ka)(1 + a),
или
(1 + a)
k + 1
l 1 + (k + 1)a + ka
2
.
Та а ka
2
l 0, то справедливо неравенство
(1 + a)
k + 1
l 1 + (k + 1)a.
Значит, доазана имплиация α(k) º α(k + 1). Ита, спра-
ведливость исходноо неравенства установлена.
Доажите, что для любоо n Ý N справедливо неравенство:
15. m , если x
i
> 0 (1 m i m n).
16. · · ... <
17. < 1 + + ... + < n.
18. (1 – x
1
)(1 – x
2
) ... (1 – x
n
) l 0,5, если x
i
> 0 (1 m i m n)
и x
1
+ x
2
+ ... + x
n
m 0,5.
19. x
1
x
2
... x
n
m , если x
i
> 0 (1 m i m n) и x
1
+ x
2
+ ...
... + x
n
= a.
20. + + + ... + > .
21. > .
22. Пользуясь тем, что ln (1 + x) < x, доажите неравенство
1 + + + ... + > ln (n + 1).
§ 91. Системы счисления
Здесь мы будем рассматривать тольо та называемые пози-
ционные системы счисления. Напомним, что целое число A
называют записанным в (позиционной) системе счисления с ос-
x
1
x
2
... x
n
+++
n
---------------------------------------------- -
x
1
x
2
...x
n
n
1
2
---
3
4
---
5
6
---
2n 1–
2n
-----------------
1
3n 1+
---------------------- .
n
2
---
1
2
---
1
2
n
1–
----------------
a
n
---
n
1
1
-------
1
2
-------
1
3
-------
1
n
-------
n
4
n
n 1+
------------- -
2n()!
n!()
2
--------------
1
2
---
1
3
---
1
n
---
§ 91. Системы счисления 541
нованием t (или, ороче, в t-ичной системе счисления, де t > 1,
t Ý N), если оно представлено в виде
A =
де 0 m a
i
< t, i = 0, 1, ..., n.
Числа a
0
, a
1
, ..., a
n
называют t-ичными цифрами числа A,
а число t— основанием t-ичной системы счисления.
При t = 10 получаем десятичную систему счисления.
Ясно, что a
0
= A – является остатом от
деления A на t. При делении A на t неполное частное имеет вид
Если разделить ео на t, то в остате полу-
чим a
1
. Поступая далее та же, будем последовательно получать
все цифры числа A в t-ичной системе.
Если число A имеет вид
A = a
n
t
–n
+ a
n – 1
t
–n + 1
+ ... + a
1
· t
–1
,
то для получения цифр этоо числа ео требуется умножать по-
следовательно на t. При первом умножении имеем
At =
здесь a
1
— целое число. Чтобы найти a
2
, следует умножить на t
число At – a
1
; тода a
2
будет следующей цифрой данноо числа.
Поступая та далее, мы будем получать последовательно циф-
ры дробноо числа A в t-ичной записи.
П р и м е р 1. Записать числа 506 и 0,506 в системе счисле-
ния с основанием 4.
Решение. Соласно изложенному выше алоритму, имеем
Записывая подчернутые остати в обратном поряде, по-
лучаем запись числа 506 в четверичной системе счисления:
(506)
10
= (13322)
4
.
506 4
2
126 4
2
31 4
3
74
3
1
a
n
t
n
a
n 1–
t
n 1–
... + a
1
ta
0
,+++
(a
n
t
n
... + a
1
t)+
a
n
t
n 1–
... + a
1
.+
a
n
t
n–1+
a
n 1–
t
n–2+
... + a
1
;++
542 Г л а в а 16. Элементы матем. логики. Системы счисления
Чтобы получить запись дробноо числа 0,506 в четверичной
системе счисления, воспользуемся изложенным выше алорит-
мом и выполним следующие вычисления:
0,506 · 4 = 2
,024, 0,024 · 4 = 0,096, 0,096 · 4 = 0,384,
0,384 · 4 = 1
,436, 0,436 · 4 = 1,744, 0,744 · 4 = 2,976,
и т. д. Цифры получающеося числа — это последовательные
целые части результатов умножения, т. е.
(0,506)
10
d (0,200112...)
4
.
Ответ.(506)
10
= (13322)
4
; (0,506)
10
= (0,200112...)
4
.
П р и м е р 2. В лассе 24 девочи и 32 мальчиа, всео 100
челове. В аой системе счисления записаны числа?
Р е ш е н и е. Составим уравнение
2 · p
1
+ 4 · p
0
+ 3 · p
1
+ 2 · p
0
= p
2
,
де p— неизвестное основание системы счисления. Приводя
подобные члены, получим уравнение
5p + 6 = p
2
,
орни отороо p
1
= 6, p
2
= –1.
Ответ. Числа записаны в шестеричной системе счисления.
Запишите данное число в уазанной системе счисления:
1. (10000)
10
в шестеричной системе.
2. (114144)
6
в десятичной системе.
3. (101)
2
в десятичной системе.
4. (25)
7
в десятичной системе.
5. В системе счисления с основанием 5 дано число 120010.
Запишите ео в десятичной системе. Каому числу будет соот-
ветствовать данная запись, если система счисления четвертичная?
Для чисел, записанных в десятичной системе, используют
правила умножения и сложения «столбиом», деления «улом».
Эти же правила полностью применимы в любой позиционной
системе счисления.
Сложение «столбиом», а и в десятичной системе, вседа
производят поразрядно, начиная с младшео разряда. При этом
если в предыдущем разряде сумма превышает основание систе-
мы или равна ему, то нужно выполнить перенос в следующий
разряд.
§ 91. Системы счисления 543
П р и м е р 3. Сложить «столбиом» числа (1357)
8
и (2463)
8
.
Р е ш е н и е. Имеем
Сладывая в разряде единиц 7 и 3, получаем 10 = 8 + 2, 2 за-
писываем, а 1 переносим в следующий разряд. Далее, 1 + 5 + 6 =
= 12, 12 = 8 + 4, 4 записываем, а 1 переносим в следующий раз-
ряд; 1 + 3 + 4 = 8, 8 = 1 · 8 + 0, 0 записываем, а 1 переносим
в следующий разряд.
Ответ. (4042)
8
.
При умножении следует сначала выписать таблицу умноже-
ния чисел, меньших основания системы.
Возьмем в ачестве примера таблицу умножения шестерич-
ной системы:
Все числа в таблице записаны в шестеричной системе счис-
ления. На пересечении данных столбца и строи находятся
числа, являющиеся произведением номеров строи и столбца.
Пользуясь этой таблицей, лео перемножать числа «столбиом».
П р и м е р 4. Умножить число (142)
6
на (212)
6
.
Ответ. (34544)
6
.
+
(1357)
8
(2463)
8
(4042)
8
12345
112345
2 2 4 10 12 14
3 3 10 13 20 23
4 4 12 20 24 32
5 5 14 23 32 41
Решение. (142)
6
(212)
6
(324)
6
(142)
6
0
(324)
6
00
(34544)
6
542 Г л а в а 16. Элементы матем. логики. Системы счисления
Чтобы получить запись дробноо числа 0,506 в четверичной
системе счисления, воспользуемся изложенным выше алорит-
мом и выполним следующие вычисления:
0,506 · 4 = 2
,024, 0,024 · 4 = 0,096, 0,096 · 4 = 0,384,
0,384 · 4 = 1
,436, 0,436 · 4 = 1,744, 0,744 · 4 = 2,976,
и т. д. Цифры получающеося числа — это последовательные
целые части результатов умножения, т. е.
(0,506)
10
d (0,200112...)
4
.
Ответ.(506)
10
= (13322)
4
; (0,506)
10
= (0,200112...)
4
.
П р и м е р 2. В лассе 24 девочи и 32 мальчиа, всео 100
челове. В аой системе счисления записаны числа?
Р е ш е н и е. Составим уравнение
2 · p
1
+ 4 · p
0
+ 3 · p
1
+ 2 · p
0
= p
2
,
де p— неизвестное основание системы счисления. Приводя
подобные члены, получим уравнение
5p + 6 = p
2
,
орни отороо p
1
= 6, p
2
= –1.
Ответ. Числа записаны в шестеричной системе счисления.
Запишите данное число в уазанной системе счисления:
1. (10000)
10
в шестеричной системе.
2. (114144)
6
в десятичной системе.
3. (101)
2
в десятичной системе.
4. (25)
7
в десятичной системе.
5. В системе счисления с основанием 5 дано число 120010.
Запишите ео в десятичной системе. Каому числу будет соот-
ветствовать данная запись, если система счисления четвертичная?
Для чисел, записанных в десятичной системе, используют
правила умножения и сложения «столбиом», деления «улом».
Эти же правила полностью применимы в любой позиционной
системе счисления.
Сложение «столбиом», а и в десятичной системе, вседа
производят поразрядно, начиная с младшео разряда. При этом
если в предыдущем разряде сумма превышает основание систе-
мы или равна ему, то нужно выполнить перенос в следующий
разряд.
§ 91. Системы счисления 543
П р и м е р 3. Сложить «столбиом» числа (1357)
8
и (2463)
8
.
Р е ш е н и е. Имеем
Сладывая в разряде единиц 7 и 3, получаем 10 = 8 + 2, 2 за-
писываем, а 1 переносим в следующий разряд. Далее, 1 + 5 + 6 =
= 12, 12 = 8 + 4, 4 записываем, а 1 переносим в следующий раз-
ряд; 1 + 3 + 4 = 8, 8 = 1 · 8 + 0, 0 записываем, а 1 переносим
в следующий разряд.
Ответ. (4042)
8
.
При умножении следует сначала выписать таблицу умноже-
ния чисел, меньших основания системы.
Возьмем в ачестве примера таблицу умножения шестерич-
ной системы:
Все числа в таблице записаны в шестеричной системе счис-
ления. На пересечении данных столбца и строи находятся
числа, являющиеся произведением номеров строи и столбца.
Пользуясь этой таблицей, лео перемножать числа «столбиом».
П р и м е р 4. Умножить число (142)
6
на (212)
6
.
Ответ. (34544)
6
.
+
(1357)
8
(2463)
8
(4042)
8
12345
112345
2 2 4 10 12 14
3 3 10 13 20 23
4 4 12 20 24 32
5 5 14 23 32 41
Решение. (142)
6
(212)
6
(324)
6
(142)
6
0
(324)
6
00
(34544)
6
544 Г л а в а 16. Элементы матем. логики. Системы счисления
П р и м е р 5. Разделить «улом» число (120101)
3
на (102)
3
.
Таим образом, (120101)
3
= (1101)
3
· (102)
3
+ (22)
3
.
Ответ.(1101)
3
· (102)
3
+ (22)
3
.
16. Сложите числа (23651)
8
и (17043)
8
.
17. Сложите числа (423)
6
, (1341)
6
и (521)
6
.
18. Умножьте число (352)
6
на (245)
6
.
19. Составьте таблицу умножения двоичной системы.
10. Перемножьте числа (101)
2
и (100)
2
. Результат представь-
те в десятичной системе.
11. Доажите, что число (121)
n
является полным вадра-
том, если n > 2.
12. Доажите, что число (1331)
n
является полным убом,
если n > 3.
13. В аой системе счисления справедливо равенство
31 – 13 = 13?
14. Найдите частное от деления (1111)
3
на (22)
3
.
15. В аой системе счисления справедливо равенство
101 · 11 = 1111?
16. Доажите, что если масса тела выражается целым чис-
лом и не превосходит 31 , то ее можно определить с помощью
не более пяти ирь при условии, что ири ставятся тольо на
одну чашу весов. Уажите массы ирь.
17. Доажите, что если масса тела выражается целым чис-
лом и не превосходит 40 , а взвешивание выполняется на ры-
чажных весах (т. е. ири моут быть установлены на любую
чашу весов), то для определения массы тела понадобится не
более четырех ирь. Найдите массы этих ирь и опишите ало-
ритм взвешивания.
Р е ш е н и е. (120101)
3
(102)
3
(102)
3
(1101)
3
0(111)
3
0(102)
3
000(201)
3
000(102)
3
0000(22)
3
§ 91. Системы счисления 545
18. Пусть условия взвешивания таие же, а в упр. 17, и
известно, что — масимальная масса, оторую удается оп-
ределить с помощью p имеющихся ирь. Доажите, что если
— масимальная масса, оторую удается определить
с помощью p + 1 ири, то = 3M
p
+ 1.
19. Доажите, что если — масимальная масса руза,
оторую можно определить с помощью m
1
, ..., ирь, то
= .
20. Выясните, аое минимальное число ирь и аой массы
потребуется для взвешивания тела массой m (m m n) на рычаж-
ных весах. Уажите алоритм взвешивания.
21. Пусть r = pa, де a— основание системы счисления, p—
число разрядов. Если r = 30, то в аой системе счисления
можно представить масимальное число?
С представлением числа в той или иной системе счисления
связаны признаи делимости числа, оторые формулируются
на основе цифровой записи числа.
П р и м е р 6. Вывести призна делимости на 3 в десятич-
ной системе счисления.
Р е ш е н и е. Представим число A = в виде
A = =
= =
=
Все числа 10
k
– 1 делятся на 3, следовательно, A делится на 3
в том и тольо в том случае, если (т. е.
сумма ео цифр) делится на 3.
22. Доажите, что A = делится на 9, если
делится на 9.
23. Доажите, что A = делится на 6, если
a
0
делится на 6.
M
p
M
p 1+
M
p 1+
M
p
m
p
M
p
(11...1)
3
p единиц
(a
n
a
n 1–
... a
0
)
10
a
n
· 10
n
a
n 1–
· 10
n 1–
... + a
0
· 10
0
++
a
n
(10
n
1–1)a
n 1–
(10
n 1–
1– 1) ... + a
0
· 10
0
++ ++
a
n
(10
n
1)– a
n 1–
(10
n 1–
1)– ...++
... + a
1
(10 1)– a
n
a
n 1–
...+ a
1
a
0
.++ + +
a
n
a
n 1–
... + a
1
a
0
,++ +
(a
n
a
n 1–
...a
0
)
10
a
n
a
n 1–
... a
0
+++
(a
n
a
n 1–
...a
0
)
12
544 Г л а в а 16. Элементы матем. логики. Системы счисления
П р и м е р 5. Разделить «улом» число (120101)
3
на (102)
3
.
Таим образом, (120101)
3
= (1101)
3
· (102)
3
+ (22)
3
.
Ответ.(1101)
3
· (102)
3
+ (22)
3
.
16. Сложите числа (23651)
8
и (17043)
8
.
17. Сложите числа (423)
6
, (1341)
6
и (521)
6
.
18. Умножьте число (352)
6
на (245)
6
.
19. Составьте таблицу умножения двоичной системы.
10. Перемножьте числа (101)
2
и (100)
2
. Результат представь-
те в десятичной системе.
11. Доажите, что число (121)
n
является полным вадра-
том, если n > 2.
12. Доажите, что число (1331)
n
является полным убом,
если n > 3.
13. В аой системе счисления справедливо равенство
31 – 13 = 13?
14. Найдите частное от деления (1111)
3
на (22)
3
.
15. В аой системе счисления справедливо равенство
101 · 11 = 1111?
16. Доажите, что если масса тела выражается целым чис-
лом и не превосходит 31 , то ее можно определить с помощью
не более пяти ирь при условии, что ири ставятся тольо на
одну чашу весов. Уажите массы ирь.
17. Доажите, что если масса тела выражается целым чис-
лом и не превосходит 40 , а взвешивание выполняется на ры-
чажных весах (т. е. ири моут быть установлены на любую
чашу весов), то для определения массы тела понадобится не
более четырех ирь. Найдите массы этих ирь и опишите ало-
ритм взвешивания.
Р е ш е н и е. (120101)
3
(102)
3
(102)
3
(1101)
3
0(111)
3
0(102)
3
000(201)
3
000(102)
3
0000(22)
3
§ 91. Системы счисления 545
18. Пусть условия взвешивания таие же, а в упр. 17, и
известно, что — масимальная масса, оторую удается оп-
ределить с помощью p имеющихся ирь. Доажите, что если
— масимальная масса, оторую удается определить
с помощью p + 1 ири, то = 3M
p
+ 1.
19. Доажите, что если — масимальная масса руза,
оторую можно определить с помощью m
1
, ..., ирь, то
= .
20. Выясните, аое минимальное число ирь и аой массы
потребуется для взвешивания тела массой m (m m n) на рычаж-
ных весах. Уажите алоритм взвешивания.
21. Пусть r = pa, де a— основание системы счисления, p—
число разрядов. Если r = 30, то в аой системе счисления
можно представить масимальное число?
С представлением числа в той или иной системе счисления
связаны признаи делимости числа, оторые формулируются
на основе цифровой записи числа.
П р и м е р 6. Вывести призна делимости на 3 в десятич-
ной системе счисления.
Р е ш е н и е. Представим число A = в виде
A = =
= =
=
Все числа 10
k
– 1 делятся на 3, следовательно, A делится на 3
в том и тольо в том случае, если (т. е.
сумма ео цифр) делится на 3.
22. Доажите, что A = делится на 9, если
делится на 9.
23. Доажите, что A = делится на 6, если
a
0
делится на 6.
M
p
M
p 1+
M
p 1+
M
p
m
p
M
p
(11...1)
3
p единиц
(a
n
a
n 1–
... a
0
)
10
a
n
· 10
n
a
n 1–
· 10
n 1–
... + a
0
· 10
0
++
a
n
(10
n
1–1)a
n 1–
(10
n 1–
1– 1) ... + a
0
· 10
0
++ ++
a
n
(10
n
1)– a
n 1–
(10
n 1–
1)– ...++
... + a
1
(10 1)– a
n
a
n 1–
...+ a
1
a
0
.++ + +
a
n
a
n 1–
... + a
1
a
0
,++ +
(a
n
a
n 1–
...a
0
)
10
a
n
a
n 1–
... a
0
+++
(a
n
a
n 1–
...a
0
)
12
546 Г л а в а 16. Элементы матем. логики. Системы счисления
24. Доажите, что A = делится на 8, если
(a
1
a
0
)
12
делится на 8.
25. Доажите, что A = делится на 11, если
делится на 11.
26. Доажите, что A = делится на p – 1 в том
и тольо в том случае, если делится на p – 1.
27. Известно, что число A = делится на 7. Доажи-
те, что p ратно 7.
28. Известно, что число A = делится на 11. Доа-
жите, что p ратно 11.
29. Доажите, что если основание системы счисления p—
простое число, большее 3, то – 1 делится на (100)
5
– 1.
(a
n
a
n 1–
...a
0
)
12
(a
n
a
n 1–
...a
0
)
12
a
n
a
n 1–
... a
0
+++
(a
n
a
n 1–
...a
0
)
p
a
n
a
n 1–
... a
0
+++
(3630)
p
(1210)
p
(100)
p
546 Г л а в а 16. Элементы матем. логики. Системы счисления
24. Доажите, что A = делится на 8, если
(a
1
a
0
)
12
делится на 8.
25. Доажите, что A = делится на 11, если
делится на 11.
26. Доажите, что A = делится на p – 1 в том
и тольо в том случае, если делится на p – 1.
27. Известно, что число A = делится на 7. Доажи-
те, что p ратно 7.
28. Известно, что число A = делится на 11. Доа-
жите, что p ратно 11.
29. Доажите, что если основание системы счисления p—
простое число, большее 3, то – 1 делится на (100)
5
– 1.
(a
n
a
n 1–
...a
0
)
12
(a
n
a
n 1–
...a
0
)
12
a
n
a
n 1–
... a
0
+++
(a
n
a
n 1–
...a
0
)
p
a
n
a
n 1–
... a
0
+++
(3630)
p
(1210)
p
(100)
p