Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
Скачать 3.28 Mb.
|
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. |