Лето 5-7 класс. 3 занятие. Графы.

Публикация в группе: Подготовка к турнирам. Лето 5-7 класс

На третьем занятии летнего сложного курса по подготовке к олимпиадам и математическим турнирам мы рассмотрим тему «Графы».

Теоретический блок:

Задачный блок:

Все задачи в одном файле для скачивания (без подсказок): 3-uslovija-utjum-grafy.pdf
Все задачи в одном файле для скачивания (c подсказками): 3-uslovija-utjum-grafy-s-podskazkami.pdf

1. Дороги между 1000 городами
Источник: УТЮМ-59, 6 класс, группа «Старт», третья лига, тур 3, задача 6.

2-1 В стране 1000 городов, некоторые из них соединены дорогами. Между любыми пятью городами есть не более трёх дорог. Каково наибольшее возможное количество дорог в стране?




2. Разделение страны на две республики
Источник: УТЮМ-60, 6 класс, группа «Старт», первая лига, тур 1, задача 4.

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



3. Раскраска рёбер полного графа в 4 цвета
Источник: УТЮМ-59, 6 класс, группа «Старт», высшая лига, тур 4, задача 5.

2-3 Дан полный граф с n ≥ 3 вершинами. Нужно покрасить каждое ребро в один из четырёх цветов так, чтобы выполнялись два условия: 1) все четыре цвета встречались; 2) для любых трёх вершин три соединяющих их ребра были либо все одного цвета, либо все разных цветов. Для какого наибольшего n такая раскраска существует?


onclick=»show_text(13, ‘9. Оценка сверху. Возьмём вершину A и разобьём остальные вершины на 4 группы по цвету ребра из A. Если B и C в одной группе, то AB и AC одного цвета; тогда в треугольнике ABC третье ребро BC обязано быть того же цвета. Значит, внутри каждой группы все рёбра цвета этой группы. Докажем, что в группе не может быть 3 вершин, если есть другая непустая группа. Возьмём X из одной группы и три вершины Y1,Y2,Y3 из другой. Рёбра XYi не могут иметь цвет первой или второй группы, значит могут иметь только два оставшихся цвета. Два из них совпадут; тогда в треугольнике XYiYj две стороны одного цвета, а третья — другого, что запрещено. Поэтому каждая группа содержит не больше 2 вершин, и n≤1+4·2=9. Пример на 9 вершинах: запишем их в таблицу 3×3. Красим в один цвет тройки-строки 123,456,789; во второй — столбцы 147,258,369; в третий — диагонали 159,267,348; в четвёртый — диагонали 168,249,357. Каждая пара вершин попадает ровно в одну тройку, значит каждое ребро получает цвет. Любой треугольник либо целиком лежит в одной тройке, либо его рёбра имеют три разных цвета.’)» >

4. Красно-синие рёбра в кубе
Источник: УТЮМ-62, 6 класс, группа «Старт», высшая лига, тур 4, задача 2.

2-4 Рассмотрим граф, вершины которого — все строки из нулей и единиц длины 10. Две вершины соединены ребром, если соответствующие им строки отличаются ровно в одной позиции.
В этом графе выбрали 512 рёбер, не имеющих общих концов, и покрасили их в красный цвет. Остальные рёбра покрасили в синий цвет. Докажите, что найдётся цикл длины не более 18, в котором красные и синие рёбра чередуются.



5. Единственный общий сосед
Источник: УТЮМ-66, 7 класс, младшая группа, третья лига, тур 1, задача 7.

2-5 В государстве есть несколько городов, между любыми двумя городами не более одной дороги. Для любых двух городов A и B найдётся ровно один отличный от них город, соединённый дорогами и с A, и с B. Известно, что есть город, соединённый дорогами не более чем с двумя другими. Докажите, что есть город, соединённый дорогами со всеми остальными.



6. Три дороги из A и B
Источник: УТЮМ-59, 7 класс, младшая группа, третья лига, математический бой №1, задача 5.

В стране всего 10 городов, среди них есть столица A и культурная столица B. Некоторые города соединены дорогами. Из городов A и B выходит по три дороги, а из каждого из остальных городов — по две дороги. Из любого города можно добраться до любого другого. Известно, что все замкнутые маршруты, в которых города не повторяются, содержат по четыре дороги. Докажите, что между A и B дороги нет.


onclick=»show_text(16, ‘Предположим, что дорога AB есть. Из A, кроме дороги AB, выходят ещё две дороги. Если пойти по одной из них, то дальше в каждом промежуточном городе степень 2: одна дорога ведёт назад, а по второй путь продолжается. Так как граф связен, путь в итоге должен прийти в B. Значит, кроме ребра AB, есть ещё два пути из A в B. Пусть их длины x и y. Ребро AB вместе с первым путём образует простой цикл длины 1+x, а со вторым — цикл длины 1+y. По условию все простые циклы имеют длину 4, значит x=y=3. Но два этих пути вместе образуют простой цикл длины x+y=6, что противоречит условию. Следовательно, дороги AB нет.’)» >

7. Односторонние дороги в 28 городах
Источник: УТЮМ-60, 7 класс, младшая группа, первая лига, математический бой №3, задача 4.

3-7 В стране 28 городов. Между некоторыми городами проходят односторонние дороги. При этом нет двух таких городов A и B, что существует и дорога из A в B, и дорога из B в A. Известно, что для любых 27 городов есть циклический маршрут, проходящий по каждому из этих 27 городов ровно один раз и не проходящий по другим городам. Какое наименьшее число дорог может быть в этой стране?



8. Яблоки и друзья
Источник: УТЮМ-65, 7 класс, младшая группа, высшая лига, тур 1, задача 7.

2-8 В школе некоторые ученики дружат друг с другом. Каждый ученик пронумеровал своих друзей числами от 0 до n − 1, где n — количество его друзей. В день d каждый ученик передаёт яблоко другу с номером, равным остатку от деления d на число его друзей. Каждый день после передачи у всех снова оказывается по одному яблоку. Через некоторое время все снова собираются передавать яблоко другу с номером 0. Докажите: если два человека дружат, то у них поровну друзей.