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

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

нужно правильно набрать пятизначный номер. Каково наименьшее количество номеров нужно перебрать, чтобы наверняка открыть камеру?
(Числа 23 и 37 можно увидеть ив числе 237.)
2.12. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево (например, таких как 54345,
17071
)?
2.13. Сколько существует девятизначных чисел, сумма цифр которых четна. Сколькими способами можно разложить 7 монет различного достоинства потрем карманам. Назовем натуральное число симпатичным, если в его записи встречаются только нечетные цифры. Сколько существует четырехзначных симпатичных чисел. На двух клетках шахматной доски стоят черная и белая фишки. За один ход можно передвинуть любую из них на соседнюю по вертикали или по горизонтали клетку. (две фишки не могут стоять на одной клетке. Могут ли в результате таких ходов встретится всевозможные варианты расположения этих двух фишек, причем ровно по одному разу. Принцип Дирихле
Принцип Дирихле (принцип ящиков. При любом распределении или более предметов по n ящикам в каком-нибудь ящике окажется не менее чем k + 1 предмет. Докажите, что среди москвичей есть два человека с равным числом волос, если известно, что у любого человека на голове менее одного миллиона волос. В мешке 70 шаров, отличающихся только цветом 20 красных,
20
синих, 20 желтых, остальные — черные и белые. Какое наименьшее число шаров надо вынуть из мешка, не видя их, чтобы среди них было не менее 10-ти шаров одного цвета

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

16 2. Комбинаторика. В волейбольном турнире команды играют друг с другом по одному матчу. За победу дается одно очко, за поражение — ноль. Известно,
что в один из моментов турнира все команды имели разное количество очков. Сколько очков набрала в конце турнира предпоследняя команда и как она сыграла с победителем. Бесконечная клетчатая доска раскрашена в три цвета (каждая клеточка — в один из цветов. Докажите, что найдутся четыре клеточки одного цвета, расположенные в вершинах прямоугольника со сторонами, параллельными стороне одной клеточки. Докажите, что из 11 различных бесконечных десятичных дробей можно выбрать две такие, которые совпадают в бесконечном числе разрядов. На плоскости даны 6 точек так, что никакие три из них не лежат на одной прямой. Каждая пара точек соединена отрезком синего или красного цвета. Докажите, что среди данных точек можно выбрать такие три, что все стороны образованного ими треугольника будут окрашены в один цвет. (См. также. Докажите утверждение задачи
1.26
при помощи принципа
Дирихле.
3. Размещения, перестановки и сочетания
Определение. Пусть M =
{a
1
, . . . , a n
} — множество из n элементов. Наборы вида (a i
1
, . . . , a будем называть k-размещениями. Два размещения считаются различными, если они отличаются друг от друга входящими в них элементами или порядком элементов.
Если в размещениях элементы a i
1
, . . . , a i
k попарно различны, то это размещения без повторений. Если же среди элементов a i
1
, . . . , a могут попадаться одинаковые, то такие наборы называются размеще- ниями с повторениями.
Количества размещений без повторений и с повторениями обозначаются и A
k соответственно. Докажите равенства:
а) A
k n
= n(n − 1) . . . (n − k + б) ¯
A
k n
= n k
2.36. В пассажирском поезде 17 вагонов. Сколькими способами можно распределить по вагонам 17 проводников, если за каждым вагоном закрепляется один проводник?
Определение. Перестановками называются размещения без повторений элементов множества M =
{a
1
, . . . , a n
}.

3. Размещения, перестановки и сочетания
17
Количество перестановок множества из n элементов обозначается. Докажите равенство P
n
= n!
2.38. Сколько существует способов расставить 8 ладей на шахматной доске так, чтобы они не били друг друга. Семнадцать девушек водят хоровод. Сколькими различными способами они могут встать вкруг. Сколько существует ожерелий, составленных из 17 различных бусинок. Найдите сумму всех 7-значных чисел, которые можно получить всевозможными перестановками цифра) Сколькими способами 28 учеников могут выстроиться в очередь в столовую?
б) Как изменится это число, если Петю Иванова и Колю Васина нельзя ставить друг за другом. Сколькими способами можно выбрать четырех человек на четыре различные должности, если имеется девять кандидатов на эти должности. Из класса, в котором учатся 28 человек, назначаются на дежурство в столовую 4 человека. Сколькими способами это можно сделать Сколько существует способов набрать команду дежурных, в которую попадет ученик этого класса Коля Васин?
Определение. Пусть M =
{a
1
, . . . , a n
} — множество из n элементов. сочетаниями называются наборы (a i
1
, . . . , a i
k
)
, в которых порядок считается несущественным. То есть два сочетания считаются различными, если они отличаются друг от друга входящими в них элементами, ноне порядком элементов.
Аналогично размещениям сочетания бывают без повторений и с по- вторениями.
Количества сочетаний без повторений и с повторениями обозначаются и C
k соответственно. Из двух математиков и десяти экономистов надо составить комиссию из восьми человек. Сколькими способами можно составить комиссию, если в нее должен входить хотя бы один математик. На плоскости дано n точек. Сколько имеется отрезков с концами в этих точках. На плоскости проведено n прямых общего положения. Найдите количество точек пересечения этих прямых. Сколько треугольников образуют эти прямые

18 2. Комбинаторика. На двух параллельных прямых a и b выбраны точки A
1
,
A
2
, . . . , A
m и B
1
, B
2
, . . . , B
n соответственно. Сколько будет точек пересечения, если провести все отрезки вида A
i
B
j
(1 6 i 6 m, 1 6 j 6 при условии, что никакие три из этих отрезков водной точке не пересекаются. Ключи от сейфа. Международная комиссия состоит из человек. Материалы комиссии хранятся в сейфе. Сколько замков должен иметь сейф, сколько ключей для них нужно изготовить и каких разделить между членами комиссии, чтобы доступ к сейфу был возможен тогда и только тогда, когда соберутся не менее 6 членов комиссии?
Рассмотрите задачу также в том случае, когда комиссия состоит из человека сейф можно открыть при наличии m членов комиссии 6 n).
2.50. У Нины 7 разных шоколадных конфету Коли 9 разных карамелек. Сколькими способами они могут обменяться друг с другом пятью конфетами. Докажите равенства а) C
k n
=
n!
(n − k)! б) C
k n
= C
k n+k−1
=
(n + k − 1)!
(n − 1)! k!
2.52. Докажите, что биномиальный коэффициент C
k можно определить как количество способов выбрать элементное подмножество в множестве из n элементов. Бином Ньютона. Докажите справедливость формулы + y)
n
= C
0
n x
n
+ C
1
n x
n−1
y + C
2
n x
n−2
y
2
+ . . . + C
n n
y Числа C
k называются биномиальными коэффициентами, поскольку они возникают при возведении в степень бинома x + y.
2.54. Сколько рациональных слагаемых содержится в разложении а) (
√
2 +б) (
√
2 +
3
√
3)
300
?
2.55
*
. Докажите, что для любого натурального a найдется такое натуральное n, что все числа n + 1, n n
+ 1
, n n
n
+ 1
, . . . делятся на a.
2.56. Сколько диагоналей имеет выпуклый:
а) 10-угольник;

