стр. 1
(всего 9)

СОДЕРЖАНИЕ

>>

Алгебра и теория чисел для
математических школ

Н. Б. Алфутова, А. В. Устинов

September 3, 2003
УДК 51
ББК 21.1
А45




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

ББК 21.1




c Алфутова Н. Б., Устинов А. В., 2002.
c МЦНМО, 2002.
ISBN 5-94057-038-0
Предисловие

Настоящее пособие представляет собой сборник задач по математи-
ке, предназначенный прежде всего для учеников старших классов, инте-
ресующихся точными науками. Он также будет полезен преподавателям
математики и студентам, изучающим математику в высших учебных
заведениях. Значительная часть материала может быть использована
для подготовки к письменным и устным вступительным экзаменам в
ВУЗы.
Основу сборника составляют задачи к курсу алгебры, который в
1995 – 2000 годах читался О. А. Чалых, Н. Б. Алфутовой и А. В. Усти-
новым. В приложении А приведена программа этого курса. Для того,
чтобы сделать содержание книги более широким и целостным, авторы
включили в нее дополнительный материал, собрав и упорядочив задачи
из других источников.
Математические курсы, читаемые в школе-интернате им. А. Н. Кол-
могорова, традиционно содержат разделы, которые можно назвать
смежными. Они находятся на стыке алгебры с комбинаторикой, геомет-
рией, теорией чисел и математическим анализом. Поэтому некоторые
задачи из книги имеют к алгебре лишь косвенное отношение. Эти
задачи призваны подчеркнуть связь различных разделов математики
и проиллюстрировать многообразие методов.
В каждой главе кратко излагается теоретический материал, необ-
ходимый для понимания задач. В конце задачи иногда даются ссылки
на задачи или литературу, которые непосредственно связаны с данным
материалом.
При подготовке пособия использовались различные учебники и мо-
нографии, сборники олимпиадных и конкурсных задач, большая часть
упражнений была почерпнута из многочисленных публикаций журнала
«Квант». В результате работы над книгой был создан своеобразный
путеводитель, помещенный в приложение Б. В нем по каждой из тем
задачника даны ссылки на соответствующие публикации. К сожалению,
в настоящий момент не представляется возможным указать авторов
всех задач, вошедших в книгу, и перечислить все оригинальные источ-
ники. Часть материала встречается сразу в нескольких сборниках. Со
многими задачами авторы познакомились еще за время своего обучения
в школе-интернате. Некоторые упражнения рождались в разговорах с
коллегами по кафедре математики.
В настоящее время в центре дополнительного образования «Ди-
стантное обучение» идет работа над созданием сетевого аналога курса
алгебры с использованием материалов данной книги. Авторы надеятся,
что в ближайшее время он также станет доступен читателям.
Авторы приносят глубокую благодарность педагогам и математи-
кам, работавшим в разное время в ФМШ № 18 при МГУ (позднее в
школе им. А. Н. Колмогорова), опыт которых отражен в этой книге.
Особенно авторы благодарят В. В. Вавилова, А. А. Егорова, И. Д. Кана,
которые взяли на себя труд прочесть предварительные варианты книги,
за их многочисленные добавления, исправления и полезные советы.
Отдельное спасибо О. А. Соловьеву за неизменную TEX-ническую под-
держку.
Авторы будут благодарны читателям за отзывы, критические заме-
чания, предложения и новые задачи. Их можно отправлять по элек-
тронной почте или по адресу: 117630, Москва, ул. акад. Челомея, д. 8 Б,
ЦДО «Дистантное обучение».

Н. Б. Алфутова
alpha@pisem.net
А. В. Устинов
ustinov@mech.math.msu.su
Обозначения
В списке указаны страницы, на которых введены эти обозначения.


Обозначение Смысл Стр.
множество натуральных чисел
N
множество целых чисел
Z
множество рациональных чисел 70
Q
целая часть числа x (наибольшее целое, не превос-
[x]
ходящее x)
{x} дробная часть числа x: {x} = x ? [x]
факториал: n! = 1 · 2 · . . . · n 7
n!
{xn } последовательность x1 , x2 , . . . , xn , . . .
b|a b делит a 8
.b
. a кратно b 8
a.
a ? b mod m a сравнимо с b по модулю m 53
? класс вычетов по модулю m 53
a
запись числа в q-ичной системе счисления 6
(ak . . . a0 )q
наибольший общий делитель чисел a1 , . . . , an 29
(a1 , . . . , an )
наименьшее общее кратное чисел a1 , . . . , an 32
[a1 , . . . , an ]
[a0 ; a1 , . . . , an ] цепная дробь 42
функция Эйлера 60
?(n)
количество положительных делителей числа n 34
?(n)
сумма положительных делителей числа n 34
?(n)
числа Фибоначчи 36
Fn v
мнимая единица i = ?1 101
i
множество комплексных чисел 101
C
комплексно сопряженное число к числу z 101
z
arg z аргумент комплексного числа z 101
|z| модуль комплексного числа z 101
отношение длины окружности к диаметру
?
основание натуральных логарифмов 73
e v
? = ( 5 + 1)/2 — число Фидия 39
?
оператор конечной разности 151
?
?n
Ak число k-размещений с повторениями из n элементов 16
k
число k-размещений без повторений из n элементов 16
An
число перестановок из n элементов 17
Pn
k
число k-сочетаний с повторениями из n элементов 17
Cn
k
число k-сочетаний без повторений из n элементов 17
Cn
числа Каталана 25
Cn
репьюнит порядка n: En = 11 . . . 1 74
En
n
Глава 1
Метод математической индукции

1. Аксиома индукции
Аксиома индукции. Если известно, что некоторое утверждение
верно для 1, и из предположения, что утверждение верно для некото-
рого n, вытекает его справедливость для n+1, то это утверждение верно
для всех натуральных чисел.
1.1. Деление с остатком. Докажите, что если a и b — целые числа
и b = 0, то существует единственная пара чисел q и r таких, что

r < |b|.
a = bq + r, 0

1.2. Позиционная система счисления. Докажите, что при целом
q 2 каждое натуральное число n может быть единственным образом
представлено в виде

n = ak qk + ak?1 qk?1 + . . . + a1 q + a0 ,

где 0 a0 , . . . , ak < q. (См. также 3.125, 11.68.)
Определение. Если ak , ak?1 , . . . , a1 , a0 — цифры числа n в q-ич-
ной системе счисления, то используется запись n = (ak ak?1 . . . a1 a0 )q .
Для записи числа в десятичной системе счисления используется так-
же запись (ak ak?1 . . . a1 a0 )10 = ak ak?1 . . . a1 a0.
1.3. Пусть {an } = a0 , a1 , . . . , an , . . . — периодическая последова-
тельность, то есть для некоторого натурального T

(n
an+T = an 0).

Докажите, что среди всех периодов этой последовательности существу-
ет период наименьшей длины t, причем T делится на t без остатка.
1.4. Аксиомы индукции. Докажите, что аксиома индукции рав-
носильна любому из следующих утверждений. (См. также 12.1.)
1) Всякое непустое подмножество натуральных чисел содержит наи-
меньшее число.
2. Тождества, неравенства и делимость 7

2) Всякое конечное непустое подмножество натуральных чисел со-
держит наибольшее число.
3) Если некоторое множество натуральных чисел содержит 1 и вме-
сте с каждым натуральным числом содержит следующее за ним, то оно
содержит все натуральные числа.
4) Если известно, что некоторое утверждение верно для некоторо-
го a, и из предположения, что утверждение верно для всех натуральных
чисел k, таких, что a k < n вытекает его справедливость для n, то
это утверждение верно для всех натуральных чисел k a.
5) (Обратная индукция.) Если известно, что некоторое утвержде-
ние верно для 1 и 2, и из предположения, что утверждение верно для
некоторого n > 1, вытекает его справедливость для 2n и n ? 1, то это
утверждение верно для всех натуральных чисел.
1
1.5. Число x таково, что число x + — целое. Докажите, что при
x
1
любом натуральном n число xn + также является целым. (См. так-
xn
же 7.46.)
1.6. Даны натуральные числа x1 , . . . , xn . Докажите, что число

(1 + x2 ) · . . . · (1 + x2 )
1 n

можно представить в виде суммы квадратов двух натуральных чисел.
(См. также 7.14.)
1.7. Числовая последовательность A1 , A2 , . . . , An , . . . определена
равенствами

(n
A1 = 1, A2 = ?1, An = ?An?1 ? 2An?2 3).

2 число 2n+2 ?7A2 является полным квадратом.
Докажите, что при n n


2. Тождества, неравенства и делимость
Определение. Через n! (читается «n факториал») обозначается
произведение всех натуральных чисел от 1 до n:

n! = 1 · 2 · . . . · n.

Для удобства считается, что 0! = 1.
В задачах 1.8 – 1.14 докажите тождества.
1.8. 1 + 3 + 5 + . . . + (2n ? 1) = n2 .
n(n + 1)(2n + 1)
1.9. 12 + 22 + . . . + n2 = .
6
8 1. Метод математической индукции

n(2n ? 1)(2n + 1)
1.10. 12 + 32 + . . . + (2n ? 1)2 = .
3
1.11. 13 + 23 + . . . + n3 = (1 + 2 + . . . + n)2 .
n(n + 1)(n + 2)(n + 3)
1.12. 1 · 2 · 3 + 2 · 3 · 4 + . . . + n(n + 1)(n + 2) = .
4
12 22 n2 n(n + 1)
1.13. .
+ + ... + =
1·3 3·5 (2n ? 1)(2n + 1) 2(2n + 1)
1.14. 1 · 1! + 2 · 2! + . . . + n · n! = (n + 1)! ? 1.
1.15. Факториальная система счисления. Докажите, что каж-
дое натуральное число n может быть единственным образом представ-
лено в виде
n = a1 · 1! + a2 · 2! + a3 · 3! + . . . ,
где 0 3, . . .
a1 1, 0 a2 2, 0 a3
1.16. Числа a0 , a1 , . . . , an , . . . определены следующим образом:
(n
a0 = 2, a1 = 3, an+1 = 3an ? 2an?1 2).
Найдите и докажите формулу для этих чисел.
Определение. Пусть a — целое и b — натуральное числа. b называ-
ется делителем a, если существует целое число q такое, что a = bq.
В этом случае a называется кратным b, а q — частным от деления a
на b.
Соотношение «b делит a» записывается в виде b | a или в виде
. b («a кратно b»). Причем эти записи всегда включают в себя
.
a.
предположение, что b = 0.
Если b не является делителем a, то будем писать b a.
Докажите, что в задачах 1.17 – 1.24, указанные соотношения выпол-
няются для любого натурального n.
.
.
1.17. 10n + 18n ? 1 . 27.
1.18. 11n+2 + 122n+1 . 133.
.
.
.
1.19. 25n+3 + 5n · 3n+2 . 17.
.
1.20. n3 + 5n . 6.
.
.
.
.
1.21. 62n+1 + 1 . 7.
.
.
1.22. 32n+2 + 8n ? 9 . 16.
.
.
1.23. 4n + 15n ? 1 . 9.
.
n
.
1.24. 23 + 1 . 3n+1 .
1.25. Докажите, что для всех натуральных n число, записываемое
3 единицами, делится на 3n .
n
2. Тождества, неравенства и делимость 9

1.26* . Из чисел от 1 до 2n выбрано n+1 число. Докажите, что среди
выбранных чисел найдутся два, одно из которых делится на другое.
(См. также 2.34.)
1.27. Решите уравнение
x(x ? 1) · . . . · (x ? n + 1)
x(x ? 1)
x
? . . . + (?1)n
1? + = 0.
1! 2! n!
В задачах 1.28 – 1.36 докажите справедливость неравенств для нату-
ральных n.
1 1 1 1
1.28. + 2 + 2 + . . . + 2 < 2. (См. также 7.81.)
12 2 3 n
v
1 1 1
1.29. v + v + . . . + v n.
n
1 2
4n
(2n)!
1.30. .
>
(n!)2 n+1
1 1 1 13
1.31. (n > 1).
+ + ... + >
n+1 n+2 2n 24
1.32. Неравенство Бернулли. (1+x)n 1+nx при любом x > ?1.
1.33. 2n > n.
1 · 3 · 5 · . . . · (2n ? 1) 1
v
1.34. .
2 · 4 · 6 · . . . · 2n 2n + 1
1.35. nn+1 > (n + 1)n (n > 2).
1.36. |x1 + . . . + xn | |x1 | + . . . + |xn |, где x1 , . . . , xn — произвольные
числа.
1.37* . Неравенство между средним арифметическим и сред-
ним геометрическим. Докажите неравенство
v
x1 + . . . + xn
x1 · . . . · xn ,
n
n
где x1 , . . . , xn — положительные числа.
1.38. Докажите неравенство 2m+n?2 mn, где m и n — натуральные
числа.
1.39. Для каких n выполняются неравенства:
а) n! > 2n ; б) 2n > n2 .
1.40. Вычислите произведение
23 ? 1 33 ? 1 n3 ? 1
·3 · ... · 3 (n 2).
23 + 1 3 + 1 n +1
10 1. Метод математической индукции

3. Индукция в геометрии и комбинаторике
1.41. Из квадрата клетчатой бумаги размером 16 ? 16 вырезали
одну клетку. Докажите, что полученную фигуру можно разрезать на
«уголки» из трех клеток.
1.42. Ханойская башня I. Головоломка «Ханойская башня» пред-
ставляет собой 8 дисков, нанизанных в порядке уменьшения размеров
на один из трех колышков. Задача состоит в том, чтобы переместить
всю башню на один из других колышков, перенося каждый раз только
один диск и не помещая больший диск на меньший.
Докажите, что эта головоломка имеет решение. Какой способ ре-
шения головоломки будет оптимальным (по числу перемещений)? (См.
также 5.71.)
1.43. Ханойская башня II. Занумеруем колышки в задаче о Ха-
нойской башне числами 1, 2, 3. Предположим, что требуется переме-
стить диски с 1-го колышка на 3-й. Сколько понадобится перекладыва-
ний, если прямое перемещение диска с 1-го колышка на 3-й запрещено?
(Каждое перекладывание должно производится через 2-й колышек. Как
и раньше, больший диск нельзя класть на меньший.)
1.44. Ханойская башня III. Сколько понадобится перекладыва-
ний, если в условии задачи 1.42 добавить дополнительное требование:
первый диск нельзя класть на второй колышек?
1.45. Докажите, что квадрат можно разрезать на n квадратов для
любого n, начиная с шести.
1.46. Докажите, что правильный треугольник можно разрезать на
n правильных треугольников для любого n, начиная с шести.
1.47. Золотая цепочка. а) На постоялом дворе остановился пу-
тешественник, и хозяин согласился в качестве уплаты за проживание
брать кольца золотой цепочки, которую тот носил на руке. Но при
этом он поставил условие, чтобы оплата была ежедневной: каждый день
должно быть отдано ровно на одно кольцо больше, чем в предыдущий
день. Замкнутая в кольцо цепочка содержала 11 колец, а путешествен-
ник собирался прожить ровно 11 дней, поэтому он согласился. Какое
наименьшее число колец он должен распилить, чтобы иметь возмож-
ность платить хозяину?
б) Из скольких колец должна состоять цепочка, чтобы путешествен-
ник мог прожить на постоялом дворе наибольшее число дней при усло-
вии, что он может распилить только n колец?
1.48. Банк имеет неограниченное количество трех- и пятирублевых
купюр. Докажите, что он может выдать ими без сдачи любое число
рублей, начиная с восьми. (См. также 3.72.)
3. Индукция в геометрии и комбинаторике 11

1.49* . Гениальные математики. а) Каждому из двух гениальных
математиков сообщили по натуральному числу, причем им известно,
что эти числа отличаются на единицу. Они поочередно спрашивают
друг друга: «Известно ли тебе мое число?» Докажите, что рано или
поздно кто-то из них ответит «да». Сколько вопросов они зададут друг
другу? (Математики предполагаются правдивыми и бессмертными.)
б) Как изменится число заданных вопросов, если с самого начала
известно, что данные числа не превосходят 1000?
1.50. На сколько частей делят плоскость n прямых «общего поло-
жения», то есть таких, что никакие две не параллельны и никакие три
не проходят через одну точку?
1.51. На плоскости проведены n окружностей так, что любые две из
них пересекаются в паре точек, и никакие три не проходят через одну
точку. На сколько частей делят плоскость эти окружности?
1.52. На сколько частей делят пространство n плоскостей, проходя-
щих через одну точку, если никакие три не имеют общей прямой?
1.53* . На сколько частей делят пространство n плоскостей «общего
положения»? И что это за «общее положение»?
1.54. Плоскость поделена на области несколькими прямыми. Дока-
жите, что эти области можно раскрасить в два цвета так, чтобы любые
две соседние области были окрашены в разные цвета. (Соседними на-
зываются области, имеющие общий участок границы.)
1.55. Сумма углов n-угольника. Докажите, что произвольный
n-угольник (не обязательно выпуклый) можно разрезать на треуголь-
ники непересекающимися диагоналями. Выведите отсюда, что сумма
углов в произвольном n-угольнике равна (n ? 2)?.
1.56. Клетки шахматной доски 100 ? 100 раскрашены в 4 цвета так,
что в любом квадрате 2 ? 2 все клетки разного цвета. Докажите, что
угловые клетки раскрашены в разные цвета.
1.57. Имеется k ящиков. В некоторых из них лежат еще k ящиков.
В некоторых из последних лежат еще ящики (снова k штук) и т. д.
Сколько всего ящиков, если заполненных m?
1.58. Теорема Эйлера. Докажите, что для любого выпуклого
многогранника имеет место соотношение

