Федоров Р.М., Канель-Белов А.Я., Ковальджи А.К., Ященко И.В. Московские математические олимпиады 1993-2005

Подождите немного. Документ загружается.

Основные факты 391

гое, то попасть из первого состояния во второе невоз-

можно.

Полуинвариант — это число, которое при данных опе-

рациях изменяется в определенную сторону (например,

увеличивается). Если имеется полуинвариант и он из-

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

можно.

Задачи: инвариант 93.8.3, 95.9.5, 95.10.6, 99.9.1;

полуинвариант 94.10.5, 04.8.6.

Литература: [62].

◦

. Г р а ф ы, к о м п о н е н т ы с в я з н о с т и, д е р е в ь я.

Во многих ситуациях удобно изображать объекты точ-

ками, а связи между ними — линиями. Такой способ пред-

ставления называется графом. Например, схема метро —

это граф. Точки называют вершинами графа, а линии —

ребрами.

Граф называется связным, если из любой вершины

можно попасть в любую, двигаясь по ребрам. Циклом

в графе называется такая последовательность различных

вершин A

, A

, ..., A

, что каждая следующая верши-

на соединена ребром с предыдущей, а первая вершина

соединена с последней.

Связный граф без циклов называется деревом. Дерево

с n вершинами всегда имеет n −1 ребро.

Множество вершин, в которые можно попасть из дан-

ной, двигаясь по ребрам, называется компонентой связно-

сти этой вершины графа. Связный граф состоит из одной

компоненты связности, а несвязный граф распадается на

несколько компонент.

Иногда рассматриваются графы с петлями (петля — это

ребро, соединяющее вершину с ней самой) и кратными

ребрами (кратные ребра — это несколько ребер, соединяю-

щих одну и ту же пару вершин).

Ориентированный граф — это граф, на ребрах которого

указано направление.

Задачи: 94.10.3, 98.9.4, 99.11.5, 01.11.6, 03.8.5,

03.10.5.

Литература: [62], [45].

392 Основные факты

◦

. П е р и о д и ч н о с т ь.

Рассмотрим бесконечную последовательность a

, a

, ..., a

, ... Для краткости мы будем обозначать такую

последовательность просто a

Последовательность a

называется периодичной или

периодической, если найдется такое m, что при всех n,

больших некоторого числа K, выполняется равенство

n+m

= a

. При этом конечная последовательность a

K+1

K+2

, . . . , a

K+m

называется периодом, а число m называ-

ется длиной периода.

Наименьшее число m, для которого выполняется ука-

занное свойство, называется длиной минимального перио-

да, а соответствующий период называется минимальным

периодом.

Например, для последовательности

БББББББАББАББАББАББАБ. . .

можно взять K = 5, m = 3 (период — ББА). А можно взять

K = 5, m = 6, тогда периодом будет ББАББА. Можно также

взять K = 6, m = 3, и периодом будет БАБ. Отсюда видно,

что K и m определены неоднозначно.

Т е о р е м а. Пусть a

— периодическая последователь-

ность с длиной минимального периода m. Число l явля-

ется длиной некоторого периода последовательности a

тогда и только тогда, когда l делится на m (см.

факт 5).

Пусть m — длина минимального периода последователь-

ности a

. Выберем K минимально возможным. Тогда по-

следовательность a

, . .., a

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

следовательности a

. Итак, каждая периодическая после-

довательность имеет вид

предпериод период период период ...,

что часто записывают как предпериод(период). Например,

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

так: БББББ(ББА).

З а м е ч а н и е. Длину периода часто называют периодом. Предпе-

риодом иногда называют последовательность a

, . . . , a

без предполо-

жения о минимальности K.

Задачи: 93.10.1, 94.10.2, 95.11.5, 99.11.7, 02.8.6,

05.9.5.

Основные факты 393

Теория чисел

◦

. Д е л и м о с т ь.

Говорят, что целое число a делится на целое число b

(или кратно числу b), если найдется такое целое число c,

что a = bc. В этом случае также говорят, что b делит a.

(Например, «2 делит 6» или «6 делится на 2», «−1 де-

лит −5».) Обозначение: b |a.

Свойства: а) любое число делится на ±1 и на себя; 0

делится на любое число, но никакое ненулевое число не

делится на 0.

б) Если d |a и d |b, то d |a ±b; кроме того, d |ac для

любого целого c; если c |b и b |a, то c |a.

в) Если b |a, то |b|6 |a| или a = 0.

г) Если d |a и d |b, k и l — целые числа, то d |ka + lb;

более общо, если каждое из чисел a

, a

, . . . , a

делится

на d, а k

— целые числа, то

d |k

+ k

+ . . . + k

