«Алфутова Н. Б. Устинов А. В. А45 Алгебра и теория чисел. Сборник задач для математических школ.— М.: МЦНМО, 2002.— 264 с. ISBN 5-94057-038-0 Настоящее пособие представляет собой сборник задач по математике, ...»

11.58. Каким рекуррентным соотношениям вида (11.4) удовлетворяют последовательности Найдите:

а) lim n ; б) lim n ; в) lim n. (См. также 11.36.) 3. Производящие функции Определение. Выражения вида называются формальными степенными рядами.

Формальные степенные ряды можно складывать, вычитать, умножать, делить, дифференцировать и устраивать их композицию, не беспокоясь о сходимости.

Определение. Производной формального степенного ряда (11.5) называется ряд 11.60. Найдите произведения следующих формальных степенных рядов:

11.61. Обращение степенного ряда. Докажите, что если a0 = 0, то для ряда F(x) существует ряд F1 (x) = b0 + b1 x +... + bn xn +...

такой, что F(x)F1 (x) = 1.

11.62. Вычислите:

Определение. Пусть {an } = a0, a1,... — произвольная числовая последовательность. Формальный степенной ряд будем называть производящей функцией этой последовательности.

11.63. Пусть F(x) — производящая функция последовательности {an }.

11.63. Докажите, что для нечётных p выполняется равенство например, 11.64. Вычислите производящие функции следующих последовательностей:

11.65. Вычислите суммы:

11.66. Пусть an — число решений уравнения в целых неотрицательных числах и F(x) — производящая функция последовательности an. Докажите равенства:

11.67. Пусть, как и раньше, an — число решений уравнения (11.6) в целых неотрицательных числах. Найдите формулу для an, пользуясь задачей 11.63. (См. также 2.70.) 11.68. Докажите тождество:

(См. также 1.2.) 11.69. Бином Ньютона для отрицательных показателей.

Докажите, что для всех неотрицательных n выполняются равенства 11.70. Вычислите производящие функции следующих последовательностей:

11.71. Счастливые билеты. Предположим, что у нас имеется 1 000 000 автобусных билетов с номерами от 000 000 до 999 999. Будем называть билет счастливым, если сумма первых трех цифр его номера равна сумме трех последних. Пусть N — количество счастливых билетов. Докажите равенства:

11.72. Найдите число счастливых билетов.

Определение. Назовем экспонентой степенной ряд 11.73. Докажите следующие свойства экспоненты:

а) Exp (z) = Exp(z); б) Exp(( + )z) = Exp(z) · Exp(z).

(См. также 7.52.) 11.74. Функции a, b и c заданы рядами Докажите, что (См. также 9.8.) 11.75. Докажите, что производящая функцияпоследовательности чисел Фибоначчи может быть записана в виде где =,=. Пользуясь результатом задачи 11.63, получите формулу Бине. (См. также 3.126 и 11.43.) 11.76. Докажите, что бесконечная сумма 0,1 + 0,01 + 0,002 + 0,0003 + 0,00005 + 0,000008 + 0,0000013 +...

сходится к рациональному числу.

11.77. Найдите производящую функцию последовательности чисел Люка Пользуясь этой функцией, выразите Ln в замкнутой форме через и. (См. также 3.135.) 11.78. Вычислите суммы 11.79. Производящие функции многочленов Фибоначчи и Люка. Найдите производящие функции последовательности многочленов Фибоначчи и последовательности многочленов Люка 11.80. Производящие функции многочленов Чебышёва. Найдите производящие функции последовательностей многочленов Чебышёва первого и второго рода (см. 7.38):

11.81. Вычислите, используя производящие функции, следующие суммы:

11.81. Найдите произвольную функцию линейной рекуррентной последовательности второго порядка (11.2) с начальными членами a0 и Определение. Разбиением называется представление натурального числа в виде суммы натуральных слагаемых. Порядок слагаемых считается несущественным. Например, разбиения 3 = 1 + 2 и 3 = 2 + не различаются.

11.82. Пусть p(n) — количество разбиений числа n. Докажите равенства:

(По определению считается, что p(0) = 1.) 11.83. На доске написано n натуральных чисел. Пусть ak — количество тех из них, которые больше k. Исходные числа стерли и вместо них написали все положительные ak. Докажите, что если с новыми числами сделать то же самое, то на доске окажется исходный набор чисел. Например, для чисел 5, 3, 3, 2, получается следующая цепочка 11.84. Докажите, что каждое целое положительное число n может быть 2n1 1 различными способами представлено в виде суммы меньших целых положительных слагаемых, если два представления, отличающихся хотя бы порядком слагаемых, считать различными. Например, лишь 241 1 = 7 следующих сумм имеют значение 4:

11.85. Каждое положительное число n можно представить в виде суммы различных слагаемых, причем это можно сделать столькими же способами, сколькими способами это же число представимо в виде суммы различных слагаемых. Например, все возможные представления числа 6 посредством различных слагаемых будут:

посредством нечетных:

Для доказательства этого факта обозначим через d(n) количество разбиений числа n на различные слагаемые, а через l(n) — на нечетные.

Установите равенства:

(Считается по определению, что d(0) = l(0) = 1.) 11.86*. Придумайте какое-либо взаимно однозначное соответствие между разбиениями натурального числа на различные и на нечетные слагаемые. В этом могут помочь диаграммы Юнга, уже упоминавшиеся в разделе 4, с. 148.

11.87. Определите коэффициент an в разложении (1+qx)(1+qx2 )(1+qx4 )(1+qx8 )(1+qx16 )... = a0 +a1 x+a2 x2 +a3 x3 +...

(См. также 5.64.) 11.88. Каков знак n-го члена в разложении произведения (См. также 5.73.) 11.89. Найдите общую формулу для коэффициентов ряда 11.90. Переменные x и y связаны равенством Разложите y по степеням x.

11.91. Переменные x и y связаны равенством Разложите y по степеням x.

вательности чисел Каталана {Cn }. Докажите, что она удовлетворяет равенству и получите явный вид функции C(z). (См. также 2.116.) 11.93. Выведите формулы для чисел Каталана из задачи 2.115, воспользовавшись результатом предыдущей задачи и равенством где — обобщенные биномиальные коэффициенты (смотрите определение на с. 154).

4. Многочлены Гаусса Определение. Для целых неотрицательных k и l определим функции gk,l (x) равенством что все они являются многочленами.

11.95. Докажите следующие свойства функций gk,l (x):

где hm (x) = (1 x)(1 x2 )... (1 xm ) (h0 (x) = 1);

б) gk,l (x) = gl,k (x);

в) gk,l (x) = gk1,l (x) + xk gk,l1 (x) = gk,l1 (x) + xl gk1,l (x);

г) gk,l+1 (x) = g0,l (x) + xg1,l (x) +... + xk gk,l (x);

д) gk,l (x) — многочлен относительно x степени kl.

Многочлены gk,l (x) называются многочленами Гаусса. Их свойства во многом аналогичны свойствам биномиальных коэффициентов.

В частности, среди многочленов они играют ту же роль, что и биномиальные коэффициенты среди чисел.

11.96. Определение функций gk,l (x) не позволяет вычислять их значения при x = 1. Но, поскольку функции gk,l (x) являются многочленами, они определены и при x = 1. Докажите равенство gk,l (1) = Ck. Каk+l кие свойства биномиальных коэффициентов получаются, если в свойства б) – г) из задачи 11.95 подставить значение x = 1?

11.97. Найдите сумму Sl (x) = g0,l (x) g1,l1 (x) + g2,l2 (x)... + (1)l gl,0 (x).

11.98. Обозначим через Pk,l (n) количество разбиений числа n на не более чем k слагаемых, каждое из которых не превосходит l. Докажите равенства:

а) Pk,l (n) Pk,l1 (n) = Pk1,l (n l);

б) Pk,l (n) Pk1,l (n) = Pk,l1 (n k);

в) Pk,l (n) = Pl,k (n);

г) Pk,l (n) = Pl,k (kl n).

11.99. Пусть fk,l (x) — производящая функция последовательности Pk,l (n):

а) Докажите равенства:

fk,l (x) = fk1,l (x) + xk fk,l1 (x) = fk,l1 (x) + xl fk1,l (x).

б) Докажите, что функции fk,l (x) совпадают с многочленами Гаусса gk,l (x).

11.100. Докажите, что при любых k и l многочлен gk,l (x) является возвратным, то есть xkl gk,l (1/x) = gk,l (x). Решите задачу двумя способами: пользуясь определением многочленов Гаусса и при помощи свойств чисел Pk,l (n) из задачи 11.98.

11.101. Докажите, что не используя свойства многочленов Гаусса.

12.1. Ученик Коля Васин при помощи метода математической индукции смог доказать, что в любом табуне все лошади одной масти.

Если есть только одна лошадь, то она своей масти, так что база индукции верна. Для индуктивного перехода предположим, что есть n лошадей (с номерами от 1 до n). По индуктивному предположению лошади с номерами от 1 до n1 одинаковой масти. Аналогично лошади с номерами от 2 до n также имеют одинаковую масть. Но лошади с номерами от 2 до n 1 не могут менять свою масть в зависимости от того как они сгруппированы — это лошади, а не хамелеоны. Поэтому все n лошадей должны быть одинаковой масти.

Есть ли ошибка в этом рассуждении, и если есть, то какая? (См.

также 1.4.) 12.2. Иногда вычитая дроби можно вычитать их числители и складывать знаменатели. Например:

Для каких дробей это возможно?

12.3. Найдите все дроби с числителем и знаменателем не превосходящими 100, в которых можно проводить сокращение на равные цифры.

Примером может служить равенство 12.4. Легко проверить равенства В каких еще случаях можно выносить логарифм за скобку?

12.5. При каких значениях a и b возможно равенство 12.6. Квадраты двух зеркальных чисел 12 и 21 также являются зеркальными числами (144 и 441). Какие двузначные числа обладают аналогичным свойством? И дополнительный вопрос: в каких системах счисления число 441 будет полным квадратом?

12.7. Черная пятница. Докажите, что тринадцатое число месяца с большей вероятностью приходится на пятницу, чем на другие дни недели. Предполагается, что мы живем по Григорианскому стилю (см.

3.153).

12.8. Коля Васин, решая задачу, получил в ответе шестизначное число. А потом он подумал, что это произведение двух трехзначных чисел и выполнил умножение. Каким был первоначальный ответ, если второй ответ оказался в три раза меньше?

12.9. Восстановите алфавит племени Мумбо-Юмбо из задачи 2.6.

