Математика
Библиотечка физико-математической школы
С.И.Гельфанд
М.А.Гервер А.А.Кириллов Н.Н. Константинов А.Г.Кушниренно
Задачи по элементарной математике
Математика
Библиотечка физико-математической школы
Выпуск 3
С. И. Гельфанд
М. Л. Гервер
А, А, Кириллов
Н. Н. Константинов
А. Г. Кушниренко математике
Последовательности Комбинаторика
' Пределы
Задачи по элементарной
Издательство «Наука»
Главная редакция физико-математической литературы
Москва 1965
512
Г32
УДК 512
Математика
Библиотечка
физико-математической школы
Редактор серии И. М. Гельфанд
Оглавление
Предисловие
4
Задачи
Глава 1. Последовательности , . .
§ 1.	Что такое последовательность
§ 2.	Метод математической индукции .	,
§ 3.	Условия задач , » Глава 2. Комбинаторика Глава 3. Пределы . .
§ 1.	Подготовительные задачи .	. .	.
§ 2.	Задачи, связанные с определением предела .	.	.	.
§ 3.	Задачи на вычисление пределов Контрольные задачи
К главе 1	,
К главе 2	... .
К главе 3
7
7
10
14
22
30
31
36
43
49
49
52
55
Решения
57
91
116
Ответы и указания
165
167
171
Предисловие
Настоящий третий выпуск серии «Библиотечка физико-математической школы» является сборником задач для 9—10 классов.
Сборник составлен так, что он может служить и учебником по соответствующим разделам курса.
Наше изложение во многом отличается от традиционного.
Во-первых, большее внимание уделяется логической подготовке по сравнению с вычислительной.
Во-вторых, мы больше рассчитываем на самостоятельную работу учащихся. Третье существенное отличие — в отборе материала. Мы старались научить именно тому из школьной математики, что пригодится в дальнейшем в учебе и работе.
Эту книжку можно читать по-разному. Самый простой и наименее полезный способ — прочитать условия задач, прочитать и разобрать решения, а потом решить контрольные задачи. Мы считаем, что учащийся может усвоить материал и при таком пассивном способе. Но гораздо полезнее поступить так. Не заглядывая в ответы, указания и решения,
самостоятельно решить целую серию задач. Уже после этого можно сравнить полученные результаты с приведенными ответами. Затем прочитайте решения. Мы рекомендуем сделать это даже в том случае, если задачи не вызвали затруднения, так как в решениях мы часто сообщаем полезные дополнительные сведения, а иногда ставим новые вопросы.
Если такой способ работы окажется для Вас слишком трудным, Вы можете пойти по промежуточному пути; после того как несколько задач Вы не смогли решить, несмотря на ряд попыток, загляните в раздел «Ответы и указания». Если задача и после этого не выходит, прочитайте решение.
Мы будем, как и в первом выпуске, пользоваться «дорожными знаками».
Знаком «Стоянка разрешена» отмече-ны места, содержащие сведения, необходимые для понимания дальнейшего: определения, формулы и т. д. Около такого знака надо остановиться и внимательно прочитать это место.
Знак «Крутой подъем» стоит там, где содержится более трудный материал. Если это мелкий шрифт, то при первом чтении это место можно пропустить.
Особенно внимательны будьте около знака «Опасный поворот». Часто он стоит на таком месте, где на первый взгляд все кажется легким и простым. Однако, если как следует не разобраться, то это может привести в дальнейшем к серьезным ошибкам.
р
Обычно задачник служит дополнением к учебнику. При работе с нашей книжкой можно не пользоваться учебником.
Такой способ прохождения материала практикуется начиная с 1962/63 учеб
р
ного года в некоторых математических шкодах Москвы *).
Сделаем еще два замечания:
1) Вероятнее всего, вначале Вас больше заинтересует комбинаторика. Откройте книжку на стр. 22. Вы можете «без страха» начинать решать задачи прямо с главы 2 (задачи 44, 46, 501). Чтобы решить, например, задачу 44, не надо знать даже алгебру, и Вы спокойно можете предложить эту задачу (как и задачу о погремушках) своему младшему брату или сестре.
2) В книге есть много задач, в которых нужно доказать некоторое утверждение для любого п. Не пугайтесь этого! Проверьте сначала это утверждение для п=2, 3, 4; при этом Вы заметите ряд закономерностей, которые помогут Вам (и это самое главное) понять и прочувствовать условие задачи, а иногда и подскажут способ решения (см., например,' задачу 2)
Работа над книгой распределялась так: главу 1 написал С. И. Гельфанд, главу 2 — М. Л. Гервер и А. Г Кушни-ренко, главу 3 — А. А. Кириллов, Н Н. Константинов участвовал в подборе задач и в редактировании всех глав.
Авторы выражают благодарность ряду товарищей, оказавших ту или иную помощь в работе над книжкой: И. М. Гельфанду, Е. Г. Глаголевой, Е. Б. Дынкину, В. С. Рябенькому, Б. В. Шабату, а также ученикам 11-Г и 10-Г классов школы № 7 и 10-Е и 10-Ж классов школы № 2 (Москва), в особенности М. Подольной, А. Рыскину, Е. Шац и М. Шифрину.
*) См. статью М. Л. Гервер, Н. Н. Константинов, А. Г. Кушниренко «Задачи по алгебре и анализу» в сборнике «Обучение в математических школах», Выпуск 1, Москва, «Просвещение», 1965. Часть материала статьи вошла в состав этой книжки.
ГЛАВА 1
ПОСЛЕДОВАТЕЛЬНОСТИ
§ 1. Что такое последовательность
Будем говорить, что задана последовательность чисел
Mj, W2» •••>
если каждому натуральному п *) поставлено в соответствие некоторое число ип.
Приведем примеры последовательностей:
Пример 1. 1,1,1, I, .1.
Здесь ил=1— каждому п ставится в соответствие число 1.
Пример 2. Последовательность нечетных чисел:
Здесь иц — 2п—L
•) Натуральными называют целые положительные числа.
Пример 3. Последовательность задана формулой
,, _ п<п + П
““	2	’
а)	Выпишите эту последовательность.
(Ответ: 1, 3, 6, 10, 15, 21, 28, ...)
б)	Найдите u100, и„_3 и ип+1.
(Ответ:
мюо — 5050;
„	_ (п~3)(п-3+1)	(п — 3)(п — 2)
2---------------2	’
,,	_ (Я + 1) (п + 2) ,
«п+1--------------- •)
Формула, задающая ип, называется формулой общего члена последовательности. Например, последовательность
1,	4, 9, 16, 25, 36, 49, ...
можно коротко записать формулой общего члена: и„ = п2.
Пример 4. Напишите формулу общего члена для следующей последовательности:
2,	5, 8, 11, 14, 17, ...
Пример 5. Закономерность, по которой выписаны члены последовательности, не всегда легко обнаружить. Например, пусть дана последовательность:
0, — , 13, —, 62,	171,...
’2	2	2
Найдите какое-нибудь правило, определяющее последовательность.
(Ответ: формула для общего члена этой последовательности имеет, например, вид:
Пример 6. Для последовательности
3,	1, 4, 1, 5, 9, 2, 6, 5, 3, 5, ...
вряд ли возможно написать сколько-нибудь разумную формулу общего члена. Тем не менее, нам задана последовательность по следующему правилу: на п-м месте стоит п-я цифра числа л, записанного в виде десятичной дроби (л = 3,1415926...*)). Таким образом, задано определенное правило, по которому каждому натуральному числу п поставлено в соответствие число и„— член последовательности. Например, Ui=Z, иг— = 1, u7=2.
В принципе мы можем узнать не только, какое число стоит на 1-м или 7-м месте, но и на 100-м, и на 1005-м, и вообще на любом месте. Несмотря на то, что эта последовательность не задана формулой общего члена, можно установить ряд интересных вещей.
Например, математики доказали, что эта последовательность не является периодической.
') Вы знаете из геометрии, что число л — это отношение длины окружности к диаметру. Первое значение л нашел Архимед. Он знал, что число
1	10
л заключено между ЗуиЗ—. При решении
задач в школе Вы обычно пользуетесь значением л=3,14. В более тонких расчетах берут более точное значение л, например, 3,14159. В принципе можно вычислить значение л с любой степенью точности. Впрочем, трудно представить себе задачу, в которой нужно было бы знать больше, чем десяток-другой знаков числа л. В качестве курьеза можно сказать, что один человек по фамилии Шенке потратил большую часть своей жизни на то, чтобы вычислить 707 знаков л. Недавно для интереса на электронной машине сосчитали несколько десятков шсяч знаков числа л. 11ри лом обнаружилось, что, начиная с 202 знака, в вычисления Шенкса вкралась ошибка!
Пример 7. Выпишите первые 10 членов последовательности
1, 1, 2, 3, 5,
составленной по следующему правилу! первые ее два члена равны единице («1 = 1, «2=1), а каждый член, начиная с третьего, равен сумме двух предыдущих, т. е. справедлива формула
“Я=«п-1+«П-2	(«>3).
Написать выражение для ип в этом случае можно, но не очень легко. (Члены этой последовательности называются числами Фибоначчи. См. о них еще задачу 43.)
Пример 8. Найдите первые члены последовательности
«1, «2, ...»
n-й член которой равен сумме всех на ту-* ральных чисел от 1 до п включительно.
(Решение: «1 = 1, «2=14-2 = 3, «3=14-24-3=6,	«4=14-24-34-4 = 10, ...
.... ип = 14-24-34--4-П.
Ответ: 1, 3, 6, 10, 15, 21, ...),
§ 2. Метод математической индукции
Если первый человек в очереди — женщина, и за каждой женщиной стоит женщина, то все в очереди — женщины.
Рассуждение, заключенное в этом шуточном примере, часто встречается в самых разных областях математики и носит название принципа математической индукции. Более серьезная формулировка этого принципа такова;
Имеется последовательность утверждений. Если первое утверждение верно, и за каждым верным утверждением сле
дует верное, то все утверждения в последовательности верны.
Пример 9. Пусть нужно доказать формулу
1 + 2 + 3 + -.. + п = п(п2+ ° .
Эта формула содержит целуй» последовательность утверждений;
1)	1 = — ,
2
2)	1+2 = — ,
2
3)	1 +	2 + 3 = ^,
4)	1+2 +	3 + 4 = ^,
Первое утверждение, разумеется, верно. Проверим, что за каждым верным утверждением следует верное.
Пусть утверждение k) верно, т. е. равенство
1 + 2 + 3 + .. . + k=
справедливо. Прибавим к обеим частям равенства число й+1. Получим
1 + 2 + 3 +... + * + (k + 1) =
= k(k+D k (Л+ l)(fe + 2)
Но это как раз и есть утверждение &+1), следующее за утверждением k).
Мы доказали, таким образом, что за каждым верным утверждением следует верное. В силу принципа матема
тической индукции, наша формула верна при любом k.
Эту же задачу можно решить и без использования метода математической индукции. Обозначим сумму, которую мы хотим найти, через ип. Напишем два равенства
и„ = 1 +2 + 3 + ...+ (п—2) + (п—1) +п,
ип = п+ (п—1) + (п—2) +...+3+2 +1
=	- 28
Рис 1
р
г(в нижней строке написана та же сумма, но записанная в обратном порядке). Мы получим
2ил =[1+п]+[2+(п—1)]+
+[3+ (п—2)]+...+[(п—2) +3]+ +[(л—1) +2]+[п+1].
В каждой квадратной скобке стоит число п+1, а всего таких скобок п (рис. 1). Поэтому
2и„=(п+1)+(п+1)+...+(«+!)+(«+1)== п раз
= п(п+1), МЛ+Ъ' п 2
и наше равенство доказано.
Приведем еще одну формулировку принципа математической индукции, немного отличную от первой.
Пусть имеется какое-нибудь предположение, или, как еще говорят, гипотеза, и мы хотим проверить справедливость этой гипотезы для всех натуральных п.
Допустим, что удалось доказать такие два утверждения:
а)	Наша гипотеза справедлива при п= 1.
б)	Из того, что эта гипотеза верна при n=k, тле k — произвольное нату
ральное число, следует, что она верна и при л=&+1.
Принцип математической индукции состоит в том, что из утверждения а) и б) следует справедливость нашей гипотезы для всех натуральных чисел п.
Утверждение б) носит условный характер. В нем не утверждается, что гипотеза верна для п=А+1. Оно состоит лишь в том, что если наша гипотеза верна для n — k, то она верна и для n=k+\. Мы будем называть б) индуктивным предположением.
Пример 10. Докажем, что для любого натурального п число п5—п делится на 5.
Проведем доказательство методом математической индукции.
а)	При п=1 выражение ns—п равно нулю и, значит, делится на 5.
б)	Пусть k—произвольное натуральное число. Покажем, что если при n=k число л®—п делится на 5, то (А+1)5— — (А+1) тоже делится на 5. Используя равенство
(A+l)s=&s+5£4+10£3+l062 + 5£+l
(проверьте его), представим число (fe-t-1)5—(&+1) в виде
(*+l)5-(fe+l) =
= (k5+5k* +1Ok3 +1 Ok2+5k +1) — (k +1) = = (k5—k) +5(k4+2k3+2k2+k).
Мы представили число (fe+I)5—(k+l) в виде суммы двух слагаемых. Первое из них, k5—k, делится на 5 по нашему предположению. Второе слагаемое, 5(Л4 + 2А3 + 2А2+А), также делится на 5. Сумма двух чисел, делящихся на 5, сама делится на 5, т. е. (fe + l)s—(Л+1) делится на 5.
Итак, утверждения а) и б) доказаны. Значит, по принципу математической
р
I j j j
1
Рис 2
индукции, число n5—n делится на 5 при всех натуральных п.
Существуют другие формулировки принципа математической индукции, эквивалентные данным нами. Вот одна из них:
Если:
а)	некоторое утверждение верно при л= 1;
б)	из того, что оно верно для всех n^k, следует, что оно верно и для n=k+l, то это утверждение верно для всех п.
Отличие этой формулировки от предыдущей состоит в следующем.
В пункте б) мы требуем, чтобы наше утверждение было справедливо для всех n^k, а не только для n = k.
Легко сообразить, что обе формулировки принципа математической индукции эквивалентны в том смысле, что всякая теорема, которую можно доказать, применяя метод индукции в одной форме, может быть доказана и с помощью другой его формы.
Заметим также, что доказательство утверждения а) нужно, так сказать, лишь для «затравки». Если вместо него доказать утверждение
а') о том, что наша гипотеза справедлива, скажем, для и=8, а пункт б) оставить неизменным, то из утверждений а') и б) будет следовать, что наша гипотеза верна для всех натуральных п, начиная с восьми. Именно с таким положением мы встретимся, например, в задаче 9.
§ 3. Условия задач
1.	Доказать, что при всех натуральных п выполняется равенство (рис. 2);
р+23+33+ ... + № = -"2(П4+1Г .
2.	Доказать, что при всех натуральных п выполняется равенство
— Ч---------ь ••• ч-----
1-2	2-3	n(n+D
п
п + 1 ’
3.	Вычислить сумму
—— Ч- —— ч- ... Ч-----------:.
1-4	4-7	(Зп —2)(Зп+1)
4.	Доказать, что равенство
—---------1-----!-------1-... Ч-
а(а+1)	(а+1)(а+2)
1
п
(а+п—1) (а+п)	а (а + п)
справедливо при всех натуральных п и всех а, которые не равны нулю или целому отрицательному числу.
5.	Доказать равенство
1 -1!+2-21+3.3!+ ...+п-п!= (п+1) 1—1*) (п — любое натуральное число).
6. Доказать, что равенство
п + 1
2п
справедливо при всех целых п^>2.
7.	Доказать равенство
1 —22 + 32 —42 Ч- ...Ч-(— 1)л~1п2 =
_/ lr-i»(n + l) '	’	2
8.	На сколько частей делят плоскость п прямых, никакие две из которых не параллельны и никакие три не пересекаются в одной точке.
*) Через п! (читается «эн факториал») обозначается произведение всех целых чисел от 1 до п.
8=@® S-©@©
(1= ©@@
Рис 5
9.	Доказать, что любую сумму денег, большую 7 копеек, можно уплатить без сдачи только трех- и пятикопеечными монетами (рис. 3).
10.	Доказать, что плоскость, разбитую на части п прямыми, можно закрасить черной и белой краской так, что любые две части, имеющие общую сторону, будут окрашены в разный цвет (такая раскраска называется правильной, рис. 4).
11.	Доказать, что сумма кубов трех последовательных натуральных чисел делится на 9
12.	Доказать, что для любого целого «>0.
Ц«+2	\22п+1
делится на 133.
13.	Доказать, что для любого «>-2 справедливо неравенство
(1 + а)п > 1 + па, если предположить, что а>—1 и а=£0.
14. Доказать, что для любого «>-2
Теперь мы переходим к задачам о последовательностях. Полезно посмотреть еще раз определение последовательности и примеры на стр. 7—10.
15.	Пусть последовательность задана следующим образом:
«1 = 2; «2 = 3; «„ = 3«„_x—2n„_,
при п > 2.
Доказать, что справедлива формула u^'^ + l.
16.	Пусть Ui ~ 1; nn+i — ып + &п> л—натуральное число. Доказать, что ип =(2л-1)2.
Пусть дана последовательность и\, и2, ... Составим по ней новую последовательность vt, v2, ... следующим образом: vn—u„+l—и„ при всех п. Эта последовательность называется последовательностью разностей последовательности tii, «2. — Будем обозначать нашу новую последовательность так: Див Ди2, ... (Д — заглавная греческая буква, читается «дельта»).
17.	Пусть и„ — п2. Найти формулу общего члена последовательности разностей.
18.	Даны две последовательности и\, и2, ... и v2, ... с одной и той же последовательностью разностей, т. е. такие, что Ал„ = Дип для всех п.
а)	Можно ли утверждать, что и„ = п„?
б)	Можно ли утверждать, что un=vп, если дополнительно известно, что Ui = ot?
19.	Пусть каждый член последовательности Wi, пу2, ... равен сумме соответствующих членов последовательностей их, и2, ... и vt, v2. т. е. wn —
= и„+ vn для всех п. Доказать, что в этом случае Дау„ = Д«„ + Дуд для всех п.
20.	Дана последовательность un = nk. Доказать, что общий член ее последовательности разностей выражается многочленом (k—1)-й степени от п, и найти старший коэффициент этого многочлена.
21.	Дана последовательность, у которой ип выражается многочленом k-ii
2 С. И. Гельфанд и др.
17
о
216
5
С
2
3
О 1 8 27 64 125
)1
>7
Р9
Р7
)61
PuC.J
степени от п со старшим коэффициентом Яо- Доказать, что Лял выражается многочленом (k—1)-й степени от п, и найти его старший коэффициент.
22. Дана последовательность u„=nft, где k — фиксированное положительное число. Составляется ее последовательность разностей, у полученной последовательности снова составляется последовательность разностей, и так делается k раз (рис. 5). Доказать, что в результате получится последовательность, у которой все члены равны одному и тому же числу. Какому именно?
23. Дана последовательность vn=nk. Доказать, что существует последовательность ult U2, ..., общий член которой выражается многочленом (А + 1)-й степени от п и для которой \un=vn. Найти также старший коэффициент этого многочлена.
24.	Дана последовательность и2> — Для нее составили последовательность разностей. Для получившейся последовательности снова составили последовательность разностей. Когда это проделали четыре раза, то получилась последовательность из одних нулей. Доказать, что исходная последовательность! задается многочленом 3-й степени.
25.	Про некоторую последователь-! ность иь ы2. — известно, что ее последовательность разностей vt, V2, ... выра-, жается многочленом А-й степени. Доказать, что сама последовательность «i,j и2, ... может быть задана многочленом (А+1)-й степени.
26.	Вычислить сумму l2 + 22+... + n2J
27.	Вычислить сумму
1 -2+2-34-3-4+...+«(«+!).
Арифметической прогрессией называется последовательность, у которой пл+1 — ип +d при всех п. Число d называется разностью прогрессии.
Геометрической прогрессией называется последовательность, у которой ип+1 =и п -q при всех п. Число q называется знаменателем прогрессии.
28.	а) Выразить n-й член арифметической прогрессии через первый член «1 и разность d.
б) Выразить n-й член геометрической прогрессии через первый член и\ и знаменатель q.
29.	а) Найти формулу для суммы S„ первых п членов арифметической прогрессии.
б) Найти формулу для произведения Р„ первых п членов геометрической прогрессии.
30.	а) Найти сумму первых 15 членов арифметической прогрессии, у которой л	1
первый член равен 0, а разность — .
б) Найти произведение первых 15 членов геометрической прогрессии, у которой первый член равен 1, а знамена-
Зу——— тель у 10.
31.	а) Третий член арифметической прогрессии равен 0. Найти сумму первых 5 членов.
б) Третий член геометрической про-' грессии равен 4. Найти произведение первых 5 членов.
32.	Доказать, что сумма S„ первых п членов геометрической прогрессии вы-
п" _1
ражается формулой S„=at --------.
q — 1
33.	Некто приезжает в город с очень интересной новостью и через 10 минут сообщает ее двоим. Каждый из вновь узнавших новость через 10 минут сообщает ее еще двоим (которые ее еще не знают) и т. д. *). Через сколько времени эту новость будет знать весь город, если в нем три миллиона жителей?
34.	Велосипедист и кавалерист соревновались на стадионе (рис. 6). Им нужно было пройти 5 кругов. На первый круг они затратили одинаковое время. Каждый следующий круг велосипедист проезжал в 1,1 раза медленнее, чем предыдущий. Кавалерист на каждый круг затрачивал на одну и ту же величину больше времени, чем на предыдущий. К финишу они пришли одновременно. Кто из них затратил больше времени на 5-й круг и во сколько раз?
35.	Найти сумму всех положительных нечетных чисел, не превосходящих тысячи.
36.	Найти сумму всех положительных трехзначных чисел, не делящихся ни из 2, ни на 3.
37.	Сумма S„ первых п членов по следовательности выражается формулой 5л=3л2. Доказать, что эта последовательность является арифметической прогрессией. Вычислить ее первый член и разность.
*) Конечно, до тех пор, пока в городе имеются еще не знающие этой новости.
38.	Существует ли геометрическая прогрессия, среди членов которой есть числа 27; 8; 12 (эти числа могут стоять в прогрессии не обязательно подряд и не обязательно в данном здесь порядке)? На каких местах могут стоять эти числа в прогрессии?
39.	Тот же вопрос для чисел 1; 2; 5.
40.	Квадраты 12-го, 13-го и 15-го членов арифметической прогрессии образуют геометрическую прогрессию. Найти все возможные знаменатели этой прогрессии.
41.	Найти все геометрические прогрессии, у которых каждый член, начиная с третьего, равен сумме двух предыдущих.
42.	Члены некоторой последовательности являются суммами соответствующих членов двух геометрических прогрессий. Чему равен 3-й член этой последовательности, если первые два равны О?
43.	Представить члены последовательности Фибоначчи («1 = 1;	«2=1;
кп+2 =ил+1+ыл)*) в виде суммы соответствующих членов двух геометрических прогрессий.
) См. пример 7 на стр. 10.
Г Л А В A 2
КОМБИНАТОРИКА
Р) rw О^СьИ OWOCOxT*'.
QffQO ^^-вгти £444^2. ettTli-4-l ( Hl. С^Коч иСч-мча. Н-в, 'LopumJ' ffff? 
Рис.7
В большинстве задач этой главы нужно ответить на вопрос, «сколькими способами?». Подобные ’ задачи (на подсчет числа различных комбинаций) часто называют комбинаторными,' а раздел математики, занимающийся их решением — комбинаторикой. Комбинаторные расчеты имеют большое значение в теории вероятностей, вычислительной математике, теории автоматов и математической экономике.
44.	В кухне пять лампочек. Сколько существует способов освещения?
Понятно ли, что такое способы освещения? Каждая лампа может гореть и не гореть. Два способа считаются различными, если они отличаются состоянием хотя бы одной лампы (рис. 7 и 8).
45.	Пусть имеется п ламп. Число способов освещения, при которых горят k ламп, обозначим через С*. Доказать,
что С,} С%-)-С£-j-C% — 2". , Понятно ли обозначение Сл? Что означает С5? Чему равно Св?
46.	В городе п светофоров. Каждый может находиться в одном из трех состояний (гореть красным, желтым или зеленым светом). Сколькими способами можно зажечь все светофоры?
47.	Сколькими способами можно зажечь п светофоров, из которых k могут находиться в одном из трех состояний, а остальные п—k в одном из двух?
9mu СлослЙ»
ff9V9
Pm, 8
48.	Сколько существует шестизначных чисел, не содержащих нуля и восьмерки?
49.	Каково максимальное возможное число различных автомобильных номеров, состоящих из четырех цифр и после них трех букв (рис. 9, всего в алфавите 32 буквы)?
50.	В некотором царстве каждые два человека отличаются набором зубов (рис. 10). Какова может быть наибольшая численность населения царства (максимальное количество зубов—32).
51.	В выражении (х—1) (х—2) X Х(х—3)...(х—100) раскрыты скобки и приведены подобные. Найти коэффициент при х".
52.	Сколькими способами можно представить натуральное число п в виде суммы двух натуральных слагаемых?
Задачу эту можно понимать по-разному. Можно считать, что порядок слагаемых несуществен, а можно считать, что существен. Иными словами, можно
считать, что 8 = 3 + 5 и 8 = 5 + 3 — это одно и то же разложение, а можно считать, что разные. Ответы тоже будут получаться разные. Предлагается решить обе задачи.
53.	Аналогичный вопрос о разбиении на три слагаемых (порядок существен).
Треугольником Паскаля называется такая таблица:
1 1 1
1	2	1
13	3	1
1	4	6	4	1
1	5	10	10	5	1
(по сторонам треугольника стоят единицы, а каждое из остальных чисел таблицы есть сумма двух чисел, стоящих над ним).
54.	Доказать, что в треугольнике Паскаля сумма чисел, стоящих в («+1)-й строке, равна 2".
55.	Какое наибольшее число слонов можно расставить на шахматной доске так, чтобы они не угрожали друг другу? Доказать, что число способов такой расстановки слонов есть квадрат некоторого числа.
Чтобы понять условие, нужно, конечно, знать, как ходит слон. Слон ходит по диагоналям. Например, с поля с/З слон одним ходом может попасть на любое из полей, отмеченных на рис. 11 (Ь\, с2' и т. д.). Таким образом, 2 слона угрожают друг другу, если они стоят на од-] ной диагонали.
56.	У мамы два яблока и три груши. Каждый день в течение пяти дней под
ряд она выдает по одному фрукту. Сколькими способами это может быть сделано?
57.	Аналогичная задача, когда яблок k, а груш п.
58.	Аналогичная задача, когда имеется 2 яблока, 3 груши и 4 апельсина.
59.	Сколькими способами можно расставить на шахматной доске 8 ладей так. чтобы они не били друг друга?
Ладья ходит по горизонталям и вертикалям. Например, ладья d3 угрожает всем полям вертикали d и горизонтали 3 (рис. J2).
60.	Сколькими способами из п предметов можно выбрать два?
До сих пор число способов выбрать 2 предмета из п (или число способов освещения, когда из п ламп горят 2) мы обозначали через Сп- Задача состоит в том, чтобы вычислить Сп (например, в задаче 56 уже сосчитано, что Cs?=10).
61.	Сколькими способами можно рассадить класс, если присутствует 26 человек, а мест 28?
62.	У отца есть пять попарно различных апельсинов, которые он выдает своим восьми сыновьям так, что каждый получает либо один апельсин, либо ничего. Сколькими способами это может быть сделано?
63.	Обозначим через Сп число способов, которыми можно зажечь k лампочек из п (каждая лампочка может быть в двух состояниях). Доказать, что число Сп стоит на (А+1)-м месте (п+1)-й строки треугольника Паскаля.
64.	Сколькими способами можно расставить на шахматной доске 4 ладьи так, чтобы они не били друг друга?
65.	В роте имеется 3 офицера и 40 солдат. Сколькими способами может быть выделен наряд, состоящий из одного офицера и трех солдат?
66.	Сколькими способами из п предметов можно выбрать три?
67.	Сколькими способами из п предметов можно выбрать 6?
68.	На рояле 88 клавиш. Сколько существует последовательностей из шести попарно различных звуков? (В последовательности звуки идут один за другим.) Сколько существует аккордов из шести звуков? (Аккорд получается, если любые 6 клавиш нажаты одновременно.)
69.	В каких строках треугольника Паскаля все числа нечетные?
70.	Сколько членов получится после раскрытия всех скобок в выражении: (а+1) (6+1) (с+1) (d+1) (е+1) (f+1) X X(g+1)?
71.	Сколько при этом получится членов, содержащих три буквы?
72.	В выражении (1+x + t/)20 раскрыты скобки, но не приведены подобные. Сколько членов при этом получится?
73.	В выражении (1+х5+х7)20 раскрыты скобки. Определить коэффициенты при х17 и х18 после приведения подобных.
I
74.	В выражении (1+х)Бв раскрыты скобки и приведены подобные, Найти коэффициенты при хв и л48,
75.	Доказать, что
(1 + ху = С° +	+...+
ч-сг^+с^.
Эта формула носит название бином Ньютона.
76.	Из задач 75 и 63 вытекает следующее утверждение. Пусть ад, alt а2, .... а„ — числа (п+1)-й строки треугольника Паскаля. Тогда
(1 + х)п = а0 + агх + а2х2 + ... + апх".
Докажите этот факт, опираясь непосредственно на определение треугольника Паскаля (и не пользуясь результатами задач 75 и 63).
77.	Между каждыми двумя цифрами числа 14 641 вставлено k нулей. Доказать, что полученное число — полный квадрат.
78.	В выражении (а+Ь)п раскрыты скобки и приведены подобные. Выписать член, содержащий ак.
79.	В выражении (x+y+z)n найти член, содержащий xkylt
80.	Найти: а) С° + С2 + С’ + С% + ...; б) С\ + С® -|- Сп+ ...
81.	Определить сумму коэффициентов многочлена, который получится, если в выражении (1+х—Зх2)1965 раскрыть скобки и привести подобные члены.
82.	Сколькими нулями оканчивается число И100—1?
83.	Что больше: 995°+10050 или 10150?
84.	Сколько различных делителей имеет число 2-3-5-7-11?
85.	Сколько различных делителей имеет число 10!?
86.	Сколько диагоналей можно провести в выпуклом п-угольнике?
87.	Сколько различных четных пятизначных чисел с неповторяющимися цифрами можно составить из цифр 0, 1, 3, 4, 5?
88.	Сколькими способами можно разложить в два кармана девять монет различного достоинства?
89.	В классе изучается 10 предметов. В среду шесть уроков, при этом все уроки различные. Сколькими способами можно составить расписание на среду?
90.	Сколькими способами можно распределить Зп предметов между тремя людьми так, чтобы каждый человек получил п предметов. 91
91. В комнате несколько человек, знающих хотя бы один из трех языков. Шестеро знают английский язык, шестеро — немецкий, семеро — французский. Четверо знают английский и немецкий. Трое — немецкий и французский. Двое — французский и английский. Один человек знает все три языка. Сколько человек в комнате? Сколько из них знают только английский?
92.	В библиотеке числится некоторое число читателей (т. е. людей, которые прочитали хотя бы одну книгу этой библиотеки). Про любые k книг (1 л) известно, сколько читателей прочитало их все. Как узнать, сколько читателей в библиотеке? (Всего в библиотеке п книг.)
93.	Сколько существует телефонных номеров, содержащих комбинацию 12? (Номер состоит из шести цифр.)
94.	Тот же вопрос для номеров из и цифр.
ГЛАВА 3
ПРЕДЕЛЫ
Эта глава содержит больше дополнительного материала и потребует от Вас много самостоятельной работы.
Предлагаемые здесь задачи можно разделить на две группы. Первую группу составляют задачи подготовительного раздела (кроме нескольких трудных задач, отмеченных звездочкой) и задачи основных разделов, отмеченные кружком. Те из Вас, кто хочет овладеть теорией пределов в рамках школьной программы, могут ограничиться задачами первой группы. Проверкой вам будут служить контрольные задачи №№ 33, 34а, 346, 35, 39, 40а, 40г, 43.
Задачи второй группы рассчитаны на более высокую логическую подготовку и являются введением в математический анализ. При решении этих задач особенно важна самостоятельная работа. Мы не рекомендуем здесь применять пассивный способ изучения, о котором мы говорили во введении.
§ 1. Подготовительные задачи
95.	Двум школьникам поручили вести календарь погоды. Они должны отмечать день знаком « + », если погода хорошая, и знаком «—», если погода плохая. Первый школьник поступал так. Он делал наблюдения три раза в сутки— утром, днем и вечером. Если хотя бы во время одного наблюдения шел дождь, он ставил отметку «—». В остальных случаях он ставил « + ». Второй школьник делал наблюдения в то же время, что и первый. Если хотя бы во время одного наблюдения дождя не было, он ставил « + ». В остальных случаях он ставил «—». Таким образом, каждый день погода получала одну из оценок: + + ; Ч—; —Н . Все ли эти оценки на самом деле могут встретиться?
96.	К двум школьникам из задачи 95 присоединился третий, который делает наблюдения в то же время, что и первые два, и ставит «—», если по крайней мере во время двух наблюдений шел дождь, и « + » в остальных случаях. Какие из восьми оценок + + +; +4—; +—+; —++; —;---------------+ ; +-----;
------могут на самом деле встретиться?
97.	а) Триста человек построены в 30 рядов и 10 колонн. Из каждого ряда выбрали самого высокого человека, а из этих 30 человек выбрали самого низкого. Потом из каждой колонны выбрали самого низкого человека, а из этих 10 человек— самого высокого. Кто окажется выше: самый высокий из низких, или самый низкий из высоких?
б) Изменится ли ответ, если построить людей не прямоугольником, а уг« лом, как на рис. 13 (в первых десяти колоннах по 20 человек, в следующих — по 10)?
0©0©00Оф©0
©®(ЭСНЭ<Э<Э0®@ ©®©«©@©000
©о©©ф
О© )©©
©©0©© ее®©© п
ри(.
98.	Контрольная работа называется легкой, если на каждой парте найдется ученик, который решил все задачи. Сформулируйте определение трудной контрольной.
99.	Рассмотрим два определения легкой контрольной:
а)	В каждом варианте каждую задачу решил хотя бы один ученик.
б)	В каждом варианте хотя бы один ученик решил все задачи.
Может ли контрольная быть легкой в смысле определения а) и трудной в смысле определения б)?
100.	Какие из следующих теорем верны?
1)	Если каждое слагаемое делится на 7, то и сумма делится на 7.
2)	Если каждое слагаемое не делится на 7, то и сумма не делится на 7.
3)	Если хотя бы одно слагаемое делится на 7, то и сумма делится на 7.
4)	Если сумма делится на 7, то и каждое слагаемое делится на 7.
5)	Если сумма не делится на 7, то и каждое слагаемое не делится на 7.
6)	Если сумма не делится на 7, то хотя бы одно слагаемое не делится на 7,
101 *. Пусть А и В означают какие-нибудь два утверждения. Чертой над буквой будем обозначать отрицание соответствующего утверждения (рис. 14). Например, если буквой А обозначено утверждение «в треугольнике АВС все стороны равны», то А будет означать утверждение «в треугольнике АВС не все стороны равны». Рассмотрим восемь теорем:
1.	Если А, то В.
2.	Если А, то В.
3.	Если А, то В.
4.	Если А. то В.
5.	Если В, то А,
6.	Если В, то А.
7.	Если В, то А.
8.	Если В, то А.
Известно, что теорема 1 верна. Требуется разбить остальные теоремы на три группы: в первую группу отнести теоремы, которые заведомо верны, во вторую — теоремы, которые заведомо неверны, в третью — теоремы, которые могут быть верными, а могут быть и неверными. Условимся при этом не рассматривать в качестве А и В утверждений, которые всегда неверны, и утверждений, которые всегда верны. (Например, «В треугольнике АВС все углы прямые» или «В треугольнике АВС три медианы пересекаются в одной точке».)
102.	Решить уравнения*);
а)	х+2 |х| =3,
б)	х2+3|х|—4=0,
в)	| 2х+1 |+|2х— I |=2.
вСОВЫТИЯЖ
Д	(йегё
А — 'Е+и+ь не ixSeT
В - не г>~иры~
ТЕОРЕМЫ:
103. Докажите неравенства:
А , YTVC В
а) I х + у] < | х | + | у\,
б) [х — f/|>|x| — |f/|,
в) k—f/|>lkl—kll-
Выясните в каждом из этих случаев, когда неравенство превращается в ра^ венство.
2+С^ллх. А 1 Щ£> В
А ? В
С. U
*) Величина |х| (читается «модуль икс» или- «абсолютная величина икс») определяется следую-
щим образом:	X,	если х>0,
1*1 =	0,	если. х = 0,
	—X,	если х < 0.
