Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В

• Название: Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
• Дата: 16.10.2022
• Размер: 3.28 Mb.
• Имя файла: algebra.pdf
• Тип: Учебное пособие; #736986
• страница: 22 из 71

13.9. а) Покажем, что если a
>
0 и (1 +
a
)
n
>
1 + n
a
, то. Действительно, (1+
a
)
n
+1
=(1+
a
)(1
+
a
)
n
>
>
(1
+
a
)(1
+ n
a
)
= 1 + (n + 1)
a
+ n
a
2
>
1 + (n + 1)
a б) Для n = 1 требуемое неравенство выполняется. Предположим, что если 0 <
a
6 1/n, то выполняется неравенство (1 +
a
)
n
<
<
1 + n
a
+ n
2
a
2
. Пусть число таково, что 0 <
b
6 1/(n + 1). Тогда b
6 1/n, поэтому (1 +
b
)
n
+1
<
(1
+ n
b
+ n
2
b
2
)(1
+
b
)
= 1 + (n + 1)
b
+
+ (n
2
+ n + n
2
b
)
b
2
. Остаётся проверить, что n
2
+ n + n
2
b
6
(n
+ те. Это неравенство следует из того, что b
6 1/(n + и n
2
<
(n
+ 1)
2

Решения задач. Докажем сначала требуемое неравенство для чисел вида индукцией по m. Для m = 1 оно следует из того,
что a − 2
√
ab
+ b = (
√
a
−
√
b)
2
>
0; равенство достигается, только если. Предположим, что требуемое неравенство доказано для и докажем его для m + 1. Ясно, что a
k
a
k
+2
m
6
((a
k
+ Поэтому. . . a
2
m+1
)
1/2
m+1 6
(b
1
b
2
. . . где b
k
= (a
k
+ a
k
+2
m
)/2, а по предположению индукции. . . b
2
m
)
1/2
m
6 1
2
m
(b
1
+ . . . + b
2
m
)
=
1 2
m
+1
(a
1
+ . . . + Пусть теперь n любое. Тогда n < для некоторого m. Положим. Ясно, что (a
1
+ . . . + a
n
)
+
+ (a
n
+1
+ . . . + a
2
m
)
= nA + (2
m
−n)A=2
m
A и a
1
. . . a
2
m
= a
1
. . . a
n
· Поэтому a
1
. . . a
n
· A
2
m
−n
6
(2
m
A/2
m
)
2
m
= A
2
m
, те равенство достигается, только если a
1
= . . . = a
n
13.11. Для n = 2, 4 и 5 требуемое неравенство несложно проверить. Покажем, что при n > 5 из неравенства следует неравенство. По предположению индукции поэтому нужно лишь проверить неравенство 2n
3
>
3n
2
+ 3n + При n > 5 выполняются неравенства 1 < 3n < 3n
2
<
2n
3
/3, поэтому+ 3n + 1 < 3(2n
3
/3)
= 2n
3
13.12. Пусть a =
r
2 +
q
2 + . . . +
√
2
|
{z
}
n
−1 раз. Тогда r
2 +
q
2 + . . . +
√
2
|
{z
}
n раз + Таким образом, требуется доказать, что −
√
2 + a
2 − a
>
1 Индукцией по n легко доказать, что a < 2. Поэтому следующие неравенства эквивалентны требуемому − 4
√
2 + a > 2 − a,
6 + a > 4
√
2 + После возведения в квадрат получаем неравенство 36 + 12a + a
2
>
>
32 + 16a, те Глава 13. Индукция. Применим индукцию по n. При n=1 получаем очевидное тождество. Равенство 2
+
a
1
a
2
a
3 4
+ . . . +
a
1
a
2
. . . a
n
a
n
+1 2
n
”
p
4
=
= a
1
p
2
+ a
1
“
a
2
+
a
2
a
3 2
+ . . . +
a
2
a
3
. . . a
n
+1 показывает, что cos 2
“
a
1
+
a
1
a
2 2
+
a
1
a
2
a
3 4
+ . . . +
a
1
a
2
. . . a
n
a
n
+1 2
n
”
p
4
=
= − sin
“
a
2
+
a
2
a
3 2
+ . . . +
a
2
a
3
. . . a
n
+1 Из этой формулы и тождества 2 sin a
2
= ±
√
2 − 2 cos следует, что sin
“
a
1
+
a
1
a
2 2
+
a
1
a
2
a
3 4
+ . . . +
a
1
a
2
. . . a
n
a
n
+1 2
n
”
p
4
=
= ±a
1
r
2 + 2 sin
“
a
2
+
a
2
a
3 2
+ . . . +
a
2
a
3
. . . a
n
a
n
+1 Нетрудно также убедиться, что в действительности всегда бе- рётся знак плюс, поскольку знак числа a
1
+
a
1
a
2 2
+
a
1
a
2
a
3 4
+ . . .
. . .
+
a
1
a
2
. . . a
n
a
n
+1 совпадает со знаком числа a
1
. Теперь, воспользовавшись предположением индукции, получаем требуемое тождество. Применим индукцию по числу автомобилей n. При n = утверждение очевидно. Предположим, что утверждение доказано для n автомобилей. Рассмотрим теперь n + 1 автомобиль. Ясно,
что среди них обязательно найдётся автомобиль A, который может доехать до следующего за ним автомобиля B, поскольку иначе бензина во всех автомобилях не хватило бы для того, чтобы проехать один раз по всей кольцевой дороге. Выльем бензин изв и уберём B. Среди оставшихся n автомобилей по предположению индукции найдётся автомобиль, который может проехать по всей кольцевой дороге, забирая по пути бензину остальных автомобилей. Тогда тот же самый автомобиль сможет проехать по всей кольцевой дороге ив исходной ситуации, до переливания бензина изв. Действительно, доехать от A до B он сможет, а на всех остальных участках дороги бензина у него будет ровно столько же,
сколько ив ситуации с n автомобилями

Решения задач. Будем считать, что дробь m/n несократимая. Применим индукцию по m. При m = 1 доказывать нечего. Пусть m > 1. Разделим нас остатком, причём частное запишем в виде d
0
− а остаток запишем в виде m−k, те. где d
0
>
1 и 0 < k < m. Тогда +
k
n
”
. По предположению индукции дробь k/n можно представить в требуемом виде+ . . . +
1
d
1
d
2
. . . Поэтому дробь+ . . . +
1
d
0
d
1
d
2
. . . тоже можно представить в требуемом виде

ГЛАВА КОМБИНАТОРИКА. Элементы комбинаторики. Сколькими способами можно выбрать k предметов из n различных предметов, если порядок, в котором выбираются предметы а) учитывается б) не учитывается. Докажите, что (x + y)
n
=
n
P
k=0
C
k
n
x
k
y
n
−k
, где (n
− Число C
k
n
=
n!
k! (n
− k)!
называют
биномиальным коэффициентом.
Удобно считать, что C
k
n
= 0, если n < 0 или k > n.
14.3. Докажите, что C
k
n
+ C
k
−1
n
= C
k
n+1
14.4. Сколько ожерелий можно составить из пяти белых бусинок и двух чёрных?
14.5. а) Семь девушек водят хоровод. Сколькими различными способами они могут встать вкруг б) Сколько ожерелий можно составить из семи различных бусин. Сколько существует различных путей на плоскости, ведущих из точки с координатами (0, n) в точку с координатами, если двигаться разрешено каждый раз либо на 1 вверх (координата y увеличивается на 1), либо на 1 влево (координата x уменьшается на 1)?
14.7. а) Сколькими способами натуральное число n можно представить в виде суммы m целых неотрицательных чи-