12.10. Найдите коэффициент при x у многочлена 12.11. «1 = 1». Изучив комплексные числа, Коля Васин решил вывести формулу, которая носила бы его имя. После нескольких попыток ему это удалось:

После некоторых размышлений, Коля придумал более короткое доказательство своего тождества:

Не ошибся ли где-нибудь Коля Васин? (См. также 7.24.) 12.12. После экспериментов с мнимой единицей, Коля Васин занялся комплексной экспонентой. Пользуясь формулами задачи 7.51, он смог доказать, что sin x всегда равен нулю, а cos x — единице:

Где ошибка в приведенных равенствах? (См. также 7.55.) 12.13. «65 = 64 = 63». Тождество Кассини лежит в основе одного геометрического парадокса. Он заключается в том, что можно взять шахматную доску, разрезать ее на четыре части, как показано ниже, а затем составить из этих же частей прямоугольник:

Как расположить те же четыре части шахматной доски, чтобы доказать равенство «64 = 63»? (См. также 3.112.) 12.14. Из километров — в мили. В задаче 3.125 была введена фибоначчиева система счисления. Она оказывается удобной, когда нужно сделать перевод расстояния из километров в мили или наоборот.

Предположим, что мы хотим узнать, сколько миль в 30 километрах.

Для этого представляем число 30 в фибоначчиевой системе счисления:

Теперь нужно сдвинуть каждое число на одну позицию вправо, получая Поэтому предполагаемый результат — 19 миль. (Правильный ответ — около 18,46 миль.) Аналогично делается перевод из миль в километры.

Объясните, почему работает такой алгоритм. Проверьте, что он дает округленное число миль в n километрах при всех n 100, отличающееся от правильного ответа меньше чем на 2/3 мили.

12.15. Обозначим через S сумму следующего ряда:

Преобразовав равенство (12.1), можно получить уравнение, из которого находится S:

Сумму S можно также найти объединяя слагаемые ряда (12.1) в пары:

Наконец, переставив местами соседние слагаемые, получаем еще одно значение S:

Итак, действуя четырьмя разными способами, мы нашли четыре значения суммы S:

Какое же значение имеет сумма S в действительности?

Глава 1.15. Воспользуйтесь тождеством из задачи 1.14.

1.16. an = 2n + 1 (n 0).

1.26. При n = 1 утверждение задачи очевидно. Предположим, что утверждение справедливо для некоторого n 1 и докажем его для n+1. Назовем набор чисел допустимым, если ни одно из них не делится ни на какое другое. Пусть нам удалось среди чисел от 1 до 2n + найти допустимый набор из n + 2 чисел. В этом наборе будут обязательно присутствовать числа 2n + 1 и 2n + 2, так как иначе получается противоречие с индукционным предположением. Другие n чисел из допустимого набора обозначим a1,..., an. Среди них нет числа n + 1, так как n + 1 | 2n + 2. Поэтому, дополняя набор a1,..., an числом n + 1, получаем снова допустимый набор. Но он состоит из n + 1 числа в пределах от 1 до 2n, что снова противоречит предположению индукции.

Мы доказали даже чуть более сильное утверждение: среди любых n + 1 натуральных чисел, меньших 2n, есть два числа, отношение которых — степень числа 2.

1.37. Это неравенство удобно доказывать при помощи «обратной индукции» (см. задачу 1.4), то есть делать переход от n к n 1. Но предварительно понадобится доказать справедливость этого неравенство для всех n вида n = 2k.

1.42. Самое короткое решение содержит 28 1 перемещений.

1.45. Если квадрат допускает разбиение на n квадратов, то он допускает разбиение и на n + 3 квадрата (достаточно один из квадратов разрезать на четыре). Разобьем все натуральные числа на три арифметические прогрессии n = 3k, n = 3k + 1, n = 3k + 2, и в каждой из них найдем минимальное n, для которого задача имеет решение. В первой прогрессии минимальное такое n равно 6, во второй — 4, в третьей — 8. (Требуемые разбиения строятся из квадратов 3 3, 2 2 и 5 5.

1.47. а) 2 кольца (11 = 1 + 1 + 3 + 6). б) Из (n + 1)2n 1 колец.

1.48. Банк может выдать суммы 8, 9 и 10 рублей. Прибавляя к ним нужное количество трехрублевых купюр, можно получить любую большую сумму.

1.50. 1 + n(n + 1)/2.

1.53. (n3 + 5n + 6)/6.

1.58. Проведите индукцию по числу граней.

1.59. Пусть не все точки лежат на одной прямой. Проведем прямую через каждую пару точек и рассмотрим всевозможные пары: прямая и не лежащая на ней точка. Противоречие получается, если рассмотреть пару, в которой расстояние от точки до прямой минимально.

1.61. Пусть an число невырожденных треугольников периметра n с целыми длинами сторон. Докажите, что Глава 2.1. а) 24. б) 28.

2.3. 103 · 303.

2.4. Школьников в 27/25 раза больше.

2.6. 40.

2.11. 360.

2.12. 9 · 2.14. 37.

2.15. 54.

2.16. Найдите число способов поставить фишки на поля одного цвета и на поля разных цветов. Ответ: нет.

2.18. 2.19. Если всего имеется n точек, то из каждой выходит от 0 до n линий. Но не может быть двух точек таких, что из одной выходит n линий, а из другой — 0.

2.20. Если взять k + 1 карточку с нечетными номерами, то условие задачи будет выполнено. Если взять k + 2 карточки, то рассматривая разности чисел на них, мы получим не менее k + 1 различных чисел от 1 до 2k. Поэтому хотя бы 2 из них совпадут с числами на k невыбранной карточке.

2.21. Шахматная доска может быть разбита на 16 квадратов 2 2.

Если на доске более 16 королей, то два из них попадут в такой квадрат и будут бить друг друга. Ответ: 16.

2.22. В каждой из 50 пар женщина находиться не может.

2.23. Пусть N(k, l) и N(k, r) — количества левых и правых сапог k-го размера соответственно. По условию задачи Не может случиться так, что для каждого размера левых (правых) сапог меньше чем правых (левых). Без ограничения общности будем считать, что Тогда количество годных пар N(41, l) + N(42, l) + N(43, r) = 300 N(43, l) + N(43, r) 100.

2.24. См. задачу 2.19.

2.25. Расположим данные числа в порядке возрастания и разобьем их на группы по цифре десятков. Число m таких групп удовлетворяет условиям 6 m 10. Среди m групп найдется группа A6, в которой не менее 6-ти чисел. Аналогично (методом от противного) устанавливается существование групп A5,..., A1. Первое число возьмем из A1. Второе — из A2, так чтобы цифра единиц отличалась от цифры единиц первого числа и т. д.

2.27. 999.

2.28. Докажем по индукции, что если из чисел от 1 до 2n 2 (n 3) выбрано n + 1 различное число, то из них можно выбрать три таких числа, что сумма двух из них равна третьему. При n = 3 утверждение задачи очевидно. Предположим, что утверждение доказано для n = k и рассмотрим случай n = k + 1. Если k + 1 из выбранных чисел попали в промежуток от 1 до 2k 2, то применимо предположение индукции.

Если же это не так, то обязательно должны быть выбраны числа 2k и 2k. Другие k выбранных чисел находятся на отрезке от 1 до 2k 2.

Разбивая этот отрезок на пары (1, 2k 2), (2, 2k 3),..., (k 1, k), получаем, что одна из пар состоит из выбранных чисел. Но тогда они дают в сумме 2k 1. Если число 1002 заменить на 1001, то утверждение перестанет быть верным. Примером может служить набор 1000, 1001,..., 2000.

2.30. Пусть в турнире участвуют n команд. Тогда разыгрывается n(n 1) очков. Команды могли набрать разное количество очков (0, 1, ..., n 1) лишь после окончания турнира. Поэтому предпоследняя команда набрала 1 очко и обязана была проиграть победителю.

2.31. Пусть доска раскрашена в два цвета. Рассмотрим произвольный столбец. Один из цветов встречается в нем бесконечное число раз.

Зафиксируем этот цвет. Вычеркнем из таблицы все строчки, которые в выбранном столбце не содержат зафиксированный цвет. Покажите, что в оставшейся таблице можно найти четыре нужные клетки. Для решения задачи с произвольным числом цветов, примените индукцию.

2.33. Рассмотрим произвольную из 6-ти данных точек. По крайней мере 3 отрезка, выходящие из этой точки, окрашены в один цвет. Можно считать эти отрезки синими. Если два из их концов соединены отрезком синего цвета, то нужный треугольник найден. Если это не так, то концы отрезков образуют треугольник красного цвета.

2.34. Рассмотрим n последовательностей Каждая из них имеет ровно один элемент на отрезке [n + 1; 2n].

Значит, из (n + 1)-го выбранного числа хотя бы два окажутся в одной и той же последовательности.

2.36. 17!.

2.38. 8!.

2.39. 16!.

2.40. 16!/2.

2.41. 28 · 6! · 1111111.

2.42. а) 28!; б) 28! 27 · 2 · 26!.

2.43. C4.

2.49. По условию задачи, любые 5 человек сейф открыть не могут.

Значит у них нет ключа от некоторого замка. При этом любой другой член комиссии должен этот ключ иметь. Поэтому нужно поставить C5 замков. 4 ключа от каждого замка отдаются некоторой четверке членов комиссии, причем разные ключи раздаются разным четверкам. При этом, если соберутся 6 человек, то среди них будет по представителю из каждой четверки и они смогут открыть все замки.

В общем случае понадобится Cm1 замков и n m + 1 ключ к каждому из них.

2.54. а) 26; б) 51.

2.55. Рассмотрите n = 2a 1.

2.58. а) 5!; б) 6!/2; в) 8!/3!; г) 11!/(2! · 3!); д) 11!/(4! · 2! · 2!);

е) 13!/(2!)4.

2.59. Каждому маршруту можно поставить в соответствие слово, состоящее из m букв «x» и n букв «y» по следующему правилу: если делается шаг параллельно оси Ox, то пишем «x», если вдоль оси Oy, то пишем «y». Таких слов всего 2.60. Поставьте в соответствие каждому маршруту кузнечика слово, в котором по 9 раз встречаются буквы x, y и z. Ответ: 27!/(9!)3.

2.63. Выбор множеств A и B равносилен приписыванию каждому элементу множества C одной из букв a, b или c. В обоих случаях ответ 3n.

2.66. Каждому такому числу однозначно соответствует выбор 6-ти цифр из набора 9876543210. Ответ: C6.

