«ЗАД АЧИ П О АЛГЕ БР Е, АР И Ф МЕ Т И КЕ И АН АЛИ ЗУ Учебное пособие Москва Издательство МЦНМО 2007 УДК 512.1+517.1+511.1 ББК 22.141+22.161 П70 Прасолов В. В. П70 Задачи по алгебре, арифметике и анализу: Учебное пособие. ...»

7.13. В отчёте о лыжном забеге сказано, что 96% его участников выполнили норму. Известно, что эта цифра дана с точностью до 0,5%. Каково наименьшее число участников этого забега?

7.14. В карьере заготовлено 120 гранитных плит по 7 т и 80 плит по 9 т. На железнодорожную платформу можно погрузить до 40 т. Какое наименьшее число платформ потребуется, чтобы вывезти все плиты?

7.15. Груз весом 13,5 т упакован в ящики так, что вес каждого ящика не превосходит 350 кг. Докажите, что этот груз можно перевезти на 11 полуторатонках. (Весом пустого ящика можно пренебречь.) 7.16. Десять рабочих должны собрать из деталей 50 изделий. Сначала детали каждого изделия нужно покрасить;

на это одному рабочему требуется 10 минут. После окраски му требуется 20 минут. Сколько рабочих нужно назначить малярами и сколько монтажниками, чтобы работа была выполнена в кратчайшее время? (Двое рабочих не могут одновременно красить или монтировать одно и то же изделие.) 7.17. На консультации было 20 школьников и разбиралось 20 задач. Оказалось, что каждый из школьников решил две задачи и каждую задачу решили два школьника.

Докажите, что можно так организовать разбор задач, чтобы каждый школьник рассказал одну из решённых им задач и все задачи были разобраны.

7.18. В библиотеке поставили две доски. На одной доске читатель записывает число читателей, которых он застал, войдя в читальный зал, а на другой — сколько читателей оставалось, когда он уходил из библиотеки. Рано утром и поздно вечером читателей в библиотеке не было. Докажите, что за день на обеих досках появятся одни и те же числа (возможно, в другом порядке).

7.19. Подряд выписаны n чисел, среди которых есть положительные и отрицательные. Подчёркивается каждое положительное число, а также каждое число, сумма которого с несколькими непосредственно следующими за ним числами положительна. Докажите, что сумма всех подчёркнутых чисел положительна.

7.20. Докажите, что число всех цифр в последовательности 1, 2, 3,..., 10k равно числу всех нулей в последовательности 1, 2, 3,..., 10k+1 .

7.1. Из второго стакана убавилось молока ровно столько, сколько в него добавилось чая. Поэтому чая в молоке ровно столько, сколько молока в чае.

7.2. О т в е т: 10 км. Можно считать, что велосипедист всё время едет в одном направлении (длина пути от этого не меняется).

Его скорость в 2 раза больше скорости пешехода, поэтому за то время, за которое пешеход пройдёт 5 км, велосипедист проедет 10 км.

7.3. О т в е т: 127. Мысленно добавим к стае какую-нибудь птицу, например, утку, которая летит со стаей до самого последнего озера. Тогда на каждом озере садится ровно половина птиц, причём на седьмом озере садятся две птицы — гусь и утка. Значит, в стае было 27 птиц, из них 27 1 = 127 гусей.

7.4. О т в е т: 120 км. Пусть x — расстояние от A до B. До первой встречи оба велосипедиста вместе проехали x км, а до второй — 3x км. Значит, велосипедист, выехавший из A, к моменту второй встречи проехал 3 · 70 = 210 км. С другой стороны, он проехал x + 90 км. Поэтому x = 210 90 = 120 км.

7.5. О т в е т: 35. Пусть v — скорость течения реки, u — скорость парохода, l — расстояние от Горького до Астрахани. По условию =5 и = 7; требуется найти l/v. Из системы уравнений l = 5u + 5v, l = 7u 7v находим l/v = 35.

7.6. а) Чтобы A и B прибыли в пункт N одновременно, они должны пройти пешком одно и то же расстояние x км и проехать на велосипеде одно и то же расстояние 15 x. Тогда C до встречи с B тоже должен пройти пешком расстояние x. Поэтому C до встречи с A проедет на велосипеде 15 2x, а после этого A проедет на велосипеде 15 x. Всего A и C вместе проедут на велосипеде 30 3x. За это же время B пройдёт пешком x, поэтому =, из M за ч до того, как A и B отправятся в путь из M.

б) Чтобы A и B затратили на дорогу наименьшее время, они должны прибыть в N одновременно, т. е. они должны пройти пешком одинаковые расстояния. Действительно, пусть A проходит пешком расстояние x и проезжает на велосипеде 15 x, а B проходит y и проезжает 15 y. Тогда время, затраченное A, равx Нас интересует большее из этих чисел; оно должно быть наименьшим. За то же самое время, за которое A проходит пешком расстояние x, B и C успевают проехать на велосипеде расстояние Для любой другой точки прямой 7x + 4y = 60 координата x или координата y будет больше.

Задача о том, когда должен выйти C, чтобы A и B прибыли одновременно, — это в точности задача а).

7.7. Пусть скорость парохода равна v, скорость течения реки равна w. Если v w, то пароход вообще не сможет плыть против течения. Если же v > w, то на путь из A в B и обратно требуется время а на то, чтобы проплыть 20 км по озеру, требуется время 20/v.

7.8. Пусть расстояние между деревнями равно a. Предположим, что баня построена на расстоянии x от деревни A (0 x a).

Тогда общее расстояние равно 200x + 100(a x) = 100x + 100a. Оно минимально, когда x = 0. Это означает, что баню нужно построить в деревне A.

7.9. О т в е т: нет, не может. Пусть на пересечении строки, в которой стоит число A, и столбца, в котором стоит число B, стоит число x. Тогда A x B.

7.10. Пусть a1 > a2 >... > a7 — количество грибов, собранных грибниками. Если a3 16, то a2 17 и a1 18, поэтому a1 + a2 + a3 51. Если a3 15, то a4 14, a5 13, a6 12 и a7 11, поэтому a4 + a5 + a6 + a7 50, а значит, a1 + a2 + a3 50.

7.11. П е р в о е р е ш е н и е. По условию в каждом походе мальчиков было меньше 2/3 девочек, участвовавших в походе.

Следовательно, в каждом походе мальчиков было меньше 2/3 всех девочек, учащихся в классе. Каждый мальчик был хотя бы в одном походе, поэтому мальчиков в классе меньше 4/3 всех девочек, т. е. мальчиков меньше 4/7 общего числа учеников.

В т о р о е р е ш е н и е. Пусть всего в классе x мальчиков и y девочек; в первом походе было x1 мальчиков и y1 девочек, во втором — x2 и y2. По условию 5x1 < 2(x1 + y1 ), поэтому 3x1 < 2y1 2y.

Аналогично 3x2 < 2y. Следовательно, 3(x1 + x2 ) < 4y. Кроме того, по условию x1 + x2 x. Поэтому 3x < 4y, т. е. 7x < 4(x + y).

= 3,6, т. е. 8x = 7y. Значит, x = 7a и y = 8a для некоторого целого a.

Поэтому число x + y = 15a делится на 15. Единственное число, делящееся на 15, которое больше 30 и меньше 50, — это 45. Таким образом, x = 21 и y = 24.

7.13. Пусть в забеге участвовало n лыжников, причём k из них не выполнили норму. По условию 3,5 100k/n 4,5. Значит, k иn > 22,2k 22,2. Поэтому n 23. Если в забеге участвовало 23 лыжника, из которых норму не выполнил только один, то требуемое условие выполняется.

7.14. На одну платформу нельзя погрузить 6 плит даже по 7 т. Поэтому нужно по крайней мере 200/5 = 40 платформ. Сорока платформ достаточно: на каждую платформу можно погрузить 3 плиты по 7 т и 2 плиты по 9 т.

7.15. Выделим 8 машин и будем последовательно их грузить, причём каждый раз тот ящик, который уже нельзя погрузить, будем ставить рядом с машиной. Погруженные ящики вместе с ящиками, стоящими рядом с машинами, весят более 8· 1,5= 12 т, поэтому оставшиеся ящики весят менее 1,5 т; их можно увезти на одной полуторатонке. Поскольку 4 · 350 = 1400 < 1500, на одной машине можно увезти любые 4 ящика. Значит, 8 ящиков, стоящих рядом с машинами, можно увезти на двух оставшихся полуторатонках.

7.16. О т в е т: 3 маляра и 6 монтажников (один рабочий лишний, т. е. можно назначить 4 маляров и 6 монтажников или 3 маляров и 7 монтажников). Легко проверить, что 3 маляра и 6 монтажников могут выполнить работу за 195 минут. Действительно, через 15 минут после начала работы маляров 3 изделия готовы к сборке и 3 монтажника соберут их через 20 минут. После этого к сборке будут готовы 6 изделий, причём монтажникам никогда уже не придётся ждать, пока маляры закончат покраску очередного изделия. Через 15 + 20 + 140 = 175 минут после начала работы будет смонтировано 3 + 7 · 6 = 45 изделий. Чтобы смонтировать 5 оставшихся изделий, нужно ещё 20 минут (этим смогут заниматься только 5 монтажников).

Если маляров меньше трёх, то покраска займёт не менее 250 минут, а если монтажников меньше шести, то монтаж займёт не менее 200 минут.

7.17. Начнём разбор задач с того, что произвольный школьник расскажет одну из решённых им задач. Пусть этот школьник решил задачи a1 и a2, а рассказал он задачу a1. Тогда есть ровно один школьник, который тоже решил задачу a2 (и ещё задачу a3 ). Этот школьник расскажет задачу a2. Затем школьник, который решил задачи a3 и a4, расскажет задачу a3 и т. д. Так мы дойдём до n-го школьника, который решил задачи an и ak, где 1 k n 1. Нужно понять, что делать, если n < 20. Ясно, что k = 1. Действительно, задачу ak, где 2 k n 1, решили два школьника с номерами k 1 и k. Пусть n-й школьник расскажет задачу an. Для оставшихся школьников и оставшихся задач выполняется то же самое условие: каждый из школьников решил две задачи и каждую задачу решили два школьника. Поэтому можно повторить то же самое и т. д.

7.18. Можно считать, что всегда выходит самый последний из пришедших в библиотеку читателей. Действительно, не имеет значения, кто именно запишет на доске число читателей, остающихся в зале; один читатель может перепоручить это другому — результат от этого не изменится. Тогда каждый читатель на обеих досках запишет одно и то же число.

7.19. Пусть выписаны числа a1, a2,..., an. Подчеркнём число ai k + 1 чертами, если k — наименьшее число, для которого ai + ai+1 + ai+2 +... + ai+k > 0 (положительное число a1 подчёркивается одной чертой). Ясно, что если число ai подчёркнуто k + чертами, то числа ai+1, ai+2,..., ai+k подчёркнуты соответственно k, k 1,..., 2, 1 чертами. Подчёркнутые числа разобьём на группы следующим образом. Сначала возьмём числа, подчёркнутые наибольшим числом черт (пусть это число черт равно K), и следующие за каждым из них K 1 чисел. Затем возьмём числа, подчёркнутые K 1 чертами, и следующие за каждым из них K чисел, и т. д. Сумма чисел в каждой группе положительна.

7.20. Сопоставим цифре числа из первой последовательности нуль числа из второй последовательности следующим образом. Напишем после данной цифры нуль. В результате получим число из второй последовательности с отмеченным нулём. Нашей цифре мы сопоставляем именно этот нуль. Наоборот, нулю числа из второй последовательности сопоставим цифру числа из первой последовательности следующим образом. Отметим цифру, которая стоит перед данным нулём, и после этого нуль вычеркнем. В результате получим число из первой последовательности с отмеченной цифрой. Нашему нулю мы сопоставляем именно эту цифру. Эти операции взаимно обратны, поэтому мы получаем взаимно однозначное соответствие между цифрами числа первой последовательности и нулями чисел второй последовательности.

НЕРАВЕНСТВА

Напомним, что согласно задаче 1.1 для всех x > 0 выполняется неравенство x + 1/x 2.

8.1. При каких n существуют положительные числа x1,..., xn, удовлетворяющие системе уравнений 8.2. Докажите, что если числа a1,. .., an положительны 8.3. Докажите, что если x5 x3 + x = 2, то 3 < x6 < 4.

8.4. а) Докажите, что если x1, x2, x3 — положительные числа, то б) Докажите, что если x1, x2,..., xn — положительные числа, причём n 4, то Будем говорить, что положительные числа a, b, c удовлетворяют неравенству треугольника, если a + b > c, b + c > a и c + a > b. На геометрическом языке это означает, что из отрезков длиной a, b, c можно составить треугольник.

8.5. Докажите, что положительные числа a, b, c удовлетворяют неравенству треугольника тогда и только тогда, когда (a2 + b2 + c2 )2 > 2(a4 + b4 + c4 ).

