Реферат: Связь комбинаторики с различными разделами математики

--PAGE_BREAK--а) Вокруг каждой из трёх осей, соединяющих центры противоположных граней, имеется три вращения на углы <shape id="_x0000_i1078" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image053.wmz» o:><img width=«17» height=«41» src=«dopb64058.zip» v:shapes="_x0000_i1078">, <shape id="_x0000_i1079" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image055.wmz» o:><img width=«15» height=«15» src=«dopb64059.zip» v:shapes="_x0000_i1079">, <shape id="_x0000_i1080" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image057.wmz» o:><img width=«25» height=«41» src=«dopb64060.zip» v:shapes="_x0000_i1080">. Им соответствуют перестановки:
1) (1, 5, 8, 4) (2, 6, 7, 3)
2) (1, 8) (2, 7) (3, 6) (4, 5)
3) (1, 4, 8, 5) (2, 3, 7, 6)
4) (1, 4, 3, 2) (5, 8, 7, 6)
5) (1, 3) (2, 4) (5, 7) (6, 8)
6) (1, 2, 3, 4) (5, 6, 7, 8)
7) (1, 5, 6, 2) (3, 4, 8, 7)
8) (1, 6) (2, 5) (3, 8) (4, 7)
9) (1, 2, 6, 5) (3, 7, 8, 4)
б) Вокруг каждой из четырёх диагоналей куба имеется по два вращения. Им соответствуют перестановки:
10) (1) (2, 5, 4) (3, 6, 8) (7)
11) (2) (1, 3, 6) (4, 7, 5) (8)
12) (3) (1, 6, 8) (2, 7, 4) (5)
13) (4) (1, 3, 8) (2, 7, 5) (6)
14) (1) (2, 4, 5) (3, 8, 6) (7)
15) (2) (1, 6, 3) (4, 5, 7) (8)
16) (3) (1, 8, 6) (2, 4, 7) (5)
17) (4) (1, 8, 3) (2, 5, 7) (6)
в) Вокруг каждой из шести осей, соединяющих середины противоположных рёбер куба, имеется одно вращение. Им соответствуют перестановки:
18) (1, 5) (2, 8) (3, 7) (4, 6)
19) (1, 2) (3, 5) (4, 6) (7, 8)
20) (1, 7) (2, 3) (4, 6) (5, 8)
21) (1, 7) (2, 6) (3, 5) (4, 8)
22) (1, 7) (2, 8) (3, 4) (5, 6)
23) (1, 4) (2, 8) (3, 5) (6, 7)
Вместе с тождественной перестановкой (1)(2)(3)(4)(5)(6)(7)(8) получаем 24 перестановки – все элементы группы G. Итак, в группе Gвращений куба имеется:
1 перестановка типа <1, 1, 1, 1, 1, 1, 1, 1>,
6 перестановок типа <4, 4>,
9 перестановок типа <2, 2, 2, 2>,
8 перестановок типа <1, 1, 3, 3>.
Тогда перестановка первого типа имеет 38 неподвижных точек, любая из перестановок второго типа – 32, третьего и четвёртого типов – 34 неподвижных точек (по формуле <shape id="_x0000_i1081" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image059.wmz» o:><img width=«16» height=«21» src=«dopb64061.zip» v:shapes="_x0000_i1081">nk = nk). Поэтому согласно лемме Бернсайда, имеем <shape id="_x0000_i1082" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image061.wmz» o:><img width=«79» height=«48» src=«dopb64062.zip» v:shapes="_x0000_i1082">(38 + 6∙32 + 9∙34 + 8∙34) = 333.
Таким образом, число геометрически различимых способов раскраски вершин куба в три цвета равно 333.
Задача 2. Сколько различных ожерелий из семи бусин можно составить из бусин двух цветов – красного и синего?
Решение. Переформулируем эту задачу следующим равносильным образом: сколькими геометрически различными способами можно раскрасить вершины правильного семиугольника в два цвета? Пусть М – множество всевозможных по-разному раскрашенных правильных семиугольников одного размера, положение которых в пространстве фиксировано. Тогда имеется 27 = 128 различных вариантов раскраски вершин семиугольника, так как каждую вершину независимо от других можно раскрасить двумя способами. Здесь два способа раскраски неотличимы, если один из них можно получить из другого, применяя к семиугольнику либо преобразования вращения, либо симметрии относительно осей. Будем описывать раскраски «словами» длины 7, составленными из букв к (вершина окрашена в красный цвет) и с (вершина окрашена в синий цвет). Проделаем те же действия, что и в задаче 1 для применения леммы Бернсайда. Опишем разложения в произведение циклов для всех перестановок из группы G.
а) Тождественному преобразованию соответствует перестановка:
1) (1)(2)(3)(4)(5)(6)(7)
б) Поворотам на углы <shape id="_x0000_i1083" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image063.wmz» o:><img width=«181» height=«41» src=«dopb64063.zip» v:shapes="_x0000_i1083"> соответствуют перестановки:
2) (1,2,3,4,5,6,7)
3) (1,3,5,7,2,4,6)
4) (1,4,7,3,6,2,5)
5) (1,5,2,6,3,7,4)
6) (1,6,4,2,7,5,3)
7) (1,7,6,5,4,3,2)
в) Симметриям относительно осей, соединяющих вершины семиугольника с серединами противоположных сторон, соответствуют перестановки:
8) (1) (2,7) (3,6) (4,5)
9) (2) (1,3) (7,4) (5,6)
10) (3) (2,4) (1,5) (6,7)
11) (4) (3,5) (2,6) (7,1)
12) (5) (4,6) (3,7) (2,1)
13) (6) (5,7) (4,1) (2,3)
14) (7) (1,6) (2,5) (3,4),
где 1, 2, 3, 4, 5, 6, 7 – числа, с помощью которых занумерованы вершины семиугольника.
Итак, в группе G имеется:
1 перестановка типа <1, 1, 1, 1, 1, 1, 1>,
6 перестановок типа <7>,
7 перестановок типа <1, 2, 2, 2>.
Слово неподвижно относительно перестановки <shape id="_x0000_i1084" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image047.wmz» o:><img width=«16» height=«19» src=«dopb64055.zip» v:shapes="_x0000_i1084"><shape id="_x0000_i1085" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image046.wmz» o:><img width=«13» height=«13» src=«dopb64034.zip» v:shapes="_x0000_i1085"><shape id="_x0000_i1086" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image049.wmz» o:><img width=«17» height=«23» src=«dopb64056.zip» v:shapes="_x0000_i1086"> тогда и только тогда, когда буквы, стоящие на местах с номерами из одного цикла в перестановке α, совпадают. Поэтому тождественная перестановка имеет 27 неподвижных точек на М, перестановки второго типа – по 2, а перестановки третьего типа – по 24. Применяя лемму Бернсайда, получаем
<shape id="_x0000_i1087" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image065.wmz» o:><img width=«79» height=«48» src=«dopb64064.zip» v:shapes="_x0000_i1087">(27 + 6∙2 + 7∙24) = 18.
Итак, из бусин двух цветов можно составить 18 семибусенных ожерелий.
Задача 3. Грани куба можно раскрасить: а) все в белый цвет; б) все в чёрный цвет; в) часть в белый, а остальные в чёрный. Сколько имеется разных способов раскраски?
Решение. <img width=«148» height=«149» src=«dopb64065.zip» v:shapes="_x0000_s1082 _x0000_s1083 _x0000_s1084 _x0000_s1085 _x0000_s1086 _x0000_s1087 _x0000_s1088 _x0000_s1089 _x0000_s1090 _x0000_s1091 _x0000_s1092 _x0000_s1093 _x0000_s1094 _x0000_s1095">
Грань (1' 4' 5' 8') – 1
Грань (2' 3' 6' 7') – 2
Грань (3' 4' 7' 8') – 3
Грань (1' 2' 5' 6') – 4
Грань (1' 2' 3' 4') – 5
Грань (5' 6' 7' 8') – 6
Рис. 3
а) Вокруг каждой из трёх осей, соединяющих центры противоположных граней, имеется три вращения на углы <shape id="_x0000_i1088" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image053.wmz» o:><img width=«17» height=«41» src=«dopb64058.zip» v:shapes="_x0000_i1088">, <shape id="_x0000_i1089" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image055.wmz» o:><img width=«15» height=«15» src=«dopb64059.zip» v:shapes="_x0000_i1089">, <shape id="_x0000_i1090" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image057.wmz» o:><img width=«25» height=«41» src=«dopb64060.zip» v:shapes="_x0000_i1090">. Им соответствуют перестановки:
1) (1) (2) (5, 4, 6, 3)
2) (1) (2) (4, 3) (6, 5)
3) (1) (2) (5, 3, 6, 4)
4) (3) (4) (1, 6, 2, 5)
5) (3) (4) (1, 2) (6, 5)
6) (3) (4) (5, 2, 6, 1)
7) (5) (6) (1, 3, 2, 4)
8) (5) (6) (1, 2) (3, 4)
9) (5) (6) (4, 2, 3, 1)
б) Вокруг каждой из четырёх диагоналей куба имеется по два вращения. Им соответствуют перестановки:
10) (2, 6, 3) (1, 5, 4)
11) (3, 6, 2) (4, 5, 1)
12) (6, 4, 2) (1, 5, 3)
13) (2, 4, 6) (3, 5, 1)
14) (1, 3, 6) (2, 4, 5)
15) (6, 3, 1) (5, 4, 2)
16) (1, 4, 6) (2, 3, 5)
17) (6, 4, 1) (5, 3, 2)
в) Вокруг каждой из шести осей, соединяющих середины противоположных рёбер куба, имеется одно вращение. Им соответствуют перестановки:
18) (2, 3) (1, 4) (5, 6)
19) (1, 3) (4, 2) (5, 6)
20) (1, 6) (5, 2) (3, 4)
21) (1, 5) (6, 2) (3, 4)
22) (4, 6) (3, 5) (1, 2)
23) (6, 3) (5, 4) (1, 2)
Вместе с тождественной перестановкой (1)(2)(3)(4)(5)(6) получаем 24 перестановки – все элементы группы G. Итак, в группе Gвращений куба имеется:
1 перестановка типа <1, 1, 1, 1, 1, 1>,
6 перестановок типа <1, 1, 4>,
3 перестановки типа <1, 1, 2, 2>,
8 перестановок типа <3, 3>,
6 перестановок типа <2, 2, 2>.
Поэтому тождественная перестановка имеет 26 неподвижных точек на М, перестановки второго и пятого типов имеют по 23 неподвижных точек на М, перестановки третьего типа – по 24, а перестановки четвёртого типа – по 22. Тогда по лемме Бернсайда получаем  <shape id="_x0000_i1091" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image068.wmz» o:><img width=«79» height=«48» src=«dopb64062.zip» v:shapes="_x0000_i1091">(26 + 6∙23+ 3∙24+ 8∙22 + 6∙23) =10.
Итак, число геометрически различных способов раскраски граней куба в два цвета равно 10.
Задача 4. Сколько различных ожерелий можно составить из двух синих, двух белых и двух красных бусин?
Решение. Переформулируем задачу так: сколькими геометрически различными способами можно раскрасить вершины правильного шестиугольника так, чтобы две были синего цвета, две – белого, две – красного? а) Вокруг центра шестиугольника имеется пять поворотов на углы <shape id="_x0000_i1092" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image069.wmz» o:><img width=«119» height=«41» src=«dopb64066.zip» v:shapes="_x0000_i1092">. Им соответствуют перестановки:
1) (1, 2, 3, 4, 5, 6)
2) (1, 3, 5) (2, 4, 6)
3) (1, 4) (2, 5) (3, 6)
4) (1, 5, 3) (2, 6, 4)
5) (1, 6, 5, 4, 3, 2)
б) Имеется три симметрии относительно осей, соединяющих противоположные вершины правильного шестиугольника. Им соответствуют перестановки:
6) (1) (4) (2, 6) (3, 5)
7) (2) (5) (3, 1) (4, 6)
8) (3) (6) (2, 4) (1, 5)
в) Имеется три симметрии относительно осей, соединяющих середины противоположных сторон правильного шестиугольника. Им соответствуют перестановки:
9) (1, 2) (6, 3) (5, 4)
10) (1, 6) (2, 5) (3, 4)
11) (2, 3) (1, 4) (6, 5)
Вместе с тождественной перестановкой (1) (2) (3) (4) (5) (6) получаем 12 перестановок – все элементы группы G. Итак, в группе G имеется:
1 перестановка типа <1, 1, 1, 1, 1, 1>,
2 перестановки типа <6>,
2 перестановки типа <3, 3>,
4 перестановки типа <2, 2, 2>,
3 перестановки типа <1, 1, 2, 2>.
Определим количество неподвижных точек для перестановок каждого типа. Так как количество различных цветов, в которые нужно раскрасить шестиугольник, равно трём, то минимальное количество циклов в перестановке должно быть равно трём, чтобы она имела неподвижные точки. То есть перестановки 1), 2), 4), 5) неподвижных точек не имеют. Для перестановки первого типа получим <shape id="_x0000_i1093" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image059.wmz» o:><img width=«16» height=«21» src=«dopb64061.zip» v:shapes="_x0000_i1093">36 = <shape id="_x0000_i1094" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image071.wmz» o:><img width=«53» height=«52» src=«dopb64067.zip» v:shapes="_x0000_i1094"> = 90 неподвижных точек. Для каждой перестановки типа <2, 2, 2> по принципу умножения получаем по Р3 =3∙2∙1= 6 неподвижных точек. Для каждой перестановки типа <1, 1, 2, 2> по принципу умножения получим по Р3 =3∙2∙1∙1= 6 неподвижных точек. Применим лемму Бернсайда: <shape id="_x0000_i1095" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image073.wmz» o:><img width=«79» height=«47» src=«dopb64068.zip» v:shapes="_x0000_i1095">(1∙90+ 4∙6+ 3∙6) = 11.
Итак, 11 различных ожерелий можно составить из двух синих, двух белых, двух красных бусин.
Задача 5. Сколькими геометрически различными способами три абсолютно одинаковые мухи могут усесться в вершинах правильного пятиугольника?
Решение. Обозначим М – множество различных способов расположения трёх одинаковых мух в вершинах пятиугольника, если вершины занумерованы. Тогда |M| = <shape id="_x0000_i1096" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image059.wmz» o:><img width=«16» height=«21» src=«dopb64061.zip» v:shapes="_x0000_i1096">25 (3, 2)=<shape id="_x0000_i1097" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image075.wmz» o:><img width=«41» height=«52» src=«dopb64069.zip» v:shapes="_x0000_i1097">=10 способов расположения мух, где 2 – количество элементов множества М1 = {м, с} (где м – муха, с – свободная вершина),
3, 2 – кратности соответственно м и с.
а) Вокруг центра пятиугольника имеется четыре поворота на углы <shape id="_x0000_i1098" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image077.wmz» o:><img width=«111» height=«41» src=«dopb64070.zip» v:shapes="_x0000_i1098">. Им соответствуют перестановки:
1) (1, 2, 3, 4, 5)
2) (1, 3, 5, 2, 4)
3) (1, 4, 2, 5, 3)
4) (1, 5, 4, 3, 2)
б) Имеется пять симметрий относительно осей, соединяющих вершины пятиугольника с серединами противоположных сторон. Им соответствуют перестановки:
5) (1) (2, 5) (3, 4)
6) (2) (1, 3) (5, 4)
7) (3) (2, 4) (1, 5)
8) (4) (3, 5) (2, 1)
9) (5) (1, 4) (2, 3),
где 1, 2, 3, 4, 5 – числа, с помощью которых занумерованы вершины пятиугольника. Вместе с тождественной перестановкой (1)(2)(3)(4)(5) имеем 10 элементов группы G. Итак, в группе G имеется:
1 перестановка типа <1, 1, 1, 1, 1>,
4 перестановки типа <5>,
5 перестановок типа <1, 2, 2>.
Определим количество неподвижных точек для перестановок каждого типа. Чтобы перестановка имела неподвижные точки, минимальное количество циклов в перестановке должно быть равно двум, так как множество М1 состоит из двух элементов м и с. Поэтому перестановки 1) – 4) не имеют неподвижных точек. Тогда для перестановки типа <1, 1, 1, 1, 1> имеем по формуле: <shape id="_x0000_i1099" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image059.wmz» o:><img width=«16» height=«21» src=«dopb64061.zip» v:shapes="_x0000_i1099">25(3, 2) = <shape id="_x0000_i1100" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image075.wmz» o:><img width=«41» height=«52» src=«dopb64069.zip» v:shapes="_x0000_i1100">= 10 неподвижных точек. Для каждой перестановки типа <1, 2, 2> получим по принципу умножения по Р2 =2∙1∙1= 2 неподвижные точки. По лемме Бернсайда получаем <shape id="_x0000_i1101" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image079.wmz» o:><img width=«77» height=«48» src=«dopb64071.zip» v:shapes="_x0000_i1101">(1∙10+ 5∙2) = 2.
Итак, двумя геометрически различными способами три одинаковые мухи могут усесться в вершинах правильного пятиугольника.
Задача 6. Сколькими способами можно раскрасить вершины куба в два цвета (красный и синий) так, чтобы вершин каждого цвета было поровну?
Решение. Для решения этой задачи воспользуемся задачей 1. Пусть М – множество всевозможных по-разному раскрашенных кубов одного размера, положение которых в пространстве фиксировано. Тогда по формуле <shape id="_x0000_i1102" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image059.wmz» o:><img width=«16» height=«21» src=«dopb64061.zip» v:shapes="_x0000_i1102">nk(k1, k2, …, kn) = <shape id="_x0000_i1103" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image081.wmz» o:><img width=«99» height=«52» src=«dopb64072.zip» v:shapes="_x0000_i1103"> получим |M| = <shape id="_x0000_i1104" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image059.wmz» o:><img width=«16» height=«21» src=«dopb64061.zip» v:shapes="_x0000_i1104">28(4,4) = <shape id="_x0000_i1105" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image083.wmz» o:><img width=«41» height=«52» src=«dopb64073.zip» v:shapes="_x0000_i1105">= 70 по-разному раскрашенных кубов. Так как нам нужно раскрасить вершины в два цвета (4 — в красный, 4 — в синий), то минимальное количество циклов в перестановке должно быть равно двум. Поэтому все перестановки 1) – 24) (задача 1) имеют неподвижные точки. В результате в группе Gимеется:
1 перестановка типа <1, 1, 1, 1, 1, 1, 1, 1>,
6 перестановок типа <4, 4>,
9 перестановок типа <2, 2, 2, 2>,
8 перестановок типа <1, 1, 3, 3>.
Тогда перестановка типа <1, 1, 1, 1, 1, 1, 1, 1> имеет <shape id="_x0000_i1106" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image059.wmz» o:><img width=«16» height=«21» src=«dopb64061.zip» v:shapes="_x0000_i1106">28(4,4) = <shape id="_x0000_i1107" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image085.wmz» o:><img width=«41» height=«52» src=«dopb64073.zip» v:shapes="_x0000_i1107">= 70 неподвижных точек. Каждая перестановка типа <4, 4> имеет (по принципу умножения Р2 =2∙1= 2 неподвижные точки. Для каждой перестановки типа <2, 2, 2, 2> имеется <shape id="_x0000_i1108" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image059.wmz» o:><img width=«16» height=«21» src=«dopb64061.zip» v:shapes="_x0000_i1108">24(2, 2) = <shape id="_x0000_i1109" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image086.wmz» o:><img width=«138» height=«98» src=«dopb64074.zip» v:shapes="_x0000_i1109">= 6 неподвижных точек. Каждая перестановка типа <1, 1, 3, 3> имеет (по принципу умножения) Р2 =2∙1∙2∙1= 4 неподвижные точки. По лемме Бернсайда получаем <shape id="_x0000_i1110" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image088.wmz» o:><img width=«79» height=«48» src=«dopb64062.zip» v:shapes="_x0000_i1110">(1∙70+ 6∙2 + 9∙6 + 8∙4) = 7.
Итак, семью способами можно раскрасить вершины куба в два цвета так, чтобы вершин каждого цвета было поровну.
Задача 7. Сколькими различными способами можно грани куба раскрасить в четыре цвета так, чтобы все четыре цвета присутствовали в раскраске каждого куба?
Решение. Для решения этой задачи воспользуемся задачей 3. Пусть М – множество всевозможных по-разному раскрашенных кубов одного размера, положение которых в пространстве фиксировано. Тогда по принципу умножения: первую грань можно раскрасить 4 способами, вторую – тремя, третью – двумя, четвёртую – одним способом, пятую – четырьмя, шестую – четырьмя способами. Получим |M| = 4∙3∙2∙1∙4∙4 = 384. Найдём геометрически различные способы раскраски. Для этого используем описанные в задаче 3 разложения в произведение циклов всех перестановок из группы G вращений куба. Так как в раскраске куба должны присутствовать четыре разных цвета, то минимальное количество циклов в перестановке должно быть равно четырём. Поэтому перестановки 1), 3), 4), 6), 7), 9) – 23) в задаче 3 неподвижных точек не имеют. Таким образом, неподвижные точки имеют 3 перестановки типа <1, 1, 2, 2> и 1 перестановку типа <1, 1, 1, 1, 1, 1>. Определим количество неподвижных точек для перестановок каждого типа. Для перестановки типа  <1, 1, 1, 1, 1, 1> имеем по принципу умножения Р4 = 4∙3∙2∙1∙4∙4 = 384 неподвижные точки. Для каждой перестановки типа <1, 1, 2, 2> по принципу умножения имеется Р4 = 4∙3∙2∙1 = 24 неподвижные точки. По лемме Бернсайда получаем <shape id="_x0000_i1111" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image089.wmz» o:><img width=«69» height=«41» src=«dopb64075.zip» v:shapes="_x0000_i1111">(1∙384+3∙24) = 19.
Итак, существует 19 различных способов раскраски граней куба в 4 цвета так, чтобы все 4 цвета присутствовали в раскраске каждого куба.

