alfutova(алгебра и теория чисел). Сборник задач для математических школ м мцнмо, 2002. 264 с Настоящее пособие представляет собой сборник задач по математике

• Название: Сборник задач для математических школ м мцнмо, 2002. 264 с Настоящее пособие представляет собой сборник задач по математике
• Дата: 27.01.2020
• Размер: 2 Mb.
• Имя файла: alfutova(алгебра и теория чисел).pdf
• Тип: Сборник задач; #106051
• страница: 1 из 23

Алгебра и теория чисел для математических школ
Н. Б. Алфутова, А. В. Устинов
September 3, 2003

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

Предисловие
Настоящее пособие представляет собой сборник задач по математике, предназначенный прежде всего для учеников старших классов, интересующихся точными науками. Он также будет полезен преподавателям математики и студентам, изучающим математику в высших учебных заведениях. Значительная часть материала может быть использована для подготовки к письменными устным вступительным экзаменам в
ВУЗы.
Основу сборника составляют задачи к курсу алгебры, который в – 2000 годах читался О. А. Чалых, Н. Б. Алфутовой и А. В. Усти- новым. В приложении
А
приведена программа этого курса. Для того,
чтобы сделать содержание книги более широкими целостным, авторы включили в нее дополнительный материал, собрав и упорядочив задачи из других источников.
Математические курсы, читаемые в школе-интернате им. АН. Колмогорова, традиционно содержат разделы, которые можно назвать смежными. Они находятся на стыке алгебры с комбинаторикой, геометрией, теорией чисел и математическим анализом. Поэтому некоторые задачи из книги имеют к алгебре лишь косвенное отношение. Эти задачи призваны подчеркнуть связь различных разделов математики и проиллюстрировать многообразие методов.
В каждой главе кратко излагается теоретический материал, необходимый для понимания задач. В конце задачи иногда даются ссылки на задачи или литературу, которые непосредственно связаны сданным материалом.
При подготовке пособия использовались различные учебники и монографии, сборники олимпиадных и конкурсных задач, большая часть упражнений была почерпнута из многочисленных публикаций журнала
«Квант». В результате работы над книгой был создан своеобразный путеводитель, помещенный в приложение
Б
. В нем по каждой из тем задачника даны ссылки на соответствующие публикации. К сожалению,
в настоящий момент не представляется возможным указать авторов всех задач, вошедших в книгу, и перечислить все оригинальные источники. Часть материала встречается сразу в нескольких сборниках. Со

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