3 С. И. Гельфанд и др.
33
104. Верно ли, что существует такое натуральное число л, для которого:
а) ^1000< 1,001?
б)* ^<1,001?
в) п+1— V п < 0,1?
г) ]/п2+п — п < 0,1?
105. Верно ли, что существует такое число С, что при всех целых k выполняется неравенство
I 1 I С
I й4—з I
106*. Верно ли, что для любого числа С существует бесконечное множество целых чисел k, для которых выполняется неравенство
k sin k>C?
ЛОВУШКА
р
Пусть дана бесконечная последовательность {хп} *). Будем изображать члены этой последовательности точками на числовой оси (при этом может оказаться, конечно, что несколько членов последовательности попадут в одну и ту же точку; например, в последовательно-
•	1 t 1 . 1. 1
сти г,—; 1;——; ... все члены с не-
2	3	4
четным номером попадут в точку 1).
Назовем отрезок [о, Ь] на числовой оси ловушкой для последовательности {хп}, если вне этого отрезка или совсем нет членов последовательности, или их только конечное число.
Назовем отрезок [о, fc] на числовой оси кормушкой для последовательности (хп), если на этом отрезке лежит бесконечное множество членов последовательности (рис. 15).
*) Символом {хл) кратко обозначается последовательность Х|, х?, . . .,хп, , , ,
107.	а) Докажите, что всякая ловушка является кормушкой.
б) Придумайте такую последовательность и такой отрезок, который был бы кормушкой для этой последовательности, по не был бы ловушкой для нее.
108.	Даны последовательности:
. . 1	1
а)	1; — ; —
2	з
б)	1; 2; —
2
1 . > •••>
п
; 1—; 1-^-2	3	3
п
1 —
п
в)	1; —; 3; —; 5;	2л—1; —
2	4	6	2п
и отрезки
А) [~т’ 4“]’Б) 1]*В) [~2’2]-
Выясните, какие отрезки для каких последовательностей являются ловушками или кормушками.
109.	Существует ли последовательность, для которой каждый из отрезков [0, 1] и [2, 3] является:
а)	кормушкой?
б)	ловушкой?
ПО. Известно, что для некоторой последовательности каждый из отрезков [0, 1] и [9, 10] является кормушкой. Существует ли для этой последовательности:
а)	ловушка длины 1?
б)	ловушка длины 9?
111. а) Существует пость, не имеющая ни
ли последователь-одной кормушки?
б)* Существует ли последовательность, для которой любой отрезок яв ляется кормушкой?
§ 2. Задачи, связанные с определением предела
Число а называется пределом последовательности , если для любого положительного числа е (греческая буква «эпсилон») найдется такое число k, что для всех членов последовательности, у которых номер п больше k, выполняется неравенство (рис. 16)
|х„ — а\ <е.
Тот факт, что число а является пределом последовательности {хп}, запи-
lllllllllllllliy a lllllllllxi
X.
Рис.16
сывают так:
11m хп — а П->со
(читается: «предел х„ при п, стремящем-, ся к бесконечности, равен а), или так:
хп а при я -> со
-1/2, сС
(читается: «х п стремится к а при п, стре мяшемся к бесконечности»),
112°. Даны последовательности:
в) хп= (----г)"(рис- 17)1
г) х„ = logn 2.
В каждом из этих случаев укажите такое число k, чтобы при n>k выпол
нялось неравенство
А) |х„| <1, Б) |х„| <0,001, В) |х„| <0,000001.
113. а) Докажите, что если х„->апри п^-со, то любой отрезок с центром в точке а является ловушкой для последовательности {х„}.
б) Верно ли обратное утверждение?
114*. а) Докажите, что если х„->а прип->сю, то каждый отрезок с центром в точке а является кормушкой, а никакой отрезок, не содержащий точки а, не является кормушкой для последовательности {х„}.
б) Известно, что для некоторой последовательности {хп} любой отрезок с центром в точке а является кормушкой, а никакой отрезок, не содержащий точки а, не является кормушкой. Можно ли утверждать, что хп->а при п->сю?
115. Докажите, что если некоторый отрезок является кормушкой для последовательности {хп}’ то никакое число, лежащее вне этого отрезка, не может быть пределом последовательности {хп}.
116°. Какие из следующих последовательностей имеют пределы?
.__i_. JL.	_ _L	. . 1__________L-
’	2’3’	4	’	2n— 1	’ 2п ’	’
~ п 2	8	26	3я—1
б)	0; —; — ; — ; ...;-------;...,
'	3	9	27 3я
в)	1; 1 + —; 1+ — + — ; 1+ Цг +
’	2	2	4	2
4	8	2	2я
(рис. 18);
Рис. 18
г)	1; 2; 3; 4; п\
д)	1; 1; 1; 1;	1;
е)	0; 1; 0; — ; 0; —;...; 0; — ;...; 2	з	п
ж)	0,2;	0,22;	0,222;	0,2222;	...
...; 0,22-2;...; Л
з)	sin 1°; sin 2°; sin 3°; ...; sin n°; ...;
. cos 1° cos 2° cos3° COS/2° . : —'•• —...........................
K)0;	1-J-; —A-; I
2	3	4	5	6
;...(pnc. 19).
117°. Могут быть пределами довательности?.
ли два разных числа одной и той же после-
118. Число а называется предельной точкой последовательности |xrt), если для любого положительного числа е и любого числа k найдется такой номер
п > k,
для которого выполняется неравенство
|х„ —а|<е.
а)	Докажите, что если а — предельная точка последовательности {х„}, то любой отрезок с центром в точке а является кормушкой для последовательности (х„).
б)	Докажите обратную теорему.
119.	Докажите, что предел последовательности (если он существует) является предельной точкой
120.	Для каждой из следующих по-  следовательностей укажите все ее предельные точки:
,	п+1
а)х”=—
в)	хя= sin 11°,
г)	хп— ,
д)	хп= п,
.112	12	3	1
е)	—-; — : — ; — ; — ; — ; — ;
2	3	3	4	4	4	5
2	3	4
5 ’ 5 ’ 5
121.	Последовательность	на-
зывается ограниченной, если существует такое число С, что для любого номера п выполняется неравенство
р
Сформулируйте определение неограниченной последовательности.
122.	а) Докажите, что если последовательность имеет предел, то она ограничена.
б) Верно ли обратное утверждение?
123.	Говорят, что последовательность {*„} стремится к бесконечности (это записывают так:	при п->оо),
если для любого числа С найдется такое число k, что для всех номеров n>fc выполняется неравенство (рис. 20):
1*л1 > с.
р
Какие из следующих последовательностей стремятся к бесконечности и какие не ограничены:
а)	хп = п,
б)	(—1)",
в)	хп — п( ~1)П,
{п при п четном,
• _
У п при п нечетном,
124. Придумайте ограниченную последовательность, которая
а)	имеет и наибольший и наименьший члены,
б)	имеет наибольший член, ио не имеет наименьшего,
в)	имеет наименьший член, но не имеет наибольшего,
г)	не имеет ни наименьшего, ни наибольшего членов.
125. Рассмотрим следующие 16 условий- (буква «л» означает «для любого», буква «и» — «найдется такое что»):
1.	н	е>0	н	k	H	n>k	\Xn	-a\-	< £-
2.	и	е>0	н	k	H	n>k	\Xn	— a 1'	e.
3.	н	е>0	н	k	Л	n>k	l*„	— a| <	\
4.	н	е>0	н	k	Л	n>k	\Xn	-«l:	e.
5.	н	е>0	л	k	H	n>k	к	—«1 •	< e.
6.	н	е>0	л	k	H	n>k	\xn	— «N	
7.	II	е>0	л	k	Л	n>k	Iх»	— a|<	C e-
8.	н	е>0	л	k	Л	n>k	к		> e.
9.	л	е>0	н	k	H	n>k	|*л	-a|<	< e.
10.	л	е>0	н	k	H	n>k	l*«	—	> e.
11.	л	е>0	н	k	Л	n>k	\Xn	-a|<	C
12.	л	е>0	н	k	Л	n>k	\xn	-a|:	> e.
13.	л	Е>0	л	k	H	n>k	к	-a|<	
14.	л	е>0 л	п	n>k	\хп —
15.	л	е>0 л	k	л	n>k	|х„— о|<е.
16.	л	е>0 л	k	л	n>k	|хп —
Какие из этих условий выражают уже знакомые вам свойства последовательностей (быть ограниченной, иметь число а пределом, иметь число а предельной точкой, стремиться к бесконечности) или отрицания этих свойств?
126. Рассмотрим следующие пять свойств последовательностей: 1) тождественно равняться а, 2) иметь число а пределом, 3) иметь число а предельной точкой, 4) быть ограниченной, 5) стремиться к бесконечности.
Каждую последовательность можно охарактеризовать набором из пяти плюсов или минусов. Например, набор —I- + Ч— означает, что последовательность обладает свойствами 2, 3, 4 и не обладает свойствами 1, 5. Некоторые наборы не имеют смысла (например, набор + + + + +: если последовательность обладает свойством 1, она не может обладать свойством 5).
а)	Укажите все наборы, имеющие смысл. Для каждого из них постройте последовательность, характеризуемую этим набором.
б)	Докажите, что остальные наборы не имеют смысла.
127. Докажите, что если последовательность имеет предел, то в ней есть или наибольший член, или наименьший член, или и тот и другой. Привести примеры всех трех случаев.
128. Докажите, что из любой бесконечной последовательности можно выбрать бесконечную монотонную подпоследовательность. (Последовательность
{хп} называется монотонной, если выполняется одно из следующих условий:
1) х1<х2<х3<...<хя<...,
2) Xj х2 х3 ... хп ...
В первом случае последовательность называют неубывающей, во втором случае — иевозрастающей.)
В теории пределов очень важно одно свойство вещественных чисел, которое обычно принимают за аксиому.
Аксиома Больцано—Вейерштрасса:
Всякая монотонная ограниченная последовательность имеет предел.
Эта аксиома отражает свойство «полноты» совокупности вещественных чисел. Образно говоря, она состоит в том, что на числовой оси нет «проколов» и «дырок».
В курсе математического анализа доказывается, что аксиома Больцано — Вейерштрасса равносильна каждому из следующих утверждений.
1. Если на числовой оси построена бесконечная последовательность отрезков, так что каждый следующий отрезок лежит внутри предыдущего, то все эти отрезки имеют по крайней мере одну общую точку.
2. Всякое вещественное число можно записать в виде бесконечной (периодической или непериодической) десятичной дроби, и каждой такой дроби соответствует некоторое вещественное число.
Если одно из этих утверждений принять за аксиому, то второе утверждение и аксиома Больцано — Вейерштрасса станут теоремами, которые можно доказать.
129*. Докажите, что аксиома Больцано—Вейерштрасса не выполняется, если рассматривать только рациональные числа (т. е. существуют монотонные ограниченные последовательности рацио
нальных чисел, которые не имеют рационального предела).
130.	Докажите, что всякая ограниченная последовательность имеет хотя бы одну предельную точку.
131.	Докажите, что следующие последовательности имеют предел:
а)	1; 1 + 4-; 1 + 4- +4- ’	* +
4	4	9
б)	1; 1--- ; 1 —— + —;	1 —
3	3	5
2-4--L—		1)"~1 •
3	5	2n— 1
§ 3. Задачи на вычисление пределов
132°. Докажите, что если Итхп=а и
Нту„ = Ь, то
□->00
a)	lim (хп+уп)=а + Ь, Л—>со
б)	Нт (х„—уп)=а—Ь,
В) lim (хпуп) =ab, П~+со
г) lim — = -5-, если b + 0 и уп + 0. л—><х> Уп	и
133°. Придумайте последовательности {%„} и {уп}, для которых limx„ = 0, П—>ОО
limf/n=0 и такие, что п —СО
а) —->0 Уп
при п -> СО ,
б)	—	1 при п -> оо,
Уп
\ хп
в)	—->оо при П-> сю,
Уп
г)	11m — не существует.
Л->оо Уп
134°. Найти пределы	последователь-
.	ностей: .	2л 4-1 а) Хп=	3— , "	Зп—5 Юл б) х=	, ”	Л2+1 В) X -	п(п+2) п (л-Ь1)(л+3) ’ ,	2л+1 Г Хп	2„_j		
Д) хп= Цтг (1*4-2* + ... + п*)
ГГ+1
(k — фиксированное натуральное число).
Последовательность задачи 134д) имеет следующий геометрический смысл. Рассмотрим часть плоскости, ограниченную графиком функции y=xk, осью Ох и прямой х=1. Разобьем отрезок [О, 1] на оси Ох на п равных частей и построим на каждой части прямоугольник так, чтобы правая верхняя вершина лежала на графике нашей функции (рис. 21). Сумма площадей всех построенных прямоугольников равна как раз величине х„=—^—(1 *+2*+...+«*). Предел этой величины при я-»оопо определению называется площадью рассматриваемой криволинейной фигуры.
135°. Доказать, что
lim (i/+'^j_|/+Zl)=o.
136. Доказать, что lim — =0. „->«> 2"
137. Доказать,
что lim — = 0 при п-ьоо Оп
с>1.
138*. Доказать, что lim 1^12- =0, п-*а> П
139*. Найти lim ft п.
П-Ь-со
До сих пор мы говорили о пределах числовых последовательностей. Но с по мощью чисел можно задавать различные геометрические объекты. Например, направление прямой линии на плоскости можно задать угловым коэффициентом; точку на прямой линии и на плоскост» можно задавать ее координатами и т. д Во всех случаях, когда термины «предел» или «стремится» применяются к последовательности геометрических объектов, имеются в виду числовые последовательности, характеризующие эти объекты. Так, например, выражение «последовательность точек Мп на плоскости стремится к точке М» надо понимать в том смысле, что координаты точек Мп стремятся к соответствующим координатам точки Af.
140°. Улитка ползет по линиям клетчатой бумаги, передвигаясь за первый шаг на одну клетку вправо, за второй — на одну клетку вверх, за третий — на одну клетку вправо, за четвертый — на одну клетку вверх и т. д. (рис. 22). Вторая улитка сидит на месте и наблюдает за первой в подзорную трубу. Будет ли направление подзорной трубы стремиться к пределу, если первая улитка будет продолжать двигаться описанным образом?
р
141. Как изменится ответ предыдущей задачи, если улитка будет двигаться следующим образом:
а)	1 клетку вправо, 2 клетки вверх, I клетку вправо, 2 клетки вверх и т. д.?
б)	1 клетку вправо, 2 клетки вверх, 3 клетки вправо, 4 клетки вверх, 5 клеток вправо, 6 клеток вверх и т. д.?
в)	1 клетку вправо, 2 клетки вверх, 4 клетки вправо, 8 клеток вверх, 16 клеток вправо, 32 клетки вверх и т. д. (рис. 23)?
142°. На параболе, которая является графиком функции t/=x2, берется точка Ло с абсциссой а и последовательность точек А„ с абсциссами а+ —. Обозначим
"	п
через Мп точку пересечения оси Ох с секущей, проведенной через точки Ао и Ап. Докажите, что последовательность точек Мя имеет предел при п -> со, и найдите этот предел.
Пусть Ма — предел последовательности точек Мп. Прямая АоМо называется касательной к параболе в точке Ао.
рис 24
143°. Мальчик Петя вышел из дому и пошел в школу. Пройдя половину пути, он решил, что лучше пойти в кино, и свернул к кинотеатру. Когда он прошел половину пути, ему захотелось покататься на коньках и он повернул к катку. Пройдя половину пути до катка, он подумал, что нужно все-таки учиться, и повернул к школе. Но на половине пути к школе он снова свернул к кинотеатру (рис. 24). Куда придет мальчик Петя, если он будет идти таким образом?
144°. Последовательность {MJ точек на прямой строится по следующему закону. Первые две точки Л1> и Л12 берутся произвольно, а каждая следующая
точка является серединой отрезка, соединяющего две предыдущие точки. Доказать, что существует предел последовательности	и найти его.
145.	Сумма бесконечного ряда чисел определяется следующим образом. Пусть дан ряд
о 1+0.2 + йз+...+ап +..»
Обозначим через S„ сумму первых п слагаемых. Если по’следовательность {Sn} имеет предел S, то число 5 называется суммой заданного ряда. Если же последовательность {SJ не имеет предела, то говорят, что заданный ряд расходится и не приписывают ему никакой суммы.
Найти суммы
а)	1+й + а2 + ... + аи+ ...,
б)	а + 2а2+3а3 + ... + пап +...,
р
п(л+1)
Г) 1-2-3 + 2-3-4 + 3-4-5 +	+
+-----!
л(«+1)(п+2)
146.	Имеется неограниченное количе* ство одинаковых кирпичей, имеющих форму прямоугольного параллелепипеда. Кирпичи кладутся друг на друга с некоторым сдвигом так, чтобы они не падали (рис. 25). Какой длины «крышу» можно таким образом получить?
РИС. 25-
147.	Доказать, что последовательность
2; 2 + — ; 2
2 н-------— ; 2 + ---------?-----;
1 1 ’
24----- 24-----------------
имеет предел, и найти его.
148.	Для вычисления квадратного корня из положительного числа а можно пользоваться следующим методом последовательных приближений. Возьмите произвольное число Хо и постройте последовательность по такому закону:
Докажите, что если х0>0, то Пт хп = =V а, если же х0<0, то Пт х„=—У а (Знаком У~а~ мы обозначаем арифметический корень из а.)
Сколько понадобится последовательных приближений (т. е. сколько членов последовательности {хп} нужно вы числить), чтобы найти значение ]Л10 с точностью до 0,00001, если в качестве начального значения взять х0=3?
КОНТРОЛЬНЫЕ ЗАДАЧИ
К главе 1
1.	Вычислить сумму
1	.	1	.	I	1
ЬЗ 3-5	(2п — 1)(2л+1)
2.	Доказать, что при любом натуральном п
I2	22	п2
	1-	р ... 4~	= 1-3-------------------3-5-(2л—1)(2л-(-1)
_ л(л+1) 2(2л + 1)
3.	Вычислить произведение
где л>-3.
4.	Доказать, что
(л + 1)(п + 2) . . . (2л —1)2л 2„
1-3-5.. ,(2л — 1)
4 С. И. Гельфанд и др.
49
5.	Доказать, что при любом натуральном п>1 справедливо неравенство
_^ + -1_ + ... + А>2з «4-1	«4-2	2л 24
6.	При каких натуральных п справедливо неравенство
2">2/г4-1?
7.	Доказать, что
2"-1(а'г4-6'г)>(а + 6),!,
где а4-6>0, а^Ь, п>1.
8.	Доказать, что плоскость, разбитую на части п окружностями, можно закрасить черной и белой краской так, что любые две соседние части будут закрашены в разные цвета.
Pu« 26
9.	Стороны произвольного выпуклого многоугольника покрашены снаружи. Проводится несколько диагоналей многоугольника так, что никакие три из них не пересекаются в одной точке. Каждая из этих диагоналей тоже покрашена с одной стороны, т. е. с одной стороны отрезка проведена узкая цветная полоска (рис. 26). Доказать, что хотя бы один из многоугольников, на которые разбит диагоналями исходный многоугольник, весь покрашен снаружи.
10.	Доказать, что при всяком целом 0 число 10"+1 — 10(п4-1) +п делится на 81.
11.	Вычислить сумму
1 -34-3-54-...4-л(п4-2).
12.	В арифметической прогрессии сумма первых п членов равна сумме
первых т членов, п^т. Доказать, что сумма первых п-\-т членов этой прогрессии равна 0.
13.	Вычислить сумму
6 + 66 + 666 4-... + 666 ... 66.
п раз
14.	Существует ли арифметическая прогрессия, среди членов которой встречаются числа 1,К2иЗ? Эти числа могут стоять в прогрессии не обязательно подряд и не обязательно в том порядке, в котором они здесь написаны.
15.	Дана геометрическая прогрессия, знаменатель которой есть целое число, не равное 0 и —1. Доказать, что сумма любого числа произвольно выбранных ее членов не может равняться никакому члену этой прогрессии.
16.	Каждая сторона правильного треугольника разбита на п равных частей. Через все точки деления проведены прямые, параллельные сторонам. Они разбивают треугольник на равные маленькие треугольнички. Часть из них покрашена в черный, часть — в белый цвет, так что любой черный граничит с четным числом белых, а любой белый — с нечетным числом белых. Доказать, что маленькие треугольники, расположенные в углах большого, покрашены одинаково.
17.	Найдите ошибку в следующем  доказательстве» по индукции утверж-"ения «Все числа равны между собой».
Доказательство. Будем доказывать, что любые п чисел равны между собой. Одно число равно самому себе. Поэтому при п=1 утверждение справедливо. Допустим, что оно справедливо
при n=fs, и докажем его справедливость при n—k+1.
Перенумеруем все числа из заданного множества номерами 1,2, 3, . . ., &+1-Первые k чисел равны между собой и поэтому равны первому числу. Исключим второе число. Тогда оставшиеся числа, среди которых есть (k+ 1)-е число, равны друг другу и равны первому числу.
Итак, все числа равны первому, а значит, равны между собой. Доказательство закопчено.
К главе 2
18.	На гранях кубика поставлены цифры от 1 до 6. Получилась игральная кость. Найти число различных игральных костей.
19.	Что вероятнее получить в сумме при двукратном кидании кости: 9 или 10 (рис. 27)?
20.	По окончании партии домино все костяшки оказались выложенными в цепь. Найти число всевозможных цепей (костяшки выкладываются по прямой линии).
21.	а) Сколькими способами можно рассадить за круглым столом 19 человек?
б) Сколькими способами можно рассадить за круглым столом 19 человек, так, чтобы между А и Б сидело ровно г человек?
22.	Две дворовые команды играют в футбол «до 10». Судья записывает в протокол, как меняется счет. Например: 1 :0, 1 :1, 1 :2, 1 :3, 1 :4, 2:4, 2:5, 2:6, 3:6,
4:6, 5:6, 6:6, 7:6, 6:6, 9:6, 9:7, 16 7. Сколько может получиться различных протоколов?
23.	Детская погремушка состоит из кольца, на которое насажены три белых шарика и семь красных. Некоторые погремушки, кажущиеся на первый взгляд разными, можно сделать одинаковыми, расположив кольца и передвинув шарики надлежащим образом (рис. 28). Найти число действительно различных погремушек.
24.	Сколькими способами фишка может попасть с поля al шахматной доски на поле Л8, если она каждым ходом ходит только на клетку вверх или на клетку вправо?
25.	Сколькими способами можно поставить на шахматную доску две белые ладьи и две черные так, чтобы белые не били черных?
РИС.28
26.	Сколькими путями шашка al может попасть в дамки? (Других шашек на доске нет.)
27.	Сколькими несамопересекающи-мися путями можно попасть из Л в В (рис. 29)? (Движение происходит по кольцевым и радиальным маршрутам с пересадками на станциях, отмеченных белыми кружками.)
28.	Сколькими способами на трехмерной шахматной доске 3X3X3 можно расставить 9 ладей так, чтобы они не били друг друга? (Ладья держит под боем свою строку, свой столбец и свою вертикаль )
29.	В каждой клетке таблицы 2Хи стоит одно из чисел от 1 до п, причем в
любой строке стоят разные числа и в любом столбце стоят разные числа. Сколько таких таблиц?
30, Один забывчивый пассажир оставил свои вещи в автоматической камере хранения, а когда он за час до отхода поезда пришел получать их, то обнаружил, что почти забыл номер. Он помнил только, что в номере встречаются 23 и 37. Сколько номеров ему придется перебрать? (Чтобы получить вещи, нужно правильно набрать пятизначный номер.)
31.	У отца было 7 дочерей. Всякий раз, когда одна выходила замуж, каждая из ее старших сестер, оставшихся в невестах, шла жаловаться отцу, что нарушен старинный обычай выходить замуж по старшинству. После того как вышла замуж последняя дочь, оказалось, что отец выслушал 7 жалоб. Сколькими способами это могло произойти?
Более серьезная формулировка этой задачи такова. Назовем п-перестановкой строку из /г чисел от 1 до л, в которой каждое число встречается 1 раз. Пару чисел (р, I) из этой строки назовем беспорядком, если р>1 и р стоит в «-перестановке левее, чем /. Сколько существует «-перестановок с k беспорядками? (В задаче про сестер-невест n=k=7.)
32.	Если в городе 2 высотных здания, то их шпили можно увидеть в любом порядке (слева направо), если смотреть из разных точек города. То же верно и для трех высотных зданий, если только они не расположены на одной прямой (рис. 30). Архитектор хочет расположить 7 высотных зданий так, чтобы, гуляя по городу, можно было увидеть их шпили в любом порядке. Удастся ли это ему?
К главе 3
33.	Докажите, что число 2 не является пределом последовательности
1; 3; — ; 2— ; —; 2— ;
2	2	3	,3
-1-; 2-L п п
34.	Известно, что limxB = l. Найти пределы последовательностей:
а) ТТТ • б) хпт *
Г) Уп= V^n-
в) Уп=
Хп — 1