Условия задач
179
сел, если представления n=x
1
+ . . . + и n=y
1
+ . . . + считаются одинаковыми тогда и только тогда, когда x
1
= y
1
, . . .
. . . , x
m
= б) Тот же вопрос для представления в виде суммы натуральных чисел. Докажите, что+ . . . + x
k
)
n
=
X
l
1
+
...+l
k
=
n
n!
l
1
! . . . l
k
!
x
l
1 1
. . . x
l
k
k
14.2. Тождества для биномиальных коэффициентов. Докажите, что:
а) C
0
n
+ C
1
n
+ . . . + C
n
n
= б) C
0
n
+ C
2
n
+ C
4
n
+ C
6
n
+ . . . = C
1
n
+ C
3
n
+ C
5
n
+ . . . = 2
n
−1
14.10. Докажите, что C
k
n+m
= C
0
m
C
k
n
+ C
1
m
C
k
−1
n
+ . . . + C
k
m
C
0
n
(
Вандермонд).
14.11. Докажите, что C
n
2n
= (C
0
n
)
2
+ (C
1
n
)
2
+ . . . + (C
n
n
)
2
14.12. Докажите, что C
n+k
2n
=
P
i
2
n
−k−2i
C
k
n
C
i+k
n
−i
14.13. Докажите, что C
k
−1
n
−1
C
k+1
n
C
k
n+1
= C
k
n
−1
C
k+1
n+1
C
k
−1
n
14.14. Докажите, что если p + q = 1, то q
n
+1
p
− q
14.15. Пусть P(x) — многочлен степени n, причём P(x) =
= для x = 1, 2, . . ., n + 1. Вычислите P(n + 2).
14.16. Докажите, что и n(n + 1)2
n
−2
14.17. Докажите, что 1
m
+ 1
C
m
n
=
2
n
+1
− 1
n
+ и+ 1
C
m
n
=
1
n
+ 1

