книги из ГПНТБ / Войтишек В.В. Курс лекций по математике для слушателей подготовительного отделения

Решение

примера 2 . Пусть требуется

построить треугольник

йВСі

' зная

сторону

вс.

,

противолежащий угол й

и соответстңую-

щую высоту. Если выбрано положение стороны

ВС,

ыы инеем два

множества для точки й-

ВС

а)

дуга,вмещающая данный угол

и построенная

на

,

как

на хорде;

б)

прямая, параллельная ВС

и

отстоящая от неё

на

расстоянии,

равном высоте.

Условие,

налагаемое

на

положение

точки, называется

п р о ­

с т ы м

у с л о в и е м ,

если

существует

некоторая линия -

множество точек, удовлетворяющих этому условию. При этом точка

определяется двумя простыми условиями, и если известны два соот­

ветствующих множества, то искомая точка найдётся как точка

их

пересечения.

Вообще, всякая фигура определяется некоторым числом простых

условий. Многоугольник, имеющий

п

сторон,

определяется

по вели­

чине и положению &п

простыми условиями, так как

при этом

требу­

ется

определить

положение п

точек. Чтобы определить его

только по

величине и по форме, достаточно

С£п-3)

простых условий,

так

как можно .задать произвольно одну вершину и направление одной из

выходящих из

этой вершины сторон. Это число

с&п-З)

равняется

п

для

треугольника,

но

не

равняется

п т

если

п

превосхо­

дит

3 .

4 .

В силу

этого,

когда мы встречаемся с

какой-либо задачей

на построение, ыы должны постараться преобразовать условие задачи

таким

образом,

чтобы

свести её

к одной

из

тех

задач,

которые мы

умеем

решать;

например,

преобразовать условие

так, чтобы вывести

из него два множества точек для одной из точек, связанных с иско­

мой фигурой.

Для этого мы рассматриваем фигуру, которая по предположению

удовлетворяет поставленным условиям

(говоря

при этом:

"предположим,

И в этом случае

следует соблюдать те же общие правила, как

и при доказательстве

теорем. Как. и в случае задач на множества

точек

полученное заключение должно быть вполне равносильно усло­

вию.

Действительно,

если, с одной стороны, из условий задачи долж­

но следовать найденное построение, то,

с

другой стороны, мы долж­

ны убедиться в том, что любая фигура,

построенная найденным нами

способом, обязательно удовлетворяет всем

условиям задачи.

Г л а в а

I У

МНОЖЕСТВА ЧИСЕЛ

§• I .

Натуральные

числа

,

Мы берем

за основу множество

натуральных чисел

(обозначение

N = { 1 X 5 ........п,

. .. }

).

Множество N

задается

системой

аксиом

(Пеано,

1889).

1 °.

Единица -

натуральное число

(обозначение I ) .

2 ° .

п е М = > слН) e l f

(из

того,

что п

принадлежит ß f

следует,

что следующее число

т +і)

тоже

принадлежит Ж

; эта

аксиома вводит и операцию сложения).

3 °.

Единица не имеет предшествующего элемента

((п+1) = 1=* п ф Я ) .

4 °.

Если для

п e N

•

и т е К

известно, что

Сл+і)= (m+l) ,

то п-т .

5 °. Пусть

А -некоторое

множество

натуральных чисел такое,

что

а)

и

д ;

б)

если

п е Д

)

( п +і ) е

Д .

Тогда Д

содержит

все натуральные числа, т .е .

Дтло К .

Из последней аксиомы вытекает возможность доказательства по

индукции

(принцип математической индукции): если

известно,

что

а)

рассматриваемое свойство

верно для

единицы;

б)

и если, пред­

положив,

что для о

верно

это

свойство,

можно показать,что

для

cnti)

также верно данное

свойство,

то

отсюда следует,

что

для

всех натуральных чисел верно рассматриваемое свойство.

Во множестве натуральных чисел можно складывать и умножать.

Замечание. Одно и то же число может быть записано многими

способами. Именно, в разных системах исчисления число

записывается

а - г 3 +

+С-1 + d .

Но

сразу видно,

что

а

=о,

ибо I 3= зчз ,

а зчз>иоз.

Цифра 6 = 4 (ибо

49

X

5

=

245,

а 49 х 4 = 196),

далее, с = I ,

d

= 2 . Итак, 2 0 5 ц 0)

=

4

І2 (7) .

