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

14.48. Ответ. Числа 9 и 10 можно получить двумя разными способами 9=3+6=4+5 и 10=4+6=5+5. Нонам необходимо учитывать порядок, в котором выпадают числа на костях. Поэтому число 9 получается четырьмя разными способами, а число лишь тремя 9 = 3 + 6 = 6 + 3 = 4 + 5 = 5 + 4, 10 = 4 + 6 = 6 + 4 = 5 + 5.
14.49. Ответ «отец––мать––отец». (Такой ответ представляется на первый взгляд странным, потому что приходится дважды играть с сильным игроком. Но при другом порядке матчей нужно обязательно выиграть единственный матч с сильным игроком, а не один из двух матчей.)
Пусть вероятность выиграть матчу отца равна p, ау матери. По условию p < q. Победу мальчику приносят следующие исходы турнира ВВП, ВВВ, ПВВ (здесь В означает выигрыша П — проигрыш. Для турнира «отец––мать––отец» вероятности таких исходов равны pq(1 −p), pqp, (1−p)qp. Поэтому вероятность выигрыша в таком турнире равна 2pq − pqp. Аналогично вероятность выигрыша в турнире «мать––отец––мать» равна 2pq − Ясно, что pqp < qpq, поэтому 2pq − pqp > 2pq − qpq.
14.50. Ответ. Пусть игроки сыграют ещё три партии,
т. е. игра фиктивно продолжается даже после того, как первый игрок получил приз. Второй игрок получит приз тогда и только тогда, когда он выиграет все три партии. Поскольку все 2 3
= исходов этих трёх партий равновероятны, второй игрок получит приз с вероятностью 1/8. Соответственно, первый игрок получит приз с вероятностью 7/8.
14.51. а) Ответ. Пусть в ящике лежит m красных носков и n чёрных. Вероятность того, что первый выбранный носок красный, равна + m
. При условии, что первый выбранный носок красный, вероятность того, что второй выбранный носок тоже красный, равна 1
n + m
− 1
. Поэтому вероятность того, что оба носка красные, равна + m
·
m
− 1
n + m
− 1
. Таким образом, требуется, чтобы выполнялось равенство + m
·
m
− 1
n + m
− 1
=
1 При n = 1 получаем m = 3. Такой набор носков нам подходит

Глава 14. Комбинаторика б) Ответ. Ясно, что n > 0. Тогда, как легко проверить + m
>
m
− 1
n + m
− 1
. Поэтому должны выполняться неравенства + m
”
2
>
1 2
>
“
m
− 1
n + m
− те. По условию число n чётно.
Для n = 2, 4, 6 получаем m = 5, 10, 15. В первых двух случаях равенство (1) не выполняется, а в третьем выполняется. При этом+ m = 6 + 15 = Замечание. Положим x = m − n и y = n. Тогда равенство (1)
перепишется в виде (2x − 1)
2
− 2(2y)
2
= 1. Поэтому в общем случае мы имеем дело с уравнением Пелля.
14.52. Ответ да, могут. Пусть, например, на гранях костей написаны следующие числа:
на кости A
1, 4, 4, 4, 4, на кости B
2, 2, 2, 5, 5, на кости C
3, 3, 3, 3, 3, 6.
B выигрывает у A, если на B выпадает 5 или на B выпадает а на A выпадает 1. Вероятность этого равна 1/2 + 1/2 · 1/6 = 7/12 >
>
1/2.
C выигрывает у B, если на C выпадает 6 или на C выпадает а на B выпадает 2. Вероятность этого равна 1/6 + 5/6 · 1/2 = 7/12 >
>
1/2.
A выигрывает у C, если на A выпадает 4, а на C выпадает Вероятность этого равна 5/6 · 5/6 = 25/36 > 1/2.

ГЛАВА РЕКУРРЕНТНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ
Рекуррентной последовательностью порядка k называют последовательность чисел u
1
, u
2
, . . . , где числа u
1
, u
2
, . . . , произвольные, а при всех n > 1 выполняется соотношение a
1
u
n
+k−1
+ . . . + a
k
u
n
, где a
1
, a
2
, . . . , a
k
— некоторые фиксированные числа. Общие свойства. Пусть a
1
, a
2
, . . . , a
k
— фиксированные числа и u
n+k
=
= a
1
u
n+k
−1
+ . . . + a
k
u
n
. Докажите, что+ u
2
x
+ u
3
x
2
+ u
4
x
3
+ . . . =
P
k
−1
(x)
1 − a
1
x
− a
2
x
2
− . . . − где P
k
−1
(x) — многочлен степени не выше k
− 1.
15.2. Пусть a
1
, a
2
, . . . , a
k
— фиксированные числа и u
n+k
=
= a
1
u
n+k
−1
+ . . . + a
k
u
n
. Предположим, что x
1
, . . ., x
k
— попарно различные корни уравнения x
k
= a
1
x
k
−1
+ a
2
x
k
−2
+ . . . + Докажите, что тогда u
n
= c
1
x
n
−1 1
+ . . . + для некоторых фиксированных чисел c
1
, . . . , c
k
15.2. Числа Фибоначчи
Числами Фибоначчи называют последовательность чисел F
1
= 1,
F
2
= 1, F
n
= F
n
−1
+ при n > 3. Начало этой последовательности имеет вид 1, 1, 2, 3, 5, 8, 13, 21, . . .
15.3. Докажите, что F
n+k
= F
n
−1
F
k
+ F
n
F
k+1
15.4. а) Докажите, что числа и взаимно просты.
б) Докажите, что НОД(F
m
, F
n
)
= F
d
, где d = НОД(m, n).
15.5. Докажите, что если m>2, то делится на тогда и только тогда, когда n делится на m.