Наибольший общий делитель чисел a и b мы обозна-

чаем НОД(a, b). Числа a и b называются взаимно про-

стыми, если НОД(a, b) = 1 (иначе говоря, числа взаимно

просты, если из того, что d |a и d |b, следует, что d = ±1).

Задачи: 93.9.3, 95.8.2, 95.9.1, 95.10.5, 97.8.4, 98.8.2,

98.10.4, 99.8.4, 99.10.3, 99.11.6, 00.9.2, 00.9.4,

01.9.4, 03.9.4, 02.9.4, 02.11.4, 03.11.7, 04.8.4,

04.11.3, 05.8.1, 05.9.2, 05.10.5, 05.11.5.

Литература: [29], гл. 1.

◦

. П р и з н а к и д е л и м о с т и.

а) Число четно тогда и только тогда, когда его послед-

няя цифра четна.

б) Остаток от деления числа на 5 равен остатку от

деления его последней цифры на 5. В частности, число

делится на 5 тогда и только тогда, когда его последняя

цифра делится на 5.

в) Остаток от деления числа на 9 равен остатку от

деления суммы его цифр на 9. В частности, число делится

на 9 тогда и только тогда, когда сумма его цифр делится

на 9. Аналогичные утверждения верны для деления на 3.

Задачи: 93.8.1, 94.10.1, 97.8.4, 97.10.6, 98.10.4, 01.9.5.

394 Основные факты

◦

. Д е л е н и е с о с т а т к о м.

Пусть a и b — целые числа, причем b 6= 0. Тогда найдут-

ся единственные q и r такие, что

а) a = qb + r;

б) 0 6 r < |b|.

При этом q и r называются частным и остатком от

деления a на b соответственно.

Пусть b > 0. Остатками при делении на b могут быть

числа 0, 1, ..., b −1. Число дает остаток r при делении

на b тогда и только тогда, когда оно имеет вид qb + r. При

этом все числа разбиваются на b (бесконечных) арифмети-

ческих прогрессий. Например, при b = 2 это прогрессии

2n и 2n + 1 (ср. с фактом 23), при b = 3 — прогрессии 3n,

3n + 1 и 3n + 2 и т. д.

Число делится на b тогда и только тогда, когда его

остаток от деления на b равен нулю.

Остатки суммы (разности, произведения) однозначно

определяются остатками слагаемых (сомножителей). На-

пример, если числа a и b дают остатки 3 и 6 при делении

на 7, то a + b дает остаток 2 = 3 + 6 −7, число a −b —

остаток 4 = 3 −6 + 7, а ab — остаток 4 = 3 · 6 −14 при делении

на 7.

Точное утверждение таково: если остаток от деления a

на b ра-

вен r

, а остаток от деления a

на b равен r

, то остаток от деления

+ a

на b равен остатку от деления r

+ r

на b, а остаток от деления

на b равен остатку от деления r

на b.

Задачи: 93.8.1б, 94.11.6, 96.11.4, 97.9.4, 00.9.2,

00.10.6, 03.8.6, 05.9.5, 05.10.5.

Литература: [29], гл. 1 и [30], § 2.

◦

. Если t |s, то a

−1 |a

−1.

Д о к а з а т е л ь с т в о. Если t |s, то можно записать s = kt с нату-

ральным k. Тогда

−1 = (a

)

