Лето 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 такая раскраска существует?



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 дороги нет.



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. Докажите: если два человека дружат, то у них поровну друзей.