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

4.190. С помощью признака делимости Паскаля установите признаки делимости на числа 3, 9, 6, 8, 12, 15, 11, 7, 27, 37.

Иногда в качестве ri удобнее брать не остаток, а «недостаток», то есть такое наибольшее неположительное число, что 10i ri (mod m).

4.191. Опишите все системы счисления, в которых число делится на 2 тогда и только тогда, когда сумма его цифр делится на 2. Решите задачу, заменив модуль 2 произвольным натуральным числом m > 1.

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

1) число делится на 5 тогда и только тогда, когда сумма его цифр делится на 5;

2) число делится на 7 тогда и только тогда, когда число, составленное из двух его последних цифр, делится на 7.

4.193. Докажите, что если необходимый и достаточный признак делимости, выражающийся через свойства цифр числа, не зависит от порядка цифр, то это признак делимости на 3 или на 9.

4.193. Установите признаки делимости на а) 2, б) 3, в) 5, для чисел, записанных в фибоначчевой системе счисления.

6. Китайская теорема об остатках Китайская теорема об остатках. Пусть целые числа m1,..., mn попарно взаимно просты, то есть (mi, mj ) = 1 при i = j, m = m1... mn, и a1,..., an, A — произвольные целые числа. Тогда существует ровно одно целое число x такое, что и A x < A + m. (См. также 6.51.) Одним из важнейших применений китайской теоремы об остатках является система счисления в остатках. В ней целое число представляется набором его остатков (или вычетов) по взаимно простым модулям. В такой системе счисления операции с числами сводятся к операциям с их остатками.

4.194. При каких целых n число an = n2 + 3n + 1 делится на 55?

4.195. Найдите остатки от деления:

а) 1910 на 66; б) 1914 на 70; в) 179 на 48; г) 1414 на 100.

4.196. Натуральные числа m1,..., mn попарно взаимно просты.

Докажите, что сравнение равносильно системе 4.197. Натуральные числа m1,..., mn попарно взаимно просты. Докажите, что число x = (m2 m3... mn )(m1 ) является решением системы 4.198. Пользуясь результатом предыдущей задачи, укажите в явном виде число x, которое удовлетворяет системе (4.3).

4.199. Докажите китайскую теорему об остатках.

4.200. Укажите все целые числа x, удовлетворяющие системам:

4.201. Найдите наименьшее натуральное число, дающее при делении на 2, 3, 5, 7 остатки 1, 2, 4, 6 соответственно.

4.202. На столе лежат книги, которые надо упаковать. Если их связать в одинаковые пачки по 4, по 5 или по 6 книг, то каждый раз останется одна лишняя книга, а если связать по 7 книг в пачку, то лишних книг не останется. Какое наименьшее количество книг может быть на столе?

4.203. Найдите остаток от деления числа 1000! на 10250.

4.204. Найдите наименьшее четное натуральное число a такое, что на 13.

4.205. Пусть натуральные числа m1, m2,..., mn попарно взаимно просты. Докажите, что если числа x1, x2,..., xn пробегают полные системы вычетов по модулям m1, m2,..., mn соответственно, то число пробегает полную систему вычетов по модулю m1 m2... mn. Выведите отсюда китайскую теорему об остатках.

4.206. Китайская теорема об остатках и функция Эйлера.

Докажите, что число x является элементом приведенной системы вычетов тогда и только тогда, когда числа a1,..., an, определенные сравнениями (4.3) принадлежат приведенным системам вычетов по модулям m1,..., mn соответственно. Выведите отсюда мультипликативность функции Эйлера.

4.207. Предположим, что числа m1,..., mn попарно взаимно проc сты. Докажите, что любую правильную дробь вида можно представить в виде алгебраической суммы правильных дробей вида ni /mi (y = 1,..., n).

4.208. Какие цифры надо поставить вместо звездочек, чтобы число 454 делилось на 2, 7 и 9?

4.209. Найдите наименьшее натуральное число, половина которого — квадрат, треть — куб, а пятая часть — пятая степень.

4.210. Числа-автоморфы. а) Трехзначное число 625 обладает своеобразным свойством самовоспроизводимости, как то:

Сколько четырехзначных чисел удовлетворяют уравнению б) Докажите, что при любом k существует ровно 4 набора из k цифр — 00... 00, 00... 01 и еще два, оканчивающиеся пятеркой и шестеркой, — обладающие таким свойством: если натуральное число оканчивается одним из этих наборов цифр, то его квадрат оканчивается тем же набором цифр.

4.211. Больное войско. Генерал хочет построить для парада своих солдат в одинаковые квадратные каре, но он не знает сколько солдат (от 1 до 37) находится в лазарете. Докажите, что у генерала может быть такое количество солдат, что он, независимо от заполнения лазарета, сумеет выполнить свое намерение.

Например, войско из 9 человек можно поставить в виде квадрата 3 3, а если один человек болен, то в виде двух квадратов 2 2.

4.212. Восточный Календарь. В китайской натурфилософии выделяются пять первоэлементов природы — дерево, огонь, металл, вода и земля, которым соответствуют пять цветов — синий (или зеленый), красный, белый, черный и желтый. В восточном календаре с древних времен используется 12-летний животный цикл так, что каждому из годов в цикле соответствует одно из животных. Кроме того, каждый год проходит под покровительством одной из стихий и окрашивается в один из цветов:

годы, оканчивающиеся на 0 и 1 — годы металла (цвет белый);

годы, оканчивающиеся на 2 и 3 — это годы воды (цвет черный);

годы, оканчивающиеся на 4 и 5 — годы дерева (цвет синий);

годы, оканчивающиеся на 6 и 7 — годы огня (цвет красный);

годы, оканчивающиеся на 8 и 9 — годы земли (цвет желтый).

В 60-летнем календарном цикле каждое животное возникает 5 раз.

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

1. Рациональные и иррациональные числа Определение. Число называется рациональным, если оно представимо в виде = m/n, где m — некоторое целое, а n — натуральное числа. Все остальные действительные числа называются иррациональными. Множество всех рациональных чисел обозначается через Q. Два числа называются несоизмеримыми, если их отношение иррационально.

Определение. Десятичная дробь где b1 b2... bn — наименьший по длине отрезок цифр, повторяющийся начиная с некоторого места, называется периодической десятичной дробью. При том набор цифр b1 b2... bn называется периодом, набор a1 a2... ak — предпериодом, n — длиной периода и дробь записывается в виде 5.1. Представьте следующие рациональные числа в виде десятичных дробей:

5.2. Найдите цифры a и b такие, для которых 5.3. Найдите период дроби Как можно объяснить тот факт, что после запятой появляются степени числа 2?

5.4. Число Фейнмана. Объясните поведение следующей десятичной дроби и найдите ее период:

5.5. Представьте следующие числа в виде обычных и в виде десятичных дробей:

а) 0,(12) + 0,(122); б) 0,(3) · 0,(4); в) 0,(9) 0,(85).

5.6. Докажите, что число рационально тогда и только тогда, когда оно представляется конечной или периодической десятичной дробью.

5.7. Для каких натуральных n число представляется конечной десятичной дробью?

5.8. Пусть число задается десятичной дробью а) = 0,101001000100001000001... ;

б) = 0,123456789101112131415...

Будет ли это число рациональным?

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

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

5.11. Найдите все такие натуральные n, для которых и представляется конечными десятичными дробями.

5.12. Докажите, что среди чисел [2k 2] (k = 0, 1,... ) бесконечно много составных.

5.13. Докажите иррациональность следующих чисел:

5.14. Метод спуска. Докажите, что уравнения а) 8x4 + 4y4 + 2z4 = t4 ; в) x2 + y2 + z2 + u2 = 2xyzu;

не имеют решений в натуральных числах.

5.15. Докажите, что уравнение x3 + x2 y + y3 = 0 не имеет рациональных решений кроме (0; 0).

5.16. Может ли а) сумма двух рациональных чисел быть иррациональной?

б) сумма двух иррациональных чисел быть рациональной?

в) иррациональное число в иррациональной степени быть рациональным?

5.17. Один из корней уравнения x2 +ax+b = 0 равен 1+ 3. Найдите a и b, если известно, что они рациональны.

5.18.

Пусть a, b, c — различные простые числа. Докажите, что числа a, b, c не могут быть членами одной арифметической прогрессии.

5.19. Упростите выражение:

5.20. Докажите равенство 5.21. Найдите первые 17 знаков в десятичной записи у чисел:

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

5.23. Задача Бхаскары. Упростите выражение 5.24. Формула сложного радикала. Докажите равенство:

(См. также 7.15.) иррационально.

5.26. При каких натуральных a и b число loga b будет рациональным?

5.27. Докажите, что sin x и cos x рациональны тогда и только тогда, когда число tg(x/2) рационально.

5.28. Дана квадратная сетка на плоскости и треугольник с вершинами в узлах сетки. Докажите, что тангенс любого угла в треугольнике — число рациональное.

5.29. Можно ли нарисовать правильный треугольник с вершинами в узлах квадратной сетки?

5.30. Дан лист клетчатой бумаги. Докажите, что при n = 4 не существует правильного n-угольника с вершинами в узлах решетки.

5.31. Докажите, что на окружности с центром в точке ( 2; 3) лежит не более одной точки целочисленной решетки.

5.32. Избавьтесь от иррациональности в знаменателе:

5.33. При каких натуральных n число ( 2 + 1)n ( 2 1)n будет целым?

5.34. Докажите следующие равенства:

5.35. Иррациональность числа e. Число e определяется равенством e = lim (1 + 1/n)n. Докажите, что а) e = lim (2 + 1/2! + 1/3! +... + 1/n!);

в) e — иррациональное число.

(См. также 11.73, 7.51).

5.36*. Число e и комбинаторика. Дано N точек, никакие три из которых не лежат на одной прямой. Каждые две из этих точек соединены отрезком, и каждый отрезок окрашен в один из k цветов.

Докажите, что если N > [k! e], то среди данных точек можно выбрать такие три, что все стороны образованного ими треугольника будут окрашены в один цвет. (См. также 2.33.) 5.37*. Определим последовательности чисел {xn } и {dn } условиями Докажите, что число 2 в двоичной системе счисления представляется в виде 2 = (d1, d2 d3... )2. (Двоичную запись числа 2 можно найти в приложении В.) 2. Десятичные дроби Разложение рациональных чисел в десятичные дроби непосредственно связано со специальными числами, называемыми репьюнитами.

Определение. Репьюнитом порядка n называется число, состоящее из n единиц En = 11... 1.

Репьюниты существуют не только в десятичной системе счисления.

Но в других системах счисления они уже не будут связаны с десятичными дробями.

5.38. Докажите, что равенство равносильно тому, что десятичное представление дроби 1/m имеет вид 1/m = 0, (a1 a2... an ).

5.39. Докажите, что если (m, 10) = 1, то существует репьюнит En, делящийся на m. Будет ли их бесконечно много?

5.40. Как связаны между собой десятичные представления чисел {p/q} и {10k p/q}?

5.41. Докажите, что если (m, 10) = 1, то у десятичного представления дроби 1/m нет предпериода.

Определение. Если у десятичной дроби отсутствует предпериод, то такая дробь называется чисто периодической.