Наиболее употребительными (после

Конечные

подмножества. Элементы комбинаторики

Если рассматривать подмножества К

,

такие,

что

каждое число

из подмножества меньше или равно заданному числу

л ,

то получим

конечное множество, содержащее не

более

п

элементов.

Часть задач,

возникающих в конечных множествах,

рассматрива­

ются и решаются

к о м б и н а т о р н ы м и

м е т о д а м и .

Типичный вопрос для комбинаторики: сколько элементов

(или подмно­

жеств данного

конечного множества)

обладают некоторым

свойством?

Другой вопрос,

характерный для этих задач: сколькими

способами

можно разбить конечное множество на подмножества по некоторому

набору признаков?

Комбинаторные методы используются

при

решении задач, связан­

ных с обработкой информации, составлением планов и расписаний.

Однако существенное затруднение

необходимость

производить пере­

бор различных вариантов - здесь не

преодолено'до

сих

пор. Ярким

мый отрезок

времени,

является

задача -

невозможность научить уни­

версальную цифровую машину, играть в шахматы. Подсчитано,

что пере-

•

О

непрерывной работы машины,

производя­

бор вариантов займет

10 лет

щей операции

со скоростью, составляющей

% скорости света. Однако

Правило произведения

Если

объект А можно выбрать тп.

способами,

а второй

объект

ß

(после

того, как

первый

выбран)

-

п

способами,

то

выбор пары

{ й,В

) в указанном

порядке

можно

осуществить ( т . п

)

способами.

Дадим

определение размещений,

перестановок и сочетаний

(все

эти понятия в двух вариантах

-

с

повторением

и без

них),

широко

используя

понятие множества.^

Пусть дано некоторое

конечное

множество,

состоящее

из

эле­

ментов

( ап а& .......aJ -

Вместо

самих

элементов

-

a t

, а g ...

-

можно рассматривать

их индексы

^ 1,2,5

,

Сп-&), (п-і),

п} .

поскольку

природа

а^

с и

к 4 п )

нас

не

интересует. Важно

только,

что можно различать данные элементы.

Определение.

Сочетанием

из п

элементов

по к

(элементов)

называется всякое подмножество, содержащее ровно к

элементов.

В двух различных сочетаниях из

п

элементов

по к

есть

хотя бы

один элемент, содержащийся в одном

сочетании

и не содержащийся в

другом.

ТЕОРЕМА

(без доказательства). Число

сочетаний

из

п.

элемен­

тов

по^іг (обозначение«?*

и ли (£)),

где

o d k i n . ,

равно

------- —-------- Здесь

принято

считать

0!=

I;

І!= І;

к != І .2 .3 ...СЗН)к.

кКп -к)!

,1

Итак,

С* =

к/Сп-к)!

п

ТЕОРЕМА

к

+ С

к-і

к

( без

доказательства).

С

гг

= С

^.

п

п+ і

Пусть дано конечное упорядоченное множество. (Единственное

требование

к такому множеству

-

приведение

его во

взаимно-одно­

значное

сосответствие

с множеством

{

f,â,3,

... , п } .

Это

соответствие

ся перестановкой элементов

этого

множества.

ТЕОРЕМА (без доказательства).

Число

всевозможных перестановок

из И элементов (обозначение

)

равно

кі/ Итак,

Определение. Операция взаимно-однозначного отображения

на

себя конечного множества из я

элементов

называется

подстановкой.

Для нее используют

символ

( і

2

3 ...

п

\

(

і

iz

i3 ...

іѣ / .

п.

, располо­

Во второй строке написаны те же самые числа от I до

женные в

другом порядке. Например, . / !

2

3

4 \ .

U

I

3

2 / ' -

Для двух подстановок определяют операцию (ее результат

- но­

вая

подстановка -

называется

произведением

исходных подстановок)

I 2 3. ..п

с,

h

' / 2 3 . . . я

1

К 1,■■■

{

b

f a h

•• ■к

/'

h

к

■■■к

I

г. J

п

Например,

1

2

3

4^/4

2

3

1

1 2

3

4

4

2

3

І/.(

3

2

4

1

3

2

4

1

Этот

пример можно растолковать

так: пусть

{

/ , 2 , з , ч ]

-

множе­

остается неподвижной. Какое перемещение описывает

следующее

про­

изведение:

1 2 3 4VA 2 3 IN

/

I 2 3

4 \

?

4 2 3 іД .4 3 2 I /

( 4 3 2 I /

Интересно отметить, что переставлять сомножители

здесь

опас­

н о , т . е .

аб-4 § а

в общем случае.

Определение. Размещением из я

элементов

по к

называется

всякое

упорядоченное

подмножество,

содержащее

ровно к

элементов.

ТЕОРЕМА (без

доказательства).

Число

различных размещений из

п

элементов по£

(обозначение

Д*

) равно fn-yy

'

Следствия. I)

Д° = Рп ;

2)

^

= Pt -

.

Повторения. Допустим, что мы составляем конечное множество

из

п элементов а, , Од, в3 ,... ,а ѣ /причём

любой

эл ем ен ту можно

зачислять в наше множество до я

раз.

Предыдущие определения касались того случая, когда множество

состояло

ровно из

я

элементов,

и каждый элемент встречался

во

множестве ровно один раз. Теперь

разрешается

брать

во

множество

несколько раз элемент

одного сорта.

Но если х = а , х& = а ,

, у = 6 , у^ -6,

у} =6

,

то

( a t b f = а 3+ З а 2Ь +

Появилась возможность привести подобные члены.

Итак, имеется і

ячеек и

я

сортов элементов

по к

штук

каждого сорта.

Определение. Размещением

с

повторениями

из я по К'(п-

число

типов элементов, в каждом типе

по к

одинаковых

элементов)

назы­

вается последовательность элементов длины к ,

причем

одно

разме­

щение с повторениями

равно другому

в том и только

в том случае,

друг от друга или видом входящих в них элементов,

или порядком >

этих элементов.

ТЕОРЕМА.(без доказательства). Число

всевозможных размещений

с повторениями из

я

по к (обозначение

& )

равно я .

Пример. Всех

трехзначных чисел, составленных из четырех цифр

-[ 1 ,2 ,3 ,4 } ,будет 64

=43

(проверьте!).

элемент

повторяется

я)

раз,

второй элемент

- ,

я& раза и

так

далее,

последний к

-ый

элемент

повторяется

пі

раз “ где л,,...,по­

данные числа и

я, -t n& + n3

+... + n t

= я

,

называется

всякое

размещение с

повторениями из

п

по

к

с

заданным

выше

распределением

повторений.

ТЕОРЕМА (без доказательства). Число различных перестановок

с повторениями

из л

по к

(числа

nf , п&, . .

заданы;

обоз-

начение

Р ( п, , пг , п3>...,

пк ))

равно

п /

СП, +ТІ2 +... + пк)!

п /

nA( n p . . n t !

Ѵ ' Ѵ Ѵ - Ѵ

пз ■

Итак,

D /

п!

"

1

’ "s

"' ■’

'

n j пг !

'

Идея доказательства становится ясной из замечания, что если

бы все

элементы

были

разными,

то

P C U

J

■J X = п ! ,

т . е .

числу перестановок без повторений. А в слу^йіе

повторений п,

означает

число мест

из

п. ,

которые может

занимать первый

эле­

мент.

Неразличимых перестановок

поэтому

ц, /

. Число перестановок

должно уменьшиться в п,!

раз.

Эта теорема используется при подсчете коэффициентов после

раскрытия скобок

в выражении

с х + х а +х

*... +хк) ѣ

(полиномиальная теорема).

Замечание. Число

Р

Сп,,...,

пк ) часто подсчитывается в комбина­