2.67. Из (m+1)-й позиции (m1 место между белыми шарами и два места по краям) нужно выбрать n позиций, в которые будут положены черные шары. Ответ: Cn. m+ 2.72. 113 = C0 103 + C1 102 + C2 101 + C3 100, 114 = 14641.

2.74. В этой задаче возможны различные ответы. Можно, например, расположить сверху перевернутый треугольник Лейбница (смотрите задачу 2.88). Можно также доопределить биномиальные коэффициенты Ck при отрицательных n при помощи равенства а) из задаn чи 11.69.

2.77. а) Левая часть: число способов выбрать m элементов из r, а потом из выбранных m выбрать еще k. Правая часть: сразу выбираем k элементов из r, а из оставшихся выбираем еще m k.

2.79. 36 шаров.

2.81. Примените «жадный» алгоритм. Сначала из n нужно вычесть наибольшее число вида C3 так, чтобы остаток был неотрицательным.

Из него нужно вычесть наибольшее число вида C2. То что останется всегда можно записать в виде C1. x 2.82. Общее число способов выбрать компанию из 3 человек равно C3 = 120. Каждая ссора разрушает не более 8 таких компаний, поэтому число разрушенных компаний не больше 8 · 14 = 112. Значит осталось по крайней мере 8 дружных компаний.

2.84. C6 4( 3)64.

2.87. Каждая точка пересечения диагоналей однозначно определяет четверку вершин, через которые проходят эти диагонали. Наоборот, каждой четверке вершин соответствует ровно одна точка пересечения диагоналей. Поэтому число точек пересечения диагоналей Tn вычисляется по формуле Tn = C4. Для нахождения Kn — числа частей, на которые n-угольник разбивается диагоналями, нужно проверить равенство Суммируя его по m в пределах от 2 до n, находим, что Отсюда 2.88. Знаменатели чисел, расположенных в рядах гармонического треугольника, пропорциональны элементам треугольника Паскаля, причем коэффициентами пропорциональности служат граничные члены. Там, где в треугольнике Паскаля стоит число Ck, в треугольнике проверяется непосредственным вычислением.

2.90. Для нахождения суммы достаточно сложить следующие равенства, которые следуют из рекуррентной формулы для треугольника Лейбница (см. решение задачи 2.88) Общая формула аналогична равенству из задачи 2.77 д).

2.92. C4 /C4.

2.93. 5/90 = 1/18.

2.94. а) 1/103 ; б) 1/102.

2.96. Да, может.

2.100. 20.

2.101. Пусть Na — количество треугольников, у которых одна из сторон параллельна стороне BC исходного треугольника. Аналогично определим числа Nb, Nc, Na,b, Nb,c, Na,c и Na,b,c. Через N обозначим общее число треугольников. Тогда N = 63, Na = Nb = Nc = 62, Na,b = = Nb,c = Na,c = 6, Na,b,c = 1. Искомое число находится по формуле включений и исключений:

2.102. а) 13200; б) 8800; в) 8000.

2.103. 1600.

2.104. 998 910.

2.107. Пусть S — площадь всей комнаты, Si — площадь i-го ковра (i = 1, 2, 3), Si,j — площадь, покрытая i-м и j-м коврами одновременно (1 i < j 3), и S1,2,3 — площадь, покрытая всеми тремя коврами. По формуле включений и исключений Отсюда Поэтому хотя бы одна из площадей S1,2, S1,3 или S2,3 не меньше 1 м2.

2.108. Решение этой задачи повторяет рассуждения из задачи 2.107.

2.109. б) Формула включений и исключений дает:

Запишем отдельно равенства, которые получаются если формулу включений и исключений применить отдельно к каждому ковру. Например, для первого имеем Складывая пять подобных равенств, получаем Найдем теперь такую линейную комбинацию равенств (13.1) и (13.2), в которой отсутствует сумма Si,j,k. Очевидно, что для этого к неравенству (13.2) нужно прибавить утроенное неравенство (13.1):

Отсюда Значит для некоторых i и j выполняется неравенство Si,j 1/5.

в) Найдите линейную комбинацию равенств (13.1) и (13.2), в которой отсутствует сумма Si,j.

2.110.

цифры на отдельных частях показывают какими из фигур покрыты соответствующие участки. Например, цифры 1 и 2 в первой клетке означают, что она покрыта первой и второй фигурами. Эта схема показывает, что оценки 1/5 и 1/20 — точные.

2.111. Постройте взаимно однозначное соответствие между такими последовательностями и расстановками скобок в произведении x0 · x1 ·... · xn по одному из правил 2.112. Чтобы построить взаимно однозначное соответствие между триангуляциями многоугольника и расстановками скобок в произведении x0 · x1 ·... · xn, нужно расставить на сторонах многоугольника переменные x0, x1,..., xn (оставшейся стороне приписывается все произведение x0 · x1 ·... · xn ).

2.113. Придумайте соответствие между всеми такими маршрутами ладьи и последовательностями чисел из задачи 2.111.

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.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.21. Подставьте n = 40 или n = 41. При n = 0, 1,..., 39 числа P(n) будут простыми.

3.23. Рассмотрите число p1 ·2 ·... · pn 1.

3.25. e5 = 1807 = 13 · 139.

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

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.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 + + bcv = c, в котором a делит левую часть. Значит a делит и правую часть, то есть a | c.

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

3.40. 10.

3.41. 10.

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. а) Предположим, что данное число целое. Тогда после деления числителя на знаменатель с остатком, приходим к равенству Либо полученная дробь равна нулю, что возможно при 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.

3.53. На 17.

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

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

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

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

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

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

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

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

3.76. 27.

3.77. 24.

3.78. 123.

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

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

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

3.86. Равенства следуют из того, что все делители числа n = p1 ·...

... · ps имеют вид 3.87. n = 12.

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

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

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

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

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

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

Поскольку (x) — мультипликативная функция, то По условию, (n) = 2n = 2k b, так что Отсюда Если 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 = 2p1 (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. По формуле Лежандра 3.107. Нет. Рассмотрите числа n вида n = 2k 1 и примените к ним формулу Лежандра.

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

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

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

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

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

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

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

3.116. 1.

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+8 < Fn+ Fn+2 < Fn+9.

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

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

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

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

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). Более коротко ответ задачи можно записать так:

3.131. Fn+1.

3.134. Fn2 + Fn = Ln1.

3.136.

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

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

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

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

3.138. а) Докажите сначала вспомогательные неравенства Fn+ 3.141. б) F = Fnk+1 Fn1 + Fk1 Fn1 = Fnk1 Fn1 + Fk+1 Fn1.

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

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

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

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

Делая такую замену в равенстве приходим к соотношению б) Примените индукцию. в) Из пункта б) немедленно следует, что числа 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 астрономическим годам, то продолжительность одного астрономического года равнялась бы дням, что всего лишь на 26 секунд превышает продолжительность года, найденную из астрономических наблюдений. Расхождение невелико:

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

3.158. В Юлианском стиле ошибка в одни сутки накапливается за 128 лет.

3.159. [365; 4, 7, 1] = 365. Омар Альхайями ввел цикл из 33 лет, в котором семь раз високосный год считался четвертый, а восьмой раз високосный год был не четвертый, а пятый. Таким образом, здесь имеется 8 лишних суток в 33 года. Ошибка в одни сутки в этом календаре набегает примерно за 5000 лет. Точнее сказать нельзя, потому что сама продолжительность астрономического года меняется из-за замедления вращения Земли вокруг своей оси. Этот эффект задается приближенной формулой Саймона Ньюкома:

1 год = (365,24219879 0,0000000614 · (n 1900)) суток, где n — номер года.

3.161. а) 2 = [1; 2]; б) 3 = [1; 1, 2]; в) 1/2 + 7 = [3; 6, 1, 6, 5].

3.163. 97/56.

3.164. Докажем сначала, что всякая чисто периодическая цепная дробь задает квадратичную иррациональность. При решении задачи 3.149 а) была получена формула (13.4), которая выражает зависимость подходящей дроби от последнего неполного частного. Заменяя в этой формуле ak на, приходим к равенству которое дает квадратное уравнение для :

Таким образом, — квадратичная иррациональность. Осталось заметить, что если то также является квадратичной иррациональностью.

3.166. Проверьте, что последовательность удовлетворяет начальным условиям p1 = 2, p2 = 5 и рекуррентному уравнению pn+2 = 2pn+1 + pn, а последовательность — начальным условиям q1 = 1, q2 = 2 и рекуррентному уравнению qn+2 = 2qn+1 + qn. Отсюда будет следовать, что pn /qn — n-я подходящая дробь к числу [2] = 1 + 2.

3.167. Предположим сначала, что — число иррациональное и pn /qn — подходящие дроби к. В этом случае последовательность знаменателей стремится в бесконечность, значит для некоторого n будут выполнены неравенства qn q qn+1. При таком выборе n дробь p/q может совпасть только с n-й подходящей дробью. Покажем, что другие варианты невозможны. Действительно, если это не так, то число p/q попадает в один из трех интервалов (; pn /qn ), (pn /qn ; pn+1 /qn+1 ), (pn+1 /qn+1 ; ) (будем считать, что pn /qn < pn+1 /qn+1 ). В первом случае из неравенств следует оценка qn > 2q, которая противоречит выбору n. Во втором случае имеем:

откуда q qn + qn+1, что также противоречит выбору n. В третьем случае из неравенств Таким образом, ни один из этих трех случаев невозможен, и В случае рационального = следует воспользоваться тем, что при = 3.169. Предположим, что для некоторой дроби p/q выполняется неравенство Согласно задаче 3.167, число p/q является подходящей дробью к 2.

Пусть p/q = Pn /Qn. Тогда Рассмотрим последовательность чисел an = |Pn+k Qn Pn Qn+k |. Она удовлетворяет начальным условиям a0 = 0, a1 = 1 и рекуррентному соотношению ak = 2ak1 + ak2 (k 2).Поэтому числа an совпадают со знаменателями подходящих дробей к 2: ak = Qk1 (k 1), то есть Чтобы получить противоречие с исходным предположением, достаточно доказать неравенство Свойства чисел Qn похожи на свойства чисел Фибоначчи. В частности, для них можно доказать равенство, аналогичное соотношению из задачи 3.114:

Отсюда Остается заметить, что 3.170. Примените алгоритм Евклида к многочленам aFk+2 1 и Fk+ 3.173. Число = [a0 ;..., an ] является корнем многочлена f(x) = = qn x2 + (qn1 pn )x pn1. Вторым корнем будет сопряженная иррациональность. Так как f(0) = pn1 < 0 и f(1) = pn pn1 > 0, то второй корень принадлежит интервалу (1; 0).