8.6. Докажите, что если для положительных чисел a1, a2,..., an (n 3) выполняется неравенство то любые три из этих чисел удовлетворяют неравенству треугольника.

8.7. Неравенство Aa(Bb + Cc) + Bb(Cc + Aa) + Cc(Aa + Bb) > где a>0, b>0, c>0 — заданные числа, выполняется для всех A > 0, B > 0, C > 0. Можно ли из отрезков a, b, c составить треугольник?

8.8. Докажите неравенство xy 8.9. Докажите неравенство Неравенство из задачи 8.9 называют неравенством Коши. Другие его доказательства приведены в задачах 1.9 и 5.12.

8.10. Докажите неравенство 8.11. Пусть x1,..., xn — положительные числа. Докажите неравенство 8.12. Пусть S = a1 +... + an, где a1,..., an — положительные числа и n 2. Докажите, что 8.4. Неравенство между средним арифметическим Пусть a1,..., an — положительные числа. Их средним арифa1 +... + an ним геометрическим называют число G = 1 n a... a. В 1821 г.

Коши доказал неравенство A G. Доказательство Коши использовало индукцию, но не обычным способом: сначала доказывалось, что если утверждение верно для n = 2m, то оно верно и для n = 2m+1, а затем доказывалось, что если утверждение верно для n, то оно верно и для n 1 (см. решение задачи 13.10).

8.13. Пусть a1,..., an — положительные числа. Докажите неравенство (Если не все данные числа равны, то неравенство строгое.) 8.14. Пусть a, b > 0. Докажите, что 2 a + 3 3 b 5 5 ab.

8.15. Докажите, что для любого натурального n 2 имеют место неравенства 8.16. Пусть a1,..., an, w1,..., wn — положительные числа. Докажите, что З а м е ч а н и е. При w1 =... = wn = 1 получаем неравенство между средним арифметическим и средним геометрическим, поэтому неравенство из задачи 8.16 является обобщением неравенства между средним арифметическим и средним геометрическим.

8.17. Пусть a1,..., an — положительные числа, 1,...

..., n — попарно различные положительные числа. Для графики функций y = f(x) и y = ax касались при x = x0.

Докажите, что f(x) ax, причём равенство достигается только при x = x0.

См. также задачи 13.10, 25.21.

8.18. Пусть a, b, c — положительные числа. Докажите, что причём равенство достигается тогда и только тогда, когда 1/a + 1/c = 1/b.

8.19. Пусть a1,..., an — положительные числа. Докажите, что 8.20. Докажите, что для любых положительных чисел a, b, c выполнено неравенство 8.22. Пусть a, b, c — положительные числа. Докажите, что 8.23. Докажите, что если a, b, c, d — положительные чисa+c ла, причём a/b < c/d, то < b > 0. Докажите, что aa bb > ab ba.

8.26. Предположим, что x1,..., xn — действительные числа, про которые известно, что все числа 1 = xi, 2 = 8.30. Докажите, что для всех натуральных n 2 имеет место неравенство 8.31. Пусть x и y — произвольные вещественные числа.

Докажите, что 8.32. Докажите, что для всех натуральных n справедливо неравенство 8.34. Докажите, что (2n 1)n + (2n)n < (2n + 1)n для любого натурального n > 2.

8.35. По окружности расставлены в произвольном порядке числа 1, 2,..., n. Докажите, что сумма модулей разностей соседних чисел не меньше 2n 2.

8.36. Пусть 0 < a xi b. Докажите, что 8.37. Докажите, что если 1 x1,..., xn 1 и x3 +...+x3 = n = 0, то x1 +... + xn n/3.

8.38. Докажите, что если xy = 4 и z2 + 4w2 = 4, то (x z)2 + + (y w)2 1,6.

8.39. Пусть A(x) = A1 (x) +... + A5 (x), где x = (x1, x2, x3, x4, x5 ) и Ai (x) = (xi xj ). Докажите, что A(x) 0 для 8.40. Сто положительных чисел x1, x2,..., x100 удовлетворяют условиям Докажите, что среди них можно найти три числа, сумма которых больше 100.

См. также задачу 18.4.

8.41. Пусть n = 1 — натуральное число и a > b > 0. Докаan + bn 8.42. Сравните числа 8.9. Неравенства Гёльдера и Минковского 8.43. а) Пусть a — рациональное число, причём a > 1 или a < 0. Докажите, что для любого x > 0, x = 1, выполняется неравенство xa ax + a 1 > 0.

б) Пусть a — рациональное число, причём 0 < a < 1. Докажите, что для любого x > 0, x = 1, выполняется неравенство 8.44. Докажите, что если m и n — натуральные числа, отличные от 1, то 8.45. Пусть A и B — положительные числа, а p и q — рациональные числа, связанные соотношением 1/p + 1/q = 1.

Докажите, что если p > 1, то A1/p B1/q A/p + B/q, а если p < 1, то A1/p B1/q A/p + B/q. (Если A = B, то оба неравенства строгие.) 8.46. Пусть xi и yi — положительные числа, а p и q — рациональные числа, связанные соотношением 1/p + 1/q = 1.

Докажите, что если p > 1, то а если p < 1, то (неравенство Гёльдера).

8.47. Пусть xi и yi — положительные числа, а p > 1 — рациональное число. Докажите, что Если p < 1, то неравенство заменяется на противоположное (неравенство Минковского).

8.1. Воспользовавшись неравенством xi + 1/xi 2, получим получаем решение x1 = x2 = x3 = 1. При n = 2 получаем решение 8.2. Из соотношения a1... an = 1 следует, что ((1 + a1 )(1 + a2 )... (1 + an ))2 = Сложив равенства x x3 + x = 2 и x7 x5 + x3 = 2x2, получим x + x = 2 + 2x2, т. е. x6 + 1 = 2(x + 1/x) 4. Следовательно, x6 3.

Неравенство строгое, поскольку x = 1.

в виде что b/a + a/b 2 и т. д.

б) При n = 4 получаем При n > 4 требуемое неравенство можно доказать по индукции. Предположим, что для чисел x1,..., xn неравенство уже доказано. Выберем среди положительных чисел x1,..., xn+1 наименьшее. После циклической перенумерации этих чисел можx1 x последнее неравенство выполняется по предположению индукции.

8.5. Положительные числа a, b, c удовлетворяют неравенству треугольника тогда и только тогда, когда Действительно, два выражения в скобках не могут быть одновременно отрицательными. Например, неравенства a + b < c и b + c < a не могут выполняться одновременно. После раскрытия скобок неравенство (1) записывается в виде 2(a2 b2 + b2 c2 + c2 a2 ) (a4 + b4 + c4 ) > 0, а из этого уже легко получить требуемое.

8.6. Прежде всего покажем, что для таких чисел выполняется неравенство Исходное неравенство можно записать в виде где S2 = a2 +... + a2 и S4 = a4 +... + a4. Выделим полный квадрат:

Следовательно, S2 1 > (n 1)S4, т. е. S2 > (n 2)S4, что и требовалось.

Далее по индукции получаем При k = n 2 согласно задаче 8.5 это неравенство означает, что числа an2, an1, an удовлетворяют неравенству треугольника. То же самое доказательство можно применить и для любой другой тройки чисел.

О т в е т: не всегда. Положим a = b = 1, c = 2. Тогда требуемое неравенство примет вид т. е. AC + BC > 0. Это неравенство выполняется для всех положительных A, B, C.

З а м е ч а н и е. Из отрезков a, b, c всегда можно составить вырожденный треугольник. Чтобы доказать это, положим A = B = 1, C =. Тогда иначе неравенство (1) не выполнялось бы при малых. Значит, c2 4ab (a + b)2. Числа a, b, c положительны, поэтому c a + b.

Неравенства a b + c и b a + c доказываются аналогично.

8.8. Достаточно заметить, что (x y)2 0.

8.10. Это неравенство является частным случаем неравенства Коши; достаточно положить b1 =... = bn = 1.

8.11. Это неравенство очевидным образом следует из неравенства Коши: достаточно положить ai = xi и bi = 1/ xi.

8.12. Положим bi = S ai. Тогда требуемое неравенство запишется в виде (задача 8.11).

8.13. П е р в о е р е ш е н и е. Применим индукцию по n. При n = 1 требуемое утверждение верно. Предположим, что требуемое неравенство доказано для любых n положительных чисел.

Рассмотрим положительные числа b1 = n+1 a1,..., bn+1 = n+1 an+1.

Ясно, что (bn bn )(bi bj ) 0. Просуммируем такие неравенства для всех пар i, j, для которых i > j. В результате получим (Если не все данные числа равны, то неравенство строгое.) Воспользовавшись неравенством между средним арифметическим и средним геометрическим для n чисел, получим Следовательно, что и требовалось.

В т о р о е р е ш е н и е. Расположим данные числа в порядке возрастания: a1 a2... an. Если a1 = an, то a1 = a2 =... = an.

В таком случае A = G. Поэтому будем предполагать, что a1 < an.

Тогда a1 < A < an, а значит, т. е. A(a1 + an A) > a1 an. В частности, a1 + an A > 0.

Применим индукцию по n. Предположим, что неравенство между средним арифметическим и средним геометрическим верно для любых n 1 положительных чисел. Применим его к числам a2, a3,..., an1, a1 + an A. В результате получим Здесь Умножим теперь обе части полученного неравенства на A:

мы воспользовались доказанным выше неравенством A(a1 +an A)> > a1 an.

З а м е ч а н и е. По поводу доказательства неравенства между средним арифметическим и средним геометрическим с помощью выпуклых функций см. задачу 26.22.

8.14. Положим a = x10 и b = y15. Согласно неравенству между средним арифметическим и средним геометрическим 8.15. Применим неравенство между средним арифметическим тате получим т. е.

Применим неравенство между средним арифметическим и средn ним геометрическим для чисел 1,,,...,. В результате получим т. е.

8.16. П е р в о е р е ш е н и е. Применим индукцию по n и воспользуемся неравенством из задачи 8.45. Введём для удобства обозначения Wn = W и Wn1 = w1 +... + wn1. Ясно, что жением индукции.

В т о р о е р е ш е н и е. Мы воспользуемся неравенством 1 + + x < ex для x = 0 (задача 28.48). Определим числа b1,..., bn так, поэтому w1 b1 +... + wn bn = 0. Легко видеть, что если не все числа a1,..., an равны, то хотя бы одно из чисел b1,..., bn отлично от нуля. В таком случае Заодно мы доказали, что требуемое неравенство является строгим, если не все числа a1,..., an равны.

8.17. Пусть g(x)=ax. По условию f(x0 )=g(x0 ) и f (x0 )=g (x0 ), т. е. ax0 =f(x0 ) и a x0 1 = ai i x0 i 1. Следовательно, a=f(x0 )/x Согласно неравенству из задачи 8. Таким образом, f(x) f(x0 ) = ax. Остаётся заметить, что есx ”x ли x = x0, то числа, i = 1,..., n, попарно различны, поэтому получаем строгие неравенства.

8.18. Рассмотрим треугольник AOC, в котором AO = a, CO = c и угол при вершине O равен 120. Проведём биссектрису угла O и отложим на ней или на её продолжении отрезок = b. ТоOB гда по и AC= a2 + ac + c2. Поэтому требуемое неравенство — это обычное неравенство треугольника AC AB + BC. Оно обращается в равенство тогда и только тогда, когда точка B лежит на отрезке AC. Это эквивалентно тому, что сумма площадей треугольников AOB и BOC равна площади треугольника AOB, т. е. ac sin 120 = = (ab + bc) sin 60. Учитывая, что sin 120 = sin 60, получаем ac = = ab + bc, т. е. 1/a + 1/c = 1/b.

8.19. Согласно неравенству между средним арифметическим и средним геометрическим 8.20. Выделим полный квадрат:

= (a3 b 2a2 bc + c2 ab) + (b3 c 2b2 ca + a2 bc) + (c3 a 2c2 ab + b2 ca) = 8.21. Фиксируем все числа x1,..., xn, кроме одного числа xi = x.

Тогда выражение в левой части неравенства имеет вид ax + b, где a и b — постоянные числа. Оно максимально при x = 0 или при x = (или постоянно). Значит, выражение в левой части неравенства максимально в том случае, когда каждое из чисел x1,..., xn равно 0 или 1.

Предположим, что xi = xi+1 = 1 (или xn = x1 = 1). После циклической перенумерации можно считать, что x1 = x2 = 1. Рассмотрим лишь те члены, которые зависят от x1 и x2, т. е. x1 + x2 x1 x x2 x3 xn x1. При x1 = 1 и x2 = 1 это выражение равно 1 x3 xn, а при x1 = 1 и x2 = 0 оно равно 1 xn 1 x3 xn. Поэтому можно считать, что никакие два соседних числа в последовательности x1, x2,..., xn, x1 не равны одновременно 1. Тогда количество единиц не превосходит [n/2], а выражение в левой части не превосходит количества единиц.

