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

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

a,b
, N
b,c
, N
a,c и N
a,b,c
. Через N обозначим общее число треугольников. Тогда N = 6 3
, N
a
= N
b
= N
c
= 6 2
, N
a,b
=
= N
b,c
= N
a,c
= 6
, N
a,b,c
= 1
. Искомое число находится по формуле включений и исключений 3
− 3
· 6 2
+ 3
· 6 − 1 = 5 3
2.102
. а) б) в) 8000.

Ответы, указания, решения 2.103
. 1600.
2.104
. 998 910.
2.107
. Пусть S — площадь всей комнаты, S
i
— площадь го ковра = 1, 2, 3), S
i,j
— площадь, покрытая мим коврами одновременно 6 i < j 6 3), и S
1,2,3
— площадь, покрытая всеми тремя коврами. По формуле включений и исключений − (S
1
+ S
2
+ S
3
) + (S
1,2
+ S
1,3
+ S
2,3
) − S
1,2,3
> Отсюда+ S
1,3
+ S
2,3
> S
1
+ S
2
+ S
3
− S = Поэтому хотя бы одна из площадей S
1,2
, или не меньшем. Решение этой задачи повторяет рассуждения из задачи 2.109
. б) Формула включений и исключений дает −
X
S
i
+
X
S
i,j
−
X
S
i,j,k
+
X
S
i,j,k,l
− S
1,2,3,4,5
> Запишем отдельно равенства, которые получаются если формулу включений и исключений применить отдельно к каждому ковру. Например,
для первого имеем+ S
1,2,3,4,5
> Складывая пять подобных равенств, получаем 2
X
S
i,j
+ 3
X
S
i,j,k
− 4
X
S
i,j,k,l
+ 5S
1,2,3,4,5
> Найдем теперь такую линейную комбинацию равенств (
13.1
) ив которой отсутствует сумма. Очевидно, что для этого к неравенству) нужно прибавить утроенное неравенство (
13.1
):
3S − 2
X
S
i
+
X
S
i,j
−
X
S
i,j,k,l
+ 5S
1,2,3,4,5
> Отсюда 2
X
S
i
− 3S = 5 − 3 = Значит для некоторых i и j выполняется неравенство S
i,j
> в) Найдите линейную комбинацию равенств (
13.1
) ив которой отсутствует сумма 12 13 14 15 23 24 25 34 35 45 123 124 125 134 135 145 234 235 245 345

Ответы, указания, решения цифры на отдельных частях показывают какими из фигур покрыты соответствующие участки. Например, цифры 1 ив первой клетке означают, что она покрыта первой и второй фигурами. Эта схема показывает, что оценки 1/5 и 1/20 — точные. Постройте взаимно однозначное соответствие между такими последовательностями и расстановками скобок в произведении x
0
· x
1
· . . . · x по одному из правил "("
→ +1;
"
· "
→ или "
· "
→ +1;
")"
→ −1.
2.112
. Чтобы построить взаимно однозначное соответствие между триангуляциями многоугольника и расстановками скобок в произведении, нужно расставить на сторонах многоугольника переменные x
0
, x
1
, . . . , x оставшейся стороне приписывается все произведение. Придумайте соответствие между всеми такими маршрутами ладьи и последовательностями чисел из задачи 2.115
. Чтобы доказать, что существует циклический сдвиг последовательности, у которого все частичные суммы положительны, примените принцип максимума рассмотрите тот циклический сдвигу которого наибольшее количество первых частичных сумм положительно. Единственность следует из того, что ни одну из последовательностей нельзя разбить на два отрезка с положительными суммами.
Чтобы получить формулу для чисел Каталана, дополните последовательность задачи
2.103
элементом a
0
= 1 2.116
. Рассмотрите в произведении x
0
· x
1
· . . . · x то умножение,
которое делается последним.
Глава
3 3.1
. Если p
1
, p
2
, . . . , p n
— все простые числа, то число N = p
1
×
× p
2
· . . . · p n
+ не может быть ни простым ни составными. Перепишем уравнение в виде 2q
2
= (p − 1)(p + 1)
. Заметим, что p
— непременно нечетное простое число. Отсюда q — четное. Поэтому q = 2
. Значит p = 3.
3.7
. Пусть p
1
= 3
, p
2
= 7
, . . . , p n
— все такие простые числа. Рассмотрим число N = 4p
2
· . . . · p n
+ Оно не делится ни на одно из чисел p
1
, p
2
, . . . , p n
, но обязательно содержит простой делитель вида 4k + 3.
3.8
. Доказательство повторяет рассуждения задачи. В качестве числа N можно взять N = 6p
1
· . . . · p n
+ 5