Глава 4.3. Если a и b — нечетные числа, то равенство a2 + b2 = c2 невозможно, поскольку c2 не может давать остаток 2 при делении на 4.

4.5. Каждая кость домино накрывает одну черную и одну белую клетки доски. Но из шахматной доски вырезаны две черные клетки.

Ответ: нет.

4.12. Рассмотрите множества четных и нечетных чисел.

4.18. Проследите за четностью числа стаканов, которые стоят вверх дном.

4.19. Не обращайте внимания на угловые и центральные клетки.

4.20. Воспользуйтесь тем, что при любых слияниях амеб, четность суммарного количества амеб типов A и B не меняется. То же самое можно сказать про типы A, C и B, C. Ответ: останется амеба типа B.

4.21. Расставьте амеб сначала как на рисунке 1.

Если в начале игры снята фишка с центральной клетки, то, рассуждая как в задаче 4.20, получаем, что последняя фишка может остаться только на клетке, помеченной буквой A. Но амеб с самого начала можно расположить и по-другому (смотрите рис. 2). Клеток, которые оба раза оказываются помечены буквой A оказывается 5 и это именно те клетки, которые указаны в условии задачи.

4.22. В расширенной таблице сумма элементов в любом столбце и в любой строке четная. Если изменить один из элементов, то изменятся суммы для одной строки и одного столбца (станут нечетными). Чтобы исправить такую ошибку, надо будет изменить тот элемент таблицы, который находится на пересечении строки и столбца с нечетными суммами. Минимальное число ошибок, которые нельзя обнаружить — 4.

Например, можно изменить все четыре цифры в сообщении 0111. При этом суммы во всех строках и столбцах останутся четными.

4.23. p2 1 = (p 1)(p + 1). Четные числа p 1 и p + 1 отличаются на 2, поэтому одно из них делится на 4.

4.24. Такое число делится на 111 = 3 · 37.

4.25. а) 8 делителей можно найти среди чисел вида 11... 1 (n единиц) выбирая n = 1, 2, 3, 6, 331, 662, 993. б) Воспользуйтесь равенством 4.29. m/n = 5/2.

4.30. Подставьте c = 6k a b или рассмотрите остатки от деления на 2 и на 3.

4.31. Проследите за тем, как меняется предпоследняя цифра у чисел вида 11n.

4.32. Пусть b и c — длины второго катета и гипотенузы. Возможны следующие варианты: (b, c) = (8, 17), (35, 40), (36, 39) и (112, 113).

Ответ: 4.

4.33. а) (x, y) = (±5, ±9), (±10, ±3). б) Представьте уравнение в виде (1 + x)(1 + x2 ) = 2y. Ответ: (x, y) = (0, 0), (1, 2).

4.34. k1999 + (17 k)1999. 17.

4.35. Разобьем номера всех счастливых билетов на две группы.

В первую группу отнесем номера, которые состоят из двух равных трехзначных чисел (например, 765765). Все остальные номера отнесем ко второй группе. Поскольку то каждый номер из первой группы делится на 13, а, значит, делится на 13 и сумма всех номеров из первой группы. Рассмотрим номер abcdef из второй группы (abc = def). Вместе с этим номером во второй группе находится и номер defabc. Таким образом, все номера из второй группы разбиваются на пары. Сумма номеров в каждой паре делится на 13, так как abcdef + defabc = (abc + def) · 1001 = (abc + def) · 7 · 11 · 13.

Поэтому делится на 13 и сумма всех номеров из второй группы.

4.36. Рассмотрите остаток, который такое число будет давать при делении на 9.

4.39. а) Не может, так как 2004 · 4 не делится на 10 = 1 + 2 + 3 + 4.

б) Может. Можно взять 401 пару квадратов с таким расположением чисел (1, 2, 3, 4) и (4, 3, 2, 1).

число p в числителе сократиться не может.

4.43. Пусть n составное число и p — один из его простых делителей.

Представим n в виде n = p m, где (m, p) = 1. По формуле Лежандра (см. задачу 3.101) находим, что p входит в разложение Cp в степени n 1, поэтому n Cp. n 4.45. Воспользуйтесь результатом задачи 4.42.

4.46. Нет. Например, если мы на первом шаге объединяем две первых кучки, то дальше в любой из получающихся кучек количество камней будет кратно 5.

4.47. Воспользуйтесь тем, что среди чисел a1, a1 +a2,..., a1 +a2 +...

... + an либо одно делится на n, либо два дают равные остатки при делении на n.

4.48. Покажем, что среди 10 последовательных чисел найдется такое, которое не делится на числа 2, 3, 5, 7. Оно и будет удовлетворять условию задачи. Действительно, среди этих чисел 5 делятся на 2. Среди оставшихся чисел не более 2 делятся на 3, и не более одного — на 5 и 7.

Таким образом исключается не более 9 чисел.

4.49. Среди чисел 1, 2,..., 99 есть 50 нечетных и 49 четных. Это значит, что на одной из карточек на обеих сторонах будут написаны нечетные числа.

4.50. а) Ничего. б) Это соотношение справедливо для всех целых a 4.51. Воспользуйтесь равенствами (a + c) (b + d) = (a c) + (b d), ac bd = c(a b) + b(c d).

4.52. Согласно определению, класс a состоит из таких чисел b, что должно иметь вид mt + a.

4.53. Пусть a = b. Рассмотрим элемент c, принадлежащий обоим этим классам. Согласно предыдущей задаче, для некоторых целых t и t2 будут выполняться равенства c = a + mt1, b = a + mt2. Отсюда a b = m(t2 t1 ), то есть b a (mod m).

4.54. По принципу Дирихле такие числа попадают по одному в каждый из классов по модулю m.

4.59. Первый игрок должен следить за тем, чтобы количество камней, оставшихся после его хода, давало остаток 1 при делении 6.

4.62. Если одна фирма приобрела x килограммов яблок, то вторая— 2x, поэтому масса приобретенных яблок должна делится на 3.

4.64. Дискриминант дает остаток 5 при делении на 8, и поэтому не может быть полным квадратом.

4.68. От числа b · 105 + a делается переход к числу 10a + b. При делении на 7 эти числа дают остатки 5b + a и 3a + b. Утверждение задачи следует из сравнения 5b + a 5(3a + b) (mod 7).

4.69. Среди этих чисел всегда есть одно, которое делится на 3. Поэтому p = 3.

4.71. Здесь, как и в задачах 4.69, 4.70, нужно рассмотреть остатки от деления на 3.

4.72. Среди любых пяти последовательных членов такой арифметической прогрессии один обязательно делится на 5. Если это не 5, то простых чисел, идущих подряд, будет не более 4. Ответ: 5, 11, 17, 23, 29.

4.74. Так как числа n2 при делении на 3 дают остатки либо 0, либо 1, то указанное число целым быть не может.

4.75. Сравнение a2 + b2 0 (mod 3) возможно только если оба числа a и b делятся на 3. Аналогичные рассуждения проходят и для модуля m = 4.78. Остаток равен 24 1 (mod 17).

4.79. Нет. Рассмотрите числа Евклида en по модулю 5.

4.80. Перейдите от равенства a2 + b2 = c2 к сравнению по соответствующему модулю.

4.83. а), б), г) ни при каких n; в) при n = 3 + 11k (k Z).

4.84. а) n = 8 + 17k (k Z); б) ни при каких.

4.91. Докажите, что при всех целых x будет выполняться сравнение P(x) 1 (mod 2). Из него будет следовать, что значения P(x) не могут быть нулевыми.

4.93. а) x 2 (mod 13); б) x 24 (mod 37); в) x 5 (mod 11);

г) x 15 (mod 169).

4.94. 1652 и 6125.

4.97. Все числа от 2 до p 2 можно разбить на пары взаимно обратных по умножению чисел, то есть для каждого a из этого интервала найдется b (отличное от a по задаче 4.96) такое, что ab 1 (mod p).

Поэтому (p 1)! p 1 (mod p).

4.98. Пусть n — составное число. Если p — некоторый простой делитель числа n (p < n), то (n1)! 0 (mod p), что противоречит условию (n 1)! 1 (mod p).

4.100. Число p — простое тогда и только тогда, когда 4((p 1)! + 1) + + p 0 (mod p). Остается доказать, что p + 2 — простое тогда и только тогда, когда 4((p 1)! + 1) + p 0 (mod p + 2). С этой целью умножим обе части очевидного сравнения p 2 (mod p + 2) на p + 1. Получаем Части полученного сравнения умножим на 2(p 1)! :

К обеим частям полученного сравнения прибавим по p + 4:

По теореме Вильсона p + 2 — число простое тогда и только тогда, когда (p + 1)! + 1 0 (mod p + 2) и, следовательно, 2((p + 1)! + 1) + (p + 2) 0 (mod p + 2), откуда 4((p 1)! + 1) + p 0 (mod p + 2).

4.101. Из условия задачи следует, что a1 a2 + a2 a3 +... + an1 an + + an a1 0 (mod 4). Это сравнение остается справедливым при замене знака у любого из чисел aj (j = 1,..., n). Заменив все числа на +1, приходим к сравнению n 0 (mod 4).

4.102. Докажите неразрешимость по модулю m, где а) m = 4;

з) m = 13.

4.103. Сумма пяти последовательных целых чисел всегда делится на 5:

Но число n2 + 2 не может делится на 5, поэтому 5(n2 + 2) полным квадратом не является.

4.104. Выберите среди чисел 1, 2,..., n то, которое делится на максимальную степень двойки. Такое число будет ровно одно. Поэтому после приведения к общему знаменателю числитель будет нечетным.

4.105. Для решения задачи нужно рассмотреть последние цифры указанных чисел, или, что то же самое, перейти к сравнению по модулю 10.

4.107. Воспользуйтесь задачей 3.38.

4.108. Во всех случаях ответ 6.

4.111. Воспользуйтесь соотношением 10p1 1 = 99... 9 0 (mod p).

4.115. При a = 0 утверждение очевидно. Предположим, что оно доказано для некоторого a 0. Из результата задачи 4.42 следует соотношение (a+1)p ap +1 (mod p). Далее, применяя предположение индукции, приходим к нужному сравнению.

4.117. Существует a одноцветных раскрасок и раскрасок, в которых участвует не менее двух цветов. Ответ: + a.

4.118. а) 1; б) 9.

4.119. Данное число делится на 31.

4.120. Данное число делится на 1093.

4.122. Пусть q — простой делитель числа 2p 1. Тогда выполняются сравнения 2p 1 0 (mod q) и 2q1 1 0 (mod q) (второе из них — малая теорем Ферма). Далее следует воспользоваться результатом задачи 3.54 а).

