Книги по разным темам Pages:     | 1 |   ...   | 18 | 19 | 20 | 21 | 22 |   ...   | 30 |

2.115. Чтобы доказать, что существует циклический сдвиг последовательности {a1,..., an}, у которого все частичные суммы положительны, примените принцип максимума: рассмотрите тот циклический сдвиг, у которого наибольшее количество первых частичных сумм положительно. Единственность следует из того, что ни одну из последовательностей нельзя разбить на два отрезка с положительными суммами.

Чтобы получить формулу для чисел Каталана, дополните последовательность задачи 2.103 элементом a0 = 1.

2.116. Рассмотрите в произведении x0 x1 ... xn то умножение, которое делается последним.

Глава 3.1. Если p1, p2,..., pn Ч все простые числа, то число N = p p2 ... pn + 1 не может быть ни простым,x ни составным.

3.2. 2 и 19.

3.5. Перепишем уравнение в виде 2q2 = (p - 1)(p + 1). Заметим, что p Ч непременно нечетное простое число. Отсюда q Ч четное. Поэтому q = 2. Значит p = 3.

3.7. Пусть p1 = 3, p2 = 7,..., pn Ч все такие простые числа. Рассмотрим число N = 4p2 ... pn + 3. Оно не делится ни на одно из чисел p1, p2,..., pn, но обязательно содержит простой делитель вида 4k + 3.

3.8. Доказательство повторяет рассуждения задачи 3.7. В качестве числа N можно взять N = 6p1 ... pn + 5.

Ответы, указания, решения 3.9. Каждому делителю a числа n соответствует делитель b, для которого a b = n. Одно из чисел a или b не превосходит n.

3.10. Когда n Ч полный квадрат. Воспользуйтесь решением задачи 3.9.

3.11. 111 = 3 37; 1111 = 11 101; 11111 = 41 271; 111111 = 3 7 13 37; 1111111 = 239 4649.

3.12. Рассмотрите числа 1001! + 2, 1001! + 3,..., 1001! + 1001.

3.14. а) 5, 11, 17, 23, 29; б) 7, 37, 67, 97, 127, 157.

3.15. Возьмем в качестве начального элемента прогрессии элемент a этой прогрессии такой, что a > 1. Тогда все числа ak = a + kd при k = ma делятся на a, то есть являются составными.

3.17. Рассмотрите остатки от деления на 3.

3.18. 5.

3.20. n4 + 4 = n4 + 4n2 + 4 - 4n2 = (n2 - 2n - 2)(n2 + 2n - 2).

3.21. Подставьте n = 40 или n = 41. При n = 0, 1,..., 39 числа P(n) будут простыми.

3.23. Рассмотрите число p12 ... pn - 1.

3.24. 2 3 5 7 11 13 + 1 = 30031 = 59 509.

3.25. e5 = 1807 = 13 139.

3.26, 3.29. Воспользуйтесь формулами сокращенного умножения из задачи 6.78.

n n+1 2n 3.27. Так как 2n > n + 1, то 2n+1 | 22. Отсюда 22 - 1 | 22 - 1.

n+1 2n n Но тогда fn | 22 - 1 | 22 +1 - 2 = 2f - 2.

3.28. Смотрите задачу 3.19.

3.30. При x = 0 многочлен принимает значение a0. Поэтому a0 = p Ч некоторое простое число. Подставляя в многочлен P(x) числа x1 = p,.

.

x2 = p2, x3 = p3,..., получаем P(xj). p. Следовательно P(xj) = p (j = 1, 2,... ) и многочлен P(x) принимает одно и то же значение в бесконечном числе точек, что невозможно. Ответ: нет.

3.32. (m, n) + 1, m + n - (m, n).

3.33. Рассмотрите прямоугольник OABC, расположенный на координатной плоскости так, что его вершины имеют координаты O(0; 0), A(q, 0), B(q, p), C(0, p). Проведите в нем диагональ OB и прямые вида x + y = k (k = 0, 1,..., p + q), которые разделят ее на p + q равных частей.

3.34. Через 180 дней.

3.35. У пар (a, b) и (b, r) совпадают множества общих делителей.

Значит совпадают и наибольшие элементы в этих множествах.

3.38. Если (a, b) = 1, то для некоторых целых u и v выполняется равенство au + bv = 1. Домножив его на c, получаем равенство acu + 182 Ответы, указания, решения + bcv = c, в котором a делит левую часть. Значит a делит и правую часть, то есть a | c.