−1 = (a

−1)(1 + a

+ a

+ .. . + a

(k−1)t

и a

−1 делится на a

−1. Утверждение доказано.

Используя алгоритм Евклида (см. [30], § 3), можно показать, что

при a > 1

НОД(a

−1, a

−1) = a

НОД(t,s)

−1.

Задачи: 99.11.6, 03.11.7 05.10.5.

Основные факты 395

◦

. Если d |ab и НОД(a, d) = 1, то d |b. В частности,

2k + 1 |2x тогда и только тогда, когда 2k + 1 |x (см. задачу

01.9.4).

Если простое число делит произведение, то оно делит

один из сомножителей. Точнее, если простое число p де-

лит произведение a

...a

, то p |a

для некоторого i.

Задачи: 94.8.2, 94.10.1, 99.10.3, 01.9.4, 02.11.4,

01.11.2, 03.11.7, 04.8.4, 05.10.2, 05.10.5,

05.11.5.

Литература: [29], гл. 1.

◦

. Р а з л о ж е н и е н а п р о с т ы е м н о ж и т е л и.

Число p > 1 называется простым, если оно делится

лишь на ±p и ±1. Остальные натуральные числа, б ´ольшие

единицы, называются составными. Каждое составное

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

простых. Иногда бывает удобно сгруппировать одинаковые

простые и записать это произведение в виде

...p

где p

, p

, ..., p

— различные простые числа, n

, n

, ...

..., n

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

О с н о в н а я т е о р е м а а р и ф м е т и к и. Разложение

числа на простые множители единственно (с точно-

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

Однозначность разложения на множители часто исполь-

зуется неявно — см., например, задачи 98.8.2 и 04.10.1.

Задачи: 94.9.5, 95.9.4, 95.10.5, 96.11.4, 98.8.2,

98.11.4, 99.8.3, 99.10.3, 99.11.6, 03.11.7,

04.8.4, 04.10.1, 05.8.1.

Литература: [29], гл. 1, [30].

◦

. Д е с я т и ч н а я з а п и с ь ч и с л а.

Запись a

n−1

...a

означает n-значное натуральное

число, первая цифра которого равна a

, вторая — a

n−1

, . . .

..., последняя — a

. Таким образом,

n−1

...a

= 10

n−1

+ 10

n−2

n−1

+ . . . + 10a

+ a

Иногда мы пользуемся записью типа ab, когда a и b —

не обязательно цифры. Такая запись обозначает число,

396 Основные факты

которое получится, если к числу a приписать справа чис-

ло b. Если число b является k-значным, то

ab = 10

a + b.

Заметим также, что натуральное число b является

k-значным тогда и только тогда, когда 10

k−1

6 b < 10

Задачи: 94.8.2, 94.9.5, 94.10.1, 94.11.6, 97.8.4,

97.10.6, 98.10.4, 99.9.4, 99.11.7, 00.8.5,

01.9.5, 04.11.3, 05.11.5.

◦

. С и с т е м ы с ч и с л е н и я.

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

ния. В m-ичной системе счисления запись a

n−1

...a

означает m

n−1

+ m

n−2

n−1

+ . . . + ma

+ a

. Цифрами

m-ичной системы счисления являются числа 0, 1, 2, . . .

..., m −2, m −1.

В математике особенно важны двоичная и троичная системы счис-

ления, а в информатике — двоичная, восьмеричная и шестнадцатерич-

ная системы.

Задачи: 94.10.2, 95.11.4, 98.10.4, 04.11.6.

◦

. Б е с к о н е ч н ы е д е с я т и ч н ы е д р о б и.

Каждое действительное число может быть разложено в

бесконечную десятичную дробь:

±a

n−1

...a

...,

где a

и b

— цифры. Смысл этой записи таков:

n−1

...a

... = 10

n−1

+ 10

n−2

n−1

+ . ..

... + a

+ 10

−1

+ 10

−2

+ 10

−3

+ ...

(здесь справа стоит бесконечная сумма, т. е. сумма ряда,

см. [75], гл. 3).

Число x рационально тогда и только тогда, когда со-

ответствующая бесконечная десятичная дробь периодична

(см. факт 4).

Обобщение: можно разложить число в бесконечную

m-ичную дробь, см. факт 12.

Задачи: 93.10.1, 94.10.2.

Основные факты 397

Геометрия

◦

. М е д и а н а п р я м о у г о л ь н о г о т р е у г о л ь -

н и к а.

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

тогда, когда длина его медианы, проведенной к некото-

рой стороне, равна половине длины этой стороны.

Равносильная формулировка: геометрическое место то-

чек, из которых отрезок AC виден под прямым углом,

есть окружность, построенная на AC как на диаметре (без

точек A и C). В одну сторону это утверждение можно еще

сформулировать так: из любой точки окружности диаметр

виден под прямым углом (кроме концов диаметра).

При этом если точка B лежит внутри этой окружности,

то ∠ABC — тупой, если вне — острый.

Задачи: 93.9.1, 95.10.3, 96.9.5, 97.8.5, 98.8.3, 00.8.4,

00.9.5, 01.8.4, 01.9.3, 02.8.5, 03.9.5, 04.10.2,

05.8.3.

◦

. У г о л м е ж д у к а с а т е л ь н о й и х о р д о й.

Касательная образует с хордой два смежных угла,

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

заключенной внутри него.

Более формально, угол, на который нужно повернуть прямую l по

часовой стрелке, чтобы она перешла в прямую AB, равен половине

угла, на который нужно повернуть по часовой стрелке окружность,

чтобы точка A перешла в точку B. Обратное утверждение тоже верно:

из равенства углов следует, что прямая l касается окружности.

Задачи: 94.9.4, 96.9.3, 96.11.5, 99.9.3.

Литература: [46], гл. 2.

◦

. В н е в п и с а н н ы е о к р у ж н о с т и.

Вневписанной окружностью треугольника ABC назы-

вается окружность, касающаяся одной из сторон треуголь-

ника и продолжений двух других сторон. Таким образом,

имеются три вневписанных окружности (рис. 193).

Центр вневписанной окружности есть точка пересече-

ния биссектрисы одного из углов треугольника и двух

биссектрис внешних углов треугольника. Таким образом,

эти три биссектрисы пересекаются в одной точке.

Задачи: 93.8.6, 01.9.3, 02.10.6, 04.10.5.

398 Основные факты

◦

. О б щ и е к а с а т е л ь н ы е к д в у м о к р у ж н о с т я м.

Рассмотрим две непересекающиеся окружности. К ним

можно провести ровно 4 общих касательных (т. е. пря-

мых, касающихся каждой из окружностей, см. рис. 194).

Обозначим центры окружностей и точки касания как на

рисунке.

Рис. 193 Рис. 194

Касательные A

и B

называются внешними, а

и D

— внутренними. Внутренние касательные пе-

ресекаются в точке R, лежащей на отрезке O

, причем

где r

и r

— радиусы окружностей с центрами O

и O

соответственно.

Аналогичные утверждение верны про точку пересече-

ния внешних касательных. Заметим также, что к пересе-

кающимся окружностям можно провести ровно две (внеш-

ние) общие касательные, а к касающимся — ровно 3.

Задачи: 94.10.4, 96.11.5, 02.8.3.

◦

. П л о щ а д и и о т н о ш е н и я п л о щ а д е й.

Напомним, что площадь треугольника равна половине

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

рую (или на продолжение которой) эта высота опущена.

Основные факты 399

а)

б)