б) угольник (k > 3)?
2.57. В выпуклом угольнике проведены все диагонали. Они разбивают его на выпуклые многоугольники. Возьмем среди них многоугольник с самым большим числом сторон. Сколько сторон он может иметь

3. Размещения, перестановки и сочетания 2.58. Анаграммы. Анаграммой называется произвольное слово,
полученное изданного слова перестановкой букв. Сколько анаграмм можно составить из слова) точка;
б) прямая;
в) перешеек;
г) биссектриса д) абракадабра;

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

б) множество A содержалось бы в множестве B?
2.64. Полиномиальная теорема. Докажите, что в равенстве+ . . . + x m
)
n
=
X
k
1
+...+k m
=n
C(k
1
, . . . , k m
)x k
1 1
. . . x k
m коэффициенты C(k
1
, . . . , k могут быть найдены по формуле, . . . , k m
) =
n!
k
1
!
· . . . · k Числа C(k
1
, . . . , k называются полиномиальными коэффициентами

20 2. Комбинаторика. При игре в преферанс каждому из трех игроков раздают по
10
карт, а две карты кладут в прикуп. Сколько различных раскладов возможно в этой игре (Считаются возможные раздачи без учета того, что каждые 10 карт достаются конкретному игроку) (См. также. Сколько существует 6-значных чисел, у которых каждая последующая цифра меньше предыдущей. Имеется m белых и n черных шаров, причем m > n. Сколькими способами можно все шары разложить вряд так, чтобы никакие два черных шара не лежали рядом (См. также. Шесть ящиков занумерованы числами от 1 до 6. Сколькими способами можно разложить по этим ящикам 20 одинаковых шаров так,

чтобы ни один ящик не оказался пустым?
Сколькими способами можно разложить n одинаковых шаров по m
(n > m) пронумерованным ящикам так, чтобы ни один ящик не оказался пустым. Шесть ящиков занумерованы числами от 1 до 6. Сколькими способами можно разложить по этим ящикам 20 одинаковых шаров (на этот раз некоторые ящики могут оказаться пустыми. Сколько решений имеет уравнение x
1
+ x
2
+ x
3
= а) в натуральных;

б) в целых неотрицательных числах?
(См. также. Сколькими способами можно составить букет из 17 цветков,

если в продаже имеются гвоздики, розы, гладиолусы, ирисы, тюльпаны и васильки?
Определение. Биномиальные коэффициенты удобно располагать в виде таблицы, которая называется треугольником Паскаля 0
C
0 1
C
1 1
C
0 2
C
1 2
C
2 2
C
0 3
C
1 3
C
2 3
C
3 3
1 1
1 1
2 1
1 3
3 Он обладает самыми разнообразными свойствами (см. задачи

3. Размещения, перестановки и сочетания 2.72. Почему равенства 11 2
= и 11 3
= похожи на строчки треугольника Паскаля Чему равно 11 4
?
2.73. Сколькими способами двигаясь последующей таблице от буквы к букве кв в
а а
а д
д д
д р
р р
р р
а а
а а
а ат т
т т
т т
т можно прочитать слово квадрат. Придумайте какой-нибудь способ достроить треугольник Паскаля вверх. При каких значениях n все коэффициенты в разложении бинома Ньютона (a + b)

n нечетны?
2.76. Вычислите суммы:
а) C
0 5
+ 2C
1 5
+ 2 2
C
2 5
+ . . . + 2 5
C
5 б) C
0
n
− C
1
n
+ . . . + (−1)
n
C
n в) C
0
n
+ C
1
n
+ . . . + C
n n
2.77. Докажите тождества:
а) C
m r
C
k m
= C
k r
C
m−k б) C
m+1
n+1
= C
m n
+ в) C
n
2n
= (C
0
n
)
2
+ (C
1
n
)
2
+ . . . + (C
n г) C
k n+m
= C
0
n
C
k m
+ C
1
n
C
k−1
m
+ . . . + C
k д) C
k n
= C
k−1
n−1
+ C
k−1
n−2
+ . . . + Попробуйте доказать эти тождества тремя разными способами:
пользуясь тем, что C
k n
— это количество элементных подмножеств в множестве из n элементов исходя из того, что C
k n
— это коэффициент при x у многочлена (1 + x)
n
; пользуясь шахматным городом из задачи 2.78. Свойство шестиугольника. Докажите равенство C
k+1
n
· C
k n+1
= C
k n−1
· C
k+1
n+1
· C
k−1
n
2.79. 120 одинаковых шаров плотно уложены в виде правильной треугольной пирамиды. Сколько шаров лежит в основании. В разложении (x + y)
n по формуле бинома Ньютона второй член оказался равен 240, третий — 720, а четвертый — 1080. Найдите x,
y и n.