3.39. Если m > n и m = nq + r, где r < n, то один шаг алгоритма Евклида приводит к равенству ( 1.. 1, 1.. 1 ) = ( 1.. 1, 1.. 1 ).

....

m n n r То есть, применяя алгоритм Евклида к числам, мы получаем, что он применяется к их длинам m и n Поэтому, в конце концов, получится число, состоящее из (m, n) единиц.

3.40. 10.

3.41. 10.

3.42. 19 19 - 360 = 1.

3.43. 500.

3.45. Только если эти числа равны.

3.47. 20 отметок, 9 оборотов.

3.49. Примените алгоритм Евклида к числам, стоящим в числителе и знаменателе.

3.50. а) Так как (n2 + 2n + 4, n2 + n + 3) = (n + 1, 3), то дробь будет сократима, когда (n + 1, 3) > 1. Ответ: n = 3k - 1.

б) Так как (n3 -n2 -3n, n2 -n+3) = (n2 -n+3, 6n), то дробь можно сократить либо на 2, либо на 3, либо на некоторый делитель числа n.

Первый случай невозможен. Во втором случае находим, что n = 3k или n = 3k + 1. В третьем случае (n2 - n + 3, n) = (n, 3), поэтому n снова должно быть числом вида n = 3k. Ответ: n = 3k, n = 3k + 1.

3.51. а) Предположим, что данное число целое. Тогда после деления числителя на знаменатель с остатком, приходим к равенству n4 + 1 n + = n2 - n +.

n2 + n + 1 n2 + n + Либо полученная дробь равна нулю, что возможно при n = -3, либо выполняется неравенство 0 < |n2 + n + 1| < |n + 3|. Так как при любых n 0 < n2 + n + 1, то нужно рассмотреть два случая: n + 3 0 и n + 3 < 0.

В первом случае, приходим к неравенству n2 2. Из значений n = -1, n = 0, n = 1 условию задачи удовлетворяют только первые два. Ответ:

n = -3, -1, 0.

б) n = 0, 1.

3.52. n = 2, 3.

3.53. На 17.

3.54. а) При m n выполняется равенство (am - 1, an - 1) = = (am-n - 1, an - 1). Поэтому алгоритм Евклида для чисел становится Ответы, указания, решения алгоритмом Евклида для показателей и заканчивается парой показателей (m, n) и 0. Можно также сказать, что задача равносильна задаче 3.39. Действительно, при решении задачи 3.39 основание системы счисления не имело никакого значения. В частности, можно считать, что вычисления проводились в системе счисления с основанием a.

б) Воспользуйтесь равенством fn+1 = f0f1... fn + 2.

3.55. Воспользуйтесь взаимной простотой чисел Ферма.

3.57. Воспользуйтесь результатом задачи 3.38.

3.58. Воспользуйтесь результатом задачи 3.57.

3.64. Начните, например, с двух соседних чисел Фибоначчи Fn и Fn+1.

3.66. 7 и 2.

3.68. а) Воспользуйтесь методом математической индукции.

3.73. Как и в задаче 3.72, каждой точке с целыми неотрицательными координатами (x; y) следует поставить в соответствие число N(x, y) = = ax + by. Все точки, для которых N(x, y) = c (13.3) получаются друг из друга сдвигом на вектор (b; -a). Отсюда следует, что наименьшее число c, для которого уравнение (13.3) имеет n + решение, равно nab + a + b. В этом случае все решения описываются формулой (xk; yk) = (1 + kb; 1 + (n - k)a) (0 k n).

Аналогично, наименьшее число c, для которого уравнение (13.3) имеет n решений, равно (n - 1)ab + a + b. Поэтому те c, для которых уравнение (13.3) имеет n решений, находятся в пределах (n - 1)ab + a + b c nab + a + b.

3.74. Точка с координатой 4140.5.

3.76. 27.

3.77. 24.

3.78. 123.

3.81. При помощи формул задачи 3.80, доказательство каждого тождества сводится к доказательству некоторого равенства, содержащего максимумы и минимумы.

а) max(, min(, )) = ;

б) min(, max(, )) = ;

в) + + = max(,, ) + min( +, +, + );

г) + + = min(,, ) + max( +, +, + ).

3.84. а) 32; б) 3 4 6 8 12.

184 Ответы, указания, решения 3.86. Равенства следуют из того, что все делители числа n = p ...

s... p имеют вид s 1 s d = p... p (0 1 1,..., 0 s s).

1 s 3.87. n = 12.

3.88. а) 28; б) 160 или 169.

3.89. x = 6, y = 5, z = 4.

3.90. Мультипликативность функций (n) и (n) следует из формул задачи 3.86.

