Математические олимпиады и олимпиадные задачи.

Напомним, что граф } — это набор точек, некоторые из которых соединены линиями. Точки называются вершинами графа, линии — рёбрами.

Получите из левой картинки правую, проводя линии между точками (по одной). Около каждой точки подписывайте, сколько из неё выходит линий. Как изменяются числа после каждого дорисовывания линии? Можно ли 15 телефонов соединить проводами так, чтобы каждый был соединён ровно с 5 другими?

Решение. Будем называть ребёнка чётным, если у него четное число знакомых, и нечётным в противном случае. Заметим, что число нечётных детей чётно. Посмотрим, от кого Гоша мог получить письма. Либо от четных знакомых, либо от нечетных незнакомых. Разберем два случая.
1) Гоша — чётный. Тогда он получит чётное число писем от знакомых и еще чётное число от незнакомых.
2) Гоша — нечётный. Тогда он получит нечётное число писем от незнакомых и еще нечётное число писем от знакомых.
В обоих случаях получили, что Гоша получит чётное число писем. Т.е. еще хотя бы одно.

Точка — это абстрактный объект, который не имеет измерительных характеристик: ни высоты, ни длины, ни радиуса. В рамках задачи важно только его местоположение

Точка обозначается цифрой или заглавной (большой) латинской буквой. Несколько точек — разными цифрами или разными буквами, чтобы их можно было различать

точка A, точка B, точка C

A B C

точка 1, точка 2, точка 3

1 2 3

Можно нарисовать на листке бумаги три точки "А" и предложить ребёнку провести линию через две точки "А". Но как понять через какие? A A A

Линия — это множество точек. У неё измеряют только длину. Ширины и толщины она не имеет

Обозначается строчными (маленькими) латинскими буквами

линия a, линия b, линия c

a b c

Линия может быть

1. замкнутой, если её начало и конец находятся в одной точке,
2. разомкнутой, если её начало и конец не соединены

замкнутые линии

разомкнутые линии

Ты вышел из квартиры, купил в магазине хлеб и вернулся обратно в квартиру. Какая линия получилась? Правильно, замкнутая. Ты вернулся в исходную точку. Ты вышел из квартиры, купил в магазине хлеб, зашёл в подъезд и разговорился с соседом. Какая линия получилась? Разомкнутая. Ты не вернулся в исходную точку. Ты вышел из квартиры, купил в магазине хлеб. Какая линия получилась? Разомкнутая. Ты не вернулся в исходную точку.

1. самопересекающейся
2. без самопересечений

самопересекающиеся линии

линии без самопересечений

1. прямой
2. ломанной
3. кривой

прямые линии

ломанные линии

кривые линии

Прямая линия — это линия которая не искривляется, не имеет ни начала, ни конца, её можно бесконечно продолжать в обе стороны

Даже когда виден небольшой участок прямой, предполагается, что она бесконечно продолжается в обе стороны

Обозначается строчной (маленькой) латинской буквой. Или двумя заглавными (большими) латинскими буквами — точками, лежащими на прямой

прямая линия a

a

прямая линия AB

B A

Прямые могут быть

1. пересекающимися, если имеют общую точку. Две прямые могут пересекаться только в одной точке.
   • перпендикулярными, если пересекаются под прямым углом (90°).
2. параллельными, если не пересекаются, не имеют общей точки.

параллельные линии

пересекающиеся линии

перпендикулярные линии

Луч — это часть прямой, которая имеет начало, но не имеет конца, её можно бесконечно продолжать только в одну сторону

У луча света на картинке начальной точкой является солнце

солнышко

Точка разделяет прямую на две части — два луча A A

Луч обозначается строчной (маленькой) латинской буквой. Или двумя заглавными (большими) латинскими буквами, где первая — это точка, с которой начинается луч, а вторая — точка, лежащая на луче

луч a

a

луч AB

B A

Лучи совпадают, если

1. расположены на одной и той же прямой,
2. начинаются в одной точке,
3. направлены в одну сторону

лучи AB и AC совпадают

лучи CB и CA совпадают

C B A

Отрезок — это часть прямой, которая ограничена двумя точками, то есть она имеет и начало и конец, а значит можно измерить её длину. Длина отрезка — это расстояние между его начальной и конечной точками

Через одну точку можно провести любое число линий, в том числе прямых

Через две точки — неограниченное количество кривых, но только одну прямую

кривые линии, проходящие через две точки

B A

прямая линия AB

B A

От прямой «отрезали» кусочек и остался отрезок. Из примера выше видно, что его длина — наикратчайшее расстояние между двумя точками. ✂ B A ✂

Отрезок обозначается двумя заглавными(большими) латинскими буквами, где первая — это точка, с которой начинается отрезок, а вторая — точка, которой заканчивается отрезок

отрезок AB

B A

Задача: где прямая , луч , отрезок , кривая ?

Ломанная линия — это линия, состоящая из последовательно соединённых отрезков не под углом 180°

Длинный отрезок «поломали» на несколько коротких