§ 2. «Метод просеивания» [4] Познакомимся с наиболее общим методом пересчёта, который можно назвать «методом просеивания» или «комбинаторным просеиванием»: с любым свойством P можно связать его расщепление на некотором множестве A, в соответствии с которым A разбивается на две части: подмножество А1, образованное элементами, обладающими свойством Р, и А2, образованное элементами, не обладающими свойством Р, т. е. обладающими свойством <shape id="_x0000_i1112" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image091.wmz» o:><img width=«19» height=«21» src=«dopb64076.zip» v:shapes="_x0000_i1112">. Выбирая свойства подходящим образом, можно последовательным просеиванием пересчитать подмножества с наложенными на них теми или иными ограничениями.
2.1. Формула включения и исключения
Пусть А – конечное множество и <shape id="_x0000_i1113" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image093.wmz» o:><img width=«61» height=«25» src=«dopb64077.zip» v:shapes="_x0000_i1113">. Будем обозначать через <shape id="_x0000_i1114" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image095.wmz» o:><img width=«24» height=«27» src=«dopb64078.zip» v:shapes="_x0000_i1114"> дополнение А1 по отношению к А, а через Card A – число элементов в А.
Тогда
<shape id="_x0000_i1115" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image097.wmz» o:><img width=«311» height=«27» src=«dopb64079.zip» v:shapes="_x0000_i1115">.
Если <shape id="_x0000_i1116" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image093.wmz» o:><img width=«61» height=«25» src=«dopb64077.zip» v:shapes="_x0000_i1116">и <shape id="_x0000_i1117" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image099.wmz» o:><img width=«64» height=«25» src=«dopb64080.zip» v:shapes="_x0000_i1117">, то
<shape id="_x0000_i1118" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image101.wmz» o:><img width=«351» height=«57» src=«dopb64081.zip» v:shapes="_x0000_i1118">                                         (1)
<shape id="_x0000_i1119" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image103.wmz» o:><img width=«392» height=«25» src=«dopb64082.zip» v:shapes="_x0000_i1119">.
Покажем, что формула (1) обобщается на случай nподмножеств <shape id="_x0000_i1120" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image105.wmz» o:><img width=«56» height=«25» src=«dopb64083.zip» v:shapes="_x0000_i1120">, i=1, 2,… n:
<shape id="_x0000_i1121" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image107.wmz» o:><img width=«499» height=«147» src=«dopb64084.zip» v:shapes="_x0000_i1121">             (2)
Действуем по индукции. Имеем
<shape id="_x0000_i1122" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image109.wmz» o:><img width=«477» height=«57» src=«dopb64085.zip» v:shapes="_x0000_i1122">                (3)
Предположим, что (2) выполняется для случая n-1 подмножеств Ai, i=1, 2,…,n-1:
<shape id="_x0000_i1123" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image111.wmz» o:><img width=«13» height=«25» src=«dopb64086.zip» v:shapes="_x0000_i1123"><shape id="_x0000_i1124" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image113.wmz» o:><img width=«488» height=«88» src=«dopb64087.zip» v:shapes="_x0000_i1124">             (4)
Рассмотрим следующие подмножества множества An:
<shape id="_x0000_i1125" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image115.wmz» o:><img width=«549» height=«57» src=«dopb64088.zip» v:shapes="_x0000_i1125">
Применяя (4) с A=An, имеем
<shape id="_x0000_i1126" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image117.wmz» o:><img width=«441» height=«119» src=«dopb64089.zip» v:shapes="_x0000_i1126">                         (5)
Подставляя (5) и (4) в (3), получаем (2). Таким образом, с учётом (1) формула (2) доказана по индукции. Эту формулу называют формулой включения и исключения. Часто её представляют в таком виде:
<shape id="_x0000_i1127" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image119.wmz» o:><img width=«488» height=«145» src=«dopb64090.zip» v:shapes="_x0000_i1127">               (6)
Формулы (2) и (6) играют основную роль в перечислении подмножеств, обладающих заданными свойствами. Посмотрим на эти формулы с другой точки зрения. Пусть элементы <shape id="_x0000_i1128" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image121.wmz» o:><img width=«56» height=«25» src=«dopb64083.zip» v:shapes="_x0000_i1128"> обладают свойством Pi, i=1, 2, …,n. Тогда мы скажем, что подмножество <shape id="_x0000_i1129" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image122.wmz» o:><img width=«149» height=«29» src=«dopb64091.zip» v:shapes="_x0000_i1129">обладает свойством <shape id="_x0000_i1130" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image124.wmz» o:><img width=«140» height=«29» src=«dopb64092.zip» v:shapes="_x0000_i1130">. Таким образом, если элементы А могут обладать n различными свойствами, то число элементов А, обладающих k указанными свойствами и не обладающих n-k остальными, дается формулой (6).
2.2. Общий метод «просеивания» или «пропускания через решето». Решето Сильва – Сильвестра
Формула (6) описывает последовательный процесс пересчёта, называемый решетом Сильва – Сильвестра.
    продолжение
