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

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

подставить значение x = 1?
11.97. Найдите сумму) = g
0,l
(x) − g
1,l−1
(x) + g
2,l−2
(x) − . . . + (−1)
l g
l,0
(x).
11.98. Обозначим через количество разбиений числа n на не более чем k слагаемых, каждое из которых не превосходит l. Докажите равенства:
а) P
k,l
(n) − P
k,l−1
(n) = P
k−1,l
(n − б) P
k,l
(n) − P
k−1,l
(n) = P
k,l−1
(n − в) P
k,l
(n) = г) P
k,l
(n) = P
l,k
(kl − n)
11.99. Пусть f k,l
(x)
— производящая функция последовательности k,l
(x) = P
k,l
(0) + xP
k,l
(1) + . . . + x kl
P
k,l
(kl).

4. Многочлены Гаусса
167
а) Докажите равенства k,l
(x) = f k−1,l
(x) + x k
f k,l−1
(x) = f k,l−1
(x) + x l
f б) Докажите, что функции f совпадают с многочленами Гаусса g
k,l
(x)
11.100. Докажите, что при любых k и l многочлен g является возвратным, то есть x kl g
k,l
(1/x) = g k,l
(x)
. Решите задачу двумя способами пользуясь определением многочленов Гаусса и при помощи свойств чисел из задачи 11.101. Докажите, что) + P
kl
(1) + P
kl
(2) + . . . + P
kl
(kl) = C
k не используя свойства многочленов Гаусса

Глава Шутки и ошибки. Ученик Коля Васин при помощи метода математической индукции смог доказать, что в любом табуне все лошади одной масти.
Если есть только одна лошадь, то она своей масти, так что база индукции верна. Для индуктивного перехода предположим, что есть лошадей (с номерами от 1 до n). По индуктивному предположению лошади с номерами от 1 до n−1 одинаковой масти. Аналогично лошади с номерами от 2 до n также имеют одинаковую масть. Но лошади с номерами от 2 доне могут менять свою масть в зависимости оттого как они сгруппированы — это лошади, а не хамелеоны. Поэтому все лошадей должны быть одинаковой масти.
Есть ли ошибка в этом рассуждении, и если есть, то какая (См.
также
1.4
.)
12.2. Иногда вычитая дроби можно вычитать их числители и складывать знаменатели. Например − 25 6 + 10
=
9 6
−
25 10
;
8 − 50 2 + 5
=
8 2
−
50 Для каких дробей это возможно. Найдите все дроби с числителем и знаменателем не превосходящими, в которых можно проводить сокращение на равные цифры.
Примером может служить равенство 6 6 6 64
=
1 4
12.4. Легко проверить равенства log

16 +
16 15

=
log 16 + log
16 15
;
log

64 7
− 8

=
log
64 7
−
log В каких еще случаях можно выносить логарифм за скобку. При каких значениях a и b возможно равенство sin a + sin b = sin(a + b)?

