Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду

• Название: Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду
• Дата: 19.09.2022
• Размер: 3.42 Mb.
• Имя файла: matprob.pdf
• Тип: Сборник; #684321
• страница: 5 из 31

1. Какие из следующих рядов сходятся (в зависимости от параметра s > 0, если он задан в условии)?
а)
1 2
+
2 3
+ . . . +
k k + 1
+ . . б) 1 +
1
√
2
+
1 3
√
3
+ . . . +
1
k
√
k
+ . . в 2 − 1
+
1 2
2
− 1
+ . . . +
1 2
n
− 1
+ . . где. ж) 1 +
1 2
s
√
2
+
1 3
s
√
3
+ . . . +
1
n s
√
n
+ . . . (s целое).
з) 1 +
1 2
s
+ . . . +
1
n s
+ . . и 2(log
2 2)
s
+ . . . +
1
n(log
2
n)
s
+ . . .

Сходимость рядов
63
к)*
∞
P
n=1
(2n − 1)!!
(2n)!!
. Через a!! обозначается произведение всех чисел от до a, имеющих туже четность, что и Указание если не получается, то см. далее. В этой задаче считается, что a n
>
0 и b n
>
0.
а)
Необходимое условие сходимости. Если ряд n
сходится,
то для любого ε > 0 существует такой номер N , что для любого n > выполнено неравенство a n
< ε.
б)
Признак сравнения. Если ряд сходится и b n
6
a n
, то ряд тоже сходится.
в)
Признак Даламбера. Если ε > 0, N > 0 и a n+1
/a n
< 1 − ε для любого n > N , то ряд n
сходится.
г)
Признак Коши. Если ε > 0, N > 0 и n
√
a n
< 1 − ε для любого n > N , то ряд сходится. Какие из утверждений 3 б, 4 г, 5 в) предыдущего раздела верны без предположения о положительности слагаемых Как подправить те,
которые неверны. Сходится ли ряда. б) 1 −
1 2
+
1 3
−
1 4
+ . . . + (−1)
n+1 1
n
+ . . в) 1 −
1
√
2
+
1
√
3
−
1 2
+ . . . +
(−1)
n+1
√
n
+ . . г n n
;
д)*
∞
P
n=1
cos
πn
3
n
;
е)*
∞
P
n=1
(−1)
[
√
n]
n
?
Указание: если не получается, то см. далее. а) Ряды −
1 2

+

1 3
−
1 4

+ . . . +

1 2k − 1
−
1 2k

+ . . и −

1 2
−
1 3

−

1 4
−
1 5

− . . . −

1 2k
−
1 2k + 1

− . . .
сходятся.
б) Суммы рядов из а) равны (обозначим эти суммы через S).

Гл. 2. Миникурс по анализу в) Для любого n > 1000 имеем − 0,01 < 1 −
1 2
+
1 3
−
1 4
+ . . . + (−1)
n+1 1
n
< S + г) Ряд 1 −
1 2
+
1 3
−
1 4
+ . . . + (−1)
n+1 1
n
+ . . . сходится и его сумма равна S.
6. а) Признак Лейбница. Если последовательность {a n
} монотонно убывает к нулю те, то ряд a
n сходится.
б)
Признак Абеля. Если последовательность {a n
} монотонно убывает, а частичные суммы ряда ограничены, то ряд n
b сходится. Для каких z ∈ R сходится ряда б в г д n
z n
, где lim n→∞
n
√
a n
= R (определите понятие lim; выясните только для |z| 6= R).

8. Для каких z ∈ C сходятся ряды из предыдущей задачи?
Указания
1. е) Используйте равенство + 1
=
1
p n(n + 1)(
√
n +
√
n + Приложение (Некоторые используемые определения были известны большинству учеников, напомнены на занятиях и здесь не приводятся. Нарисуйте векторные поля и интегральные кривые, соответствующие следующим системам дифференциальных уравнений, а также найдите формулы для общих решений.
4)
См. Арнольд В. И. Обыкновенные дифференциальные уравнения. М Наука

Приложение
65
а)
(
x
′
= x,
y
′
= б 2x,
y
′
= в x,
y
′
= г y,
y
′
= да д) Найдите линейное (аффинное) преобразование, которое переводит фазовый портрет системы из задачи 1 в фазовый портрет линейного векторного поля с одной из матриц 0 0 µ