--PAGE_BREAK--Пример. Рассмотрим множество
<shape id="_x0000_i1131" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image126.wmz» o:><img width=«120» height=«24» src=«dopb64093.zip» v:shapes="_x0000_i1131">
и следующие свойства:
<shape id="_x0000_i1132" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image128.wmz» o:><img width=«85» height=«25» src=«dopb64094.zip» v:shapes="_x0000_i1132">четное число,
<shape id="_x0000_i1133" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image130.wmz» o:><img width=«73» height=«25» src=«dopb64095.zip» v:shapes="_x0000_i1133"> и А >6,                                                                                    (7)
<shape id="_x0000_i1134" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image132.wmz» o:><img width=«72» height=«25» src=«dopb64096.zip» v:shapes="_x0000_i1134"> и 2 < A< 8.
Подсчитаем число элементов А, обладающих свойством <shape id="_x0000_i1135" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image134.wmz» o:><img width=«93» height=«27» src=«dopb64097.zip» v:shapes="_x0000_i1135">. Обозначим подмножества, соответствующие свойствам Р1, Р2, Р3, через А1, А2, А3. Тогда
<shape id="_x0000_i1136" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image136.wmz» o:><img width=«497» height=«54» src=«dopb64098.zip» v:shapes="_x0000_i1136">
«Просеиваем» сначала А через Р1: CardA1=6. Затем просеиваем А1 через Р2и Р3: <shape id="_x0000_i1137" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image138.wmz» o:><img width=«137» height=«25» src=«dopb64099.zip» v:shapes="_x0000_i1137">, <shape id="_x0000_i1138" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image140.wmz» o:><img width=«136» height=«25» src=«dopb64100.zip» v:shapes="_x0000_i1138">. Просеиваем <shape id="_x0000_i1139" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image142.wmz» o:><img width=«56» height=«25» src=«dopb64101.zip» v:shapes="_x0000_i1139"> через Р3: <shape id="_x0000_i1140" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image144.wmz» o:><img width=«181» height=«25» src=«dopb64102.zip» v:shapes="_x0000_i1140"> Итак, <shape id="_x0000_i1141" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image146.wmz» o:><img width=«295» height=«26» src=«dopb64103.zip» v:shapes="_x0000_i1141"> 
Формула (6) не позволяет, однако, перечислить элементы искомого множества. Находим его, выписывая последовательно: <shape id="_x0000_i1142" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image148.wmz» o:><img width=«137» height=«25» src=«dopb64104.zip» v:shapes="_x0000_i1142">, <shape id="_x0000_i1143" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image150.wmz» o:><img width=«140» height=«27» src=«dopb64105.zip» v:shapes="_x0000_i1143">, <shape id="_x0000_i1144" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image152.wmz» o:><img width=«156» height=«27» src=«dopb64106.zip» v:shapes="_x0000_i1144">. Разумеется, для множества с небольшим числом элементов проще выписать искомое подмножество, однако это трудно сделать при большой мощности множества.
2.3. Использование общего метода решета в теории чисел
Теорема 1. Пусть А={1, 2, …,n} и а1, а2, …, аr, <shape id="_x0000_i1145" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image154.wmz» o:><img width=«60» height=«25» src=«dopb64107.zip» v:shapes="_x0000_i1145">,  i=1, 2, …,r, попарно взаимно просты. Количество целых чисел kтаких, что 0 < k≤ n, aiне делит k, i=1, 2, …,r, равно
<shape id="_x0000_i1146" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image156.wmz» o:><img width=«452» height=«64» src=«dopb64108.zip» v:shapes="_x0000_i1146">                       (8)
Доказательство. Обозначим <shape id="_x0000_i1147" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image158.wmz» o:><img width=«137» height=«25» src=«dopb64109.zip» v:shapes="_x0000_i1147"> и выпишем формулу (2):
<shape id="_x0000_i1148" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image160.wmz» o:><img width=«439» height=«89» src=«dopb64110.zip» v:shapes="_x0000_i1148">                         (9)
Имеем
Card A=n,
Card Ai=<shape id="_x0000_i1149" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image162.wmz» o:><img width=«39» height=«55» src=«dopb64111.zip» v:shapes="_x0000_i1149">, i=1, 2, …,r,
<shape id="_x0000_i1150" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image164.wmz» o:><img width=«128» height=«28» src=«dopb64112.zip» v:shapes="_x0000_i1150"><shape id="_x0000_i1151" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image166.wmz» o:><img width=«56» height=«63» src=«dopb64113.zip» v:shapes="_x0000_i1151">,  i≠j, i, j=1, 2, …,r,
∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙                                                  (10)
<shape id="_x0000_i1152" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image168.wmz» o:><img width=«231» height=«25» src=«dopb64114.zip» v:shapes="_x0000_i1152">= <shape id="_x0000_i1153" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image170.wmz» o:><img width=«85» height=«55» src=«dopb64115.zip» v:shapes="_x0000_i1153">.
Подставляя (10) в (9), получаем (8).
Пример. Пусть <shape id="_x0000_i1154" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image172.wmz» o:><img width=«121» height=«24» src=«dopb64116.zip» v:shapes="_x0000_i1154">, а1=3, а2=7, а3=8.
Количество целых чисел, не превосходящих 35 и не делящихся ни на 3, ни на 7, ни на 8, равно
<shape id="_x0000_i1155" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image174.wmz» o:><img width=«539» height=«149» src=«dopb64117.zip» v:shapes="_x0000_i1155">
Рассмотрим другие приложения.
Количество целых чисел k таких, что
< k ≤ n, (k, n)=1, <shape id="_x0000_i1156" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image176.wmz» o:><img width=«53» height=«25» src=«dopb64118.zip» v:shapes="_x0000_i1156">,
обозначают через φ(n) и называют функцией Эйлера.
Теорема 2. Пусть <shape id="_x0000_i1157" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image176.wmz» o:><img width=«53» height=«25» src=«dopb64118.zip» v:shapes="_x0000_i1157">. Тогда
                                         <shape id="_x0000_i1158" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image178.wmz» o:><img width=«148» height=«57» src=«dopb64119.zip» v:shapes="_x0000_i1158">,                                       (11)