В ? Р + Г = 2,

где В — число его вершин, Р — число ребер, Г — число граней.
12 1. Метод математической индукции

1.59* . Задача Сильвестра. На плоскости взяты несколько точек
так, что на каждой прямой, соединяющей любые две из них, лежит по
крайней мере еще одна точка. Докажите, что все точки лежат на одной
прямой.
1.60. Выпуклая оболочка. Докажите, что для любого числа точек
плоскости найдется выпуклый многоугольник с вершинами в некоторых
из них, содержащий внутри себя все остальные точки.
1.61. Сколько существует (невырожденных) треугольников пери-
метра 100 с целыми длинами сторон?
Глава 2
Комбинаторика

1. Сложить или умножить?
2.1. а) В Стране Чудес есть три города A, B и C. Из города A в
город B ведет 6 дорог, а из города B в город C — 4 дороги. Сколькими
cпособами можно проехать от A до C?
б) В Стране Чудес построили еще один город D и несколько новых
дорог — две из A в D и две из D в C. Сколькими способами можно
теперь добраться из города A в город C?
Правило суммы. Если элемент a можно выбрать m способами, а
элемент b (независимо от выбора элемента a) — n способами, то выбор
«a или b» можно сделать m + n способами.
Правило произведения. Если элемент a можно выбрать m спо-
собами, а элемент b (независимо от выбора элемента a) — n способами,
то выбор «a и b» можно сделать m · n способами.
2.2. Cколько существует различных семизначных телефонных но-
меров (cчитается, что номер начинаться с нуля не может)?
2.3. Номер автомашины состоит из трех букв русского алфавита
(30 букв) и трех цифр. Сколько существует различных номеров авто-
машин?
2.4. В некоторой школе каждый школьник знаком с 32 школьница-
ми, а каждая школьница — с 29 школьниками. Кого в школе больше:
школьников или школьниц и во сколько раз?
2.5. В языке одного древнего племени было 6 гласных и 8 согласных,
причем при составлении слов гласные и согласные непременно чередо-
вались. Сколько слов из девяти букв могло быть в этом языке?
2.6. Алфавит племени Мумбо-Юмбо состоит из трех букв. Словом
является любая последовательность, состоящая не более чем из четырех
букв. Сколько слов в языке племени Мумбо-Юмбо? (См. также 12.9.)
2.7. Сколько существует шестизначных чисел, делящихся на 5?
2.8. Сколько существует шестизначных чисел, в записи которых есть
хотя бы одна четная цифра?
14 2. Комбинаторика

2.9. Сколько существует десятизначных чисел, в записи которых
имеется хотя бы две одинаковые цифры?
2.10. Каких семизначных чисел больше: тех, в записи которых есть
единица, или остальных?
2.11. Пассажир оставил вещи в автоматической камере хранения,
а когда пришел получать вещи, выяснилось, что он забыл номер. Он
только помнит, что в номере были числа 23 и 37. Чтобы открыть камеру,
нужно правильно набрать пятизначный номер. Каково наименьшее ко-
личество номеров нужно перебрать, чтобы наверняка открыть камеру?
(Числа 23 и 37 можно увидеть и в числе 237.)
2.12. Сколько существует пятизначных чисел, которые одинаково
читаются слева направо и справа налево (например, таких как 54345,
17071)?
2.13. Сколько существует девятизначных чисел, сумма цифр кото-
рых четна?
2.14. Сколькими способами можно разложить 7 монет различного
достоинства по трем карманам?
2.15. Назовем натуральное число «симпатичным», если в его записи
встречаются только нечетные цифры. Сколько существует четырех-
значных «симпатичных» чисел?
2.16* . На двух клетках шахматной доски стоят черная и белая фиш-
ки. За один ход можно передвинуть любую из них на соседнюю по
вертикали или по горизонтали клетку. (две фишки не могут стоять
на одной клетке). Могут ли в результате таких ходов встретится все
возможные варианты расположения этих двух фишек, причем ровно
по одному разу?

2. Принцип Дирихле
Принцип Дирихле (принцип ящиков). При любом распределе-
нии nk + 1 или более предметов по n ящикам в каком-нибудь ящике
окажется не менее чем k + 1 предмет.
2.17. Докажите, что среди москвичей есть два человека с равным
числом волос, если известно, что у любого человека на голове менее
одного миллиона волос.
2.18. В мешке 70 шаров, отличающихся только цветом: 20 красных,
20 синих, 20 желтых, остальные — черные и белые. Какое наименьшее
число шаров надо вынуть из мешка, не видя их, чтобы среди них было
не менее 10-ти шаров одного цвета?
2. Принцип Дирихле 15

2.19. Некоторые точки из данного конечного множества соединены
отрезками. Докажите, что найдутся две точки, из которых выходит
поровну отрезков.
2.20. Имеется 2k + 1 карточек, занумерованных числами от 1 до
2k + 1. Какое наибольшее число карточек можно выбрать так, чтобы ни
один из извлеченных номеров не был равен сумме двух других извле-
ченных номеров?
2.21. Какое наибольшее число королей можно поставить на шахмат-
ной доске так, чтобы никакие два из них не били друг друга?
2.22. Сто человек сидят за круглым столом, причем более половины
из них — мужчины. Докажите, что какие-то двое из мужчин сидят друг
напротив друга.
2.23. На складе имеется по 200 сапог 41, 42 и 43 размеров, причем
среди этих 600 сапог 300 левых и 300 правых. Докажите, что из них
можно составить не менее 100 годных пар обуви.
2.24. Несколько футбольных команд проводят турнир в один круг.
Докажите, что в любой момент турнира найдутся две команды, сыг-
равшие к этому моменту одинаковое число матчей.
2.25* . Дано 51 различных двузначных чисел (однозначные числа
считаем двузначными с первой цифрой 0). Докажите, что из них можно
выбрать 6 таких чисел, что никакие 2 из них не имеют одинаковых цифр
ни в одном разряде.
2.26. Числа от 1 до 101 выписаны в произвольном порядке. Докажи-
те, что из них можно вычеркнуть 90 чисел так, что оставшиеся 11 чисел
будут следовать одно за другим в порядке возрастания или убывания.
2.27. Имеется 2000 точек. Какое максимальное число троек можно
из них выбрать так, чтобы каждые две тройки имели ровно одну общую
точку?
2.28. Даны 1002 различных числа, не превосходящих 2000. Дока-
жите, что из них можно выбрать три таких числа, что сумма двух из
них равна третьему. Останется ли это утверждение справедливым, если
число 1002 заменить на 1001?
2.29* . Дана прямоугольная таблица, в каждой клетке которой на-
писано вещественное число, причем в каждой строке таблицы числа
расположены в порядке возрастания. Докажите, что если расположить
числа в каждом столбце таблицы в порядке возрастания, то в строках
полученной таблицы числа по-прежнему будут располагаться в порядке
возрастания.
16 2. Комбинаторика

2.30. В волейбольном турнире команды играют друг с другом по од-
ному матчу. За победу дается одно очко, за поражение — ноль. Известно,
что в один из моментов турнира все команды имели разное количество
очков. Сколько очков набрала в конце турнира предпоследняя команда
и как она сыграла с победителем?
2.31. Бесконечная клетчатая доска раскрашена в три цвета (каждая
клеточка — в один из цветов). Докажите, что найдутся четыре клеточки
одного цвета, расположенные в вершинах прямоугольника со сторона-
ми, параллельными стороне одной клеточки.
2.32. Докажите, что из 11 различных бесконечных десятичных дро-
бей можно выбрать две такие, которые совпадают в бесконечном числе
разрядов.
2.33. На плоскости даны 6 точек так, что никакие три из них не
лежат на одной прямой. Каждая пара точек соединена отрезком си-
него или красного цвета. Докажите, что среди данных точек можно
выбрать такие три, что все стороны образованного ими треугольника
будут окрашены в один цвет. (См. также 5.36.)
2.34. Докажите утверждение задачи 1.26 при помощи принципа
Дирихле.