3.91. Все делители числа n можно разбить на пары чисел a, b таких, что a b = n, причем в каждой паре одно из чисел обязательно не превосходит n.

3.93. (m n) < (m) (n); (m n) < (m) (n).

3.94. Воспользуйтесь формулой для (n) из задачи 3.86.

3.95. Представим n в виде n = 2k-1b, где b Ч нечетное число, k 2.

Поскольку (x) Ч мультипликативная функция, то (n) = (2k-1)(b) = (2k - 1)(b).

По условию, (n) = 2n = 2kb, так что (2k - 1)(b) = 2kb.

Отсюда b = (2k - 1)c, (b) = 2kc = b + c.

Если c = 1, то у числа b существует по крайней мере три положитель ных делителя b, c и 1. В этом случае (b) 1 + b + c, что противоречит равенству (b) = b + c. Поэтому c = 1, (b) = b + 1, то есть b = 2k - 1 Ч простое число. Согласно задаче 3.29, это возможно только при простых значениях показателя k. Таким образом n имеет вид n = 2p-1(2p - 1), где p и b = 2p - 1 Ч простые числа.

Первые простые числа Мерсенна p = 2, 3, 5, 7 дают совершенные числа n = 6, 28, 496, 8128.

3.96. 220 и 284; 17296 и 18416.

3.98. 120.

3.100. Оба числа совпадают с количеством натуральных чисел, не превосходящих и делящихся на d.

3.102. Отбросьте знак целой части в формуле Лежандра и дополните сумму до бесконечной геометрической прогрессии.

Ответы, указания, решения 3.103, 3.104. По формуле Лежандра p = (akpk-1 +... + a1) + (akpk-2 +... + a2) +... + ak = = ak(pk-1 +... + p + 1) +... + a1 = (ak(pk - 1) +... + a0(p0 - 1)) (n - ak -... - a1 - a0) = =.

(p - 1) (p - 1) 3.107. Нет. Рассмотрите числа n вида n = 2k - 1 и примените к ним формулу Лежандра.

3.108. 377 пар кроликов.

3.109. Пусть an Ч количество способов, которыми кузнечик может добраться до n-й клетки. Тогда a1 = a2 = 1. Кроме того, в (n + 1)-ю клетку кузнечик может попасть либо из n-й клетки, либо перепрыгнув n-ю клетку. Поэтому an+1 = an-1 + an. Отсюда an = Fn-1.

3.110. 233 способами.

3.111. Из начальных условий F0 = 0, F1 = 1 и рекуррентного соотношения Fn+2 = Fn+1 + Fn числа Фибоначчи с отрицательными номерами определяются однозначно: F-n = (-1)n+1Fn.

3.112. Примените индукцию.

3.113. Все равенства доказываются при помощи метода математической индукции.

3.114. Разбейте все пути кузнечика на две группы: проходящие и не проходящие через n-ю клетку.

3.116. 1.

F3 Fn+3.117. -.

F1 F2 Fn Fn+3.118. а), б), в) Рассмотрите последовательность остатков от деления Fn на 2, 3 и 4. г) Воспользуйтесь тождеством из задачи 3.114.

3.119. Рассмотрим остатки от деления чисел F1, F2,... на m. По двум соседним элементам этой последовательности она однозначно восстанавливается влево и вправо. Поэтому эта последовательность циклически повторяется и 0 (остаток от деления F0 на m) встретится в ней бесконечно много раз.

3.122. а) Воспользуйтесь результатом задачи 3.35. б) Воспользуйтесь равенством (Fm+n, Fm) = (Fm, Fn), которое следует из тождества задачи 3.114.

3.123. Из пункта а) задачи 3.113 следует равенство Fn + Fn+1 +... + Fn+7 = Fn+9 - Fn+2.

Это число не может быть числом Фибоначчи, поскольку Fn+8 < Fn+9 - Fn+2 < Fn+9.

186 Ответы, указания, решения 3.124. Найдите рекуррентную формулу для числа таких последовательностей. Можно также воспользоваться результатом задачи 3.109.

Для этого нужно каждую единицу интерпретировать как прыжок кузнечика через клетку.

3.125. Для разложения числа n в фибоначчиевой системе счисления нужно воспользоваться жадным алгоритмом: вычитать из n наибольшее число Fm, не превосходящее n.

3.126. Докажите, что числа Fn, найденные по формуле Бине, удовлетворяют начальным условиям F0 = 0, F1 = 1 и рекуррентному соотношению Fn+1 = Fn + Fn-1.