Глава 15. Рекуррентные последовательности. Докажите, что +
√
5 2

n
−

1 −
√
5 2

n

(
Бине).
15.7. Докажите, что для любого натурального n число+ 5 C
3
n
+ 25 C
5
n
+ 125 C
7
n
+ . . делится на 2
n
−1
15.8. а) Пусть f
1
(x)
=1, f
2
(x)
=x и при n > 3. Докажите, чтоб) Докажите, что 1 + C
1
n
−1
+ C
2
n
−2
+ C
3
n
−3
+ . . .
15.9. Докажите, что 1 − x − x
2
= F
1
+ F
2
x
+ F
3
x
2
+ F
4
x
3
+ . . .
15.10. Докажите, что для любого натурального числа n
найдётся число Фибоначчи, делящееся на n.
15.11. Докажите, что сумма восьми последовательных чисел Фибоначчи не может быть равна числу Фибоначчи. Докажите, что если a
2
−ab−b
2
= ±1, где a и b — натуральные числа, то a = и b = для некоторого n.
15.13. Найдите все решения в натуральных числах уравнения, где C
m
n
=
n!
m! (n
− m)!
— биномиальный коэффициента) Докажите, чтоб) Докажите, что F
2 2n+1
+ F
2 2n−1
+ 1 = 3F
2n+1
F
2n−1
15.15. При каких натуральных a и b число a
2
+ b
2
+ делится на ab?
15.16. Найдите все пары натуральных чисел a и b, для которых a
2
+ 1 делится на b, а b
2
+ 1 делится на a.

Условия задач. Докажите, что любое натуральное число n единственным образом можно представить в виде n=F
k
1
+F
k
2
+. . .
. . .
+ F
k
m
, где k
1
>
k
2
+ 1, k
2
>
k
3
+ 1, . . . , k
m
−1
>
k
m
+ 1, k
m
>
1.
15.18. Докажите, что число Фибоначчи с нечётным номером не может делиться на простое число вида 4k + 3.
15.3. Числа Фибоначчи и алгоритм Евклида. Пусть a и b — натуральные числа, причём a > и НОД(a, b) = d. Докажите, что если алгоритм Евклида,
применённый к a и b, останавливается после n шагов, то > и b > dF
n+1
15.20. а) Докажите, что при n > б) Докажите, что если F
n+1
<
10
k
, то n 6 5k.
15.21. Докажите, что количество шагов алгоритма Евклида, применённого к паре натуральных чисел a > b, не превосходит количества цифр десятичной записи числа умноженного на 5.
15.4. Числа Фибоначчи в комбинаторике. Чему равно количество подмножеств множества, 2, 3, . . . , n}, не содержащих двух последовательных чисел. Сколькими способами можно представить число в виде суммы нескольких слагаемых, равных 1 или Представления, различающиеся порядком слагаемых, считаются различными. Сколькими способами можно представить число в виде суммы нескольких целых слагаемых a
i
>
2? (Представления, различающиеся порядком слагаемых, считаются различными. Сколькими способами можно представить число в виде суммы положительных нечётных слагаемых (Представления, различающиеся порядком слагаемых, считаются различными

Глава 15. Рекуррентные последовательности. Специальные рекуррентные
последовательности
15.26. Пусть a
1
= 1, a
2
= 0, a
3
= 1 и+ n + 1)(n + 1)
n
a
n+2
+ (n
2
+ n + 1)a
n+1
−
n
+ при n > 1. Докажите, что a
n
— квадрат целого числа для любого n > 1.
15.27. Пусть u
1
= 1, u
2
= 0, u
3
= 1 и u
n
= u
n
−2
+ при > 4. Докажите, что u
2n
− и u
2n+1
− делятся на Решения. В произведении+ u
2
x
+ u
3
x
2
+ u
4
x
3
+ . . .)(1 − a
1
x
− a
2
x
2
− . . . − коэффициент при x
n
+k−1
, n> 1, равен u
n
+k
−a
1
u
n
+k−1
−. . .−a
k
u
n
= Значит, это произведение представляет собой многочлен степени не выше k − 1.
15.2. Согласно задаче 10.35 можно выбрать числа c
1
, . . . , c
k
так,
что
u
1
= c
1
+ . . . + c
k
,
u
2
= c
1
x
1
+ . . . + c
k
x
k
,
u
k
= c
1
x
k
−1 1
+ . . . + Тогда+ . . . + c
k
x
k
k
= c
1
(a
1
x
k
−1 1
+ . . . + a
k
)
+ . . . + c
k
(a
1
x
k
−1
k
+ . . . + a
k
)
=
= a
1
u
k
+ . . . + a
k
u
1
= Аналогично c
1
x
k
+1 1
+ . . . + c
k
x
k
+1
k
= и т. д. Применим индукцию по k. При k = 1 получаем F
n
+1
=
= F
n
−1
+ F
n
, а при k = 2 получаем F
n
+2
= F
n
−1
+ 2F
n
= F
n
−1
+ F
n
+ F
n
=
= F
n
+1
+ F
n
. База индукции доказана. Предположим теперь, что F
n
−1
F
k
−2
+ и F
n
+k−1
= F
n
−1
F
k
−1
+ F
n
F
k
. Тогда F
n
+k
=
= F
n
−1
(F
k
−2
+ F
k
−1
)
+ F
n
(F
k
−1
+ F
k
)
= F
n
−1
F
k
+ F
n
F
k
+1
15.4. а) Предположим, что числа и делятся на целое число d > 1. Тогда F
n
−1
= F
n
+1
− тоже делится на d и т. д. В итоге получим, что F
2
= 1 делится на d.