Ответы, указания, решения 3.9
. Каждому делителю a числа n соответствует делитель b, для которого a · b = n. Одно из чисел a или b не превосходит. Когда n — полный квадрат. Воспользуйтесь решением задачи 11 ×
× 13 · 37; 1111111 = 239 · 4649.
3.12
. Рассмотрите числа 1001! + 2, 1001! + 3, . . . , 1001! + 1001.
3.14
. а) 5, 11, 17, 23, б) 7, 37, 67, 97, 127, 157.
3.15
. Возьмем в качестве начального элемента прогрессии элемент этой прогрессии такой, что a > 1. Тогда все числа a k
= a + kd при k = ma делятся на a, то есть являются составными. Рассмотрите остатки отделения на 3.
3.18
. 5.
3.20
. n
4
+ 4 = n
4
+ 4n
2
+ 4 − 4n
2
= (n
2
− 2n − 2)(n
2
+ 2n − 2)
3.21
. Подставьте n = 40 или n = 41. При n = 0, 1, . . . , 39 числа будут простыми. Рассмотрите число p
1
·
2
· . . . · p n
− 1 3.24
. 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031 = 59 · 509.
3.25
. e
5
= 1807 = 13
· 139.
3.26
,
3.29
. Воспользуйтесь формулами сокращенного умножения из задачи 3.27
. Так как 2
n
> n + 1
, то 2
n+1
| 2 2
n
. Отсюда 2 2
n+1
− 1
| 2 2
2n
− Но тогда f n
| 2 2
n+1
− 1
| 2 2
2n
+1
− 2 = 2
f n
− 2 3.28
. Смотрите задачу 3.30
. При x = 0 многочлен принимает значение a
0
. Поэтому a
0
= некоторое простое число. Подставляя в многочлен P(x) числа x
1
= p
,
x
2
= p
2
, x
3
= p
3
, . . . , получаем P(x j
) ... p
. Следовательно P(x j
) = p
(j = 1, 2, . . . ) и многочлен P(x) принимает одно и тоже значение в бесконечном числе точек, что невозможно. Ответ нет. (m, n) + 1, m + n − (m, n).
3.33
. Рассмотрите прямоугольник OABC, расположенный на координатной плоскости так, что его вершины имеют координаты O(0; 0),
A(q, 0)
, B(q, p), C(0, p). Проведите в нем диагональ OB и прямые вида x + y = k
(k = 0, 1, . . . , p + q), которые разделят ее на p + q равных частей. Через 180 дней. У пари) совпадают множества общих делителей.
Значит совпадают и наибольшие элементы в этих множествах. Если (a, b) = 1, то для некоторых целых u и v выполняется равенство au + bv = 1. Домножив его на c, получаем равенство acu +