4.123. Воспользуйтесь равенством n16 1 = (n8 1)(n8 + 1).

4.129. Применяя формулу из задачи 3.127, находим, что Fp 5(p1)/ (mod p), 2Fp+1 1 + 5(p1)/2 (mod p). Кроме того, 5(p1)/2 1 (mod p) при = 10k ± 1 и 5(p1)/2 1 (mod p) при = 10k ± 3.

4.130. Число x = 1 удовлетворяет условиям xp1 1 0 (mod p) и x 1 0 (mod p). Далее следует применить результат задачи 3.54.

4.131. Используйте условия xp1 1 0 (mod p) и x5 1 0 (mod p).

4.132. а) 16; б) p 1; в) p(p 1); г) При подсчете (p ) нужно будет отбрасывать все числа, делящиеся на p. Таких чисел на отрезке от 1 до p будет p. Поэтому (p ) = p1 (p 1).

4.133. p.

4.134. Числа, взаимно простые с b, находятся в (b) столбцах.

В каждом из них (a) чисел, взаимно простых с a. (См. задачу 4.55.) 4.135. (m).

4.136. (a, m) = 1 и b делится на все простые числа из разложения m.

4.139. а) x = 3, 4, 6; б) x = 15, 30, 20, 24, 16; в) 36; г) нет решений.

4.140. Необходимо, чтобы (m) = 2. Но 1 5 (mod 4), поэтому ответом служат только числа 3 и 5.

4.141. а) x = 2 ; б) x = 21 32 (1, 2 1); в) нет решений.

4.142. а) При простом n; б) при четном n; в) при любом n.

4.144. Каждому простому числу p, являющемуся делителем как m так и n, в числе (m · n) соответствует множитель 1 1/p, а в числе (m) · (n) — множитель (1 1/p)2. Так как (1 1/p) < 1, то при (m, n) = 1 будет выполняться неравенство (m · n) > (m) · (n).

4.145. 8, 12.

4.146. Все такие дроби можно разбить на пары k/n, (nk)/n. Числа в такой паре совпадать не могут. Из равенства k/n = (n k)/n следует, что n — четное, k = n/2 и дробь k/n можно сократить на n/2.

4.147. Пусть S(n) — искомая сумма. Очевидно, что S(1) = 1. При n> Ответ: S(1) = 1, S(n) = (n)/2 при n > 1.

4.148. (d).

4.149. Рассмотрим ряд чисел из задачи 4.148. С одной стороны, он состоит из n дробей. С другой стороны, все числа разбиваются на группы дробей с равным знаменателем d, каждая из которых состоит из (d) чисел.

4.150. (n)/2.

4.151. а) Из мультипликативности функции Эйлера следует, что формулу достаточно доказать в случае, когда числа m и n суть степени одного и того же простого числа. Пусть m = p, n = p ( 0). Тогда нужное тождество следует из равенств [m, n] = m = p, (m, n) = n = p.

б) Если воспользоваться мультипликативностью функции Эйлера, то задача сводится к проверке равенства Оно, в свою очередь, следует из соотношения (p ) = p (p1). (См. задачу 4.132.) 4.152. 3(10 ) 1 0 (mod 104 ).

4.155. Делимость на 2 и на 3 проверяется непосредственно. Делимость на p следует из малой теоремы Ферма.

4.156. a(m)1 b.

4.158. В качестве n можно взять, например, (m).

4.159. Пусть n = p1... ps. Достаточно доказать, что 2n! 1. pj j при j = 1,..., s. Для этого нужно применить теорему Эйлера к каждому из чисел mj = pj j.

4.160. Так как 561 = 3·11·17, то достаточно доказать справедливость сравнений a560 1 (mod p), где p принимает значения p = 3, 11, 17.

Каждое такое сравнение выполняется по малой теореме Ферма.

4.161. Очевидно, что решением задачи могут быть только те a, для которых (a, 10) = 1. Так как (10) = 4, то сравнение a10 + (mod 10) равносильно сравнению a2 +1 0 (mod 10). Перебирая случаи a = ±1, a = ±3, находим, что a ±3 (mod 10). Ответ: a ± (mod 10).

4.162. Покажите, что при (a, m) = 1 выполняется соотношение 4.166. 3993, 3597, 6797.

4.167. Примените признаки делимости на 8, 9 и 11. Ответ: 1 380 456.

4.169. Нет. Для доказательства можно находить не сумму цифр, а просуммировать арифметическую прогрессию 1 + 2 +... + 500.

4.170. Для проверки делимости на 9 и 11 можно рассмотреть сумму данного числа с числом 8079... 2019.

4.173. 11 111 111 100.

4.175. 9.

4.179. Примените признак делимости на 11.

4.180. Примените признак делимости на 3.

4.181. Нет. Рассмотрите остатки от деления на 9.

4.182. Сравнения 10a + b 0 (mod 19) и a + 2b 0 (mod 19) равносильны.

4.184. Число xxyy всегда делится на 11. Если оно полный квадрат, то и число x0y должно делится на 11. Ответ: 882 = 7744.

4.185. Число получается из суммы своих цифр умножением на 12, значит, оно кратно 3. Согласно признаку делимости на 3, сумма цифр также делится на 3. Поэтому само число должно делится на 9. Кроме того оно делится на 4. Следовательно нужно искать среди чисел, которые делятся на 36. Поскольку сумма цифр трехзначного числа не превосходит 27, то само число может быть не больше 27·12 = 324. Перебор можно еще сократить, если заметить, что сумма цифр может быть не больше 18 (она делится на 9 и меньше 27). Поэтому само число не больше 18 · 12 = 216. Осталось перебрать числа 108, 144, 180, 216. Ответ: 108.

4.187. а) Стратегия второго: писать цифру так, чтобы сумма предыдущей цифры и его равнялась 6.

б) Стратегия первого: сначала нужно написать 1, а потом писать цифру так, чтобы сумма предыдущей цифры и его равнялась 6. В этом случае перед последним ходом второго игрока сумма цифр будет равна 55, и он не сможет добиться своей цели.

4.188. Рассмотрите остатки от деления на 9.

4.189. Так как aj 10j aj rj (mod m), то M N (mod m). Поэтому числа M и N могут делиться на m только одновременно.

4.191. Сравнение равносильно сравнению которое имеет место независимо от ai тогда и только тогда, когда q 1 0 (mod m). В частности, для m = 2 годится система счисления с любым нечетным основанием. Ответ: q = 1 + mk (k 1).

4.192. 21.

4.194. Исследуйте отдельно делимость на 5 и на 11. Ответ: n = = 6 + 55k, k Z.

4.195. а) Обозначим остаток от деления 1910 на 66 через r. Из сравнений 19 1 (mod 2), 19 1 (mod 3), 19 2 (mod 11), следует, что r 1 (mod 2), r 1 (mod 3), r (2)10 (mod 11). По малой теореме Ферма, (2)10 1 (mod 11). Отсюда r = 1. б) 11; в) 17; г) 36.

4.197. Воспользуйтесь теоремой Эйлера.

4.200.

4.201.

4.203.

4.204. 15803.

4.207. Пусть n = 2. Равенство можно переписать в виде c = a · m1 + b · m2. Для того, чтобы решить это уравнение, рассмотрите сравнение c a · m1 + b · m2 (mod m1 · m2 ) и воспользуйтесь задачей 4.196. Для произвольного n нужно применить индукцию 4.208. 45486.

4.209. 215 · 310 · 56.

4.210. а) Данное сравнение равносильно выполнению двух условий x(x 1) 0 (mod 24 ) и x(x 1) 0 (mod 54 ). Отсюда x 0, 1 (mod 24 ) и x 0, 1 (mod 54 ). Поэтому по модулю 104 исходному сравнению будут удовлетворять 4 числа, из которых два — это числа x = 0 и x = 1. Два других решения — это x = 0625 и x = 9376, из которых четырехзначным является только второе. Ответ: x = 9376.

б) Докажите утверждение по индукции. Если процесс нахождения таких чисел не остановить, то кроме 0 и 1 получатся два бесконечных «числа»

4.211. Примените китайскую теорему об остатках с m1 = p2,...

..., m37 = p2, где p1,..., p37 — различные простые числа.

Глава 5.1. а) 1/7 = 0,(142857); б) 2/7 = 0,(285714); в) 1/14 = 0,(714285);

г) 1/17 = 0,(0588235294117647).

5.3. 1/49 = 0,(020408163265306122448979591836734693877551). Если просуммировать геометрическую прогрессию 2/102 + 4/104 +..., то получается в точности 1/49.

5.4. 1/243 = 0,(004115226337448559670781893).

5.5. а) 15926/111111 = 0,(143334); б) 4/27 = 0,(148); в) 14/99 = = 0,(14).

5.9. Рассмотрите отдельно те цифры, которые встречаются конечное число раз и те, которые встречаются бесконечно много раз.

5.12. Среди указанных чисел бесконечно много четных.

в) Определим число равенством ( 3) = 2. Если =, то получаем невозможное равенство 3p = 4q.

Другой пример можно построить при помощи числа = 2.

Если оно рационально, то задача решена. Если оно иррационально, то 2 = 2 и искомой парой чисел будут и 2.

5.17. Подставляя в уравнение x = 1 + 3, приходим к равенству Так как 3 — иррациональное число, то такое равенство возможно лишь 5.18. Если числа a, b, c являются членами одной арифметической прогрессии, для некоторых целых и q будет выполняться После возведения последнего равенства в квадрат получаем, что ac — рациональное число. Но это невозможно, поскольку a и c — различные простые числа.

5.21. а) 9 = 100 1; б) 1; в) 10.

5.24. Возведите равенство в квадрат.

5.25. Для решения этой задачи удобнее доказать более общее утверждение: если b1,..., bn — ненулевые целые числа, a1,..., an — различные натуральные числа, свободные от квадратов, то Выбирая здесь a1 = 1, получаем иррациональность суммы радикалов a2 +... + an. Для доказательства соотношения 13.5 проведите индукцию по числу простых p1,..., pm, входящих в разложения чисел a1,..., an на множители.

5.26. Только если a и b являются степенями одного и того же числа, то есть a = dm и b = dn для некоторых натуральных d, m и n.

5.28. Тангенс угла между стороной треугольника и любой из координатных осей рационален. Углы треугольника являются суммами или разностями таких углов и, следовательно, также имеют рациональные тангенсы.

5.29. Воспользуйтесь тем, что прямая, проходящая через целые точки, имеет рациональный тангенс наклона, а tg 60 = 3 Q. / 5.31. Пусть на окружности лежат две точки (x; y) и (u; v). Тогда Невозможность последнего равенства доказывается возведением в квадрат.