8.22. Требуемое неравенство легко преобразуется к виду a2 b2 c (a + b + c) 2abc(ab + bc + ac) 2abc(a + b + c) + (a2 c + b2 a + c2 b) + + abc(a2 c + b2 a + c2 b) + (ab + bc + ac) 0. Но левая часть этого неравенства равна ab(b+1)(ac1)2 +bc(c+1)(ab1)2 +ac(a+1)(bc1)2.

8.23. Неравенство эквивалентно неравенству ab + ad < < ab + bc, т. е. ad < bc. А неравенство < эквивалентно нераb+d d венству ad + cd < bc + cd, т. е. ad < bc.

8.24. Если x = y, то требуемое неравенство очевидно. Если x > y числитель и знаменатель положительны, а при x < y отрицательны.

8.25. По условию a b > 0 и a/b > 1. Поэтому (a/b)ab > 1, т. е. aab > bab. Это неравенство эквивалентно требуемому.

8.26. О т в е т: да, верно. Чтобы это доказать, рассмотрим многочлен Числа x1,..., xn являются его корнями. Поэтому достаточно проверить, что если x < 0, то f(x) = 0. Но если x > 0, то З а м е ч а н и е. Условий >0 и >0 не достаточно для того, чтобы комплексные числа x и x были положительны. Например, x +x4 (1x5 )+(1x)>0. Если x 1, то x9 (x3 1)+x(x3 1)+1>0.

Кроме того, 1 xy = |1 xy|.

8.29. Ясно, что Если x > 1, то оба выражения в скобках положительны, а если 0 < x < 1, то отрицательны.

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

8.31. Докажем сначала, что если m и n — натуральные числа одной чётности, то Это неравенство легко преобразуется к виду (xm ym )(xn yn ) 0.

Если числа m и n нечётные, то из неравенства x y следуют неравенства xm ym и xn yn, а из неравенства x y следуют неравенства xm ym и xn yn. Если же числа m и n оба чётные, то из неравенства x2 y2 следуют неравенства xm ym и xn yn.

Из этих неравенств следует требуемое.

8.35. Точки, в которых стоят числа 1 и n, разбивают окружность на две дуги. На каждой дуге сумма разностей соседних чисел равна n 1 (если мы идём от n к 1), а сумма модулей чисел не 8.36. По условию (xi a)(xi b) 0 и xi > 0, поэтому + xi a + b. Складывая такие неравенства, получаем ab + xi Домножим обе части этого неравенства на x* и воспользуемся тем, получим Это неравенство эквивалентно требуемому.

8.37. Рассмотрим многочлен P(x) = 4(x + 1)(x 1/2)2 = (x + 1) (4x2 4x + 1) = 4x3 3x + 1. Ясно, что P(xi ) 0. Сложив неравенства P(x1 ) 0,. .., P(xn ) 0, получим 3(x1 +... + xn ) + n 0, т. е. x1 +... + xn n/3.

8.38. На геометрическом языке это неравенство означает, что расстояние между эллипсом x2 + 4y2 = 4 и гиперболой xy = 4 не меньше 1,6. При доказательстве удобно пользоваться именно геометрической формулировкой. Мы будем доказывать следующее Касательная к эллипсу x2 + 4y2 = 4 в точке 2 параллельна касательной к гиперболе xy = 4 в точке (2 2, 2), и квадрат расстояния между этими касательными равен 1,6.

Обратившись к рис. 8.1, несложно убедиться, что из этого следует требуемое утверждение.

Согласно задаче 1.26 касательная к эллипсу x2 + 4y2 = 4 в точке 2, 2 задаётся уравнением 2x + 2 2y = 4, т. е.

а касательная к Прямые, заданные уравнениями (1) и (2), параллельны. Расстояние между ними равно высоте h прямоугольного треугольника с катетами 2 и 2 опущенной на гипотенузу. Ясно, что h = ab/c, где a = 2, b = 2 2 и c = a2 + b2. Таким образом, h2 = 1,6, что и требовалось.

8.39. Значение A(x) не изменяется при любой перестановке переменных, поэтому можно считать, что x1 x2 x3 x4 x5.

В таком случае A1 (x) + A2 (x) = (x1 x2 )[(x1 x3 )(x1 x4 )(x1 x5 ) так как x1 x2 0, x1 x3 x2 x3 0 и т. д. Аналогично доказывается, что A4 (x) + A5 (x) 0. Ясно также, что A3 (x) представляет собой произведение двух неположительных и двух неотрицательных сомножителей, поэтому A3 (x) 0.

8.40. Можно считать, что x1 x2... x100 > 0. Если x1 100, то x1 + x2 + x3 > 100. Поэтому будем считать, что x1 < 100. Тогда 100 x1 > 0, 100 x2 > 0, x1 x3 0 и x2 x3 0, поэтому Следовательно, x1 + x2 + x3 > 100.

8.41. Применим индукцию по n. При n = 2 нужно доказать неравенство a2 + 2ab + b2 < 2a2 + 2b2, которое эквивалентно очевидa n + bn “ a+b ”n+1 “ an +bn ”“ a+b ” an+1 +bn+1 +an b+abn доказать, что an b + abn < an+1 + bn+1. Это неравенство эквивалентно 8.42. Применим неравенство задачи 8.41 при n = 3, a = 8.43. Пусть n — натуральное число. Тождество Пусть m — натуральное число, причём m> n. Тогда (ym 1)/m> > (yn 1)/n при y > 0, y = 1. Положим y = x1/n, где x > 0, x = 1. Тогда (xm/n 1)/m > (x 1)/n, т. е. xm/n 1 (x 1) > 0. Мы получили требуемое неравенство для a = m/n > 1.

Чтобы получить остальные неравенства, поступим следующим образом. Для a > 1 положим xa = x1b = yb1, где b = 1 a < и y = x1. Тогда неравенство xa ax + a 1 > 0 перепишется в виде Положим теперь b = 1/a и y = xa (здесь снова a > 1 и x > 0). Тогда неравенство xa ax+a1>0 перепишется в виде y yb + 1>0, 8.44. Воспользуемся неравенством из задачи 8.43 б), положив x = m + 1 и a = 1/n. В результате получим (m + 1)1/n < 1 + m/n.

Аналогично (n + 1)1/m < 1 + n/m. Значит, 8.45. Положим x = A/B, a = 1/p и 1 a = 1/q. Тогда Остаётся воспользоваться результатом задачи 8.43.

З а м е ч а н и е. По поводу других доказательств см. задачи 26.23 (случай p > 1) и 28.43.

Сложив такие неравенства для i = 1,..., n, получим В случае, когда p < 1, доказательство аналогично.

8.47. Пусть p > 1. Ясно, что Согласно неравенству Гёльдера (задача 8.46) где q = p/(p 1), т. е. 1/p + 1/q = 1. Запишем такое же неравенство для второй суммы и сложим оба этих неравенства. В результате получим Это неравенство эквивалентно требуемому.

В случае, когда p < 1, доказательство аналогично.

ВЫЧИСЛЕНИЕ СУММ И ПРОИЗВЕДЕНИЙ

9.1. Арифметическая и геометрическая прогрессии 9.1. Пусть a1,..., an — арифметическая прогрессия. Докажите, что 9.2. Пусть a1,..., an — арифметическая прогрессия с положительными членами. Докажите, что Десятичную дробь = 0,a1 a2 a3... называют периодической, если ak+n = ak для всех k N; число n называют длиной периода. Если N = 1, то дробь называют чисто периодической. Для десятичных дробей с ненулевой целой частью используется та же самая терминология. Для периодической десятичной дроби используется запись 0,a1 a2... aN1 (aN aN+1... aN+n1 ).

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

По поводу обратного утверждения см. задачу 17.1.

9.4. Рационально ли число 0,1234567891011... (подряд записаны все натуральные числа)?

9.5. Докажите, что любое число вида nk, где n и k — натуральные числа, отличные от 1, можно представить в виде суммы n последовательных нечётных чисел.

9.6. Найдите сумму 1 + 2x + 3x2 +... + (n + 1)xn.

9.7. Пусть a, a + d, a + 2d,... — бесконечная арифметическая прогрессия, причём a, d > 0. Докажите, что из неё можно выбрать бесконечную подпоследовательность, являющуюся геометрической прогрессией, тогда и только тогда, когда число a/d рационально.

9.8. Имеется 4n положительных чисел, таких, что из любых четырёх попарно различных можно составить геометрическую прогрессию. Докажите, что среди этих чисел найдётся n одинаковых.

9.9. Дана геометрическая прогрессия, знаменатель которой — целое число (не равное 0 и 1). Докажите, что сумма любого числа произвольно выбранных её членов не может равняться никакому члену этой прогрессии.

9.2. Изменение порядка суммирования 9.10. Докажите, что если n = p + q 1, то (a1 +a2 +...+ap )+(a2 +...+ap+1 )+...+(anp+1 +...+an )= =(a1 +a2 +...+aq )+(a2 +...+aq+1 )+...+(anq+1 +...+an ).

9.11. Числа a1, a2,..., an таковы, что сумма любых семи последовательных чисел отрицательна, а сумма любых одиннадцати последовательных чисел положительна. При каком наибольшем n это возможно?

Сумму 1 + 2 + 3 +... + n можно вычислить следующим способом.

Сложим равенства (k + 1)2 = k2 + 2k + 1 для k = 1, 2,..., n. В результате после сокращения получим (n + 1)2 = 1 + 2S1 (n) + n, где 9.12. Вычислите таким же способом суммы S2 (n) = 12 + 118 Глава 9. Вычисление сумм и произведений 9.13. а) Докажите, что Ck Sk (n) + Ck1 Sk1 (n) +... + C1 S1 (n) + S0 (n) = б) Докажите, что при фиксированном k сумма Sk (n) является многочленом степени k + 1 от n со старшим коэффиnk+ 9.14. а) Пусть S=C1 S2k1 (n)+C3 S2k3 (n)+C5 S2k5 (n)+..., причём последнее слагаемое в этой сумме равно Ck Sk (n)k при нечётном k и Ck1 Sk+1 (n) при чётном k. Докажите, что б) Докажите, что S2k1 (n) — многочлен степени k от n(n + 1) (при фиксированном k).

следнее слагаемое в этой сумме равно Ck+1 S0 (n) при чётk ном k и Ck+1 S1 (n) при нечётном k. Докажите, что S = 9.16. Найдите сумму 9.17. а) Докажите, что для любого простого числа p > числитель дроби делится на p.

б) Докажите, что для любого простого числа p > 3 числитель дроби делится на p2.

дробь, причём число 6k 1 простое. Докажите, что p делится на 6k 1.

9.19. Пусть p > 2 — простое число, ak — остаток от делеp3 p 9.5. Вычисление одной суммы двумя способами 9.20. По окружности в произвольном порядке расставлено a плюсов и b минусов. Пусть p — количество пар стоящих рядом плюсов, q — количество пар стоящих рядом минусов.

Докажите, что a b = p q.

ность арифметической прогрессии. Поэтому рассматриваемая сумма равна 9.2. Заметим, что где d — разность арифметической прогрессии. Поэтому рассматриваемая сумма равна 9.3. Ясно, что 0,a1 a2... aN1 (aN aN+1... aN+n1 ) = a1 a2... aN1 10N+1 + 120 Глава 9. Вычисление сумм и произведений число.

9.4. Предположим, что это число рационально. Тогда согласно задаче 17.1 оно записывается периодической десятичной дробью 0,a1 a2 a3..., где ak+n = ak для всех k N (n — длина периода). Выберем m достаточно большим, чтобы число 10m+2n было записано после aN. Тогда получим, что, с одной стороны, период состоит из одних нулей, а с другой стороны, период содержит единицу.

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

равнялось nk, нужно положить a + n 1 = nk1, т. е. a = nk1 n + 1.

Ясно, что число a при этом нечётно.

9.6. Чтобы получить требуемую сумму, нужно сложить 1 + x + В результате получим 9.7. Пусть a/d = m/n, где m и n — натуральные числа. При всех натуральных k число (1 + n)k 1 делится на n, поэтому число bk = a(1 + n)k = a + bk d принадлежат данной арифметической прогрессии.

Пусть a + kd, a + ld, a + md — последовательные члены геометрической прогрессии, причём k < l < m. Тогда (a + ld)2 = (a + kd) (a + md), т. е. a(2l k m) = d(km l2 ). Остаётся проверить, что 2l k m = 0. Пусть 2l k m = 0. Тогда km l2 = 0. Поэтому (k m)2 = (k + m)2 4km = 4l2 4l2 = 0, что противоречит условию k < m.

9.8. Покажем, что среди данных чисел не может быть больше четырёх попарно различных чисел. Объединим равные числа в группы, выберем в каждой группе по одному числу и расположим выбранные числа в порядке убывания: a > b > c > d > e >...

Числа a, b, c, d по условию образуют геометрическую прогрессию.

Но ab > cd и ac > bd, поэтому ad = bc, т. е. d = bc/a. Те же самые рассуждения показывают, что e = bc/a.