3. Размещения, перестановки и сочетания
Определение. Пусть M = {a1 , . . . , an } — множество из n элемен-
тов. Наборы вида (ai1 , . . . , aik ) будем называть k-размещениями. Два
k-размещения считаются различными, если они отличаются друг от
друга входящими в них элементами или порядком элементов.
Если в размещениях элементы ai1 , . . . , aik попарно различны, то
это размещения без повторений. Если же среди элементов ai1 , . . . , aik ,
могут попадаться одинаковые, то такие наборы называются размеще-
ниями с повторениями.
Количества размещений без повторений и с повторениями обознача-
?
ются Ak и Ak соответственно.
n n

2.35. Докажите равенства:
?
а) Ak = n(n ? 1) . . . (n ? k + 1); б) Ak = nk .
n n

2.36. В пассажирском поезде 17 вагонов. Сколькими способами мож-
но распределить по вагонам 17 проводников, если за каждым вагоном
закрепляется один проводник?
Определение. Перестановками называются n-размещения без по-
вторений элементов множества M = {a1 , . . . , an }.
3. Размещения, перестановки и сочетания 17

Количество перестановок множества из n элементов обозначает-
ся Pn .
2.37. Докажите равенство Pn = n!.
2.38. Сколько существует способов расставить 8 ладей на шахмат-
ной доске так, чтобы они не били друг друга?
2.39. Семнадцать девушек водят хоровод. Сколькими различными
способами они могут встать в круг?
2.40. Сколько существует ожерелий, составленных из 17 различных
бусинок?
2.41. Найдите сумму всех 7-значных чисел, которые можно полу-
чить всевозможными перестановками цифр 1, . . . , 7.
2.42. а) Сколькими способами 28 учеников могут выстроиться в
очередь в столовую?
б) Как изменится это число, если Петю Иванова и Колю Васина
нельзя ставить друг за другом?
2.43. Сколькими способами можно выбрать четырех человек на че-
тыре различные должности, если имеется девять кандидатов на эти
должности?
2.44. Из класса, в котором учатся 28 человек, назначаются на де-
журство в столовую 4 человека. Сколькими способами это можно сде-
лать? Сколько существует способов набрать команду дежурных, в ко-
торую попадет ученик этого класса Коля Васин?
Определение. Пусть M = {a1 , . . . , an } — множество из n элемен-
тов. k-сочетаниями называются наборы (ai1 , . . . , aik ), в которых по-
рядок считается несущественным. То есть два k-сочетания считаются
различными, если они отличаются друг от друга входящими в них эле-
ментами, но не порядком элементов.
Аналогично размещениям сочетания бывают без повторений и с по-
вторениями.
Количества сочетаний без повторений и с повторениями обознача-
ются Ck и Ck соответственно.
n n
2.45. Из двух математиков и десяти экономистов надо составить
комиссию из восьми человек. Сколькими способами можно составить
комиссию, если в нее должен входить хотя бы один математик?
2.46. На плоскости дано n точек. Сколько имеется отрезков с кон-
цами в этих точках?
2.47. На плоскости проведено n прямых «общего положения». Най-
дите количество точек пересечения этих прямых. Сколько треугольни-
ков образуют эти прямые?
18 2. Комбинаторика

2.48. На двух параллельных прямых a и b выбраны точки A1 ,
A2 , . . . , Am и B1 , B2 , . . . , Bn соответственно. Сколько будет точек пе-
ресечения, если провести все отрезки вида Ai Bj (1 i m, 1 j n),
при условии, что никакие три из этих отрезков в одной точке не пере-
секаются?
2.49* . Ключи от сейфа. Международная комиссия состоит из 9
человек. Материалы комиссии хранятся в сейфе. Сколько замков дол-
жен иметь сейф, сколько ключей для них нужно изготовить и как их
разделить между членами комиссии, чтобы доступ к сейфу был возмо-
жен тогда и только тогда, когда соберутся не менее 6 членов комиссии?
Рассмотрите задачу также в том случае, когда комиссия состоит из
n человек, а сейф можно открыть при наличии m членов комиссии
(m n).
2.50. У Нины 7 разных шоколадных конфет, у Коли 9 разных ка-
рамелек. Сколькими способами они могут обменяться друг с другом
пятью конфетами?
2.51. Докажите равенства
(n + k ? 1)!
n!
а) Ck = б) Ck = Ck
; .
n+k?1 =
n n
(n ? k)! k! (n ? 1)! k!
2.52. Докажите, что биномиальный коэффициент Ck можно опре-
n
делить как количество способов выбрать k-элементное подмножество в
множестве из n элементов.
2.53. Бином Ньютона. Докажите справедливость формулы

(x + y)n = C0 xn + C1 xn?1 y + C2 xn?2 y2 + . . . + Cn yn .
n n n n


Числа Ck называются биномиальными коэффициентами, поскольку они
n
возникают при возведении в степень бинома x + y.
2.54. Сколько рациональных слагаемых содержится в разложении
v v v v
а) ( 2 + 4 3)100 ; б) ( 2 + 3 3)300 ?
2.55* . Докажите, что для любого натурального a найдется такое
n
натуральное n, что все числа n + 1, nn + 1, nn + 1, . . . делятся на a.
2.56. Сколько диагоналей имеет выпуклый:
а) 10-угольник; б) k-угольник (k > 3)?
2.57. В выпуклом n-угольнике проведены все диагонали. Они раз-
бивают его на выпуклые многоугольники. Возьмем среди них много-
угольник с самым большим числом сторон. Сколько сторон он может
иметь?
3. Размещения, перестановки и сочетания 19

2.58. Анаграммы. Анаграммой называется произвольное слово,
полученное из данного слова перестановкой букв. Сколько анаграмм
можно составить из слов: а) точка; б) прямая; в) перешеек; г) бис-
сектриса; д) абракадабра; е) комбинаторика?
Некоторые комбинаторные задачи решаются, если условие удается
переформулировать в терминах слов и анаграмм. Примером может слу-
жить следующая задача.
2.59. Шахматный город. Рассмотрим прямоугольную сетку
квадратов размерами m ? n — шахматный город, состоящий из «квар-
талов», разделенных n ? 1 горизонтальными и m ? 1 вертикальными
«улицами». Каково число различных кратчайших путей на этой сетке,
ведущих из левого нижнего угла (точка (0; 0)) в правый верхний угол
(точку (m; n))? (См. также 2.77.)
2.60. Имеется куб размером 10 ? 10 ? 10, состоящий из малень-
ких единичных кубиков. В центре O одного из угловых кубиков сидит
кузнечик. Он может прыгать в центр кубика, имеющего общую грань
с тем, в котором кузнечик находится в данный момент, причем так,
чтобы расстояние до точки O увеличивалось. Сколькими способами
кузнечик может допрыгать до кубика, противоположного исходному?
2.61. Параллелограмм пересекается двумя рядами прямых, парал-
лельных его сторонам; каждый ряд состоит из m прямых. Сколько
параллелограммов можно выделить в образовавшейся сетке?
2.62. Сколькими способами можно разделить на команды по 6 че-
ловек для игры в волейбол группу:
а) из 12; б) из 24 спортсменов?
2.63. Имеется множество C, состоящее из n элементов. Сколькими
способами можно выбрать в C два подмножества A и B так, чтобы
а) множества A и B не пересекались;
б) множество A содержалось бы в множестве B?
2.64. Полиномиальная теорема. Докажите, что в равенстве

C(k1 , . . . , km )xk1 . . . xkm
(x1 + . . . + xm )n = 1 m
k1 +...+km =n


коэффициенты C(k1 , . . . , km ) могут быть найдены по формуле
n!
C(k1 , . . . , km ) = .
k1 ! · . . . · km !

Числа C(k1 , . . . , km ) называются полиномиальными коэффициентами.
20 2. Комбинаторика

2.65. При игре в преферанс каждому из трех игроков раздают по
10 карт, а две карты кладут в прикуп. Сколько различных раскла-
дов возможно в этой игре? (Считаются возможные раздачи без учета
того, что каждые 10 карт достаются конкретному игроку.) (См. так-
же 2.95.)
2.66. Сколько существует 6-значных чисел, у которых каждая по-
следующая цифра меньше предыдущей?
2.67. Имеется m белых и n черных шаров, причем m > n. Сколь-
кими способами можно все шары разложить в ряд так, чтобы никакие
два черных шара не лежали рядом? (См. также 3.129, 11.84.)
2.68. Шесть ящиков занумерованы числами от 1 до 6. Сколькими
способами можно разложить по этим ящикам 20 одинаковых шаров так,
чтобы ни один ящик не оказался пустым?
Сколькими способами можно разложить n одинаковых шаров по
m (n > m) пронумерованным ящикам так, чтобы ни один ящик не
оказался пустым?
2.69. Шесть ящиков занумерованы числами от 1 до 6. Сколькими
способами можно разложить по этим ящикам 20 одинаковых шаров (на
этот раз некоторые ящики могут оказаться пустыми)?
2.70. Сколько решений имеет уравнение