5.42. Найдите возможные значения знаменателя обычной дроби вида 1/m, которая представляется чисто периодической десятичной дробью с двумя цифрами в периоде.

5.43. Пусть (n, 10) = 1, m < n, (m, n) = 1, и t — наименьшее число такое, что 10t 1. n. Докажите, что t кратно длине периода дроби m/n. Будет ли это длина периода?

5.44. Докажите, что если (m, 10) = 1, то частное 9En /m, записанное как n-значное число (возможно с нулями в начале) состоит из нескольких периодов десятичного представления дроби 1/m. Кроме того, если еще выполнены условия (m, 3) = 1 и En — первый репьюнит, делящийся на m, то число 9En /m будет совпадать с периодом.

5.45. Докажите, что если (m, 30) = 1, то число, состоящее из цифр периода дроби 1/m делится на 9.

5.46*. Эффект девяток. Периодом дроби 1/7 является число N = = 142857. Оно обладает следующим свойством: сумма двух половин периода — число из одних девяток (142 + 857 = 999). Докажите в общем случае, что для простого q > 5 и натурального p < q период дроби p/q есть 2n-значное число N = N1 N2 такое, что N1 + N2 = 99... 9.

5.47*. Загадочное число. Число N = 142857 обладает и рядом других свойств. Например: 2 · 142 857 = 285 714, 3 · 142 857 = 428 571..., то есть при умножении на 1, 2, 3,..., 6 цифры циклически переставляются; 14 + 28 + 57 = 99; N2 = 20408122449, 20408 + 122449 = 142857 = N.

Аналогичные операции можно проделывать и с другими периодами дробей. Что получается для чисел 1/17, 1/19? Объясните эти факты.

5.48. Обозначим через L(m) длину периода дроби 1/m. Докажите, что если (m, 10) = 1, то L(m) является делителем числа (m).

5.49. Пусть (m, n) = 1. Докажите, что сумма длин периода и предпериода десятичного представления дроби m/n не превосходит (m).

5.50. Докажите, что если (m1, 10) = 1 и (m2, 10) = 1, то справедливо равенство L(m1 m2 ) = [L(m1 ), L(m2 )]. Чему равна длина периода дроби 1/m1 + 1/m2 ?

5.51. Найдите все шестизначные числа, которые уменьшаются втрое при перенесении последней цифры на первое место.

5.52. Найдите все шестизначные числа, которые увеличиваются в целое число раз при перенесении последней цифры в начало.

5.53. Докажите, что не существует целых чисел, которые от перестановки начальной цифры в конец увеличивались бы в 5, 6 или 8 раз.

5.54. Пусть число m имеет вид m = 2a 5b m1, где (10, m1 ) = 1.

Положим k = max(a, b). Докажите, что период дроби 1/m начинается с (k+1)-й позиции после запятой, и имеет такую же длину, как и период дроби 1/m1.

5.55*. Найдите последние три цифры периодов дробей 1/107, 1/131, 1/151. (Это можно сделать, не считая предыдущих цифр.) 3. Двоичная и троичная системы счисления 5.56. Имеются весы с двумя чашами и по одной гире в 1 грамм, 3 грамма, 9 грамм, 27 грамм и 81 грамм. Как уравновесить груз в 61 грамм, положенный на чашу весов?

5.57. Дан мешок сахарного песка, чашечные весы и гирька в 1 г.

Можно ли за 10 взвешиваний отмерить 1 кг сахара?

5.58. Летела стая гусей. На каждом озере садилась половина гусей и еще пол-гуся. Остальные летели дальше. Все гуси сели на n озерах.

Сколько всего гусей было в стае?

5.59. Имеются 4 гири и двухчашечные весы без стрелки. Сколько всего различных по весу грузов можно точно взвесить этими гирями если а) гири можно класть только на одну чашку весов;

б) гири можно класть на обе чашки весов?

5.60. Вы имеете право сделать 4 гири любого веса. Какие это должны быть гири, чтобы на весах из предыдущей задачи можно было взвесить грузы от 1 до 40 кг?

5.61. а) Имеются две веревки. Если любую из них поджечь с одного конца, то она сгорит за час. Веревки горят неравномерно. Например, нельзя гарантировать, что половина веревки сгорает за 30 минут. Как, имея две такие веревки, отмерить промежуток времени в 15 минут?

б) Сколько промежутков времени (считая нулевой) можно отмерить, имея три такие веревки?

5.62. а) У одного человека был подвал, освещавшийся тремя электрическими лампочками. Выключатели этих лампочек находились вне подвала, так что включив любой из выключателей, хозяин должен был спуститься в подвал, чтобы увидеть, какая именно лампочка зажглась.

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

б) Сколько лампочек и выключателей можно идентифицировать друг с другом, если разрешается 2 раза спуститься в подвал?

5.63. С числом разрешается производить две операции: «увеличить в два раза» и «увеличить на 1». За какое наименьшее число операций можно из числа 0 получить а) число 100; б) число n? (См. также 6.77.) 5.64. Бинарный метод возведения в степень. Предположим, что необходимо возвести число x в степень n. Если, например, n = 16, то это можно сделать выполнив 15 умножений x16 = x · x ·... · x, а можно обойтись лишь четырьмя:

Пусть Придумайте алгоритм, который позволял бы вычислять xn при помощи умножений, где (n) = r — число единиц в двоичном представлении числа n. (См. также 11.88.) 5.65. Пусть l(n) — наименьшее число умножений, необходимое для нахождения xn. На примере чисел n = 15 и n = 63 покажите, что бинарный метод возведения в степень не всегда оптимален, то есть для некоторых n выполняется неравенство l(n) < b(n).

5.66. Коля Васин задумал число от 1 до 31 включительно и выбрал из 5 данных карточек те, на которых это число присутствует. Как, зная эти карточки, угадать задуманное число? Какими должны быть карточки, чтобы по ним можно было угадывать числа от 1 до 63?

5.67. Карточный фокус. а) Берется колода из 27 карт (без одной масти). Ваш друг загадывает одну из карт. После чего вы раскладываете все карты в три равные кучки, кладя каждый раз по одной карте (в первую кучку, затем во вторую, затем в третью, потом снова в первую и т. д.). Ваш друг указывает на ту кучку, в которой лежит его карта.

Далее вы складываете все три кучки вместе, вставляя при этом указанную кучку между двумя другими. Эта процедура повторяется еще два раза. На каком месте в колоде окажется загаданная карта, после того, как вы сложите вместе три кучки в третий раз?

б) На каком месте окажется загаданная карта, если с самого начала было 3n (n < 9) карт?

5.68. Коля Васин задумал число: 1, 2 или 3. Вы задаете ему только один вопрос, на который он может ответить «да», «нет» или «не знаю».

Сможете ли вы угадать число, задав всего лишь один вопрос?

5.69. Коля Васин задумал число от 1 до 200. За какое наименьшее число вопросов вы сможете его отгадать, если он отвечает на каждый вопрос а) «да» или «нет»;

б) «да», «нет» или «не знаю»?

5.70*. Как и раньше загадывается число от 1 до 200, а загадавший отвечает на вопросы «да» или «нет». При этом ровно один раз (за все ответы) он имеет право соврать. Сколько теперь понадобится вопросов, чтобы отгадать задуманное число?

5.71. Докажите, что каждое целое число A представимо в виде где каждое из чисел ak = 0, 1 или 1 и ak ak+1 = 0 для всех 0 k n1, причем такое представление единственно.

5.72. Множество Кантора. Отрезок числовой оси от 0 до покрашен в зеленый цвет. Затем его средняя часть — интервал (1/3; 2/3) перекрашивается в красный цвет, потом средняя часть каждого из оставшихся зелеными отрезков тоже перекрашивается в красный цвет, с оставшимися зелеными отрезками проделывается та же операция и так до бесконечности. Точки, оставшиеся зелеными, образуют множество Кантора.

а) Найдите сумму длин красных интервалов.

б) Докажите, что число 1/4 останется окрашенным в зеленый цвет.

в) Из суммы произвольным образом вычеркнуты слагаемые. Докажите, что сумма оставшихся слагаемых — зеленое число.

г) Докажите, что всякое число x [0, 2] представимо в виде x = +, где и — элементы множества Кантора.

5.73. Последовательность Морса. Бесконечная последовательность из нулей и единиц построена по следующему правилу. Сначала написан нуль. Затем делается бесконечное количество шагов. На каждом шаге к уже написанному куску последовательности приписывается новый кусок той же длины, получаемый из него заменой всех нулей единицами, а единиц — нулями.

а) Какая цифра стоит на 2001 месте?

б) Будет ли эта последовательность, начиная с некоторого места, периодической?

в) Докажите, что данная последовательность переходит в себя при замене каждого нуля на комбинацию 01, а каждой единицы — на комбинацию 10.

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

д) Как, зная представление числа n в двоичной системе счисления, найти n-й элемент данной последовательности? (См. также 11.88.) 5.74. Ханойская башня и двоичная система счисления. Рассмотрим два процесса, каждый из которых состоит из 28 1 шагов.

Первый — это процесс решения головоломки «Ханойская башня» (см.

1.42) при помощи оптимального алгоритма. Второй — это процесс прибавления единицы, который начинается с 0 и заканчивается числом 28 1. Опишите связь между этими двумя процессами.

5.75. Задача Иосифа Флавия. n человек выстраиваются по кругу и нумеруются числами от 1 до n. Затем из них исключается каждый второй до тех пор, пока не останется только один человек. Например, если n = 10, то порядок исключения таков: 2, 4, 6, 8, 10, 3, 7, 1, 9, так что остается номер 5. Для данного n будем обозначать через J(n) номер последнего оставшегося человека. Докажите, что а) J(2n) = 2J(n) 1;

б) J(2n + 1) = 2J(n) + 1;

в) если n = (1bm1 bm2... b1 b0 )2, то J(n) = (bm1 bm2... b1 b0 1)2.

5.76. Ним-сумма. Будем говорить, что число n является ним-суммой чисел m и k (m k = n), если оно получается из чисел m и k после следующих преобразований.

1) m и k записываются в двоичной системе счисления (меньшее число дополняется спереди нулями).

2) Полученные наборы цифр как векторы складываются покомпонентно по модулю 2:

3) Набор цифр (ns,..., n1, n0 ) переводится в число n:

4=(100)2, 9=(111)2, (1, 0, 0) + (1, 1, 1)(0, 1, 1) (mod 2), (011)2 =3.

Докажите, что ним-сумма удовлетворяет следующим свойствам:

то найдется такой номер j (1 j 5.77. Игра «Ним». Имеется несколько кучек камней. Двое по очереди берут из них камни. За один ход разрешается взять любое (ненулевое) количество камней, но только из одной кучки. Выигрывает тот, кто взял последний камень.

Для анализа игры каждому набору кучек камней m1, m2,..., ml поставим в соответствие его ним сумму (5.1).

а) Докажите, что если игрок делает ход из позиции с нулевой ним-суммой, то в результате получается позиция с ним-суммой n = 0.

б) Докажите, что из позиции с ненулевой ним-суммой всегда можно сделать ход в позицию с ним-суммой n = 0.

в) Опишите выигрышную стратегию в игру «Ним».

г) Какой следует сделать ход, если перед вами три кучки: 3, 4 и камней?