22 2. Комбинаторика. Биномиальная система счисления. Покажите, что любое целое неотрицательное число n может быть представлено в виде n = C
1
x
+ C
2
y
+ где x, y, z — целые числа такие, что 0 6 x < y < z.
2.82. В компании из 10 человек произошло 14 попарных ссор. Докажите, что все равно можно составить компанию из трех друзей. Найдите m и n зная, что C
m n+1
: C
m−1
n+1
= 5 : 5 : 3.
2.84. Какое слагаемое в разложении (1 +по формуле бинома
Ньютона будет наибольшим. Сколько четырехзначных чисел можно составить, используя цифры 1, 2, 3, 4 и 5, если:
а) никакая цифра не повторяется более одного раза;
б) повторения цифр допустимы;
в) числа должны быть нечетными и повторений цифр быть не должно. Сколько существует различных возможностей рассадить юношей и 5 девушек за круглый стол с ю креслами так, чтобы они чередовались. В выпуклом угольнике проведены все диагонали. Известно,
что никакие три из них не пересекаются водной точке. Насколько частей разделится при этом многоугольник Во скольких точках пересекутся диагонали. Гармонический треугольник Лейбница 1
1 2
1 2
1 3
1 6
1 3
1 4
1 12 1
12 1
4 1
5 1
20 1
30 1
20 1
5 1
6 1
30 1
60 1
60 1
30 Здесь изображен фрагмент таблицы, которая называется треугольником Лейбница. Его свойства аналогичны в смысле противоположности свойствам треугольника Паскаля. Числа на границе треугольника обратны последовательным натуральным числам. Каждое число

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