где произведение берётся по всем простым делителям аiчисла n.
Доказательство. Так как все ai делят n и взаимно просты, то имеем
<shape id="_x0000_i1159" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image180.wmz» o:><img width=«99» height=«58» src=«dopb64120.zip» v:shapes="_x0000_i1159">=<shape id="_x0000_i1160" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image182.wmz» o:><img width=«85» height=«52» src=«dopb64121.zip» v:shapes="_x0000_i1160">.
По формуле (8)
<shape id="_x0000_i1161" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image184.wmz» o:><img width=«412» height=«180» src=«dopb64122.zip» v:shapes="_x0000_i1161">
т.е. получаем (11).
Пример. Пусть n=84. Простыми делителями 84 являются 2, 3, 7; поэтому
<shape id="_x0000_i1162" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image186.wmz» o:><img width=«285» height=«52» src=«dopb64123.zip» v:shapes="_x0000_i1162">
Функция Мёбиуса. Представим (11) в другом виде, используя функцию Мёбиуса μ(n), определяемую следующим образом:
μ(1)=1;
μ(n)=0, если n делится на квадрат простого числа;
μ(а1а2…аr)=(-1)r, если ai – различные простые множители, i=1, 2, …,r.
Преобразуем равенство (11), используя функцию Мёбиуса:
<shape id="_x0000_i1163" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image188.wmz» o:><img width=«541» height=«228» src=«dopb64124.zip» v:shapes="_x0000_i1163">
Тогда
                                             <shape id="_x0000_i1164" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image190.wmz» o:><img width=«121» height=«52» src=«dopb64125.zip» v:shapes="_x0000_i1164">,                                         (12)