5.78. Марсианские амебы II. При помощи ним-сумм можно исследовать самые разные игры и процессы. Например, можно получить еще одно решение задачи 4.20.

Постройте на множестве марсианских амеб {A, B, C} функцию f, для которой выполнялись бы равенства Какие рассуждения остается провести, чтобы решить задачу про амеб?

5.79. Игра «Йога» II. Проанализируйте при помощи ним-сумм игру «Йога» из задачи 4.21.

5.80. Игра «Шоколадка». Имеется шоколадка, состоящая из 6 8 = 48 долек. Одна из долек отмечена:

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

а) Опишите выигрышную стратегию в этой игре. Кто из игроков выиграет, если отмеченная долька располагается так, как показано на рисунке?

б) При каких размерах шоколадки начинающий игрок выигрывает при любом расположении отмеченной дольки?

в) При каких размерах шоколадки начинающий игрок проигрывает при любом расположении отмеченной дольки?

5.81. Имеется несколько кучек камней. Двое по очереди берут из них камни. За один ход разрешается взять из одной кучки от 1 до 5 камней.

Определите выигрышную стратегию в этой игре, если тот, кто взял последний камень а) выигрывает; б) проигрывает. (См. также 4.59.) 5.82*. Пешечное противостояние. На доске 3 n расставлены n черных и n белых пешек так, как показано на рисунке:

Пешки ходят и бьют по шахматным правилам, к которым добавляется одно: бить обязательно. Тот, кто не может сделать ход: а) выигрывает; б) проигрывает. Какой из игроков выигрывает в этой игре в зависимости от значения n?

5.83. 4 монеты. Из четырех монет одна фальшивая (она отличается по весу от настоящей, но не известно, в какую сторону). Требуется за два взвешивания на двухчашечных весах без гирь найти фальшивую монету.

5.84*. 12 монет. Из двенадцати монет одиннадцать настоящих, а одна фальшивая (она отличается по весу от настоящей, но не известно, в какую сторону). Требуется за три взвешивания на двухчашечных весах без гирь найти фальшивую монету и выяснить, легче она или тяжелее настоящей.

5.85*. 13 монет. Предположим теперь, что имеется 13 монет, из которых одна — фальшивая. Как за три взвешивания на двухчашечных весах без гирь найти фальшивую монету, если не требуется выяснять, легче она или тяжелее настоящей?

1. Квадратный трехчлен Теорема Виета для квадратного уравнения. Пусть x1, x2 — корни уравнения x2 + px + q = 0. Тогда справедливы равенства 6.1. Пусть x1, x2 — корни уравнения x2 + px + q = 0. Выразите через p и q следующие величины 6.2. Для многочленов f(x) = x2 + ax + b и g(y) = y2 + py + q с корнями x1, x2 и y1, y2 соответственно, выразите через a, b, p, q их результант, который определяется равенством Вычисление результанта позволяет проверить многочлены f(x) и g(y) на наличие у них общих корней.

6.3. Уравнение x2 + px + q = 0 имеет корни x1 и x2. Напишите уравнение, корнями которого будут числа y1, y2 равные:

6.4. Пусть x1, x2 — корни квадратного уравнения ax2 + bx + c = 0 и Sn = xn + xn (n 0). Докажите формулу 6.5. При каких значениях параметра a сумма квадратов корней уравнения является наибольшей? Чему равна эта сумма?

6.6. Какими должны быть p и q, чтобы выполнялось равенство 6.7. При каких значениях параметра a один из корней уравнения x2 x + a3 = 0 является квадратом другого?

6.8. Пусть f(x) = x2 +px+q. При каких p и q выполняются равенства f(p) = f(q) = 0?

6.9. При каких p и q уравнению x2 + px + q = 0 удовлетворяют два различных числа 2p и p + q?

6.10. При каких a уравнение имеет два различных корня?

6.11. Нарисуйте множество всех таких точек координатной плоскости, из которых к параболе y = 2x2 можно провести две перпендикулярные друг другу касательные.

6.12. Рассмотрим графики функций y = x2 + px + q, которые пересекают оси координат в трех различных точках. Докажите, что все окружности, описанные около треугольников с вершинами в этих точках, имеют общую точку.

6.13. Известно, что уравнение x2 + 5bx + c = 0 имеет корни x1 и x2, x1 = x2, а некоторое число является корнем уравнения y2 +2x1 y+2x2 = и корнем уравнения z2 + 2x2 z + 2x1 = 0. Найти b.

6.14. Известно, что многочлены ax2 + bx + c и bx2 + cx + a (a = 0) имеют общий корень. Найдите его.

6.15. При каких a уравнения x2 + ax + 1 = 0 и x2 + x + a = 0 имеют хотя бы один общий корень?

6.16. Пусть — корень уравнения x2 + px + q = 0, а — уравнения x px q = 0. Докажите, что между и лежит корень уравнения x2 2px 2q = 0.

6.17. Укажите все точки плоскости (x; y), через которые не проходит ни одна из кривых семейства 6.18. Укажите все точки плоскости (x; y), через которые не проходит хотя бы одна кривая семейства 6.19. Изобразите ту часть плоскости (x; y), которая накрывается всевозможными кругами вида 6.20. Докажите, что корни уравнения — всегда вещественные.

Определение. Каждому квадратному трехчлену x2 + px + q будем ставить в соответствие на координатной плоскости Opq точку с координатами (p; q). Эту плоскость назовем фазовой. Прямые вида a2 + ap + q = 0 будем называть корневыми, а параболу p2 4q = 0 — дискриминантной.

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

6.22. Для каждого действительного a построим на плоскости Opq корневую прямую a2 +ap+q = 0. Докажите, что полученное множество прямых совпадает с множеством всех касательных к дискриминантной параболе p2 4q = 0. (См. также 9.20.) 6.23. Обозначим корни уравнения x2 + px + q = 0 через x1, x2. Нарисуйте на фазовой плоскости Opq множества точек M(p; q), которые задаются условиями:

6.24. Найдите все значения параметра a, для каждого из которых уравнение 4x2 2x + a = 0 имеет два корня, причем x1 < 1, x2 > 1.

6.25. Найдите все такие q, что при любом p уравнение x2 +px+q = имеет два действительных корня.

6.26. Фазовая плоскость Opq разбивается параболой p2 4q = 0 и прямыми p + q + 1 = 0, 2p + q + 4 = 0 на несколько областей. Для точек каждой области укажите, сколько корней имеет соответствующий им многочлен x2 + px + q = 0 на интервале (2; 1).

6.27. На фазовой плоскости через точку (p; q) проведены касательные к дискриминантной параболе p2 4q = 0. Найдите координаты точек касания.

6.28. При каких значениях параметра a один из корней уравнения больше 1, а другой — меньше 1?

6.29. Известно, что модули корней уравнений x2 + ax + b = 0 и x + cx + d = 0 меньше 1. Докажите, что модули корней уравнения также меньше 1.

6.30. В квадратном уравнении x2 + px + q = 0 коэффициенты p и q независимо пробегают все значения от 1 до 1. Найдите множество значений, которые могут при этом принимать действительные корни этого уравнения.

6.31. При каких значениях параметра a оба корня уравнения (2 a)x2 3ax + 2a = 0 больше ?

6.32. При каких значениях параметра a оба корня уравнения (1 + a)x2 3ax + 4a = 0 больше 1?

6.33. При каких значениях параметра a уравнение (a 1)x 2(a + 1)x + 2(a + 1) = 0 имеет только одно неотрицательное решение?

6.34. При каком значении параметра m сумма квадратов корней уравнения x2 (m + 1)x + m 1 = 0 является наименьшей?

6.35. Найдите все значения параметра r, при которых уравнение (r 4)x2 2(r 3)x + r = 0 имеет два корня, причем каждый из которых больше 1.

6.36. Найдите все значения x, удовлетворяющие неравенству хотя бы при одном значении a [1; 2].

2. Алгоритм Евклида для многочленов и теорема Безу 6.37. Деление многочленов с остатком. Пусть P(x) и Q(x) — многочлены, причем Q(x) не равен нулю тождественно. Докажите, что существуют многочлены T (x) и R(x) такие, что и deg R(x) < deg Q(x); и покажите, что при этом T (x) и R(x) определяются однозначно.

Определение. Если многочлен P(x) поделен на Q(x) с остатком то T (x) называется неполным частным, а R(x) — остатком. Если многочлен R(x) тождественно равен нулю, то в этом случае T (x) — полное частное, и Q(x) называется делителем P(x) (Q(x) | P(x)).

6.38. Теорема Безу. Докажите, что остаток от деления многочлена P(x) на x c равен P(c).

6.39. Докажите, что многочлен степени n имеет не более чем n корней.

6.40. Можно ли из какой-то точки плоскости провести к графику многочлена n-й степени больше, чем n касательных?

6.41. Пусть x1, x2,..., xn — корни уравнения an xn +...+a1 x+a0 = 0.

Какие корни будут у уравнений 6.42. Пусть многочлен имеет корни x1, x2,..., xn, то есть Рассмотрим многочлен Q(x) = P(x) P(x). Докажите, что а) многочлен Q(x) имеет степень 2n и содержит только четные степени переменной x;

б) функция Q( x) является многочленом с корнями x2, x2,..., x2.

(См. также 9.83.) 6.43. Разделите многочлены с остатком:

6.44. Найдите остаток от деления многочлена P(x) = x5 17x + 1 на x + 2.

6.45. При каком значении a многочлен P(x) = x1000 +ax2 +9 делится на x + 1?

6.46. Найдите остаток от деления многочлена 6.47. Докажите, что многочлен P(x) = (x + 1)6 x6 2x 1 делится на x(x + 1)(2x + 1).

6.48. Многочлен P(x) дает остаток 2 при делении на x1, и остаток при делении на x2. Какой остаток дает P(x) при делении на многочлен (x 1)(x 2)?

6.49. Найдите необходимое и достаточное условие для того, чтобы выражение делилось на x + y + z.

6.50. При каких n многочлен 1 + x2 + x4 +... + x2n2 делится на Определение. Пусть m(x) — не равный тождественно нулю многочлен. Два многочлена a(x) и b(x) называются сравнимыми по модулю m(x), если их разность делится на m(x). Как и для чисел, соотношение сравнимости для двух многочленов записывается в виде 6.51. Китайская теорема об остатках для многочленов.

Пусть m1 (x),..., mn (x) попарно взаимно простые многочлены, то есть (mi (x), mj (x)) = 1 при i = j, a1 (x),..., an (x) — произвольные многочлены. Докажите, что тогда существует ровно один многочлен и deg p(x) < deg m1 (x) +... + deg mn (x). (См. также 6.131 и 6.140.) 6.52. Пусть P(x) = (2x2 2x + 1)17 (3x2 3x + 1)17. Найдите a) сумму коэффициентов этого многочлена;

б) суммы коэффициентов при четных и нечетных степенях x.

6.53. При каких a и b многочлен P(x) = (a + b)x5 + abx2 + 1 делится на x2 3x + 2?

6.54. Кубическое и квадратное уравнения с рациональными коэффициентами имеют общее решение. Докажите, что у кубического уравнения есть рациональный корень.

6.55. Найдите остаток R(x) от деления многочлена xn + x + 2 на 6.56. Один из корней уравнения x3 6x2 +ax6 = 0 равен 3. Решите уравнение.