9.9. Каждый член геометрической прогрессии представляется в виде aqn, n 0. Случай, когда q = 1, очевиден, поэтому будем считать, что q = 1. Предположим, что существуют различные целые неотрицательные числа k1, k2,..., km+1 (m 2), для которых Пусть l1 < l2 <... < lm+1 — это числа k1, k2,..., km+1, записанные в порядке возрастания. Перепишем равенство (1) в виде После сокращения на aql1 получим Левая часть равенства равна 1, а правая часть делится на целое число ql2 l1, абсолютная величина которого строго больше 1. Получено противоречие.

9.10. Первую сумму можно записать в виде (ai +...+ai+p1 )=

PP PP PP PP

тате мы получили вторую сумму.

+ (a7 +... + a17 ). Поэтому n < 17.

При n = 16 такая последовательность существует: 5, 5, 13, 5, 5, 5, 13, 5, 5, 13, 5, 5, 5, 13, 5, 5.

9.12. Сложив равенства (k + 1)3 = k3 + 3k2 + 3k + 1 для k = 1, 2,...

..., n, получим (n + 1)3 = 1 + 3S2 (n) + 3S1 (n) + n. Значит,..., n, получаем (n + 1)4 = 1 + 4S3 (n) + 6S2 (n) + 4S1 (n) + n. Значит, 4S3 (n) = (n + 1)4 n(n + 1)(2n + 1) 2n(n + 1) (n + 1) = n2 (n + 1)2.

9.13. а) С одной стороны,... + C1 j + 1) = Ck Sk (n) + Ck+1 Sk1 (n) +... + C1 S1 (n) + S0 (n).

122 Глава 9. Вычисление сумм и произведений б) Достаточно воспользоваться формулой из задачи а) и применить индукцию по k. Нужно лишь учесть, что Ck = k + 1.

9.14. а) С одной стороны, С другой стороны, эта сумма равна сумме выражений вида 9.15. С одной стороны, Преобразуем последнее равенство, воспользовавшись тем, что 13 +... + (2n 1)3 = n2 (2n2 1).

9.17. а) Рассматриваемую сумму можно разбить на слагаемые сле приведения таких дробей к общему знаменателю получаем одно из чисел 2, 3,. .., p 1.

б) Рассматриваемая дробь равна где Нужно доказать, что M делится на p.

Согласно теореме Вильсона (задача 31.15 а) (p 1)! 1 (mod p), поэтому xk2 1 (mod p). Теперь легко убедиться, что, когда k пробегает значения 1, 2,...,. Действительно, k2 пробегает все квадратичные вычеты. Для каждого k можно выбрать k так, что kk 1 (mod p). Ясно, что k2 тоже пробегает все квадратичные вычеты и k x (mod p).

Это число делится на p.

9.18. Сначала заметим, что Число слагаемых в последней сумме чётно, поэтому слагаемые можно сгруппировать в пары По условию число 6k 1 простое. Поэтому сумма нескольких дробей с числителями 6k 1 является дробью, числитель которой делится на 6k 1.

9.19. Покажем, что kp + (p k)p делится на p2. Действительно, (xy)p =yp +pxyp1 +..., где многоточием обозначены члены, делящиеся на x2. В нашем случае (p k)p kp + pkp1 p kp (mod p2 ), поэтому kp + (p k)p делится на p2.

124 Глава 9. Вычисление сумм и произведений Число p простое, поэтому если 1 k p 1, то оба числа kp и (p k)p на p не делятся. Значит, ak + apk = p2. Рассматриваемая сумма разбивается на (p 1)/2 слагаемых вида ak + apk, поэтому она равна p2 (p 1)/2.

9.20. Запишем между соседними плюсами число +2, между соседними минусами запишем 2, а между соседними плюсом и минусом запишем 0. С одной стороны, сумма всех записанных чисел равна 2(a b). С другой стороны, она равна 2(p q).

МНОГОЧЛЕНЫ — I

10.1. Представьте многочлен (x+1)(x+2)(x+3)(x+4)+ в виде полного квадрата.

10.2. а) Докажите, что остаток от деления многочлена f(x) на x a равен f(a) (Безу).

б) Пусть x0 — корень многочлена f(x). Докажите, что f(x) делится на x x0.

10.3. Пусть P(x) = an xn + an1 xn1 +... + a1 x + a0 — многочлен с целыми коэффициентами. Предположим, что он имеет рациональный корень x0 = p/q, причём p/q — несократимая дробь. Докажите, что an делится на q, а a0 делится на p.

10.4. Найдите многочлен с целыми коэффициентами, корнем которого является число 2 + 3.

10.5. Найдите многочлен с целыми коэффициентами, корнем которого является число 3 2 + 3 3.

10.6. Найдите все многочлены вида xn ± xn1 ± xn2 ±...

... ± x ± 1, у которых все корни вещественны.

10.7. Определите коэффициенты, которые будут стоять при x17 и x18 после раскрытия скобок и приведения подобГлава 10. Многочлены — I ных членов в выражении 10.8. Пусть P(x) = an xn + an1 xn1 +... + a0 — многочлен с вещественными коэффициентами, причём an 1. Докажите, что если число m больше любого из чисел |an1 | + 1,...

..., |a0 | + 1, то Q(x) = P(x + m) — многочлен с положительными коэффициентами.

10.9. При делении многочлена x1951 1 на x4 + x3 + 2x2 + + x + 1 получается частное и остаток. Найдите в частном коэффициент при x14.

10.10. Пусть x1,..., xn — корни многочлена Докажите, что x1 + x2 +... + xn = an1, 1 i0 при x 0. Докажите, что если m, n > 0, то НОД(am, an ) = = ad, где d = НОД(m, n).

10.19. Докажите, что многочлен x15 1 имеет делители всех степеней от 1 до 14, т. е. для любого натурального числа k 14 найдётся многочлен степени k с целыми коэффициентами, делящий x15 1.

10.20. Докажите, что многочлен x2n + xn + 1 делится на x2 + x + 1 тогда и только тогда, когда n не делится на 3.

10.21. а) Известно, что ax3 +bx2 +cx+d, где a, b, c, d — заданные целые числа, при любом целом x делится на 5.

Докажите, что все числа a, b, c, d делятся на 5.

б) Известно, что ax4 + bx3 + cx2 + dx + e, где a, b, c, d, e — заданные целые числа, при любом целом x делится на 7. Докажите, что все числа a, b, c, d, e делятся на 7.

10.22. Докажите, что если p/q — несократимая рациональная дробь, являющаяся корнем многочлена с целыми коэффициентами, то p kq — делитель числа f(k) при любом целом k.

10.23. Докажите, что ни при каком целом A многочлен 3x2n + Axn + 2 не делится на многочлен 2x2m + Axm + 3.

10.24. Докажите, что положительный корень уравнения x(x + 1)... (x + n) = 1 меньше, чем 1/n!.

10.25. Докажите, что многочлен P(x) степени n не может иметь более n различных корней.

Число a называют корнем кратности k (k 1) многочлена P(x), если P(x) делится на (x a)k и не делится на (x a)k+1.

10.26. Докажите, что многочлен P(x) степени n не может иметь более n корней с учётом их кратностей, т. е. если a1,..., am — различные корни с кратностями k1,..., km, то 10.27. Докажите, что уравнение где a1 0, a2 0, an 0, не может иметь двух положительных корней.

10.28. Пусть f1 (x) = x2 2, fn (x) = f1 (fn1 (x)). Докажите, что для любого натурального n уравнение fn (x) = x имеет ровно 2n различных решений.

10.29. Докажите, что в произведении после раскрытия скобок и приведения подобных членов не остаётся членов, содержащих x в нечётной степени.

10.30. Какой остаток даёт x + x3 + x9 + x27 + x81 + x243 при делении на (x 1)?

10.31. В каком из выражений:

после раскрытия скобок и приведения подобных членов больший коэффициент при x20 ?

10.32. а) Найдите целое число a, при котором (x a) (x 10) + 1 разлагается в произведение (x + b)(x + c) двух множителей с целыми b и c.

б) Найдите такие отличные от нуля неравные между собой целые числа a, b, c, чтобы выражение x(x a)(x b) (x c) + 1 разлагалось в произведение двух многочленов с целыми коэффициентами.

10.9. Интерполяционные многочлены 10.33. Пусть x1,..., xn+1 — попарно различные числа.

Докажите, что существует ровно один многочлен P(x) степени не выше n, принимающий в точке xi заданное значение ai (интерполяционный многочлен Лагранжа).

10.35. Пусть a1,..., an — попарно различные числа. Докажите, что для любых b0, b1,..., bn1 система линейных уравнений имеет решение, причём ровно одно.

10.36. Даны точки x0, x1,..., xn. Докажите, что многочлен f(x) степени n, принимающий в этих точках значения f(x0 ),..., f(xn ), можно представить в виде f(x) = f(x0 ) + (x x0 )f(x0 ; x1 ) + где f(x0 ;... ; xk ) зависит только от точек x0,..., xk и значений многочлена в этих точках (интерполяционный многочлен Ньютона).

З а м е ч а н и е. Интерполяционный многочлен Ньютона удобен тем, что при добавлении к x0, x1,..., xn одной точки xn+ нужно вычислить только f(x0 ;... ; xn+1 ); остальные коэффициенты, в отличие от интерполяционного многочлена Лагранжа, пересчитывать не нужно.

10.37. Пусть R(x) = P(x)/Q(x), где P и Q — взаимно простые многочлены. Докажите, что R(x) можно представить в виде где cik — некоторые числа, A(x) — некоторый многочлен.

10.38. Докажите, что представление рациональной функции в виде, указанном в задаче 10.37, единственно.

Многочлен p(x) называют целозначным, если он принимает целые значения при всех целых x.

10.39. Докажите, что многочлен целозначный.

торого целого числа n. Тогда где c0, c1,..., ck — целые числа.

10.12. Многочлены от нескольких переменных Многочлен от n переменных x1,..., xn — это сумма мономов вида ak1...kn x11... xkn. Степень монома — это число k1 +... + kn.

Степень многочлена от нескольких переменных — это наибольшая степень (ненулевого) монома.

10.41. Докажите, что многочлен вида x200 y200 + 1 нельзя представить в виде произведения многочленов от одного только x и одного только y.

10.42. а) Существуют ли многочлены P = P(x, y, z), Q = = Q(x, y, z) и R = R(x, y, z) от переменных x, y, z, удовлетворяющие тождеству б) Тот же вопрос для тождества См. также задачу 16.10.

10.1. Равенства (x+ 1)(x+ 2)(x+ 3)(x+ 4) + 1= x4 + 10x3 +... + и (x2 + ax + b)2 = x4 + 2ax3 +... + b2 показывают, что подходящими кандидатами являются квадратные трёхчлены x2 + 5x ± 5.

Далее заметим, что (x2 + 5x + 5)2 1 = (x2 + 5x + 4)(x2 + 5x + 6) и x2 + 5x + 4 = (x + 1)(x + 4), x2 + 5x + 6 = (x + 2)(x + 3).

10.2. а) Поделим f(x) на x a с остатком. В результате получим f(x) = (x a)g(x) + r, где r — некоторое число. Положим x = a.

В результате получим f(a) = r.

б) Непосредственно следует из а), поскольку f(x0 ) = 0.

10.3. Равенство an xn + an1 x0 +... + a1 x0 + a0 = 0 после умножеn ния на qn запишется в виде an pn +an1 pn1 q+...+a1 pqn1 +a0 qn =0.

Число an pn = (an1 pn1 q +... + a1 pqn1 + a0 qn ) делится на q, причём по условию p и q не имеют общих делителей. Следовательно, an делится на q. Число a0 qn = (an pn + an1 pn1 q +... + a1 pqn1 ) делится на p, причём p и q не имеют общих делителей. Следовательно, a0 делится на p.