x1 + x2 + x3 = 1000

а) в натуральных; б) в целых неотрицательных числах?
(См. также 11.67.)
2.71. Сколькими способами можно составить букет из 17 цветков,
если в продаже имеются гвоздики, розы, гладиолусы, ирисы, тюльпаны
и васильки?
Определение. Биномиальные коэффициенты удобно располагать
в виде таблицы, которая называется треугольником Паскаля

C0 1
0
C0 C1 1 1
1 1
C0 C1 C2 1 2 1
2 2 2
C0 C1 C2 C3 1 3 3 1
3 3 3 3
... ... ... ... ... ... ... ... ... ... ... ... ... ...

Он обладает самыми разнообразными свойствами (см. задачи 2.76,
2.77).
3. Размещения, перестановки и сочетания 21

2.72. Почему равенства 112 = 121 и 113 = 1331 похожи на строчки
треугольника Паскаля? Чему равно 114 ?
2.73. Сколькими способами двигаясь по следующей таблице от бук-
вы к букве
к
в в
а а а
д д д д
р р р р р
а а а а а а
т т т т т т т

можно прочитать слово «квадрат»?
2.74. Придумайте какой-нибудь способ достроить треугольник Пас-
каля вверх.
2.75. При каких значениях n все коэффициенты в разложении би-
нома Ньютона (a + b)n нечетны?
2.76. Вычислите суммы:
а) C0 + 2C1 + 22 C2 + . . . + 25 C5 ;
5 5 5 5
б) C0 ? C1 + . . . + (?1)n Cn ;
n n n
0 1 n
в) Cn + Cn + . . . + Cn .
2.77. Докажите тождества:
а) Cm Ck = Ck Cm?k ;
r r?k
r m
m+1 m m+1
б) Cn+1 = Cn + Cn ;
в) Cn = (C0 )2 + (C1 )2 + . . . + (Cn )2 ;
2n n n n
г) Ck = C0 Ck + C1 Ck?1 + . . . + Ck C0 ;
n+m nm nm nm
д) Ck = Ck?1 + Ck?1 + . . . + Ck?1 .
n?1 n?2 k?1
n
Попробуйте доказать эти тождества тремя разными способами:
пользуясь тем, что Ck — это количество k-элементных подмножеств в
n
множестве из n элементов; исходя из того, что Ck — это коэффициент
n
k n
при x у многочлена (1 + x) ; пользуясь «шахматным городом» из
задачи 2.59.
2.78. Свойство шестиугольника. Докажите равенство

Ck?1 · Ck+1 · Ck = Ck · Ck+1 · Ck?1 .
n?1 n n+1 n?1 n+1 n


2.79. 120 одинаковых шаров плотно уложены в виде правильной
треугольной пирамиды. Сколько шаров лежит в основании?
2.80. В разложении (x + y)n по формуле бинома Ньютона второй
член оказался равен 240, третий — 720, а четвертый — 1080. Найдите x,
y и n.
22 2. Комбинаторика

2.81. Биномиальная система счисления. Покажите, что любое
целое неотрицательное число n может быть представлено в виде
n = C1 + C2 + C3 ,
x y z

где x, y, z — целые числа такие, что 0 x < y < z.
2.82. В компании из 10 человек произошло 14 попарных ссор. До-
кажите, что все равно можно составить компанию из трех друзей.
2.83. Найдите m и n зная, что
Cm+1 : Cm : Cm?1 = 5 : 5 : 3.
n+1 n+1 n+1
v
2.84. Какое слагаемое в разложении (1 + 3)100 по формуле бинома
Ньютона будет наибольшим?
2.85. Сколько четырехзначных чисел можно составить, используя
цифры 1, 2, 3, 4 и 5, если:
а) никакая цифра не повторяется более одного раза;
б) повторения цифр допустимы;
в) числа должны быть нечетными и повторений цифр быть не долж-
но?
2.86. Сколько существует различных возможностей рассадить 5
юношей и 5 девушек за круглый стол с 10-ю креслами так, чтобы они
чередовались?
2.87* . В выпуклом n-угольнике проведены все диагонали. Известно,
что никакие три из них не пересекаются в одной точке. На сколько
частей разделится при этом многоугольник? Во скольких точках пере-
секутся диагонали?
2.88. Гармонический треугольник Лейбница.
1
1
1 1
2 2
1 1 1
3 6 3
1 1 1 1
4 12 12 4
1 1 1 1 1
5 20 30 20 5
1 1 1 1 1 1
6 30 60 60 30 6
Здесь изображен фрагмент таблицы, которая называется треуголь-
ником Лейбница. Его свойства «аналогичны в смысле противополож-
ности» свойствам треугольника Паскаля. Числа на границе треуголь-
ника обратны последовательным натуральным числам. Каждое число
4. Формула включений и исключений 23

внутри равно сумме двух чисел, стоящих под ним. Найдите формулу,
которая связывает числа из треугольников Паскаля и Лейбница.
2.89. Докажите равенства:
1 1 1 1 1 1
а) + ...;
=++ + +
1 2 6 12 20 30
1 1 1 1 1 1
б) = + + ...;
+ + +
2 3 12 30 60 105
1 1 1 1 1 1
в) = + + + + + ...
3 4 20 60 140 280
2.90. Найдите сумму
1 1 1 1
+ + + + ...
12 30 60 105
и обобщите полученный результат.
2.91. Найдите суммы рядов
1 1 1 1
а) + ...;
+ + +
1·2 2·3 3·4 4·5
1 1 1 1
б) + ...;
+ + +
1·2·3 2·3·4 3·4·5 4·5·6
0! 1! 2! 3!
в) + . . . (r
+ + + 2).
r! (r ? 1)! (r ? 2)! (r ? 3)!
Определение. Вероятностью наступления какого-либо события
называется отношение числа благоприятных исходов к числу всех воз-
можных исходов, предполагаемых равновероятными. (См. [8].)
2.92. В ящике имеется 10 белых и 15 черных шаров. Из ящика
вынимаются 4 шара. Какова вероятность того, что все вынутые шары
будут белыми?
2.93. Пишется наудачу некоторое двузначное число. Какова вероят-
ность того, что сумма цифр этого числа равна 5?
2.94. Имеется три ящика, в каждом из которых лежат шары с номе-
рами от 0 до 9. Из каждого ящика вынимается по одному шару. Какова
вероятность того, что
а) вынуты три единицы; б) вынуты три равных числа?
2.95. У игрока в преферанс оказалось 4 козыря, а еще 4 находятся
на руках у двух его противников. Какова вероятность того, что козыри
лягут а) 2 : 2; б) 3 : 1; в) 4 : 0? (См. также 2.65.)

4. Формула включений и исключений
2.96. Зоопарки. Во всех зоопарках, где есть гиппопотамы и носоро-
ги, нет жирафов. Во всех зоопарках, где есть носороги и нет жирафов,
24 2. Комбинаторика

есть гиппопотамы. Наконец, во всех зоопарках, где есть гиппопотамы
и жирафы, есть и носороги. Может ли существовать такой зоопарк, в
котором есть гиппопотамы, но нет ни жирафов, ни носорогов?
2.97. Двоечники. В классе имеется a1 учеников, получивших в
течение года хотя бы одну двойку, a2 учеников, получивших не менее
двух двоек, и т. д., ak учеников, получивших не менее k двоек. Сколько
всего двоек в этом классе? (Предполагается, что ни у кого нет более k
двоек.)
2.98. Пусть имеется n подмножеств A1 , . . . , An конечного множества
E и ?j (x) — характеристические функции этих множеств, то есть

x ? Aj ,
1,
(j = 1, . . . , n).
?j (x) =
x ? E \ Aj
0,