6.57. При каких значениях параметра a многочлен P(x) = xn +axn (n 2) делится на x 2?

6.58. При каких действительных p и q двучлен x4 + 1 делится на x + px + q?

6.59. При каких a многочлен делится на x 1?

6.60. Найдите все многочлены, которые удовлетворяют тождеству..., a1, a0 0. Докажите, что это уравнение не может иметь двух положительных корней.

6.62. Правило знаков Декарта. Докажите, что количество положительных корней многочлена не превосходит числа перемен знака в последовательности an,...

6.63. Как правило знаков Декарта применить к оценке числа отрицательных корней многочлена 6.64. Докажите, что многочлен делится на (b c)(c a)(a b).

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

Как и для чисел, наибольший общий делитель многочленов P1 (x),...

..., Pk (x) обозначается (P1 (x),..., Pk (x)).

6.65. Докажите, что из равенства P(x) = Q(x) T (x) + R(x) следует соотношение (P(x), Q(x)) = (Q(x), R(x)).

6.66. Алгоритм Евклида для многочленов. Пусть P(x) и Q(x) — многочлены, причем Q(x) не равен нулю тождественно и Q(x) P(x).

Докажите, что при некотором s 1 существуют многочлены A0 (x), A1 (x),..., As (x) и R1 (x),..., Rs (x) такие, что и (P(x), Q(x)) = Rs (x). (Сравните с задачей 3.36.) 6.67. Пусть (P(x), Q(x)) = D(x). Докажите, что существуют многочлены U(x) и V(x) такие, что deg U(x) < deg Q(x), deg V(x) < deg P(x), и (Сравните с задачей 3.37.) 6.68. Найдите наибольший общий делитель многочленов P(x), Q(x) и представьте его в виде P(x) U(x) + Q(x) V(x):

6.69. Найдите (xn 1, xm 1).

6.70. Последовательность a0, a1, a2,... задана условиями Докажите, что для любых натуральных m и k (am, ak ) = a(m,k).

6.71. Решите систему 6.72. При каком положительном значении p уравнения 3x2 4px+9 = = 0 и x2 2px + 5 = 0 имеют общий корень?

6.73. Найдите многочлены P(x) и Q(x) такие, что 6.74. При помощи метода неопределенных коэффициентов (смотрите раздел 3, с. 92) найдите такие линейные функции P(x) и Q(x), чтобы выполнялось равенство 6.75. Найдите такие линейные функции P(x) и Q(x), чтобы выполнялось равенство двух положительных дробей со знаменателями n и n + 1?

6.77. Схема Горнера. Значение многочлена в точке x = c можно вычислить, используя ровно n умножений. Для этого нужно представить многочлен Pn (x) в виде (См. также 5.63.) Пусть bn, bn1,..., b0 — это значения выражений, которые получаются в процессе вычисления Pn (c), то есть Докажите, что при делении многочлена Pn (x) на (x c) с остатком, у многочлена в частном коэффициенты будут совпадать с числами bn1,..., b1, а остатком будет число b0. Таким образом, будет справедливо равенство:

6.78. Формулы сокращенного умножения. Докажите следующие равенства:

6.79. Формула Тейлора для многочлена. Докажите, что любой многочлен Pn (x) можно единственным образом разложить по степеням (x c):

причем коэффициенты ck могут быть найдены по формуле (См. также 11.21.) 6.80. Пользуясь схемой Горнера, разложите x4 + 2x3 3x2 4x + по степеням x + 1.

6.81. Разложите P(x + 3) по степеням x, где P(x) = x4 x3 + 1.

3. Разложение на множители Метод неопределенных коэффициентов. В задачах о разложении многочленов на множители часто оказывается полезным подход, который называется методом неопределенных коэффициентов.

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

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

6.82. Разложите на множители с действительными коэффициентами многочлены:

(См. также 9.8.) 6.83. Можно ли разлложить на множители с целыми коэффициентами многочлен x4 + x3 + x2 + x + 12?

6.84. Докажите, что многочлен x4 +px2 +q всегда можно разложить в произведение двух многочленов второй степени.

6.85. Упростите выражение:

6.86. Докажите, что при нечетном m выражение делится на 6.87. Пусть a, b, c — попарно различные числа. Докажите, что выражение не равно нулю.

6.88. Докажите, что если три действительных числа a, b, c связаны соотношением то обязательно какие-либо два из этих чисел в сумме дают ноль.

6.89. Докажите, что если a + b + c = 0, то 6.90. Теорема о рациональных корнях многочлена. Докажите, что если (p, q) = 1 и p/q — рациональный корень многочлена с целыми коэффициентами, то Эти соотношения позволяют перечислить все рациональные числа, которые могут быть корнями данного многочлена. (См. также 7.41.) 6.91. Докажите при помощи предыдущей задачи, что 17 — иррациональное число.

6.92. Докажите, что cos 20 — число иррациональное.

6.93. Найдите рациональные корни многочленов:

6.94. Решите уравнения:

4. Многочлены с кратными корнями Определение. Пусть P(x) = (x a)k Q(x), k 1 и Q(a) = 0. Тогда число a называется корнем многочлена P(x) кратности k. Если a — корень кратности 1, то он называется простым корнем, если кратность больше 1, то число a называется кратным корнем.

6.95. Докажите, что корень a имеет кратность больше 1 тогда и только тогда, когда P(a) = 0 и P (a) = 0.

6.96. Для данного многочлена P(x) опишем способ, который позволяет построить многочлен R(x), имеющий те же корни, что и P(x), но все кратности 1.

Положим Q(x) = (P(x), P (x)) и R(x) = P(x) Q1 (x). Докажите, что а) все корни многочлена P(x) будут корнями R(x);

б) многочлен R(x) не имеет кратных корней.

6.97. Постройте многочлен R(x) из предыдущей задачи, если:

6.98. Докажите, что многочлен не имеет кратных корней.

6.99. При каких A и B многочлен Axn+1 + Bxn + 1 имеет число x = не менее чем двукратным корнем?

6.100. Докажите, что многочлен x2n nxn+1 + nxn1 1 при n > имеет трехкратный корень x = 1.

6.101. Докажите, что многочлен P(x) делится на свою производную тогда и только тогда, когда он имеет вид P(x) = an (x x0 )n.

6.102. Докажите, что при n > 0 многочлен nxn+1 (n + 1)xn + делится на (x 1)2.

6.103. Докажите, что при n > 0 многочлен делится на (x 1)3.

6.104. Докажите, что при n > 0 многочлен делится на (x 1)3.

6.105. Докажите, что многочлен имеет число 1 корнем кратности m тогда и только тогда, когда выполнены условия:

(См. также 11.12.) 6.106. Докажите, что многочлен без остатка делится на (См. также 11.95.) 5. Теорема Виета Теорема Виета. Пусть x1, x2,..., xn — корни многочлена (an = 0). Тогда справедливы равенства Определение. Многочлен, не изменяющийся при любых перестановках своих переменных, называется симметрическим.

Многочлены называются элементарными симметрическими.

Теорема. Всякий симметрический многочлен F(x1,..., xn ) представим в виде многочлена от элементарных симметрических многочленов: F(x1,..., xn ) = G(1,..., n ) и единственным образом (См. [23].) При этом коэффициенты G получаются из коэффициентов F только при помощи операций сложения, вычитания и умножения, то есть, если все коэффициенты F были целыми числами, то и коэффициенты G также будут целыми числами.

Задачи о выражении симметрических многочленов через элементарные симметрические могут быть решены при помощи метода неопределенных коэффициентов (см. с. 92). Для нахождения искомого представления многочлена F(x1,..., xn ) степени m достаточно рассмотреть сумму с неопределенными коэффициентами одночленов вида a1... an, суммарная степень (a1 + 2a2 +... + nan ) каждого из которых равна m.

6.107. Выразите через элементарные симметрические многочлены следующие выражения:

а) (x + y)(y + z)(x + z); г) (x2 + y2 )(y2 + z2 )(x2 + z2 );

6.108. Известно, что a+b+c = 0, a2 +b2 +c2 = 1. Найдите a4 +b4 +c4.

6.109. Числа x, y, z удовлетворяют системе Докажите, что хотя бы одно из этих чисел равно a.

6.110. Решите систему:

6.111. Найдите все значения параметра a, для каждого из которых корни x1, x2, x3 многочлена x3 6x2 + ax + a удовлетворяют равенству 6.112. Постройте кубический многочлен, корни которого равны квадратам корней многочлена x3 + x2 2x 1 = 0.

6.113. Известно, что x1, x2, x3 — корни уравнения Составьте кубической уравнение, корнями которого были бы числа 6.114. Выразите свободный член c кубического уравнения через коэффициенты a и b, зная, что корни этого уравнения образуют арифметическую прогрессию.

6.115. Пусть известно, что все корни уравнения положительны. Какому дополнительному условию должны удовлетворять его коэффициенты p, q и r для того, чтобы из отрезков, длины которых равны этим корням, можно было составить треугольник?

6.116. а) Известно, что Докажите, что при любом натуральном n выполняется равенство б) Известно, что Докажите, что при любом натуральном n выполняется равенство 6.117. Решите системы:

6.118. Числа a, b, c являются тремя из четырех корней многочлена Найдите все такие многочлены.

6.119. Известно, что целые числа a, b, c удовлетворяют равенству a + b + c = 0. Докажите, что 2a4 + 2b4 + 2c4 — квадрат целого числа.

6.120. Найдите зависимость между коэффициентами кубического уравнения ax3 + bx2 + cx + d = 0, если известно, что сумма двух его корней равна произведению этих корней.

6.121. При каких a и b уравнение x3 + ax + b = 0 имеет три различных решения, составляющих арифметическую прогрессию?

6.122. Путь a, b, c — стороны треугольника, p — его полупериметр, а r и R — радиусы вписанной и описанной окружностей соответственно.

Составьте уравнение с коэффициентами, зависящими от p, r, R, корнями которого являются числа a, b, c. Докажите равенство 6.123. Решите в натуральных числах систему 6.124. В каком из двух уравнений сумма квадратов корней больше 6. Интерполяционный многочлен Лагранжа 6.125. Решите уравнение 6.126. Докажите тождество 6.127. Пусть x1 < x2 <... < xn — действительные числа. Постройте многочлены f1 (x), f2 (x),..., fn (x) степени n1, которые удовлетворяют условиям fi (xi ) = 1 и fi (xj ) = 0 при i = j (i, j = 1, 2,..., n).

6.128. Опишите явный вид многочлена где fi (x) — многочлены из предыдущей задачи.

6.129. Пусть x1 < x2 <... < xn — действительные числа. Докажите, что для любых y1, y2,..., yn существует единственнный многочлен f(x) степени не выше n 1 такой, что f(x1 ) = y1,..., f(xn ) = yn.

6.130. Пусть A, B и C — остатки от деления многочлена P(x) на x a, x b и x c. Найдите остаток от деления того же многочлена на произведение (x a)(x b)(x c).

Определение. Многочлен степени не выше n1, значения которого в данных точках x1,..., xn (узлах интерполяции) совпадают с заданными числами y1,..., yn, называется интерполяционным многочленом Лагранжа.

6.131. Какие остатки дает многочлен f(x) из предыдущей задачи на многочлены вида (x xi )? Проинтерпретируйте этот факт при помощи китайской теоремы об остатках для многочленов (см. 6.51).