Рис. 195

Треугольники ABC и AB

C с общим

основанием AC имеют одинаковую пло-

щадь тогда и только тогда, когда их вы-

соты, проведенные к основанию, равны.

Если прямая BB

параллельна AC, то пло-

щади этих треугольников равны. Обратно,

если точки B и B

лежат по одну сторону

от прямой AC и площади треугольников

ABC и AB

C равны, то BB

kAC.

В конфигурации, изображенной на

рис. 195, а, отношение площадей тре-

угольников ABC и ADC равно отношению

AB к AD. На рис. 195, б отношение пло-

щадей треугольников AB

и ABC равно

Задачи: 97.11.1, 99.11.2, 04.11.4, 05.10.3.

Литература: [46], гл. 4.

Многочлены

◦

. Д е л е н и е м н о г о ч л е н о в и т е о р е м а Б е з у.

Многочлены с рациональными коэффициентами можно

делить с остатком, как и целые числа (ср. с фактом 7):

Т е о р е м а. Пусть f и g — многочлены, причем g 6= 0.

Тогда найдутся единственные многочлены q и r такие,

что а) f = qg + r; б) степень r меньше степени g.

При этом q и r называются частным и остатком от

деления f на g соответственно. Аналогичная теорема вер-

на для многочленов с действительными коэффициентами.

Заметим, что мы полагаем степень нулевого многочлена

равной −∞.

Например, частное от деления x

+ 1 на x

+ x равно

−x + 1, а остаток равен 1 −x.

Т е о р е м а Б е з у. а) Остаток от деления многочлена

f(x) на x −a равен f(a).

б) f(x) делится на x −a тогда и только тогда, когда

a — корень многочлена f(x).

Задачи: 97.9.6, 98.11.1, 03.11.1.

Литература: [48].

400 Основные факты

◦

. К о р н и м н о г о ч л е н а и т е о р е м а В и е т а.

Т е о р е м а. а) Многочлен степени n имеет не более,

чем n корней.

б) Пусть x

, x

, . . . , x

— различные корни многочлена

f(x) степени n, тогда

f(x) = a(x −x

)(x −x

)...(x −x

где a — коэффициент многочлена f(x) при x

в) Если

+ a

n−1

+ . . . + a

x + a

= (x −x

)(x −x

)...(x −x

то

n−1

= −

16i6n

n−2

16i<j6n

n−3

= −

16i<j<k6n

. . . . . . . . . . . . . . . . . . . . . . .

= (−1)

...x

(1)

г) В частности, если x

, ..., x

— различные корни

многочлена x

+ a

n−1

+ ... + a

x + a

, то имеют место

формулы (1).

Утверждения «в» и «г» называют теоремой Виета.

При n = 3 формулы (1) принимают вид:

= −(x

+ x

= x

+ x

= −x

При n = 2 получаем обычную теорему Виета, известную

из школьной программы.

Часто используют обратную теорему Виета: если опре-

делить коэффициенты многочлена формулой (1), то кор-

нями этого многочлена будут в точности числа x

, x

, ...

..., x

Задачи: 95.10.1, 95.10.5, 97.10.4, 98.11.1.

Литература: [48].