где суммирование производится по всем k, делящим n (включая 1).
Пример. Имеем
μ(1)=1,                  <shape id="_x0000_i1165" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image192.wmz» o:><img width=«135» height=«29» src=«dopb64126.zip» v:shapes="_x0000_i1165">,                   <shape id="_x0000_i1166" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image194.wmz» o:><img width=«135» height=«29» src=«dopb64127.zip» v:shapes="_x0000_i1166">,
<shape id="_x0000_i1167" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image196.wmz» o:><img width=«125» height=«28» src=«dopb64128.zip» v:shapes="_x0000_i1167">,             <shape id="_x0000_i1168" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image198.wmz» o:><img width=«192» height=«29» src=«dopb64129.zip» v:shapes="_x0000_i1168">,       
<shape id="_x0000_i1169" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image200.wmz» o:><img width=«135» height=«29» src=«dopb64130.zip» v:shapes="_x0000_i1169">,           <shape id="_x0000_i1170" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image202.wmz» o:><img width=«153» height=«28» src=«dopb64131.zip» v:shapes="_x0000_i1170">,
<shape id="_x0000_i1171" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image204.wmz» o:><img width=«143» height=«24» src=«dopb64132.zip» v:shapes="_x0000_i1171">,          <shape id="_x0000_i1172" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image206.wmz» o:><img width=«143» height=«24» src=«dopb64133.zip» v:shapes="_x0000_i1172">,       
<shape id="_x0000_i1173" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image208.wmz» o:><img width=«155» height=«28» src=«dopb64134.zip» v:shapes="_x0000_i1173">,       <shape id="_x0000_i1174" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image210.wmz» o:><img width=«164» height=«24» src=«dopb64135.zip» v:shapes="_x0000_i1174">,   <shape id="_x0000_i1175" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image212.wmz» o:><img width=«173» height=«28» src=«dopb64136.zip» v:shapes="_x0000_i1175">
При n=84 формула (12) даёт
<shape id="_x0000_i1176" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image214.wmz» o:><img width=«429» height=«52» src=«dopb64137.zip» v:shapes="_x0000_i1176">
Решето Эратосфена. Известен следующий способ перечисления простых чисел pi, pi≤ n: вычисляется <shape id="_x0000_i1177" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image216.wmz» o:><img width=«63» height=«28» src=«dopb64138.zip» v:shapes="_x0000_i1177"> и из последовательности 2, 3, …, n вычеркиваются последовательно все числа, кратные 2, затем кратные 3, …, кратные c. Оставшиеся числа и есть искомые.
Используя теорему 2, можно получить следующую формулу пересчёта. Если  через M(n) обозначить количество простых чисел q таких, что <shape id="_x0000_i1178" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image218.wmz» o:><img width=«84» height=«29» src=«dopb64139.zip» v:shapes="_x0000_i1178">, то в силу (8)
 M(n)=<shape id="_x0000_i1179" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image220.wmz» o:><img width=«512» height=«64» src=«dopb64140.zip» v:shapes="_x0000_i1179">(13)