Звенья ломаной (похожи на звенья цепи) — это отрезки, из которых состоит ломанная. Смежные звенья — это звенья, у которых конец одного звена является началом другого. Смежные звенья не должны лежать на одной прямой.

Вершины ломаной (похожи на вершины гор) — это точка, с которой начинается ломанная, точки, в которых соединяются отрезки, образующие ломаную, точка, которой заканчивается ломанная.

Обозначается ломанная перечислением всех её вершин.

ломанная линия ABCDE

вершина ломанной A, вершина ломанной B, вершина ломанной C, вершина ломанной D, вершина ломанной E

звено ломанной AB, звено ломанной BC, звено ломанной CD, звено ломанной DE

звено AB и звено BC являются смежными

звено BC и звено CD являются смежными

звено CD и звено DE являются смежными

A B C D E 64 62 127 52

Длина ломанной — это сумма длин её звеньев: ABCDE = AB + BC + CD + DE = 64 + 62 + 127 + 52 = 305

Задача: какая ломанная длиннее , а у какой больше вершин ? У первой линии все звенья одинаковой длины, а именно по 13см. У второй линии все звенья одинаковой длины, а именно по 49см. У третьей линии все звенья одинаковой длины, а именно по 41см.

Многоугольник — это замкнутая ломанная линия

Стороны многоугольника (помогут запомнить выражения: "пойти на все четыре стороны", "бежать в сторону дома", "с какой стороны стола сядешь?") — это звенья ломанной. Смежные стороны многоугольника — это смежные звенья ломанной.

Вершины многоугольника — это вершины ломанной. Соседние вершины — это точки концов одной стороны многоугольника.

Обозначается многоугольник перечислением всех его вершин.

замкнутая ломанная линия, не имеющая самопересечения, ABCDEF

многоугольник ABCDEF

вершина многоугольника A, вершина многоугольника B, вершина многоугольника C, вершина многоугольника D, вершина многоугольника E, вершина многоугольника F

вершина A и вершина B являются соседними

вершина B и вершина C являются соседними

вершина C и вершина D являются соседними

вершина D и вершина E являются соседними

вершина E и вершина F являются соседними

вершина F и вершина A являются соседними

сторона многоугольника AB, сторона многоугольника BC, сторона многоугольника CD, сторона многоугольника DE, сторона многоугольника EF

сторона AB и сторона BC являются смежными

сторона BC и сторона CD являются смежными

сторона CD и сторона DE являются смежными

сторона DE и сторона EF являются смежными

сторона EF и сторона FA являются смежными

A B C D E F 120 60 58 122 98 141

Периметр многоугольника — это длина ломанной: P = AB + BC + CD + DE + EF + FA = 120 + 60 + 58 + 122 + 98 + 141 = 599

Многоугольник с тремя вершинами называется треугольником, с четырьмя — четырёхугольником, с пятью — пятиугольником и т.д.

Задача 5:

В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими? Решение:

Предположим, что это возможно. Рассмотрим тогда граф, вершины которого соответствуют телефонам, а ребра - соединяющим их проводам. В этом графе 15 вершин, степень каждой из которых равна пяти. Подсчитаем количество ребер в этом графе. Для этого сначала просуммируем степени всех его вершин. Ясно, что при таком подсчете каждое ребро учтено дважды (оно ведь соединяет две вершины!). Поэтому число ребер графа должно быть равно 15 • 5/2. Но это число нецелое! Следовательно, такого графа не существует, а значит, и соединить телефоны требуемым образом невозможно.

При решении этой задачи мы выяснили, как подсчитать число ребер графа, зная степени всех его вершин. Для этого нужно просуммировать степени вершин и полученный результат разделить на два.

Задача 6:

В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве? Решение:

Общее число дорог равно 100 • 4/2 = 200.

Задача 7:

В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 - по 4 друга, а 10 - по 5 друзей? Решение:

Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 - степень 4, 10 - степень 5. Однако у такого графа 19 нечетных вершин, что противоречит теореме.

Задача 8:

В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы было 4 телефона, каждый из которых соединен с тремя другими, 8 телефонов, каждый из которых соединен с шестью, и 3 телефона, каждый из которых соединен с пятью другими? Решение:

Нельзя. Примените теорему о числе нечетных вершин.

Задача 9:

У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств? Решение:

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

Задача 10:

Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог? Решение:

Если в государстве k городов, то дорог - 3k/2. Это число не может быть равно 100.

Задача 11:

Джон, приехав из Диснейленда, рассказывал, что там на заколдованном озере имеются 7 островов, с каждого из которых ведет 1, 3 или 5 мостов. Верно ли, что хотя бы один из этих мостов обязательно выходит на берег озера? Решение:

Да, верно, иначе нарушается теорема о числе нечетных вершин.

Задача 12:

Докажите, что число людей, когда-либо живших на Земле и сделавших нечетное число рукопожатий, четно. Решение:

Это в точности теорема о нечетных вершинах.

Задача 13:

Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими? Решение:

Нет, нельзя. Примените теорему к графу, вершины которого - данные отрезки, а ребро соединяет две вершины тогда, когда два соответствующих отрезка пересекаются.