5.32. ж) Смотрите задачу 6.82 г).

5.33. При четных n.

5.36. Как и в задаче 2.33, идея решения основана на принципе Дирихле. При k = 1 утверждение задачи очевидно. Далее применим индукцию. Предположим, что утверждение задачи доказано для k 1, и докажем его для k. Рассмотрим произвольную из N данных точек. Из нее выходит по крайней мере N1 = отрезков, окрашенных в один и тот же цвет, где x — минимальное целое число n такое, что x n. Для N1 справедлива оценка (См. задачу 3.100.) Если концы каких-либо двух из этих N1 отрезков соединены отрезком того же цвета, то нужный треугольник найден.

В противном случае, концы соединяются отрезками, окрашенными в k 1 цветов. Так как N1 > [(k 1)! e], то, согласно предположению индукции, можно найти треугольник одного цвета с вершинами в этих точках.

5.38. По формуле для суммы геометрической прогрессии 5.39. По теореме Эйлера 10k(m) 1 0 (mod m) при любом k 1.

Поэтому 9 · Ek(m) 0 (mod m). Если m не делится на 3, то Ek(m) (mod m). Если же m делится на 3 или на 9, то на m будут делится числа E3k(m) и E9k(m) соответственно.

5.41. Пусть r0 = 1, r1 = 10 m[10/m]... — остатки, которые возникают при делении 1 на m столбиком. Тогда rk 10k (mod m), так как приписывание нуля равносильно умножению на 10. Если (m, 10) = 1, то 10(m) 1 (mod m), то есть r(m) = r0 = 1. Отсюда следует, что у дроби отсутствует предпериод, и что длина периода делит (m).

5.42. 11, 33 и 99 — делители числа 99, не делящие 9.

5.43. Если 10t 1 (mod n), то остатки r0 и rt (см. задачу 5.38) совпадают, так как r0 = m и rt 10t m (mod n). Значит период дроби m/n делит t. Наоборот, если T — длина периода, то rT = r0 (дробь чисто периодическая согласно задаче 5.41) и r0 10T r0 (mod n). Так как r0 = m и (m, n) = 1, то полученное сравнение можно сократить на r0. Следовательно, 10T 1 (mod n).

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

5.46. Пусть t = 2n — длина периода. Согласно задаче 5.43, выполняется сравнение 10t 1 (mod q). Отсюда 10n 1 (mod q) поэтому N1 + N2 = 99. .. 9.

5.47. При разложении 1/7 в десятичную дробь последовательность остатков устроена следующим образом:

Первое свойство объясняется равенствами Объяснение второго свойства получается, если в равенстве 1/7 + + 2/7 + 4/7 = 1 перейти к десятичной записи.

Чтобы объяснить последнее свойство, запишем N в виде N = = (106 1)/7. Отсюда N2 = (106 1)2 /49. Число, которое получается сложением половинок числа N2, будет периодом дроби Так как то из половинок числа N2 получится число N.

5.48. См. решение задачи 5.41.

5.51. Пусть abcdef = 3 · fabcde. Рассмотрим число, которое разлагается в периодическую десятичную дробь с периодом abcdef:

Тогда Отсюда =. Остается перебрать различные значения f.

5.52. Рассмотрите десятичные дроби, у которых искомое число является периодом.

5.57. Да. Причем меньшим числом взвешиваний обойтись нельзя.

5.59. а) 24 1 = 15; б) (34 1)/2 = 40.

5.60. 1, 3, 9 и 27 кг.

5.61. а) Первую веревку следует поджечь с двух концов, а вторую — с одного. После догорания первой веревки второй останется гореть минут. Чтобы сократить этот промежуток вдвое, следует поджечь и второй конец оставшейся веревки. б) 24 1.

5.62. а) Лампочка может находится в трех состояниях — включенном, выключенном и в нагретом. б) 9.

наименьшее число операций равно k1 + m.

5.65. b(15) = 6, но l(15) = 5:

Аналогично l(63) = 8 < 10 = b(63).

5.66. Для нахождения числа нужно сложить первые числа с выбранных карточек. Например, если загадано число 23, то потребуется сложить числа 1, 2, 4 и 16.

5.67. Загаданная карта всегда оказывается в центре колоды.

5.71. Если A четно, то представление числа A получается из представления меньшего числа m = A/2 «сдвигом» на один разряд. Если же A нечетно, то a0 = ±1 и число a1 должно равняться нулю; поэтому число A a0 делится на 4 и представление числа A получается из представления меньшего числа m = (A a0 )/4 «сдвигом» на два разряда и добавлением цифры a0. В обоих случаях единственность представления числа A следует из единственности представления числа m.

5.72. Числа от 0 до 1 удобно рассматривать как бесконечные троичные дроби из цифр 0, 1 и 2. Числа, о которых говорится в пункте в) — это те числа, в троичной записи которых нет ни одной 1.

5.73. а) 1; б) нет; д) n-й элемент данной последовательности совпадает по модулю 2 с (n) (суммой двоичных цифр числа n).

5.74. Занумеруем диски в головоломке «Ханойская башня» числами от 0 до 7. При увеличении на 1 числа n, записанного в двоичной системе счисления, могут измениться цифры сразу в нескольких разрядах. Если среди всех изменившихся разрядов наибольший номер имеет k-й разряд, то это означает, что на n-м шаге решения головоломки «Ханойская башня» следует перемещать диск с номером k.

5.75. а) Если по кругу стоят числа 1, 2,..., 2n, то вначале вычеркиваются все четные числа. Оставшиеся числа 1, 3, 5,..., 2n 1 снова подвергаются процедуре вычеркивания. k-е число в этом списке имеет вид 2k 1. После того, как из этого списка будут вычеркнуты все числа кроме одного, останется число с номером J(n), которое равно 2J(n) 1.

5.76. г) Пусть n = (ns... n1 n0 )2, где ns = 1. Тогда у одного из чисел m1, m2,..., ml в s-м разряде также стоит единица. Если mj — одно из таких чисел, то mj n < mj.

5.77. а) Если n равнялось 0 и одно из чисел m1, m2,..., ml изменилось, то изменится и число n. Оно станет равно количеству взятых камней, отличному от нуля.

б) Согласно задаче 5.76 г), для некоторого j (1 j l) выполняется неравенство mj n < mj. Поэтому из j-й кучки можно взять mj (mj n) камней, что приведет к обнулению ним-суммы.

в) Игрок находится в проигрышной позиции, если перед его ходом n = 0. Все остальные позиции — выигрышные. Для того, чтобы выиграть в «Ним», нужно оставлять после своего хода проигрышную позицию.

г) Нужно сделать переход к позиции 1, 4, 5.

5.78. Можно, например положить f(A) = 3, f(B) = 5, f(A) = 6. Теперь остается заметить, что при слиянии амеб общая ним-сумма не меняется, а в начальный момент времени она равна 5 = f(B).

5.80. а) Игра «Шоколадка» сводится к игре «Ним» с 4 кучками камней. Например, позиция, изображенная на рисунке, соответствует такому набору камней: 2, 5, 1, 4 (2 ряда слева от отмеченной дольки, 5 — справа, 1 — снизу и 4 — сверху.

5.81. б) Пусть в кучках m1, m2,..., ml камней, и r1, r2,..., rl — остатки от деления чисел m1, m2,..., ml на 6. Положим — ним-сумма по модулю 6. Если в начальной позиции n = 0, то выигрывает второй игрок; во всех остальных случаях — первый. Исключение составляет случай (Рассмотрите этот случай отдельно.) Стратегия выигрыша первого игрока: если перед ходом первого игрока набор камней удовлетворяет равенствам 13.6, причем l нечетно, то ход надо делать так, чтобы новая ним-сумма n равнялась 1; если l четно и rl = 1, то забирается любой из камней, лежащих отдельно. Во всех остальных случаях ход надо делать так, чтобы n = 0. Если это невозможно, то первый игрок проигрывает.

5.83. Сначала следует сравнить 1-ю и 2-ю монеты, затем 1-ю и 4-ю.

5.84. Во-первых, специальным образом пронумеруем монеты: присвоим им трехзначные номера 001, 010, 011, 012, 112, 120, 121, 122, 200, 201, 202, 220.

Для первого взвешивания положим на одну чашу весов те монеты, у которых старший разряд равен 0 (то есть 001, 010, 011, 012), а на другую - те монеты, у которых он равен 2 (200, 201, 202, 220). Если перетянет чашка с «0», запишем на бумажке цифру 0. Если перетянет «2»— запишем 2. Если чаши весов останутся в равновесии — запишем 1.

Для второго взвешивания на одну чашу выложим монеты 001, 200, 201, 202 (то есть все те монеты, у которых второй разряд равен 0), а на другую — 120, 121, 122, 220 (то есть те монеты, у которых средний разряд равен 2). Запишем результат взвешивания таким же образом, что и при первом взвешивании.

Третьим взвешиванием сравниваем 010, 020, 200, 220 с 012, 112, 122, 202 (соответственно, нули и двойки в младшем разряде) и записываем третью цифру.

Мы получили три цифры — иначе говоря, трехзначное число. Далее определяем фальшивую монету по следующему рецепту:

Если это число совпадает с номером какой-то монеты, то эта монета фальшивая и тяжелее остальных. Если нет, то заменим в этом числе все нули на двойки, а все двойки на нули. После этого оно должно совпасть с номером какой-то монеты. Эта монета фальшивая и легче остальных.

5.85. Нужно присвоить 13-й монете номер 111 и не использовать ее при взвешиваниях. К остальным монетам следует применить алгоритм из задачи 5.84.

Глава 6.5. Наибольшее значение суммы квадратов корней — 18. Это значение достигается при a = 3.

6.7. Воспользуйтесь теоремой Виета. Ответ: 5/2, 3/2.

6.8. (p, q) = (0, 0), (1, 2), (1/2, 1/2).

6.9. Воспользуйтесь теоремой Виета. Ответ: p = 2/3, q = 8/3.

6.11. Все такие точки образуют прямую y = 1/8.

6.12. Все окружности проходят через точку D(0; 1).

6.13. b = 1/10.

6.15. Рассмотрите разность данных многочленов. Ответ: a = 2.

6.17. Все точки, удовлетворяющие условию задачи лежат под параболой y = 4x 2x2. Ответ: y < 4x 2x2.

6.20. а) Найдите дискриминант этого уравнения и воспользуйтесь неравенством из задачи 10.7. б) Воспользуйтесь неравенством из задачи 10.12.