где  pi-,    i=1, 2, …,r, — простые числа, не превосходящие <shape id="_x0000_i1180" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image222.wmz» o:><img width=«28» height=«27» src=«dopb64141.zip» v:shapes="_x0000_i1180"> (- 1 в правой части добавляется, так как 1 не считается простым).
В силу (12)
                                          M(n)= <shape id="_x0000_i1181" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image224.wmz» o:><img width=«40» height=«19» src=«dopb64142.zip» v:shapes="_x0000_i1181"> <shape id="_x0000_i1182" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image226.wmz» o:><img width=«71» height=«52» src=«dopb64143.zip» v:shapes="_x0000_i1182">,                                  (14)
где суммирование в (14) производится по всем простым делителям n (включая 1).
Пример. Сколько простых среди чисел 2, 3, …, 84? Имеем <shape id="_x0000_i1183" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image228.wmz» o:><img width=«44» height=«28» src=«dopb64144.zip» v:shapes="_x0000_i1183">=9. Простыми числами между 2 и 9 будут 2, 3, 5, 7. Согласно (13)
<shape id="_x0000_i1184" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image230.wmz» o:><img width=«507» height=«185» src=«dopb64145.zip» v:shapes="_x0000_i1184">
Таким образом, имеется всего 19 + 4 = 23 простых числа среди 2, 3, …, 84. Решето Эратосфена перечисляет их: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83.
Расширения данной темы: иногда подмножества не выделяются, а фиксируется число свойств, которыми обладают их элементы. Для этого случая можно вывести формулу, используя формулу (6).

§3. Разбиение фигур на части меньшего диаметра [1, 2] Диаметром фигуры F назовём такое расстояние d, что, во-первых, расстояние между любыми двумя точками M и N фигуры F не превосходит d, и, во-вторых, можно отыскать в фигуре F хотя бы одну пару точек A, B, расстояние между которыми в точности равно d.
Примеры:
·        Если фигура F представляет собой сегмент круга, ограниченный дугой l и хордой а, то в случае, когда дуга l не превосходит полуокружности, диаметр фигуры F равен а; в случае же, когда дуга l больше полуокружности, диаметр фигуры F совпадает с диаметром всего круга.
·        Если фигура F представляет собой многоугольник, то его диаметром является наибольшее из расстояний между вершинами.
В фигуре может существовать и много пар точек, расстояние между которыми равно d: в случае эллипса такая пара точек только одна, в случае квадрата их две, в случае правильного треугольника – три, в случае круга таких пар бесконечно много.
Постановка задачи: Круг диаметра d нельзя разбить на две части, диаметр каждой из которых будет меньше d, но можно разбить на три такие части (рис. 4(а, б)).
ref  SHAPE  \* MERGEFORMAT <lock v:ext=«edit» rotation=«t» aspectratio=«t» position=«t»><shape id="_x0000_s1097" type="#_x0000_t75" o:divferrelative=«f»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><fill src=«13963.files/image232.gif» o: type=«pattern»><fill src=«13963.files/image233.gif» o: type=«pattern»><fill src=«13963.files/image233.gif» o: type=«pattern»><fill src=«13963.files/image232.gif» o: type=«pattern»><img width=«549» height=«196» src=«dopb64146.zip» v:shapes="_x0000_s1096 _x0000_s1097 _x0000_s1098 _x0000_s1099 _x0000_s1100 _x0000_s1101 _x0000_s1102 _x0000_s1103 _x0000_s1104 _x0000_s1105 _x0000_s1106 _x0000_s1107 _x0000_s1108 _x0000_s1109 _x0000_s1110 _x0000_s1111"><imagedata src=«13963.files/image235.wmz» o: croptop="-65506f" cropbottom=«65506f»><lock v:ext=«edit» rotation=«t» position=«t»><img width=«547» height=«196» src=«dopb64147.zip» v:shapes="_x0000_i1185">
Тем же свойством обладает равносторонний треугольник со стороной d. Но имеются фигуры, которые можно разбить на две части меньшего диаметра (рис. 5(а, б)).
 