24 2. Комбинаторика есть гиппопотамы. Наконец, во всех зоопарках, где есть гиппопотамы и жирафы, есть и носороги. Может ли существовать такой зоопарк, в котором есть гиппопотамы, нонет ни жирафов, ни носорогов. Двоечники. В классе имеется учеников, получивших в течение года хотя бы одну двойку, учеников, получивших не менее двух двоек, и т. д, a учеников, получивших не менее k двоек. Сколько всего двоек в этом классе (Предполагается, что ни у кого нет более k двоек. Пусть имеется n подмножеств A
1
, . . . , A
n конечного множества
E
и χ
j
(x)
— характеристические функции этих множеств, то есть) =

1,
x
∈ A
j
,
0,
x
∈ E
\ A
j
(j = 1, . . . , Докажите, что при этом χ(x) — характеристическая функция множества, связана с функциями χ
1
(x)
, . . . , формулой − χ(x) = (1 − χ
1
(x)) . . . (1 − χ
n
(x)).
2.99. Формула включений и исключений. Докажите справедливость равенства A
2
∪ . . . ∪ A
n
| = |A
1
| + . . . + |A
n
| − |A
1
∩ A
2
| −
−
|A
1
∩ A
3
| − . . . − |A
n−1
∩ A
n
| + . . . + (−1)
n−1
|A
1
∩ A
2
∩ . . . ∩ где через обозначено количество элементов множества A. (См. также. Из 100 студентов университета английский язык знают студентов, немецкий — 30, французский — 42, английский и немецкий, английский и французский — 10, немецкий и французский — все три языка знают 3 студента. Сколько студентов не знают ни одного из трех языков. Каждая сторона в треугольнике ABC разделена на 8 равных отрезков. Сколько существует различных треугольников с вершинами в точках деления (точки A, B, C не могут быть вершинами треугольников, у которых ни одна сторона не параллельна ни одной из сторон треугольника ABC?
2.102. Сколько существует целых чисел от 1 до 16 500, которые а) не делятся наб) не делятся ни на 5 ни на вне делятся ни на 5 ни на 3, ни на 11?

5. Числа Каталана