,

λ 1 0 или cos ϕ
r sin ϕ
−r sin ϕ r cos е Фазовый портрет любого линейного векторного поляна плоскости (или, что тоже самое, линейной однородной системы двух дифференциальных уравнений первого порядка с двумя неизвестными функциями) переводится некоторым линейным преобразованием в фазовый портрет одного из вышеуказанных примеров.
ж)* Ни один из этих примеров не переводится нив какой другой линейным преобразованием.
Сдвигом последовательности {a n
} называется последовательность b
n
= a обозначение b n
= T a n
). Очевидно, сдвиг является линейным оператором на пространстве последовательностей. Рассмотрим также единичный оператор E{a n
} = {a n
}. Тогда ∆ = T − На множестве операторов (действующих на пространстве последовательностей) естественно определяются операции суммы и умножения на число. Очевидно, что множество операторов с этими операциями является линейным пространством над R. Умножением операторов называется их композиция. а) ∆
P
= T . Чему равен Приведите другой пример неком- мутативности умножения операторов.
б) Является ли множество операторов с операцией умножения группой в) Справедлив ли закон ассоциативности для умножения операторов друг на друга и на числа?

г) Выполняется ли дистрибутивность для сложения и умножения операторов?
Итак, несмотря на некоммутативность умножения многочлен от оператора определен. Поэтому рекуррентное уравнение c
k a
n+k
+ . . . + c
1
a n+1
+ c
0
a
0
= можно записать в виде k
T
k
+ . . . + c
1
T + c
0
E){a n
} = 0.

Гл. 2. Миникурс по анализу. а) Пусть характеристическое уравнение рекуррентного уравнения порядка l имеет корень λ кратности l. Сформулируйте и докажите теорему об общем решении этого рекуррентного уравнения.
Указание: b n
=
a n
λ
n
5. а) Если P (T )(T − λE)
l a
n
= 0 для многочлена P , то для последовательности имеем ∆
l
P (T )b n
= б) Решите уравнение ∆
l−1
b n
= λ
n n
k
6. а) Если λ — корень многочлена P кратности l (у P могут быть и другие корни, то P (T )[f (n)λ
n
] = 0 для любого многочлена f (n) степени б Для любых чисел λ
1
, . . . , λ
k
∈ C и l
1
, . . . , l последовательности n
i
λ
n j
(j = 1, . . . , k; i = 0, . . . , l j
) линейно независимы.
Указание: рассмотрите lim в) Выведите из аи б) теорему о решениях линейного однородного рекуррентного уравнения

ГЛАВА 3
МИНИКУРС ПО ТЕОРИИ ЧИСЕЛ
1)
А. Б. Скопенков
Первые четыре пункта приводятся для полноты, чтобы миникурс можно было изучать с нуля (из них на занятиях Школ использовались только наиболее сложные задачи).
Схема зависимости пунктов следующая (если водном пункте используются только определения из другого, то эти пункты не считаются зависимыми):
Простые числа
//
Каноническое разложение
Делимость
//
::
t t
t t
t t
t t
t t
t Линейные диофантовы уравнения
//

Малая теорема
Ферма
//
%%K
K
K
K
K
K
K
K
K
K
K