6.132. Постройте многочлены f(x) степени не выше 2, которые удовлетворяют условиям:

а) f(0) = 1, f(1) = 3, f(2) = 3;

б) f(1) = 1, f(0) = 2, f(1) = 5;

в) f(1) = 1, f(0) = 0, f(2) = 4.

6.133. Корабль с постоянной скоростью проплывает мимо небольшого острова. Капитан каждый час измеряет расстояние до острова. В 12, 14 и 15 часов расстояния равнялись 7, 5 и 11 километров соответственно.

Каким было расстояние до острова в 13 часов? Чему оно будет равно в 16 часов?

6.134. Два корабля двигаются с постоянными скоростями. Расстояния между ними, измеренные в 12, 14 и 15 часов равнялись 5, 7 и километра соответственно. Каким было расстояние между кораблями в 13 часов?

6.135. На плоскости расположено 100 точек. Известно, что через каждые четыре из них проходит график некоторого квадратного трехчлена. Докажите, что все 100 точек лежат на графике одного квадратного трехчлена.

6.136. Решите систему 6.137. Пусть a, b и c — три различных числа. Докажите, что из системы следуют равенства x = y = z = 0.

6.138. Про многочлен f(x) = x10 + a9 x9 +... + a0 известно, что Докажите, что f(x) = f(x) для любого действительного x.

6.139. Пусть P(x) = an xn +... + a1 x + a0 — многочлен с целыми коэффициентами. Докажите, что хотя бы одно из чисел не меньше 1.

6.140. Докажите, что если f(x) есть многочлен, степень которого меньше n, то дробь (x1, x2,..., xn — произвольные попарно различные числа) может быть представлена в виде суммы n простейших дробей:

где A1, A2,..., An некоторые константы. (См. также 6.51.) 6.141. Решите систему 1. Комплексная плоскость Определение. Комплексными числами называются числа вида z = = x + iy, где x и y — действительные числа, а i — так называемая мнимая единица, то есть число, квадрат которого равен 1; x называется действительной или вещественной частью z, а y — мнимой частью (обозначается x = Re z, y = Im z). Числа z с x = 0, y = 0 называются чисто мнимыми. Число z = x iy называется комплексно сопряженным к числу z = x + iy. Множество всех комплексных чисел обозначается C.

7.1. Пусть z = x + iy, z = x + iy. Найдите 7.2. Проверьте равенства:

Определение. Каждому комплексному числу z = x + iy ставится в соответствие точка (x; y) на координатной плоскости Oxy и вектор с теми же координатами. Длина вектора r = x2 + y2 называется модулем числа z (r = |z|). Угол, отложенный на плоскости Oxy против часовой стрелки от оси Ox до вектора (x; y), называется аргументом числа z (r = arg z). Обычно считается, что функция arg z принимает значения Если |z| = r, arg z =, то комплексное число z может быть записано в виде z = r(cos + i sin ). Такая запись называется тригонометрической формой числа z. Представление z = x + iy называется алгебраической формой числа z.

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

7.4. Дайте геометрическую интерпретацию следующих неравенств:

если |z| = 1.

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

7.6. Какие множества на комплексной плоскости описываются следующими условиями:

7.81*. Ряд обратных квадратов. а) Докажите, что при нечетном n > 1 справедливо равенство б) Докажите тождество:

7.82*. Положительные многочлены. Многочлен P(x) при всех действительных x принимает только положительные значения. Докажите, что найдутся такие многочлены a(x) и b(x), для которых P(x) = = a2 (x) + b2 (x).

2. Преобразования комплексной плоскости Будем пользоваться обозначениями:

Ta — параллельный перенос на вектор a;

Sl — симметрия относительно прямой l (осевая симметрия с осью l);

R — поворот вокруг точки A на угол против часовой стрелки;

Hk — гомотетия с центром в точке A и коэффициентом k.

7.83. Во что перейдет треугольник с вершинами в точках: 0, 1 i, 1 + i в результате преобразования 7.84. Во что перейдет угол с вершиной в начале координат в результате преобразования w = z3 ?

7.85. Каким геометрическим преобразованиям плоскости соответствуют следующие отображения:

7.86. Как представить в виде w = f(z) симметрию относительно прямой l проходящей через начало координат под углом к оси Ox?

7.87. Выразите в виде w = f(z) следующие геометрические преобразования:

Здесь точка O = (0; 0) — начало координат. Композиция преобразований делается справа налево: (f g)(z) = f(g(z)).

7.88. Представьте гомотетию H2 в виде композиции параллельного переноса и гомотетии с центром в точке O.

7.89. Теорема о трех центрах подобия. Докажите при помощи комплексных чисел, что композицией двух гомотетий является гомотетия или параллельный перенос:

причем в первом случае вектор a параллелен прямой A1 A2, а во втором случае центр результирующей гомотетии A лежит на прямой A1 A2 и k = k1 · k2.

7.90. Постройте образ квадрата с вершинами A(0; 0), B(0; 2), C(2; 2), D(2; 0) при следующих преобразованиях:

7.91. Куда переходит полоса 2 < Re z < 3 при отображениях:

а) образ окружности |zabi| = a2 + b2 при отображении w = 1/z;

7.93*. Правильный n-угольник вписан в единичную окружность.

Докажите, что а) сумма квадратов всех сторон и всех диагоналей равна n2 ;

б) сумма всех сторон и всех диагоналей равна n ctg ;

в) произведение всех сторон и всех диагоналей равно nn/2.

Определение. Дробно-линейными отображениями комплексной плоскости называются преобразования, записываемые формулами 7.94. Как действуют отображения (7.1) и (7.2) в случае, когда = = ad bc = 0?

Определение. Расширенной комплексной плоскостью C называется комплексная плоскость C, к которой добавлена бесконечно удаленная точка =, то есть C = C {}.

7.95. Докажите, что дробно-линейные отображения являются взаимно однозначными отображениями расширенной комплексной плоскости.

7.96. Докажите, что произвольное дробно-линейное отображение вида (7.1) может быть получено композицией параллельных переносов и отображения вида w = R/z.

1. Геометрия помогает алгебре 8.1. Докажите, что сумма векторов, направленных из центра правильного n-угольника в его вершины, равна нулю.

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

sin(/7) sin(2/7) sin(3/7) (См. также 7.26.) 8.3. Вычислите 8.4. Найдите cos 36 и cos 72.

8.5. а) Используя геометрические соображения, докажите, что основание и боковая сторона равнобедренного треугольника с углом 36 при вершине несоизмеримы (т. е. их отношение иррационально).

б) Придумайте геометрическое доказательство иррациональности 2.

8.6. Решите уравнения при 0 < x < 90 :

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

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

8.9. Пусть x, y, z — положительные числа и xyz(x + y + z) = 1.

Найдите наименьшее значение выражения (x + y)(x + z).

8.10. Неотрицательные числа x, y, z удовлетворяют неравенствам 5 x, y, z 8. Какое наибольшее и наименьшее значение может принимать величина 8.11. Найдите все корни xk уравнения Какому алгебраическому уравнению удовлетворяют числа 2 cos xk ? (См.

также 7.58, 8.88.) 8.12. Решите систему Какой геометрический смысл она имеет? (См. также 8.83.) 8.13. Положительные числа a, b, c, x, y, z таковы, что Выразите величину xy + yz + xz через a, b и c. (См. также 9.16.) 2. Комплексные числа и геометрия В задачах этого пункта точки на комплексной плоскости отождествляются с числами. Поэтому с точками можно будет проделывать различные арифметические операции. Например, под суммой двух точек z и z2 будем понимать точку плоскости, соответствующую числу z1 + z2.

8.14. Пусть z1 и z2 — фиксированные точки комплексной плоскости.

Дайте геометрическое описание множеств всех точек z, удовлетворяющих соотношениям:

Определение. Комплексное число называется отношением трех точек (трех комплексных чисел) z2, z1, z0.

8.15. Докажите, что угол между прямыми, пересекающимися в точке z0 и проходящими через точки z1 и z2, равен аргументу отношения V(z2, z1, z0 ) точек z2, z1, z0.

8.16. Докажите, что три точки z2, z1, z0 лежат на одной прямой тогда и только тогда, когда V(z2, z1, z0 ) — вещественное число, или 8.17. Докажите, что прямая, проходящая через точки z1 и z2 — это геометрическое место точек z, для которых 8.18. Докажите, что уравнение прямой на комплексной плоскости всегда может быть записано в виде где C — чисто мнимое число.

8.19. Докажите, что условием того, что четыре точки z0, z1, z2, z3 лежат на одной окружности (или прямой) является вещественность числа Определение. Комплексное число называется двойным отношением четырех точек (четырех комплексных чисел) z0, z1, z2, z3.

8.20. Инвариантность двойного отношения. Пусть z1, z2, z3, z4 — четыре точки плоскости, в которые дробно-линейное отображение (7.1) переводит данные четыре точки z1, z2, z3, z4. Докажите, что 8.21. Как изменяется двойное отношение W(z1, z2, z3, z4 ) при действии отображения (7.2)?

8.22. Круговое свойство дробно-линейных отображений.

Докажите, что дробно-линейное отображение переводит каждую прямую линию или окружность снова в прямую линию или окружность.

8.23. Докажите, что уравнение окружности (или прямой) на комплексной плоскости всегда может быть записано в виде где A и C — чисто мнимые числа.

8.24. Докажите, что уравнение (8.1) при отображениях w = z + u и w = R/z переходит в уравнение такого же вида. Получите из этого круговое свойство дробно-линейных отображений.

Определение. Инверсией относительно окружности S с центром O и радиусом R называется преобразование плоскости, переводящее произвольную точку A, отличную от O, в точку A, лежащую на луче OA на расстоянии OA = R2 /OA. Образом точки O считается бесконечно удаленная точка, а образом бесконечно удаленной точки, соответственно, точка O.

Инверсией относительно окружности S будем также называть инверсией с центром O и коэффициентом R2, а окружность S — окружностью инверсии.

8.25. Докажите, что отображение w = 1/z является инверсией относительно единичной окружности.

8.26. Представьте в виде композиции дробно-линейного отображеaz + b ния w = и комплексного сопряжения w = z инверсию относиcz + d тельно окружности а) с центром i и радиусом R = 1; б) с центром Rei и радиусом R;

в) с центром z0 и радиусом R.

8.27. Круговое свойство инверсии. Докажите, что инверсия переводит каждую окружность или прямую линию снова в окружность или прямую линию.

8.28. Пусть уравнение некоторой прямой или окружности имеет вид (8.1). Пусть образ этой линии при отображении (7.1) задается уравнением где A и C также чисто мнимые числа. Выразите A, B и C через A, B и C.

Определение. Степенью точки A относительно окружности радиуса R с центром в точке O называется величина |OA|2 R2.

8.29. Докажите, что степень точки w относительно окружности равна 8.30. Радикальная ось двух окружностей. Докажите, что геометрическое место точек w, степень которых относительно двух неконцентрических окружностей S1 и S2 одинакова, является прямой.

Такая прямая называется радикальной осью окружностей S1 и S2.

8.31. Радикальный центр трех окружностей. На плоскости даны три окружности S1, S2 и S3. Докажите, что если две радикальных оси этих окружностей пересекаются в точке Q, то третья радикальная ось также проходит через эту точку.