торных задачах,

где

элементы располагаются цепочкой в ряд. Эту и

предыдущие формулы надо применять осторожно,

если

элементы

рас­

положены по кругу или

(как

в случае ожерелья)

этот

круг можно пере­

жается через предыдущие числа. Обозначим

это число так: С к

Тогда с к = РСк, п-i)

=C„+t-i ■

Пояснение. t Многочлен

Q

сх,у,...,

называется однородным

многочленом степени

п ,

ебли

его можно записать

в виде

суммы

одночленов, каждый из которых имеет одну

и ту

же

степень,

равную

п:

=

£

й5 х П,^ Пл ... иУПк,

П,*П2*..*Пк=П

— —

2

Тогда верно утверждение, что в этой сумме

С *

- Сп+к_1

различных слагаемых.

(Это утверждение мы

тоже

не доказываем здесь).

рениями. Сумма кратностей (число к

)

называется порядком соче­

тания.

Всякое

сочетание

с

повторениями

к

-

ого

порядка,

составлен­

ное из множества,

содержащего

п элементов,

называется сочетанием

с повторениями из

п

элементов по к.

Мы заканчиваем перечисление фактов из комбинаторики еще од­

ним общим правилом, связанным с подсчетом элементов.

Формула включений и исключений. Пусть имеется

п. элементов,

некоторые

из

которых

обладают

свойствами

ы.і , ы.£ , .. ..о ^ .

При этой

каждый элемент

может либо не

обладать ни

одним из

этих

свойств, либо обладать одним или несколькими свойствами.

Пусть

М (ы. >0L

. . , ы і ) -

количество

элементов,

обладающих по

край­

ней мере

свойствами

ы.

ы .■

.. . , <*, .

Запись

ы,

означает,

что

1

' і

к

■ „

к

мы учитываем

элемент,

не

обладающий свойством

.

Тогда

М

(<*,

.,5S) = n-M(dLl)-M&Lj-...-M(dis)+

+ M (c l* J .£ fe+6M(ct.l ,otJ) + .. . + М (<*-, , oij) +■■■

+М

CcL^'CLj) -

- . . . - M C d ^ , d j . „ « V +...

Например, в первой сотне натуральных чисел есть числа, деля­

щиеся на

2 (свойство

оit

) ,

на 3 (с в о й с т в о ^ ) ,

на

5

(свойство

ас

) .

Тогда М (Ы'

,ök£ ,ökj)

- количество чисел,

не

делящихся ни

на 2 ,

ни

на 3 ,

ни на

5. По общей формуле

И

гЦ ,5 g

= 100 - M C М<Ы£ ) - М( ы3 -)+

М Ң , Ы Я) +М(<к,,сі} )+Мбсл ,Ыі ) - M U r ^£ ,<kj)

И <4,5g'äj) - 100-50-33-£0+16+10+6-5=£6.

Заключительное замечание. Приведем примеры задач, в которых

комбинаторные методы

"работают" частично.

1. Сколько

существует

разных разверток куба на плоскости?

2 . Сколькими способами можно разложить число

один

миллион

на три разных сомножителя,

каждый их которых не равен

единице.