Квадратичные вычеты
НОД и НОК
Гауссовы числа
Проверка простоты
Первообразные корни
Для успешного решения задач по теории чисел настоятельно рекомендуем проработать книгу Виноградов ИМ. Основы теории чисел
(после изучения настоящего миникурса или параллельно с ним).
Латинскими буквами обозначаются целые числа.
Делимость и деление с остатком (Число a делится на ненулевое число b, если существует такое k, что a = kb. Обозначение b|a. В этом случае b называется делителем числа Отдельные разделы написаны А. Я. Канель-Беловым, АИ. Галочкиным,
А. А. Засориным, СВ. Конягиным, ДА. Пермяковым и И. Н. Шнурниковым. Многие решения написаны МВ. Прасоловым под редакцией автора. В разделе Малая теорема Ферма использованы задачи от ДА. Пермякова, а в разделе Первообразные корни — от А. Я. Канеля-Белова и МВ. Прасолова.

Гл. 3. Миникурс по теории чисел. Какие из следующих утверждений верны для любых n, a, а) 2|(n
2
− б) 4|(n
4
− в) если c|a итог) если b|a, то bc|ac для любого д) если bc|ac для некоторого c, то b|a.
2. а) Сформулируйте и докажите признаки делимости наб) Делится ли число 11 . . . 1 из 1993 единиц на в) Число 1 . . . 1 (2001 единиц) делится на 37.
3. а) Если k не кратно ни 2, ни 3, ни 5, то k
4
− 1 кратно б) Если a + b + c делится на 30, то и a
5
+ b
5
+ делится на 30.
4. Пусть a делится на 2 и не делится на 4. Докажите, что число четных делителей a равно числу нечетных делителей a.
5. а) Для любых a и b существует такое n, что nb 6 a < (n + 1)b.
б)
Теорема о делении с остатком. Для любых чисел a и b (b 6= существуют и единственны такие числа q и r, что a = bq + r и 0 6 r < Эти числа называются частными остатком отделения на b.
6. а) Найдите частные и остатки отделения числа 1996 на −17, на 4 и n
2
+ n + 1 на n + 1 (для каждого целого б) Найдите всевозможные частные и всевозможные остатки отделения числа в) Найдите последнюю цифру числа 1997 1997 Зачетные задачи 1 б) г) д 2 б, в 3 а, баб а)–в). Из них письменно 2 в, Контрольные вопросы. Сколько делителей у числа а) б) в) где) ж) 7.
II. Какие из следующих утверждений верны для любых чисел a, b,
c, а) 6|n
3
− б) 3 ∤ n
2
+ в) если b|a, тог) если a|b и b|a, то |a| = д) если c|ab, то c|a или c|b.