10.5. Несложные вычисления показывают, что где = 3 6( 2+ 3 и 3 36( 4+ 3 9). Поэтому x9 15x6 87x 10.6. Пусть x1,..., xn — корни многочлена xn + an1 xn1 + + an2 xn2 +.P, где ai = ±1. Согласно теореме Виета x1 +... + xn = с одной стороны, |x1 | = m | 1 | = 2m 3/2 > 1, а с другой стороны, |x1 | = n | 1 | = 2n 2/3 < 1. Снова приходим к противоречию.

10.25. Пусть a — корень многочлена P(x). Поделим P(x) на x a с остатком. В результате получим P(x) = (x a)R(x) + b.

При этом b = P(a) = 0. Значит, многочлен P(x) делится на x a.

Если a1,..., am — корни многочлена P(x), то он делится на (x a1 )... (x am ), поэтому n m.

10.26. Многочлен P(x) делится на (x a1 )k1... (x am )km, поэтому k1 +... + km n.

10.27. Перепишем данное уравнение в виде При x > 0 функция f(x) = + 2 +... + n монотонно убывает, поэтому она не может принимать значение 1 при двух различных положительных значениях x.

10.28. Функция f1 (x) монотонно убывает от 2 до 2 на отрезке [2, 0] и монотонно возрастает от 2 до 2 на отрезке [0, 2].

Поэтому уравнение f1 (x) = x имеет корень x1 (2, 0) и корень x2 = 2. Кроме того, уравнение f1 (x) = 0 имеет два корня ±x. Функция f2 (x) поочерёдно монотонно возрастает в пределах от до 2 на следующих четырёх отрезках: [2, x ], [x, 0], [0, x ], [x, 2]. Поэтому на каждом из этих отрезков по крайней мере одно решение имеет уравнение f2 (x) = x и ровно одно решение имеет уравнение f2 (x) = 0. Значит, для функции f3 (x) получаем 23 интервалов монотонности и т. д. В результате получаем, что уравнение fn (x) имеет по крайней мере 2n решений. Но больше 2n решений оно не может иметь, потому что степень многочлена fn (x) равна 2n.

10.29. Рассматриваемое произведение является многочленом P(x), обладающим следующим свойством: P(x) = P(x).

10.30. О т в е т: 6. Пусть x + x3 + x9 + x27 + x81 + x243 = P(x) (x 1) + r. Положив x = 1, получим r = 6.

10.31. О т в е т: в выражении (1 + x2 x3 )1000. Пусть P(x) = = (1 x2 + x3 )1000 и Q(x) = (1 + x2 x3 )1000. Коэффициент при x у многочлена P(x) такой же, как у P(x)=(1x2 x3 )1000, а у многочлена Q(x) такой же, как у Q(x) = (1 + x2 + x3 )1000. Ясно, что у многочлена (1 + x2 + x3 )1000 коэффициент при x20 больше, чем у многочлена (1 x2 x3 )1000. Действительно, у первого многочлена член p20 x20 равен сумме нескольких членов вида (x2 )n (x3 )m, где 2n + 3m = 20, а у второго многочлена член q20 x20 равен сумме тех же самых членов, но со знаком (1)n+m. Во втором случае встречаются члены со знаком минус, например, при m = и n = 7.

10.32. а) Пусть (x a)(x 10) + 1 = (x + b)(x + c). Положив x = b, получим (b + a)(b + 10) = 1. Числа a и b целые, поэтому числа b + a и b + 10 тоже целые. Число 1 представляется в виде произведения двух целых множителей двумя способами.

Соответственно получаем два варианта: 1) b + 10 = 1 и b + a = 1;

2) b + 10 = 1 и b + a = 1. Поэтому a = 8 или a = 12. В первом случае (x 8)(x 10) + 1 = (x 9)2, а во втором случае (x 12)(x 10) + 1 = (x 11)2.

б) Пусть x(x a)(x b)(x c) + 1 = P(x)Q(x), где P(x) и Q(x) — многочлены с целыми коэффициентами. Ясно, что P(x) и Q(x) — многочлены со старшим коэффициентом 1. При x = 0, x = a, x = b и x = c имеет место равенство P(x)Q(x) = 1, т. е. либо P(x) = 1 и Q(x) = 1, либо P(x) = 1 и Q(x) = 1. В обоих случаях P(x) Q(x) = 0. Степень многочлена P(x) Q(x) строго меньше четырёх, поэтому P(x) = Q(x) для всех x. Таким образом, x(x a)(x b)(x c) = P2 (x) 1 = (P(x) + 1)(P(x) 1). Поэтому (x b)(x c) = ±2 (мы не различаем решения, отличающиеся лишь перестановкой чисел a, b, c). Следовательно, a = b + c и bc = 2. В результате получаем следующие наборы значений (a, b, c): (1, 2, 3), (1, 2, 3), (1, 2, 1), (2, 1, 1). Им соГлава 10. Многочлены — I ответствуют следующие разложения многочлена x(x a)(x b) 10.33. Единственность многочлена P следует из того, что разность двух таких многочленов обращается в нуль в точках x1,...

..., xn+1 и имеет при этом степень не выше n. Ясно также, что следующий многочлен обладает всеми требуемыми свойствами:

10.34. Пусть P(x) — интерполяционный многочлен Лагранжа степени Тогда Коэффициент при xn у этого многочлена равен С другой стороны, если m n, то P(x) = xm. Поэтому 10.35. Пусть Pi (t) = p0i + p1i t + p2i t +... + pn1,i tn1 — интерполяционный многочлен Лагранжа, принимающий значение 1 при t = ai и значение 0 при t = aj, где j = i. Умножим данные уравнения на p0i, p1i,..., pn1,i и сложим их. В результате получим Pi (a1 )x1 +... + Pi (an )xn = p0i b0 +... + pn1,i bn1, т. е. xi = p0i b0 +...

... + pn1,i bn1. Единственность решения доказана. Остаётся проверить, что так мы действительно получаем решение, т. е.

при k = 0, 1,..., n 1. Для этого достаточно доказать, что ai Pi (t) = tk при указанных k. Но это очевидно: при k n i= не выше n 1, обращающийся в нуль при t = a1,..., an.

10.36. Должны выполняться следующие равенства:

f(x1 ) = f(x0 ) + (x1 x0 )f(x0 ; x1 ), f(x2 ) = f(x0 ) + (x2 x0 )f(x0 ; x1 ) + (x2 x0 )(x2 x1 )f(x0 ; x1 ; x2 ) и т. д. Из этих равенств немедленно получаем выражения для f(x0 ; x1 ), f(x0 ; x1 ; x2 ) и т. д.

10.37. Поделив P на Q с остатком, можно перейти к дроби S/Q, где степень S меньше степени Q. Пусть Q= Q1 Q2, где Q1 и Q2 — взаимно простые многочлены. Тогда можно выбрать многочлены a(x) и b(x) так, что a(x)Q1 (x) + b(x)Q2 (x) = 1. Поэтому В полученных дробях нужно снова поделить с остатком числитель на знаменатель и т. д. После нескольких таких операций придём к сумме многочлена A(x) и нескольких дробей вида p(x)/(x a)n, где p(x) — многочлен степени меньше n. Остаётся записать многочлен p(x) в виде 10.38. Для данного ai выберем наибольшее k, для которого встречается дробь, cik = 0. Покажем, что число cik опреk делено однозначно. Действительно, после умножения на (x ai )k получаем равенство вида где f(x) — рациональная функция, в знаменателе которой нет множителей x ai, т. е. значение f(ai ) определено. Подставив в равенство (1) x = ai, получим, что cik равно значению рациональной функции R(x)(x ai )k при x = ai. cik 10.39. При k = 1 это очевидно. Предположим теперь, что многочлен Ck целозначный. Легко проверить, что Следовательно, при всех целых m, n разность является целым числом. Остаётся заметить, что Ck+1 = 0.

10.40. Индукцией по k легко доказать, что любой многочлен pk (x) степени k можно представить в виде где c0, c1,..., ck — некоторые числа. Действительно, Поэтому если pk (x) = axk +..., то многочлен pk (x) ak!Ck имеет степень не выше k 1 и к нему можно применить предположение индукции. Таким образом, нужно лишь доказать, что числа c0, c1,..., ck целые. Докажем это индукцией по k. База индукции:

k = 0. По условию многочлен p0 (x) = c0 принимает целое значение при x = n, поэтому число c0 целое. Предположим теперь, что требуемое утверждение доказано для многочленов степени не выше k.

Пусть многочлен принимает целые значения при x = n, n + 1,..., n + k + 1. Рассмотрим многочлен Он принимает целые значения при x = n, n + 1,..., n + k. Поэтому числа c0, c1,..., ck целые, а значит, число тоже целое.

10.41. Предположим, что существуют многочлены f(x) = a0 xn + + a1 xn1 +... + an и g(y) = b0 ym + b1 ym1 +... + bm, для которых f(x)g(y) = x200 y200 + 1. Положив x = 0, получим an g(y) = 1, т. е. g(y) = 1/an при всех y. Положив y = 0, аналогично получим, станта, а функция x200 y200 + 1, очевидно, не является константой.

10.42. а) Система уравнений x y + 1= 0, y z 1= 0, z 2x+ 1= = 0 имеет решение (x, y, z) = (1, 2, 1). При таких значениях переменных левая часть рассматриваемого выражения обращается в нуль. Поэтому таких многочленов P, Q, R не существует.

поэтому (f + g + h)7 = 1. Выражение в левой части этого равенства представляет собой сумму слагаемых вида fa gb hc, где a + b + c = 7;

в частности, одно из чисел a, b, c не меньше 3. Сгруппируем те слагаемые, для которых a 3. В результате получим выражение вида f3 P. Среди оставшихся слагаемых сгруппируем те, для которых b 3. Получим выражение вида g3 Q. Для оставшихся слагаемых c 3, т. е. их сумма имеет вид h3 R. В результате мы получили требуемое тождество f3 P + g3 Q + h3 R = 1.

ТРИГОНОМЕТРИЯ

11.1. Неравенства и сравнение чисел 11.1. Докажите, что sin < < tg для 0 < < и n 2, то 11.3. Сравните числа tg 55 и 1,4.

11.4. Докажите, что если 0 <, 11.5. Докажите, что сумма принимает как положительные, так и отрицательные значения.

11.6. Докажите, что если для любого угла выполняется неравенство 11.8. Пусть A — произвольный угол, B и C — острые углы. Всегда ли существует такой угол X, что 11.2. Тригонометрические тождества 11.9. Упростите выражение 11.10. Докажите, что 11.11. Докажите, что 11.12. Найдите соотношение между 11.13. Решите уравнение 11.14. Решите уравнение 11.15. Найдите все действительные решения уравнения 11.16. Решите уравнение связанные с правильными многоугольниками При решении задач этого параграфа полезна следующая геометрическая задача.

11.18. Докажите, что сумма векторов, идущих из центра правильного многоугольника в его вершины, равна нулевому вектору.

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

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

а) cos 36 cos 72 = 1/2;

11.21. Докажите, что 11.5. Вычисление сумм и произведений 11.24. Докажите, что:

б) Докажите, что 11.26. Докажите, что 11.27. Докажите, что 11.28. Докажите, что 11.29. а) Докажите, что cos + cos( + x) + cos( + 2x) +...

11.30. а) Докажите, что cos n = Tn (cos ) и sin(n + 1) = = Un (cos ) sin, где Tn и Un — многочлены степени n.

б) Докажите, что sin(2k + 1) = sin Pk (sin2 ), где Pk — многочлен степени k.

11.31. Докажите, что sin(2k + 1) 11.7. Вспомогательные тригонометрические функции 11.32. Решите систему уравнений 11.33. Решите систему уравнений 11.34. а) Пусть x1,..., xn — попарно различные положительные числа, n 3. Докажите, что среди них можно выбрать два числа xi и xj, для которых б) Пусть x1,..., xn — попарно различные числа, n 3.

Докажите, что среди них можно выбрать два числа xi и xj, для которых 11.35. Докажите, что для любого положительного числа x и любого натурального числа n имеет место неравенство 1 > = 1,4.

11.4. Из формулы для тангенса разности двух углов следует, что 0<, < Ясно, что После приведения этих дробей к общему знаменателю получим дробь, числитель которой равен cos( + )(1 + cos( )) 0 при 0<, Знаменатель дроби при таких, положителен.

11.5. Предположим, что сумма принимает только положительные значения при всех x. Заменив x на x + получим, что выражение принимает положительные значения при всех x. Сложив эти выражения, получим, что сумма принимает положительные значения при всех x. Затем повторим те же самые рассуждения, последовательно заменяя x на x +, x +, x +, x +. В результате получим, что cos 32x принимает положительные значения при всех x. Но при x = выражение cos 32x принимает значение 1. Получено противоречие.

11.6. Согласно задаче 11.29 б) cos k + cos 2 k +... + cos n k = получим a1 a2... an n.

11.7. Возьмём на окружности радиуса 1 с центром O точки K, A и B так, что AOK = и BOK = (рис. 11.1). Опустим из точки A перпендикуляр AH на прямую OK.

Пусть C — точка пересечения этоC Сравнение площадей сектора OAB и треугольника OAC показывает, что ( ) < OH · (tg tg ). Сравнение Из двух полученных неравенств следует, что условию cos B cos C > 0. Кроме того, sin B sin C + cos B cos C = cos(B C) 1 и cos A 1. Поэтому 11.9. Покажем, что tg 20 + tg 40 + 3 tg 20 tg 40 = 3, т. е.

Каждый из рассматриваемых арктангенсов меньше поэтому их сумма меньше Если угол заключён между 0 и и его тангенс равен 1, то этот угол равен 11.11. Пусть tg = 1/5. Дважды воспользовавшись равенством 11.12. О т в е т: arcsin cos arcsin x + arccos sin arccos x =.

Пусть arcsin cos arcsin x = и arccos sin arccos x =. Тогда arcsin x, и 0 sin arccos x 1, поскольку 0 arccos x Далее, = ± cos ; cos = sin arccos x, поэтому arccos x = и x= = cos = ± sin. Из того, что cos = sin (= ±x), следует, Положим t = sin x. Учитывая, что cos2 x = 1 t2, получаем уравнение 4t3 7t + 3 = 0. Это уравнение имеет корни t1 = 1, t2 = 1/ и t3 = 3/2. Последний корень нам не подходит.