Ответы, указания, решения+ bcv = c
, в котором a делит левую часть. Значит a делит и правую часть, то есть a
| c.
3.39
. Если m > n и m = nq + r, где r < n, то один шаг алгоритма
Евклида приводит к равенству 1 . . . 1
| {z }
m
, 1 . . . 1
| {z }
n
) = ( 1 . . . 1
| {z }
n
, 1 . . . 1
| {z То есть, применяя алгоритм Евклида к числам, мы получаем, что он применяется к их длинами Поэтому, в конце концов, получится число, состоящее из (m, n) единиц. 10.
3.41
. 10.
3.42
. 19 · 19
◦
− 360
◦
= 1
◦
3.43
. 500.
3.45
. Только если эти числа равны. 20 отметок, 9 оборотов. Примените алгоритм Евклида к числам, стоящим в числителе и знаменателе. а) Так как (n
2
+ 2n + 4, n
2
+ n + 3) = (n + 1, 3)
, то дробь будет сократима, когда (n + 1, 3) > 1. Ответ n = 3k − б) Так как (n
3
−n
2
−3n, n
2
−n+3) = (n
2
−n+3, 6n)
, то дробь можно сократить либо на 2, либо на 3, либо на некоторый делитель числа Первый случай невозможен. Во втором случае находим, что n = 3k или n = 3k + 1
. В третьем случае (n
2
− n + 3, n) = (n, 3)
, поэтому n снова должно быть числом вида n = 3k. Ответа) Предположим, что данное число целое. Тогда после деления числителя на знаменатель с остатком, приходим к равенству n
4
+ 1
n
2
+ n + 1
= n
2
− n +
n + 3
n
2
+ n + Либо полученная дробь равна нулю, что возможно при n = −3, либо выполняется неравенство 0 <
|n
2
+ n + 1
| < |n+3|. Так как при любых n
0 < n
2
+ n + 1
, то нужно рассмотреть два случая n + 3 > 0 и n + 3 < В первом случае, приходим к неравенству n
2 6 2. Из значений n = −1,
n = 0
, n = 1 условию задачи удовлетворяют только первые два. Ответ = −3
, −1, б) n = 0, 1.
3.52
. n = 2, 3.
3.53
. На 17.
3.54
. а) При m > n выполняется равенство (a m
− 1, a n
− 1) =
= (a m−n
− 1, a n
− 1)
. Поэтому алгоритм Евклида для чисел становится

Ответы, указания, решения
183
алгоритмом Евклида для показателей и заканчивается парой показателей) и 0. Можно также сказать, что задача равносильна задаче. Действительно, при решении задачи
3.39
основание системы счисления не имело никакого значения. В частности, можно считать, что вычисления проводились в системе счисления с основанием б) Воспользуйтесь равенством f n+1
= f
0
f
1
. . . f n
+ 2 3.55
. Воспользуйтесь взаимной простотой чисел Ферма. Воспользуйтесь результатом задачи 3.58
. Воспользуйтесь результатом задачи 3.64
. Начните, например, с двух соседних чисел Фибоначчи F
n и F
n+1 3.66
. 7 и 2.
3.68
. а) Воспользуйтесь методом математической индукции. Как ив задаче, каждой точке с целыми неотрицательными координатами (x; y) следует поставить в соответствие число N(x, y) =
= ax + by
. Все точки, для которых, y) = получаются друг из друга сдвигом на вектор (b; −a). Отсюда следует,
что наименьшее число c, для которого уравнение (
13.3
) имеет n + решение, равно nab + a + b. В этом случае все решения описываются формулой k
; y k
) = (1 + kb; 1 + (n − k)a)
(0 6 k 6 Аналогично, наименьшее число c, для которого уравнение (
13.3
) имеет решений, равно (n − 1)ab + a + b. Поэтому те c, для которых уравнение) имеет n решений, находятся в пределах − 1)ab + a + b
6 c 6 nab + a + b.
3.74
. Точка с координатой 4140.5.
3.76
. 27.
3.77
. 24.
3.78
. 123.
3.81
. При помощи формул задачи, доказательство каждого тождества сводится к доказательству некоторого равенства, содержащего максимумы и минимумы.
а) max(α, min(α, β)) = б) min(α, max(α, β)) = в) α + β + γ = max(α, β, γ) + min(α + β, α + γ, β + га б) 3 · 4 · 6 · 8 · 12.