Обозначения
В списке указаны страницы, на которых введены эти обозначения.
Обозначение
Смысл
Стр.
N
множество натуральных чисел
Z
множество целых чисел
Q
множество рациональных чисел
70
[x]
целая часть числа x (наибольшее целое, не превосходящее дробная часть числа x:
{x} = x − факториал n! = 1 · 2 · . . . · n
7
{x последовательность x
1
, x
2
, . . . , x n
, . . .
b
| a делит a
8
a ... b кратно b
8
a
≡ b mod m сравнимо с b по модулю m
53
¯
a класс вычетов по модулю m
53
(a k
. . . a
0
)
q запись числа в q-ичной системе счисления, . . . , a наибольший общий делитель чисел a
1
, . . . , a n
29
[a
1
, . . . , a наименьшее общее кратное чисел a
1
, . . . , a n
32
[a
0
; a
1
, . . . , a цепная дробь
42
ϕ(n)
функция Эйлера
60
τ(n)
количество положительных делителей числа сумма положительных делителей числа n
34
F
n числа Фибоначчи мнимая единица i =
√
−1 множество комплексных чисел комплексно сопряженное число к числу z
101
arg z аргумент комплексного числа модуль комплексного числа отношение длины окружности к диаметру основание натуральных логарифмов = (
√
5 + 1)/2
— число Фидия
39
∆
оператор конечной разности число k-размещений с повторениями из n элементов число k-размещений без повторений из n элементов число перестановок из n элементов число сочетаний с повторениями из n элементов число сочетаний без повторений из n элементов числа Каталана
25
E
n репьюнит порядка n: E
n
= 11 . . . 1
| {z }
n
74

Глава Метод математической индукции. Аксиома индукции
Аксиома индукции. Если известно, что некоторое утверждение верно для 1, и из предположения, что утверждение верно для некоторого, вытекает его справедливость для n+1, то это утверждение верно для всех натуральных чисел. Деление с остатком. Докажите, что если a и b — целые числа и b 6= 0, то существует единственная пара чисел q и r таких, что a = bq + r,
0 6 r < |b|.
1.2. Позиционная система счисления. Докажите, что прицелом каждое натуральное число n может быть единственным образом представлено в виде n = a k
q k
+ a k−1
q k−1
+ . . . + a
1
q + где 0 6 a
0
, . . . , a k
< q
. (См. также
3.125
,
11.68
.)
Определение. Если a k
, a k−1
, . . . , a
1
, a
0
— цифры числа n в q-ич- ной системе счисления, то используется запись n = (a k
a k−1
. . . Для записи числа в десятичной системе счисления используется также запись (a k
a k−1
. . . a
1
a
0
)
10
= a k
a k−1
. . . a
1
a
0 1.3. Пусть n
} = a
0
, a
1
, . . . , a n
, . . .
— периодическая последовательность, то есть для некоторого натурального T
a n+T
= a n
(n > Докажите, что среди всех периодов этой последовательности существует период наименьшей длины t, причем T делится на t без остатка. Аксиомы индукции. Докажите, что аксиома индукции равносильна любому из следующих утверждений. (См. также) Всякое непустое подмножество натуральных чисел содержит наименьшее число

2. Тождества, неравенства и делимость 2) Всякое конечное непустое подмножество натуральных чисел содержит наибольшее число) Если некоторое множество натуральных чисел содержит 1 и вместе с каждым натуральным числом содержит следующее за ним, то оно содержит все натуральные числа) Если известно, что некоторое утверждение верно для некоторого, и из предположения, что утверждение верно для всех натуральных чисел k, таких, что a 6 k < n вытекает его справедливость для n, то это утверждение верно для всех натуральных чисел k > a.
5) (Обратная индукция) Если известно, что некоторое утверждение верно для 1 и 2, и из предположения, что утверждение верно для некоторого n > 1, вытекает его справедливость для 2n и n − 1, то это утверждение верно для всех натуральных чисел. Число x таково, что число x +
1
x
— целое. Докажите, что при любом натуральном n число x n
+
1
x также является целым. (См. также. Даны натуральные числа x
1
, . . . , x n
. Докажите, что число + x
2 1
)
· . . . · (1 + можно представить в виде суммы квадратов двух натуральных чисел.
(См. также. Числовая последовательность A
1
, A
2
, . . . , A
n
, . . определена равенствами 1,
A
2
= −1,
A
n
= −A
n−1
− 2A
n−2
(n > Докажите, что при n > 2 число 2
n+2
−7A
2
n является полным квадратом. Тождества, неравенства и делимость
Определение. Через n! (читается «n факториал) обозначается произведение всех натуральных чисел от 1 до n:
n! = 1
· 2 · . . . · Для удобства считается, что 0! = В задачах
1.8
–
1.14
докажите тождества. 1 + 3 + 5 + . . . + (2n − 1) = n
2 1.9. 1 2
+ 2 2
+ . . . + n
2
=
n(n + 1)(2n + 1)
6

8 1. Метод математической индукции. 1 2
+ 3 2
+ . . . + (2n − 1)
2
=
n(2n − 1)(2n + 1)
3 1.11. 1 3
+ 2 3
+ . . . + n
3
= (1 + 2 + . . . + n)
2 1.12. 1 · 2 · 3 + 2 · 3 · 4 + . . . + n(n + 1)(n + 2) =
n(n + 1)(n + 2)(n + 3)
4 1.13.
1 2
1
· 3
+
2 2
3
· 5
+ . . . +
n
2
(2n − 1)(2n + 1)
=
n(n + 1)
2(2n + 1)
1.14. 1 · 1! + 2 · 2! + . . . + n · n! = (n + 1)! − 1.
1.15. Факториальная система счисления. Докажите, что каждое натуральное число n может быть единственным образом представлено в виде n = a
1
· 1! + a
2
· 2! + a
3
· 3! + . . . где 0 6 a
1 6 1, 0 6 a
2 6 2, 0 6 a
3 6 3, . . .
1.16. Числа a
0
, a
1
, . . . , a n
, . . . определены следующим образом 2,
a
1
= 3,
a n+1
= 3a n
− 2a n−1
(n > Найдите и докажите формулу для этих чисел.
Определение. Пусть a — целое и b — натуральное числа. b называется делителем a, если существует целое число q такое, что a = В этом случае a называется кратным b, а q — частным отделения на Соотношение «b делит a» записывается в виде b
| a или в виде a ... b
(«a кратно b»). Причем эти записи всегда включают в себя предположение, что b 6= Если b не является делителем a, то будем писать b - Докажите, что в задачах, указанные соотношения выполняются для любого натурального n.
1.17. 10
n
+ 18n − 1 ... 27 1.18. 11
n+2
+ 12 2n+1
... 133 1.19. 2 5n+3
+ 5
n
· 3
n+2
... 17 1.20. n
3
+ 5n ... 6 1.21. 6 2n+1
+ 1 ... 7 1.22. 3 2n+2
+ 8n − 9 ... 16 1.23. 4
n
+ 15n − 1 ... 9 1.24. 2 3
n
+ 1 ... 3
n+1 1.25. Докажите, что для всех натуральных n число, записываемое единицами, делится на 3
n

2. Тождества, неравенства и делимость 1.26
*
. Из чисел от 1 до 2n выбрано n+1 число. Докажите, что среди выбранных чисел найдутся два, одно из которых делится на другое.
(См. также. Решите уравнение −
x
1!
+
x(x − 1)
2!
− . . . + (−1)
n x(x − 1)
· . . . · (x − n + 1)
n!
= В задачах
1.28
–
1.36
докажите справедливость неравенств для натуральных. (См. также+ . . . +
1
√
n
>
√
n
1.30.
(2n)!
(n!)
2
>
4
n n + 1 1.31.
1
n + 1
+
1
n + 2
+ . . . +
1 2n
>
13 24
(n > 1).
1.32. Неравенство Бернулли. (1+x)
n
> 1+nx при любом x > −1.
1.33. 2
n
> n
1.34.
1
· 3 · 5 · . . . · (2n − 1)
2
· 4 · 6 · . . . · 2n
6 1
√
2n + 1 1.35. n n+1
> (n + 1)
n
(n > 2).
1.36.
|x
1
+ . . . + x n
| 6 |x
1
| + . . . + |x n
|, где x
1
, . . . , x n
— произвольные числа. Неравенство между средним арифметическими средним геометрическим. Докажите неравенство x
1
+ . . . + x n
n
>
n
√
x
1
· . . . · x где x
1
, . . . , x n
— положительные числа. Докажите неравенство 2
m+n−2
> mn, где m и n — натуральные числа. Для каких n выполняются неравенства:
а) n! > б) 2
n
> n
2 1.40. Вычислите произведение 3
− 1 2
3
+ 1
·
3 3
− 1 3
3
+ 1
· . . . ·
n
3
− 1
n
3
+ 1
(n > 2).

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

3. Индукция в геометрии и комбинаторике 1.49
*
. Гениальные математики. а) Каждому из двух гениальных математиков сообщили по натуральному числу, причем им известно,
что эти числа отличаются на единицу. Они поочередно спрашивают друг друга Известно ли тебе мое число Докажите, что рано или поздно кто-то из них ответит да. Сколько вопросов они зададут друг другу (Математики предполагаются правдивыми и бессмертными.)

б) Как изменится число заданных вопросов, если с самого начала известно, что данные числа не превосходят 1000?
1.50. Насколько частей делят плоскость n прямых общего положения, то есть таких, что никакие две не параллельны и никакие три не проходят через одну точку. На плоскости проведены n окружностей так, что любые две из них пересекаются в паре точек, и никакие три не проходят через одну точку. Насколько частей делят плоскость эти окружности. Насколько частей делят пространство n плоскостей, проходящих через одну точку, если никакие три не имеют общей прямой. Насколько частей делят пространство n плоскостей общего положения И что это за общее положение. Плоскость поделена на области несколькими прямыми. Докажите, что эти области можно раскрасить в два цвета так, чтобы любые две соседние области были окрашены в разные цвета. (Соседними называются области, имеющие общий участок границы. Сумма углов угольника. Докажите, что произвольный угольник (необязательно выпуклый) можно разрезать на треугольники непересекающимися диагоналями. Выведите отсюда, что сумма углов в произвольном угольнике равна (n − 2)π.
1.56. Клетки шахматной доски 100 × 100 раскрашены в 4 цвета так,
что в любом квадрате 2 × 2 все клетки разного цвета. Докажите, что угловые клетки раскрашены в разные цвета. Имеется k ящиков. В некоторых из них лежат еще k ящиков.
В некоторых из последних лежат еще ящики (снова k штуки т. д.

Сколько всего ящиков, если заполненных m?
1.58. Теорема Эйлера.
Докажите, что для любого выпуклого многогранника имеет место соотношение
В − Р + Г = где В — число его вершин, Р — число ребер, Г — число граней

12 1. Метод математической индукции. Задача Сильвестра. На плоскости взяты несколько точек так, что на каждой прямой, соединяющей любые две из них, лежит по крайней мере еще одна точка. Докажите, что все точки лежат на одной прямой. Выпуклая оболочка. Докажите, что для любого числа точек плоскости найдется выпуклый многоугольник с вершинами в некоторых из них, содержащий внутри себя все остальные точки. Сколько существует (невырожденных) треугольников периметра с целыми длинами сторон

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

14 2. Комбинаторика. Сколько существует десятизначных чисел, в записи которых имеется хотя бы две одинаковые цифры. Каких семизначных чисел больше тех, в записи которых есть единица, или остальных. Пассажир оставил вещи в автоматической камере хранения,
а когда пришел получать вещи, выяснилось, что он забыл номер. Он только помнит, что в номере были числа 23 и 37. Чтобы открыть камеру,