Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
15.12. Равенство a 2 = b 2 + ab ± 1 показывает, что a > b, причём a = b лишь в том случае, когда оба эти числа равны 1. Поэтому будем считать, что a > b. Для пары b, a − b тоже выполняется требуемое равенство, поскольку b 2 − (a − b)b − (a − b) 2 = −(a 2 − ab − Поэтому после нескольких таких замен мы дойдём до пары (1, Обратное преобразование имеет вид (x, y) 7→ (x + y, x), поэтому из пары (1, 1) мы будем последовательно получать пары (F n +1 , для n = 2, 3, . . . 15.13. Рассматриваемое уравнение эквивалентно уравнению. Пусть d=НОД(m, n), n=da и m=db. После сокращения на d получаем уравнение abd = (a − b)((a − b)d + Число d взаимно просто с (a − b)d + 1, а число ab взаимно просто с a − b, поэтому ab = (a − b)d + 1 и d = a − b. Подставим в первое уравнение выражение a = b + d и заменим a − b на d. В результате получим b 2 + bd = d 2 + 1, те. В задаче 15.12 приведено решение уравнения чуть более общего вида, когда в правой части стоит ±1. Отбросив те решения, которые соответствуют получим d = F 2k , b = и a = b + d = F 2k+1 . Таким образом и m = Замечание. Равенство C m −1 n = эквивалентно равенству+ C m −2 n −1 = C m n −1 15.14. а) Применим индукцию по n. При n = 1 равенство очевидно. Предположим, что доказано равенство F 2n+1 F 2n−1 = F 2 2n + для некоторого n. Тогда 2n+2 + 1 = (F 2n+1 + F 2n ) 2 + 1 = F 2 2n+1 + 2F 2n+1 F 2n + F 2 2n + 1 = = F 2 2n+1 + 2F 2n+1 F 2n + F 2n+1 F 2n−1 = F 2n+1 (F 2n+1 + 2F 2n + F 2n−1 ). Остаётся заметить, что F 2n+1 + 2F 2n + F 2n−1 = F 2n+2 + F 2n+1 = F 2n+3 Решения задач 207 б) Воспользовавшись задачей а, получаем 2n+1 + F 2 2n−1 − 2F 2n+1 F 2n−1 = (F 2n+1 − F 2n−1 ) 2 = F 2 2n = F 2n+1 F 2n−1 − а значит, F 2 2n+1 + F 2 2n−1 + 1 = 3F 2n+1 F 2n−1 15.15. Можно считать, что a > b. Согласно задаче 15.14 б) пара чисел (a, b) = (F 2n+1 , F 2n−1 ), n > 1, обладает требуемым свойством пара чисел (a, b) = (1, 1) тоже. Покажем, что никакие другие пары натуральных чисел (a, b), где a > b, этим свойством не обладают. Применим индукцию по a. Прежде всего отметим, что если a = b, то число 2a 2 + 1 делится на a 2 , поэтому 1. Предположим, что a 2 + b 2 + 1 = kab, где k — натуральное число и a > 1. Положим a 1 = b и b 1 = kb − a = b 2 + 1 a . Тогда 1 + b 2 1 + 1 = b 2 + k 2 b 2 − 2kab + a 2 + 1 = k 2 b 2 − kab = kb(kb − a) = поэтому числа (a 1 , b 1 ) обладают требуемым свойством. Проверим, что 16 b 1 6 a 1 < a. Действительно, b 1 = b 2 + 1 a < b 2 + 1 b < b +1. Число целое, поэтому b 1 6 b = a 1 . Кроме того, a 1 = b < a по условию. Значит, по предположению индукции b = a 1 = и kb −a=b 1 = для некоторого n > 0 (мы считаем, что F −1 = 1). Нов таком случае из равенства a 2 + b 2 + 1 = kab следует, что k = 3, поэтому kb − b 1 = 3F 2n+1 − F 2n−1 = 2F 2n+1 + F 2n+1 − F 2n−1 = F 2n+1 + F 2n+1 + + F 2n = F 2n+1 + F 2n+2 = F 2n+3 15.16. Формула F 2 2n+1 +F 2 из задачи 15.14 б) показывает, что пара (F 2n−1 , F 2n+1 ) обладает требуемым свойством. Покажем, что никакая другая пара натуральных чисел, b), где a 6 b, этим свойством не обладает. Применим индукцию по b. Прежде всего заметим, что если a = b, то a 2 + 1 делится на поэтому a = b = 1. Пусть b > 1, a 6 b, a 2 + 1 = l b и b 2 + 1 где и m — целые числа. Тогда (a 2 + 1) 2 = l 2 b 2 = l 2 ( m a − поэтому 1 ≡ − l 2 (mod a), те делится на a. Кроме того > a(a + 1) > a 2 + 1, поэтому l 6 a < b. Воспользовавшись предположением индукции, получим l = и a = F 2n−1 . Значит 2n+1 + 1 F 2n−1 = 3F 2n+1 F 2n−1 − F 2 2n−1 F 2n−1 = 3F 2n+1 − F 2n−1 = F 2n+1 15.17. В качестве выберем наибольшее число Фибоначчи, не превосходящее n, те. Тогда 06 n−F k 1 < F k 1 +1 −F k 1 = = F k 1 −1 . Поэтому если в качестве мы выберем наибольшее число Фибоначчи, не превосходящее n−F k 1 , тот. е. k 2 +1< < k 1 . Затем выбираем наибольшее число Фибоначчи, не превосходящее, и т. д Глава 15. Рекуррентные последовательности Единственность представления следует из того, что F k 1 6 n < < F k 1 +1 . Действительно, F k 1 + F k 2 + . . . + F k m 6 F k 1 + F k 1 −2 + F k 2 −4 + . . последнее слагаемое в этой сумме равно при нечётном и прич тном k 1 . Заменим на F 4 − 1, а F 2 — на F 3 − 1. После этой замены сумма легко сворачивается и получается F k 1 +1 − 1. 15.18. Положим в задаче 15.3 k = n − 1. В результате получим. Поэтому если делится на простое число p вида 4k + 3, то оба числа и делятся на p задача. В таком случае число F n −2 = F n − тоже делится на p и т. д. Приходим к противоречию, поскольку F 1 = 1 не делится на p. 15.19. Применим индукцию по n. Если n = 1, то b = d = и a > 2d = dF 3 . Предположим, что требуемое утверждение доказано для некоторого n > 1. Рассмотрим числа a > b, для которых алгоритм Евклида останавливается после n + 1 шагов. На первом шаге пара (a, b) заменяется на пару (b, c), где c = a −qb6 a−b. Для пары (b, c) алгоритм Евклида останавливается после n шагов, прич м НОД(b, c) = НОД(a, b) = d. Поэтому согласно предположению индукции b > и c > dF n +1 . Следовательно, a > b + c > d× ×(F n +2 + F n +1 ) = dF n +3 15.20. а) При n = 2 и 3 требуемое неравенство легко проверяется, поэтому будем считать, что n>3. Воспользуемся тождеством из задачи 15.3: F n +5 = F (n −2)+7 = F n −3 F 7 + F n −2 F 8 = 13F n −3 + 21F n −2 > > 10F n −3 + 20F n −2 = б) Применим индукцию по k. При k = 1 достаточно заметить, что F 7 = 13 > 10. Предположим, что для данного k > 1 мы уже доказали, что из неравенства следует неравенство n6 Пусть F m +1 < 10 k +1 . Тогда согласно задаче а) поэтому F (m −5)+1 < 10 k . Следовательно, согласно предположению индукции m − 5 6 5k, те, что и требовалось. Пусть алгоритм Евклида, применённый к паре (a, останавливается после n шагов. Тогда согласно задаче 15.19 b Если количество цифр в десятичной записи числа b равно k, то < 10 k , поэтому F n +1 < 10 k . Остаётся воспользоваться результатом задачи 15.20. 15.22. Ответ. Пусть искомое число равно x n . При 1 есть подмножества ∅ и {1}, поэтому x 1 = 2. При n = 2 есть подмножества ∅, {1} и {2}, поэтому x 2 = 3. Легко проверить, что x n −1 + при n > 3. Действительно, если рассматриваемое подмножество содержит n, то оно не содержит n − 1, и никаких других ограничений на него не накладывается. Количество таких Решения задач 209 подмножеств равно x n −2 . Ясно также, что количество рассматриваемых подмножеств, не содержащих n, равно x n −1 15.23. Ответ. Пусть искомое число равно x n . Ясно, что 1 и x 2 = 2. Докажем, что x n = x n −1 + при n > 3. Действительно, количество представлений числа n с первым слагаемым равно x n −1 , ас первым слагаемым 2 — x n −2 15.24. Ответ. Пусть искомое число равно x n . Ясно, что 0, x 2 = 1 и x 3 = 1. Докажем, что x n = x n −1 + при n > Первое слагаемое может быть равно 2; количество таких представлений равно x n −2 . Первое слагаемое может быть больше 2. Тогда из него можно вычесть 1 и получить представление числа n − Поэтому количество таких представлений равно x n −1 15.25. Ответ. Пусть искомое число равно x n . Ясно, что 1 и x 2 = 1. Докажем, что x n = x n −1 + при n > 3. Действительно, количество представлений с первым слагаемым 1 равно. Если же первое слагаемое не меньше 3, то из него можно вычесть 2 и получить представление числа n − 2. 15.26. Рассмотрим последовательность b n , для которой b 1 = 1, b 2 = 0 и b n +2 = nb n +1 + при n > 1. Возведём в квадрат равенства b n +2 − и b n +3 = (n + 1)b n +2 + b n +1 . Затем, чтобы уничтожить член b n +2 b n +1 , умножим первое из полученных равенств на+ 1, второе на n и сложим их. В результате получим + 1)(n + 1) n b 2 n +2 + (n 2 + n + 1)b 2 n +1 − n + Кроме того, b 3 = 1. Значит, a n = b 2 n 15.27. Проверим, что при 0 < k < m − 2 имеет место равенство u k +1 u m −k + u k +2 u m −k−1 + При k = 1 это равенство очевидно. Поэтому достаточно доказать, что u k +1 u m −k + u k +2 u m −k−1 + u k u m −k−2 = u k +2 u m −k−1 + u k +3 u m −k−2 + + u k +1 u m −k−3 . Сократим члены в обеих частях этого равенства и воспользуемся тем, что u k +1 u m −k = u k +1 u m −k−2 + + u k +1 u m −k−3 . После сокращения членов u k +1 u m −k−3 , приходим к очевидному равенству (u k +1 + u k )u m −k−2 = Положив в равенстве (1) m = 2n и k = n − 1, получим u 2n − u 2 n −1 = = 2u n u n +1 . Положив в равенстве (1) m = 2n + 1 и k = n − 1, получим u 2 n +1 = u n (u n −1 + u n +2 ). ГЛАВА ПРИМЕРЫ И КОНСТРУКЦИИ. Наборы чисел. Можно ли выбрать 10 натуральных чисел так, чтобы ни одно из них не делилось ни на какое другое, но квадрат любого числа делился бы на каждое из чисел. а) Докажите, что существует бесконечно много пар натуральных чисел k, l > 2, для которых k! l! = n! для некоторого натурального б) Докажите, что для каждого натурального числа существует бесконечно много наборов натуральных чисел, . . ., a m > 2, для которых a 1 ! a 2 ! . . . a m ! = n! для некоторого. Докажите, что для любого натурального n существуют различных натуральных чисел, сумма любых двух из которых делится на их разность. а) Конечно или бесконечно множество пар натуральных чисел a, b, обладающих следующим свойством: простые делители чисел a и b одинаковые и простые делители чисел a + 1 и b + 1 тоже одинаковые (и при этом a 6= б) Конечно или бесконечно множество пар натуральных чисел a, b, обладающих следующим свойством простые делители чисел a и b+1 одинаковые и простые делители чисел+ 1 и b тоже одинаковые. Укажите попарно различные натуральные числа, q, r, p 1 , q 1 , r 1 , для которых p 2 + q 2 + r 2 = p 2 1 + q 2 1 + r 2 и p 4 + q 4 + r 4 = p 4 1 + q 4 1 + r 4 1 ( Рамануджан). Условия задач. Бесконечные последовательности. Для любого ли натурального n из последовательности. можно выделить арифметическую прогрессию длины n? 16.7. Существует ли бесконечная последовательность натуральных чисел a 1 , a 2 , . . ., в которой нет степеней натуральных чисел и никакая сумма нескольких различных членов этой последовательности не является степенью натурального числа. Последовательности операций. Карточки с числами 1, 2, 3, . . ., 32 сложены в стопку по порядку. Разрешается снять сверху любое число карточек и вложить их между оставшимися карточками, не меняя порядка карточек в каждой из двух частей, а в остальном произвольно. а) Докажите, что за 5 таких операций можно разложить карточки в произвольном порядке. б) Докажите, что за 4 такие операции нельзя разложить карточки в обратном порядке. Многочлены и рациональные функции. Приведите пример рациональной функции те. отношения двух многочленов, которая отлична от константы и R(x) = R(1/x) и R(x) = R(1 − x). 16.10. Существует ли многочлен f(x, y) от двух вещественных переменных, который всюду отличен от нуля, но принимает значения, сколь угодно близкие к нулю. Существует ли многочлен f(x) с целыми коэффициентами, который при некоторых различных вещественных принимает одинаковые значения, но при всех различных рациональных значениях x принимает различные значения Глава 16. Примеры и конструкции. Разные примеры и конструкции. Можно ли разбить на пары 2n человек 2n − 1 способами так, чтобы каждый человек был в паре с каждым другим ровно при одном разбиении. а) Имеется кусок цепи из 60 звеньев, каждое из которых весит 1 г. Какое наименьшее число звеньев надо расковать, чтобы из образовавшихся частей можно было составить все веса в 1 г, 2 г, 3 г, . . ., 60 г (раскованное звено весит тоже 1 г)? б) Тот же вопрос для цепи из 150 звеньев. Можно ли провести в городе 10 автобусных маршрутов и установить на них остановки так, что какие бы маршрутов ни были взяты, найдётся остановка, не лежащая ни на одном из них, а любые 9 маршрутов проходят через все остановки. Дано n целых чисел a 1 = 1, a 2 , a 3 , . . ., a n , причём a i 6 a i+1 6 2a i (i = 1, 2, . . ., n − 1) и сумма всех чисел чёт- на. Можно ли эти числа разбить на две группы так, чтобы суммы чисел в этих группах были равны. Радиолампа имеет семь контактов, расположенных по кругу и включаемых в штепсель, имеющий семь отверстий. Можно ли занумеровать контакты лампы и отверстия штепселя так, чтобы при любом включении лампы хотя бы один контакт попал на своё место (те. в отверстие стем же номером. а) Имеется 555 гирь весом 1 г, 2 г, 3 г, 4 г, . . . . . . , 555 г. Разложите их натри равные повесу кучи. б) Имеется 81 гиря весом 1 г, 2 г, 3 г, . . ., 81 2 г. Разложите их натри равные повесу кучи. Рассматриваются всевозможные десятизначные числа, записываемые при помощи цифр 2 и 1. Разбейте их на два класса так, чтобы при сложении любых двух чисел каждого класса получилось число, в записи которого содержится не менее двух троек Решения задач. Прямой угол разбит на бесконечное число квадратов со стороной 1. Можно ли в каждом из этих квадратов написать натуральное число так, чтобы в каждом ряду квадратов, параллельном одной или другой стороне прямого угла, любое натуральное число встречалось ровно один раз? См. также задачу Решения. Ответ да, можно. Пусть p 1 , . . . , p 10 — различные простые числа, N = p 1 . . . p 10 . Тогда числа N 1 = p 1 N, . . . , N 10 = обладают требуемыми свойствами. Действительно, число делится на p 2 i , а число N j , где j 6= i, делится только на p i , а на оно уже не делится. С другой стороны, делится на N 2 , а делится на N j |