35.	Докажите, что если последовательность {хл| имеет предел а, то последовательность, полученная из нее любой перестановкой членов, тоже имеет предел а.
36.	Докажите, что если последовательность имеет предел а, то любая ее бесконечная подпоследовательность тоже имеет предел а.
37.	Докажите, что если число а является предельной точкой последовательности {х„}, то можно выбрать из {хя} такую подпоследовательность, для которой число а является пределом. Верно ли обратное утверждение?
38.	Придумайте последовательность, для которой все предельные точки были бы целыми числами и каждое целое число было бы предельной точкой.
39.	Докажите, что если	при
всех п и lim хп=а, то а>0.
П-»<»
40.	Найдите пределы:
а)
lim
л->со
п2 + Зп — 2
1+2+3 + ... + п
б)
lim
л->оо
п2
4" ’
В)
11m n+-lgn+2\ пж п2—1g п—2п
г) lim (]/n2+n— Vг?-—п).
41.	Последовательность {х„} строится последующему закону: первый член выбирается произвольно, а каждый следующий выражается через предыдущий по формуле хл+1 =ахп +Ь, где а и b — постоянные числа. При каких а и b последовательность {х„} имеет предел?
42*. Докажите, что если из ряда
вычеркнуть все числа, в записи которых участвует цифра 3, то сумма ряда из оставшихся членов будет конечна.
РисЗ!
43. На графике функции г/=х2 рассмотрим точки Ап и Вп с абсциссами —
и —— соответственно. Проведем через п
А„, В„ и начало координат окружность. Пусть М„ — центр этой окружности (рис. 31). Докажите, что последовательность точек {7И„} имеет предел, и найдите его.
РЕШЕНИЯ
Глава 1
1. Решим задачу, используя метод математической индукции.
а)	При п=1 равенство справедливо.
б)	Пусть равенство справедливо при и=£, где k — произвольное число. Докажем, что в таком случае оно справедливо и при п=& + 1, т. е. что
I3 + 23 + З3 4-... + k3 4- (k + I)3 =
= (^ + 1)а (^ +
4
В самом деле, пусть при n = k равенство справедливо, т. е. пусть
]з + 23 4- З3 4- ... 4- k3 = —4-1)2 .
4
Тогда
I3 4- 234-334- ... 4-£34-(/г4-1)3=
= —^+1)-4-(^4-1)3=(£4-1)2[— 4- k 4-11 =
4	| 4	J
=	+ 4Л 4- 4) =	1)2 4-2)2 .
Таким образом, из справедливости равенства при n=k вытекает его справедливость при n=k+l. Поэтому на основании принципа математической индукции мы можем утверждать, что при всех натуральных п имеет место равенство
13+23+33+... + п3= п2(п+П- .
4
2.	Первое решение. Применим принцип математической индукции.
а)	Непосредственной проверкой убеждаемся в справедливости равенства при п— 1
б)	Пусть равенство справедливо при каком-нибудь натуральном числе k, т. е.
-L + -L + J- + ...+
1*2	2-3	3-4	k(k + 1) k+ 1
Докажем, что тогда оно справедливо и при n=k+l. Действительно,
Ь2 2^3 + 3~ +	+	1) +	1
+_____L__ =	+------!----=
+ fe + 1	(4-1) (*+2)
__ fe (Л + 2) + 1 _ fe2+241 = (Л+1)(42)	(41) (42) ~
__ (б+Р2	= Ж
(4-1) (4-2) k + 2 '
Таким образом, оба утверждения, необходимые для применения принципа математической индукции, доказаны. Поэтому наше равенство верно для всех п.
Второе решение. Для любого п имеет место формула
1 _ 1 __ 1
п(п -I- 1) п	л + 1
58
I
(она проверяется непосредственно). Поэтому левую часть равенства, которое мы хотим доказать, можно записать следующим образомз
В полученной сумме все слагаемые, кроме первого и последнего, взаимно уничтожаются, Поэтому
- + — +	+----— 4-
1-2	2-3	3-4	(п —1)п
+ —I—=1-------
п(п + 1) П-Р 1	п+1
что и требовалось доказать.
3. Первое решение. Докажем методом математической индукции, что имеет место равенство
± + _L + I -	1	- п
1-4 4-7	"	(Зп—2)(Зп+1)	Зп+1
а) При п—1 равенство справедливо, б) Пусть это равенство выполнено для натурального числа k, т, е. пусть
— 4~ — 4- • • - 4--------------=	.
1-4	4-7	(3£—2)(ЗЛ+1) ЗЛ+1
Покажем, что тогда оно будет справедливо и для п=Л+1.
В самом деле,
— + — + Н----------------?-------1-
14	4-7	(ЗА—2) (ЗАН-1)
+--------’------ + ’____________________=
(ЗАН-1) (3A-J4) ЗАН-1 (3A-J-1) (ЗА-)-4)
= ЗАг+4А+1 _ (3A+l)(fe+l) = fe+1 (ЗА+1)(ЗА+4) — (ЗАН-1) (ЗАН-4) ~ ЗА+4
Таким образом, справедливость равенства доказана для всех п.
Второе решение. Воспользуемся формулой
----1----=-------L_ н----1---. .
(Зп—2)(ЗпЦ-1)	3(3п—2)	3(Зп+1)
Применяя ее ко всем слагаемым нашей суммы, получим
_L 4. 1 4.	1	4.	4. i 4.
14 'г 4-7	7-10	(Зп—5)(3п—2)
+------?----= (---4 +
(Зп—2)(Зп-Н)	\31	3-4/
+	+ (з^7	3-10 )+••• +
+ (—*—+ —1 U
\ 3(3п—5)	3(3п—2) /
+ (—!— + —!—V \ 3 (Зп—2)	З(Зп-Н) /
После раскрытия скобок все слагаемые, кроме первого и последнего, взаимно уничтожатся, и мы получим
JL 4. _L 4. J_ 4.... 4._____!_______=
1-4	4-7	7-10	(Зп—2)(3n+D
= J________1	_ п
3	З(Зп-Ы) ~ Зп-[-1 ’
Равенство доказано.
4. Приведем здесь одно из возможных решений, основанное на принципе математической индукции.
а]	Непосредственной проверкой легко убедиться, что при п=1 равенство справедливо,
б)	Пусть равенство справедливо при п=А:
—-----+--------------F.. - +
0(а+1)	(о+1)(о+2)
, * 1 = *
"Г (а4-4₽1)(а+Л) а(а+Л)
Покажем, что тогда оно справедливо и при я = Имеем
*_____1_____!_____|_
° (° +1)	(а+1)(а+2) .......
+--------‘-----+--------’_____=
(a+k—l)(a+k)	(a+k)(a+k+l)
a(a-j-k) (a+A)(e+*+l)
А(а+А+1)та 	А24-оА+в+А!
a(eJ-A)(eJ-AJ-l)	а(а+А}(а+А+1)
_	(a+A)(A+l)	__ fe+1
а(а J- A)(a+AJ-l) а(а4-А+1) Поэтому на основании принципа математической индукции мы можем теперь утверждать, что равенство справедливо при всех натуральных п.
5. Решим задачу методом математической индукции.
а) При и = 1 равенство справедливо (проверьте!).
б) Пусть равенство выполняется при n=k:
1 • 11+2-2!+.,. + £. £!=(&+1)1—1.
Покажем, что в этом случае оно будет выполняться и при n=k+\. В самом деле,
1.1!+2-2! + ...+Л.^+(Л+1)(Л+1)! = = (Л+1)1—1 + (£+1)(£+1)! =
= (й+2) (А+1)1—1.
Но из определения л! ясно, что (й + 2)Х X (Л+1) ! = (k+2)!, Поэтому
1-П-1 2-2! + ...+ (й+1) (£+!)! =
= (* + 2)!—1,
т. е. наше равенство оказалось верным и *при л = Л+1. Применяя метод математической индукции, получаем, что наше равенство справедливо при всех натуральных п.
6. Первое решение. Будем доказывать наше равенство методом математической индукции.
а)	При п=1 непосредственная проверка показывает справедливость равенства.
б)	Пусть равенство справедливо для какого-нибудь натурального
_ М-1 2k
Покажем, что в этом случае оно справедливо и для n=k+l. Действительно,
(М-1)|(М1)а- И = (MDMA-+2) 2А(*Ч-1)3	2£(М-1)2
k+2
2(MD
Теперь, применяя принцип математической индукции, мы можем утверждать, что равенство справедливо при всех п >2.
Второе решение. Для каждого натурального п^>2 имеет место фор-мула
1 _ (Л—1)(Л + 1)
па	л2
Применив ее к каждому сомножителю в левой части равенства, получим
J_ \	(2-1) (2+1) (3-1) (3+D
па /	22	З2
,,(4- 1)(4+1) (и —2)л . (л— !)(п+1) 4*	(л—I)2	п-
Легко видеть, что почти все сомножители из числителя и знаменателя сокращаются. Не сокращаются только 2—1 = = 1 и /г+1 в числителе, а также 2 и п в знаменателе. Поэтому
л+1
2л *
т. е. равенство доказано.
7.	Применим метод математической индукции.
а)	При /г= 1 формула справедлива (проверьте!).
б)	Пусть формула справедлива для какого-нибудь натурального числа k, т. е. пусть
1 - 22 + З2 — ... + (—	=
— /___[\fe-i
1	2
Покажем, что тогда она справедлива и для п=й+1. В самом деле,
1 — 22 + З2 — ... + fe2 +
4- (— l)k(k +1)2 = (—1)й—1 -(fe2+1)- +
+ (-W+ i)2 = (-i)ft-1(fe+ 1)X
[2 J 2
пИ*+П(*+2) k '	2
Поэтому, используя принцип математической индукции, получаем справедливость нашей формулы при всех натуральных п.
8. Пусть уже проведено п прямых. Проведем (п+1)-ю прямую. С предыдущими п прямыми эта прямая пересекается в п точках, так как по условию она пересекается с каждой из них и ни с какими двумя не пересекается в одной и той- же точке. Ясно, что этими п точ ками (п+1)-я прямая разделяется на п+1 отрезков (два из них бесконечны). Каждый из этих отрезков разрезает старую часть плоскости и делает из нее две новые части. Поэтому п+1 отрезков вместе создают из п+ 1 старых частей плоскости (2п + 2) новых частей, т. е. при добавлении (п+1)-й прямой число частей плоскости увеличивается на п+1. Теперь легко сосчитать число частей, на которые плоскость разбивается п прямыми. Одна прямая разбивает плоскость на 2 части. При добавлении 2-й прямой количество частей увеличивается на 2, при добавлении 3-й еще на 3 и т. д. Поэтому общее число частей равно
2+2+3+4+ ...+п =
= 1+(1+2+3+...+л)= 1 + — (n2+t) .
(См. выше на стр. 11 пример 9.) Поэтому число частей, на которые прямые п(п+1) , .
делят плоскость, равно —-- • +1.
9. а) При п=8 очевидно, что 8 копеек можно представить трех- и пятикопеечными монетами: 8=5+3.
б) Пусть мы можем представить k копеек в виде суммы трех- и пятикопеечных монет. Покажем, что то же можно сделать и для k+\ копейки. Рассмотрим два случая: в представлении k копеек есть хотя бы одна пятикопеечная монета, или нет ни одной. В первом случае, заменяя пятикопеечную монету на две трехкопеечные, получаем нужное представление k+1 копейки. Во втором случае k копеек представляются только трехкопеечными монетами, причем ясно, что число этих монет не меньше трех. Поэтому мы можем заменить три трехкопеечные монеты на две пятикопеечные и получим нужное нам представление /г+1 копейки. Таким образом, если k копеек можно представить в виде суммы трех- и пятикопеечных монет, то то же можно сделать и для А+1 копейки. Поэтому, используя принцип математической индукции, получаем, что любое количество денег, большее 7 копеек, можно представить трех- и пятикопеечными монетами.
10.а) Если плоскость разбита всего одной прямой, то ее можно закрасить так, как требуется в условии задачи. Для этого достаточно одну полуплоскость закрасить в одни цвет, а вторую — в другой.
б)	Пусть мы закрасили нужным образом плоскость, на которой проведено п прямых. Проведем (п+1)-ю прямую и покажем, что полученную плоскость тоже можно раскрасить нужным образом. Новая прямая разбивает плоскость
5 С. И. Гельфанд и др.
65
на две полуплоскости. Чтобы получить нужную раскраску, поступим так. В одной из полученных полуплоскостей изменим цвет каждого куска (т. е. заменим белый цвет на черный, а черный на белый), а в другой — оставим без изменений. Покажем, что после этого плоскость останется раскрашенной правильно. Возьмем два соседних куска. Возможны два случая: либо прямая, их разделяющая — это одна из старых прямых, либо это новая, (/г + 1)-я прямая. В первом случае до проведения новой прямой и изменения цвета эти куски были закрашены в разные цвета, а потом либо оба поменяли цвет, либо пи один не поменял. Ясно, что они останутся закрашенными в разные цвета. Во втором случае эти куски до проведения новой прямой были закрашены в один цвет, а после ее проведения один из кусков изменил свой цвет, т. е. эти два куска будут закрашены в разные цвета. Таким образом, если мы умеем правильно раскрашивать плоскость, разбитую на части п прямыми, то мы можем правильно раскрасить плоскость, разбитую на части п+1 прямой. Теперь мы можем применить принцип математической индукции, который доказывает справедливость нашего утверждения.
11.	Нужно доказать, что’для любого натурального п число
п3+ (п +1)3+ (п+2)3
делится на 9.
а)	При п= 1 утверждение верно, так как 13+23+33=36 делится на 9.
б)	Пусть утверждение справедливо для какого-нибудь натурального числа k, т, е. пусть &3+(&+1)3+(&+2)3 делится на 9. Докажем, что тогда это утверждение справедливо и для n=k+l,
Имеем
(&+1)3 + (Л+2)3+ (£ + 3)3= (А+1)3 +
+ (& + 2)3+(&3+3 • ЗА2 + 3 • З2-& + 33) =
= [&3+ (£+1)3+ (&+2)3] + 9(#24-3# + 3).
Мы представили число (&+1)3+ (&+2)3 + + (&+3)3 в виде суммы двух слагаемых, из которых первое делится на 9 по предположению, а второе является произведением 9 на целое число. Поэтому и сумма этих слагаемых будет делиться на 9.
Таким образом, мы можем использовать принцип математической индукции, который доказывает наше утверждение.
12.	а) Проверим наше утверждение при п=0. В этом случае
Цп+2+122,1+1= Ц2+12= 121 + 12=133
делится на 133.
б) Пусть наше утверждение выполняется для какого-нибудь k^-О, т. е. пусть 11* + 2 + 12 2А + * делится на 133. Покажем, что в этом, случае оно выполнено и для n=k+l. Имеем
1 1(* + 1) + 2 4- 192(*+Ь+1 = Цй+3_|_
+ 122*+3= 1Ы1*+2+ 144-122*+1=
= 11-11*+2 +11.122ft+1 + 133- 122ft+1 =
= 11 (1 lfe+2+122ft+1)+133- 122A+!.
Первое из полученных слагаемых делится на 133 по предположению, второе — содержит множителем число 133. Поэтому и их сумма делится на 133.
Теперь принцип математической индукции показывает, что утверждение справедливо для всех
13.	а) При п=2 неравенство справедливо, поскольку (1+а)2= 1+2а+а2> >1+2а, так как а2>0 при а+0.
б) Пусть неравенство справедливо для какого-нибудь натурального &>2, т. е. пусть
(1 4- o)fc > 1 -|- ka.
Докажем, что оно справедливо и при n=k+l. В самом деле, по условию 14-а>0. Поэтому, умножая обе части неравенства
(1 4- а)* > 14- ka
на 14-0, получим
(14-a)ft(14-a) > (14-*о)(1+о),
(14-о)*+1 >(14- (А4-1) о)4-ka?.
Но Z?o2>0 при а=^0, поэтому (14-a)ft+1> 1 4-(&4-1)а.-
Таким образом, применяя принцип математической индукции, получаем, что при всех п >2
(14-о)" > 1 4- па, если а>—1, о^=0-
14.	а) При п=2 неравенство выполнено, так как 1Ч——
/Т
б) Пусть неравенство выполнено при n—k, т. е. пусть
Покажем, что тогда неравенство выполнено и при n=k+l. Для этого достаточно доказать справедливость неравенства
1
кт+т
>Vk+ 1 ~V k.
В самом деле, если последнее неравенство будет доказано, то, сложив его с нашим неравенством при л=&, которое по предположению справедливо, получим
наше неравенство при п=&+1. Докажем теперь неравенство
—	> ут+т -	(*)
V к +1
Умножим обе его части naF^+l + |/v, получим неравенство
> + 1/Тг>'
которое, очевидно, справедливо. Поэтому и неравенство (*) тоже справедливо. Таким образом, из справедливости неравенства
1 1	1 I 1	1	--
1 Т — Ч—,— -J-	-Р — ~> I п
V 2 К 3 т ’ • • Г к в г
при n=k вытекает его справедливость при n=k+\.
Теперь мы можем применить принцип математической индукции, и наше неравенство оказывается справедливым при всех /г^2.
15.	а) При /г=1 и 2 формула очевидна.
б) Пусть формула справедлива при всех п<0г, где k^2. Покажем, что тогда она справедлива и при /г = #+1. Действительно,
llk+i ~ 3uk	= 3 (2ft 1 Ч- 1)
—2(2fc-2+ 1) = 3-2*-1-!- 3 — 2fc-i — 2 =
=9,2*~1— 1 = 2ft— 1.
Теперь мы можем применить принцип математической индукции, который показывает, что формула справедлива при всех п.
16.	а) При n= 1 формула справедлива.
б) Пусть формула справедлива при n—k, т. е. пусть
нА = (2£-1)2.
Покажем, что тогда она справедлива и при n~k+\. Действительно,
“fc+i =	+ 8А = (2k — 1)2+8А =
=4А2—4А+1 +8А=4А2+4А!+ 1 =(2Z?+1)2. Применяя принцип математической индукции, получаем, что она верна для всех натуральных ti-
ll.	Мп=ип+1~ип=^(п+1)2—п2= = 2л + 1.
18.	Покажем, что для всех п справедлива формула
4~ • • • 4“^Mn-l==Mn"
В самом деле, вспоминая определение последовательности, имеем
«1+ДМ1+Ди2+ • • • +Д«„-1 = «1+(«2—“1)+ + («3 к2) + ... -r(zfn 
Все члены последней суммы, кроме ип, взаимно уничтожаются, и мы получаем нужную формулу.
Ясно, что такая же формула справедлива и для
Теперь найдем, чему равно ип—vn
lln — vn = (th + Д^1 + Дк2 + • • • + дип-1)— -----(У1 + Ду1 + Ду2+--+ Дг7л-1) =
Дп2 — Ау2 ”i~ • • • "Т
Но из условия задачи мы знаем, что A«1 = AU1, A«2 = AU2.	—^vn-i 11
поэтому
«п — Vn = «j —
Отсюда следует, что если uj =/= пц то un~vn =/= 0, т. е. и „ и vn не равны ни для какого п. Если же U\ = v\, то для всех п выполнено равенство ut =vn^
19.	Задача решается непосредственной проверкой
Д№„=(да„+1 — ш„)= (un+1+vn+1)—(u„+vn)=
=(»«+! — «„)+("„+! — ^Я)=Д«Я+Д^Я-
20.	Мы имеем Дил=(я+1)л—пк. Покажем, что
(я+	+ ...,
где точками обозначены члены, содержащие п в степени, меньшей чем k—1.
Мы докажем это, используя индукцию по числу k.
а)	При /г=1 утверждение справедливо.
б)	Пусть утверждение справедливо при каком-нибудь k=ko, т. е. пусть
(п 4- I)6» = я*» + ^оя*«—1 + ..., где точками обозначены члены, содержащие п в степени, меньшей чем k0—1. Покажем, что тогда утверждение будет справедливо и при />=Л0+1. Имеем (п+	=(«+1)*° (п+1)=
=(п*»-4-Лоя^-1Т- ...) (« + 1)=
-|-Лоп*«—*+ ... =
—(&0-р1) nfco-p ..., где в последнем выражении точками обозначены члены, содержащие п в степени, меньшей чем k0. Таким образом, наше утверждение справедливо и при k = ko~[~ 1.
Теперь, используя принцип математической индукции, получаем, что для всех k
(n+l)/i=nk+knk~1+ ...
Поэтому
Дал=(«+ l)ft — nk—nk	... — nk=
=knk~l + ...,
где точки обозначают члены, содержащие п в степени, меньшей чем k—1. Значит, Ди„ выражается многочленом ог п степени k—1, и коэффициент при старшем члене этого многочлена равен k.
21. Пусть ип —aonk + (цпк~1 4~ • •• 4-4-ай-1Л4-аЛ.
Рассмотрим тогда последовательность ип как сумму Л+1 последовательностей с общими членами aonk, а\Пк~1, ... ..<^k-in’ak соответственно. Тогда вследствие результата задачи 19 последовательность Дия будет суммой последовательностей разностей этих Л4-1 последовательностей. Из задачи 20 ясно, что общий член первой последовательности разностей выражается многочленом (k—1)-й степени от п со старшим коэффициентом aok, а общие члены всех остальных последовательностей разностей выражаются многочленами степени, меньшей чем k—1. Поэтому общий член последовательности Ди л выражается многочленом (Л—1)-й степени от п со старшим коэффициентом aok.
22. Покажем, что k-e разности последовательности un—nk при всех k равны k\. Применим индукцию по k.
а)	Ясно, что при k=\ утверждение справедливо, так как если и„=п, то Дил=1 = 11.
б)	Пусть утверждение доказано для всех k^.k0. Докажем его для &=Л04-1. Возьмем последовательность u„=ns« + ’. Тогда мы знаем (см. задачу 20), что общий член ее первой последовательности разностей выражается многочленом от п степени k0 со старшим коэффициентом k0 4-1. Пусть этот многочлен есть
А«п=(^о+ О Н-а1п*«~1+а2пк<г-2 4-... 4-<40.
Последовательность Ди „ есть сумма A’o+l последовательностей с общими членами (k0+\)nk«, щи6»-1, соответственно. Нам нужно взять k0 раз последовательность разностей у последовательности Ди„. Ясно, что для этого достаточно взять k0 раз последовательность разностей у каждого слагаемого, и результаты сложить. Из того, что наше утверждение доказано для k—ko, следует, что из первого слагаемого после взятия разностей Ло раз получится последовательность, все члены которой одинаковы и равны (&о+1)/го!= (#о+1)1- Из того, что утверждение доказано для k—k0—1, следует, что, взяв k0—1 раз носледовательность разностей у второго слагаемого, мы получим последовательность, у которой все члены одинаковы и равны tzj (k0—1)!, а взяв последовательность разностей еще раз, получим последовательность, у которой все члены равны 0. Аналогично, после взятия k0 раз последовательность разностей у всех последующих слагаемых, мы получим 0, Поэтому все члены (/г0+1)-й последовательности разностей у последовательности ип равны (k0+1)1.
Таким образом мы получили, что fe-я последовательность разностей последовательности nk для всех k равна klt
23.	Решим задачу индукцией по k.
а)	Пусть 6 = 0, т. е. ия = 1 для всех п. Ясно, что в этом случае искомая последовательность существует, а именно ип=п. Мы будем обозначать эту последовательность через {и„0>}.
б)	Пусть утверждение доказано для всех k-^k0. Это означает, что существуют последовательности {«„’J. ...
такие> что Ди™ =1, ДипП)=и, ....
..., Ди(*о) = п*°. Покажем, что существует последовательность {i4*o+I)} такая, что Au<ft°+I) =nfco+1 . Найдем эту последовательность следующим образом. Возьмем сначала последовательность с общим членом я*»+2 . Мы знаем, что общий член ее последовательности разностей выражается многочленом от п степени &0+1, старший коэффициент которого равен Ло+2 (см. задачу 21). Поэтому общий член последовательности
„	п^+г
разностей для последовательности —------
л0+2 выражается многочленом от п степени Ло+1 со старшим коэффициентом 1.
Пусть этот многочлен есть
n*„+i _|_	1 4- ... 4-Щ„.
Тогда в качестве {гД*°+1)} возьмем последовательность со следующим общим членом:
“ •+" = -йт	I
—... — а*о40).
Покажем, что она будет удовлетворять нужным условиям. В самом деле, используя результаты задачи 19, получаем
X /
— А	. .—А (щоц™)=
= nk°+I+aonl!‘+ аХ“-1+ - • •+
+	— aQnk° — а^"—1 — ... — щ, =
=«*•+*.
Таким образом, существует последовательность ^п,+1>} с нужными свойст
вами. Теперь, используя принцип математической индукции, получаем, что для каждого k существует последовательность для которой Au<*>=nft . Ясно-также, что общий член последовательности {u(nk)} выражается многочленом (&+1)-й степени от п со старшим коэф-, 1 фициентом ———.
24.	Введем обозначения цл=Д«п, к'л=д^л.	t/„=Ax„, Из усло-
вия задачи известно, что уп=0 при всех п. Из этого следует, что хп одинаковы при всех п. Отсюда видно, что w„ при всех п выражается многочленом 1-й степени от п. Пусть этот многочлен есть aon + ai. Из решения задачи 18 мы знаем, что
Vn = *4 +	+ ^2 +• • •+ ^-1 =
= ty + я0 [1~Ь 2 + ... + (п — 1)]4-аг(п—1).
Но мы знаем, что 1 + 2 + ...+ (п—1) =
=------—— (см. стр. И), поэтому
= v^a^n— 1)+п0 -(п~п ,
т. е. общий член последовательности vn выражается многочленом 2-й степени от п. Пусть этот многочлен есть v „=Ьоп2+, +bin+bz. Тогда
чп = 111 +	+ V2 +--+Чл-1 —
+ b2(n - 1) + bx +
+ fe0[l2 + 22 + ... + (n-l)2].
Покажем, что сумму 12+22+...+ (п—I)2 можно записать в виде многочлена 3-й степени от п. В самом деле, обозначим эту сумму S„. Тогда AS„=nz. Поэтому из задачи 23 следует, что S „ выражается
многочленом 3-й степени от п. Значит, и и п тоже выражается многочленом 3-й степени от п.
25.	Пусть многочлен и„ имеет вид
vn = аопк + а1пк~1 + ... + ак_гп + ак. Возьмем тогда последовательность w„=aou<a>+ a1u<n~t)+.. ,+ak_1u(n>+akitn>, где u(k>, u^-1’....и1}),	— после-
довательности, существование которых доказано в задаче 23. Тогда из задачи 19 следует, что при всех п &wn=vn. Таким образом при всех п &wn=&v п . Из задачи 18а) следует, что разность ип—wn одинакова при всех п (она равна Uj—Oj). Поэтому при всех п справедливо равенство
akUn	-}-akUn0')-y
+ («i — ™1)-
Из задачи 23 известно, что ивыражается многочленом (fe-pl)-fi степени от п. Поэтому общий член последовательности и„ выражается многочленом (й + 1)-й степени от п.
26.	Пусть un = 1 +22 + ...+ (п—1)2+п2. Тогда ясно, что Ды„=п2. Из задачи 24 следует, что и„ выражается многочленом 3-й степени, т. е.
и п—а0п3+щп2+а2п+а3.
Найдем теперь а0, ai, а2, а3. Подставив для этого вместо п числа 0, 1, 2, 3, получим
Мо=оз=0,
Щ =fl!o + fl!i + 02 + ЙЗ= 1, и2 ~ 8«0+4«| + 2а2 + о3 — 5, «3 = 27a0+9ai -t-3a2y- ct3= 14.
Решим полученную систему:
О<) + О1+ <72= 1,1 8czo + 4aj+ 2й2= 5,1 27 tZg+9а i + За2 =14.)
Для этого вычтем из 3-го уравнения утроенное первое, а из второго — удвоенное первое. Тогда получим
24а0+6<7i = 11, 1 6а0+2а] = 3; J
6о0 = 2, а0 = —- , ал = —, а2 — —- . О	Z	О
Таким образом,
н„ = -^-п3 + — п2 + — п =
"	3	2	6
= п (2n2 + 3n+ 1) _ п(п+ 1)(2я+ 1) 6	~	6
т. е. 12+22+ ... +п2= п-(п+ 9 <2п У>..
6
Замечание. Мы могли бы и не использовать результатов задачи 24. Для этого нужно было, получив ответ, доказать его методом математической индукции.
27.	Обозначим «л=1 *2 + 2’3+...+ +п(п+1).
Тогда Дп„=п(п+1) —многочлен второй степени. Поэтому из результата задачи 24 следует, что и п—многочлен 3-й степени. Положим
ип — апп3 + atn2 + а2п + а3.
Для вычисления а0, aj, а2, а3 подставим значения п=0, 1, 2, 3. Получим систему четырех уравнений с 4-мя неизвестными: ио=а3=О, Ui = ЙО +	+ 02 + Яз = 2,
и2 = 8а0-1-4а1 +2а2 + а3=8, u3=27a0+9ai + За2+а3=20, которая сводится к системе
Оо + О1 + в2— 2, 8o0+4ai + 2а2= 8, 27<Zo+9czi + За2=20.
Вычтем первое уравнение из 2-го и утроенное первое из 3-го. Получим
Зао+ Qi= 2,1 24a0+6ai = 14.J В полученной системе вычтем ушестеренное первое уравнение из 2-го:
6п0 = 2; а0 = -i-; == 1; a2 = -|—
Поэтому
1	3 I 2 	2
u„ — — nA 4- я 2 4-n =
"	3	3
_ n3 + 3n2+2n _ n(n + !)(» + 2) ~	3	~	3
t. e.
1-2+2-3+...-M («+!)= П (n+1^(n+-22- .
28.	а) Из определения арифметической прогрессии имеем
«л = «л-1 + d = «л-2 + 2d = .. .= =	+ (п—l)d.
б) Из определения геометрической прогрессии имеем
«1 = «л-1? = «л-2?2= • • • =«i?n-1.
29.	а) Нам надо найти следующую сумму:
S„ = «14- «2 4- • • - + «л-14- «„•
Из задачи 28 а) мы знаем, что эту сумму можно записать следующим образом: Sn = «1 + («! + d) + («J + 2d) + ... +
+ [«j + (я — 2) d] + [Mj + (п —1) d]. Эту же сумму можно переписать, переставив члены в обратном порядке: S„=[«i + (и—l)d]+[uj+ (п—2) d]+.. •+ + (uj + 2d) + (uj+d) +ui.
Сложим два полученных равенства
25й =-{»! +[M1 + (n-l)d]} +
“К [И1 + (п— 2) d]} + • • • +
+ {[14 4~ (п — 2)d] + (h.j -f- d)} +
+ {[Wi + (n — l)d] 4- nJ-
(Каждый член из верхней строки сперва складывается со стоящим под ним членом из верхней строки.) Ясно, что сумма в каждой фигурной скобке равна 2io + + (я—l)d. Таких фигурных скобок у нас п. Поэтому
2Sn = «[2^ 4- (я—1) d] — 2utn 4- п(п—1) d,
Q	, п (п — 1) ,
sn = «1«+ - 2 d-
б) Нам нужно найти
Рп=Н1-н2.....ип_г«„.
Из задачи 28 6) известно, что Р„ можно записать следующим образом:
Рп =	... • urqn~2  и^1 =
=	+ 2 + • + (Я — 2) + (л — 1)«
Но мы знаем (см. стр. 11), что 1+2+ ... +
+ (я—2) + (я—1) = —. Поэтому
п (П —I)
Рм = «'19	2	•
30.	а) Согласно формуле, полученной в задаче 29 а),
О ,, „ , п(п— 1) ,	15-14	1
о =	---------- d =---------= 35.
"	1	2	2	3
б) По формуле, полученной в задаче 29 6),
n (п — 1)	______ 15-14
15-14	1
= 10 2	3 = 1035.
31.	а) Мы знаем, что у арифметической прогрессии Ui = u3—2d; U2—u3—d; Ui=u3+d; U5 — u3+2d. Поэтому сумма первых пяти членов равна
S$=Ui + U2 + U3 +	(из—2d) +
+ («з— d) +1/3+ (из+d) +
4- («з4-2d) = 5п3=0.
б) Нам нужно найти
P5 = U1-U2,«3-U4,«5.
Мы знаем, что у геометрической прогрессии
U,	«3	п
«1 = 4-; и2=-^-’, ilt^Usq; u5 = usq^.
q2	q
Поэтому
^5= -V-—•кз*«з?-Из92=^-45=1024. q2 q
32.	Нам нужно найти сумму первых п членов геометрической прогрессии, т. е. величину
5л = «1 + «2 + Н3 + • • - + Un ~
— ut ф- urq 4- u^tf- 4-... 4* «i<7" *.
Рассмотрим величину qSп—Sn:
qSn — Sn =q(ll1+u1q+u1q2+ ... 4-ZZ1gn-1)—
— (аг+ Urq+ Utq^+ ...+ Uj/J"-1) =
= iixq 4- tt# 4- «i93 + ••• + ^q"-1 4- «19"— — th — ui<7 — «192 — • • • — «i9n~2 — ui9re-1-
Мы видим, что в этой сумме взаимно уничтожаются все члены, кроме первого и последнего, т. е.
qSn —Sn = щср — Hj, S„(9— 1) = и19л —«1.
Q »19п — »l
9-1 ‘
33.	Легко видеть, что число людей, которым сообщили новость в конце 1-й десятиминутки, равно 2, число людей, которым сообщили новость после 2-й десятиминутки, равно 4 и вообще число людей, которым сообщили новость в конце k-н десятиминутки, равно 2ft.
Число всех людей, которые будут знать новость через 10# минут, равно числу людей, узнавших эту новость через 0 минут (т. е. 1 человек), плюс число людей, узнавших новость через 10 минут (2 человека), плюс число людей, узнавших новость через 20 минут (4 человека), и так далее до людей, узнавших новость через £-10 минут (2* человек).
Поэтому это число людей равно
Sft = 1 + 2 + 4 + ... + 2*.
Мы видим, что есть сумма первых £+1 членов геометрической прогрессии с первым членом 1 и знаменателем 2. Поэтому
= l-2ft+i—1 =2*+i_i k 2—1
Теперь для решения задачи осталось найти наименьшее k, при котором Sk, т. е. число всех людей, которые знают новость через £-10 минут, будет больше 3000 000 (общее количество жителей города). Легко видеть, что это наименьшее £ = 21, так как
222—1=4194303.
Таким образом, все жители города будут знать новость через 210 минут= =3 часа 30 минут.
34.	Обозначим через at, да, аз, а4 и с6 количество времени, затраченное велосипедистом на 1-й, 2-й, 3-й, 4-й и 5-й круги соответственно, а через bit bi, b3, bt, b5 — те же времена для кавалериста.
6 С. И. Гельфанд и др.
81
Тогда из условия задачи мы знаем, что числа alt .... 05 образуют геометрическую прогрессию со знаменателем 1,1, а числа bi, bs — арифметическую прогрессию. Обозначим разность этой прогрессии через d. Мы знаем, что ai~b\ и что tzi + а2 + аз+04+05 = bi + 62 + &з + 64+^5. Используя формулы, полученные в задачах 29 и 32, последнее уравнение можно переписать следующим образом:
cyl, Г— at
1.1 — 1
с . 5-4 , = 5О1+—- d,
^(10(1,Is — 1) — 5) = 10d, d _	10(1,Р — 1) —5
~	10
Нам нужно найти отношение —-
Ьъ   о1 + 4d _ 1	4	_d_
Os “ Cj 1,14 ~ 1.1*	1.14
Подставляя сюда полученное значение d
—, имеем
а,
Ьъ 1________.__4 . 10(1,15 — 1) — 5 =
с4 = 1,14	1,14 ’	Ю
=	+4(l,ls—1) —2)=^
= -J— (4-0,6105 — 1) = l.l4
-~4421 ^ 0,986 < 1
1,4641
Таким образом, мы видим, что кавалерист затратил на последний круг примерно в 0,986 раза меньше времени, чей велосипедист.
35.	Нам нужно найти сумму 1+3-J-+ 5+...+997+999. Ясно, что это есть сумма первых 500 членов арифметик-
ской прогрессии с первым членом 1 и разностью 2. Поэтому наша сумма равна 1-500 + 500'499 -2= 500 + 500-499=
2
= 500-500 = 250 000.
36.	Вычтем из суммы всех положительных трехзначных чисел S(l> сумму положительных трехзначных чисел, делящихся на 2 (S(2>), и сумму положительных трехзначных чисел, делящихся на 3 (S(3)). При этом числа, делящиеся и на 2 и на 3, т. е. делящиеся на 6, мы вычитали 2 раза.
Поэтому для получения ответа нам к полученной разности нужно добавить сумму всех положительных трехзначных чисел, делящихся на 6 (S(6))> т. е. взять величину
S = SO) — S<2> — S<3> + S<6>.
Каждая из четырех написанных справа сумм есть сумма некоторого числа членов соответствующей арифметической прогрессии. Это число членов и разность прогрессии указаны в таблице.
	“1	п	d
I	100	900	1
II	100	450	2
III	102	300	3
IV	102	150	6
Поэтому =100-900+ 9С°2899 - 1 = =90 000 + 404 550=494 500,
S(2) = Ю0-450 + — 449 -2 = 247050,
2
да = юг-зоо + —°'299 .з =
2
= 30600 + 134550 = 165 150, да= 102-150 +	,6==82 350
2
s = s<*> — да—да + да = 164 zoo.
37.	Для любой последовательности n-й член получится, если из суммы первых п членов вычесть сумму первых (п—1) членов, т. е.
“n = Sn — Sn-l-
В нашем случае
ип = Sn — S„_x = Зл2 —3(n —I)2 = 6n — 3. Найдем теперь ип—ип_г\
= (6л — 3) — [6(л —1) — 3] =6. Мы видим, что разность двух соседних членов последовательности и„ постоянна и равна 6. Это значит, что наша последовательность есть арифметическая прогрессия с разностью 6. Первый член ее равен Wi=Si=3.
38.	Предположим, что мы уже нашли интересующую нас геометрическую прогрессию. Пусть число 27 стоит в ней на т-м месте, 8 — на п-м и 12 — на р-м. Обозначим через wt первый член прогрессии и через q — ее знаменатель. Тогда получим
27 = щдт~\
8 =
\2 = u1qP~\
Деля почленно первое равенство на второе и третье, получим
27
— = От~п,
8 а
— =пт~Р.
4 v
Возведем первое равенство в степень in—р, а второе — в степень п—р и приравняем их правые части. Тогда получим
дЗ/п—Зр—2т+2п   <23т—3р~2т+2п
д/и—Зр + 2л _
Нетрудно видеть, что последнее равенство может выполняться только в случае, когда т—Зр + 2п=0. Пусть обратно, т, п, р — целые положительные числа такие, что т—Ър+Чп^О. Тогда выполняются равенства gm—Зр-|-2/г _______
/ 27 \т~Р __ / 9 \т~п \“П
Пусть ? = ]/ —, тогда
27	о
— = пт~п и — = ат~р. 8	4	7
Обозначим через ut такое число, для которого 12 = uiqp~1	(такое число всегда
27 существует). Тогда из равенств ——qm п 8
9	_
п —== qm р следует, что 4
8 =
27 = u^-1.
Это означает, что в геометрической прогрессии со знаменателем q и первым членом числа 27, 8 и 12 стоят на m-м, n-м и р-м местах. В качестве примера такой последовательности приведем з последовательность с «1=8, <?=“• В ней т=4, п=1, р--2.
39.	Предположим, что мы нашли геометрическую прогрессию, в которой числа 1, 2 и 5 стоят на m-м, n-м и р-м местах соответственно. Тогда
1 =
2 =
5 — u1qp~1.
Деля второе и третье равенства на первое, получим
2 = qn~m,
5 = цР-т.
Возводя первое равенство в степень р—т, а второе — в степень п—т и приравнивая их правые части, получим
<2Р~ т — §п—т
Ясно, что это равенство может выполняться, только когда р—т=0 и wi—т=0, так как в противном случае справа стоит нечетное число, а слева — четное.
Но по смыслу задачи ясно, что числа т, п и р все должны быть различны. Поэтому наше предположение о существовании геометрической прогрессии с нужными свойствами привело к противоречию, и такой прогрессии не существует.
40.	Обозначим через «12, Щз, «15 соответственно 12-й, 13-й и 15-й члены арифметической прогрессии. Мы знаем, что числа «®2, ы,3, и?{5 образуют геометрическую прогрессию, т. е. что
2	2
"13 = "15 2	2
"12	"13
Извлекая квадратный корень из обеих частей этого равенства, получим, что либо
«13 __ «15
«12	«18
либо
«13 _  «15
«12	«13
Рассмотрим первое равенство. Для любой арифметической прогрессии Н]3= = Ui2+d, Hi5 = tZi3 + 2d=Hi2+3d, где d— разность прогрессии. Поэтому
«la 4~ d _ «1з 4~ 2d
^12	Ы13
14- — = 1 4- —, «12	«18
d __ 2d
«12	«13
Предположим, что d^=0, тогда
и2
ДИ- = 2, -^ = 4, «12	«12
т. е. в этом случае знаменатель полученной геометрической прогрессии равен 4.
Аналогично можно рассмотреть случай, когда выполнено равенство
«13   «15 «12	«13
В этом случае, проделывая такие же действия, получим равенстваi
и22 + 4«!2 d -|- d2 = О,
( — У 4-4-А-4-1=0, _Д_ = — 2 + У~3~.
«12
Случай а): ~^— =—2+/-3". «12
7 = /±1^\2=4 —2/3.
\ «12 /
Случай б): ——= —2—/ 3 
W12
= 1 + ~ = — I — / 3", «12	«13
q = ( ±1+ V=4 + 2 /Т.
\ «12 /
Таким образом, из равенства
«13 	«15
«12	«13
следует, что q может равняться либо 4—2/ 3, либо 4 + 2/ 3.
Остается еще случай rf=0. Ясно, что в этом случае 7=1.
41.	Пусть у нас есть такая геометрическая прогрессия. Тогда для нее выполнено равенство
н1<7п+1 = //17п+н1<7п-1при всех п. Отсюда следует, что
72 = ?+ Ь
Таким образом, знаменатель геометрической прогрессии, у которой каждый член равен сумме двух предыдущих, может 1+/5 принимать только значения ---%--- и
1—/У „
-—£—Ясно, что верно и обратное, т. е,
что у любой прогрессии с одним из этих знаменателей каждый член равен сумме двух предыдущих.
42.	Обозначим первый член первой прогрессии через U\, ее знаменатель через q, первый член второй прогрессии через vt, а ее знаменатель через р. Мы знаем, что
ui + vi — о, »i<7 + viP = °-
Нам нужно найти, чему равно uiq2+vtp23 ulq2 + vlp2=uiq2—uip2=ui(q2—р2) =
= ui(<7—р) (q+p).
Но из равенств
«1 +»! =0,
utq + viP=O
следует, что Ui(q—р)—0.
Поэтому Utq2 + vip2 = iii(q—р) (q+р) = =0, т. е. третий член нашей последовательности тоже равен 0.
43.	Нам нужно найти две геометрические прогрессии {ип} и {гп} , для которых выполняются равенства
И\ + == 1, ы2 + 02 = 11
Un + Vn = Un-1 + Vn-1 + Un-2 + Vn-2‘
Обозначим через р и q знаменатели этих прогрессий. Ясно, что p^q, так как сумма двух геометрических прогрессий с одинаковыми знаменателями снова есть геометрическая прогрессия, а последовательность Фибоначчи не является геометрической прогрессией. Наше последнее равенство можно записать
следующим образом:
=
— ы1<7"~2+ &1Р"-2 + ад"-3 + t'iP"-s, u1qn-z(q1 — q — 1) = — vlPn~2 (р2 — р — 1).
Покажем, что тогда р2—р—1=0 и q2— —9—1=0. В самом деле, пусть это не так, и пусть, например, р2—р—1 =^0. Тогда, поделив обе части последнего равенства на
Viqn 3(р2— р— 1),
получим
<7* —<7—1 .
Ч р2 — р — 1
при всех п>3.
Левая часть равенства не зависит от п, значит, и правая не должна зависеть от п. Но это может быть только в том случае, если p — q. Однако мы уже видели, что p=kq. Таким образом, мы пришли к противоречию, т. е. наше предположение о том, что р2—р—1=И= 0, неверно. Поэтому р2—р—1=0. Аналогично, q2—q—1=0. Из этого следует, что р и q являются корнями уравнения х2—х—1=0, причем различными. Кор-
1 —I—т/” 5 нями этого уравнения служат —------ и
1-/Т л
---2---• Положим, например, р=
1 + |/”5	1—у/ 5 т т «
=----2---’ 9—----2---' Найдем теперь
«1 и vt. Для их нахождения у нас есть два уравнения
“i
Hi +	= 1,
1 + V 5
2
= 1.
Из них мы получаем, что
1 + V Т — 1 + / Т “1 = ; ^1= —“ — • 2/5	2 У 5
Поэтому
Следовательно,
ап = «л + Vn =
1 г/1 + /Т\п /1 — /TV] /Т[\ 2 /	\ 2 2 J
Глава 2
44. Первое решение. Число способов освещения, при которых горит одна лампа из пяти, равно числу способов освещения, при которых горят 4 лампы из пяти (рис. 32/
ое®е®~®оооо •oe®e~otooo ©®оее~ооесо t®eo®~ooo®o еееео^сооое
рис. 32*
Аналогично, число способов освещения, при которых горят 2 лампы из пяти, равно числу способов, при которых не
горят 2 лампы из пяти (т. е. горят 3 лампы из пяти). Эти способы показаны на рис. 33 (10 способов, при которых горят
Вс
ооооо
гмс. 55
Вс<г лаллы ki ЪорлГ-.
РМ€. 3%
2 лампы, и 10 способов, при которых горят 3 лампы). Имеются еще два способа (рис. 34) (все лампы горят, все лампы не горят). Мы перебрали все способы освещения и теперь их легко сосчитать.
Второе решение. 1) Пусть в кухне имеется одна лампа. Она может быть в двух состояниях: не гореть • или гореть О , т. е. способов освещения 2.
2)	2 лампы. Первая лампа может быть в двух состояниях: • и О.
Каждое из них можно скомбинировать с любым из двух состояний второй лампы: если вторая лампа не горит, получаем 2 способа освещения.
Если вторая лампа горит, получаем еще 2 способа
Всего способов освещения 4:
• • О О
3)	3 лампы. Первые две лампы могут быть в четырех состояниях. Каждое из этих четырех состояний можно скомбинировать с любым из двух состояний третьей лампы.
Всего способов освещения 8:
4)	4 лампы. Первые три лампы могут быть в восьми состояниях. Каждое из них можно скомбинировать с любым из двух состояний четвертой лампы. Имеется 8-2=16 способов освещения.
5)	5 ламп. Имеется 16-2 = 32 способа освещения. Рассмотренный метод решения допускает незначительные модификации: переход от двух ламп к трем
можно иллюстрировать не только приведенной выше схемой, но и следующими схемами:
Обе они тоже показывают, что добавление одной лампы (которая может быть в двух состояниях) увеличивает число способов освещения вдвое.
45. Сколько имеется способов освещения, если есть п ламп? Подсчитаем это число двумя методами (ср. с решением задачи 44).
Первый метод:
0) Может не гореть ни одна лампа. Таких способов освещения С° (горят 0 ламп из п). Ясно, что С° = 1 при любом п. Тем не менее, чтобы доказываемая формула выглядела «красиво», мы будем писать не 1, а С°.
1) Может гореть ровно 1 лампа из п. Таких способов освещения С1
2) Через С2п обозначено число способов освещения, при которых горят 2 лампы из п.
к) Когда горят k ламп из п, получаем Скп способов освещения.
п) Наконец, могут гореть все п ламп. Таких способов освещения С". (Снова ясно, что С" =1.)
Итак, всего способов освещения:
с£ + с;+с* + ...+с£+... + с;.
Второй метод. Обозначим число способов освещения п лампами (каждая из которых может гореть или не гореть) через Dп. Докажем по индукции, что Dn = 2" (по существу, это уже доказано в указании к этой задаче).
Di — число способов освещения при наличии одной лампы, очевидно, равно 2. Далее, £>Я=2ПП_1 (каждый способ освещения (п—1)-й лампой порождает 2 способа освещения п лампами: п-я лампа может гореть и не гореть). Значит, из предположения Dn_t = 2”~1 вытекает, что Dn =2" . Итак, D п=2п . Но выше мы показали, что
^=cn0+Q+-+^+-+c2.
Следовательно,
^+q+...+^+...+(>=2".
46. Если есть только один светофор, то способов включения 3. Добавим теперь второй светофор. Из всякого способа включения одного светофора, изменяя состояние второго, мы можем получить три способа включения двух. Значит, число способов увеличится втрое. Итого: 3-3 = 32 способов. Добавим третий светофор. Из всякого способа включения двух светофоров снова можно получить три способа включения трех светофоров, изменяя состояние третьего. Снова число способов увеличится втрое. Для трех светофоров способов будет 3 - 32 = 33. При добавлении одного светофора число способов всегда увеличится втрое. Значит, п светофоров можно зажечь 3" способами.
47. Пусть первые k светофоров горят каким-то способом (таких способов 3*, см. задачу 46), при этом остальные можно зажечь 2"~* способами (см. зада-
чу 45). Значит, из каждого способа включения k первых светофоров можно получить 2"—k способов включения всех светофоров. Значит, всего способов 3*.2«-Л
49.	Ответ: 104-323 номеров (в алфавите 32 буквы).
50.	Поставим в соответствие каждому жителю царства последовательность из 32-х нулей и единиц по следующему правилу: если у жителя есть первый зуб, то поставим на первое место последовательности 1, а если нет, то 0; если у жителя есть второй зуб, то поставим на второе место последовательности 1, а если нет, то 0; если у жителя и т. д. (мы предполагаем, что зубы раз и навсегда как-то занумерованы). Из условия ясно, что разным жителям будут поставлены в соответствие разные последовательности, поэтому максимальное число жителей в царстве равно просто числу таких последовательностей. А число таких последовательностей 232 (см. решение задач 44 и 45). Кстати, 232 ~4 ООО 000 000 (четыре миллиарда). Это больше нынешнего населения земного шара.
51.	Рассмотрим слагаемые, которые получатся после раскрытия скобок, но до приведения подобных. Каждое такое слагаемое есть произведение ста сомножителей, причем любой из этих сомножителей есть либо буква х, либо цифра. Первый сомножитель есть либо х, либо — 1, второй сомножитель есть либо х, либо —2 и т. д. Нас интересуют только такие произведения, в которых 99 раз встречается х и 1 раз встречается число. Таких будет сто, так как число может
встретиться на первом, на втором и т. д. на сотом месте.
Соответствующие произведения будут:
— 1 -x-x-...-х, х-(—2)-х-х-...-х, ...» 99 раз	98 раз
х-х- ...-х-(— 100).
99 раз
Значит, коэффициент при х" равен 101-100
- (1+2+3+...+100) = — —~— = —5050 (в скобках стоит сумма членов арифметической прогрессии. См. главу 1).
52.	А. Порядок существен. В этом случае каждое разложение определяется первым слагаемым, которое может быть любым натуральным числом, меньшим п (при этом и второе слагаемое будет натуральным числом). Значит, всего разложений будет п—1.
Б. Порядок несуществен. Если п нечетно, то разложений вдвое меньше, чем в случае А, так как разложения п=1 + (п—1) и п= (п—1) + 1, га=2 + + (п—2) и п—(п—2)+2 и т. д. теперь л	п—1
считаются одинаковыми. Ответ: j -Если же п четно, то для разложения
любого другого найдется. Отсюда получаем ответ:
1 -L (п —') —1 _ JL
2	2
53.	Подсчитаем, сколько есть разложений, у которых первое слагаемое 1. Сумма второго и третьего слагаемых должна быть п— 1. Ясно, что таких раз-
7 С. И. Гельфанд и др.
97
ложений столько же, сколько разложений числа п—1 в сумму двух слагаемых. Но мы уже знаем, что их п—2 (см. решение задачи 52). Точно так же число разложений, у которых первое слагаемое 2, равно п—3 и т. д. Разложений, у которых первое слагаемое п—2, одно. Вот мы и подсчитали все разложения. Их будет
(п—2)(n—1) (п-2) + (/г-3) +...+2 +1 = -------
(Слева стоит сумма членов арифметической прогрессии.) Подсчитайте таким же способом число разложений в сумму четырех слагаемых. Ответ к этой задаче;
(п—1)(п—2) (п-3)
6
Еще одно решение задачи 53 смотри в замечании к решению задачи 60.
54.	Применим метод математической индукции. При /2=1 (вторая строка) сумма чисел равна 2. Докажем, что сумма чисел в (/г+1)-й строке вдвое больше. чем в /г-й. Для этого напишем п-ю и (п+1)-ю строки треугольника Паскаля в следующем виде;
1 а Ь ... f g 1
0+1	1+а а+Ь ... f+g g+1	1+0
вычислим сумму чисел в (л+1)-й строке
(0+1) + (1+а) + (а + Ь) +' + .„+(/+£) + (£+1) + (1+0).
Для этого сложим сначала первые слагаемые каждой скобки, а затем вторые слагаемые. Получим
(О+1+a + b + ...+f+g+l) +
+ (1 +a + fc + ...+g+ 1 +0) =
= 2(1 +a + fe + ...+/+g+l).
Слева стоит сумма чисел (п + 1)-й строки, а справа — удвоенная сумма чисел п-й строки. Теперь ясно, что сумма чисел в (п+1)-й строке равна 2Л.
55.	В указании к задаче показан конкретный пример расстановки 14 слонов. Следовательно, 14 слонов расставить можно. Если мы докажем, что больше чем 14 слонов расставить нельзя, то первая половина задачи будет решена. Рассмотрим сначала чернопольных слонов. Сколько их можно расставить на шахматной доске, чтобы они не угрожали друг другу? 7 поставить можно; докажем, что нельзя поставить больше. Выберем 7 черных диагоналей, параллельных друг друту (рис. 35). На одной
диагонали может стоять максимум один слон. Поэтому ответ: 7. Если мы возьмем «черные» диагонали, перпенди
кулярные указанным, то их окажется 8 (причем крайние будут содержать по одной клетке). Рассматривая эти диагонали, тоже можно было бы убедиться, что больше семи слонов поставить нельзя (действительно, если поставлено восемь слонов, не бьющих друг друга, то два из них должны оказаться на крайних диагоналях, но так как каждая из этих диагоналей состоит из одной клетки, то эти два слона должны оказаться в противоположных углах доски, т. е. бить друг друга). Но это рассуждение излишне, так как мы получаем наш результат более простым способом, выбрав диагонали, как указано на рис. 35.
Максимальное число белопольных слонов, не угрожающих друг другу, тоже равно 7. Белопольный и чернопольный слоны не могут угрожать друг другу. Значит, всего на доске можно расставить максимум 14 слонов, не угрожающих друг другу.
Обозначим через Б число способов расставить 7 белопольных слонов, не угрожающих друг другу; через Ч — число способов расставить 7 чернопольных слонов, не угрожающих друг другу; наконец, через С—число способов расставить 14 слонов, не угрожающих друг другу. Ясно, что Б=Ч, С=Б- Ч—(Ч)2, т. е. С — квадрат некоторого числа.
Замечание. Решите более общую задачу. Пусть доска имеет размеры пх«, п — четное. Докажите, что наибольшее число слонов, не угрожающих друг другу, равно (2п—2). Докажите, что число способов расставить (2п—2) слонов, не угрожающих друг другу, равно 2".
56.	Вот один способ раздать яблоки и груши: оеоее 'в 1 -й и 3-й день — яблоки, во 2-й, 4-й и 5-й дни — груши),
вот еще один способ: •••оо
(в первые три дня — груши, в последние два—яблоки). Итак, нужно пересчитать все таблички из двух светлых и трех темных кружков; но мы уже сделали это, решая задачу 44. Ответз С2 =10.
57.	Каждому способу раздачи сопоставим табличку из k светлых и п темных кружков; дни, когда выдают яблоко, отмечаются светлым кружком; дни, когда выдают грушу, — темным.
Таким образом, задача эквивалентна следующей:
Имеется (n+k) ламп. Найти число способов освещения, при которых горят k ламп.
Остается вспомнить, что это число мы обозначили через C*+ft (явное выражение через п и k можно получить, сопоставив ответ с результатами задач 60, 66 и 67).
59. Мы уже доказали, что на каждой вертикали стоит ровно одна ладья (см. указания). Разумеется, и на каждой горизонтали стоит тоже ровно одна ладья. Ладью на вертикаль а можно было поставить на любое из восьми полей (все горизонтали были свободны). Но после того, как эта ладья поставлена на доску, одна горизонталь уже занята (если, например, ладья стоит на поле а2, то на горизонталь 2 нельзя ставить другие ладьи). Поэтому на вертикаль b ладыо можно поставить только семью способами (в рассмотренном только что примере ее можно ставить на поля Ы, ЬЗ, Ы, ..., Ь8). После того как и ладья b поставлена на доску, заняты уже 2 горизонтали, а свободных горизонталей
остается 6, так что ладью с можно ставить на любое из 6 полей. Ладью d можно поставить пятью способами, ладью е — четырьмя, f — тремя, g — двумя, h — только одним. Итак, ладью а можно поставить на доску восемью способами. Число способов поставить на доску ладьи а и b равно 8-7. Число способов расстановки ладей а, b и с равно 8-7-6 и т. д. Ладьи а, Ь, с, ..., h можно поставить на доску 8-7-6-5-4-3-2-1 = = 8! способами (I обозначает факториал, см. задачу 5). Чтобы проверить, хорошо ли Вы поняли решение, решите задачу:-«Сколькими способами можно расставить на доске с пХп клетками и ладей, не угрожающих друг другу?» Ответ: п\. Еще раз проверьте себя. Сейчас будет дано другое решение задачи 59, причем получится... другой ответ (?!). Если Вы верите, что первое решение верное, то ищите ошибку во втором решении.
Второе решение будет дано сразу для доски пХп. Обозначим число способов расстановки п ладей (не угрожающих друг другу) на доске пХп через L п. Докажем, что £п = (л!)2.
Доказательство ведем по индукции. При n—1 теорема, очевидно, верна: £i=(l!)2 (на доске из одного поля можно расставить одну ладью одним способом). Покажем, что если £ „_х= =[(п—I)!]2, то £„=(nl)2. Для этого достаточно доказать, что Ln=n2-Ln_v Рассмотрим одну из ладей. Ее можно поставить на любое из п2 полей. Дальнейшие рассуждения иллюстрируются рисунками, причем на рисунках п=4. Итак, пусть первая ладья поставлена на одно из полей (на поле Р, рис. 36). Вырежем из доски проходящие через это поле вертикаль и горизонталь (на рисунке они заштрихованы). Остальные ладьи нельзя ставить на эти вертикаль и гори-
зонталь. Из частей, на которые распалась доска (на рисунке они обозначены А, В, С и D), сложим доску размером (п—1)X(п—1), сдвинув части параллельно самим себе. На исходной доске
ЛАДЬЯ CTOWT НА ПОЛЕ Р
PUC.36
расставим все п ладей так, чтобы они не угрожали друг другу и чтобы первая ладья стояла на поле Р. При этом все ладьи, кроме первой, окажутся на не-заштрихованных полях. Будем сдвигать части А, В, С и D вместе со стоящими на них ладьями. Тогда на полученной доске (п—1)Х(п—1) получится расстановка п—1 ладьи, причем ладьи не угрожают друг другу. Разным расстановкам ладей на первой доске соответствуют при этом разные расстановки ладей на второй доске, и каждая расстановка ладей на второй доске может быть получена таким образом. Всего различных расстановок на второй доске . И поле Р можно выбрать п2 способами. Значит, Z.„=n2
Где ошибка?
Может быть, найти ошибку и не просто. Тем более, что доказательство пе очень простое. Чтобы облегчить Ваши поиски, приведем еще одно доказательство (уже для случая п=4).
Итак, сколькими способами можно расставить 4 ладьи на доске 4X4, чтобы они не угрожали друг другу?
Первую ладью можно поставить на любое из 16 полей. После того как ладья поставлена на некоторое поле (см. рис. 36), остальные ладьи можно ставить только на незаштрихованные поля. Значит, вторую ладью можно поставить на доску девятью способами. Чтобы поставить третью ладью (когда поставлены первые две), остается 4 поля. Наконец, четвертую ладью можно (когда поставлены первые три) поставить единственным образом (чтобы ладьи не угрожали друг другу). Итак, £4= 16«9-4• 1 = (4!)2.
Где же ошибка? Подумайте, прежде чем читать дальше.
Решение было бы верным, если бы на ладьях были написаны номера. При этом расстановки, изображенные на рис. 37,
Рису»
были бы различными. Если номера не написаны, то это одна и та же расстановка (рис. 38).
Итак, мы доказали следующие 2 теоремы:
1) Число 1п расстановок п ладей*) на доске пХм равно п\, если ладьи не различимы.
*) Не угрожающих друг другу.
2) Число Ln расстановок п ладей *) на доске пХп равно (и!)2, если ладьи перенумерованы.
Каждая из этих теорем легко выводится из другой. Убедимся в этом снова для п=4 (потом проведите это рассуждение в общем виде).
На доске 4X4 отметим 4 поля, удовлетворяющих следующему требованию: если расставить на отмеченные поля 4 ладьи, то они не будут угрожать друг другу. Назовем отмеченные поля а, Ь, с и d. Ясно, что число различных способов отметить 4 поля равно Ц. Напишем на ладьях номера: 1, 2, 3 и 4. Пусть Р4 — число различных перестановок ладей 1, 2, 3 и 4 на полях а, Ь, с и d. Число не зависит, конечно, от способа выбора отмеченных полей: если А, В, С и D — какие-нибудь другие отмеченные поля, то число различных расположений ладей 1, 2, 3 и 4 на полях А, В, С и D тоже равно Р4. Поэтому ЬА = Р^-Ц. Остается подсчитать число Р4. Сделайте это сами. Ответ: Р4=4!. Таким образом, Р4//4=4!. Верна и более общая формула Lnlln=n\ (проверьте). Поэтому, зная, что 1п=п\, находим, что £„=(п!)2; и обратно, зная, что L„ = (nl)2, находим, что 1п=п\. Выше мы употребили символ Рп; Р„ — это число способов расставить п перенумерованных ладей на п фиксированных полях доски.
60. Перенумеруем п предметов: 1, 2, ..., п. Теперь каждый способ выбрать '2 предмета из п соответствует паре чисел (номера выбранных предметов), причем пары (/г, т) и (т, k), очевидно, определяют один и тот же способ Итак, (Р равно числу пар (1, 2), (1, 3), .... ..., (п—1, п).
) Не угрожающих друг другу.
Первый номер в паре может принимать п значений, второй — остальные п—1 значений. Всего пар л(л—1). Но пары номеров (k, т) и (т, k) при этом сосчитаны обе, хотя они определяют одну и ту же пару предметов. Значит,
_ n(n — 1)
Замечание. Теперь мы можем дать новое решение задачи 53.
Разбиение числа п на 3 слагаемых можно представить себе так: есть спииа (как в счетах), на которую надето п костяшек, затем костяшки раздвигаются в двух местах. Между костяшками п—1 промежуток. Выбрать из них два (где мы раздвигаем костяшки) можно C„_j способами. ,,	„2 (п—1)(л—2)
Итак, ответ: Cn_t ='--М------.
62. Обозначим число способов раздать 5 попарно различных апельсиноз восьми сыновьям через Подсчитаем Л| двумя методами.
Первый метод. Число способов выбрать из восьми сыновей пятерых (тех, которые получат апельсины) равно Cg. Любому такому выбору соответствует 5! способов раздачи апельсинов (число способов раздать 5 попарно различных апельсинов пяти сыновьям). Значит, Ag^Cg *5!.
Второй метод. Первый апельсин можно дать любому из 8 сыновей. Второй — любому из оставшихся 7 сыновей и т. д. Пятый — любому из оставшихся 4 сыновей (остальные трое не получат апельсинов). Итак, Д8 = 8’7-6-5-4 = -|--.
р
63. Докажем, что на (&+1)-м месте (п+1)-й строки треугольника Паскаля стоит С*. Доказывать будем индукцией по п. Для п=1 теорема верна. Действи
тельно, во второй строке треугольника Паскаля на первом месте стоит 1 и на втором месте стоит 1 = С*. Предположим, что теорема верна для п. Докажем, что тогда она верна и для п+1. Если £=0 или & = п+1, то теорема верна, так как , =1, С"^}=1, а в любой строке треугольника Паскаля на первом и последнем месте стоят единицы. Вспомним теперь, что С* есть число способов включения k ламп из п. Посмотрим, сколько есть способов включения k ламп из п+1. Если последняя лампа горит, то остальные могут гореть С*-1 способами (из остальных ламп мы можем включить любые 1). Если же последняя лампа не горит, то остальные можно включить С* способами. Тем самым доказано, что С*+1 =С*~* + С*. По индуктивному предположению в (п+1)-й строке треугольника Паскаля стоят числа & . А по определению треугольника Паскаля в следующей строке будут стоять числа:
I, С2 + С‘, с\ + с2п,..., СГ' + С'п, 1. По доказанному, эту строчку можно переписать так:
1.	C^+i,..., C^+i, 1.
Это и означает, что теорема верна для п+1. Индукция окончена.
66.	Подсчитаем сначала, сколькими способами из п предметов можно выбрать три в определенном порядке. Первым можно взять любой предмет, вторым— любой из п—1 оставшихся, третьим— любой из п—2 оставшихся. Всего п(п—1) (п—2) способов. Но при таком способе действий мы каждый набор предметов (без учета порядка) получим
ровно шесть раз (набор, состоящий из предметов А, В, С, мы получим в шести видах: АВС, АСВ, ВАС, ВСА, САВ, С В А). Значит, выбрать три предмета из п — без учета порядка выбора —
п(п— 1)(п—2)
можно 7 способами.
О
67.	По определению С*, k предметов из п можно выбрать Сп способами. Можно решать нашу задачу (т. е. найти для Сп явную формулу) так же, как и предыдущую. А можно воспользоваться индукцией. Мы доказали в задаче 63, что
Ck—1 I	s>k
fl ~Г — '“'л-1-1 •
Докажем индукцией по п, что
Ck — nf-n~ 0 (n~k + О
(условимся считать, что 0!= 1). Для п=1 наше утверждение верно. Предположим, что оно верно для п. Тогда по индуктивному предположению
гч п(п
сп+1 = ----
— 1)... (в — Л 4-2) (Л-1)!
п(п — 1)... (в— Л 4- 1) -
в(в—1) ...(п—Л4-2) / j . в — Л 4- 1 \
(Л-1)!	\ k )
(в 4- 1)-в(в — 1) ... (в 4- 1 — Л 4-1) Л!
Мы доказали, что наше утверждение верно и для п4-1. Индукция окончена. Полученную формулу можно переписать в виде
ck — п! п ~ Л! (п — Л)1
Число Ckn называется числом сочетаний из п по k.
Сп — число способов выбрать k предметов из п без учета порядка выбора.
Существует специальное обозначение и для числа способов выбрать k предметов из п в определенном порядке: Л„ • Мы уже применяли это обозначение в решении задачи 62; там были до-8!
казаны формулы: Л|=С®-5!=-gj-. Аналогичные формулы справедливы и в общем случае:
Р1
Проверьте это.
Число Л* называется числом размещений из п по k.
При k—n число Л* называют числом перестановок из п элементов и иногда обозначают через Р п.
Названия «число сочетаний из п по k» и «число перестановок из п» и обозначение С* общеупотребительны. Название «число размещений из п по k» и обозначения Л„ и Рп употребляются реже.
70.	Каждый из членов, которые получаются после раскрытия скобок в выражении
(с+1) (t>+1) (с+1) (d+1) (е+ 1) X
X (f+1) (g+1), есть произведение семи сомножителей (так как скобок семь). Любой из этих сомножителей — либо буква, либо цифра 1. Итак, мы должны найти число произведений семи сомножителей, каждый из которых может быть «в двух состояниях». Значит, наша задача эквивалентна следующей:
Найти число способов освещения семью лампочками, каждая из которых может гореть или не гореть. Ответ: 27.
71.	Прочитайте решение задачи 70. Нас интересуют такие произведения, в которые 3 раза входит буква и 4 раза — цифра 1. Таких произведений столько же, сколькими способами из 7 букв можно
7.6.5
выбрать 3, т. е. С? — j.2.3 =35.
Замечание. Повторяя почти дословно решение этой задачи, можно доказать, что после раскрытия скобок в выражении (1+fli) (1+Ог) — ...(1+ап) будет С* членов, содержащих k букв.
.72. Раскроем скобки в выражении г(1+х+у)20, но не будем приводить подобные. Каждый из членов, которые при этом получатся, есть произведение двадцати сомножителей. Причем любой из сомножителей — либо 1, либо х, либо у. Значит, наша задача эквивалентна следующей: сколькими способами можно зажечь 20 светофоров, каждый из которых может гореть либо красным, либо желтым, либо зеленым светом?
Ответ: З20 (сравните с задачей 70).
73.	Ответ: коэффициент при х17 равен 20Л918 коэффициент ПрИ х18 равен 0.
74.	Перечитайте замечание в конце решения задачи 71. Сравним два выражения:
(1+х)56и (1 + ai) (1+а2)...(1+О5б).
ЕСЛИ ПОЛОЖИТЬ О1=а2 = ... = О5б = Х, то второе выражение превратится в первое.
После раскрытия скобок в выражении (1+01) (1+а2)...(1 + а56) будет С? членов, содержащих 8 букв. Любой из
этих членов превратится в хв при замене каждой буквы ai, а2, азе на х.
Значит, коэффициент при хв в выражении (1+х)56 (после раскрытия скобок и приведения подобных) равен С|Б.
Аналогично, коэффициент при х48 равен С48 . 5о
Замечание. Числа С86 и равны. Поэтому коэффициенты при х* и при я** в выражении (1+я)56 равны. Точно так же равны между собой коэффициенты при я6 и при я50 в выражении (1+я)Е6. Вообще, в выражении (1+я)“ равны . .	Л	„п—k. ___г"—я
коэффициенты при я и при я ,	•
75.	Доказательство формулы (1+х)«-С? + С'х+С^2 +
+ ...+С^+ ...
почти дословно повторяет решение задачи 74.
76.	Проведем доказательство по индукции. При п—\ утверждение справедливо: (14-х)^ 1 +1 -х, биномиальные коэффициенты совпадают с числами 2-й строки треугольника Паскаля.
Предположим, что утверждение верно для п—1:
(1 +х)п-1 = о0 + а1х+ ... +
+ ак-1 + akxk + — + хп~\
где а0, Qi, ..., ak~i, ak.an—i —числа
из п-й строки треугольника Паскаля.
Докажем, что тогда оно верно и для п. Другими словами, нужно показать, что
(1 + х) ” = b0 + bLx + bkxk + ... + bnxn, где bo, bi, ..., bk,	b — числа из
(п+1)-й строки треугольника Паскаля.
По определению треугольника Паскаля имеем
fe0=l, b^ao + a,^.....Ьь = ak_± + ак,...
...» Ьп_г = ап_2 + ал_I, bn— I (= Qn_i).
Итак, нужно показать, что
(1 4- х)" = 1 + (а0 + nJх + ... +
+ К-! +ak)xk + ... +(a„_2+l)xn-i+bx«.
Но это очевидно:
(1+х)" = (1 +х)"-1(1 + х) =
=(ao~^aix~^~••^ап—1хП *)'(! +*)=
=a0+a1x+...+aftxfc +...-|-а„_1Хп-1-Ь
+Ц)*+ —+аЛ—1*^4" ••• + аЛ—2)(',~1+а/|-1 ХП =
1=ао+(ао+а1) •*+• - + (°А—1+°л)х<г+-" +
+(ол—з+ол—1) *П“1+ал—1 ХП
(Ь \п
1 + —j , то
член, содержащий ak, равен
п
79.	Найдем сначала все члены с xk. Напишем
(x+t/+z)n=[x+(f/4-z)Jn=
= ... + Cknxk-(y + zY~k Л-...
Теперь в выражении (y + z)n~k найдем член с у1'.
(у + г)л-*= ...+C^ky!zn^-l+ ...
Отсюда ясно, что член, содержащий xk-yl, будет
C^C^xW-^1.
Выражение С^-С1п_к можно несколько
преобразовать:
ek rl _ n!	(°— W
'''П •	--
kl (n — k)\ ll (n—k—l)\
= n'
~ fel/l(n—k—/)!
80.	Если в тождестве
(1 4~ х)" —Сп + Сп х-\ 7П х2+ ... +
+ С2~1х"~1+Слпхп
положить х=1, получим
2"=С° + С’ + С2+ ...+С-1 + С.
При х =—1 получим
0=С°-С'+ С^+...+(-1)^.
Складывая и вычитая почленно эти равенства, получим
С° + С2 + С^+...=С‘ +	+...=2"-1.
81.	Если в выражении (1 +х—Зх2)1965 раскрыть скобки и привести подобные члены, получится многочлен a0+ai-x+ + а2- х2+а3- х3+.... Заметим, что сумма его коэффициентов равна значению многочлена при х = 1
°о+аг 1+а2’ ^2_Ьаз‘	••• =
=a0-f-a1+a2+a3+ ...
Разумеется, на самом деле раскрывать скобки и приводить подобные не надо. Достаточно подставить х=1 в исходное выражение
(1 + 1—3. 1 2)1965 =(__])196Б= _ L
Итак, ао+а1 + а2 + аз+... =—1.
86. Ответ: С2—п. Решение: возьмем все пары различных вершин многоугольника (таких пар С2) и соединим
8 С. И. Гельфанд и др.
113
отрезками точки каждой пары. Получим С2п отрезков. Среди них будет п сторон, а остальные — диагонали, т. е. диагоналей будет —п.
91.	Перепишем более компактно условие задачи:
а	н	ф	ан	нф	фа	анф
6	6	7	4	3	2	1
Пусть из комнаты ушел человек, знающий три языка, тогда никто из оставшихся не знает более двух языков и мы имеем такую задачу:
анф
ан
нф
фа
анф
5	5	6
О
1
3
2
Пусть теперь из комнаты ушли три человека, знающие одновременно английский и немецкий языки; число людей, знающих другие пары языков, не изменилось (так как никто в комнате не знает трех языков):
а	н	Ф	ан	нф	фа	анф
2	2	6	0	2	1	0
После того как уйдут двое, знающие немецкий и французский, и один, знающий французский и английский, мы получим задачу:
ан нф фа анф
1	0	3
ООО О
Эта задача решается без труда: в комнате остался один человек, знающий только английский язык, и трое, знающие только французский язык; всего четыре человека. Кроме того, вышло семь человек, значит, сначала в комнате было 11 человек. Из них только английский знает один.
92.	Просуммируем число читателей, прочитавших данные k книг, по всем наборам из k книг. Полученную сумму обозначим через Sk. Докажем, что
S=St—52+^з—•$<+ ... +(—
и есть число читателей в библиотеке.
Возьмем читателя, прочитавшего ровно k книг, и посмотрим, какой вклад он вносит в каждое слагаемое суммы S. Без ограничения общности можно считать, что наш читатель прочитал первые k книг. В слагаемое наш читатель внесет вклад k( = C'k), так как он входит в число читателей, прочитавших первую книгу, в число читателей, прочитавших вторую, третью, и т. д. k-ю книгу. В S2 наш читатель внесет вклад С2к, так как он входит в число читателей, прочитавших любую пару книг из первых k. Аналогично, в Sm наш читатель внесет вклад Ck‘ при т k, и 0 при m>k. Значит, вклад нашего читателя в сумму S равен:
С1-С,2 + С?+ ...+ Cl
Но мы знаем, что—Q!+Q—^1+^1+— ...+(—1)6~’С*=0 и С° = 1. Значит, вклад нашего читателя в сумму S равен 1-Рассуждение применимо к любому читателю. Следовательно, S равно числу читателей библиотеки, что и требовалось доказать.
Замечание. Нетрудно видеть, что задача 91 является частным случаем задачи 92. Однако метод решения задачи 91 можно использовать и для решения задачи 92.
93.	Рассмотрим пять множеств телефонных номеров:
(например, множество В состоит из номеров, у которых на втором-третьем месте стоит 12, а на остальных местах что угодно). В каждом из этих множеств по 104 номеров. Множества А и В не имеют ни одного общего номера. Множества А и С имеют 102 общих номеров — это номера вида
12 12
Легко подсчитать, что существует 6- 102 номеров, которые входят одновременно в какие-нибудь два множества. И, наконец, только один номер (12 12 12) входит в три множества. Теперь либо методом решения задачи 91, либо методом решения задачи 92 можно легко показать, что искомое число равно 5- 104— —6- 102+1=49 401.
Глава 3
95.	Если за сутки не было ни одного дождя, оба школьника поставят оценки + . Если все время шел дождь, то оба
поставят —, Если утром шел дождь, а днем и вечером было сухо, то первый поставит —, а второй + ,
Случай Ч— невозможен, потому что первый школьник ставит + только в том случае, если дождя не было ни разу. Но тогда и второй школьник должен поставить +.
96.	Если первый школьник поставил +, это значит, что дождя не было ни разу. Тогда остальные два тоже поставят + . Общая оценка будет + + +. Если первый поставил —, а третий +, это значит, что дождь шел ровно один раз из трех. В этом случае второй школьник должен поставить +. Общая оценка будет —F+- Если же первый и третий поставят —, это значит, что дождь шел или 2 раза из трех, или все 3 раза. В первом случае второй школьник поставит + , во втором случае —. Общая оценка будет —I— или--------------.
Так как мы разобрали все возможные случаи, других оценок встретиться не может.
Другой способ. Дождь может идти О, 1,2 или 3 раза. Ответ вытекает из таблицы:
97.	а) Пусть А — самый низкий среди высоких, Б — самый высокий из низких. Сравним их с В — человеком, который стоит в том же ряду, что и А, и в той же колонне, что и Б. Поскольку А — самый высокий в своем ряду, то он выше
В, а так как Б — самый низкий в своей колонне, то он ниже В. Значит, А выше Б.
б) Рассмотрим два расположения (рис. 39).
Если на заштрихованные места поста вить людей более высокого роста по сравнению с остальными, то в первом случае самый низкий из высоких окажется выше, а во втором случае — ниже, чем самый высокий из низких (проверьте!).
Подумайте, почему в первом из этих случаев нельзя применить те же рассуждения, что и в решении задачи а).
99.	Предположим, что каждый школьник решил только одну задачу, но так, что каждая задача была кем-нибудь решена. В этом случае контрольная будет трудной в смысле а) и легкой в смысле б).
100.	Примеры 3 + 4 = 7, 2 + 7 = 9 показывают, что теоремы 2, 3, 4, 5 неверны. Теорема 1 очевидна. Теорема 6 легко доказывается от противного.
101.	Теорему 8 легко доказать от противного (если верна теорема 1). В самом деле, пусть теорема 8 неверна. Это значит, что из В не следует А, т. е. возможен случай, когда выполняется В и
не выполняется А. Но это означает, что не выполняется В и выполняется А. По теореме 1 это невозможно.
Для теорем 4 и 5 можно подобрать и такие примеры утверждений А и В, для которых эти теоремы верны, и такие, для которых они неверны. Наиболее наглядные примеры можно построить так. Пусть А и В—два множества точек на плоскости. В качестве А возьмем утверждение «точка М принадлежит множеству А», а в качестве В — утверждение «точка Л4 принадлежит множеству В». Тогда теорема 1 означает, что множество А целиком содержится в множестве В; теорема 2, что дополнение к А содержится в В*); теорема 3, что А содержится в дополнении к В, и т. д. Сформулируйте самостоятельно остальные теоремы и нарисуйте примеры множеств А и В, для которых эти теоремы верны, и примеры, для которых они неверны.
Нужные нам примеры получаются из рассмотрения рис. 40.
Разберите эти случаи самостоятельно и убедитесь, что теоремы 4 и 5 могут быть и верными, и неверными.
*) Дополнением к некоторому множеству А иа плоскости называется совокупность всех точек плоскости, ие входящих в А. Например, дополнением к верхней полуплоскости (включая ось Ох) будет нижняя полуплоскость (не включая точек оси Ох).
Разумеется, можно было бы привести и другие примеры (например, теоремы 1 и 6 из задачи 100 или знакомые Вам теоремы из геометрии и алгебры). Докажем теперь, что теоремы 2, 3, 6 и 7 неверны.
Если бы теорема 2 была верна, то мы имели бы следующую схему:
д теорема 1 g теорема 2 д
(если А верно, то В верно по теореме 1, если А неверно, то В верно по теореме 2). Таким образом, утверждение В должно быть верным всегда, а мы условились такие утверждения не рассматривать.
Если теорема 3 верна, то
В теорема 3 д теорема 1 g
Значит, если в каком-нибудь случае утверждение А верно, то верны два противоречащих друг другу утверждения В и В, что невозможно. Итак, А всегда неверно. Но такие утверждения мы не рассматриваем.
Если верна теорема 6, то
В теорема 6 д теорема 1 g
Мы видим, что из того, что утверждение В неверно, следует, что оно верно. Это может быть только в том случае, когда В верно всегда.
Если верна теорема 7, то д теорема 1 g теорема 7 д
Другими словами, из того, что А верно, следует, что А неверно. Значит, А всегда неверно.
102.	а) Пусть сначала xi>0. Тогда | х | —х и мы получаем уравнение 3х=3, откуда х=1. Пусть теперь х<0; тогда | х | =—х и мы получаем уравнение —х=3, откуда х=—3. Ответ: Xi = l, %2 ’ —3.
б) Для х^>0 получаем уравнение х2+3х—4 = 0, откуда Xi = l, х2 = —4. Условию х^>0 удовлетворяет только первый корень.
Для х<^0 получаем уравнение х2— •—Зх—4=0, откуда х} ——1, х2 = 4. Условию х<0 удовлетворяет только первый корень. Ответ: Х] = 1, х2 =—1-
в) Пусть х<—Тогда |2х+1 | =
= — (2х+1),|2х—1| = — (2х—1). Мы получаем уравнение —(2x4-1)— (2х—1) =2, откуда х=----1—.
Пусть —Тогда |2х+1|=>
= 2х+1, |2х—1| =—(2х—1). Мы получаем уравнение (2x4-1) — (2х—1)=2, которое выполняется тождественно. Зна-
Г 1	11
чит, все числа отрезка ——, — являют-L 2 2J
ся решениями нашего уравнения.
Пусть теперь х>у. Тогда |2х+1| = =2х+1 и |2х—1|=2х—1. Мы получаем уравнение (2x4-1) + (2х—1)=2, откуда х= —. Ответ: решениями являются все
Г 1	11
числа отрезка-----. — •
2	2 I
103. а) Пусть сначала числа х и у положительны. Тогда |х|=х, |x+y I =х-Ьу. Исследуемое неравенство превращается в равенство.
Если х положительно, а у отрицательно, то нужно отдельно рассмотреть случай х+у>0 и случай х+//<0. В первом случае |х|=х, |у[ = —у, [х+у 1=х+у. Неравенство принимает вид х+у-^х—у. Оно верно, так как у отрицательно.
Во втором случае |х|=х, |у|=—у, ,х+у| = — (х+у). Неравенство принимает вид
—X—у	у.
Оно верно, так как х положительно.
Остальные случаи получаются из разобранных, если изменить знак у обоих чисел х и у. Так как при этом |х|, |у| и /х-[--у| не изменятся, неравенство останется верным.
б) Можно было бы, как в решении задачи 9 а), рассмотреть отдельно все возможные случаи расположения чисел х, у и х—у на числовой оси, но мы воспользуемся тем, что неравенство I х + у|< |х| + у| уже доказано. Обозначим х—у через z. Тогда x=y+z. Так как |у + z|<|у| + |z|, то |х|<|у| + |х—у|, что и требовалось доказать.
в) Здесь опять возможно решение с помощью разбора различных случаев, но проще вывести это неравенство из уже доказанных. Для этого заметим, что если |х|^-|у|, то наше неравенство совпадает с неравенством задачи 1036). Если же |х| < |у[, то наше неравенство принимает вид |х — у| |у| — /х| или |у — х\~^ |у| — |х| А это снова неравенство задачи 1036), в котором переставлены х и у.
Замечание. Можно предложить более наглядное решение, если воспользоваться тем, что величина |х| равна расстоянию между точками х и 0 на числовой оси, а величина I х—у | — расстоянию между точками х и у. См. по этому поводу первый выпуск нашей «Библиотечки», который называется «Метод координат».
104. а) Неравенство ~\Г 1000<1,001 можно переписать так: 1000< (1 +0,001) ". Раскроем правую часть по формуле
бинома. Мы получим
(1 + 0,001)"=
_ 1 + п I п<п~ + .. +	1	.
1000	2-10002	*~Г 1000"
Отсюда видно, что при «>1 величина (1+0,001)" во всяком случае больше, чем	• Поэтому при достаточно
большом п, например при «.= 1000000, будет: (1+0,0001) "> 1000. Значит, при п= 1000000 выполняется и исходное неравенство У 1000 < 1,001.
б)	Так же, как в решении задачи 104а), перепишем неравенство в виде «<(1+0,001)" и раскроем правую часть по формуле бинома. Из этой формулы следует, что при п>2 справедливо неравенство (1+0,001)" >1 + ——Ь п(п~~ 1000	2-10002
Но при достаточно большом « это выражение больше, чем п. В самом деле, если п—1>2-10002, то уже последнее слагаемое будет больше, чем п. Следовательно, при «=2-10002+2 выполняется неравенство (1,001) ">«, а. значит, и
п
исходное неравенство}/^ <1,001.
в)	Воспользуемся тождеством У п+1— — У п .------1—-=. Из него видно, что
V п+1+у 11
величина Уп+1—Уп во всяком случае не больше, чем  Поэтому при «>25 выполняется неравенство
/«+1 — Уп <
1 1
2Vn 10
г)	Такого числа п не существует. В самом деле, если ]/«2 + «— «<0,1, то Г«2+й<« + 0,1 и «2+«< («+0,1)2= = П2_|_Д 4-0,01. Последнее неравенство, 5
очевидно, не выполняется ни при каком натуральном п, так как «>—+0,01.
5
105.	Посмотрим, как ведет себя вы-
I #3_2Л I 1 I
ражение ———при больших (по
абсолютной величине) значениях k. Ясно, что в числителе главную -роль играет член Л3, а в знаменателе k\ Поэтому можно ожидать, что при больших значениях k наше выражение приблизи-
|£3 I	1
—|	. Исследуем те-
перь, насколько точное значение нашего выражения отличается от найденного приближенного. Для этого сделаем преобразование:
I fe3 — 2Л + 1 I
I — 3 I
I 2 1 1 | 1 ~~ fe2 + А3
|.| I 3 k*
Пусть | k |	2; тогда
Поэтому при | k | >- 2 справедливо неравенство
I _ 2	_1_|
1 11 fea + fe3 |	_1_
1*1 li-2-l < 2
I & I
— = 2.
I
2
Итак, при |^О-2 наше выражение не превосходит 2. Остается посмотреть, какие значения оно принимает при k = — — 1, О, 1. Эти значения равны соответственно 1, */з. 0.
Ответ: искомое число С существует. Например, можно положить
С=2.
Замечание. Таким же способом можно получить более точные оценки для нашего выражения и убедиться, что наибольшее значение, равное 1, оно принимает при k=—1. Сделайте это самостоятельно.
106.	Наше выражение является произведением двух чисел: k и sin k. Первое из них может быть выбрано как угодно большим. Если при этом второе число не будет слишком маленьким, то и все произведение будет большим числом. Потребуем, например, чтобы sin k было больше 1/2. Множество точек х, для которых sin х> 1/2, состоит из бесконечного числа интервалов вида
2ли + — <х<2лп + —, 6	6
где п — любое целое число (рис. 41). Длина каждого интервала равна 2л/3. Так как эта длина больше I, внутри каждого из этих интервалов есть хотя бы одно целое число. Отсюда следует, что для любого числа С существует
бесконечно много чисел, для которых k-sin k>C. В самом деле, для всех чисел k, лежащих в указанных выше интервалах, выполняется неравенство
sinfe>y. Поэтому если натуральное число k больше, чем 2С, и лежит внутри одного из указанных интервалов, то ksink>C. Таких чисел, очевидно, бесконечно много.
107.	а) Пусть отрезок [а, 6] — ловушка. Это значит, что вне этого отрезка может быть только конечное число членов последовательности. Если бы этот отрезок не был кормушкой, то внутри его тоже было бы только конечное число членов последовательности. Но всего в последовательности бесконечное множество членов. Противоречие показывает, что отрезок [а, Ь} должен быть кормушкой.
б) Последовательность б) и отрезок Б из задачи 108. Первый, третий, пятый и т. д. члены последовательности лежат внутри отрезка, а второй, четвертый, шестой и т. д. — вне отрезка. Поэтому отрезок является кормушкой и не является ловушкой.
109. а) Последовательность
б) Такой последовательности не существует. В самом деле, предположим, что для некоторой последовательности отрезок [0, 1] — ловушка. Тогда вне этого отрезка может быть только конечное число членов последовательности. Значит, и внутрь отрезка [2, 3] попадет только конечное число членов. Поэтому отрезок [2, 3] не будет кормушкой и тем более (см. задачу 107а)) не будет ловушкой для последовательности.
110. а) При любом расположении отрезка длины 1 он не пересекается хотя бы с одним из отрезков [0, 1] и [9, 10]. Пусть, например, наш отрезок не имеет общих точек с отрезком [0, 1]. Если бы наш отрезок был ловушкой, то вне него и, в частности, внутри отрезка [0, 1] было бы только конечное число членов последовательности. А это противоречит тому, что отрезок [0, 1] по условию является кормушкой.
б) Рассмотрим две последовательности:
1) 1; 9; —; 9—; —; 9—;	9—•
'	2	2	3	3 п п ’
2) 0; 10;— ; 9—; —; 9—;	9—• .
2	2	3	3 л п
Для первой последовательности несу-ществует ловушки длины 9. (Проверьте,
что отрезки
и Гэ —, 10 3
являются
кормушками для этой последовательности. Отсюда, как и в решении задачи 110а), доказывается, что ловушки длины 9 не существует.)
Для второй последовательности отрезок (—, 9—] является ловушкой, так
как все члены последовательности, начиная с третьего, принадлежат этому отрезку.
111. а) Последовательность!; 2; 3;
п\ ... не имеет ни одной кормушки, так как в отрезке длины I содержится не более /+1 членов последовательности.
б) Мы сейчас построим последовательность, среди членов которой содержатся все рациональные числа. Поскольку в любом отрезке найдется бесконечное множество рациональных чисел, то для такой последовательности любой отрезок будет кормушкой. Чтобы построить нужную нам последовательность, будем двигаться по линиям клетчатой бумаги так, как показано на рис. 42.
Каждый раз, когда мы проходим через вершину клетки, мы записываем один член последовательности. Если клетка имеет координаты х, у (как видно из чертежа, хи у — целые числа, причем t/>0), то соответствующий член последовательности равен —. Мы полу
чаем, таким образом, последовательность
О	1	1	0 —1 —1 —2 —2 —2
1 ’ 1 ’ 2 ’ 2 * 2 ’ 1 ’ 1 ’ 2 ’ 3
Покажем, что в нашей последовательности содержатся все рациональные числа. В самом деле, каждое рациональное число по определению может быть за-р
писано в виде —, где р и q — целые <7
числа и <?>0. При движении по плоскости описанным выше образом мы па некотором шагу придем в точку с координатами р, q. Соответствующий член по-р следовательности будет как раз —
Q ‘
На самом деле каждое рациональное число встретится в нашей последовательности даже бесконечное число раз, поскольку рациональное число бесконечным числом способов можно пред-р	2	4	6
ставить в виде -(например, — ——— — ~~~—
q	3	6	9
8
= ~= •••)• Однако указать явно для каждого рационального числа номер соответствующего члена последовательности не так просто. Попро-< 1 5 буйте, например, найти номер чисел 1—,—10.
А чему равен 100-й член этой последовательности?
ИЗ. а) Рассмотрим отрезок с центром в точке а. Длину этого отрезка обозначим через 2е. По определению предела найдется такое число k, что при всех n>k справедливо неравенство |х„—а\ < е. Это неравенство означает, что точка хп лежит на пашем отрезке. Итак, вне нашего отрезка расположено не более k членов последовательности. Значит, наш отрезок — ловушка.
б) Пусть задано любое положительное число е. Рассмотрим отрезок с цент
9 С. И. Гельфанд и др.
129
ром в точке а, имеющим длину меньше 2е. По условию, этот отрезок является ловушкой. Поэтому вне его лежит только конечное число членов последовательности. Пусть k — наибольший из номеров этих членов. (Если вне отрезка совсем нет членов последовательности, то положим &=0.) Тогда для любого n>k член хп лежит на нашем отрезке, т. е. выполняется неравенство |х„—«|<е. Мы доказали, таким образом, что а —< предел последовательности
114. а) Пусть задан отрезок с центром в точке а. Обозначим длину отрезка через 2е. По определению предела существует такое число k, что при n>k выполняется неравенство \хп—а|<в. Это значит, что все члены последовательности с номерами, большими k, лежат на заданном отрезке.
Пусть теперь задан отрезок, не содержащий точки а. Обозначим через е расстояние от точки а до ближайшего конца отрезка. По определению предела существует такое число k, что при n>k выполняется неравенство [х„ — <?|<е. Это значит, что при n>k член хп лежит ближе к точке а, чем ближайший конец заданного отрезка. Поэтому все члены с номерами, большими k, лежат вне этого отрезка. Значит, на заданном отрезке не может быть бесконечного множества членов последовательности.
б) Для последовательности I; 3;
у; ...; п(~1)П *; ... любой отрезок с центром в точке 0 является кормушкой. В самом деле, подпоследовательность, составленная из членов с четными но-11] 1
мерами —;	—; ...; ——: .... очевид
но, стремится к нулю. Поэтому в любом отрезке с центром в точке 0 имеется бесконечное множество членов этой подпоследовательности (см. решейие задачи 114а)). Значит, этот отрезок является кормушкой для исходной последовательности. Покажем теперь, что никакой отрезок, не содержащий точки 0, не является кормушкой. В самом деле, для подпоследовательности, составленной из членов с четными номерами, этот отрезок — не кормушка (см. решение задачи 114а)); для подпоследовательности, составленной из членов с нечетными номерами 1; 3; 5; 7; ... вообще никакой отрезок не может быть кормушкой (докажите это самостоятельно). Поэтому на любом отрезке, не содержащем точки О, будет только конечное число членов с четными номерами и конечное число членов с нечетными номерами. Значит, на этом отрезке всего конечное число членов последовательности и, следовательно, отрезок — не кормушка.
Итак, последовательность хп=л(-1)” 1 и число 0 удовлетворяют условиям задачи 1146). Но число 0 не является пределом последовательности. В самом деле, в противном случае для всех членов последовательности, начиная с некоторого номера, выполнялось бы условие |х„| <1. Однако это неравенство не выполняется для всех членов с нечетными номерами.
Замечание. Последовательность
X —л*-*)"-1 —п
можно представлять себе как объединение двух более простых последовательностей: 1; 3; 5; 7;...;
Ill	1
2л—1;.., и —; —; —; ...; —; ... ’246	2л
Этот способ построения последовательностей
часто бывает полезен. Например, чтобы построить пример последовательности, для которой каждый из двух заданных отрезков являлся бы кормушкой (см. задачу 1096)), можно объединить две последовательности, для одной из которых первый отрезок является кормушкой, а для другой — второй отрезок является кормушкой.
115. В решении задачи 114а) мы доказали, что если хп->а при п->оо, то никакой отрезок, не содержащий точки а, не является кормушкой. Отсюда требуемое утверждение легко выводится методом от противного. Сделайте это самостоятельно.
р
116. Для того чтобы доказать, что последовательность {х„} имеет пределом число а, нужно показать, что для каждого положительного числа е можно подобрать такое число k, что при n>k будет справедливо неравенство \хп — а| < <е. Часто бывает возможно указать явную формулу, выражающую k через е.
„ч „	(—lim х =0. Так как
а) = ’ «->«
]х„|= — , то в качестве k можно взять п
1 „ . 1
—. В самом деле, при п>— выполняет-е	е
II 1
ся неравенство |хп| = — <е. п
Замечание. Число k определяется по заданному е неоднозначно. В разобранном примере в качестве k можно 2	1
было взять k= — или------1-1 (и вообще
Е	Е
любое число, большее —). Часто бывает
Е
удобно брать не самое «экономное» значение для k (которое может очень сложно выражаться через е), а более простое выражение. Например, чтобы доказать,
что lim------------=0, можно восполь-
п-»оо ns+0,6n+3,2
^.1.1
зоваться тем, что х„<—< — и в ка-" п3 п
честве k взять —. Это гораздо удобнее, Е
чем самое экономное значение
k-Y 1.6 + 1/2.562-^+^ +
+ |/ 1,6-)/2,552-^+51,,
которое получается из решения кубического уравнения
га3 + 0,6га + 3,2 = — .
Бывают и такие случаи, когда для самого экономного значения k вообще нельзя указать явной формулы, а значение «с запасом» легко может быть найдено.
б) *п
3——1 = 1 —• з" ” з" ’
lim хп = I. п->со
Так как 1х„—11= —-, то в качестве k
МОЖНО ВЗЯТЬ logs
в)	Пользуясь формулой суммы геометрической прогрессии, находим хп = = 1+-^- + ... + -^-=2—-^-.Отсюда видно, что lim х„ = 2и в качестве k можно взять Я-*-0о
10g2 (— 1
г)	Предела не существует, так как для любого числа а и любого е неравенство \хп— а| < е выполняется только для конечного числа номеров п.
д)	lim хл=1; так как |хл—1| в этом
П->оа
случае тождественно равно нулю, нера-венство ]хп—1 |<е выполняется при любом положительном в для всех номеров п.
е)	Рассмотрим отдельно случай четного и нечетного п. При четном п=2т
1 п
мы имеем хп— — . Поэтому при /п>
_ 1	2,
> — (т. е. при л>—) выполняется не-£	£
равенство |хл|<е. При нечетном п член хп равен нулю, поэтому неравенство |хл| < <0 выполняется для всех нечетных номеров. Итак, lim хп — 0 и в качестве k
П-*СО
2 можно взять число —.
Е
ж)	По формуле суммы геометрической прогрессии имеем 0, 22 ... 2 =
п
= — + — + — (1 —-
10	102	10"	9 \	10" /'
2
Отсюда limx„ =—и в качестве k мож-П-..0О	9
но взять 1g (или просто 1g ) — см. замечание к решению примера 116а)).
з)	Предела не существует. В самом деле, если /z=180/n, то х„—0, а если /2=90+360//!, то х„=1. Если бы последовательность имела предел а, то, начиная с некоторого номера п0, выполнялось бы неравенство |х„—а|<-^-. Отсюда, в свою очередь, следовало бы, что при
ni>n0 и П2>п0 выполнялось бы неравенство |х„,—х„2| < |хя, —а | + | а — <
4	4	2
Но в нашей последовательности есть члены со сколь угодно большими номерами, отстоящие друг от друга больше, 1 чем на —.
2
и)	Так как |cosn°|<C 1, то	.
п
Отсюда видно, что lim хя=0 и в каче-
, 1
стве k можно взять —.
е
к)	Предела не существует. Если бы число а было пределом, то, начиная с некоторого номера, выполнялось бы неравенство \хп—а| < -р Тогда |хя—хя+1| <
<1*« —«I +<--+ "Г = ’• Но разность между любыми соседними членами нашей последовательности больше 1.
117.	Предположим, что два разных числа а и b являются пределами одной и той же последовательности {хя}. Обозначим расстояние между этими точками через 2е. Если а — предел последовательности {%„}, то найдется такое число ku что при n>ki, будет выполняться неравенство \хп—а| < е. Аналогично, если b — предел последовательности {х„}, то найдется такое число k2, что при n>k2 будет |хп—Ь\ < е. Следовательно, если номер п больше и kt и k2, то выполняются оба неравенства |хп—< е и [хп—Ь\ < £. А это невозможно, так как \а—6| = 2е.
118.	а) Покажем, что любой отрезок с центром в точке а является кормушкой. Пусть длина отрезка равна 2е. Нам нужно показать, что бесконечно много членов последовательности попадают на этот отрезок, т. е. удовлетворяют неравенству [х„— а| е. Предположим, что это не так. Тогда на нашем отрезке лежит только конечное число членов последовательности.
Пусть k — наибольший из номеров этих членов. (Если на нашем отрезке совсем нет членов последовательности, то положим k=0.) Тогда все члены с номерами, большими k, лежат вне отрезка. Но это противоречит определению предельной точки: для любого k найдется номер n>k. такой, что |х„— а| < е, и, значит, хп лежит на нашем отрезке.
б) Предположим противное, т. е что а не является предельной точкой последовательности. Это значит, что для некоторого е и некоторого k не найдется такого номера n>k, для которого |хл—а| < <е Другими словами, на некотором отрезке с центром в точке а лежит только конечное число (не более k) членов последовательности. Мы пришли к противоречию с данным нам условием, по которому любой отрезок с центром в точке а является кормушкой для {хп} и, значит, содержит бесконечно много членов последовательности.
119.	Это следует из решений задач 113а), 107а) и 1186). Попробуйте изложить это решение, не используя понятий ловушки и кормушки.
120.	а) Последовательность хп—-
имеет пределом число 1. Значит (см. задачу 119), число 1—предельная точка
для этой последовательности. Других предельных точек последовательность не имеем (см. задачи 114а) и 118а)).
б)	Точки + 1 и—1, очевидно, являются предельными для последовательности хп=(—1)" . Для любой другой точки а можно построить такой отрезок с центром в точке а, в котором вообще нет ни одного члена последовательности. Поэтому других предельных точек последовательность не имеет.
в)	Так как функция sin хс имеет период 360°, то каждое из чисел 0, ±sin 1°; ±sin2°; ...; ± sin 89°; ±1 встречается в последовательности бесконечное число раз. Поэтому все эти числа являются предельными точками. Если число а не совпадает ни с одним из перечисленных 181 чисел, то можно построить отрезок с центром в точке а, не содержащий ни одного члена последовательности. (Для этого достаточно взять длину отрезка меньше, чем расстояние от точки а до ближайшего из указанных выше чисел.) Поэтому других предельных точек последовательность не имеет.
г)	Эту последовательность удобно представлять себе как объединение двух последовательностей уп =	1 и г„=2и.
Первая последовательность имеет единственную предельную точку 0, вторая вообще не имеет предельных точек. (Докажите эти утверждения самостоятельно.) Покажем теперь, что точка а является предельной для исходной последовательности тогда и только тогда, когда она является предельной хотя бы для одной из двух последовательностей {#„} и {zj. В самом деле, если воспользоваться результатом задачи 118, то останется доказать следующее почти очевид
ное утверждение: отрезок [а, 6] является кормушкой для последовательности {%„} тогда и только тогда, когда он является кормушкой хотя бы для одной из последовательностей {yn}, {zn}.
Замечание. Точно такими же рассуждениями доказывается общая теорема: если последовательность {хп} является объединением конечного числа последовательностей {'/«}, (гл).--{6i}. то множество предельных точек для {*«} получается объединением множеств предельных точек для {f/n). {гя},..., {/п}.
е) Если число а удовлетворяет условиям 0	1, то на любом отрезке с
центром в точке а лежит бесконечно много членов нашей последовательности. В самом деле, если длина отрезка рав-на 2е, то при любом п> —среди группы
Е
1	2	и—1	~
членов —; —;	----- есть хотя бы
п	п	п
один, лежащий на нашем отрезке. Если же п<0 или а>1, то можно построить отрезок с центром в точке а, который не содержит ни одного члена последовательности.
Поэтому предельными точками нашей последовательности будут все точки отрезка [0, 1] и только они.
122. а) Пусть последовательность {хп} имеет предел х0. Возьмем какой-нибудь отрезок [а, Ь] с центром в точке х'о- Так как этот отрезок является ловушкой для последовательности {%„} (см. задачу 113а)), то вне этого отрезка расположено только конечное число членов последовательности. Пусть xk— наибольший (по абсолютной величине) из этих членов. Обозначим через С наибольшее из чисел |а|, |fr|,	. Тогда для всех
членов последовательности будет спра-
ведливо неравенство |х„| С. В самом деле, если х лежит на отрезке [а, 6], то |хп| не превосходит наибольшего из чисел |а|, |&|. Если же хп не лежит на отрезке [а, Ь], то |х„|	(так как
xk— наибольший по абсолютной величине среди членов последовательности, не лежащих на [а, &]). Значит, и подавно х„| < С.
б) Последовательность, приведенная в задаче 1086), ограничена, так как |х„| -С 2. Докажем, что она не имеет предела. В самом деле, легко проверить, что отрезки [0, —] и[1, 1—] являются
4	4
кормушками для последовательности Расстояние между этими отрезками 3
равно —.
Отсюда вытекает (см. решение задачи 110а)), что для этой последовательности не существует ловушки длины з
< —. Но если бы последовательность 4
{*„} имела предел а, то любой отрезок с центром в точке а был бы ловушкой и, значит, существовали бы ловушки как угодно малой длины. Полученное противоречие показывает, что последовательность {хп| не имеет предела.
Разумеется, можно так изложить это решение, чтобы в нем не фигурировали термины «ловушка» и «кормушка» (ср., решение задач 116з), 116к)). Сделайте это самостоятельно.
123. а) Пусть N — любое положительное число. Для всех n~>N справедливо неравенство |x„|>2V. Поэтому последовательность {%„} стремится к бесконечности.
б)	То же решение, что и в случае а).
в)	Последовательность не ограничена, так как для любого положительного числа С найдется такой номер п, что | хп | > С (достаточно в качестве п взять любое четное число, большее С). Но эта последовательность не стремится к бесконечности, так как неравенство |-*„| > 1 не выполняется для всех нечетных членов последовательности.
г)	Пусть М — любое положительное число. Для всех п>№ выполняется неравенство х„>М. Следовательно, х„->оо.
д)	Покажем, что последовательность {%„} ограничена. Более точно, мы покажем, что |хп| 5. Поскольку хп >0, то |хл| = хп, и мы должны доказать, что хп<:5. А это вытекает из следующих соотношений:
5—х„ = 5
100 л
100 + п-
-------(100+п2 — 20п) = 100+л2 v
5(10— л)2
100+ Л2
0.
125. Мы разберем подробно только два примера.
I) • Покажем, что условию 1 удовлетворяет любая последовательность {хп}. В самом деле, мы должны показать, что найдется такое положительное число е, такое число k и такой номер n>k, что |х„— а|<е. Возьмем в качестве е число |хх — а| + 1 и положим &=0, п = 1. Тогда требуемое условие будет выполнено.
6) Покажем, что условие 6 означает, что последовательность {xj не имеет числа а пределом. В самом деле, утверж
дение «й является пределом последовательности {хя} » означает, что для любого е>0 найдется такое k, что для всех n>k верно неравенство \хп — а| < е. Отрицание этого утверждения выглядит так: «не для любого е>0 найдется такое k, что для всех n>k верно неравенство |х„—а| < е».
Эту фразу можно пересказать следующим образом: «для некоторого е>0 не найдется такого k, что для всех n>k верно неравенство \хп— а\ < е». А это можно сформулировать так: «найдется такое е>0, что для любого k не для всех n>k верно неравенство |х„ — а | < е». Наконец, эту фразу можно пересказать так: «найдется такое е>0, что для любого k найдется n>k, для которого |х„—й|>е».
Мы получили как раз условие 6 Обратите внимание на то, что это условие можно получить из определения предела по следующему правилу: 1) вместо слов «найдется такое, ... что» поставить «для любого»; 2) вместо слов «для любого» поставить «найдется такое,... что»; 3) неравенство |хп—а| <е заменить на противоположное неравенство |л'„—а| е. Это правило применимо и ко всем остальным условиям. Проверьте, что оно дает для каждого условия формулировку отрицания этого условия.
126.	Если набор начинается знаком + , то все члены последовательности равны а. Поэтому все остальные знаки набора однозначно определяются: последовательность имеет число а пределом и предельной точкой, ограничена и не стремится к бесконечности.
Рассмотрим теперь наборы, которые начинаются знаками ----Ь; это значит,
что последовательность стремится к а.
Тогда все остальные знаки набора определены: последовательность имеет а предельной точкой (задача 119), ограничена (задача 122а)) и не стремится к бесконечности.
Разберем еще наборы, у которых последний знак +. В этом случае последовательность стремится к бесконечности и это определяет все остальные знаки набора: последовательность не равна тождественно а, не стремится к а, не имеет а предельной точкой и не ограничена.
Остальные наборы имеют первым, вторым и пятым знаком —. Оказывается, что в этом случае на третьем и четвертом местах могут стоять любые знаки. Соответствующие примеры приведены в разделе «Ответы и указания».
127.	В разделе «Ответы и указания» приведены примеры последовательностей, имеющих предел и имеющих либо наибольший, либо наименьший член, либо и тот и другой. Остается доказать, что не существует последовательности, имеющей предел, но не имеющий ни наибольшего, ни наименьшего члена.
Пусть последовательность {х„} не имеет наибольшего члена. Покажем, что тогда можно выделить из последовательности {хп} возрастающую подпоследовательность. В самом деле, рассмотрим первый член последовательности Хь Так как он не наибольший, существует некоторый член хп, >хь Этот член хв. не может быть больше всех следующих за ним членов последовательности (так как в противном случае наибольший из первых rii членов последовательности был бы наибольшим из всех членов). Поэтому существует такой номер П2>иь что хПг>хП1. Член хп, опять не может
быть больше всех следующих за ними членов и т. д. Мы получили бесконечную возрастающую подпоследовательность
*1
Аналогично, если последовательность {х„) не имеет наименьшего члена, то существует бесконечная убывающая подпоследовательность
Х1
хт.
xmt
Обозначим' через е разность между хя и хт • Тогда при всех &>1 будет
выполняться неравенство xnk—> >xOj—хт^ = е. Отсюда вытекает (ср. решение задач 116з) или 1236)), что последовательность {хп} не имеет предела.
128.	Если последовательность {хп} или какая-нибудь ее подпоследовательность не имеют наибольшего члепа, то, как показано в решении задачи 127, можно выделить из бесконечную возрастающую подпоследовательность.. Рассмотрим теперь тот случай, когда в любой подпоследовательности есть наибольший член. Пусть хп — наибольший из всех членов последовательности, хп — наибольший из членов, следующих за х„, х„ — наибольший из членов, '*1	"3
следующих за хп* , и т. д. Очевидно, справедливы неравенства


Xnk
Итак, и в этом случае из последовательности {хп} можно выделить монотонную подпоследовательность.
129.	Рассмотрим последовательность 1,4, 1,41; 1,414; 1,4142; ... В этой последовательности член хп является приближенным (с недостатком) значением чис-
ла I/ 2 с точностью до -—.
10"
Из самого определения последовательности {х„} вытекает, что lim хп=]Л2 «—►о©
(при n>lg ( —выполняется неравенст-во |хл—рЛ2 |<е). Так как число]/2 иррационально и так как последовательность {хп} может иметь только один предел, то никакое рациональное число не является пределом последовательности.
Замечание. В этом доказательстве мы использовали тот факт, что существует вещественное число, квадрат которого равен 2 и которое может быть записано бесконечной десятичной дробью. Можно так видоизменить наши рассуждения, чтобы в них фигурировали только рациональные числа. Для этого надо определить хп как наибольшее из чисел, которые можно записать конечной десятичной дробью с п знаками после запятой и квадраты которых меньше 2. После этого нужно показать, что если хп стремится к какому-нибудь числу а, то а2=2.
Основная идея этого доказательства состоит в следующем. 2
Число х п обладает тем свойством, что хл
1
меньше 2, но (хл+ )2 уже больше 2. Поэтому при больших п число Хд очень близко к 2. С другой стороны, при достаточно больших номерах п числа хп и а близки, а, значит, близки и числа л'2 и а2. Отсюда можно заключить, что разность между а2 и 2 как угодно мала. Но эта разность — постоянное число, не зависящее от п. Поэтому а2=2. Остается доказать, что не существует ра-ииональиого числа а, квадрат которого равен 2. Попробуйте самостоятельно довести изложенные здесь соображения до строгого доказательства.
130.	Пусть дана ограниченная последовательность. Выберем из нее бесконечную монотонную подпоследовательность (см. решение задачи 128). Эта подпоследовательность ограничена и по аксиоме Больцано—Вейерштрасса имеет предел. Покажем, что этот предел является предельной точкой для исходной последовательности.
В самом деле, всякий отрезок с центром в этой точке является ловушкой для выбранной подпоследовательности. Поэтому на нем лежит бесконечное число членов исходной последовательности, т. е. этот отрезок — кормушка для исходной последовательности. Наше утверждение вытекает теперь из теоремы 1186).
131.	а) Последовательность х„=1 + I	1
+ — + очевидно, является возрастающей. Покажем, что она ограничена. В самом деле, так как — <—!—, па	п(п—1)
то
= 1 + (1-
1
п(п — 1)
Итак, |хп|<2 при всех п. Поэтому из аксиомы Больцано—Вейерштрасса следует, что существует lim хп.
Методами высшей математики можно уста-
7С2
новить, что этот предел равен —Элементарный 6
вывод этого факта см. в книге: А. М. Яглом, И. М. Яглом «Неэлементарные задачи в элементарном изложении».
б) Очевидно, что подпоследовательность х2п , составленная из членов с четными номерами, является возрастающей,
и ограниченной, так как
I__
4п—1
Поэтому существует limx2„. Обозна-
П-*оо
чим этот предел через а и покажем, что число а является пределом всей последовательности хп. В самом деле, пусть задано любое положительное число в. Тогда найдется такое число k, что при 2n>k будет выполняться неравенство
Е	1
\х2п—а|< —. Кроме того, при 2п+1> —
выполняется неравенство
1Х2л + J Х2л+2 |< ~ 
Поэтому, если номер п больше наиболь-шего из чисел k и —, то х —а < е.
Оказывается, что а= я/4(доказательство см , например, в цитированной выше книге А. М. Яг-лома и И. М Яглома).
132.	а) Нам нужно доказать, что для любого положительного числа в найдется такое число k, что |х„ 4- уп—а—й| < е при всех n~>k. Так как по условию
limx„=a, то найдется такое число
Л->Оо
что |х„—а\ < ~ при п > k±.
Точно так же из того, что lim yn=b, следует существование такого числа k2, что \уп—6[<-|- при n>k2. Пусть fe — наибольшее из чисел k\ и fe2- Тогда при n>k мы получим
\хп + Уп — « — * I < 1Х„ — о| + 1у„ — Ь\ < в.
б)	Доказывается так же, как и а).
в)	Воспользуемся тождеством
хпУп~ оЬ^пУп— bxn+bxn— ab =
= хп(Уп — b)+b(xn — а).
Так как последовательность хп имеет предел, то она ограничена (см. задачу 122а)), т. е. существует такое число С, что |х„| <1 С при всех п. Обозначим через М наибольшее из чисел Си Ь|. Пусть теперь нам задано любое положительное число е. Так как limx„=a, то
Л-лоО существует такое число ki, что при n>kt выполняется неравенство \хп—а\ <	.
Точно так же существует такое число k2, что при n>k2 выполняется неравенство 1у„—6|<^. Пусть k обозначает наибольшее из чисел k\, k2. Тогда при n>k мы будем иметь:
\хпУп~~ аЬ\ = \хп(Уп~ Ь) + Ь(хп~ fl)|<
<1*„| 1Уп — *1 + 1*1 \хп — «К
— +М— - е. 2М 2Л1
г)	Воспользуемся тождеством хп______хп—а । о
уп	Ь уп Ьуп
Предположим сначала, что нам уда-
лось доказать ограниченность вательности 1. Это означало \уп)
существует такое число М, что
последо-бы, что
Уп
при всех п. Тогда
хП______о I < I хп — а а(Ь — у„)
Уп b I I Уп	ьУп
М(хп — а) 4- 7И

Пусть нам ное число 8.
задано любое положитель-Мы можем найти такое
число ki, что — с| < при п > klt и
такое число k2, что
\Уп— Ь\
е|6|
2 |а| М
при
n>k2. Обозначим через k наибольшее из чисел k\ и k2. Тогда при ri>k мы
получим
------Е-1 ^д/+ м — |aLLL = уп b I 2Л1	Ь 12 |а| М
Докажем теперь, что если lim у п—Ь, П-+<х>
Ьу^О, у„¥=0, то последовательность 1
Ц/л1 ограничена. Предположим для определенности, что 6>0. Тогда существует такое число k, что при ri>k выполняется неравенство \уп—Ь\ <	. Из этого нера-
венства следует, что при n>k все члены последовательности {«/„} лежат на отрезке	Обозначим через М наи-
_	2	111
большее из чисел —; —;----.. • -—-
ъ |У11 |</21 1Уь1 (мы считаем здесь, что число k выбрано
г
целым). Очевидно, что неравенство — М выполняется для всех п. Разберите самостоятельно случай Ь<0.
134. Пользуясь результатами задачи
133, мы можем написать:
a) 11m	- =11 tn
а—>сс 3/1—5	л-*»
з—— п
б) lim--0" = 11m
G->oo П2-|-1	а-*os
10
1
1------
on - i	2n
г) lim—-----— = lim---------—
n-»» 271 + 1	‘
2"
д) Как показано в гл. 1, сумма 1*4-2*+. +пк является многочленом от п степени Л+1 со старшим членом ——п*+' (см. задачу 23). Поэтому * + 1
lim хп = П-^оо
_А_ п*+'+ а,пк+ .. -J-fl't+i
- lim 2+1________________________— =
п->с®
= lim (—-«-><» \ Al-pl
1
135. Имеем:	Vn + 1—Vn—1 =
Q
= —	-———- (см «Ответы и указа-
V n + l + n I
II	2	/
ния»). Поэтому
V n+1 + / n— 1
<;—1- Отсюда вытекает, что при v n—1
п>1 + -^- выполняется неравенство е2
<е-
136.	Воспользуемся тем, что 2'1— = (1 +1)" = 1 + п + -ffclL + ... > п +
поэтому |х„| = ^-<А.
2	2	J 1 л1 2” л
2
При п > — будет выполняться нера-
Е
венство |хп| < е.
137.	Воспользуемся тем, что
ап = [1 4- (а — 1)]" = 1 + п(а— 1)4-
+ (а — I)2 4- ... > AL".-.1) (а_1)2.
Поэтому
< П<П~1)(Д__1Г~~ (л-Ща-!)2'
Для любого положительного 8 при 9
 -——h 1 мы будем иметь |х„| < е.
138.	Пусть число п заключено между 2«—1 и 2т; тогда log2/i заключен между т—1 и т. Следовательно, выражение log., п	т
- не превосходит величины ——р . п	2т
Но мы знаем (см. задачу 136), что для любого е>0 найдется такое число k, что при m>k выполняется неравенство т . е	т .	.-1
----< —, или ——;<в. Покажем, что при 2"‘-2	2"'-1
п>2* будет выполняться неравенство
 <8. В самом деле, если п>2*. то п
п заключено между 2т~1 и 2т, где m>k. n	log»n т
Поэтому -7-<-^=Г<е-
139.	Покажем, что для каждого положительного е существует такое число k, что при n>k выполняется неравенство \]/~п —1 | <е. Так какр^ п >1, то
I/ п - 11
п
Посмотрим, при каких п неравенство п
У п—1 <е не выполняется.
Другими словами, при каких п вы-
п
полняется неравенство У п—1	е или
а
1 4-8, или п ^(14-8)". Так как
(1 4- e)n = 1 4- пг 4- ">(П- е2 + •••>
"(я—4) е2
2
то из неравенства n^(14-s)n вытекает, что п> еа, откуда п<1+-^-. По-2	е2
этому для всех п> 1 4—- неравенство
п
У п—1	е неверно, и следовательно, вер-
п
но неравенство У п—1<е.
140.	Будем пользоваться обозначениями, принятыми в указании к этой задаче. После первого шага улитка попадет в точку с координатами («4-1, Ь), после второго — в точку с координатами («4-1, 6+1) и т. д. После 2п-го шага она будет в точке (а+п, Ь+п), а после (2«+1)-го— в точке («+п+1, Ь + п).
Ь+п л	Ъ+ п
Поэтому 62„ = —. *2„+1 - о + „ + 1 •
Остается найти предел последовательности kп. Обозначим k2n через k,lt a k2n+1 — через kn- Легко проверить (см. решение задачи 134), что последовательности {&,г} и {&„} стремятся к 1 Поэтому для любого е > 0 найдется такое число Ц, что при п > Zi будет выполняться неравенство |Ai—1 <8. Точно так же найдется такое число Z2, что при п > fa будет выполняться неравенство | k-г — 1 |< <8. Обозначим через Z наибольшее из чисел 2Zi и 2Z2 + I. Тогда при п>1 будет выполняться неравенство \kn—1| < е.
141.	Сохраним обозначения, принятые в указании и решении задачи 140.
а)	В этом случае kn —k2n = ^+-2п , а+п
.	Ь+2п
kn — ^2n+i —------- • ^'ы получаем, что
а+п+1
lim A^ = lim k'n =2. Отсюда, как и выше, Л—Г2—>СГ
выводится, что lim k „ существует и ра-«-►оо
вен 2.
б)	В этом случае
_ b fe+2-H+..-+2n	_ Ь+п2+п.
" 2п	а+1+3+...+(2п—1)	а+п2 ’
д’*	_ fc-j-2-|-4+..,-|-2n	_
2п+1	а+1+3+...+(2п+1)	а+(п+1)2
Отсюда lim &,,= 1пп kn~^< и, как и вы-
Л—n->GC
ше, доказывается, что lim k;i существует л->оо
и равен 1.
в)	В этом случае kn = k2n =
9
£>+ —(4П—В
- М-2+«+...+22П-' _	3
~~ a+l+4+...+22n-2 —	I
а+ —0—1)
О
Ъ ~Ь - 6+2+8+-+22»-1 _
2n+1	а+1+44-...+22Л
b + -у (4"-1)
а + -у- (4"+1 — 1)
Отсюда видно, что lim Лл=2, 11тЛ„ = П—>СО	П->ОО
•=	—. Покажем, что последовательность 2
{£„} в этом случае не имеет предела. В самом деле, если некоторая последовательность имеет предел а, то любая ее подпоследовательность имеет тот же самый предел Докажите это самостоятельно, используя, например, задачи 113а) и б).
Но в нашем случае подпоследовательности {&2я} и {^2Я+1} имеют разные пределы.
О м. Р. Рп
Р~с *3
142.	Из подобия треугольников И0Л4„Ро и АпМпРп (рис. 43) мы получаем
МпР0 : МпРп — Р<Д> : Рп^п'
Обозначим абсциссу точки Мп через хп. Тогда полученную пропорцию можно переписать так:
Отсюда получается выражение для x„i
а(ап + 1)
2ап 4- 1
Поэтому
lim а 11m хд=—"  «-►оо
lim
Л—>oo
a2   a
2a"	Г’
Геометрически полученный ответ можно сформулировать так: касательная, проведенная к любой точке параболы, делит пополам отрезок, соединяющий вершину параболы с проекцией точки касания на ось Ох.
143.	Пусть мальчик Петя вышел из точки А\. Обозначим через В, С, D соответственно точки, в которых расположены школа, кинотеатр и каток (рис. 44).
Путь мальчика Пети изобразится ломаной AiA2A3..., в которой точка А2— середина отрезка Л1В, точка Л3— середина отрезка А2С, точка Л4 — середина отрезка A3D и т. д. Докажем, что точки Аь А4, Л7, .... Л3я+1, ... лежат на одной прямой. В самом деле, отрезок Л2Л5 является средней линией в треугольнике A tBA4, поэтому этот отрезок параллелен А,А4, а длина его вдвое меньше. Точно так же, рассматривая треугольник А2СА5, мы выводим, что отрезок ДзЛ6 параллелен Л2Л5, а длина его вдвое меньше. Наконец, из треугольника Л3£)Лб мы получаем, что отрезок А4А7 параллелен ДзЛе и имеет вдвое меньшую длину. Сравнивая полученные результаты, мы видим, что отрезки AtA4 и Л4/17 являются продолжением друг друга, причем длина Д4Д7 в 8 раз меньше длины /4р44.
Точно так же устанавливается, что отрезок Л7Лю является продолжением отрезка Л4Д7, отрезок ЛюД13— продолжением отрезка /47Л|О и т. д. Итак, точ-
₽С
Рмс.Ц
ки At, At, Ar, ..., ASn+v ... лежат на одной прямой. Мы доказали также, что расстояния между этими точками обра
зуют геометрическую прогрессию со знаменателем -р Теперь нетрудно пока-
зать, что последовательность Аг, Аг, Аг, ...; ^зл+п — имеет предел. В самом деле, примем точку At за начало координат на прямой, проходящей через точки нашей последовательности, а за единицу масштаба примем длину отрезка Л1/Ц. Тогда координата точки Л3„ + 1 будет равна
- (—V
х„= 1 +- + - +'...+ — =---——
"	8	8*	8"~1	1
~ 8
Поэтому существует limx„==l-i- (см. за.
П—^90	7
дачу 132).
Мы доказали, таким образом, что последовательность точек Аг, Аг, Аг, ...; Ал+1 ’» ••• стремится к некоторой точке М. Точно так же можно доказать, что последовательность Аг, Аг, Аг, ...; ASn+2; ... стремится к некоторой точке М, а последовательность /43; А6; Аг, ...; А3п', ...— к некоторой точке Р. Таким образом, путь мальчика Пети довольно быстро приближается к движению по сторонам треугольника MNP. Докажите самостоятельно, что положение точек М, N и Р зависит только от положения точек В, С и О и не зависит от точки Ль откуда начинается движение.
144.	Пер вый способ. Введем на прямой М1М2 систему координат, приняв точку Mi за начало координат и отрезок ЛДМг за единицу масштаба. Тогда
координата хп точки Мп связана с координатами предыдущих точек соотношением
*л —1 4~ xn—t 2
(докажите это равенство самостоятельно). Покажем, что последовательность г 1	2
{хп} стремится к — .
Для этого мы покажем по индукции, 2 что х„ = — "	3
В самом деле, положив п=1, получаем = -|-р + -------=0» при л=2,
Предположим теперь, что равенство
всех n^k, и проверим его справедливость при n—k-f-1.
Подставляя выражение для xk и хк_х
В формулу Ха+1 = .**+**-!,, мы получим
Xk+x —
2

Второй способ. Рассмотрим точку N, которая делит отрезок в отношении 2:1. Докажите, по индукции, что эта же точка N делит все отрезки М2М3,	..., Л4„Л4„+1, ... в отношении
2:1. Отсюда непосредственно вытекает, что длина отрезка M„N в 2"-1раз меньше, чем длина отрезка MiN. А это значит, что последовательность Mi; Л12; .. ; Мп; ... имеет точку N своим пределом.
145.	а) По формуле суммы геомет-с ' 1—о"+1	~
рическои прогрессии о =------. Если
|а| < 1, то
lim (1 — п”-!-1)
lim Sn =	------------- = —
n—>oo	1 — Q.	1 — a
Если |a| > 1, to	при n-^co.
Наконец, если |a| =1, то получаем или последовательность S„ = n (при а=1), или	(при а — — 1). Обе эти
последовательности не имеют предела. Итак, при |a|i> 1 ряд расходится.
б) Представим Sn в виде (а4-аг4-...4--4-afi) + (а2+ а3 + ... + ап) + ... + (а',-14-+ a")-ha". Применяя к каждому из выражений в скобках формулу суммы геометрической прогрессии, получаем
а 4- а2 + ... 4- о” — пап+'
а — а"+*
------------па"+1
1 — а
1 — а
а —	1 — па) ол+1
.. (1 - а)2
1-58
Из этой формулы уже легко выводится (см. задачу 137), что при |а| < 1
S -> —-—, а при |а| > 1 "	(1—а)2	п | I
ряд расходится.
„ 1	11
в) Гак как —; ,	=--
'	п(п+1) п п+1
‘(’-1) + (т-т)+-+
+ (—---1_\ = 1-1_. s
\ П п+1 /	п + 1
г) Так как 1	= 1 Г 1_________________1
n(n+l)(n-f-2)	2 [п (п + 1)	(п+1)(п+2).
то
\ л (п + 1)	(п+1) (п+2) Л
1 Г_1_________1 I . 5 = _1_
2 [1-2	(п+1)(п+2)]’	~ 4
д) Покажем, что
1
п+1
-----------г ... ~Т	—• п+2--------2п 2
В самом деле, в этой сумме п членов и наименьший из них равен ‘/г- Теперь
(так как каждое из выражений в скоб» ках больше */а). Отсюда вытекает, что
AA = L = <
А.в. г. 1
РисА5
S„ -> оо при п -> оо. Значит, ряд расходится.
146. Два кирпича можно положить друг на друга со сдвигом на -у- (мы

считаем длину кирпича равной 1). Равнодействующая Pi сил Fi и F2 проходит 1
на расстоянии — от края второго кир-4
пича (рис. 45). Поэтому третий кирпич можно сдвинуть относительно второго на —. Теперь нужно найти равнодейст
РисЛС
вующую сил Pt и Fs. Поскольку сила Pi вдвое больше F3, точка приложения равнодействующей делит в отношении 2: 1
отрезок между точками приложения сил Рз и Pi (рис. 46). Отсюда следует, что четвертый кирпич можно сдвинуть отно
1 третьего на —
сительно
Продолжая
так дальше, можно проверить (сделайте это самостоятельно, используя принцип математической индукции), что (д + 1)-й кирпич можно сдвинуть относительно
n-го на —.
2п
Таким образом, из п кирпичей мож-
1 > 1
НО построить «крышу» ДЛИНЫ ——
+	••• +	1 п- ТаК КаК РЯД 1 +
о	2(п—1)
, 1 I 1 I I 1 I
+ ----1-----Ь ... 4-----Ь... расходится
2	3	п
(см. задачу 145д)), то «крышу» можно сделать как угодно длинной.
147. Последовательность {х„} удовлетворяет, очевидно, соотношению хя+, = =2+—. Предположим, что последовали
тельность {*„} имеет предел а. Тогда
левая часть равенства стремится к чис-лу а а правая часть — к числу 2Н-------
(см. задачу 132). Мы получаем, таким образом, равенство а = 2 + —, откуда а
а = 1±К2. Поскольку все хп больше 2, число 1—V 2 не может быть пределом последовательности
Итак, мы доказали, что если {х„} имеет предел, то этот предел равен 1 + V2.
Покажем теперь, что искомый предел действительно существует. Обозначим через уп разность между х„ и 1 + 1^2. Мы должны доказать, что lim у „=0. Подставляя в равенство П->ОО
xn+i = 2 + — выражение хп через уп, по-лучаем
1 + к2 + г/п+1 = 2 4-
1
14- V 2 -\-Уп
откуда
Уп+l —
= 2(1+ K~2+yn)+l—(1 + У~2)(1+У~2 4- t/n)_ l + V^+f/n
__ (1-Г~) >м
1 + 1<т+.1/п
Из этой формулы мы получаем следующую оценку: | уп+11 < -у 1у„ | . В самом деле, |1—рл2’|<-1-,а 14-1/2-; ч/л>1
(это следует из того, что
lf/nl<-p что
легко устанавливается по индукции).
11 С. И. Гельфанд и др
16!
Поэтому
1^.1
|1 +Г2 + </„|
1 । ।
Отсюда непосредственно вытекает, что 1&п1<	и> следовательно,
последовательность {t/n} стремится к нулю.
Замечание. Можно доказать, что последовательность
। 1 >1
«Г, «14--: «14-----~
«2
п, + — «з
«1 4-
1
1
П2 +	।
П3 +
п4
где «1, П2, Пз,.„ — любые натуральные числа, всегда имеет пределом некоторое иррациональное число а. Если последовательность пн п2; пз;.., — периодическая, то число а имеет вид г>+ г2 , где Г] и г2 — рациональные числа. Верно и обратное—_каждое иррациональное число вида Г] + + V г2 может быть записано в виде бесконечной периодической цепной дроби. Подробнее об этом см, в книге А, Я. Хинчина «Цепные дроби».
148. Сначала докажем, что если предел {хп} существует, то он равен ± j/a". В самом деле, пусть lim xn = b. Тогда
Ит •Мы полу’
П->-О0 -4 \	Хп /	4 \	V !
чаем равенство Ь2=а, Ь= ±'\га.
, откуда
Ь =
Остается заметить, что если Хо>0, то
все члены последовательности положительны; если же Хо<О, то все члены последовательности отрицательны. По-
этому в первом случае lim хп = 1/ а, а П-ЮО
во втором litn x„=—1/аТ Л->-Оо
Остается доказать, что предел последовательности {х„} действительно существует. Пусть для определенности Хо>0 (рис. 47). Обозначим через уп разность между хп и ]Ла, деленную на]/а- Подставляя выражение х =	(!+«/„) в ра-
1	/	, а \
венство х„+1——( хп Ч-----1, мы получим
2	\ хп /
V а (1+*/„+1)=

=v(^a(I+^)+
а
V а (1 Ч*У«)
откуда
УI O/li \ * 2(1 + Уп)
Нам нужно доказать, что последовательность {у„} стремится к нулю. Заметим сначала, что так как
1+г/0=1 + ——= -^>0, Vo	Vа
то все числа уп при 1 положительны. Поэтому
2
= £/«+!=	< -у- •
Отсюда вытекает, что limr/n=0. гг—>оо Рассмотрим конкретный пример а=> з—Vio = 10, х0=3. В этом случае уй= • (3,2)2= 10,24>10, то /10<3,2.
0,2	1
3
Так как
Поэтому
1^о I —
у 10
— и, 15
значит,
Далее,
,, й <м<^_
1%1	2(1+^	2	320000 '
Поэтому |х2— V 10| = f/2VTO<3^5o< <;0,00001. Итак, чтобы найти]/ 10 с точностью до 0,00001, достаточно найти член %2- Мы имеем
= 3—= 3,166666 6
= 3— = 3,162280..
228
На самом деле ]/10=3,16227765...
Как видите, найденное нами зна^ чение действительно отличается от истин него меньше чем на 0,00001.
ОТВЕТЫ И УКАЗАНИЯ
Глава 1
2. Задачу можно решать двумя способами: методом математической индукции или используя формулу
1	= J___1
п(п+ 1) п	«4-1
3. —~.
3«4-1
6. Задачу можно решать двумя способами: исполЬ" зуя принцип математической индукции или используя равенство
J____!_ = (п-1)(п+1)
п2	п3
При решении задачи методом математической индукции начинать нужно со значения п — 2.
8.	+ 1. Пусть уже проведено п прямых.
При проведении («4-1)-й прямой количество частей плоскости увеличивается на п4-1.
9. Пусть мы можем представить п копеек (п>7>' в виде суммы трех- и пятикопеечных монет. Покажите, что тогда мы можем представить (пЧ-1) копейку в виде суммы трех- и пятикопеечных монет. Далее примените метод математической индукции, начиная с п=8.
14. Воспользуйтесь неравенством
г.1	> У Л+Т— у k.
V k+1 F F
17. Дил =2n+1.
18. а) Нельзя; б) можно. Использовать формулу Uj 4-Ди]+Ди2-|-Дил_1 = Un,
20.	Коэффициент при старшем члене многочлена равен k.
21.	Воспользоваться результатами задач 19 и 20.
22.	№..
23.	Решать задачу индукцией по k. Воспользоваться результатами задач 19 и 20.
25. Использовать результаты задач 19 и 23.
«л п (п 4" 1)(2п-|- О тл	nr
26. -------------. Из задачи 25 ясно, что сумма
6
будет выражаться многочленом 3-й степени.
97 п<п+ + 2)
28.	a) un = u\+d(n— 1); б) un=uiqn~1.
29.	a) Sn = Uln+	(/; б) Рп=
30.	a) Si5 = 35; б) Pi5= 1035.
31.	а) 0; б) 45=1024.
32.	Для доказательства оассмотреть величину
33.	210 минут = 3 часам 30 минутам.
34.	Кавалерист затратил на последний круг в 0,986 раза меньше времени, чем велосипедист.
35.	250 000.
36.	164 700. Обозначим сумму всех трехзначных положительных чисел через 5(1>, сумму трехзначных положительных чисел, делящихся на 2, — через 5(2), сумму трехзначных положительных чисел, делящихся на 3, —
через S(3), и делящихся на 6 — через 5<6>. Тогда сумма 5, которую нужно найти в задаче, равна
S = S(1> — S*2> — S(3> + S<6).
37.	ui = 3, d—6.
38.	Да, существует. Если 27 стоит на т-м месте, 8 — на n-м и 12—на р-м, то числа т, п, р удовлетворяют равенству т—Зр+2п—0.
39.	Нет, не существует,
40.	Знаменатель прогрессии может принимать значения 1; 4; 4+2 У~3 и 4—2|/3.
л, гг г;	1 +/ 5
41.	Любая прогрессия со знаменателем ---------%---
1-/5" или -------.
42.	Третий член последовательности тоже равен О,
Глава 2
44.	К решению задачи можно подойти по-разному.
Первое решение. Можно просто пересчитать все способы освещения.
0) Не горит ни одна лампа
1)	Горит одна лампа (см. схему}
(1 способ}
(5 способов)
2)	Горят две лампы (нарисуйте схему и сосчитайте сами).
(? способов)
3)	Горят три лампы. (Не спешите. Не надо ничего рисовать и считать. Подумайте и поймите, что Вы уже знаете ответ.)
(? способов) 4) Горят-четыре лампы. (Ясно, что способов освещения столько же, сколько в случае 1.) Ясно?
(5 способов)
5)	Горят все 5 ламп ооооо
(1 способ)
Ответ: всего 32 способа
Второе решение. А можно рассуждать иначе. Пусть ламп не пять, а одна. Сколько тогда способов освещения? Пусть теперь 2 лампы и т. д. Во сколько раз увеличивается число способов освещения, когда добавляется 1 лампа?
45.	Прочтите указания к задаче 44.
Употребление символа Сп позволяет фразу «В комнате 5 ламп; имеется 10 способов освещения, при которых горят 3 из них» заменить формулой Cf = 10. Что означает формула Сз =С|? Чему равно С?? Сопоставление двух методов решения задачи 44 приводит к формуле С5 4- С5 С5 С5 4- С5 4- Q’ = 25.
46.	3".
47.	Зй-2”~й.
48.	Пусть Вы каким-то образом узнали, сколько есть пятизначных чисел, не содержащих нуля и восьмерки. Не можете ли Вы теперь подсчитать, сколько есть шестизначных?
49.	Сколько есть автомобильных номеров, состоящих из двух цифр и одной буквы; из двух цифр и двух букв?
50.	Не можете ли Вы придумать задачу про лампочки, которая была бы похожа на нашу?
51.	—5050.
52.	Если порядок слагаемых существен, число разложений п—1; если не существен, то при четном п от-п	п—1
вет —, а при нечетном —-—.
„ (n—1)(л—2)
56. ------------
2
54.	Докажите, что сумма чисел в (п+1)-й строке вдвое больше, чем в п-й.
55.	Иногда предлагают такое решение. Расставим
14 слонов так, как показано на рис. 48. Ясно, что
больше чем 14 слонов (попарно не угрожающих друг другу) поставить на доску нельзя.
Однако, как правило, оказывается, что автор подобного решения не может объяснить, почему это ясно. При этом обычно он не может ответить и на второй (основной) вопрос задачи.
РИС.48
56.	С| = Ю.
57.	Ответ: С*+л. (Если Вы сейчас не можете написать формулу, выражающую ответ через п и k, рекомендуем Вам ограничиться этим ответом. Несколько позже такая формула будет найдена (см. задачи 60, 66 и 67).)
58.	С^.С3.
59.	На одной вертикали не могут стоять 2 ладьи (они угрожали бы друг другу), значит, на каждой вертикали может стоять самое большее 1 ладья.
Но вертикалей 8 и ладей 8. Значит, на каждой вертикали стоит ровно 1 ладья. Сколькими способами можно ее поставить?
60.
61.	Си • (26!) = [через п! обозначается произведение 1 • 2 • 3 • 4... (п—!)•«].
62.	d-5! = -|U О:
64.	Cl • 8 • 7 • 6 • 5.
сс ,-з	л(л—1)(л—2)
би. С/ fl -	а
1-2-3
67.	С^ = ».(п-1)(Я-2)-(п-^-Ц)	. попытайтесь
1-2-3- ... -k
доказать эту формулу методом задачи 66.
се лб 88!	-	88!
68.	/1S8 = —— последовательностей, С88 =-------- ак-
6!	6! 82!
кордов.
69.	В строках с номерами 2", п=1, 2, 3,
70.	27.
•74 /"3	7-6-5
/ 1. Су = ------,
1-2-3
72. З20.
74.	Коэффициент при х8 равен de. коэффициент при х48 равен C56 = Cse.
78.	Указание:	(а + Ь)п = ап	4- — .
79.	Найдите сначала все члены, содержащие xk.
80.	Решим похожую задачу: доказать, что
2"=С„0 + С’ + С„ + ... +	+ ... + СГ1 + С”.
Эта задача, правда, уже встречалась, но сейчас мы решим ее другим методом. В тождестве (!+%)" = =С„ + Сп х -|- Сп х2 ... С„ хк + ... 4- С„ 1х"—1 4- С^х" положим х— 1. Получим 2" = С®4- С'п • 1 4- С„-12 4- ... 4-4-СтМ", что и требовалось доказать.
82.	Тремя нулями.
83.	Представьте 99 и 101 в виде: 99=100—1 и 101 = 100+1.
84.	25.
85.	У к а з а н и е: 10! = 28- З4 • 52 • 71; не можете ли Вы сказать, сколько делителей имеет число 28•З4?
87.	Какой может быть последняя цифра нашего числа? Первая цифра? Ответ: 42.
88.	29.
ап Сп Сп <3«)!
90.	С3л.С2л = —— (п!)3
91.	В комнате 11 человек,* только английский знает один.
93.	Можно воспользоваться результатом задачи 92, а можно попытаться сосчитать число номеров, не содержащих комбинацию 12, Ответ: 49401,
Глава 3
95.	Случай Н— невозможен. Остальные возможны.
96.	Возможны оценки: + + +; —F + ; —I—;
97.	а) Самый низкий из высоких всегда выше, чем самый высокий из низких, б) Изменится. При такой расстановке возможны оба случая.
98.	Контрольная работа называется трудной, если хотя бы на одной парте каждый ученик не решил хотя бы одну задачу.
99.	Может.
100.	Верны теоремы 1 и 6, остальные — нет.
101.	Первая группа — теорема 8; вторая группа — теоремы 2, 3, 6 и 7; третья группа — теоремы 4 и 5.
102.	а), б) Рассмотрите отдельно случаи х^-0 и х<0. в) Рассмотрите отдельно случаи х<—	—— -С
и	Ответы: a) Xi = l, %2=—3;
б)	хг=1, х2= — 1; в) отрезок —у, .
103.	Рассмотрите отдельно различные случаи расположения точек х, у и 0 на числовой оси. В случае а) равенство возможно, только когда х>-0, t/2>0 или у<0. В случае б) возможно, когда 4/^-0 или 0. В случае в) когда х>-0, или у^О.
104.	Утверждения а), б) и в) верны; г)—неверно.
105.	Верно.
106.	Верно.
107.	б) См. задачу 108.
108.	Для последовательности а) все указанные отрезки являются ловушками. Для последовательности б) отрезки А) и Б) — кормушки, отрезок В) — ловушка.
Для последовательности в) все три отрезка — кормушки.
109.	а) Существует; б) не существует.
110.	а) Не существует; б) неизвестно. .Может существовать и может не существовать.
111.	а) Существует; б) существует.
112. Соответствующие значения k приведены в таблице.
	А	Б	в
а	1	1 000	1 000 000
б	0	1Л999-	999 999
в	0	3 1g 2	6 1g 2
г	2	2юоо	21000000
113. б) Верно.
114.	6) Нельзя. См. последовательность из задачи 108в).
115.	Используйте задачу 1096),
116.	а) Предел равен 0; б) предел равен 1; в) предел равен 2; г) предела не существует; д) предел равен 1; е) предел равен 0; ж) предел равен 2/9; з) предела не существует; и) предел равен 0; к) предела не существует.
117.	Не могут. (Указание: ср. задачу 115.)
118.	Указание к б): сформулируйте, что значит, что число а не является предельной точкой последовательности.
119.	См. задачи 113а), 107а), 1186).
120.	а) 1; б) 1, —1; в) 0; ±sin 1°, ±sin 2°, ..., ±sin 89°, ±1; г) 0; д) предельных точек нет; е) предельные точки заполняют отрезок [0, 1],
121.	Последовательность {%„} называется неограниченной, если для любого С найдется такой номер п, что выполняется неравенство |х„ I >С.
122.	Неверно. См. задачу 1086).
123.	а) хп^ со; б) хп -+ оо; в) {хп} — не ограничена; г) хп-> оо; д) {хп} — ограничена.
124.	а) хп= (-у)" I 6)*n=V;
г) хп = (— !)"•
125.	1) Условию удовлетворяют все последовательности. 2) Не все члены последовательности равны а. 3) Последовательность ограничена. 4) Точка а не является предельной точкой последовательности. 5) Последовательность не стремится к бесконечности. 6) Число а не является пределом последовательности. 7) Последовательность ограничена. 9) Число а является либо одним из членов последовательности {*„}, либо предельной точкой этой последовательности*).
Остальные условия являются отрицаниями перечисленных. А именно, условие с номером к) означает, что не выполняется условие с номером 17—к). Например, условие- 10 означает, что не выполняется условие 7, т. е. последовательность не ограничена. Условие 15 означает, что не выполнено условие 2, т, е. все члены последовательности равны а и т. д.
126.	а) -)—|—|—|-; хп = а\
-+ + + —; Х„ = а + —;
п
-----+	+ -;	хп = а+	1 +(—!)";
-- +--------;	хп = а+	ц[1 + (-1)”];
-------+ -; лл = а + (—1)";
-----------+;	х„ = п;
------------;	хп = а+	1+ п[1 +(—!)«].
*) Если выполняется условие 9, то точка а называется точкой прикосновения для последовательности 1*л}.
127.	1) x„=-L; 2) xn = ^=L; 3) xn = (—LV n	n	\ z )
128.	Докажите, что если бесконечная последовательность не имеет наибольшего члена, то из нее можно выбрать бесконечную возрастающую подпоследовательность.
129.	Докажите, что последовательность 1,4; 1,41; 1,414; 1,4142; 1,41422; ... приближенных (с недостатком) значений для -\f 2 монотонна, ограничена и не имеет рационального предела.
130.	Воспользуйтесь результатом задачи 128 и аксиомой Больцано-Вейерштрасса.
131.	а) Воспользуйтесь неравенством —<-----!-- и
ла	л (л—1)
докажите, что последовательность ограничена, б) Рассмотрите отдельно подпоследовательности, составленные из членов с четными и нечетными номерами.
133. а) хп Уп = -t; б) хп = Уп= п	п	П	П
. 1 1.1	(—1)"
В) Хп = —,^п=-г; г)хп=—, уп= п	п	п	п
9	1
134.	а) у; б) 0; в) 1; г) 1; д) p-J-p
135.	Воспользуйтесь тождеством а—b Уа+ ф'Т’
136.	Представьте 2" в виде (1 + 1)" и воспользуйтесь формулой бинома.
137.	Представьте ап в виде [1 + (а—1)]" и воспользуйтесь формулой бинома.
138.	Воспользуйтесь результатом задачи 136.
139.	1.
140.	Возьмем начало координат в точке, где находится вторая улитка. Оси координат направим по линиям клетчатой бумаги и за единицу масштаба возьмем одну клетку. Пусть первая улитка в начальный момент находится в точке с координатами (а, Ь). Найдите
координаты (ап, bn) точки, в которую попадет улитка за п шагов. Угловой коэффициент прямой, по которой направлена подзорная труба, равен kn=^bjan. Докажите, что lim Aj„=1.
Л-+ОО
141.	См. указание к задаче 140. Ответы: a) lim kn~ =2; б) lim&„=l; в) последовательность {&„} не имеет л—>оо предела.
142.	Опустим из точек Ао и 4„ перпендикуляры на ось Ох. Пусть Ро и Рп—основания этих перпендикуляров. Докажите, что треугольники МпА0Р0 и МпАпРп подобны, и вычислите отсюда длину отрезка МпРд. От-в е т: Точка М — середина отрезка ОРд.
143.	Отметьте на листе бумаги три точки, изображающие школу, кинотеатр и каток. Возьмите произвольную четвертую точку и постройте ломаную линию Л^ДзЛ*-> изображающую путь мальчика Пети. Сравните отрезки AiAj, А%А$, АзАд. Д4Л7 и т. д.
1—а
|а|	1 ряд расходится; б)
при I а | < 1 S = —-—, 1 1 1	(1—<з)2
(Указание: представьте Sn в ких прогрессий.) в) 1 1 (п+1) (п+2) J ’ докажите, что
при
L2 зание:
144.	Точка М делит отрезок в отношении 2:1. 145. a) Sn= 1 ~° + ; при |а| <1	-р1-^ , при
£ _ а — (и + 1 — па)ап+1 .
П~	(1—0)2
|а|	1 ряд расходится,
виде суммы п геометри«ее-/г s=1; г) s-=4-x =-—; д) ряд расходится. (УКа-4
1 1 । । 1 - 1 \ + 1 и + 2	2п 2 )
= 1
146.	Можно построить «крышу» как угодно большой длины. Указание: примем длину кирпича за 1. Докажите по индукции, что кирпичи не будут падать, если (и+’)-й кирпич (считая сверху) сдвинуть относительно n-го кирпича на 1/2и. После этого воспользуйтесь результатом задачи 145д). •
147.	1 + 1/2.
148.	Достаточно вычислить х2.
Сергей Израилевич Гельфанд
Михаил
Львович Гервер
Александр Александрович Кириллов
Николай Николаевич Константинов
Анатолий Георгиевич Кушниренко
	Задачи по элементарной математике. Последовательности. Комбинаторика. Пределы М„ 1965 г., 176 стр. с илл.
Редакторы:	Б. В. Шабат и А. 3. Рывкин
Художники серии:	В. В. Смолянинов и В. Б. Янкилевский
Техн, редактор Корректор	С. Я. Шкляр Г. Г. Желтова
Сдано в набор Подп. к печати Бумага Физич. печ. л, Усл. печ. л, Уч.-изд. л.	3/V 1965 г. 2/VI 1965 г. 84X108732 5,5 9,02 6,67
Т-06970 Тираж Цена книги Заказ	200 000 экз. 20 коп. 394 Издательство «Наука» Главная редакция физико-математической литературы. Москва, В-71, Ленинский проспект, 15
1-я тип. Профиздага. Москва, Крутицкий вал, 18
Математика
Библиотечка
фпзико-математической школМ
Серия основная
Выпуск 1.	II. М. Гельфанд, Е. Г. Глаголева, А А. Кириллов.
Метол координат
ыпуск 2.	II. М. Гельфанд, Е. Г. Глаголева, Э. Э. Шиоль.
Функции и графики (основные приемы)
Выпуск 3.	С. И. Гельфанд, М. .П. Гсрвер, А. Л. Кириллов,
Н. II. Константинов, Л. Г. Купишренко. Задачи по элементарной математике Последовательно сти, комбинаторика, пределы