Докажите, что при этом ?(x) — характеристическая функция множе-
ства A = A1 ? . . . ? An , связана с функциями ?1 (x), . . . , ?n (x) формулой
1 ? ?(x) = (1 ? ?1 (x)) . . . (1 ? ?n (x)).
2.99. Формула включений и исключений. Докажите справед-
ливость равенства
|A1 ? A2 ? . . . ? An | = |A1 | + . . . + |An | ? |A1 ? A2 | ?
? |A1 ? A3 | ? . . . ? |An?1 ? An | + . . . + (?1)n?1 |A1 ? A2 ? . . . ? An |,
где через |A| обозначено количество элементов множества A. (См. также
4.138.)
2.100. Из 100 студентов университета английский язык знают 28
студентов, немецкий — 30, французский — 42, английский и немец-
кий — 8, английский и французский — 10, немецкий и французский — 5,
все три языка знают 3 студента. Сколько студентов не знают ни одного
из трех языков?
2.101. Каждая сторона в треугольнике ABC разделена на 8 равных
отрезков. Сколько существует различных треугольников с вершинами
в точках деления (точки A, B, C не могут быть вершинами треуголь-
ников), у которых ни одна сторона не параллельна ни одной из сторон
треугольника ABC?
2.102. Сколько существует целых чисел от 1 до 16 500, которые
а) не делятся на 5;
б) не делятся ни на 5 ни на 3;
в) не делятся ни на 5 ни на 3, ни на 11?
5. Числа Каталана 25

2.103. Сколько существует целых чисел от 1 до 33 000, которые не
делятся ни на 3 ни на 5, но делятся на 11?
2.104. Сколько существует целых чисел от 1 до 1 000 000, которые
не являются ни полным квадратом, ни полным кубом, ни четвертой
степенью?
2.105. Беспорядки. В классе 30 учеников. Сколькими способами
они могут пересесть так, чтобы ни один не сел на свое место?
2.106. Сколькими способами можно расселить 15 гостей в четырех
комнатах, если требуется чтобы ни одна из комнат не осталась пустой?
2.107. В комнате площадью 6 м2 постелили три ковра произвольной
формы площадью 3 м2 каждый. Докажите, что какие-либо два из них
перекрываются по площади, не меньшей 1 м2 .
2.108. В прямоугольнике площади 5 расположено 9 фигур площа-
ди 1 каждая. Докажите, что найдутся две фигуры, площадь общей
части которых не меньше 1/9.
2.109* . В прямоугольнике площади 1 расположено 5 фигур площа-
ди 1/2 каждая.
а) Докажите, что найдутся два фигуры, площадь общей части кото-
рых не меньше 3/20.
б) Докажите, что найдутся две фигуры, площадь общей части кото-
рых не меньше 1/5.
в) Докажите, что найдутся три фигур, площадь общей части кото-
рых не меньше 1/20.
2.110. Докажите, что в условии задач 2.109 б) и в) числа 1/5 и 1/20
нельзя заменить большими величинами.

5. Числа Каталана
Во многих комбинаторных задачах решением является последова-
тельность чисел Каталана
{Cn } = {C0 , C1 , C2 , . . . } = {1, 1, 2, 5, 14, 42, . . . }.
Определение. Пусть имеется n + 1 переменная x0 , x1 , . . . , xn , и
мы хотим вычислить их произведение при помощи n умножений. Опре-
делим число Cn как количество способов расставить скобки в произ-
ведении x0 · x1 · . . . · xn так, чтобы порядок умножений был полностью
определен. Например, при n = 2 существует два способа: x0 · (x1 · x2 ),
(x0 · x1 ) · x2 , а при n = 3 уже 5:
x0 · (x1 · (x2 · x3 )), x0 · ((x1 · x2 ) · x3 ), (x0 · x1 ) · (x2 · x3 ),
(x0 · (x1 · x2 )) · x3 , ((x0 · x1 ) · x2 ) · x3 .
26 2. Комбинаторика

2.111. Сколько последовательностей {a1 , a2 , . . . , a2n }, состоящих из
+ 1 и ? 1, обладают тем свойством, что a1 + a2 + . . . + a2n = 0, а все их
частичные суммы
a1 , a1 + a2 , ..., a1 + a2 + . . . + a2n
неотрицательны?
2.112. Сколько существует способов разрезать выпуклый (n + 2)-
угольник диагоналями на треугольники?
2.113. Маршруты ладьи. Рассмотрим шахматные доски со сто-
ронами 2, 3, 4, . . . Требуется провести ладью из левого нижнего угла
в правый верхний. Двигаться можно только вверх и вправо, не заходя
при этом на клетки главной диагонали и ниже нее. (Ладья оказывает-
ся на главной диагонали только в начальный и в конечный моменты
времени.) Сколько существует таких маршрутов?
2.114. Очередь в кассу. Билеты стоят 50 центов, и 2n покупателей
стоят в очереди в кассу. Половина из них имеет по одному доллару,
остальные — по 50 центов. Кассир начинает продажу билетов, не имея
денег. Сколько существует различных порядков в очереди, таких, что
кассир всегда может дать сдачу?
2.115. Формула для чисел Каталана. Пусть {a1 , a2 , . . . , an } —
последовательность целых чисел, сумма которых равна + 1. Докажите,
что ровно у одного из ее циклических сдвигов
{a1 , a2 , . . . , an }, {a2 , . . . , an , a1 }, {an , , a1 . . . , an?1 },
...,
все частичные суммы положительны. Выведите отсюда равенства:
(4n ? 2)!!!!
1 1
Cn = Cn = Cn = ,
2n+1 2n
2n + 1 n+1 (n + 1)!

где (4n ? 2)!!!! = 2 · 6 · 10 . . . (4n ? 2) — произведение, в котором участвует
каждое четвертое число. (См. также 3.105.)
2.116. Рекуррентное соотношение для чисел Каталана. Дока-
жите, что числа Каталана удовлетворяют рекуррентному соотношению
Cn = C0 Cn?1 + C1 Cn?2 + . . . + Cn?1 C0 .
(См. также 11.92.)
Глава 3
Алгоритм Евклида
и основная теорема арифметики

1. Простые числа
Определение. Натуральное число p называется простым, если
p > 1 и p не имеет положительных делителей, отличных от 1 и p.
По соглашению, 1 не является простым числом. Остальные числа,
имеющие три и более делителей, называются составными.
3.1. Теорема Евклида. Докажите, что простых чисел бесконечно
много.
3.2. Найдите все простые числа, которые отличаются на 17.
3.3. Докажите, что остаток от деления простого числа на 30 — про-
стое число.
3.4. Пусть n > 2. Докажите, что между n и n! есть по крайней мере
одно простое число.
3.5. Найдите все такие простые числа p и q, для которых выполня-
ется равенство p2 ? 2q2 = 1.
3.6. Докажите, что если число n! + 1 делится на n + 1, то n + 1 —
простое число.
3.7. Докажите, что множество простых чисел вида p = 4k + 3 бес-
конечно. (См. также 4.127.)
3.8. Докажите, что множество простых чисел вида p = 6k + 5 бес-
конечно. (См. также 4.128.)
3.9. Докажите, что составное число n всегда имеет делитель
v
d n.
3.10. Когда натуральное число n имеет нечетное количество дели-
телей?
3.11. Разложите на простые множители числа 111, 1111, 11111,
111111, 1111111. (См. также 4.25.)
28 3. Алгоритм Евклида и основная теорема арифметики