Положим t = tg x. Учитывая, что sin 2x =, получаем уравt нение т. е. 2(1 + t)t = 0 (по условию t = 1). Это уравнение имеет корни t1 = 1 и t2 = 0.

Если мы рассмотрим данное уравнение как квадратное уравнение относительно x, то его дискриминант будет равен 4(sin2 (xy)1).

Дискриминант должен быть неотрицательным, поэтому sin2 (xy) 1, т. е. sin(xy) = ±1. Решения уравнения x2 ± 2x + 1 = 0 имеют вид x = 1. Далее, если sin(y) = ±1, то sin y = 1.

11.16. Положим x = sin и y = cos. Рассматриваемое уравнение эквивалентно системе уравнений При условии x2 + y2 = 1 первое уравнение эквивалентно уравнению Подберём так, чтобы левую часть можно было представить в виде произведения двух линейных множителей. Согласно задаче 5. для этого необходимо, чтобы выполнялось равенство Несложно проверить, что это уравнение имеет корень = 3.

Чтобы получить разложение выражения 3xy 3x2 + 4x y 1, прежде всего заметим, что 3xy 3x2 = 3x(y x). Далее, Поэтому нужно положить a = 1 и b = 1. В итоге получаем, что исходное уравнение эквивалентно уравнению 11.17. О т в е т: 63. Прежде всего отметим, что число положительных корней равно числу отрицательных корней, а ещё есть корень 0. Поэтому достаточно убедиться, что число положительных корней равно 31. Если sin x = x/100, то |x| = 100|sin x| 100.

Рассмотрим графики функций y = x/100 и y = sin x. Участок оси Ox от 0 до 100 содержит 15 отрезков длиной 2 и один отрезок длиной меньше 2. Рассматривая указанные графики, легко убедиться, что на первом отрезке длиной 2 есть один корень данного уравнения, а на каждом из остальных 14 отрезков длиной 2 есть два корня. Вычисления показывают, что длина последнего отрезка больше поэтому на нём тоже есть два корня. Всего получаем положительный корень.

11.18. Сумма векторов, идущих из центра правильного n-угольника в его вершины, переходит в себя при повороте на угол 2/n.

А единственный вектор, который переходит в себя при повороте на угол 2/n, — это нулевой вектор.

11.19. Возьмём правильный n-угольник, вписанный в окружность радиуса 1 с центром в начале координат. Повернём его так, чтобы одна его вершина попала в точку (1, 0). Рассмотрев проекции суммы векторов, идущих из центра правильного n-угольника в его вершины, на оси x и y, получим равенства а) и б); нужно только учесть, что sin 0 = 0 и cos 0 = 1. Если же этот n-угольник повернуть на угол, то получим равенство в).

б) Возьмём правильный 7-угольник с центром в начале координат, одна из вершин которого расположена в точке (1, 0).

Рассмотрев проекцию на ось x суммы векторов, идущих из начала координат в вершины 7-угольника, получим требуемое.

11.21. При n = 2m + 1 сумма из задачи 11.19 б) состоит из чётного числа слагаемых. Эти слагаемые разбиваются на пары 11.22. Нужно доказать, что 11.24. а) Применим формулу из задачи 11.23 для n = 2 и = = 2/7. В результате получим, что требуемое произведение равно sin(16/7) 8 sin(2/7) б) Решается аналогично а). Нужно лишь заметить, что sin(16/9) = sin(2/9).

= 2 ctg 2.

б) Согласно задаче а) Сложив эти равенства, получим требуемое.

11.26. Ясно, что Поэтому 11.27. Докажем сначала, что Разберём отдельно случай чётного и нечётного n. Если n = 2k, щения в равенстве (1) этих равных множителей остаётся произведение одинаковых множителей. Если n = 2k + 1, то нужно Заменим в левой части равенства (1) каждый множитель sin на 2 cos sin. После сокращения на получим требуемое.

11.28. а) Пусть S — искомая сумма синусов. Воспользовавшись тождеством 2 sin x sin y = cos(x y) cos(x + y), получим Затем воспользуемся тождеством cos x cos y = 2 sin sin.

б) Пусть S — искомая сумма косинусов. Воспользовавшись тождеством 2 cos x sin y = sin(x + y) sin(x y), получим 11.29. а) Сложим тождества для k = 0, 1, 2,..., n. В результате получим требуемое.

б) Для = 0 и x = формула из задачи а) даёт равенство При этом (n + 1/2) + /2 = (n + 1) = 2k. Остаётся заметить, что если сумма двух углов равна 2k, то сумма синусов этих углов равна нулю; кроме того, sin = 0, так как 0 < < 11.30. а) Ясно, что U0 (x) = 1, U1 (x) = 2x и T1 (x) = x. Кроме того, формулы показывают, что Un (x) = xUn1 (x) + Tn (x) и Tn+1 (x) = xTn (x) Un1 (x)(1 x2 ).

б) Используя полученные рекуррентные соотношения, легко проверить, что T2k+1 (x) = xak (x2 ) T2k (x) = bk (x2 ) U2k+1 (x) = xck (x2 ), U2k (x) = dk (x2 ), где ak, bk, ck, dk — многочлены степени k. Поэтому U2k (cos x) = dk (cos2 x) = dk (1 sin2 x) = Pk (sin2 x).

11.31. Согласно задаче 11.30 б) Pk — многочлен степени k. Далее, если =, то sin(2k + 1) = = 0. Поэтому задаче 23.7 в) 11.32. Первое уравнение можно переписать в виде y = (ясно, что x = ±1). Пусть x = tg. Тогда y = tg 2. Аналогично z = tg 4 и x = tg 8. Таким образом, tg 8 = tg. Поэтому т. е. 7 = k, где k — целое число. Наоборот, если 7 = k, то tg 8 = tg и мы получаем решение данной системы уравнений.

Всего получаем 7 различных решений, соответствующих углам 11.33. О т в е т: (1/3, 1/2, 1) и (1/3, 1/2, 1).

ла x, y, z имеют одинаковые знаки, причём если (x, y, z) — решение системы, то (x, y, z) — тоже решение. Поэтому достаточно найти положительные решения.

tg( /2) = z. Тогда и — углы треугольника, стороны которого относятся как tg и tg = 1 (можно воспользоваться, например, формулой Соответствующая ему пара чисел xi и xj обладает требуемым свойством.

= tg( i j ). Будем считать, что x1 <... < xn. Тогда числа 2 1, равна Значит, среди них есть положительное число, не превосn.

ходящее Соответствующая ему пара чисел xi и xj обладает требуемым свойством.

11.35. Выберем на оси Ox точку A = (x, 0), а на оси Oy выберем точки Bk = (0, k), k = 0, 1,... Рассмотрим треугольник Bk1 ABk.

т. е. x = (k 1)2 + x2 · k2 + x2 (sin k ). Поэтому тить, что 1 +... + n < 11.36. Согласно определению многочлена Чебышева cos n = = Tn (cos ), причём Tn (x) = 2n1 xn +... (задача 32.30). Поэтому f( ) = a0 + a1 T1 (x) + a2 T2 (x) +... + an Tn (x), где x = cos.

Наоборот, пусть задан многочлен P(x) = b0 + b1 x +... + bn xn.

Равенства cos = cos, cos 2 = 2 cos2 1, cos 3 = 4 cos 3 cos,... позволяют получить выражения cos = cos, cos2 = в выражении для cos то мы записываем для cosk то выражение, которое уже было получено ранее. Так мы получим выражения Заменив в многочлене P(x) каждый моном x на получим соответствующий тригонометрический многочлен.

11.37. а) Тригонометрический многочлен n-й степени представляет собой сумму слагаемых вида cos k, 0 k n. Поэтому достаточно проверить, что Действительно, согласно задаче 11. б) Согласно задаче а) среднее арифметическое чисел f(0), их модулей не меньше |an |. Но если среднее арифметическое чисел не меньше |an |, то одно из них не меньше |an |.

11.38. Согласно задаче 11.36 многочлену P(x) соответствует тригонометрический многочлен f( ) со старшим коэффициентом 1/2n1, для которого f( ) = P(cos ). Согласно задаче 11. |P(x0 )| = |f( 0 )| 11.39. Рассмотрим функцию g( ) = 2 sin f(x). Воспользовавшись тождеством получим g( ) = an sin(n + 1/2) h( ), где поэтому |h( )| < an. Таким образом, если sin(n + 1/2) = 1, то g( ) > 0, а если sin(n + 1/2) = 1, то g( ) < 0.

l = 0, 1,..., n, лежит ровно один корень уравнения g( ) = 0. Всего получаем n корней, причём = 0 не корень. Значит, для всех этих обращается в нуль только при = 0), т. е. они являются также и корнями тригонометрического многочлена f( ).

УРАВНЕНИЯ В ЦЕЛЫХ ЧИСЛАХ

Натуральные числа a, b, c называют пифагоровой тройкой, если a2 + b2 = c2. Пифагорову тройку называют примитивной, если у чисел a, b, c нет общего делителя.

12.1. Докажите, что если a, b, c — пифагорова тройка, то одно из этих чисел делится на 3, другое (или то же самое) делится на 4, третье — на 5.

12.2. Пусть a, b, c — примитивная пифагорова тройка.

Докажите, что одно из чисел a или b чётно, а другое нечётно.

12.3. Пусть a, b, c — примитивная пифагорова тройка, причём число a чётно. Докажите, что существуют взаимно простые числа m и n, для которых a = 2mn, b = m2 n2, 12.4. Пусть a, b, c — примитивная пифагорова тройка.

Докажите, что ab делится на 12.

12.5. Пусть a, b, c — примитивная пифагорова тройка.

Докажите, что число ab/2 (площадь прямоугольного треугольника с катетами a и b) не может быть полным квадратом.

12.6. Решите в целых числах уравнение 2xy + 3x + y = 0.

12.7. Решите в целых числах уравнение 160 Глава 12. Уравнения в целых числах 12.8. Решите в целых числах уравнение 12.9. Решите в натуральных числах уравнение 2x +7=y2.

12.10. Пусть p > 2 — простое число. Докажите, что число 2/p можно единственным способом представить в виде 1/x + 1/y, где x и y — различные натуральные числа.

12.11. Пусть n — натуральное число. Докажите, что количество решений уравнения 1/x + 1/y = 1/n в натуральных числах равно количеству делителей числа n2.

12.12. а) Найдите все натуральные числа x, y, z, для которых б) Найдите все натуральные числа x, y, z > 1, для которых 12.13. а) Найдите все решения уравнения x2 + y2 + z2 = = 2xyz в натуральных числах.

б) Найдите все решения уравнения x2 +y2 +z2 +u2 =2xyzu в натуральных числах.

12.14. Решите в целых числах уравнение 12.15. Решите в натуральных числах уравнение 2n + 12.16. Найдите все решения уравнения xy = yx :

а) в натуральных числах;

б) в рациональных числах.

12.3. Нахождение некоторых решений 12.17. а) Докажите, что для любого натурального n уравнение an + bn = cn+1 имеет бесконечно много различных решений в натуральных числах.

б) Докажите, что если m и n — взаимно простые натуральные числа, то уравнение an + bn = cm имеет бесконечно много решений в натуральных числах.

12.4. Доказательство конечности числа решений 12.18. Докажите, что для любого натурального числа n уравнение x3 + y3 = n имеет конечное число целочисленных решений.

Уравнение x dy = 1, где d — натуральное число, свободное от квадратов (т. е. число, не делящееся на квадрат натурального числа, отличного от 1), называют уравнением Пелля.

12.19. Докажите, что уравнение x2 2y2 = 1 имеет бесконечно много решений в натуральных числах.

12.20. Пусть d — натуральное число, свободное от квадратов. Докажите, что существует константа C, для которой неравенство |x2 dy2 | < C имеет бесконечно много целочисленных решений.

Решение уравнения Пелля в натуральных числах с минимальным y1 будем называть фундаментальным решением.

12.21. Докажите, что уравнение Пелля для любого натурального d (свободного от квадратов) имеет бесконечно много решений в натуральных числах. Более того, если (x1, y1 ) — фундаментальное решение, то любое решение (xn, yn ) имеет вид 12.22. Докажите, что если d 3 (mod 4), то уравнение x2 dy2 = 1 не имеет решений в натуральных числах.

12.23. Докажите, что если d — простое число, причём d 1 (mod 4), то уравнение x2 dy2 = 1 имеет решение в натуральных числах.

162 Глава 12. Уравнения в целых числах 12.24. Докажите, что если уравнение x2 dy2 = 4 имеет решение с нечётными x и y, то уравнение X2 dY2 = имеет решение в натуральных числах.

См. также задачи 31.37 и 35.11– 35.13.

Уравнением Маркова называют уравнение где числа m, n и p натуральные.

12.25. Докажите, что уравнение Маркова имеет бесконечно много решений.

12.26. Докажите, что все решения уравнения m2 + n2 + + p2 = mnp в натуральных числах имеют вид 3m1, 3n1, 3p1, где m1, n1, p1 — решение уравнения Маркова.