Делимость и деление с остатком. Остаток отделения на −10 равен:
а) б) в) г) Указания и решения. Ответы а, в)–д) да б) нет.
а) Имеем n
2
− n = n(n − 1). Четные числа идут через один. Поэтому одно из чисел n или n − 1 четное. Значит, их произведение n
2
− n четное.
б) 4 ∤ (2 4
− 2) = в) Если a = kc итог) Если a = kb, то ac = д) Если ac = kbc, то c(a − kb) = 0. Так как bc 6= 0, то c 6= 0. Значит = kb.
2. а) Можно считать, что n > 0. Тогда n = 10
m a
m
+ 10
m−1
a m−1
+ . . .
. . . + 10a
1
+ для некоторых целых 0 6 a i
6 Признак делимости на 2. Число делится на 2 тогда и только тогда, когда последняя цифра этого числа делится на Доказательство. Заметим, что число n − всегда четно. Предположим, что 2|a
0
. Если число делит каждое слагаемое, то оно делит сумму. Тогда 2|n. И наоборот, если 2|n, то Признак делимости на 4. Число делится на 4 тогда и только тогда, когда число, образованное двумя последними цифрами этого числа,
делится на Доказательство. Заметим, что число (n − 10a
1
− a
0
) всегда делится на 4. Предположим, что число a
0
+ 10a
1
, образованное двумя последними цифрами данного числа, делится на 4. Тогда 4|n. И наоборот, если, то 4|(a
0
+ Признак делимости на 5. Если последняя цифра числа 5 или то число делится на Докажите аналогично доказательству признака делимости на Признак делимости на 10. Если число оканчивается на 0, то оно делится на Докажите аналогично доказательству признака делимости на Признак делимости на 3. Если сумма цифр числа делится на то само число делится на Доказательство. При любом m число 1 = (10 − 1)(10
m−1
+ 10
m−2
+ . . . + 10 + 1)

Гл. 3. Миникурс по теории чисел делится на 3. Вычтем сумму цифр из числа n и сгруппируем слагаемые − a m
− a m−1
− . . . − a
1
− a
0
=
= (10
m
− 1)a m
+ (10
m−1
− 1)a m−1
+ . . . + (10 − 1)a
1
+ (1 − Как мы показали ранее, каждое слагаемое в последней сумме делится на 3. Отсюда вытекает утверждение задачи.
Признак делимости на 9. Если сумма цифр числа делится на то само число делится на Докажите аналогично доказательству признака делимости на Признак делимости на 11. Вычтем из суммы всех цифр числа стоящих начетных местах, сумму всех цифр на нечетных местах. Если полученное число делится на 11, то и само число n делится на Доказательство. Докажем сначала, что число 10
m
− (−1)
m при любом делится на 11. Для нечетного m число+ 1 = (10 + 1)(10
m−1
− 10
m−2
+ 10
m−3
− . . . − 10 + делится на 11. А для четного положительного m число 1 = (10
m−1
+ 1) · 10 − делится на Рассмотрим разность между суммой цифр, стоящих начетных местах, и суммой цифр, стоящих на нечетных местах. Вычтем ее из числа n и сгруппируем слагаемые − (−1)
m a
m
− (−1)
m−1
a m−1
+ . . . + a
1
− a
0
= (10
m
+ (−1)
m
)a m
+
+ (10
m−1
+ (−1)
m−1
)a m−1
+ . . . + (10 + 1)a
1
+ (1 − Так как каждое слагаемое в последней сумме делится на 11, то сумма делится на 11. Откуда вытекает утверждение.
НОД и НОК (Наибольшее число, делящее и a, и b, называется наибольшим общим делителем (a, b) чисел a и b (предполагается, что числа a и b неравны нулю одновременно).
Числа a и b называются взаимно простыми, если (a, b) = 1.
1. Найдите всевозможные значения а) (n, б) (n, n + в) (n, n + г) (2n + 3, 7n + д) (n
2
, n + 1).

НОД и НОК
71 2. а) Для любых двух чисел a и b наибольший общий делитель (a, существует и единствен.
б) (a, b) = b тогда и только тогда, когда a делится на в) (a, b) делится на любой общий делитель a и г) (ca, cb) = c(a, b) приди, взаимно просты. Бинарный алгоритма) Используя равенства (2m, 2n) = 2(m, n),
(2m + 1, 2n) = (2m + 1, n) и (2m + 1, 2n + 1) = (2m + 1, m − n), постройте алгоритм нахождения НОД.
б) Найдите (2 2
k
+ 1, 2 2
l
+ 1).
4. Если дробь a
b несократима, то и дробь a + b ab несократима.
Наименьшее положительное число, делящееся на a и на b, называется наименьшим общим кратным [a, b] чисел a и b (предполагается, что числа a и b неравны. Найдите а) [192, б) [a
2
− ab + b
2
, ab].
6. а) Для любых двух чисел a и b существует [a, b] и единственно.
б) [a, b] = a тогда и только тогда, когда a делится на в) Любое общее кратное a и b делится наг приди взаимно просты.
Зачетные задачи 1 г, д 2 в)–д); 3 а, баб а)–г). Из них письменно 3 а, 6 в).
Контрольные вопросы. (−24; −10) равно а) б) в) г) −2.
II. [15; −10] равно а) б) в) г) −5.
III. Какие из следующих утверждений верны для любых чисел a, а) Дробь a
b несократима тогда и только тогда, когда (a, b) = б) Дробь a
b несократима тогда и только тогда, когда дробь a − b ab несократима;
в) Дробь a
b несократима тогда и только тогда, когда дробь a − b a + b несократима.

