Учебное пособие Москва Издательство мцнмо 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
• страница: 23 из 71

14.46. Вершины правильного (2n + угольника помечены нулями и единицами. Всего есть n + 1 нуль и n единиц.
Будем считать два таких набора пометок одинаковыми,
если они получаются друг из друга поворотом многоуголь- ника.
а) Докажите, что количество различных наборов пометок равно 2n + 1
C
n
2n+1
=
1
n
+ б) Докажите, что количество различных наборов пометок равно c
n
14.47. Пусть 1 − x − y + 2xy
=
∞
P
p,q=0
a
p,q
x
p
y
q
. Докажите, что+ 1
C
n
2n
— число Каталана c
n
14.10. Элементы теории вероятностей. Какая сумма выпавших чисел более вероятна при бросании двух игральных костей 9 или 10?
14.49. Мальчик должен сыграть в теннис три матча со своими родителями. Он будет считаться победителем, если выиграет подряд два матча. Отец играет лучше, чем

Решения задач
185
мать. Какой порядок матчей предпочтительнее для мальчика «отец––мать––отец» или «мать––отец––мать»?
14.50. Силы двух игроков равны, те. они имеют равные шансы на победу в каждой партии. Они договорились, что приз получит тот, кто первым выиграет 6 партий. Им пришлось прервать игру после того, как первый игрок выиграл партий, а второй — 3. В каком отношении справедливо разделить приз. В ящике лежат красные и чёрные носки. Если из ящика наугад вытащить два носка, то вероятность того, что они оба красные, равна а) Какое наименьшее число носков может быть в ящике?
б) Какое наименьшее число носков может быть в ящике,
если известно, что число чёрных носков чётно?
14.52. На каждой грани игральной кости написано одно из чисел от 1 до 6, но некоторые числа могут быть написаны несколько раз. Будем говорить, что кость X выигрывает
у Y, если при одновременном бросании этих костей на X выпадает большее число, чем нас вероятностью больше Могут ли три кости A, B, C обладать следующими свойствами выигрывает у A, C выигрывает у B, A выигрывает у Решения. а) Первый предмет можно выбрать n способами, второй предмет n −1 способами, . . ., й предмет n−k+1 способами. Всего получаем n(n − 1) . . . (n − k + 1) =
n!
(n
− k)!
способов.
б) Каждому набору из k предметов, в котором порядок предметов не учитывается, соответствует k! наборов, в которых порядок предметов учитывается (это соответствует выбору k предметов из различных предметов. Всего получаем k)!
= способов. Коэффициент при в разложении (x + равен количеству способов пометить k множителей в произведении n множителей. Действительно, в каждом отмеченном множителе мы берём x, а в каждом неотмеченном множителе мы берём y.
Остаётся воспользоваться результатом задачи 14.1 б

Глава 14. Комбинаторика. Воспользуемся тождеством (1 + x)
n
(1
+ x) = (1 + Коэффициент при в левой части равен C
k
n
+ C
k
−1
n
, а в правой части равен C
k
n
+1
14.4. Ответ. Чёрные бусинки разбивают белые бусинки на две группы (одна из этих групп может содержать 0 бусинок. Вид ожерелья полностью определяется количеством бусинок в меньшей группе. Это количество может быть равно 0, 1 или 2.
14.5. а) Ответ. Семь девушек на семь разных мест в хороводе можно расставить 7! = 5040 способами. Нов хороводе расположения, которые получаются при движении хоровода, не различаются. Поворотами хоровода из одного расположения можно получить 7 других расположений. Поэтому всего получается = 6! = 720 способов.
б) Ответ. Ожерелье, в отличие от хоровода, можно не только вращать по кругу, но и перевернуть. В результате получаем = 360 различных ожерелий. Ответ. Всего мы должны сделать m шагов вверх и n − m шагов влево. Поэтому из n шагов нужно выбрать m шагов вверх. а) Ответ способами. Сопоставим разложению x
1
+ . . . + последовательность нулей и единиц, в которой сначала идёт единиц, потом один нуль, потом единиц, потом один нуль и т. д в конце идёт единиц. Всего в этой последовательности цифр, среди которых n единиц. Поэтому мы должны выбрать n предметов из n + m − 1 занумерованных
(т. е. различных) предметов.
б)
О т в е т. Каждому разложению n = x
1
+ . . . + где x
1
, . . . , x
m
— натуральные числа, соответствует разложение m = y
1
+ . . . + y
m
, где y
1
= x
1
− 1, . . ., y
m
= x
m
− 1.
14.8. Чтобы в произведении n множителей x
1
+ . . . + получить моном x
l
1 1
. . . x
l
k
k
, нужно сначала выделить множителей из и выбрать в них x
1
, затем нужно выделить из оставшихся n − множителей и выбрать в них x
2
, затем нужно выделить из оставшихся множителей и выбрать в них и т. д. Поэтому коэффициент при мономе x
l
1 1
. . . равен. . . C
l
n
n
−l
1
−...−l
n−1
=
=
n!
l
1
! (n − l
1
)!
·
(n
− l
1
)!
l
2
! (n − l
1
− l
2
)!
· . . . ·
(n
− l
1
− . . . − l
n
−1
)!
l
n
! (n − l
1
− . . . − Заметив, что n − l
1
− . . . − l
n
= 0, получаем требуемое

Решения задача+ б) 0 = (1 − 1)
n
= C
0
n
− C
1
n
+ C
2
n
− C
3
n
+ . . .
14.10. Сравните коэффициенты при в обеих частях равенства+ 1)
m
+n
= (x + 1)
m
(x
+ 1)
n
14.11. Примените тождество из задачи 14.10 при n = m = и воспользуйтесь тем, что C
i
n
= C
n
−i
n
14.12. Коэффициент при в разложении (1 + равен C
n
+k
2n
. С другой стороны,
(1
+x)
2n
=(x
2
+(1+2x))
n
=
X
i
C
i
n
x
2i
(1
+2x)
n
−i
=
X
i
C
i
n
x
2i
X
j
C
j
n
−i
2
j
x
j
В последнем выражении коэффициент при равен. Требуется доказать, что 1)!
(k
− 1)! (n − k)!
·
n!
(k + 1)! (n
− k − 1)!
·
(n + 1)!
k! (n
− k + 1)!
=
=
(n
− 1)!
k! (n
− k − 1)!
·
(n + 1)!
(k + 1)! (n
− k)!
·
n!
(k
− 1)! (n − k + Это равенство очевидно. Пусть S
n
=
P
06r6n/2
(
−1)
r
C
r
n
−r
p
r
q
r
. В действительности суммирование можно вести по всем r, так как если r > n/2, то n −r а потому C
r
n
−r
= 0. Поэтому
S
n
+1
−S
n
=
X
(
−1)
r
(C
r
n
+1−r
−C
r
n
−r
)p
r
q
r
=
X
(
−1)
r
C
r
−1
n
−r
p
r
q
r
=−pqS
n
−1
Ясно также, что S
0
= S
1
= 1. С другой стороны q
p
− q
= 1 и q
2
p
− q
=
= p + q = 1. Поэтому при n = 0 и при n = 1 требуемое утверждение верно. Если равенство S
k
=
p
k
+1
− q
k
+1
p
− доказано для всех k 6 n, то S
n
−pqS
n
−1
=
p
n
+1
− q
n
+1
− pq(p
n
− q
n
)
p
− q
=
p
n
+1
(1
− q)− q
n
+1
(1
− p)
p
− q
=
=
p
n
+2
− q
n
+2
p
− q

Глава 14. Комбинаторика. Ответ Выражение C
x
−1
m
=
(x
− 1)(x − 2) . . . (x − можно рассматривать как многочлен степени n от переменной x. Пусть 2(C
0
x
−1
+ C
1
x
−1
+ . . . + Ясно, что C
0
x
−1
+ C
1
x
−1
+ . . . + C
n
x
−1
= (1 + 1)
x
−1
= при x = 1, 2, . . .
. . . , n
+ 1. Поэтому P(x) = f(x), поскольку эти многочлены степени совпадают при n + 1 различных значениях x. Следовательно+ 2) = 2(C
0
n
+1
+ C
1
n
+1
+ . . . + C
n
n
+1
)
=
= 2(C
0
n
+1
+ C
1
n
+1
+ . . . + C
n
n
+1
+ C
n
+1
n
+1
− C
n
+1
n
+1
)
=
= 2(2
n
+1
− 1) = 2
n
+2
− 2.
14.16. Продифференцируем тождество (1 + и домножим полученное равенство на x. В результате получим+ x)
n
−1
=
n
P
m
=1
mx
m
C
m
n
; при x = 1 получаем первое из требуемых тождеств. Ещё раз повторив дифференцирование пои домноже- ние на x, получим+ 1)(1 + при x = 1 получаем второе из требуемых равенств. Запишем тождество (1 + и проинтегрируем его+ те+ При x = 1 получаем первое требуемое тождество, а при x = −1 второе. Применим индукцию по n. При n = 1 получаем обычную формулу для суммы бесконечной геометрической прогрессии

Решения задач
189
Чтобы перейти от n к n + 1, нужно доказать тождество +
∞
X
k
=1
C
n
n
+k
x
k
«
(1
− x) = 1 +Коэффициенты при в левой и правой частях равны и соответственно. Эти числа равны. Мы приведём доказательство лишь для первого числа
(для второго числа рассуждения аналогичны. При n = 0 утверждение очевидно. При n = 1 получаем (1+ a)
a
−1≡a·a+C
2
a
a
2
(mod Число a
2
+ C
2
a
a
2
= a
2
“
a
2
+
a + 1 делится на и не делится на Предположим теперь, что (a + 1)
a
n
− 1 делится на и не делится на для некоторого n > 1. Тогда+ 1)
a
n+1
− 1 = ((a + 1)
a
n
− 1)
n
= (1 + ba
n
+1
)
a
− 1 =
= a · ba
n
+1
+ C
2
a
b
2
a
2n+2
+ C
3
a
b
3
a
3n+3
+ . . здесь b — целое число, которое не делится на a). Если n > 1, то, поэтому (a+1)
a
n+1
−1≡ba
n
+2
(mod a
n
+3
); число делится на и не делится на a
n
+3
14.20. Докажем индукцией по n, что если p
k
6
n, где n > 2, то. . . p
k
6 4
n
. При n = 2 требуемое утверждение очевидно. Предположим, что оно доказано для всех чисел, не превосходящих n − Чтобы сделать шаг индукции, разберём отдельно два случая.
Пусть n = 2m. Согласно предположению индукции произведение всех простых чисел, не превосходящих m, не превосходит Кроме того, все простые числа p
i
, для которых m + 1 6 p
i
6 делят число C
m
2m
=
(2m)!
m! m!
, а это число не превосходит 2 2m
= В результате получаем, что произведение простых чисел, не превосходящих, не превосходит 4
m
· 4
m
= 4 2m
= Пусть n = 2m + 1. Согласно предположению индукции произведение всех простых чисел, не превосходящих m + 1, не превосходит. Кроме того, все простые числа p
i
, для которых+ 2 6 p
i
6 2m + 1, делят число C
m
2m+1
=
(2m + 1)!
m! (m + 1)!
. Ясно также,
что C
m
2m+1
= C
m
+1 и C
m
2m+1
+ C
m
+1 2m+1 6
2 2m+1
, поэтому C
m
2m+1 6
2 В результате получаем, что произведение простых чисел, не превосходящих, не превосходит 4
m
+1
· 2 2m
= 4 2m+1
= 4
n
14.21. Ответ. Пусть сумма первых двух цифр равна и сумма двух последних цифр тоже равна n. Число n принимает значение от 1 до 18. Если количество двузначных номеров

Глава 14. Комбинаторика у которых сумма цифр равна n, равно a
n
, то искомое число равно 1
+ a
2 2
+ . . . + a
2 18
. Двузначный номеру которого сумма цифр равна, состоит из цифр a и n − a, где 0 6 a 6 9 и 0 6 n − a 6 9. Таким образом, 0 6 a 6 9 и n −96 a6 n. Если n6 9, то остаётся неравенство 6 a 6 n, а если n > 9, то остаётся неравенство n − 9 6 a 6 9. В итоге получаем a
1
= 2, a
2
= 3, . . . , a
8
= 9, a
9
= 10, a
10
= 9, . . . , a
17
= 2, a
18
= 1.
14.22. Ответ. Число x
2
+ делится на 7 тогда и только тогда, когда оба числа x и y делятся на 7. Действительно,
квадрат целого числа при делении на 7 даёт остатки 0, 1, 2 и 4. Количество целых чисел, заключённых между 1 и 1000 и делящихся на 7, равно 142. Поэтому искомое число равно 142 2
= 20164.
14.23. Ответ чисел. Сначала вычеркнем из набора чисел, 2, . . . , 999 числа, кратные 5; их количество равно h
999 5
i
= Затем из того же набора чисел 1, 2, . . . , 999 вычеркнем числа,
кратные 7; их количество равно h
999 7
i
= 142. При этом числа,
кратные 35, будут вычеркнуты дважды. Их количество равно h
999 35
i
= 28. Значит, всего мы вычеркнули 199 + 142 − 28 = чисел, а осталось 999 − 313 = 686 чисел. Ответ. Уравнения |x| + |y| = 0, |x| + |y| = 1,
|x| + |y| = 2, . . ., |x| + |y| = 99 имеют, соответственно, 1, 2 2
, 3 2
, . . .
. . . , 100 целочисленных решений. Поэтому искомое число равно 2
+ 2 2
+ 3 2
+ . . . + 100 2
=
100 · 101 · 201 см. задачу 9.12).
14.25. Ответ. Остатки отделения на 7 чисел и повторяются с периодами 3 и 7, поэтому остатки отделения на числа 2
x
− повторяются с периодом 21. Среди чисел x от до 21 равные остатки отделения на 7 чисел и дают ровно чисел. Поэтому среди чисел от 1 доесть требуемых чисел. Непосредственная проверка с использованием полученной последовательности остатков показывает, что из оставшихся чисел 9997, 9998 и 9999 только число обладает требуемым свойством. Эта задача — обобщение задачи 4.19, при решении которой показано, что достаточно рассмотреть случай, когда a
1
=p
a
1
, . . .
. . . , a
n
= и a
1 6
a
2 6
. . . Множитель входит только в нечет, причём ровно один раз
(когда мы берём набор, состоящий из одного числа a
1
). Покажем,
что все остальные множители, входящие в нечет ив P
чёт
, взаимно сокращаются. НОК набора чисел равно p
a
k+1
, если одно из этих чисел равно a
k
+1
, а все остальные числа выбраны из a
1
, . . . , a
k
. По

Решения задач
191
этому в нечет множитель входит C
0
k
+ C
2
k
+ C
4
k
+ . . . разв нечет этот множитель входит C
1
k
+C
3
k
+C
5
k
+. . . раз. Согласно задаче 14.9 б)
каждая из этих сумм равна 2
k
−1
14.27. Ответ. Будем отдельно подсчитывать сумму тысяч, сотен, десятков и единиц для рассматриваемых чисел. На первом месте может стоять любая из пяти цифр 1, 2, 3, 4, Количество всех чисел с фиксированной первой цифрой равно · 6 · 3 = 108, поскольку на втором и третьем месте может стоять любая из шести цифра на четвёртом месте может стоять любая из трёх цифр 0, 2, 4 (мы рассматриваем только чётные числа. Поэтому сумма тысяч равна (1 + 2 + 3 + 4 + 5) · 108 · 1000 = 1 620 000. Количество чисел с фиксированной второй цифрой равно 5 · 6 · 3 = на первом месте стоит любая из пяти цифр. Поэтому сумма сотен равна (1 + 2 + 3 + 4 + 5) · 90 · 100 = 135 000. Аналогично сумма десятков равна (1 + 2 + 3 + 4 + 5) · 90 · 10 = 13 500, а сумма единиц равна (2 + 4) · 5 · 6 · 6 = 1 080.