12.27. Докажите, что если k = 1 или 3, то уравнение x2 + y2 + z2 = kxyz не имеет решений в натуральных числах.

12.28. Докажите, что если m, n, p — решение уравнения Маркова, то числа m, n и p взаимно просты.

12.1. Согласно задаче 4.42 остаток от деления квадрата целого числа на 3 и на 4 равен 0 или 1, а остаток от деления на 5 равен 0, 1 или 4. Используя только остатки 1 и 4, нельзя добиться выполнения равенства a2 + b2 = c2. В случае делимости на 3 и на это завершает доказательство. В случае делимости на 4 мы получаем, что либо все три числа a, b, c чётны, либо одно из чисел a и b чётно, а другое нечётно. Первый случай можно не разбирать, поскольку доказательство достаточно провести для примитивных пифагоровых троек. Таким образом, остаётся доказать, что если для целых чисел a1, b1, c1 выполняется равенство то число a1 чётно. Равенство (1) можно переписать в виде Числа c1 (c1 + 1) и b1 (b1 + 1) чётны, поэтому число a1 тоже чётно.

12.2. Числа a и b не могут быть оба чётными, потому что иначе число c тоже было бы чётным. Числа a и b не могут быть оба нечётными, потому что иначе число a2 + b2 делилось бы на 2, но не делилось бы на 4.

и n — взаимно простые числа. При этом c = m2 + n2 и b = m2 n2.

12.4. Нужно доказать, что для любых взаимно простых натуральных чисел m и n число mn(m + n)(m n) делится на 6. Если m и n нечётны, то m + n чётно. Если m и n не делятся на 3, то либо числа m и n дают одинаковые остатки при делении на 3 (тогда m n делится на 3), либо одно из них при делении на 3 даёт остаток 1, а другое даёт остаток 2 (тогда m + n делится на 3).

12.5. Предположим, что существуют взаимно простые натуральные числа m и n, для которых mn(m + n)(m n) = s2, где s — натуральное число. Будем считать, что s — наименьшее из всех чисел, для которых имеет место равенство такого вида. Числа m, n, m + n, m n попарно взаимно простые, поэтому m = x2, числа. Числа m и n разной чётности, поэтому числа z и t нечётz2 + t и = =. Таким образом, для числа y/2 тоже имеет место равенство указанного вида. Поэтому y2 4s2, т. е. y 4x2 y2 (x2 y2 )(x2 + y2 ). Получено противоречие.

12.6. О т в е т: (0, 0), (1, 1), (1, 3), (2, 2). Данное уравнение можно переписать следующим образом: (2x + 1)(2y + 3) = 3.

Остаётся решить 4 системы уравнений: 2x + 1 = 1, 2y + 3 = 3;

2x+ 1= 3, 2y + 3= 1; 2x+ 1= 1, 2y + 3= 3; 2x+ 1= 3, 2y + 3= 1.

12.7. Рассматриваемое уравнение можно переписать в виде (x 5)(y + 3) = 18. Его решения в целых числах соответствуют представлениям числа 18 в виде произведения двух целых чисел.

12.8. О т в е т: (0, 0), (0, 1), (1, 0), (1, 2), (2, 1), (2, 2). Рассмотрим данное уравнение как квадратное уравнение относительно x:

Дискриминант этого уравнения равен 3y2 + 6y + 1. Он отрицателен при y 3 и при y 1. Поэтому для y получаем три возможных значения: 0, 1, 2. Для каждого из этих значений получаем уравнение, которое легко решается.

12.9. О т в е т: x = 1, y = 3. Проверим, что других решений нет.

Ясно, что 22 + 7 = 11 — не квадрат, поэтому можно считать, что x 3. Тогда 2x делится на 8, а значит, y2 7 (mod 8). Но, как легко проверить, квадрат целого числа при делении на 8 может давать только остатки 0, 1 и 4.

12.10. Равенство 1/x + 1/y = 2/p можно переписать в виде p(x + y) = 2xy. Значит, одно из чисел x и y делится на p. Например, x = px. Тогда px + y = 2x y, т. е. (2x 1)y = px. Если x = 1, то y = p и x = p, а по условию числа y и x различны. Если же x > 1, то 2x 1 > x, поэтому y < p. Кроме того, числа 2x 1 и x взаимно просты. Значит, 2x 1 = p и y = x. В итоге получаем y = x = 12.11. Данное уравнение можно записать в виде n2 = (x n) (y n). Каждому делителю d числа n2 соответствует решение 12.12. а) Будем считать, что x y z. Тогда 1 = 1/x + 1/y + 1/z 3/z, поэтому z 3. Ясно также, что z = 1.

Если z = 3, то 1/x + 1/y = 2/3 и при этом 1/x + 1/y 2/y, значит, y 3. Но y z = 3, поэтому y = 3 и x = 3.

Если z = 2, то 1/x + 1/y = 1/2 и при этом 1/x + 1/y 2/y, значит, 2 y 4. Ясно, что y = 2. При y = 3 получаем x = 6, а при y = получаем x = 4.

б) Снова будем считать, что x y z. Тогда z < 3, т. е. z = 2.

Поэтому 2/y > 1/x + 1/y > 1/2, значит, y < 4. Если y = 2, то число x может быть произвольным. Если y = 3, то 1/x > 1/6, т. е. x = 3, или 5.

12.13. а) Пусть x = 2m x1, y = 2n y1, z = 2k z1, где числа x1, y1, z нечётны. Можно считать, что m n k. Тогда обе части уравнения можно сократить на (2m )2. В результате получим Если n = m = k, то согласно задаче 4.42 б) при делении на 4 число в левой части этого равенства даёт остаток 3, а число в правой части даёт остаток 0 или 2. Если же k > m, то число в левой части даёт остаток 1 или 2, а число в правой части — остаток 0. Значит, уравнение не имеет решений в натуральных числах.

б) Число x2 + y2 + z2 + u2 чётно, поэтому среди чисел x, y, z, u чётное число нечётных чисел.

Если все числа x, y, z, u нечётны, то x2 + y2 + z2 + u2 0 (mod 4), но при этом 2xyzu не делится на 4.

Если ровно два из чисел x, y, z, u нечётны, то x2 + y2 + z2 + u не делится на 4, а 2xyzu делится на 4.

Поэтому все числа x, y, z, u чётны, т. е. x = 2x1, y = 2y1, z = 2z1, u = 2u1. Мы получаем уравнение x2 + y2 + z2 + u2 = 8x1 y1 z1 u1. Теперь заметим, что (2k + 1)2 = 4k(k + 1) + 1 1 (mod 8). Поэтому если все числа x1, y1, z1, u1 нечётны, то x2 + y2 + z2 + u2 не делится на 8.

А если ровно два из этих чисел нечётно, то x2 + y2 + z2 + u2 не делится даже на 4. Значит, x1 =2x2, y1 =2y2, z1 =2z2, u1 =2u2, и мы получаем уравнение x2 + y2 + z2 + u2 = 32x2 y2 z2 u2. Снова повторив те же самые рассуждения, получим, что x, y, z, u делятся на 2n при всех n, чего не может быть.

Пусть x3 2y3 4z3 = 0, где x, y, z — целые числа. Тогда число x чётно. После замены x= 2x1 получаем уравнение 8x3 2y3 4z3 = 0.

Сократим на 2: 4x3 y3 2z3 = 0. Значит, число y чётно. После замены y = 2y1 получаем уравнение 4x3 8y3 2z3 = 0. Снова сократим на 2: 2x3 4y3 z3 =0. Значит, число z чётно. После замены z = 2z1 получаем уравнение x3 2y3 4z3 = 0, которое имеет такой же вид, как и исходное уравнение. Поэтому снова можно доказать, что числа x1, y1, z1 чётны и т. д. Но это возможно лишь в том случае, когда x = y = z = 0.

Если n = 1, то m = 1. Рассмотрим теперь случай, когда n > 1.

В этом случае 3m 1 (mod 4). Отметим, что 32k+1 = 3 · 9k 3 (mod 4).

Поэтому m = 2k, а значит, (3k 1)(3k + 1) = 2n. Таким образом, числа 3k 1 и 3k + 1 — степени двойки, которые отличаются друг от друга на 2. Это возможно лишь в том случае, когда k = 1, т. е. m = и n = 3.

12.16. Всегда есть очевидное решение x = y, поэтому достаточно рассмотреть случай, когда x > y (случай x < y рассматривается аналогично). Пусть x = ky, где k > 1 — рациональное число.

Тогда (ky)y = (yk )y, поэтому ky = yk, а значит, y = k k1. Пусть Числа p и p + q взаимно простые, поэтому число y может быть рациональным лишь в том случае, когда p = aq и p + q = bq для некоторых натуральных a и b. Предположим, что q 2. Тогда aq < p + q aq + qaq1 < (a + 1)q. Приходим к противоречию, так как между числами aq и (a + 1)q не может находиться число bq = p + q.

Поэтому q = 1. Для любого натурального p числа x = (1 + 1/p)p+ и y = (1 + 1/p)p рациональны и являются решениями уравнения xy = yx. Эти числа будут целыми лишь при p = 1. В этом случае 12.17. а) Перепишем уравнение в виде c = (a/c)n + (a/c)n. Будем искать решения вида a = a1 c и b = b1 c, где a1 и b1 — натуральные числа. Тогда c = an + bn, a = a1 (an + bn ) и b = b1 (an + bn ). Легко проверить, что мы действительно получили решение.

б) Выберем натуральные числа p и q так, что pm qn = (это можно сделать с помощью алгоритма Евклида). Положим c = (an + bn )p, a = a1 (an + bn )q и b = b1 (an + bn )q, где a1 и b1 — произвольные натуральные числа. Тогда an + bn = (an + bn )(an + bn )qn = = (an + bn )pm = cm.

12.18. Пусть x + y = a и x2 xy + y2 = b. Тогда ab = n. Число n можно лишь конечным числом способов разложить на множители a и b, поэтому получаем конечное число систем уравнений x + y = a, x2 xy + y2 = b. Выразим y из первого уравнения и подставим во второе. В результате получим уравнение x2 x(a x) + (a x)2 = b, которое имеет не более двух решений.

Каждому целочисленному решению x этого уравнения соответствует одно целочисленное решение исходной системы, а именно (x, a x).

12.19. Нетрудно найти одно решение этого уравнения, например, x1 = 3 и y1 = 2. Равенство x2 2y2 = 1 можно записать в виде Ясно, что тогда Кроме того, согласно задаче 6.22 (x1 ± y1 2)n = xn ± yn 2. Поэтому т. е. (xn, yn ) — тоже решение, причём xn+1 > xn, yn+1 > yn.

12.20. Применим задачу 17.11 для = d. В результате получим, что существует бесконечно много пар взаимно простых чисел x, y, для которых |x y d| < 1/y. В таком случае а значит, Таким образом, в качестве константы C можно взять число 2 d + 12.21. Согласно задаче 12.20 для некоторого целого k уравнение x2 dy2 = k имеет бесконечно много натуральных решений.

Выберем два различных решения x2 dy2 = k и x2 dy2 = k, для которых y1 y2 (mod k). Тогда x1 ±x2 (mod k), поэтому решения можно выбрать так, что x1 x2 (mod k). В таком случае и x1 x2 dy1 y2 x2 dy2 0 (mod k), x1 y2 x2 y1 0 (mod k). При этом x1 y2 x2 y1 = 0, поскольку иначе Положим X = k1 (x1 x2 dy1 y2 ) и Y = k1 (x1 y2 x2 y1 ) = 0. Тогда X2 dY2 = 1, т. е. пара (X, Y) — решение уравнения Пелля.

Пусть (x1, y1 ) — фундаментальное решение уравнения Пелля.

Тогда 1 + y1 d)n (x1 y1 d)n = 1, поэтому пара (xn, yn ), где xn + yn d = (x1 + y1 d), тоже является решением уравнения Пелля, поскольку согласно задаче 6.22 xn yn d = (x1 y1 d)n. Ясно также, что xn yn d = (x1 + y1 d). Остаётся проверить, что любое натуральное решение (x, y) представляется в виде x + y d = = (x1 + y1 d), где n — натуральное число. Предположим, что натуральное решение (x, y) не представляется в таком виде. Тогда можно выбрать натуральное число n так, что После умножения на (x1 + y1 d)n = xn yn d получим Положим (x + y d)(xn yn d) = X + Y d. Чтобы прийти к противоречию, достаточно показать, что X2 dY2 = 1 и X > 0, Y > 0.

По условию (x + y d)(x y d) = 1 и (xn yn d)(xn + yn d) = 1, поэтому (X + Y d)(X Y d) = т. е. X dY = 1. Кроме того, X + Y d > 1, а значит, 0 < X Y d < 1. Следовательно, 168 Глава 12. Уравнения в целых числах 12.22. Ясно, что d имеет простой делитель p = 4k + 3. Предположим, что x2 dy2 = 1. Тогда x2 1 (mod p), поэтому число является квадратичным вычетом по модулю p. С другой стороны, если p = 4k + 3 — простое число, то согласно задаче 31.36 число не является квадратичным вычетом по модулю p.