Гл. 3. Миникурс по теории чисел
Указания и решения. Ответы:
а) 1, 2, 3, 4, 6, б) в) 1, 2, 3, 6. г) 1, 3, д) Решение. а) Число (n, 12) является положительным делителем числа. Докажем, что все положительные делители числа 12 удовлетворяют условию. Пусть d|12. У числа d нет делителей, больших его самого.
Значит, (d, 12) = б) Пусть d|n, d|(n + 1) и d > 0. Тогда d|(n + 1 − n) = 1. То есть d = в) Заметим, что множество общих делителей чисел a и b совпадает с множеством общих делителей чисел a и a ± b. Действительно, если d|a и d|b, то d|(a ± b). Наоборот, если d|(a ± b) и d|a, то d|(a ± b − a) = Пользуясь этим утверждением, получаем (n, n + 6) = (6, n). Аналогично пункту а) число (6, n) пробегает все положительные делители числа г) Пользуясь утверждением из пункта в, получим цепочку равенств + 3, 7n + 6) = (2n + 3, 5n + 3) = (2n + 3, 3n) = (2n + 3, n − 3) =
= (n + 6, n − 3) = (n + 6, −9) = (n + 6, Последнее выражение пробегает все положительные делители числа д) Пусть d > 0 — общий делитель чисел и n + 1. Тогда d|(n + 1)(n − 1) = n
2
− Значит, d|(n
2
− (n
2
− 1)) = 1. То есть d = ±1.
2. а) Делитель числа не превосходит его по модулю. Значит, количество общих делителей чисел a и b конечно. А среди них есть наиболь- ший.
б) Пусть b|a. Так как делитель числа не превосходит его по модулю,
то (a, b) = b. Пусть теперь (a, b) = b. Тогда b|a по определению.
в) Пусть a > b > 0. Как было замечено в решении задачи с, общие делители чисел a и b совпадают с общими делителями чисел a ± b и Рассмотрим пару чисел a и b. Далее будем действовать последующему алгоритму если m > n, то пару чисел m и n будем заменять на пару чисел m − n и n; если m < n, то меняем их местами.
Полученные нам шаге числа m и n положительные. Общие делители чисел m и n совпадают с общими делителями чисел m k
− n и n k
, поэтому всеобщие делители (ив частности НОД) у всех получаемых пар одинаковы.
За два подряд идущих шага максимум чисел в паре уменьшается.
Значит, на некотором шаге максимум чисел в паре достигнет своего

Простые числа
73
минимального значения и алгоритм закончит работу. Это означает, что на некотором шаге получится пара с равными числами m
N
= n
N
. Их
НОД равен (a, b), значит m
N
= n
N
= (a, b). Следовательно, делители числа (a, b) совпадают с общими делителями чисел a и г) Число c(a, b) является общим делителем чисел ca и Покажем, что (ca, cb)|c(a, b), откуда будет следовать утверждение.
Очевидно, что c|ca и c|cb. Значит, по пункту в) имеем c|(ca, cb). По определению делимости (ca, cb) = ck для некоторого целого числа k.
НОД двух чисел делит их, значит, (ck)|(ca) и (ck)|(cb). Получаем k|a и k|b. Значит, по прошлому пункту получаем k|(a, b). Домножаем над) Если d — общий делитель чисел a
(a, и b
(a, b)
, то d(a, b) — общий делитель чисел a и b. Значит, по пункту в) d(a, b)|(a, b). Получаем, что d = Простые числа (Число p > 1 называется простым, если оно не имеет положительных делителей, кроме p и 1.
1. а) Найдите все такие p, что p, p + 2, p + 4 простые.
б) Если 111 . . . 11 (n единиц) простое, то n простое. Обратное невер- нов Для любого n существует m, такое что все числа m + 1, . . . , m + n составные. (а) Если a > 1 не делится ни на одно простое p, такое что p 6 то a простое.
б)
Решето Эратосфена. Пусть p
1
, . . . , p k
— все простые числа от до n. Для каждого i = 1, . . . , k вычеркнем все числа, делящиеся наибольшие. Тогда все невычеркнутые числа, меньшие n
2
, — простые.
в) Выпишите все простые числа от 1 до 200.
3. а) Простых чисел бесконечно много.
б)* Простых чисел вида 4k + 3 бесконечно много.
Теорема Дирихле. Если a, b > 0 не имеют общих делителей, отличных от ±1, то простых чисел вида ak + b бесконечно много. (Для доказательства этой теоремы нужна теория, не излагаемая здесь. Обозначим е в порядке возрастания простое число через p а) p n+1 6
p
1
· . . . · p n
+ б) p n+1 6
p
1
· . . . · p n
− 1 при n > в) Между p
1
+ . . . + p и p
1
+ . . . + p всегда есть точный квадрат

Гл. 3. Миникурс по теории чисел. а) Пусть p простое и n < p < 2n. Тогда C
n
2n делится наб. а) Верно ли, что для любого n число n
2