ref  SHAPE  \* MERGEFORMAT <lock v:ext=«edit» rotation=«t» aspectratio=«t» position=«t»><shape id="_x0000_s1113" type="#_x0000_t75" o:divferrelative=«f»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><fill src=«13963.files/image232.gif» o: type=«pattern»><shapetype id="_x0000_t7" coordsize=«21600,21600» o:spt=«7» adj=«5400» path=«m@0,l,21600@1,21600,21600,xe»><path gradientshapeok=«t» o:connecttype=«custom» o:connectlocs="@4,0;10800,@11;@3,10800;@5,21600;10800,@12;@2,10800" textboxrect=«1800,1800,19800,19800;8100,8100,13500,13500;10800,10800,10800,10800»><fill src=«13963.files/image232.gif» o: type=«pattern»><img width=«505» height=«173» src=«dopb64148.zip» v:shapes="_x0000_s1112 _x0000_s1113 _x0000_s1114 _x0000_s1115 _x0000_s1116 _x0000_s1117 _x0000_s1118 _x0000_s1119 _x0000_s1120 _x0000_s1121"><imagedata src=«13963.files/image238.wmz» o: croptop="-65505f" cropbottom=«65505f»><lock v:ext=«edit» rotation=«t» position=«t»><img width=«503» height=«172» src=«dopb64149.zip» v:shapes="_x0000_i1186">
Мы можем рассматривать для любой фигуры F задачу о разбиении её на части меньшего диаметра. Наименьшее число частей, которые для этого потребуются, обозначим через a(F). Если F – круг или равносторонний треугольник, то a(F) = 3, а для эллипса или параллелограмма a(F) = 2. Возникает вопрос, нельзя ли найти плоскую фигуру, для которой a(F)>3, то есть такую фигуру, что для разбиения её на части меньшего диаметра нельзя обойтись тремя частями, а потребуется 4 или большее число частей?
 Ответ даёт теорема Борсука: Всякая плоская фигура  F диаметра d может быть разбита на три части диаметра меньше d, то есть a(F) ≤ 3.
Лемма: Всякая плоская фигура диаметра d может быть заключена в правильный шестиугольник, у которого расстояние между параллельными сторонами равно d.
Доказательство леммы.
Проведём к фигуре F опорные прямые l1 и l2, причём l2 параллельна l1.  Вся фигура будет находиться в полосе между прямыми l1 и l2, расстояние между которыми не превосходит d (так как диаметр фигуры F равен d) (рис. 6). Проведём к фигуре F две параллельные опорные прямые m1 и m2, составляющие с l1 угол 60°. Прямые l1, l2, m1, m2образуют параллелограмм ABCD с углом 60° и высотами не превосходящими d, внутри которого целиком заключается фигура F. Проведём две опорные прямые p1, p2 фигуры F, составляющие с l1 угол 120°, и обозначим через MиN основания перпендикуляров, опущенных на эти прямые из концов диагонали AC параллелограмма (рис. 6). Покажем, что направление прямой l1 можно выбрать таким образом, чтобы выполнялось равенство AM=CN. Допустим, AM≠CN, и пусть, для определённости, AM<CN. Таким образом, величина y= AM– CN отрицательна. Начнём непрерывно изменять направление прямой l1 так, чтобы она повернулась на 180° (фигуру F будем оставлять неподвижной). Вместе с прямой l1 будут менять своё положение прямые l2, m1, m2, p1, p2(так как их положение определяется выбором l1). Поэтому при повороте прямой l1 будут непрерывно перемещаться и точки A, C, M, N, а значит, будет не<lock v:ext=«edit» aspectratio=«t»><shape id="_x0000_s1123" type="#_x0000_t75" o:divferrelative=«f»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><fill src=«13963.files/image232.gif» o: type=«pattern»><shapetype id="_x0000_t19" coordsize=«21600,21600» o:spt=«19» adj="-5898240,,,21600,21600" path=«wr-21600,,21600,43200,,,21600,21600nfewr-21600,,21600,43200,,,21600,21600l,21600nsxe» filled=«f»><path arrowok=«t» o:extrusionok=«f» gradientshapeok=«t» o:connecttype=«custom» o:connectlocs=«0,0;21600,21600;0,21600»><path o:connectlocs=«7898,0;14768,35867;0,20104»><img width=«336» height=«557» src=«dopb64150.zip» v:shapes="_x0000_s1122 _x0000_s1123 _x0000_s1124 _x0000_s1125 _x0000_s1126 _x0000_s1127 _x0000_s1128 _x0000_s1129 _x0000_s1130 _x0000_s1131 _x0000_s1132 _x0000_s1133 _x0000_s1134 _x0000_s1135 _x0000_s1136 _x0000_s1137 _x0000_s1138 _x0000_s1139 _x0000_s1140 _x0000_s1141 _x0000_s1142 _x0000_s1143 _x0000_s1144 _x0000_s1145 _x0000_s1146 _x0000_s1147 _x0000_s1148 _x0000_s1149 _x0000_s1150 _x0000_s1151">прерывно изменяться величина y= AM– CN.
ref  SHAPE  \* MERGEFORMAT <imagedata src=«13963.files/image238.wmz» o: croptop="-65505f" cropbottom=«65505f»><img width=«308» height=«406» src=«dopb64151.zip» v:shapes="_x0000_i1187">
Но когда прямая l1 повернётся на 180°, она займет положение, которое раньше занимала прямая l2. Поэтому мы получим тот же параллелограмм, что и на рис. 6,  но в нем точки А и С, а так же М иNпоменяются  «ролями». Следовательно, в этом положении величина у будет уже положительной.
ref  SHAPE  \* MERGEFORMAT <lock v:ext=«edit» rotation=«t» aspectratio=«t» position=«t»><shape id="_x0000_s1153" type="#_x0000_t75" o:divferrelative=«f»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><img width=«417» height=«227» src=«dopb64152.zip» v:shapes="_x0000_s1152 _x0000_s1153 _x0000_s1154 _x0000_s1155 _x0000_s1156 _x0000_s1157 _x0000_s1158 _x0000_s1159 _x0000_s1160 _x0000_s1161 _x0000_s1162 _x0000_s1163 _x0000_s1164 _x0000_s1165"><imagedata src=«13963.files/image243.wmz» o: croptop="-65517f" cropbottom=«65517f»><lock v:ext=«edit» rotation=«t» position=«t»><img width=«417» height=«227» src=«dopb64153.zip» v:shapes="_x0000_i1188">
 Если мы теперь изобразим график изменения величины у при повороте прямой l1 от 0° до 180° (рис. 7), то увидим, что найдётся положение прямой l1, при котором величина у обращается в нуль, т.е. АМ = CN(ибо, непрерывно изменяясь от отрицательного значения до положительного, величина у должна в некоторый момент обратиться в нуль). Мы рассмотрим положение всех наших прямых как раз в тот момент времени, когда величина у обращается в нуль (рис. 8). Из равенства АМ = CNвытекает, что шестиугольник, образованный прямыми l1, l2, m1, m2, p1,p2, центрально-симметричен.