Глава 14. Комбинаторика. Докажите, что если |x| < 1, то 1 − x

n
= 1 +См. также задачи 29.53, 29.54.
14.3. Бином Ньютона в арифметике. Докажите, что числа (a + 1)
a
n
− 1 и (a − 1)
a
n
+ делятся на и не делятся на a
n+2
14.20. Пусть p
1
= 2, p
2
= 3, . . . — последовательные простые числа. Докажите, что p
1
. . . p
k
6 4
p
k
14.4. Комбинаторика в арифметике. Сколько существует четырёхзначных номеров
(от 0001 до 9999), у которых сумма двух первых цифр равна сумме двух последних цифр. Сколько существует таких пар целых чисел x, y,
заключённых между 1 и 1000, что x
2
+ делится на 7?
14.23. Сколько существует натуральных чисел, меньших тысячи, которые не делятся ни на 5, ни на 7?
14.24. Сколько различных целочисленных решений имеет неравенство |x| + |y| < 100?
14.25. Сколько существует натуральных чисел x, меньших, для которых 2
x
− делится на 7?
14.26. Докажите, что НОД(a
1
, . . . , a
n
)
= P
нечет
/P
чёт
, где
P
нечет
— произведение НОК всех наборов, состоящих из нечётного числа различных чисел a
1
, . . ., a
n
, а P
чёт
— произведение НОК всех наборов, состоящих из чётного числа различных чисел a
1
, . . ., a
n
. (Предполагается, что числа, . . ., попарно различны. Даны 6 цифр 0, 1, 2, 3, 4, 5. Найдите сумму всех четырёхзначных чётных чисел, которые можно написать этими цифрами (одна и та же цифра в числе может повторяться Условия задач. Сколькими различными способами можно представить в виде произведения трёх натуральных чисел Произведения, отличающиеся лишь порядком сомножителей, считаются одинаковыми. Неравенства для биномиальных коэффициентов. Докажите, что 2
n
6
C
n
2n
6 2
2n
14.6. Арифметика биномиальных коэффициентов. Пусть p — простое число и 1 6 k 6 p − 1. Докажите,
что делится на p.
14.31. Пусть p — простое число. Докажите, что для всех натуральных m 6 p − 1 число (−1)
m
C
m
p
−1
− 1 делится на p.
14.32. Докажите, что если p — простое число, то C
n
np
≡
≡ n (mod p
2
).
14.33. Пусть p — нечётное простое число, n = p
a
−2
, где a
>
2. Докажите, что если m > 2, то делится на p
a
−m
14.34. Пусть p — простое число. Докажите, что если делит C
k
n
, то См. также задачи 21.31, 21.32.
14.7. Формула включений и исключений. Дано N предметов и некоторый набор свойств, . . ., P
n
. Пусть N
i
— количество предметов, обладающих свойством P
i
, N
ij
— количество предметов, обладающих свойствами и P
j
, и т. д. Докажите, что количество предметов, не обладающих ни одним изданных свойств, равно+ . . . + формула включений и исключений. Пусть n = p
a
1 1
. . . p
a
k
k
— разложение числа на различные простые множители) количество чисел от 1 до n,

Глава 14. Комбинаторика взаимно простых с n. Докажите, что f
(n)
= n

1 −
1
p
1

1 −
1
p
2

. . .

1 −
1
p
k

14.37. а) Докажите, что количество перестановок a
1
, . . .
. . . , чисел 1, . . ., n, для которых a
i
6= i при всех i, равно − 1 +
1 2!
−
1 3!
+ . . . +
(
−1)
k
k!
+ . . . б) Докажите, что доля таких перестановок среди всех перестановок стремится к 1/e при n → ∞.
14.8. Аналоги биномиальных коэффициентов. Пусть m и n — целые неотрицательные числа. Докажите, что число (2n
+ 2m)!
(2m)! n! (n
+ целое. Числа Каталана
Пусть c
0
= 1, c
1
= c
0
c
0
= 1, c
2
= c
0
c
1
+ c
1
c
0
= 2, c
3
= c
0
c
2
+
+c
1
c
1
+c
2
c
0
=5 и вообще c
k
=c
0
c
k
−1
+c
1
c
k
−2
+. . . +c
k
−1
c
0
. Числа заданные таким рекуррентным соотношением, называют
числа-
ми Каталана.
14.39. Докажите, что количество различных способов разрезать выпуклый угольник на треугольники непересе- кающимися диагоналями равно Эйлер. В строку записана n + 1 буква. Требуется расставить пар круглых скобок так, чтобы внутри каждой пары скобок стояли либо две соседние буквы, либо буква и соседнее выражение в скобках, либо два соседних выражения в скобках. Докажите, что количество различных расстановок скобок равно c
n
(
Каталан).
14.41. В расстановке скобок из задачи 14.40 сотрём все буквы и две крайние скобки (правую и левую. То, что Вот пример такой расстановки скобок ((a((bc)d))(ef)).

Условия задач
183
получится, назовём
правильной скобочной структурой. Докажите, что количество правильных скобочных структур из пар скобок равно c
n
Путём Дика из 2n звеньев называют ломаную на плоскости,
которая соединяет точки с координатами (0, 0) и (0, 2n), имеет векторы звеньев (1, ±1) и целиком лежит в верхней полуплоскости. (Векторы последовательных звеньев могут быть одинаковыми) Один из путей Дика изображён на рис. Риса) Докажите, что число различных путей Дика из звеньев равно б) Докажите, что число различных путей Дика из 2n звеньев равно+ 1
C
n
2n
14.43. а) Докажите, что количество различных последовательностей, для которых a
i
= ±1, a
1
>
0,
a
1
+ a
2
>
0, . . ., a
1
+ a
2
+ . . . + a
2n−1
>
0 и a
1
+ a
2
+ . . . + a
2n
= равно б) Кассиру которого в начальный момент времени денег нет, продаёт билеты по 50 рублей. Очередь состоит из 2n человеку половины из которых есть только одна купюра рублей, ау другой половины — 50 рублей. Докажите,
что количество различных порядков очереди, для которых кассир сможет всем дать сдачу, равно c
n

Глава 14. Комбинаторика. Шахматная ладья движется из левого нижнего угла доски n × n в правый верхний угол. При этом она делает ходы только вправо и вверх. Докажите, что количество различных путей, при которых ладья никогда не попадает на главную диагональ, за исключением исходного и конечного положения, равно Плоским бинарным деревом называют граф на плоскости, у которого нет циклов и из каждой вершины выходят либо три ребра, либо одно ребро. Фиксируем одну вершину, из которой выходит одно ребро, и будем называть её
корнем. Все остальные вершины, из которых выходит ровно одно ребро, будем называть
листьями. Докажите, что количество различных плоских бинарных деревьев с одним корнем и n листьями равно c
n
−1
(
Кэли).