3.12. Докажите, что существуют 1000 подряд идущих составных
чисел.
3.13. Докажите, что для любого натурального n найдутся n подряд
идущих натуральных чисел, среди которых ровно одно простое.
3.14. Существуют ли а) 5; б) 6 простых чисел, образующих ариф-
метическую прогрессию?
3.15. Существуют ли арифметическая прогрессия, состоящая лишь
из простых чисел?
3.16. Предположим, что нашлись 15 простых чисел, образующих
арифметическую прогрессию с разностью d. Докажите, что d > 30000.
Определение. Два простых числа, отличающиеся на 2 называются
простыми числами-близнецами.
3.17. Докажите, что 3, 5 и 7 являются единственной тройкой про-
стых чисел-близнецов.
3.18. Найдите все простые числа, которые равны сумме двух про-
стых чисел и разности двух простых чисел.
3.19. Докажите, что при n > 2 числа 2n ? 1 и 2n + 1 не могут быть
простыми одновременно.
3.20. При каких целых n число n4 + 4 — составное?
3.21. Верно ли, что многочлен P(n) = n2 + n + 41 при всех n
принимает только простые значения?
3.22. Пусть {pn } — последовательность простых чисел (p1 = 2, p2 = 3,
p3 = 5, . . . ). Докажите, что pn > 2n при n 5. При каких n будет
выполняться неравенство pn > 3n?
3.23. Докажите неравенство pn+1 < p1 p2 . . . pn .
3.24. Верно ли, что все числа вида p1 p2 . . . pn + 1 являются прос-
тыми?
3.25. Числа Евклида. Евклидово доказательство бесконечности
множества простых чисел наводит на мысль определить рекуррентно
числа Евклида:
en = e1 e2 . . . en?1 + 1 (n
e1 = 2, 2).
Все ли числа en являются простыми? (См. также 4.79.)
3.26. Числа Ферма. Докажите, что если число an + 1 простое, то
. k
.
a . 2 и n = 2k . (Простые числа вида fk = 22 + 1 называются числами
Ферма.
2. Алгоритм Евклида 29

3.27. Докажите, что fn делит 2fn ? 2.
3.28. Докажите, что числа Ферма fn при n > 1 не представимы в
виде суммы двух простых чисел.
3.29. Числа Мерсенна. Докажите, что если число an ? 1 простое,
то a = 2 и n — простое.
Простые числа вида q = 2p ? 1 называются числами Мерсенна.
3.30. Пусть Pn (x) = an xn +. . .+a1 x+a0 — многочлен с целыми коэф-
фициентами (n 1, an = 0). Может ли быть так, что при x = 0, 1, 2, . . .
все числа Pn (x) — простые?

2. Алгоритм Евклида
Определение. Наибольшим общим делителем (НОД) целых чи-
сел a1 , . . . , an называется такой положительный общий делитель
a1 , . . . , an , который делится на любой другой общий делитель этих
чисел. НОД чисел a1 , . . . , an обозначается (a1 , . . . , an ).
Если наибольший общий делитель чисел a1 , . . . , an равен 1, то эти
числа называются взаимно простыми.
3.31. Докажите, что если в наборе целых чисел a1 , . . . , an хотя бы
одно отлично от 0, то они имеют наибольший общий делитель.
3.32. В прямоугольнике с целыми сторонами m и n, нарисованном
на клетчатой бумаге, проведена диагональ. Через какое число узлов она
проходит? На сколько частей эта диагональ делится линиями сетки?
3.33. Натуральные числа p и q взаимно просты. Отрезок [0; 1] раз-
бит на p + q одинаковых отрезков. Докажите, что в каждом из этих
отрезков, кроме двух крайних лежит ровно одно из p + q ? 2 чисел
1 2 p?1 1 2 q?1
, , ..., , , , ..., .
p p p q q q

3.34. С 1 сентября четыре школьника начали посещать кинотеатр.
Первый бывал в нем каждый четвертый день, второй — каждый пятый,
третий — каждый шестой и четвертый — каждый девятый. Когда второй
раз все школьники встретятся в кинотеатре?
3.35. В задаче 1.1 доказана возможность деления с остатком про-
извольного целого числа a на натуральное число b. Докажите, что из
равенства a = bq + r следует соотношение (a, b) = (b, r).
3.36. Алгоритм Евклида. Пусть m0 и m1 — целые числа, m1 > 0
и m1 m0 . Докажите, что при некотором k > 1 существуют целые числа
30 3. Алгоритм Евклида и основная теорема арифметики

a0 , a1 , . . . , ak?1 и m2 , . . . , mk такие, что m1 > m2 > m3 > . . . > mk > 0,
ak > 1, ?
? m0 = m1 · a0 + m2 ,
?
?
? m =m ·a +m ,
?
?
? 1 2 1 3
?
? m =m ·a +m ,
2 3 2 4

?
? ..............
?
?
?m
? k?2 = mk?1 · ak?1 + mk ,
?
?
?
mk?1 = mk · ak ,
и (m0 , m1 ) = mk .
3.37. Докажите, что для любого s от k ? 1 до 0 существуют чис-
ла us , vs такие, что us ms + ms+1 vs = d, где d = (m0 , m1 ). В частности,
для некоторых u и v выполняется равенство:
m0 u + m1 v = d.
(См. также 6.67.)
3.38. Пусть (a, b) = 1 и a | bc. Докажите, что a | c.
3.39. Найдите (1 . . . 1, 1 . . . 1).
m n
3.40. Какое наибольшее значение может принимать наибольший об-
щий делитель чисел a и b, если известно, что a · b = 600?
3.41. Натуральные числа a1 , a2 , . . . , a49 удовлетворяют равенству
a1 + a2 + . . . + a49 = 540.
Какое наибольшее значение может принимать их наибольший общий
делитель?
3.42. Можно ли с помощью циркуля и линейки разделить угол 19?
на 19 равных частей?
3.43. Числа от 1 до 1000 выписаны подряд по кругу. Начиная с
первого, вычеркивается каждое 15-е число: 1, 15, 31, . . . , причем при
повторных оборотах, зачеркнутые числа считаются снова. Число обо-
ротов не ограничено. Сколько чисел останутся незачеркнутыми?
3.44. Докажите, что (5a + 3b, 13a + 8b) = (a, b).
3.45. Может ли наибольший общий делитель двух натуральных чи-
сел быть больше их разности?
3.46. Докажите, что для нечетных чисел a, b и c имеет место ра-
венство
b+c a+c a+b
, , = (a, b, c).
2 2 2
2. Алгоритм Евклида 31

3.47. По окружности радиуса 40 катится колесо радиуса 18. В ко-
лесо вбит гвоздь, который ударяясь об окружность, оставляет на ней
отметки. Сколько всего таких отметок оставит гвоздь на окружности?
Сколько раз прокатится колесо по всей окружности, прежде чем гвоздь
попадет в уже отмеченную ранее точку?
3.48. Для некоторых целых x и y число 3x + 2y делится на 23.
Докажите, что число 17x + 19y также делится на 23.
3.49. Докажите, что следующие дроби несократимы при всех нату-
ральных значениях n:
2n2 ? 1 n2 ? n + 1
2n + 13
а) ; б) ; в) .
n2 + 1
n+7 n+1
3.50. При каких целых n сократимы дроби
n2 + 2n + 4 n3 ? n2 ? 3n
а) ; б) ?
n2 + n + 3 n2 ? n + 3
3.51. При каких целых n число
n4 + 1 n3 + n + 1
а) ; б)
n2 + n + 1 n2 ? n + 1
также будет целым?
3.52. Найдите все натуральные n > 1 для которых n3 ? 3 делится
на n ? 1.
3m ? n
3.53. На какие натуральные числа можно сократить дробь ,
5n + 2m
если известно, что она сократима и что числа m и n взаимно просты.
3.54. Докажите, что при m = n выполняются равенства:
а) (am ? 1, an ? 1) = a(m,n) ? 1 (a > 1); б) (fn , fm ) = 1,
k
где fk = 22 + 1 — числа Ферма. (См. также 3.39, 3.122, 6.69.)
n
3.55. Докажите, что число 22 ? 1 имеет по крайней мере n различ-
ных простых делителей.
3.56. Докажите, что для простых чисел выполняется неравенство
n
pn+1 22 + 1.
3.57. Докажите, что равенство (a, mn) = 1 равносильно выполне-
нию двух условий (a, m) = 1 и (a, n) = 1.
3.58. Докажите, что если (a, b) = 1, то (2a + b, a(a + b)) = 1.
3.59. Докажите, что если (a, b) = 1, то наибольший общий делитель
чисел a + b и a2 + b2 равен 1 или 2.
3.60. Пусть a и b — натуральные числа. Докажите, что среди чи-
сел a, 2a, 3a, . . . , ba ровно (a, b) чисел делится на b.
32 3. Алгоритм Евклида и основная теорема арифметики

3.61. Пусть (a, b) = 1 и (x0 , y0 ) — некоторое целочисленное решение
уравнения ax + by = 1. Докажите, что все решения этого уравнения в
целых числах получаются по формулам x = x0 + kb, y = y0 ? ka, где
k — произвольное целое число.
3.62. Как описать все решения в целых числах уравнения ax+by = c
при произвольных a, b, c?
3.63. Решите в целых числах уравнения (укажите все решения):
а) 45x ? 37y = 25; г) 109x + 89y = 1;
б) 19x + 95y = 1995; д) 43x + 13y = 21;
в) 10x + 2y + 18z = 7; е) 34x ? 21y = 1.
3.64. Докажите, что число шагов в алгоритме Евклида может быть
сколь угодно большим.
3.65. Существует ли в сутках момент, когда расположенные на об-
щей оси часовая, минутная и секундная стрелки правильно идущих
часов образуют попарно углы в 120? ?
3.66. Найдите все взаимно простые a и b, для которых
a+b 3
=.
2 2 13
a ? ab + b
3.67. Докажите, что если (a1 , a2 , . . . , an ) = 1, то уравнение
a1 x1 + a2 x2 + . . . + an xn = 1
разрешимо в целых числах.
Определение. Пусть a1 , . . . , an — отличные от 0 целые числа. Наи-
меньшим общим кратным (НОК) этих чисел называется наименьшее
положительное число, кратное всем этим числам. НОК чисел a1 , . . .
. . . , an обозначается [a1 , . . . , an ].
3.68. Докажите равенства
а) [1, 2, . . . , 2n] = [n, n + 1, . . . , 2n];
б) (a1 , a2 , . . . , an ) = (a1 , (a2 , . . . , an ));
в) [a1 , a2 , . . . , an ] = [a1 , [a2 , . . . , an ]].
3.69. На доске написано n натуральных чисел. За одну операцию
вместо двух чисел, не делящих друг друга, можно написать их наи-
больший общий делитель и их наименьшее общее кратное.
а) Докажите, что можно провести только конечное число операций.
б) Финальный результат независимо от порядка действий будет од-
ним и тем же. Например:
(4, 6, 9) > (2, 12, 9) > (2, 3, 36) > (1, 6, 36),
(4, 6, 9) > (4, 3, 18) > (1, 12, 18) > (1, 6, 36).
3. Мультипликативные функции 33