+ n + 41 простое?
б) Для любого многочлена f существует такое n, что f (n) составное,
т. е. непростое, отличное от ±1.
7. Найдите все такие простые числа p, q, r, что p q
+ q p
= Зачетные задачи 2 а)–в); 3 а 4 а)–в); 5 а, баб. Из них письменно 2 а 4 а).
Контрольные вопросы. Каких чисел больше среди чисел 1, 2, 3, . . . , а) Простых;
б) непростых;
в) простых и непростых чисел поровну. Какие из следующих утверждений верны для любого числа а) p n
>
2n − 5; б) p n
6 2n + 5; в) p n
6 Указания и решения. а) Ответ p = Решение. У чисел p, p + 2, p + 4 разные остатки отделения на Значит, одно из них делится на 3. Это число простое, значит, оно равно. Единица не является простым числом, следовательно, p + 2 6= Получаем p = Число p = 3 подходит числа 3, 5, 7 являются простыми.
б) Докажем, что если число n составное, то число 11 . . . 1(n единиц)
тоже составное. Заметим, что 11 . . . 1 =
10
n
− 1 9
. Пусть n = ab, где a и b неравны. Имеем x
b
− 1 = (x − 1)(x b−1
+ x b−2
+ . . . + x + Подставляя x = 10
a
, получаем требуемое.
Обратное утверждение неверно 111 = 37 · Каноническое разложение (8)
1. а) Любое натуральное n раскладывается в произведение простых чисел.
б)
Каноническое разложение. Для любого натурального n найдутся такие различные простые p
1
, . . . , p и натуральные a
1
, . . . , a что n = p a
1 1
· . . . · p a
m m

Каноническое разложение
75
в)*
Основная теорема арифметики. Разложение натурального числа в произведение простых единственно с точностью до порядка со- множителей.
Указание. Можно использовать леммы из Линейных диофантовых уравнений. Пусть n = p a
1 1
· . . . · p a
n n
— каноническое разложение. Найдите а) количество α(n) натуральных делителей числа б) сумму s(n) натуральных делителей числа в, где сумма ведется по всем натуральным делителям числа Указание. Решайте задачу сначала для простого n, потом для n = потом для n = и затем для общего случая. Найдите каноническое разложение чисел а) б) в) C
11 22 4. а) Число n! не делится на 2
n ни при каком n > б) Показатель, с которым простое p входит в каноническое разложение числа n!, равен n
p i
i в) Найдите число нулей в конце числа 1979!.
5. а) Известно, что (a, b) = 15, [a, b] = 840. Найдите a и б) (a, b) · [a, b] = в) Выразите [a, b, c] через a, b, c, (a, b), (b, c), (c, a), (a, b, г) Выразите (a, b, c) через a, b, c, [a, b], [b, c], [c, a], [a, b, д Для n чисел существуют формулы, аналогичные формулам предыдущих пунктов.
Указание. Используйте формулу включений-исключений и каноническое разложение. Натуральное число называется совершенным, если оно равно сумме всех своих натуральных делителей, меньших его. Четное число n совершенное тогда и только тогда, когда n = 2
p−1
(2
p
− 1), где p и 2
p
− простые. а) Если (a, b) = 1 и ab = m
2
, то существуют такие числа k и l, чтоб) Найдите некоторые такие числа n > m > 100, что 1 + 2 + . . . + n =
= в) Найдите все такие числа m > n > 1, что 1 2
+ 2 2
+ . . . + n
2
= г) Если n > 2, ab = c и (a, b) = 1, то a = x и b = y для некоторых x и д) Число m(m + 1) не является степенью простого числа ни при каком целом m > 1.

Гл. 3. Миникурс по теории чисел. а) Если ab = cd, то существуют такие числа k, l, m, n, чтоб) Найдите все такие числа a, b, c, d, k, m, что ab = cd, a + d = 2
k
,
b + c = 2
m
9. Найдите наименьшее такое n, что из любых n чисел, не превосходящих, можно выбрать два, одно из которых делится на другое.
Контрольные вопросы. Найдите каноническое разложение числа а) 4 · 10 б) 2 4
· 5 в) (2 · 2 · 5)
2
II. Назовем положительное четное число четнопростым, если его нельзя представить в виде произведения двух меньших четных чисел.