Ответы, указания, решения. Равенства следуют из того, что все делители числа n = p
α
1 1
· . . .
· p
α
s имеют вид d = p
β
1 1
. . . p
β
s s
(0 6 β
1 6 α
1
, . . . , 0 6 β
s
6 α
s
).
3.87
. n = 12.
3.88
. а) били. Мультипликативность функций τ(n) и σ(n) следует из формул задачи 3.91
. Все делители числа n можно разбить на пары чисел a, b таких,
что a · b = n, причем в каждой паре одно из чисел обязательно не превосходит. τ(m · n) < τ(m) · τ(n); σ(m · n) < σ(m) · σ(n).
3.94
. Воспользуйтесь формулой для σ(n) из задачи 3.95
. Представим n в виде n = 2
k−1
b
, где b — нечетное число, k > Поскольку σ(x) — мультипликативная функция, то) = σ(2
k−1
)σ(b) = (2
k
− По условию, σ(n) = 2n = 2
k b
, так что 1)σ(b) = 2
k Отсюда b = (2
k
− 1)c,
σ(b) = 2
k c = b + Если c 6= 1, то у числа b существует по крайней мере три положительных делителя b, c и 1. В этом случае σ(b) > 1 + b + c, что противоречит равенству σ(b) = b + c. Поэтому c = 1, σ(b) = b + 1, то есть b = 2
k
− простое число. Согласно задаче, это возможно только при простых значениях показателя k. Таким образом n имеет вид n = 2
p−1
(2
p
− где p и b = 2
p
− 1
— простые числа.
Первые простые числа Мерсенна p = 2, 3, 5, 7 дают совершенные числа n = 6, 28, 496, 8128.
3.96
. 220 и 284; 17296 и 18416.
3.98
. 120.
3.100
. Оба числа совпадают с количеством натуральных чисел, не превосходящих α и делящихся на d.
3.102
. Отбросьте знак целой части в формуле Лежандра и дополните сумму до бесконечной геометрической прогрессии

Ответы, указания, решения 3.103
,
3.104
. По формуле Лежандра (a k
p k−1
+ . . . + a
1
) + (a k
p k−2
+ . . . + a
2
) + . . . + a k
=
= a k
(p k−1
+ . . . + p + 1) + . . . + a
1
=
=
(a k
(p k
− 1) + . . . + a
0
(p
0
− 1))
(p − 1)
=
(n − a k
− . . . − a
1
− a
0
)
(p − 1)
3.107
. Нет. Рассмотрите числа n вида n = 2
k
− и примените к ним формулу Лежандра. 377 пар кроликов. Пусть a n
— количество способов, которыми кузнечик может добраться до й клетки. Тогда a
1
= a
2
= 1
. Кроме того, в (n + ю клетку кузнечик может попасть либо из й клетки, либо перепрыгнув ю клетку. Поэтому a n+1
= a n−1
+ a n
. Отсюда a n
= F
n−1 3.110
. 233 способами. Изначальных условий F
0
= 0
, F
1
= и рекуррентного соотношения числа Фибоначчи с отрицательными номерами определяются однозначно F
−n
= (−1)
n+1
F
n
3.112
. Примените индукцию. Все равенства доказываются при помощи метода математической индукции. Разбейте все пути кузнечика на две группы проходящие и не проходящие через ю клетку. 1.
3.117
F
3
F
1
· F
2
−
F
n+2
F
n
· F
n+1 3.118
. а, б, в) Рассмотрите последовательность остатков отделения на 2, 3 и г) Воспользуйтесь тождеством из задачи 3.119
. Рассмотрим остатки отделения чисел F
1
, F
2
, . . . на m. По двум соседним элементам этой последовательности она однозначно восстанавливается влево и вправо. Поэтому эта последовательность циклически повторяется и 0 (остаток отделения на m) встретится в ней бесконечно много раза) Воспользуйтесь результатом задачи. б) Воспользуйтесь равенством (F
m+n
, F
m
) = (F
m
, F
n
)
, которое следует из тождества задачи 3.123
. Из пункта а) задачи
3.113
следует равенство+ F
n+1
+ . . . + F
n+7
= F
n+9
− Это число не может быть числом Фибоначчи, поскольку F
n+8
< F
n+9
−
− F
n+2
< F
n+9