3.70. Найдите наименьшее c, при котором
а) уравнение 7x + 9y = c имело бы ровно 6 целых положительных
решений;
б) уравнение 14x + 11y = c имело бы ровно 5 целых положительных
решений.
3.71. В каких пределах должно заключаться c, чтобы уравнение
19x + 14y = c имело бы 6 целых положительных решений?
3.72. Пусть a и b — натуральные взаимно простые числа. Рассмот-
рим точки плоскости с целыми координатами (x, y), лежащие в полосе
b ? 1. Каждой такой точке припишем целое число N(x, y) =
0 x
= ax + by.
а) Докажите, что для каждого натурального c существует ровно
одна точка (x, y) (0 x b ? 1), что c = N(x, y).
б) Теорема Сильвестра. Докажите, что наибольшее c, для кото-
рого уравнение ax + by = c не имеет решений в целых неотрицательных
числах, имеет вид c = ab ? a ? b.
3.73* . Пусть числа a и b взаимно просты. Докажите, что для того,
чтобы уравнение ax + by = c имело ровно n целых положительных
решений, значение c должно находиться в пределах

(n ? 1)ab + a + b c (n + 1)ab ? a ? b.

(См. также 1.48.)
3.74* . Отметим на прямой красным цветом все точки вида 81x +
+ 100y, где x, y — натуральные, и синим цветом — остальные целые
точки. Найдите на прямой такую точку, что любые симметричные от-
носительно нее целые точки закрашены в разные цвета. Объясните,
почему такая точка существует.

3. Мультипликативные функции
Основная теорема арифметики. Всякое натуральное число,
большее 1, раскладывается и только одним способом (с точностью до
порядка сомножителей) в произведение простых чисел.
3.75. Докажите основную теорему арифметики при помощи утвер-
ждения из задачи 3.38.
3.76. Найдите все двузначные числа, квадрат которых равен кубу
суммы их цифр.
3.77. На какое количество нулей заканчивается число 100! ?
34 3. Алгоритм Евклида и основная теорема арифметики

3.78. Найдите наименьшее натуральное n, для которого 1999! не
делится на 34n .
3.79. Докажите, что произведение чисел от n+1 до 2n делится на 2n ,
но не делится на 2n+1 .
3.80. Пусть a = p?1 · . . . · p?s , b = p?1 · . . . · p?s , где p1 , . . . , ps —
1 1
s s
простые, и ?1 , . . . , ?s , ?1 , . . . , ?s 0. Докажите равенства:
а) (a, b) = pmin(?1 ,?1 ) · . . . · pmin(?s ,?s ) ;
1 s
б) [a, b] = pmax(?1 ,?1 ) · . . . · pmax(?s ,?s ) ;
1 s
в) (a, b)[a, b] = ab.
3.81. Докажите равенства:
а) [a, (a, b)] = a; в) abc = [a, b, c](ab, ac, bc);
б) (a, [a, b]) = a; г) abc = (a, b, c)[ab, bc, ac].
3.82. Докажите, что (bc, ac, ab) . (a, b, c)2 .
.
.
3.83. Приведите пример, когда равенство (a, b, c)[a, b, c] = abc не
выполнено. Каким неравенством всегда будут связаны числа (a, b, c) ?
? [a, b, c] и abc?
3.84. Сколько различных делителей имеют числа
а) 2 · 3 · 5 · 7 · 11; б) 22 · 33 · 55 · 77 · 1111 ?
3.85. Для каждого k от 1 до 6 найдите наименьшее натуральное
число, которое имеет ровно k различных делителей.
3.86. Пусть ?(n) — количество положительных делителей натураль-
ного числа n = p?1 · . . . · p?s , а ?(n) — их сумма. Докажите равенства:
1 s
? +1
p?s +1 ? 1
p1 1 ? 1
·...· s
а) ?(n) = (?1 + 1) · . . . · (?s + 1); б) ?(n) = .
p1 ? 1 ps ? 1
3.87. Найдите натуральное число n, зная, что оно имеет два простых
делителя и удовлетворяет условиям ?(n) = 6, ?(n) = 28.
3.88. Некоторое натуральное число n имеет два простых делителя.
Его квадрат имеет а) 15; б) 81 делителей. Сколько делителей имеет
куб этого числа?
3.89. Найдите натуральное число вида n = 2x · 3y · 5z , зная, что
половина его имеет на 30 делителей меньше, треть — на 35 и пятая
часть — на 42 делителя меньше, чем само число.
Определение. Функция f(n), определенная на множестве нату-
ральных чисел называется мультипликативной, если она удовлетво-
ряет двум условиям:
1) f(1) = 1; 2) f(m · n) = f(m) · f(n) при (m, n) = 1.
3. Мультипликативные функции 35

Если f(1) = 1 и равенство f(m · n) = f(m) · f(n) выполнено для
всех пар натуральных чисел m и n, то функция f(n) называется вполне
мультипликативной.
3.90. Докажите мультипликативность функций ?(n) и ?(n).
v
3.91. Докажите неравенство ?(n) 2 n.
3.92. Пусть у двух целых положительных чисел равны суммы дели-
телей и равны суммы всех обратных величин к делителям. Докажите,
что эти числа равны.
3.93. Пусть (m, n) > 1. Что больше ?(m · n) или ?(m) · ?(n)? Иссле-
дуйте тот же вопрос для функции ?(n). (См. также 4.144.)
Определение. Число n называется совершенным, если ?(n) = 2n.
Например, числа 6 и 28 — совершенные:
1 + 2 + 3 + 6 = 2 · 6, 1 + 2 + 4 + 7 + 14 + 28 = 2 · 28.
3.94. Совершенные числа. Докажите, что если 2k ? 1 = p —
некоторое простое число Мерсенна, то n = 2k?1 (2k ? 1) — совершенное
число.
3.95* . Теорема Эйлера. Докажите, что если n — четное совершен-
ное число, то оно имеет вид n = 2k?1 (2k ? 1), и p = 2k ? 1 — простое
число Мерсенна.
Проблема существования нечетных совершенных чисел остается сре-
ди трудных и нерешенных задач теории чисел.
Определение. Числа m и n называются дружественными, если
сумма собственных делителей числа m равна n и, наоборот, сумма
собственных делителей числа n равна m. Другими словами, числа m и
n являются дружественными, если
?(m) ? m = n, ?(n) ? n = m,
или
?(m) = m + n = ?(n).
3.96. Дружественные числа. Докажите, что если все три числа
p = 3 · 2k?1 ? 1, q = 3 · 2k ? 1 и r = 9 · 22k?1 ? 1 — простые, то числа
m = 2k · p · q и n = 2k · r — дружественные. Постройте примеры друже-
ственных чисел.
3.97. Может ли быть так, что
а) ?(n) > 3n; б)* ?(n) > 100n?
3.98. Задача Ферма. Найдите наименьшее число вида n = 2? p1 p2 ,
где p1 и p2 — некоторые простые числа, такое, что ?(n) = 3n.
36 3. Алгоритм Евклида и основная теорема арифметики

3.99. Пусть ? — действительное положительное число, d — натураль-
ное. Докажите, что количество натуральных чисел, не превосходящих
?
? и делящихся на d, равно .
d
3.100. Докажите, что для действительного положительного ? и на-
[?]
?
турального d всегда выполнено равенство .
=
d d
3.101. Формула Лежандра. Число n! разложено в произведение
простых чисел n! = p?1 . . . p?s . Докажите равенство
1 s

n n n
?k = + 2 + 3 + ...
pk pk pk
3.102. Докажите, что число p входит в разложение n! с показателем,
n
не превосходящим .
p?1
3.103. Пусть представление числа n в двоичной системе выглядит
следующим образом:
n = 2e1 + 2e2 + . . . + 2er (e1 > e2 > . . . > er 0).

стр. 1
(всего 9)

СОДЕРЖАНИЕ

>>