Решения задач
205
б) Воспользуемся формулой задача Положим m = n + k. При m > k получаем
НОД(F
m
, F
k
)
= НОД(F
m
−k−1
F
k
+ F
m
−k
F
k
+1
, F
k
)
=
= НОД(F
m
−k
F
k
+1
, F
k
)
= НОД(F
m
−k
, поскольку числа и взаимно простые. Теперь можно воспользоваться результатом задачи 4.11.
15.5. Число делится на тогда и только тогда, когда НОД(F
n
, F
m
)
= F
m
. С другой стороны, согласно задаче 15.4
НОД(F
n
, F
m
)
= F
НОД(n,m)
. Таким образом, получаем следующее условие НОД(n, m) = m здесь мы пользуемся тем, что m > Полученное равенство, в свою очередь, эквивалентно тому, что делится на m.
15.6. Согласно задаче 15.2 F
n
= c
1
x
n
1
+ c
2
x
n
2
, где и x
2
— корни уравнения x
2
= x + 1, аи некоторые константы. Решая квадратное уравнение, получаем x
1,2
=
1 ±
√
5 2
. Константы и мы находим, воспользовавшись тем, что F
1
= 1 и F
2
= 1.
15.7. Формула Бине (задача 15.6) показывает, что C
1
n
+ 5 C
3
n
+ 25 C
5
n
+ 125 C
7
n
+ . . .
15.8. а) Многочлены f
1
(x) и f
2
(x) имеют указанный вид. Поэтому достаточно проверить, что многочлены указанного вида удовлетворяют указанному рекуррентному соотношению. Но если посмотреть на коэффициенты при степенях x по отдельности, то это рекуррентное соотношение сводится к основному тождеству для биномиальных коэффициентов C
k
n
−k
= C
k
n
−k−1
+ б) Непосредственно следует из а, поскольку F
n
= f
n
(1).
15.9. Ясно, что (1 − x − x
2
)(F
1
+ F
2
x
+ F
3
x
2
+ F
4
x
3
+ . . .) = F
1
+
+ (F
2
−F
1
)x
+ (F
3
−F
2
−F
1
)x
2
+ (F
4
−F
3
−F
2
)x
3
+ . . . При этом F
1
= 1,
F
2
− F
1
= 0, F
3
− F
2
− F
1
= 0, F
4
− F
3
− F
2
= 0, . . .
15.10. Рассмотрим пары остатков отделения на n соседних чисел Фибоначчи и для k = 1, 2, . . . , n
2
+ 1. Количество различных пар остатков равно n
2
, поэтому среди рассматриваемых пар остатков найдутся две одинаковые пары, те. числа F
k
− и F
k
+1
− делятся на n для некоторых чисел 1 6 k < l 6 n
2
+ Тогда число F
k
−1
− F
l
−1
= F
k
+1
− F
l
+1
− (F
k
− F
l
) тоже делится на n и т. д. В конце концов получаем, что числа F
2
− и делятся на n. Поэтому F
l
−k
= F
l
−k+2
−F
l
−k+1
≡F
2
−F
1
≡
≡ 0 (mod n).
15.11. Пусть S = F
k
+1
+ F
k
+2
+ . . . + F
k
+8
— сумма восьми последовательных чисел Фибоначчи. Достаточно доказать, что

Глава 15. Рекуррентные последовательности < F
k
+10
. Первое неравенство очевидно S > F
k
+7
+ F
k
+8
=
= F
k
+9
. Докажем теперь второе неравенство. Ясно, что F
k
+8
+ F
k
+9
=
= F
k
+8
+ F
k
+7
+ F
k
+8
=
= F
k
+6
+ F
k
+7
+ F
k
+7
+ F
k
+8
=
= F
k
+5
+ F
k
+6
+ F
k
+6
+ F
k
+7
+ F
k
+8
=
= F
k
+1
+ 2F
k
+2
+ F
k
+3
+ . . . + Последнее выражение, очевидно, больше S.