ref  SHAPE  \* MERGEFORMAT <lock v:ext=«edit» rotation=«t» aspectratio=«t» position=«t»><shape id="_x0000_s1167" type="#_x0000_t75" o:divferrelative=«f»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><path o:connectlocs=«0,0;21561,22899;0,21600»><shapetype id="_x0000_t9" coordsize=«21600,21600» o:spt=«9» adj=«5400» path=«m@0,l,10800@0,21600@1,21600,21600,10800@1,xe»><path gradientshapeok=«t» o:connecttype=«rect» textboxrect=«1800,1800,19800,19800;3600,3600,18000,18000;6300,6300,15300,15300»><fill src=«13963.files/image232.gif» o: type=«pattern»><img width=«567» height=«339» src=«dopb64154.zip» v:shapes="_x0000_s1166 _x0000_s1167 _x0000_s1168 _x0000_s1169 _x0000_s1170 _x0000_s1171 _x0000_s1172 _x0000_s1173 _x0000_s1174 _x0000_s1175 _x0000_s1176 _x0000_s1177 _x0000_s1178 _x0000_s1179 _x0000_s1180 _x0000_s1181 _x0000_s1182 _x0000_s1183 _x0000_s1184 _x0000_s1185 _x0000_s1186 _x0000_s1187 _x0000_s1188 _x0000_s1189 _x0000_s1190 _x0000_s1191 _x0000_s1192 _x0000_s1193 _x0000_s1194 _x0000_s1195 _x0000_s1196 _x0000_s1197"><imagedata src=«13963.files/image238.wmz» o: croptop="-65505f" cropbottom=«65505f»><lock v:ext=«edit» rotation=«t» position=«t»><img width=«565» height=«335» src=«dopb64155.zip» v:shapes="_x0000_i1189"> 
Каждый угол этого шестиугольника равен 120°, а расстояние между противоположными сторонами не превосходит d. Если расстояние между p1 и p2меньше d, то мы раздвинем эти прямые (перемещая их на одинаковое расстояние) так, чтобы расстояние между раздвинутыми прямыми было равно d. Точно так же мы поступим с прямыми l1, l2, а за тем с прямыми m1, m2. В результате мы получим центрально-симметричный шестиугольник (с углами 120°), у которого противоположные стороны удалены друг от друга на расстояние d. Из сказанного ясно, что все стороны этого шестиугольника равны между собой, т. е. этот шестиугольник – правильный, причём фигура F расположена внутри шестиугольника.
<lock v:ext=«edit» aspectratio=«t»><shape id="_x0000_s1199" type="#_x0000_t75" o:divferrelative=«f»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><img width=«189» height=«222» src=«dopb64156.zip» v:shapes="_x0000_s1198 _x0000_s1199 _x0000_s1200 _x0000_s1201 _x0000_s1202 _x0000_s1203 _x0000_s1204 _x0000_s1205 _x0000_s1206 _x0000_s1207 _x0000_s1208 _x0000_s1209 _x0000_s1210 _x0000_s1211 _x0000_s1212 _x0000_s1213 _x0000_s1214">Доказательство теоремы Борсука. Пусть F – фигура диаметра d. Согласно доказательной лемме, фигура F содержится внутри правильного шестиугольника, расстояние между противоположными сторонами которого равно d. Покажем, что этот правильный шестиугольник можно разрезать на три части, каждая из которых имеет диаметр, меньший d. При этом фигура F также разрежется на три части, диаметр каждой из которых будет меньше d. Требуемое разбиение правильного шестиугольника на три части показано на рис. 9 (точки P, Qи R являются серединами сторон, а О – центр шестиугольника). Чтобы убедится, что диаметры частей меньше d, достаточно заметить, что в треугольнике PQLугол Qпрямой, и поэтому PQ< PL= d. Таким образом, теорема доказана.
Из доказательства теоремы легко заключить, что всякая плоская фигура диаметра dможет быть разбита на три части, диаметр каждой из которых не превосходит <shape id="_x0000_i1190" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image248.wmz» o:><img width=«139» height=«28» src=«dopb64157.zip» v:shapes="_x0000_i1190"> (так как PQ= <shape id="_x0000_i1191" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image250.wmz» o:><img width=«59» height=«27» src=«dopb64158.zip» v:shapes="_x0000_i1191">) (рис. 9). Эта оценка диаметров частей является наилучшей, так как круг диаметра d нельзя разбить на три части, диаметр каждой из которых был бы меньше <shape id="_x0000_i1192" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image250.wmz» o:><img width=«59» height=«27» src=«dopb64158.zip» v:shapes="_x0000_i1192"> (часть, имеющая диаметр меньше <shape id="_x0000_i1193" type="#_x0000_t75" o:ole=""><imagedata src=«13963.files/image252.wmz» o:><img width=«59» height=«27» src=«dopb64158.zip» v:shapes="_x0000_i1193">, высекает на окружности множество, расположенное на дуге, меньшей 120°, поэтому три такие части не покрывают всей окружности).
Можно предложить следующие расширения по данному вопросу:
Теорема Борсука является стержнем этого вопроса, но она не даёт полного решения вопроса о том, чему равно a(F) для произвольной заданной фигуры Fдиаметра  d. Она даёт лишь оценкуa(F) сверху: a(F) ≤ 3. В то же время, очевидно, что a(F) ≥ 2 для любой фигуры. Возникает задача: для каких плоских фигур a(F)  равно двум и для каких оно равно трём.
Можно рассматривать задачу о покрытии выпуклых фигур гомотетичными (о наименьшем числе «уменьшенных копий» фигуры F, которыми можно покрыть всю фигуру F) и задачу о наименьшем числе направлений, освещающих всю границу фигуры F.
Все эти задачи можно рассмотреть для пространственных тел.

§4. «Счастливые билеты» [5] Назовём билет счастливым, если сумма первых трёх цифр его номера равняется сумме последних трёх цифр (для шестизначных номеров). Возникает вопрос, сколько всего существует счастливых билетов?
    продолжение
--PAGE_BREAK--