6.21. Квадратные трехчлены, не имеющие корней, соответствуют внутренности дискриминантной параболы.

6.28. Условие задачи равносильно тому, что указанная функция в точке = 1 принимает отрицательное значение. Отсюда a (2 11;

6.31.

6.33.

6.35.

6.37. В задаче нудно найти те x, для которых функция хотябы при одном a [1; 2] принимает отрицательное значение. Решим сначала обратную задачу, т. е. найдём те x, для которых так как график функций f(a) — это парабола, ветви которой направлены вниз, тоусловие () равносильно системе Последняя система после преобразований принимает вид Методом интервлов находим, что x [2, 0] {1}. Значит, решением исходной задчи будет множество (, 2) (0, 1) (1, +).

6.38. Пусть после деления P(x) на x c получился остаток r:

Подставляя сюда x = c, приходим к равенству r = P(c).

6.40. Нет.

6.42. Так как то Q(x) содержит только четные степени x и Q( x) — многочлен степени n. Кроме этого Q( x2 ) = P(xk )P(xk ) = 0, поэтому все числа x2, x2,..., x2 являются корнями Q( x).

6.44. Согласно теореме Безу, остаток равен P(2) = 3.

6.45. Согласно теореме Безу, остаток от деления P(x) на x + 1 равен P(1) = a + 10. Он будет равен 0 при a = 10.

6.46. а) Остаток равен P(1) = 5.

б) Остаток будет многочленом не выше первой степени. Подставляя в равенство значения x = 1, x = 1, находим a = 5, b = 0. Ответ: 5x.

6.47. Достаточно проверить, что P(0) = 0, P(1) = 0, P(1/2) = 0.

6.48. Запишем остаток R(x) от деления P(x) на (x 1)(x 2) в виде R(x) = ax + b. По теореме Безу P(1) = 2, P(2) = 1. Отсюда a = 1, b = 3. Ответ: R(x) = 3 x.

6.50. Нужно выяснить, при каких n функция будет многочленом относительно x. По теореме Безу, для этого необходимо и достаточно, чтобы число 1 было корнем многочлена xn + 1.

Отсюда n — нечетное число.

6.51. Докажите утверждение индукцией по n.

6.52. а) Сумма всех коэффициентов равна P(1) = 1.

б) Сумма коэффициентов при нечетных степенях находится по формуле Аналогично, сумма коэффициентов при четных степенях равна 6.53. Чтобы многочлен P(x) делился на x2 3x + 2 = (x 1)(x 2) необходимо и достаточно выполнение двух условий P(1) = 0 и P(2) = 0.

Первое условие дает (a + 1)(b + 1) = 0. Отсюда либо a = 1, либо b = 1. Если a = 1, то из второго условия b = 31/28. При b = аналогично находим a = 31/28. Ответ: (1, 31/28), (31/28, 1).

6.55. Повторяя рассуждения задачи 6.46, находим что R(x) = = [x(1 (1)n ) + 7 + (1)n ]/2.

6.56. Корни — 1, 2, 3.

= (x2 2ix 1)(x2 + 2ix 1). Из этих разложений подходит только одно — второе.

6.59. Равенство P(1) = 0 равносильно уравнению a3 4a + 3 = 0.

6.63. Рассмотрите многочлен f(x).

6.69. Смотрите решение задачи 3.54. Ответ: x(m,n) 1.

6.70. Положим Это многочлен с целыми коэффициентами, причем am = Pm (a0 ) и am = = Pmk (ak ) при m k. Так как Pn (x) = an +x Qn (x), где Qn (x) — также многочлен с целыми коэффициентами, то при m k (am, ak ) = (Pmk (ak ), ak ) = (amk + ak Qn (ak ), ak ) = (amk, ak ).

Далее остается повторить рассуждения из решения задачи 3. 6.71. x = 1.

6.72. p = 3.

6.74. Пусть P(x) = ax + b, Q(x) = cx + d. Тогда, подставив эти величины в данное равенство, находим Так как это равенство должно быть тождественным, то Отсюда a = 4, b = 5, c = 4 и d = 11, то есть P(x) = 4x + 5, Q(x) = = 4x + 11.

6.78. Найдите коэффициенты частного по схеме Горнера.

6.81. P(x + 3) = 55 + 81x + 45x2 + 11x3 + x4.

6.82. а) (22x+x2 )(2+2x+x2 ); б) (1+2x)(1+x+x2 ); в) (1+x+x2 ) ж) 3(a+b)(a+c)(b+c); з) 5(xy)(xz)(yz)(x2 xy+y2 xzyz+z2 );

и) (a4a3 b+a2 b2ab3+b4 )(a4+a3 b+a2 b2+ab3+b4 ); к) (1+x)2 (1+3x+x2 );

л) (abc)(a+bc)(ab+c)(a+b+c); м) (2+x)(6+x)(10+8x+x2 ).

6.84. В случае, когда p2 4q < 0, выражение x2 + q/x2 + p после замены t = x + q/x может быть разложено как разность квадратов.

6.85. 5/3(a2 + b2 + c2 + ab + ac + bc).

6.86. Известно, что Докажем, что многочлен (x + y + z)m xm ym zm делится на x + y.

По теореме Безу, достаточно проверить, что он обращается в ноль при y = x. Действительно, (x x + z)m xm (x)m zm = 0. Делимость на x + z и y + z доказывается аналогично.

6.87. Разложите данное выражение на множители.

6.88. Если a + b = 0, то равенство является верным. Значит после приведения к общему знаменателю, числитель будет делиться на a + b.

Аналогично, он делится на a + c и b + c. После разложения числителя на множители, решение становится очевидным.

6.89. Подставьте в левую и в правую части равенства c = a b.

6.91. Согласно задаче 6.90, рациональными корнями уравнения x 17 = 0 могут быть только числа ±1 и ±17. Но они не являются корнями. Поэтому уравнение x2 17 = 0 вообще не имеет рациональных корней.

6.92. Воспользуйтесь тем, что число = cos 20 удовлетворяет уравнению которое не имеет рациональных корней.

6.98. Покажите, что (P(x), P (x)) = 1.

6.106. Можно, например, воспользоваться задачей 3.142.

6.108. 2.

6.109. Рассмотрите выражение (a x)(a y)(a z) = a3 a2 1 + 6.110. (0, 0, a), (0, a, 0), (a, 0, 0).

6.111. a = 9.

6.115. Для того, чтобы из отрезков с длинами x1, x2, x3 можно было составить треугольник, необходимо и достаточно, чтобы Выражая левую часть через p, q и r, приходим к неравенству p3 4pq+ + 8r > 0.

6.116. а) Докажите, что пары чисел x, y и u, v являются парами корней одного и того же квадратного уравнения. Из этого будет следовать, что числа x, y совпадают с числами u, v с точностью до перестановки.

6.119. Воспользуйтесь результатом задачи 6.107 е).

6.120. (c + d)(b + c + d) = ad.

6.123. Приведите разность данных уравнений к виду 6.124. В каждом из случаев нужно узнать, сколько корней имеют уравнения: один или три.

6.125. Подставьте в уравнение x = a, x = b, x = c.

6.128. f(x) = 1.

6.129. f(x) = y1 f1 (x) +... + yn fn (x). Если таких многочленов будет два, то их разность будет многочленом степени не выше n с n + действительным корнем, что невозможно.

6.130. Остатком будет многочлен R(x) степени 2, для которого выполняются равенства Явный вид этого многочлена выписывается при помощи задачи 6.129:

6.131. По теореме Безу остаток равен f(xi ) = yi.

6.133. 1 17 километров.

6.134. 2 14.

6.135. По трем точкам график квадратного трехчлена строится однозначно.

6.136, 6.137. Каждое равенство в системе можно интерпретировать как равенство нулю соответствующего многочлена в точках a, b и c.

6.138. Если f(x) — интерполяционный многочлен Лагранжа, то f(x) также будет интерполяционным многочленом Лагранжа. В силу единственности такого многочлена (см. задачу 6.129) f(x) = f(x).

6.139. Пусть многочлен P(x) таков, что P(0) = 1,..., P(n) = 3n.

Докажите, что тогда P(n + 1) < 3n+1.

6.140. Воспользуйтесь равенством 6.141. Рассмотрите функцию Глава 7.4. а) Длина стороны треугольника не превосходит суммы длин двух других его сторон. б) Длина стороны треугольника не меньше модуля разности двух других его сторон. в) Хорда короче дуги, которую она стягивает.

7.9. Окружность (x + 5/3) + (y 1) = (4/3).

7.11. В параллелограмме сумма квадратов диагоналей равна сумме квадратов сторон.

7.13. Домножьте равенство на сопряженное.

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

г) ±( 3/2 + i/ 2); д) ±(3 4i); е) ±((5 i)/ 2).

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

7.20. Выразим t через z:

Сначала найдем значения t, которые соответствуют точкам z, лежащим на единичной окружности. Пусть z = cos + i sin. Представим числа 1 z и 1 + z в тригонометрической форме:

Подставляя эти представления в формулу для t, находим, что t — действительное число: t = tg(/2). Обратные вычисления показывают, что выбирая t именно таким образом, мы получим все точки единичной окружности кроме точки z = 1.

7.21. Для того, чтобы построить график на отрезке [1; 1], представьте x в виде x = sin t (t [/2; /2]).

7.29. Сумма степеней равна 0, если s = kn, и равна n, если s = kn.

7.30. Рассмотрите действительную и мнимую части первой формулы Муавра.

7.31. Представьте каждое из чисел в тригонометрической форме.

7.34. а) 1/2; 1/8.

7.35. а) Проверьте, что P(i) = P(i) = 0 и примените теорему Безу.

б) Как и в пункте а), достаточно проверить, что Q((cos ± sin )) = 0.

7.37. Смотрите приложение В, V.

7.39. Найдите рекуррентное соотношение, которому удовлетворяют многочлены 2Tn (x/2).

7.40. Пусть = m/n. Тогда cos(360n) = 1. Так как cos(360n) = = T360n (cos ), то получаем, что многочлен T360n (x) 1 обращается в ноль при x = cos = 1/3. Значит многочлен f(x) = 2T360n (x/2) имеет корнем число x = 2/3. Согласно задаче 7.39, многочлен f(x) имеет старший коэффициент равный 1, а остальные его коэффициенты — целые числа. Но, по теореме о рациональных корнях многочлена f(x) может иметь только целые корни.

7.41. Рассмотрите многочлен T360q (x) 1.

7.44. Pn (x) = 2Tn (x/2), где Tn (x) — многочлен Чебышёва.