12.23. Пусть (x1, y1 ) — фундаментальное решение уравнения Пелля x2 dy2 = 1. Из условия d 1 (mod 4) вытекает, что x2 y 1 (mod 4). Следовательно, x1 1 (mod 2) и y1 0 (mod 2). Перепишем равенство x2 dy2 = 1 в виде По условию число d простое, поэтому либо либо В первом случае получаем b2 da2 = 1. Во втором случае получаем a2 db2 = 1, что противоречит минимальности решения (x1, y1 ).

12.24. Положим X+Y d= Согласно задаче 4.42 г) x 1 (mod 8) и y 1 (mod 8). Следовательно, d2 5 (mod 8), а значит, x2 + 3dy2 1 + 15 0 (mod 8) и 3x2 + dy2 3 + 5 0 (mod 8), поэтому числа X и Y целые. Кроме того, 12.25. Предположим сначала, что среди чисел m, n и p есть равные, например, n = p. Тогда m2 + 2n2 = 3mn2, т. е. 3m = (m/n)2 + 2.

Следовательно, m = dn, где d — целое число. При этом d2 + 2 = 3nd, т. е. d(3n d) = 2. Поэтому d = 1 или 2. В обоих случаях n = 1.

В результате получаем решения (1, 1, 1) и (2, 1, 1). Назовём их особыми.

Возьмём теперь неособое решение (m, n, p), для которого числа m, n, p попарно различны, и рассмотрим квадратный трёхчлен Ясно, что f(m) = 0, т. е. один корень квадратного трёхчлена f равен m. Второй его корень m можно найти по теореме Виета:

m = 3np m. Ясно, что при этом (m, n, p) — решение уравнения (12.1). Покажем, что наибольшее из чисел n и p заключено между m и m. Пусть для определённости n > p. Тогда Это как раз и означает, что n заключено между m и m.

Аналогичным образом по решению (m, n, p) можно построить решения (m, n, p) и (m, n, p ).

Предположим, что m — наибольшее из чисел m, n, p. Тогда Таким образом, при переходе от решения (m, n, p) к решению (m, n, p) наибольшее из трёх чисел уменьшается, а при переходе к решениям (m, n, p) и (m, n, p ) увеличивается.

Если начинать с решения (1, 1, 1), то получим следующее дерево решений:

Это дерево содержит все решения, поскольку от произвольного решения после нескольких уменьшений максимума мы перейдём к особому решению. Под уменьшением максимума мы подразумеваем переход от решения (m, n, p), где m > max(n, p), к решению (m, n, p).

12.26. Достаточно доказать, что если m2 + n2 + p2 = mnp, то числа m, n и p делятся на 3. Если целое число не делится на 3, то его квадрат при делении на 3 даёт остаток 1. Поэтому если m2 + n2 + p2 не делится на 3, то среди чисел m, n и p есть как делящиеся на 3, так и не делящиеся на 3. Но тогда m2 + n2 + p2 = mnp 170 Глава 12. Уравнения в целых числах делится на 3, чего не может быть. Значит, m2 + n2 + p2 делится на 3, причём числа m, n и p одновременно либо все делятся на 3, либо все не делятся на 3. Второй вариант невозможен, потому что mnp = m2 + n2 + p2 делится на 3.

12.27. Случай k = 2 — это задача 12.13 а). Поэтому будем предполагать, что k > 3. Предположим, что x2 + y2 + z2 = kxyz, где x, y, z — натуральные числа. Прежде всего покажем, что эти числа попарно различны. Пусть y = z. Тогда x2 = kxy2 2y2 = (kx 2)y2, поэтому x = противоречит неравенству k > 3.

Пусть для определённости x > y > z. Рассмотрим квадратный трёхчлен f(t) = t2 kyzt + y2 + z2. Один его корень равен x, а второй корень x по теореме Виета равен kyz x. Ясно, что образом, по решению x, y, z мы построили новое решение x, y, z, для которого x, y, z < x. Повторяя эту конструкцию x раз, приходим к противоречию. (Решающее отличие от уравнения Маркова состоит в том, что здесь нет решения с двумя одинаковыми числами, поэтому операцию уменьшения решения можно применять бесконечно много раз.) 12.28. Предположим, что m = dm1, n = dn1 и p = dp1, где d > 1.

Тогда m2 + n2 + p2 = 3dm1 n1 p1. Но согласно задаче 12.27 уравнение x2 + y2 + z2 = kxyz не имеет решений в натуральных числах при k > 3.

ИНДУКЦИЯ

13.1. Вычислите сумму 13.2. Вычислите сумму 13.4. Докажите, что 13.5. Докажите неравенство 13.7. Докажите, что при целом n 2 и |x| < 13.8. Докажите, что 13.9. а) Докажите, что для любого > 0 и любого натурального n > 1 выполняется неравенство (1 + )n > 1 + n.

б) Докажите, что если 0 < 1/n и n — натуральное число, то выполняется неравенство (1 + )n < 1 + n + n2 2.

13.10. Докажите неравенство между средним арифметическим и средним геометрическим для n положительных чисел: (a1 a2... an )1/n (a1 +... + an )/n, причём равенство достигается, только если a1 =... = an.

13.11. Докажите, что 3n > n3 для любого натурального n = 3.

13.12. Докажите неравенство 13.13. Некоторые из чисел a1, a2,..., an равны +1, остальные равны 1. Докажите, что 13.14. На кольцевой автомобильной дороге стоит несколько одинаковых автомобилей. Известно, что если весь бензин, находящийся в автомобилях, слить в один из них, то этот автомобиль сможет проехать по всей кольцевой дороге и вернуться на прежнее место. Докажите, что хотя бы один из этих автомобилей сможет проехать по всей кольцевой дороге в заданном направлении, забирая по пути бензин у остальных автомобилей.

13.15. Докажите, что любую дробь m/n, где 0 < m/n < 1, можно представить в виде где 0 < q1 < q2 <... < qr, причём число qk делится на qk1 при См. также задачу 20.11.

13.1. Докажем индукцией по n, что рассматриваемая сумма равна 1. При n = 2 получаем очевидное равенство =1.

Предположим, что требуемое равенство доказано для некоторого n. Тогда 13.2. Докажем индукцией по n, что рассматриваемая сумма равна (n + 1)! 1. При n = 1 получаем очевидное равенство 1 · 1! = 2! 1. Предположим, что требуемое равенство доказано для некоторого n. Тогда 13.3. База индукции очевидна, поэтому нужно лишь проверить равенство После деления на m + 1 и умножения на 4 получаем очевидное равенство m2 + 4(m + 1) = (m + 2)2.

= An Bn. Равенство A1 = B1 очевидно, поэтому An = Bn для всех n.

13.5. Применим индукцию по k. При k = 1 требуемое неравенство очевидно: 1· 1!< 2!. Предположим, что для некоторого k требуемое неравенство выполняется. Тогда 1 · 1! + 2 · 2! + 3 · 3! +... + k · k! + + (k + 1) · (k + 1)! < (k + 1)! + (k + 1) · (k + 1)! = (k + 2)!.

13.6. Применим индукцию по n. Сначала заметим, что (1x1 ) (1 x2 ) = 1 (x1 + x2 ) + x1 x2 > 1 (x1 + x2 ). Предположим, что 13.7. Применим индукцию по n. При n = 2 получаем (1 x)2 + + (1 + x)2 = 2(1 + x2 ) < 4. Предположим теперь, что (1 x)n + + (1 + x)n < 2n. Тогда (1 x)n+1 + (1 + x)n+1 < ((1 x)n + (1 + x)n )((1 x) + (1 + x)) < 13.8. Требуемое неравенство эквивалентно неравенству 1+ k < 1 k. Воспользовавшись неравенством из задачи 13.6, получаем 13.9. а) Покажем, что если >1+(n+1). Действительно, (1+ )n+1 =(1+ )(1+ )n > (1+ ) б) Для n = 1 требуемое неравенство выполняется. Предполоn, то выполняется неравенство (1 + )n < жим, что если 0 < n3 следует неравенство 3n+1 > (n + 1)3. По предположению индукции 3n+1 > 3n3, поэтому нужно лишь проверить неравенство 2n3 > 3n2 + 3n + 1.

При n 5 выполняются неравенства 1 < 3n < 3n2 < 2n3 /3, поэтому 3n2 + 3n + 1 < 3(2n3 /3) = 2n3.

= 2 + a.

Таким образом, требуется доказать, что Индукцией по n легко доказать, что a < 2. Поэтому следующие неравенства эквивалентны требуемому:

После возведения в квадрат получаем неравенство 36 + 12a + a2 > > 32 + 16a, т. е. (a 2)2 > 0.

13.13. Применим индукцию по n. При n=1 получаем очевидное тождество. Равенство показывает, что Нетрудно также убедиться, что в действительности всегда беa1 a2 a1 a2 a зовавшись предположением индукции, получаем требуемое тождество.

13.14. Применим индукцию по числу автомобилей n. При n = утверждение очевидно. Предположим, что утверждение доказано для n автомобилей. Рассмотрим теперь n + 1 автомобиль. Ясно, что среди них обязательно найдётся автомобиль A, который может доехать до следующего за ним автомобиля B, поскольку иначе бензина во всех автомобилях не хватило бы для того, чтобы проехать один раз по всей кольцевой дороге. Выльем бензин из B в A и уберём B. Среди оставшихся n автомобилей по предположению индукции найдётся автомобиль, который может проехать по всей кольцевой дороге, забирая по пути бензин у остальных автомобилей. Тогда тот же самый автомобиль сможет проехать по всей кольцевой дороге и в исходной ситуации, до переливания бензина из B в A. Действительно, доехать от A до B он сможет, а на всех остальных участках дороги бензина у него будет ровно столько же, сколько и в ситуации с n автомобилями.

13.15. Будем считать, что дробь m/n несократимая. Применим индукцию по m. При m = 1 доказывать нечего. Пусть m > 1. Разделим n на m с остатком, причём частное запишем в виде d0 1, а остаток запишем в виде mk, т. е. n=m(d0”1)+(mk)=md0 k, индукции дробь k/n можно представить в требуемом виде:

Поэтому дробь тоже можно представить в требуемом виде.

КОМБИНАТОРИКА

14.1. Сколькими способами можно выбрать k предметов из n различных предметов, если порядок, в котором выбираются предметы: а) учитывается; б) не учитывается.

Число Ck = называют биномиальным коэффициентом.

Удобно считать, что Ck = 0, если n < 0 или k > n.

14.3. Докажите, что Ck + Ck1 = Ck.

14.4. Сколько ожерелий можно составить из пяти белых бусинок и двух чёрных?

14.5. а) Семь девушек водят хоровод. Сколькими различными способами они могут встать в круг?

б) Сколько ожерелий можно составить из семи различных бусин?

14.6. Сколько существует различных путей на плоскости, ведущих из точки с координатами (0, n) в точку с координатами (m, m), если двигаться разрешено каждый раз либо на 1 вверх (координата y увеличивается на 1), либо на 1 влево (координата x уменьшается на 1)?

сел, если представления n = x1 +... + xm и n = y1 +... + ym считаются одинаковыми тогда и только тогда, когда x1 = y1,...

б) Тот же вопрос для представления в виде суммы натуральных чисел.

14.8. Докажите, что 14.2. Тождества для биномиальных коэффициентов 14.9. Докажите, что:

(Вандермонд).

14.11. Докажите, что Cn = (C0 )2 + (C1 )2 +... + (Cn )2.

14.12. Докажите, что C2n = 2nk2i Ck Ci+k.

14.13. Докажите, что Ck1 Ck+1 Ck = Ck Ck+1 Ck1.

14.14. Докажите, что если p + q = 1, то 14.15. Пусть P(x) — многочлен степени n, причём P(x) = = 2x для x = 1, 2,..., n + 1. Вычислите P(n + 2).

14.16. Докажите, что 14.17. Докажите, что 14.18. Докажите, что если |x| < 1, то См. также задачи 29.53, 29.54.

14.3. Бином Ньютона в арифметике 14.19. Докажите, что числа (a + 1)a 1 и (a 1)a + делятся на an+1 и не делятся на an+2.

14.20. Пусть p1 = 2, p2 = 3,... — последовательные простые числа. Докажите, что p1... pk 4pk.

14.4. Комбинаторика в арифметике 14.21. Сколько существует четырёхзначных номеров (от 0001 до 9999), у которых сумма двух первых цифр равна сумме двух последних цифр?

14.22. Сколько существует таких пар целых чисел x, y, заключённых между 1 и 1000, что x2 + y2 делится на 7?

14.23. Сколько существует натуральных чисел, меньших тысячи, которые не делятся ни на 5, ни на 7?

14.24. Сколько различных целочисленных решений имеет неравенство |x| + |y| < 100?

14.25. Сколько существует натуральных чисел x, меньших 10 000, для которых 2x x2 делится на 7?