3.127. Раскройте скобки в формуле Бине, пользуясь формулой бинома Ньютона.

3.129. Равенство можно доказать методом математической индукции. Другое решение можно получить если воспользоваться задачами 3.124 и 2.67.

3.130. Sn = 0, если n 2, 5 (mod 6); Sn = 1, если n 0, 1 (mod 6);

Sn = -1, если n 3, 4 (mod 6). Более коротко ответ задачи можно записать так:

sin (n + 1)/3 2 (n + 1) Sn = = sin.

sin /3 3.131. Fn+1.

3.134. Fn-2 + Fn = Ln-1.

3.135. Ln = n + n.

3.136.

n Ln + Fn 5 k Lk - Fk - (-1)k = 1.

2 3.137. а) Подбором можно найти первые решения данного уравнения в целых числах (1, 0), (2, 1), (5, 3), в которых угадываются соседние числа Фибоначчи. Можно предположить, что ответом к задаче будут пары (xn, yn) = (F2n+1, F2n), где n Ч произвольное целое число.

(См. задачу 3.111.) Действительно, после подстановки пары (F2n+1, F2n) в уравнение, приходим к частному случаю тождества Кассини: F2 2n+-F2nF2n+2 = 1. (См. задачу 3.112.) Покажем, что у исходного уравнения нет других решений. Рассмотрим, например, те пары решений (x, y), в которых x 1 и y 0. Нетрудно проверить, что такие x и y должны быть связаны неравенствами y < x 2y. Кроме того, каждая пара решений (x, y) порождает целую цепочку решений по правилу... (x - y, 2y - x) (x, y) (2x + y, x + y)...

Ответы, указания, решения При движении по этой цепочке влево числа в парах уменьшаются:

0 < x = x - y < x, 0 y = 2y - x < y.

Поэтому на некотором шаге получится пара, в которой y = 0, x = 1, то есть пара (F1, F0). Но эта пара порождает цепочку... (F1, F0) (F3, F2)... (F2n+1, F2n)...

Значит, исходная пара должна иметь вид (x, y)=(F2n+1, F2n)=(xn, yn).

б) Все решения уравнения имеют вид (xn, yn) = (F2n, F2n-1), где n Ч произвольное целое число.

3.138. а) Докажите сначала вспомогательные неравенства Fn+ Fn, Fn+3 8Fn.

k k-1 k k-1 k 3.141. б) Fn = Fn-k+1Fn-1 + Fk-1Fn-1 = Fn-k-1Fn-1 + Fk+1Fn-1.

3.142. Докажите, что Ak допускает представление в виде линейной n комбинации с целыми коэффициентами чисел Ak-1 и Ak.

n-1 n-3.143. а) [11; 3, 4]; б) [1; 6, 6].

Fn+3.144..

Fn 3.147. Смотрите задачу 3.113, пункт г).

3.149. а) При k = 0, 1 равенство проверяется непосредственно. Далее применим индукцию. Предположим, что равенство доказано для некоторого k. Докажем его для k + 1. Подходящая дробь с номером k + получается из k-й дроби заменой ak на ak + 1/ak+1:

[a0; a1,..., ak, ak+1] = [a0; a1,..., ak + 1/ak+1].

Делая такую замену в равенстве Pk akPk-1 + Pk-[a0; a1,..., ak] = =, (13.4) Qk akQk-1 + Qk-приходим к соотношению (ak + 1/ak+1)Pk-1 + Pk-2 Pk+[a0; a1,..., ak, ak+1] = =.

(ak + 1/ak+1)Qk-1 + Qk-2 Qk+б) Примените индукцию. в) Из пункта б) немедленно следует, что числа Pk и Qk взаимно просты.

3.151. Воспользуйтесь свойством б) из задачи 3.149.

3.152. а) xk = 4 + 13k, yk = 31 + 101k (k Z); б) xk = -6 + 19k, yk = -19 + 79k (k Z).

3.153. Если бы 400 последовательных григорианских лет в точности соответствовали 400 астрономическим годам, то продолжительность одного астрономического года равнялась бы 97 366 + 303 365 = 365 + 400 188 Ответы, указания, решения дням, что всего лишь на 26 секунд превышает продолжительность года, найденную из астрономических наблюдений. Расхождение невелико:

оно составляет один день в 3323 года.

3.157. Рассмотрите прямоугольник со сторонами 1, 2 и воспользуйтесь геометрической интерпретацией алгоритма Евклида из задачи 3.146.

Pages:     | 1 |   ...   | 18 | 19 | 20 | 21 | 22 |   ...   | 30 |    Книги по разным темам