7.45. Замените тангенс на отношение синуса к косинусу.

7.46. Перейдите в равенстве z + z1 = 2 cos к сопряженным числам и вычислите z.

7.47. Поскольку в многочлены Чебышёва удобно подставлять числа вида x = cos, то для решения задачи следует воспользоваться равенством sin = cos( /2). Ответ: Если n = 2k, то Если n = 2k + 1, то 7.49. Если f(z) = 0, то f(z) = f(z) = 0.

7.50. Комплексные корни многочлена можно разбить на пары взаимно сопряженных чисел. При этом произведение соответствующих линейных сомножителей даст квадратный трехчлен с действительными коэффициентами:

будет стремится к ea :

и найдем второй предел. Заметим, что Теперь нужный предел находится по формуле Муавра:

7.52. Воспользуйтесь формулой Эйлера из задачи 7.51.

7.54. На комплексной плоскости функция ln z становится многозначной. Если z = |z|ei, то в качестве ln z можно брать любое из чисел Для каждого из них 7.55. az = ez ln a, где экспонента определяется как в задаче 7.51, а логарифм — как в задаче 7.54.

7.56. Корень i-й степени из числа z = ei = e(+2k)i равен e+2k, где k — произвольное целое число. При z = 1 получаем i 1 = e(1+2k).

Значение корня, приведенное в задаче, соответствует k = 0.

7.61. а) 250 ; б) 249.

7.67. а) Все векторы z1,..., zn имеют положительную проекцию на луч arg z = + /2.

б) Все числа z1,..., z1 лежат в полуплоскости < arg z < 7.69. Если точка z лежит вне треугольника abc, то векторы z a, z b, z c располагаются в некоторой полуплоскости. Сумма их обратных величин не может равняться нулю согласно задаче 7.67, п. б).

и результатом задачи 7.69.

7.72. а) n 1, 2 (mod 3); б) n ±1 (mod 6).

7.74. а) n = 6k ± 2; б) n = 6k 2; в) ни при каких.

7.75. а) n = 6k ± 1; б) n = 6k + 1; в) ни при каких.

7.76. Если x = 1 — корень многочлена P(xn ), то его корнем будет любое из чисел xk = cos(2k/n)+i sin(2k/n) (k = 0,..., n1). Поэтому P(xn ) делится на (x x0 )... (x xn1 ) = xn 1.

7.77. 7.

нахождения суммы квадратов корней раскроем в уравнении скобки по формуле бинома Ньютона и сделаем сокращения:

По теореме Виета Далее, применяя результат задачи 6.107, д), находим 7.81. Воспользуйтесь тем, что 0 < (см. задачу 10.44) и результатом задачи 7.80.

7.82. Многочлен P(x) не имеет действительных корней, поэтому все его корни разбиваются на пары комплексно сопряженных чисел z1, z1,. .., zn, zn (см. задачу 7.49). Пусть Тогда Отсюда P(x) = a2 (x) + b2 (x).

7.85. а) Параллельный перенос на вектор a; б) гомотетия с центром в начале координат и коэффициентом 2; в) поворот против часовой стрелки на угол вокруг начала координат.

7.89. Композиция гомотетий имеет вид Если k1 · k2 = 1, то получаем параллельный перенос. Если же k1 · k2 = 1, то это гомотетия с коэффициентом k1 · k2, центр A которой находится из уравнения 7.93. а) Воспользуйтесь задачей 7.58, а); б) Воспользуйтесь задачей 7.58, б); в) Воспользуйтесь задачей 8.41, а) – б).

7.96. Формулу (7.1) можно переписать в виде Глава 8.1. Сумма векторов, направленных из центра правильного n-угольника в его вершины, сохраняется при повороте на угол, поэтому она может быть только нулевым вектором.

8.2. а) Воспользуйтесь результатом задачи 8.1 для правильного пятиугольника, вписанного в единичную окружность.

б) Рассмотрим правильный семиугольник A1 A2... A7. Пусть M — точка пересечения диагоналей A1 A4 и A2 A5. Равенство задачи следует из подобия треугольников A1 MA5 и A2 A3 A4.

в) Воспользуйтесь результатом задачи 8.1 для правильного двенадцатиугольника, вписанного в единичную окружность.

8.7. Рассмотрите на координатной плоскости треугольник OAB, вписанный в прямоугольник OKLM, где O(0, 0), A(1, 2), B(3, 1), K(0, 2), L(3, 2), M(3, 0).

8.8. Рассмотрите равнобедренный треугольник с углом 30 при вершине.

8.9. Сделайте замены x = p a, y = p b, z = p c. Ответ: 2.

8.10. Раскройте скобки в формуле Герона. Ответ: 3 · 54 S 3 · 84.

8.11. xk = 8.12. Система приобретает геометрический смысл, если положить 8.13. Равенство x2 + xy + y2 = a2 можно трактовать как теорему косинусов в треугольнике со сторонами x, y, a и углом 120. Ответ:

8.14. а) Часть прямой, проходящей через точки z1 и z2, расположенная вне отрезка [z1 ; z2 ]. б) Внутренность отрезка, соединяющего точки z1 и z2.

8.21. W(z1, z2, z3, z4 ) = W(z1, z2, z3, z4 ).

8.28. A = Aa + Ba Ba + Cc, B = Aab + Bad Bcb + Ccd, C = Abb 8.38. а) 3/16; б) 1/16.

8.40. Сделайте умножение на sin a.

8.45. Из данных соотношений находим:

Отсюда 8.46. а) Воспользуйтесь равенствами sin 15 = sin(45 30 ) и cos 15 = cos(45 30 ); б) Воспользуйтесь результатом задачи 8.4.

8.47. Воспользуйтесь равенствами sin 6 = sin(60 54 ) и sin 54 = = cos 36.

8.48. а) На первом шаге нужно применить формулы для суммы и разности синусов к величинам sin + sin и sin sin( + + ).

б) Решается аналогично предыдущему пункту.

8.49. Сумма tg + tg + tg приводится к виду 8.51. Воспользуйтесь равенством а) из задачи 8.48.

8.55.

8.58. Наибольшее значение — 1, наименьшее — 1/4.

8.59. Воспользуйтесь равенством 8.65. а) Пусть y = arcsin x (/2 x /2). Тогда sin y = x, cos y = = 1 sin2 y = 1 x2, причем перед корнем выбирается знак плюс, так как cos y 0. Остальные формулы доказываются аналогично.

8.66. На основании определения имеем:

Отсюда Остается проверить равенство Для доказательства второго равенства достаточно заметить, что и найти 8.69. Прежде всего нетрудно показать, что величины arctg x+arctg y и arctg отличаются друг от друга на, где — целое число.

Действительно, Так как то может принимать лишь три значения 0 и ±1. Для нахождения рассмотрите косинусы левой и правой частей исходного равенства.

8.70, 8.71 Воспользуйтесь формулой из задачи 8.69.

8.74. По формуле котангенса суммы Тем самым равенство (8.2) доказано. Суммируя его по n от 1 до, находим arcctg 2 + arcctg 5 + arcctg 13 +... + arcctg F2n+1 +... = arcctg 1 = /4.

в пределах 0 < 3/2 и sin = 0.

8.80. arcsin cos arcsin x + arccos sin arccos x = /2.

8.82. По формуле из задачии 8.69 2 arctg 1/5 = arctg 5/12. Ответ: 0.

8.83. Для доказательства соотношения a = b cos + c cos воспользуйтесь равенством Другие соотношения проверяются аналогично.

8.84. Из первых двух равенств системы (8.4) находим:

После подстановки этих равенств в третье уравнение системы, приходим к соотношению 8.86. Из первого равенства Отсюда Так как данные формулы переходят одна в другую при круговой перестановке переменных,,, A, B, C и от этого преобразования правая часть последнего равенства не меняется, то Так как все величины,,, A, B, C заключены в пределах от 0 до, Глава 9.2. После подстановки z = x +, коэффициент при x2 оказывается равен A + 3. Поэтому нужно выбрать = A/3.

9.3. а) Функция f(x) = x3 + px — нечетная, поэтому ее график симметричен относительно начала координат. б) График функции f(x) = = x3 + px + q получается из графика функции f(x) = x3 + px параллельным переносом, поэтому он также имеет центр симметрии. в) Из задачи 9.2 следует, что функция f(x) = ax3 + bx2 + cx + d может быть получена из функции f(x) = x3 + px + q линейной заменой переменной и умножением на число. Оба эти преобразования сохраняют свойство графика иметь центр симметрии.

9.5. Приведите уравнение к виду 2x3 + (x + 1)3 = 0.

9.6. Воспользуйтесь условиями x1 x2 +x1 x3 +x2 x3 = 0, x1 x2 x3 = b > 0.

9.7. Числа a и b должны удовлетворять системе уравнений Поэтому a3 и b3 можно найти как корни квадратного уравнения y2 + + qy p3 /27 = 0. То есть 9.8. Разложение выглядит следующим образом:

Здесь и 2 — кубические корни из 1:

кубические корни из 1 (смотрите задачу 9.8.) 9.10. Так как 9.11. Формула Кардано получается, если воспользоваться ответом задачи 9.7 и формулой для корня x1 из задачи 9.9. Для того, чтобы найти два других корня, заметим, что при нахождении чисел a и b кубический корень можно извлечь тремя способами. Всего получается 9 комбинаций x вида x = a + b, но только три из них будут корнями, поскольку a и b связаны условием a · b = p/3. Если в качестве a и b взять пару чисел из решения задачи 9.7, то кроме корня x1 = a + b, исходное кубическое уравнение будет иметь корни x2 = a + 2 b и x3 = 2 a + b, где — кубический корень из 1.

9.12. Подбором находим корень x0 = 1. Так как то других действительных корней нет. Поэтому формула Кардано дает корень x0 = 1:

9.13. x3 + 3/4x 7/4, = 1.

9.15. По формуле Кардано находим корень x1 = 2/ 3. После деления столбиком, приходим к равенству Полученный квадратный трехчлен оказывается полным квадратом.

В итоге получается, что уравнение имеет три действительных корня, два из которых совпадают. Ответ: x1 = 2/ 3, x2 = x3 = 1/ 3.

9.16. Воспользуйтесь равенством x1 + x2 + x3 = 0.

9.17. D(x3 + px + q) = 4p3 27q2.

9.18. Решение непосредственно следует из результата задачи 9.17.

9.27. Вычитая из одного уравнения другое, находим Умножая первое уравнение на q, а второе на q и вычитая почленно, будем иметь Исключая теперь из уравнений (13.7) и (13.8) переменную x, получим искомый результат.