169 12.6. Квадраты двух зеркальных чисел 12 и 21 также являются зеркальными числами (144 и 441). Какие двузначные числа обладают аналогичным свойством И дополнительный вопрос в каких системах счисления число 441 будет полным квадратом. Черная пятница. Докажите, что тринадцатое число месяца с большей вероятностью приходится на пятницу, чем на другие дни недели. Предполагается, что мы живем по Григорианскому стилю (см. Коля Васин, решая задачу, получил в ответе шестизначное число. А потом он подумал, что это произведение двух трехзначных чисел и выполнил умножение. Каким был первоначальный ответ, если второй ответ оказался в три раза меньше. Восстановите алфавит племени Мумбо-Юмбо из задачи 12.10. Найдите коэффициент при x у многочлена − a)(x − b)(x − c) . . . (x − z).
12.11. «1 = −1». Изучив комплексные числа, Коля Васин решил вывести формулу, которая носила бы его имя. После нескольких попыток ему это удалось 1
⇒
√
1
√
−1
=
√
−1
√
1
⇒
√
1
√
1 =
√
−1
√
−1
⇒ 1 = После некоторых размышлений, Коля придумал более короткое доказательство своего тождества = i
2
=
√
−1
·
√
−1 =
p
(−1)(−1) =
√
1 = Не ошибся ли где-нибудь Коля Васин? (См. также. После экспериментов с мнимой единицей, Коля Васин занялся комплексной экспонентой. Пользуясь формулами задачи, он смог доказать, что sin x всегда равен нулю, а cos x — единице x =
e ix
− e
−ix
2i
=
(e
2πi
)
x/(2π)
− (e
−2πi
)
x/(2π)
2i
=
1 − 1 2i
= 0;
cos x =
e ix
+ e
−ix
2
=
(e
2πi
)
x/(2π)
+ (e
−2πi
)
x/(2π)
2
=
1 + 1 2
= Где ошибка в приведенных равенствах (См. также. «65 = 64 = 63». Тождество Кассини лежит в основе одного геометрического парадокса. Он заключается в том, что можно взять

170 12. Шутки и ошибки шахматную доску, разрезать ее на четыре части, как показано ниже, а затем составить из этих же частей прямоугольник:
Как расположить те же четыре части шахматной доски, чтобы доказать равенство «64 = 63»? (См. также. Из километров — в мили. В задаче
3.125
была введена фи- боначчиева система счисления. Она оказывается удобной, когда нужно сделать перевод расстояния из километров в мили или наоборот.
Предположим, что мы хотим узнать, сколько миль в 30 километрах.
Для этого представляем число 30 в фибоначчиевой системе счисления = 21 + 8 + 1 = F
8
+ F
6
+ F
2
= (Теперь нужно сдвинуть каждое число на одну позицию вправо, получая+ F
5
+ F
1
= 13 + 5 + 1 = 19 = (Поэтому предполагаемый результат — 19 миль. (Правильный ответ около 18,46 миль) Аналогично делается перевод из миль в километры.
Объясните, почему работает такой алгоритм. Проверьте, что он дает округленное число миль в n километрах при всех n 6 100, отличающееся от правильного ответа меньше чем на 2/3 мили. Обозначим через S сумму следующего ряда = 1 − 1 + 1 − 1 + 1 − . . Преобразовав равенство (
12.1
), можно получить уравнение, из которого находится S:
S = 1 − (1 − 1 + 1 − 1 + . . . ) = 1 − S
⇒ S =
1 Сумму S можно также найти объединяя слагаемые ряда (
12.1
) в пары = (1 − 1) + (1 − 1) + . . . = 0 + 0 + . . . = 0;
S = 1 − (1 − 1) − (1 − 1) − . . . = 1 − 0 − 0 − . . . = 1.

Наконец, переставив местами соседние слагаемые, получаем еще одно значение S:
S = −1 + 1 − 1 + 1 − 1 + . . . = −1 + (1 − 1) + (1 − 1) + . . . = Итак, действуя четырьмя разными способами, мы нашли четыре значения суммы S:
S =
1 2
= 0 = 1 = Какое же значение имеет сумма S в действительности

Ответы, указания, решения
Глава
1 1.15
. Воспользуйтесь тождеством из задачи 1.16
. a n
= 2
n
+ 1
(n > 0).
1.26
. При n = 1 утверждение задачи очевидно. Предположим, что утверждение справедливо для некоторого n > 1 и докажем его для n + 1
. Назовем набор чисел допустимым, если ни одно из них не делится ни на какое другое. Пусть нам удалось среди чисел от 1 до 2n + найти допустимый набор из n + 2 чисел. В этом наборе будут обязательно присутствовать числа 2n + 1 итак как иначе получается противоречие с индукционным предположением. Другие n чисел из допустимого набора обозначим a
1
, . . . , a n
. Среди них нет числа n + так как n + 1
| 2n + 2. Поэтому, дополняя набор a
1
, . . . , a числом n + 1
, получаем снова допустимый набор. Но он состоит из n + 1 числа в пределах от 1 до 2n, что снова противоречит предположению индукции.
Мы доказали даже чуть более сильное утверждение среди любых n + натуральных чисел, меньших 2n, есть два числа, отношение которых степень числа 2.
1.27
. x = 1, 2, . . . , n.
1.37
. Это неравенство удобно доказывать при помощи обратной индукции (см. задачу, то есть делать переход от n к n − 1. Но предварительно понадобится доказать справедливость этого неравенство для всех n вида n = 2
k
1.40 2
3

1 +
1
n(n + 1)

1.42
. Самое короткое решение содержит 2 8
− перемещений. 3 8
− 1 1.44
. 2 · 3 7
− 1 1.45
. Если квадрат допускает разбиение на n квадратов, то он допускает разбиение и на n + 3 квадрата (достаточно один из квадратов разрезать на четыре. Разобьем все натуральные числа натри арифметические прогрессии n = 3k, n = 3k + 1, n = 3k + 2, ив каждой из них найдем минимальное n, для которого задача имеет решение. Впервой Ответы, указания, решения
173
прогрессии минимальное такое n равно 6, во второй — 4, в третьей. (Требуемые разбиения строятся из квадратов 3 × 3, 2 × 2 и 5 × 5.
1.47
. а) 2 кольца (11 = 1 + 1 + 3 + б) Из (n + 1)2
n
− колец. Банк может выдать суммы 8, 9 и 10 рублей. Прибавляя к ним нужное количество трехрублевых купюр, можно получить любую большую сумму. 1 + n(n + 1)/2.
1.51
. n
2
− n + 2 1.53
. (n
3
+ 5n + 6)/6 1.57
. k + mk − m.
1.58
. Проведите индукцию по числу граней. Пусть не все точки лежат на одной прямой. Проведем прямую через каждую пару точек и рассмотрим всевозможные пары прямая и не лежащая на ней точка. Противоречие получается, если рассмотреть пару, в которой расстояние от точки до прямой минимально. Пусть a число невырожденных треугольников периметра n с целыми длинами сторон. Докажите, что a
n
= a n−3
+

h n − 1 если n — нечетно;
0,
если n — четно.
Отсюда a
100
= 24 + 23 + 21 + 20 + . . . + 3 + 2 = Глава 2.1
. а) б) 28.
2.2
. 9 · 10 6
2.3
. 10 3
· 30 3
2.4
. Школьников в 27/25 раза больше. 6 5
· 8 4
+ 6 4
· 8 5
2.6
. 40.
2.7
. 9 · 10 4
· 2.
2.8
. 9 · 10 5
− 5 6
2.9
. 9 · 10 9
− 9
· 9!.
2.11
. 360.
2.12
. 9 · 10 2
2.13
. 9 · 10 7
· 5.
2.14
. 3 7
2.15
. 5 4
2.16
. Найдите число способов поставить фишки на поля одного цвета и на поля разных цветов. Ответ нет

Ответы, указания, решения. 38 2.19
. Если всего имеется n точек, то из каждой выходит от 0 до n линий. Ноне может быть двух точек таких, что из одной выходит n линий, а из другой — 0.
2.20
. Если взять k + 1 карточку с нечетными номерами, то условие задачи будет выполнено. Если взять k + 2 карточки, то рассматривая разности чисел на них, мы получим не менее k + 1 различных чисел от 1 до 2k. Поэтому хотя бы 2 из них совпадут с числами на k − 1
невыбранной карточке. Шахматная доска может быть разбита на 16 квадратов 2 × Если на доске более 16 королей, то два из них попадут в такой квадрат и будут бить друг друга. Ответ 16.
2.22
. В каждой из 50 пар женщина находиться не может. Пусть N(k, l) и N(k, r) — количества левых и правых сапог го размера соответственно. По условию задачи, l) + N(k, r) = 200
(k = 41, 42, 43);
N(41, l) + N(42, l) + N(43, l) = 300;
N(41, r) + N(42, r) + N(43, r) = Не может случиться так, что для каждого размера левых (правых)
сапог меньше чем правых (левых. Без ограничения общности будем считать, что, l)
6 N(41, r),
N(42, l)
6 N(42, r),
N(43, l)
> N(43, Тогда количество годных пар, l) + N(42, l) + N(43, r) = 300 − N(43, l) + N(43, r)
> 100.
2.24
. См. задачу 2.25
. Расположим данные числа в порядке возрастания и разобьем их на группы по цифре десятков. Число m таких групп удовлетворяет условиям 6 6 m 6 10. Среди m групп найдется группа A
6
, в которой не менее 6-ти чисел. Аналогично (методом от противного) устанавливается существование групп A
5
, . . . , A
1
. Первое число возьмем из A
1
. Второе из A
2
, так чтобы цифра единиц отличалась от цифры единиц первого числа и т. д. 999.
2.28
. Докажем по индукции, что если из чисел от 1 до 2n − 2 (n > выбрано n + 1 различное число, то из них можно выбрать три таких числа, что сумма двух из них равна третьему. При n = 3 утверждение задачи очевидно. Предположим, что утверждение доказано для n = k

Ответы, указания, решения
175
и рассмотрим случай n = k + 1. Если k + 1 из выбранных чисел попали в промежуток от 1 до 2k − 2, то применимо предположение индукции.
Если же это не так, то обязательно должны быть выбраны числа 2k − и 2k. Другие k выбранных чисел находятся на отрезке от 1 до 2k − Разбивая этот отрезок на пары (1, 2k − 2), (2, 2k − 3), . . . , (k − 1, получаем, что одна из пар состоит из выбранных чисел. Но тогда они дают в сумме 2k − 1. Если число 1002 заменить на 1001, то утверждение перестанет быть верным. Примером может служить набор 1000,
1001
, . . . , 2000.
2.30
. Пусть в турнире участвуют n команд. Тогда разыгрывается n(n − очков. Команды могли набрать разное количество очков, 1, . . . , n − 1) лишь после окончания турнира. Поэтому предпоследняя команда набрала 1 очко и обязана была проиграть победителю. Пусть доска раскрашена в два цвета. Рассмотрим произвольный столбец. Один из цветов встречается в нем бесконечное число раз.
Зафиксируем этот цвет. Вычеркнем из таблицы все строчки, которые в выбранном столбце не содержат зафиксированный цвет. Покажите,
что в оставшейся таблице можно найти четыре нужные клетки. Для решения задачи с произвольным числом цветов, примените индукцию. Рассмотрим произвольную из 6-ти данных точек. По крайней мере 3 отрезка, выходящие из этой точки, окрашены в один цвет. Можно считать эти отрезки синими. Если два из их концов соединены отрезком синего цвета, то нужный треугольник найден. Если это не так, то концы отрезков образуют треугольник красного цвета. Рассмотрим n последовательностей, 2, 4, 8, . . . , 2
k
, . . .
},
{3, 6, 12, 24, . . . , 3 · 2
k
, . . .
},
{2n − 1, (2n − 1)2, (2n − 1)4, . . . , (2n − 1) · 2
k
, . . Каждая из них имеет ровно один элемент на отрезке [n + 1; Значит, из (n + го выбранного числа хотя бы два окажутся водной и той же последовательности. 17!.
2.38
. 8!.
2.39
. 16!.
2.40
. 16!/2.
2.41
. 28 · 6! · 1111111.
2.42
. а) б) 28! − 27 · 2 · 26!.
2.43
. C
4 9

Ответы, указания, решения. C
4 28
, C
3 27 2.45
. 2 · C
7 10
+ 1
· C
6 10 2.46
. C
2
n
2.47
. C
2
n
2.48
. C
2
n
· C
2
m
2.49
. По условию задачи, любые 5 человек сейф открыть не могут.
Значит у них нет ключа от некоторого замка. При этом любой другой член комиссии должен этот ключ иметь. Поэтому нужно поставить C
5 замков. 4 ключа от каждого замка отдаются некоторой четверке членов комиссии, причем разные ключи раздаются разным четверкам. При этом, если соберутся 6 человек, то среди них будет по представителю из каждой четверки и они смогут открыть все замки.
В общем случае понадобится C
m−1
n замков и n − m + 1 ключ к каждому из них. C
5 7
· C
5 9
2.54
. а) б) 51.
2.55
. Рассмотрите n = 2a − 1.
2.56
. баб) в) где. Каждому маршруту можно поставить в соответствие слово,
состоящее из m букв «x» и n букв «y» последующему правилу если делается шаг параллельно оси Ox, то пишем «x», если вдоль оси Oy, то пишем «y». Таких слов всего + n)!
m! n!
= C
m m+n
= C
n m+n
2.60
. Поставьте в соответствие каждому маршруту кузнечика слово,
в котором по 9 раз встречаются буквы x, y и z. Ответа б 4!
·
24!
(6!)
4 2.63
. Выбор множеств A и B равносилен приписыванию каждому элементу множества C одной из букв a, b или c. В обоих случаях ответ 3
n
2.65 32!
10!
· 10! · 10! · 2! · 2 2.66
. Каждому такому числу однозначно соответствует выбор 6-ти цифр из набора 9876543210. Ответ C
6 10

Ответы, указания, решения 2.67
. Из (m + й позиции (m − 1 место между белыми шарами и два места по краям) нужно выбрать n позиций, в которые будут положены черные шары. Ответа б) C
2 1002 2.71
. C
5 22 2.72
. 11 3
= C
0 3
10 3
+ C
1 3
10 2
+ C
2 3
10 1
+ C
3 3
10 0
, 11 4
= 14641 2.73
. 2 7
2.74
. В этой задаче возможны различные ответы. Можно, например, расположить сверху перевернутый треугольник Лейбница (смотрите задачу. Можно также доопределить биномиальные коэффициенты при отрицательных n при помощи равенства а) из задачи. При n = 2
k
− 1 2.76
. а) 3 б) в) 2
n
2.77
. а) Левая часть число способов выбрать m элементов из r, а потом из выбранных m выбрать еще k. Правая часть сразу выбираем элементов из r, а из оставшихся выбираем еще m − k.
2.79
. 36 шаров. x = 2, y = 3, n = 5.
2.81
. Примените жадный алгоритм. Сначала из n нужно вычесть наибольшее число вида C
3
z так, чтобы остаток был неотрицательным.
Из него нужно вычесть наибольшее число вида C
2
y
. То что останется всегда можно записать в виде C
1
x
2.82
. Общее число способов выбрать компанию из 3 человек равно 10
= 120
. Каждая ссора разрушает не более 8 таких компаний, поэтому число разрушенных компаний не больше 8 · 14 = 112. Значит осталось по крайней мере 8 дружных компаний. m = 3, n = 2.
2.84
. C
6 100 4(
√
3)
64 2.86
. 2 · 5! · 5!.
2.87
. Каждая точка пересечения диагоналей однозначно определяет четверку вершин, через которые проходят эти диагонали. Наоборот,
каждой четверке вершин соответствует ровно одна точка пересечения диагоналей. Поэтому число точек пересечения диагоналей T
n вычисляется по формуле T
n
= C
4
n
. Для нахождения K
n
— числа частей, на которые угольник разбивается диагоналями, нужно проверить равенство Ответы, указания, решения
Суммируя его по m в пределах от 2 до n, находим, что T
n+1
+
n(n − Отсюда C
4
n+1
+ C
2
n
=
n(n − 1)(n
2
− n + 10)
24 2.88
. Знаменатели чисел, расположенных в рядах гармонического треугольника, пропорциональны элементам треугольника Паскаля,
причем коэффициентами пропорциональности служат граничные члены. Там, где в треугольнике Паскаля стоит число C
k n
, в треугольнике
Лейбница находится + 1)C
k n
. Рекуррентная формула + 1)C
k−1
n
+
1
(n + 1)C
k n
=
1
n
· проверяется непосредственным вычислением. Для нахождения суммы достаточно сложить следующие равенства, которые следуют из рекуррентной формулы для треугольника
Лейбница (см. решение задачи 6
−
1 12
=
1 12
,
1 12
−
1 20
=
1 30
,
1 20
−
1 30
=
1 60
, . . Общая формула аналогична равенству из задачи
2.77
д).
2.91
. в − 1)!
· (r − 1)
2.92
. C
4 10
/C
4 25 2.93
. 5/90 = 1/18.
2.94
. а) 1/10 б) 1/10 2
2.96
. Да, может. a
1
+ a
2
+ . . . + a k
2.100
. 20.
2.101
. Пусть N
a
— количество треугольников, у которых одна из сторон параллельна стороне BC исходного треугольника. Аналогично определим числа N
b
, N
c
, N