Точка Q называется радикальным центром окружностей S1, S2 и S3.

8.32. Ортоцентр треугольника. Точки a1, a2 и a3 расположены на единичной окружности z z = 1. Докажите, что точка h = a1 + a2 + a является ортоцентром треугольника с вершинами в точках a1, a2 и a3.

8.33. Окружность Эйлера. Точки a1, a2 и a3 расположены на единичной окружности z z = 1. Докажите, что окружность с центром в точке e = h/2 и радиусом 1/2 проходит через середины сторон треугольника a1 a2 a3, основания высот и середины отрезков, соединяющих вершины a1, a2, a3 с ортоцентром h.

8.34. Цертр масс треугольника. Докажите, что точка m = (a1 + + a2 + a3 )/3 является точкой пересечения медиан треугольника a1 a2 a3.

8.35. Прямая Эйлера. Докажите, что в произвольном треугольнике точка пересечения медиан, ортоцентр и центр описанной окружности лежат на одной прямой.

8.36. Прямая Симпсона. Пусть u — точка на единичной окружности z z = 1 и u1, u2, u3 — основания перпендикуляров, опущенных из u на стороны a2 a3, a1 a3, a1 a2 треугольника a1 a2 a3.

а) Докажите, что числа u1, u2, u3 вычисляются по формулам б) Докажите, что точки u1, u2, u3 лежат на одной прямой.

8.37. На плоскости расположены 4 прямые общего положения. Каждым трем прямым поставим в соответствие окружность, проходящую через точки их пересечения. Докажите, что 4 полученных окружности проходят через одну точку.

3. Тригонометрия 8.38. Вычислите следующие произведения:

а) sin 20 sin 40 sin 60 sin 80 ; б) cos 20 cos 40 cos 60 cos 80.

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

8.40. Упростите выражение:

8.41. Упростите выражения:

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

8.43. Решите уравнение:

8.44. Известно, что sin = 1/5 sin(2 + ). Докажите равенство:

8.45. Пусть и — острые и положительные углы, удовлетворяющие равенствам Докажите, что + 2 = /2.

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

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

8.48. Докажите тождества:

8.49. Докажите тождество:

8.50. Найдите алгебраическую связь между углами, и, если известно, что 8.51. Докажите, что если + + =, то 8.52. Найдите наибольшее и наименьшее значения функций 8.53. Пусть cos x + cos y = a, sin x + sin y = b. Вычислите cos(x + y) и sin(x + y).

8.54. Докажите, что функция cos x не является периодической.

8.55. При каких целых значениях n функция имеет период 3?

8.56. Рассмотрим функцию f(x) = A cos x + B sin x, где A и B — некоторые постоянные. Докажите, что если f(x) обращается в ноль при двух значениях аргумента x1 и x2 таких, что x1 x2 = k (k — целое), то функция f(x) равна нулю тождественно.

8.57. Докажите, что если сумма при x = 0 и x = x1 = k (k — целое) обращается в ноль, то она равна нулю при всех x.

8.58. Найдите наибольшее и наименьшее значение функции f(x) = = sin6 x + cos6 x.

8.59. Решите уравнение sin4 x + cos4 x = a.

8.60. Решите уравнение sin x + sin 2x + sin 3x = 0.

8.61. Решите уравнение tg x + tg 2x + tg 3x + tg 4x = 0.

8.62. Пусть и — различные корни уравнения a cos x + b sin x = c.

Докажите, что 8.63. Решите систему:

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

8.65. Докажите, что имеют место следующие соотношения:

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

а) arctg x + arcctg x = ; б) arcsin x + arccos x =.

8.67. Докажите формулы:

а) arcsin(x) = arcsin x, б) arccos(x) = arccos x.

8.68. Чему равна сумма arctg x + arctg ?

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

и x > 0.

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

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

8.72. Найдите сумму:

8.73. Найдите сумму:

если числа a1, a2,..., an+1 образуют арифметическую прогрессию с разностью r (a1 > 0, r > 0).

8.74. Докажите, что числа Фибоначчи {Fn } удовлетворяют соотношению Получите отсюда равенство 8.75. Докажите, что при x > 1 выполняется равенство:

8.76. Решите уравнение 8.77. Докажите формулу:

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

8.79. Докажите, что если 0 < x < 1 и 8.80. Найдите соотношение между функциями 8.82. Вычислите 8.83. Теорема синусов. Докажите, что из равенств следует:

(См. также 8.12.) 8.84. Покажите, что из соотношений (8.4) и дополнительных условий 0 < <, 0 < <, 0 < <, a > 0, b > 0, c > 0 следуют равенства (8.3).

8.85. Теорема косинусов. Докажите, что соотношения (8.4) равносильны системе то есть из равенств (8.4) вытекают равенства (8.5) и наоборот.

8.86. Теорема синусов и первая теорема косинусов для трехгранного угла. Пусть имеется трехгранный угол с плоскими углами,, и противолежащими им двугранными углами A, B, C. Для него справедлива теорема синусов (8.7) и две теоремы косинусов (8.6), (8.8) (смотрите ниже). После того, как одна из этих теорем доказана, другие могут быть получены путем алгебраических преобразований.

Отвлечемся от геометрической природы задачи и предположим, что просто даны равенства и, кроме того, величины,, и A, B, C заключены между 0 и.

Докажите, что 8.87. Вторая теорема косинусов для трехгранного угла и аналог формулы Герона. Докажите, что из системы (8.6) следуют равенства 8.88. Формулы Рамануджана. Докажите следующие тождества:

(См. также 8.11.) 8.89. Пусть Докажите, что числа uk можно представить в виде многочлена от cos x.

(См. также 3.142.) 8.90. Пусть числа uk определены как и в предыдущей задаче. Докажите тождества:

а) 1u1 +u2...+u2n = 2n (1cos x)(1cos 3x)·...·(1cos(2n1)x);

1. Уравнения третьей степени 9.1. Докажите, что а) при p 0 график многочлена x3 + px + q = 0 пересекает каждую горизонтальную прямую ровно в одной точке;

б) при p < 0 график пересекает некоторые горизонтальные прямые в трех точках;

в) при p < 0 график имеет один минимум и один максимум при этом абсциссы точек минимума и максимума противоположны.

9.2. Докажите, что произвольное уравнение третьей степени при помощи линейной замены переменной z = x + можно привести к виду 9.3. Докажите, что график многочлена имеет центр симметрии.

9.4. Докажите равенство 2 + 5 + 2 5 = 1.

9.5. Решите уравнение 9.6. Докажите, что уравнение где a и b вещественные и b > 0, имеет один и только один положительный корень.

9.7. Какими должны быть числа a и b, чтобы выполнялось равенство 9.8. Разложите многочлен на три линейных множителя. (См. также 11.74.) 9.9. Выразите через a и b действительный корень уравнения Найдите представления для двух комплексных корней этого уравнения.

9.10. Докажите, что если 9.11. Формула Кардано. Получите формулу для корня уравнения x3 + px + q = 0:

9.12. Решите уравнение x3 + x 2 = 0 подбором и по формуле Кардано.

9.13. Выпишите уравнение, корнем которого будет число Запишите число без помощи радикалов.

9.14. При всех значениях параметра a найдите число действительных корней уравнения x3 x a = 0.

9.15. Решите уравнение x3 x = 0. Сколько действительных корней оно имеет?

9.16. Докажите, что если x1, x2, x3 — корни уравнения x3 +px+q = 0, (См. также 8.13.) Определение. Пусть f(x) — некоторый многочлен степени n 2, и пусть f(x) = an (x 1 )... (x n ) — разложение f(x) на линейные множители. Тогда дискриминант D(f) многочлена f(x) определяется так:

арифметических действий умеет находить x. Рассмотрим следующий алгоритм. Строится последовательность чисел {yn }, в которой y0 — произвольное положительное число, например, y0 = x, а остальные элементы определяются соотношением б) Постройте аналогичный алгоритм для вычисления корня пятой степени.

9.52. Старый калькулятор II. Производная функции ln x при x = 1 равна 1. Отсюда Воспользуйтесь этим фактом для приближенного вычисления натурального логарифма числа N. Как и в задаче 9.51, разрешается использовать стандартные арифметические действия и операцию извлечения квадратного корня.

9.53. Метод итераций. Для того, чтобы приближенно решить уравнение, допускающее запись f(x) = x, применяется метод итераций.

Сначала выбирается некоторое число x0, а затем строится последовательность {xn } по правилу xn+1 = f(xn ) (n 0). Докажите, что если эта последовательность имеет предел x = lim xn, и функция f(x) непреn рывна, то этот предел является корнем исходного уравнения: f(x ) = x.

Определение. Геометрической интерпретацией итерационного процесса служит итерационная ломаная. Для ее построения на плоскости Oxy рисуется график функции f(x) и проводится биссектриса координатного угла — прямая y = x. Затем на графике функции отмечаются точки A0 (x0, f(x0 )), A1 (x1, f(x1 )),..., An (xn, f(xn )),..., а на биссектрисе координатного угла — точки B0 (x0, x0 ), B1 (x1, x1 ),...

..., Bn (xn, xn ),... Ломаная B0 A0 B1 A1... Bn An... называется итерационной.

9.54. Постройте итерационные ломаные для следующих данных:

9.55. Последовательность чисел {an } задана условиями Верно ли, что эта последовательность ограничена?

9.56. Для последовательности {an } Докажите, что lim an = 0.

9.57. Числа a1, a2,..., ak таковы, что равенство возможно только для тех последовательностей {xn }, для которых lim xn = 0. Докажите, что все корни многочлена по модулю меньше 1.

9.58. Исследуйте последовательности на сходимость:

9.59. Что останется от прямоугольника? Золотой прямоугольник — это такой прямоугольник, стороны a и b которого находятся в пропорции золотого сечения, то есть удовлетворяют равенству a : b = b : (a b). Представим, что такой прямоугольник вырезан из бумаги и лежит на столе, обращенный к нам своей более длинной стороной. Отсечем по левую сторону прямоугольника наибольший квадрат, который можно из него вырезать; остаток будет снова золотым прямоугольником. Далее становимся по левую сторону стола так, чтобы снова иметь перед собой более длинную сторону и поступаем с новым прямоугольником так же, как и с предыдущим. Таким образом обходим стол вокруг по направлению хода часовой стрелки и по очереди отсекаем квадраты. Каждая точка прямоугольника за исключением одной, будет раньше или позже отсечена. Определите положение этой исключительной точки.

9.60. Алгоритм приближенного вычисления 3 a. Последовательность {an } определяется условиями:

9.61. Укажите способ приближенного нахождения положительного корня уравнения x3 x 1 = 0.

9.62. Последовательность чисел {an } задана условиями Докажите, что а) последовательность {an } ограничена;

б) |a1000 2| < (3/4)1000.

9.63. Найдите предел последовательности, которая задана условиями 9.64. Сходимость итерационного процесса. Предположим, что функция f(x) отображает отрезок [a; b] в себя, и на этом отрезке |f (x)| q < 1. Докажите, что уравнение f(x) = x имеет на отрезке [a; b] единственный корень x. Докажите, что при решении этого уравнения методом итераций будут выполняться неравенства:

9.65. Докажите, что для чисел {xn } из задачи 9.46 можно в явном виде указать разложения в цепные дроби:

Оцените разность |xn 2|. (См. также 9.81) 9.66. С какой гарантированной точностью вычисляется k при помощи алгоритма задачи 9.48 после пяти шагов?

9.67. Решите систему уравнений 9.68. Решите систему:

9.69. Последовательность чисел {xn } задана условиями:

Докажите, что последовательность {xn } монотонна и ограничена. Найдите ее предел.

9.70. Игра на монотонности. Докажите, что для монотонно возрастающей функции f(x) уравнения x = f(f(x)) и x = f(x) равносильны.

9.71. Решите уравнение a + a + a + x = x.

9.72. Арифметико-геометрическое среднее. Пусть a и b — два положительных числа, причем a > b. Построим по этим числам две последовательности {an } и {bn } по правилам:

Докажите, что обе эти последовательности имеют один и тот же предел.

Этот предел называется арифметико-геометрическим средним чисел a, b и обозначается µ(a, b).

9.73. Арифметико-гармоническое среднее. Пусть a и b — два положительных числа, и a < b. Определим две последовательности чисел {an } и {bn } формулами:

а) Докажите, что обе эти последовательности имеют общий предел.

Этот предел называется арифметико-гармоническим средним чисел a б) Докажите, что этот предел совпадает со средним геометрическим чисел a и b.

в) Пусть a = 1, b = k. Как последовательность {bn } будет связана с последовательностью {xn } из задачи 9.48?

9.74. Геометрико-гармоническое среднее. Назовем геометрико-гармоническим средним чисел a и b общий предел последовательностей {an } и {bn }, построенных по правилу Обозначим его через (a, b). Докажите, что величина (a, b) связана с µ(a, b) (см. задачу 9.72) равенством 9.75. Найдите все действительные решения системы 9.76. Найдите с точностью до 0,01 сотый член x100 последовательности {xn }, если б) x1 [0,1; 0,9], xn+1 = 2xn (1 xn ), (n > 1).

9.77. Докажите, что касательная к графику функции f(x), построенная в точке с координатами (x0 ; f(x0 )) пересекает ось Ox в точке с координатой 9.78. Метод Ньютона. Для приближенного нахождения корней уравнения f(x) = 0 Ньютон предложил искать последовательные приближения по формуле (начальное условие x0 следует выбирать поближе к искомому корню).

Докажите, что для функции f(x) = x2 k и начального условия x0 > 0 итерационный процесс всегда будет сходиться к k, то есть lim xn = k.

Как будет выражаться xn+1 через xn ? Сравните результат с формулой из задачи 9.48.

9.79. Метод Ньютона и числа Фибоначчи. Применим метод Ньютона для приближенного нахождения корней многочлена Какие последовательности чисел получатся, если К каким числам будут сходиться эти последовательности? Опишите разложения чисел xn в цепные дроби.

9.80. Пусть p и q — отличные от нуля действительные числа и p2 4q > 0. Докажите, что следующие последовательности сходятся:

Установите связь между предельными значениями этих последовательностей y, z и корнями уравнения x2 px + q = 0.

9.81. Метод Ньютона и цепные дроби. Предположим, что цепные дроби сходятся. Согласно задаче 9.80, они будут сходиться к корням многочлена x2 px + q = 0. С другой стороны к тем же корням будут сходиться и последовательности, построенные по методу Ньютона:

Докажите, что если x0 совпадает с нулевой подходящей дробью цепной дроби или, то числа x1, x2,... также будут совпадать с подходящими дробями к или. (См. также 9.65.) 9.82. Метод Ньютона не всегда позволяет приблизиться к корню уравнения f(x) = 0. Для многочлена f(x) = x(x 1)(x + 1) найдите начальное условие x0 такое, что f(x0 ) = x0 и x2 = x0.

9.83. Метод Лобачевского. Пусть многочлен имеет корни x1, x2,..., xn, причем |x1 | > |x2 | >... > |xn |. В задаче 6. был предъявлен способ построения многочлена Q(x) степени n, корнями которого являются числа x2, x2,..., x2. На основе этого рассуждеn ния Лобачевский придумал метод для приближенного поиска корней многочлена P(x). Он заключается в следующем. Строится последовательность многочленов P0 (x), P1 (x), P2 (x),... такая, что P0 (x) = P(x) и многочлен Pk (x) имеет корни x2,..., x2. Пусть Докажите, что 9.84. Метод Лобачевского и числа Люка. Постройте последовательность полиномов, которая получается, если метод Лобачевского применить для приближенного нахождения корней многочлена x2 x1.

Какие последовательности будут сходиться к корням x1 и x2, если |x1 | > |x2 |?

9.85. Метод Архимеда. Для приближенного нахождения числа рассмотрим окружность радиуса 1/2. Опишем около нее и впишем в нее правильные n-угольники. Обозначим их периметры через Pn (для описанного) и pn (для вписанного).

а) Найдите P4, p4, P6 и p6.

б) Докажите, что справедливы следующие рекуррентные соотношения:

в) Найдите P96 и p96. Докажите неравенства 10.21. ( x + y)8 64xy(x + y)2 (x, y 0).

10.34. Докажите, что если то наибольшая из сумм вида (k1, k2,..., kn — перестановка чисел 1, 2,..., n), это сумма а наименьшая — сумма 10.35. Неравенство Чебышёва. Докажите, что 10.36. Докажите неравенства:

10.37. Неравенство Коробова. Докажите, что при выполняется неравенство 10.38. Докажите неравенство (1+x1 )... (1+xn ) 10.39. Докажите, что для любого натурального n справедливо неравенство 10.40. Докажите, что для любого натурального n сумма лежит в пределах от 1/2 до 3/4.

Докажите, что для положительных a и b выполняется неравенство 10.42. Найдите наименьшую величину выражения 10.43. Для натурального n докажите неравенства:

(См. также 7.81.) Докажите, что для любых натуральных m и n хотя бы одно из чисел m n, n m не больше 3 3.

максимальным?

10.47. Докажите справедливость оценок:

10.57. Докажите, что для любых x1,..., xn [0; ] справедливо неравенство:

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

г) Неравенство Минковского.

10.60. Неравенство Гёльдера. Пусть p и q — положительные числа, причем 1/p + 1/q = 1. Докажите, что Определение. Для любого действительного = 0 средним степенным чисел x1,..., xn порядка называется число Частными случаями средних степенных являются: среднее гармоническое ( = 1), среднее арифметическое ( = 1), среднее квадратическое ( = 2). Средним степенным порядка 0 будем считать среднее геометрическое S0 (x) = n x1... xn.

10.61. Докажите, что выполняются классические неравенства между средними степенными:

10.63. Докажите, что если < 0 <, то причем возможно только когда x1 = x2 =... = xn.

4. Симметрические неравенства 10.65. Докажите неравенства:

в) x4 + y4 + z4 + t4 4xyzt;

Определение. Пусть имеется несколько неотрицательных переменных — для определенности, три переменные x, y и z. Наборы из такого же количества целых неотрицательных чисел, = (k, j, i), где k j i, будем называть показателями. Через T (x, y, z) = T(k,j,i) (x, y, z) будем обозначать симметрический многочлен (суммирование ведется по всем наборам {a, b, c} в количестве 3! являющимися перестановками чисел {k, j, i}).

Например неравенства из задачи 10.65 можно переписать в виде:

а) T(4,0,0) (x, y, z) T(2,1,1) (x, y, z);

б) T(3,0,0) (x, y, z) T(1,1,1) (x, y, z);

в) T(4,0,0,0) (x, y, z, t) T(1,1,1,1) (x, y, z, t);

г) T(5,0) (x, y) T(3,2) (x, y).

10.66. Запишите через многочлены вида T неравенства Определение. Диаграммой Юнга, соответствующей показателям = (1,..., n ) называется «лестница» из n ступенек, у которой высота k-й ступеньки равна k, а ширина — единице. Например Число s = 1 + 2 +... + n называется весом диаграммы Юнга.

10.67. Напишите многочлены T и нарисуйте соответствующие им диаграммы Юнга для следующих наборов :

а) (3, 2); б) (3, 2, 1); в) (3, 3, 0, 0); г) (4, 1, 1, 0).

10.68. Найдите число всех диаграмм Юнга с весом s, если набора показателей с равной суммой s = 1 +... + n = 1 +... + n.

Будем говорить, что мажорирует ( ), если справедлива система неравенств:

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

Например, (4, 2, 1) (3, 2, 2), так как 4 3, 4 + 2 3 + 2, 4 + 2 + 1 = только тогда, когда можно получить из проделав несколько (может быть один раз или ни одного) операцию Эту операцию можно представлять себе как сбрасывание одного кирпича вниз на диаграмме Юнга.

10.70. Нарисуйте все лестницы из s = 4 кирпичей в порядке убывания, начиная с самой крутой (4, 0, 0, 0), и заканчивая самой пологой (1, 1, 1, 1).

10.71. а) Проверьте, что диаграммы Юнга (4, 1, 1) и (3, 3, 0) не сравнимы, — ни одна из них не мажорирует другую. Есть ли еще такие несравнимые наборы с суммой 6?

б) Найдите все несравнимые пары наборов для s = 7.

10.72. Пусть T (x, y, z) T (x, y, z) для всех неотрицательных x, y, z. Докажите, что.

10.73*. Неравенство Мюрхеда. Пусть то при всех неотрицательных x1,..., xn выполняется неравенство 10.74. Выведите из неравенства Мюрхеда неравенство между средним арифметическим и средним геометрическим.

Сколько «кирпичей» нужно свалить, чтобы от набора (n, 0,..., 0) из n чисел перейти к набору (1, 1,..., 1)?

10.75. Докажите следующие неравенства непосредственно и при помощи неравенства Мюрхеда:

+ x2 y2 z3 );

10.76. Докажите неравенства из задачи 10.36 при помощи неравенства Мюрхеда. Как будут выглядеть диаграммы Юнга для соответствующих функций?

1. Конечные разности Определение. Пусть задана последовательность чисел Будем обозначать {bn } последовательность, состоящую из разностей соседних членов последовательности {bn }:

(Считается, что b0 = 0.) называется разностным оператором ) или оператором конечной разности.

11.1. Найдите 11.2. Пусть даны последовательности чисел {an } и {bn }, связанные соотношением bn = an, (n = 1, 2,... ). Как связаны частичные суммы Sn последовательности {an } с последовательностью {bn }?

11.3. Найдите последовательность {an } такую, что an = n2. Используя результат предыдущей задачи, получите формулу для суммы 11.4. Выведите формулу для суммы 13 + 23 + 33 +... + n3.

11.5. Докажите тождество ) Оператор — это отображение, действующее на множестве функций, последовательностей или других отображений.

Определение. Для функции f(x) выражение f(x + 1) f(x) будем обозначать f(x) и называть конечной разностью первого порядка. Конечные разности более высокого порядка определяются индуктивно:

(считается, что 0 f(x) = f(x)).

11.6. Докажите, что если Q(x) — многочлен степени m + 1, то P(x) = Q(x) — многочлен степени m.

11.7. Докажите, что для любого многочлена P(n) степени m существует единственный многочлен Q(n) степени m + 1 такой, что выполнены два условия: Q(n) = P(n) и Q(0) = 0.