Ответы, указания, решения. Найдите рекуррентную формулу для числа таких последовательностей. Можно также воспользоваться результатом задачи
3.109
Для этого нужно каждую единицу интерпретировать как прыжок кузнечика через клетку. Для разложения числа n в фибоначчиевой системе счисления нужно воспользоваться жадным алгоритмом вычитать из n наибольшее число F
m
, не превосходящее n.
3.126
. Докажите, что числа F
n
, найденные по формуле Бине, удовлетворяют начальным условиями рекуррентному соотношению. Раскройте скобки в формуле Бине, пользуясь формулой бинома Ньютона. Равенство можно доказать методом математической индукции. Другое решение можно получить если воспользоваться задачами и 3.130
. S
n
= 0
, если n ≡ 2, 5 (mod 6); S
n
= 1
, если n ≡ 0, 1 (mod 6);
S
n
= −1
, если n ≡ 3, 4 (mod 6). Более коротко ответ задачи можно записать так π(n + 1)/3
sin π/3
=
2
√
3
sin
π(n + 1)
3 3.131
. F
n+1 3.134
. F
n−2
+ F
n
= L
n−1 3.135
. L
n
= ϕ
n
+
b
ϕ
n
3.136
n r
L
n
+ F
n
√
5 2
− (−1)
k k
r
L
k
− F
k
√
5 2
= 1.
3.137
. а) Подбором можно найти первые решения данного уравнения в целых числах (1, 0), (2, 1), (5, 3), в которых угадываются соседние числа Фибоначчи. Можно предположить, что ответом к задаче будут пары (x n
, y n
) =
± (F
2n+1
, F
2n
)
, где n — произвольное целое число.
(См. задачу) Действительно, после подстановки пары (F
2n+1
, в уравнение, приходим к частному случаю тождества Кассини: F
2 2n+1
−
−F
2n
F
2n+2
= 1
. (См. задачу) Покажем, что у исходного уравнения нет других решений. Рассмотрим, например, те пары решений (x, y), в которых x > 1 и y > 0. Нетрудно проверить, что такие x и y должны быть связаны неравенствами y < x 6 2y. Кроме того, каждая пара решений (x, y) порождает целую цепочку решений по правилу (x − y, 2y − x) → (x, y) → (2x + y, x + y) → . . .

Ответы, указания, решения
187
При движении по этой цепочке влево числа в парах уменьшаются < x
0
= x − y < x,
0 6 y
0
= 2y − x < Поэтому на некотором шаге получится пара, в которой y = 0, x = 1, то есть пара (F
1
, F
0
)
. Но эта пара порождает цепочку (F
1
, F
0
)
→ (F
3
, F
2
)
→ . . . → (F
2n+1
, F
2n
)
→ . . Значит, исходная пара должна иметь вид (x, y) = (F
2n+1
, F
2n
) = (x n
, y б) Все решения уравнения имеют вид (x n
, y n
) =
±(F
2n
, F
2n−1
)
, где n
— произвольное целое число. а) Докажите сначала вспомогательные неравенства F
n+5
>
>
21 2
F
n
, F
n+3 6 8F
n
3.141
. б) F
k n
= F
n−k+1
F
k−1
n−1
+ F
k−1
F
k n−1
= F
n−k−1
F
k−1
n−1
+ F
k+1
F
k n−1 3.142
. Докажите, что A
k допускает представление в виде линейной комбинации с целыми коэффициентами чисел и A
k n−1 3.143
. а) [11; 3, б) [1; 6, 6].
3.144
F
n+1
F
n
3.147
. Смотрите задачу, пункт га) При k = 0, 1 равенство проверяется непосредственно. Далее применим индукцию. Предположим, что равенство доказано для некоторого. Докажем его для k + 1. Подходящая дробь с номером k + получается из й дроби заменой a на a k
+ 1/a k+1
:
[a
0
; a
1
, . . . , a k
, a k+1
] = [a
0
; a
1
, . . . , a k
+ 1/a Делая такую замену в равенстве a
1
, . . . , a k
] =
P
k
Q
k
=
a k
P
k−1
+ P
k−2
a k
Q
k−1
+ приходим к соотношению a
1
, . . . , a k
, a k+1
] =
(a k
+ 1/a k+1
)P
k−1
+ P
k−2
(a k
+ 1/a k+1
)Q
k−1
+ б) Примените индукцию.
в) Из пункта б) немедленно следует, что числа P
k и Q
k взаимно просты. Воспользуйтесь свойством б) из задачи 3.152
. а) x k
= 4 + 13k
, y k
= 31 + 101k
(k ∈ Z); б) x k
= −6 + 19k
,
y k
= −19 + 79k
(k ∈ Z).
3.153
. Если бы 400 последовательных григорианских лет в точности соответствовали 400 астрономическим годам, то продолжительность одного астрономического года равнялась бы 366 + 303 · 365 400
= 365 +
97 407

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