11.8. Докажите формулу 11.9. Докажите равенство 11.10. Пусть f(x) — многочлен степени m. Докажите, что если m < n, то n f(x) = 0. Чему равна величина m f(x) = 0?

11.11. Вычислите сумму 11.12. Докажите, что для всех m в промежутке 1 m < n выполняется равенство:

(См. также 6.105.) 11.13*. Пусть числа y0, y1,..., yn таковы, что для любого многочлена f(x) степени m < n справедливо равенство:

Докажите, что yk = (1)k Ck, где — некоторое фиксированное число.

11.14. Докажите следующие свойства оператора конечной разности, подобные свойствам оператора дифференцирования:

11.15. Найдите представление для (an ·bn ) через an и bn. Сравните полученную формулу с формулой для производной произведения двух функций.

11.15. Разностный аналог формулы Лейбница. Для n-ой производной произведения двух функций существует формула Лейбница Докажите её разностный аналог 11.16. Экспонентой y = ex называется такая функция, для которой выполнены условия y (x) = y(x) и y(0) = 1. Какая последовательность {an } будет обладать аналогичными свойствами, если производную заменить на разностный оператор ?

11.17. Преобразование Абеля. Для подсчета интегралов используется формула интегрирования по частям. Докажите следующие две формулы, которые являются дискретным аналогом интегрирования по частям и называются преобразованием Абеля:

11.18. Найдите последовательность {an } такую, что an = n2n.

(Вспомните как вычисляют 11.19. Найдите:

11.20. При помощи преобразования Абеля вычислите следующие суммы:

Определение. В дальнейшем под символом Cn будем понимать многочлен определенный для всех действительных x. При целых x n его значения будут совпадать с обычными биномиальными коэффициентами.

11.21. Интерполяционная формула Ньютона. а) Докажите, что для любого многочлена f(x) степени n существует единственное представление его в виде Здесь и далее биномиальный коэффициент Ck интерпретируется как многочлен от переменной x. В частности, нижний индекс у биномиального коэффициента может быть любым действительным числом. (См.

также 6.79.) б) Докажите, что коэффициенты d0, d1,..., dn в этом представлении вычисляются по формуле dk = k f(0) (0 k n).

11.22. Целозначные многочлены. Пусть многочлен f(x) степени n принимает целые значения в точках x = 0, 1,..., n. Докажите, что где d0, d1,..., dn — некоторые целые числа.

11.23. Для многочлена f(x) = x3 x найдите 2 f(x). Объясните, не применяя соображения делимости, почему f(x). 6 при всех целых x.

11.24. Докажите, что многочлен f(x) степени n принимает целые значения в точках x = 0, 1,..., n, то он принимает целые значения для любого целого x.

11.25. а) Пусть q — натуральное число и функция принимает целые значения при x = 0, 1, 2,..., n + 1. Докажите, что при любом целом x 0 число f(x) также будет целым.

б) Пусть выполняются условия пункта а) и f(x) делится на некоторое m 1 при x = 0, 1, 2,..., n + 1. Докажите, что f(x) делится на m при всех целых x 0.

11.26. Докажите, что при всех натуральных n число f(n) = 22n 9n2 + 21n 14 делится на 27.

11.27*. Для каких натуральных n в выражении можно так расставить знаки + и, что в результате получится 0?

Определение. Пусть функция f(x, y) задана во всех точках плоскости с целыми координатами. Назовем функцию f(x, y) гармонической, если ее значение в каждой точке равно среднему арифметическому значений функции в четырех соседних точках, то есть 11.28. Пусть f(x, y) и g(x, y) — гармонические функции. Докажите, что для любых a и b функция af(x, y) + bg(x, y) также будет гармонической.

11.29. Пусть f(x, y) — гармоническая функция. Докажите, что функции x f(x, y) = f(x+1, y)f(x, y) и y f(x, y) = f(x, y+1)f(x, y) также будут гармоническими.

11.30*. Дискретная теорема Лиувилля. Пусть f(x, y) — ограниченная гармоническая функция, то есть существует положительная константа M такая, что Докажите, что функция f(x, y) равна константе.

2. Рекуррентные последовательности Определение. Последовательность чисел a0, a1,..., an,..., которая удовлетворяет с заданными p и q соотношению называется линейной рекуррентной (возвратной) последовательностью второго порядка.

Уравнение называется характеристическим уравнением последовательности {an }.

11.31. Докажите, что если числа a0, a1 фиксированы, то все остальные члены последовательности {an } определяются однозначно.

11.32. Докажите, что геометрическая прогрессия {an } = bxn удовлетворяет соотношению (11.2) тогда и только тогда, когда x0 — корень характеристического уравнения (11.3) последовательности {an }.

11.33. Пусть характеристическое уравнение (11.3) последовательности {an } имеет два различных корня x1 и x2. Докажите, что при фиксированных a0, a1 существует ровно одна пара чисел c1, c2 такая, что 11.34. Пусть характеристическое уравнение (11.3) последовательности {an } имеет корень x0 кратности 2. Докажите, что при фиксированных a0, a1 существует ровно одна пара чисел c1, c2 такая, что 11.35. Найдите формулу n-го члена для последовательностей, заданных условиями (n 0):

a) a0 = 0, a1 = 1, an+2 = 5an+1 6an ;

б) a0 = 1, a1 = 1, an+2 = 3an+1 2an ;

д) a0 = 0, a1 = 1, an+2 = 2an+1 + an.

11.36. При возведении числа 1 + 2 в различные степени, можно обнаружить некоторые закономерности:

Для изучения определим числа an и bn при помощи равенства (1 + 2)n = an + bn 2, (n 0). (См. также 11.59.) а) Выразите через an и bn число (1 2)n.

б) Докажите равенство a2 2b2 = 1.

в) Каким рекуррентным уравнениям удовлетворяют последовательности {an } и {bn }?

г) Пользуясь пунктом а), найдите формулы n-го члена для последовательностей {an } и {bn }.

д) Найдите связь между числами an, bn и подходящими дробями к числу 2.

11.37. Рассмотрим равенства:

Обобщите результат наблюдения и докажите возникшие у вас догадки.

11.38. Докажите, что уравнение не имеет решений в рациональных числах x, y, z, t.

11.39. Найдите все целочисленные решения уравнения a2 3b2 = 1.

11.40. Докажите, что произвольная последовательность Qn, заданная условиями может быть выражена через числа Фибоначчи Fn и числа Люка Ln.

Определение. Многочлены Фибоначчи Fn (x) (n 0) задаются при помощи начальных условий F0 (x) = 0, F1 (x) = 1 и рекуррентного соотношения Аналогично, многочлены Люка Ln (x) определяются равенствами 11.41. Многочлены Фибоначчи и Люка. Вычислите несколько первых многочленов Фибоначчи и Люка. Какие значения эти многочлены принимают при x = 1?

Докажите, что многочлены Люка связаны с многочлены Фибоначчи соотношениями (см. также 3.133):

а) Ln (x) = Fn1 (x) + Fn+1 (x) (n 1);

б) Fn (x) (x2 + 4) = Ln1 (x) + Ln+1 (x) (n 1);

в) F2n (x) = Ln (x) · Fn (x) (n 0);

г) Ln (x)2 + Ln+1 (x)2 = F2n+1 (x)(x2 + 4) (n 0);

д) Fn+2 (x) + Fn2 (x) = (x2 + 2)Fn (x) (n 2).

11.42. Разложите функции Fn+1 (x)/Fn (x) и Ln+1 (x)/Ln (x) (n 1) в цепные дроби, (См. также 3.144.) 11.43. Получите формулу для многочленов Фибоначчи и Люка аналогичную формуле Бине. (См. также 3.126 и 11.75.) 11.44. Докажите, что многочлены Фибоначчи и Люка связаны с многочленами Чебышёва равенствами 11.45. Укажите явный вид коэффициентов в многочленах Fn (x) и Ln (x). Решите задачи 3.129 и 3.130 используя многочлены Фибоначчи.

11.46. Лягушка-путешественница. Лягушка прыгает по вершинам треугольника ABC, перемещаясь каждый раз в одну из соседних вершин. Сколькими способами она может попасть из A в A за n прыжков?

11.47. Лягушка прыгает по вершинам шестиугольника ABCDEF, каждый раз перемещаясь в одну из соседних вершин.

а) Сколькими способами она может попасть из A в C за n прыжков?

б) Тот же вопрос, но при условии, что ей нельзя прыгать в D?

в) Лягушка-сапер. Пусть путь лягушки начинается в вершине A, а в вершине D находится мина. Каждую секунду она делает очередной прыжок. Какова вероятность того, что она еще будет прыгать через n секунд? Какова средняя продолжительность жизни таких лягушек?

11.48. Докажите, что для любого числа p>2 найдется такое число, что 11.49. Садовник, привив черенок редкого растения, оставляет его расти два года, а затем ежегодно берет от него по 6 черенков. С каждым новым черенком он поступает аналогично. Сколько будет растений и черенков на n-м году роста первоначального растения?

11.50. Найдите у чисел а) (6 + 35)1999 ; б) (6 + 37)1999 ; в) (6 + 37) первые 1000 знаков после запятой.

11.51.Докажите, что при всех натуральных n выполняется сравнение [(1 + 2)n ] n (mod 2).

11.52. Докажите, что последовательность an = 1 + 17n2 (n 0) содержит бесконечно много квадратов целых чисел.

11.53. Определим последовательности {xn } и {yn } при помощи условий:

xn = xn1 + 2yn1 sin2, yn = yn1 + 2xn1 cos2, x0 = 0, y0 = cos.

Найдите выражение для xn и yn через n и.

11.54. Пять моряков высадились на остров и к вечеру набрали кучу кокосовых орехов. Дележ отложили на утро. Один из них, проснувшись ночью, угостил одним орехом мартышку, а из остальных орехов взял себе точно 1/5 часть, после чего лег спать и быстро уснул. За ночь так же поступили один за другим и остальные моряки; при этом каждый не знал о действиях предшественников. На утро они поделили оставшиеся орехи поровну, но для мартышки в этот раз лишнего ореха не осталось.

Каким могло быть наименьшее число орехов в собранной куче?

Определение. Последовательность чисел a0, a1,..., an,..., которая при заданных b0,..., bk1 удовлетворяет соотношениям называется линейной рекуррентной (возвратной) последовательностью k-го порядка.

Уравнение называется характеристическим уравнением последовательности {an }.

11.55*. Как будет выглядеть формула n-го члена для рекуррентной последовательности k-го порядка, если a) характеристическое уравнение имеет простые корни x1,..., xk ;

б) характеристическое уравнение имеет корни x1,..., xm с кратностями 1,..., m соответственно?

11.56. Пусть характеристическое уравнение (11.3) последовательности (11.2) имеет комплексные корни x1,2 = a ± ib = re±i. Докажите, что для некоторой пары чисел c1, c2 будет выполняться равенство 11.57. Найдите формулу n-го члена для последовательностей, заданных условиями (n 0):

a) a0 = 0, a1 = 1, an+2 = 4an+1 5an ;

б) a0 = 1, a1 = 2, an+2 = 2an+1 2an ;

г) a0 = 1, a1 = 8, an+2 = 6an+1 + 25an.