Олимпиадные задачи по теме «Теория графов» для 4-11 класса

Можно ли нарисовать 1006 различных 2012-угольников, у которых все вершины общие, но при этом ни у каких двух нет ни одной общей стороны?

Куб с ребром <i>n</i> составлен из белых и чёрных кубиков с ребром 1 таким образом, что каждый белый кубик имеет общую грань ровно с тремя чёрными, а каждый чёрный – ровно с тремя белыми. При каких <i>n</i> это возможно?

При каких <i>n</i> можно оклеить в один слой поверхность клетчатого куба <i>n</i>×<i>n</i>×<i>n</i> бумажными прямоугольниками 1×2 так, чтобы каждый прямоугольник граничил по отрезкам сторон ровно с пятью другими?

Туристическая фирма провела акцию: "Купи путевку в Египет, приведи четырёх друзей, которые также купят путевку, и получи стоимость путевки обратно". За время действия акции 13 покупателей пришли сами, остальных привели друзья. Некоторые из них привели ровно по четыре новых клиента, а остальные 100 не привели никого. Сколько туристов отправились в Страну Пирамид бесплатно?

Изначально на доске были написаны одночленs  1, <i>x, x</i>², ..., <i>xⁿ</i>.  Договорившись заранее, <i>k</i> мальчиков каждую минуту одновременно вычисляли каждый сумму каких-то двух многочленов, написанных на доске, и результат дописывали на доску. Через <i>m</i> минут на доске были написаны, среди прочих, многочлены  <i>S</i>₁ = 1 + <i>x,  S</i>₂ = 1 + <i>x + x</i>²,  <i>S</i>₃ = 1 + <i>x + x</i>² + <i>x</i>³,  ...,  <i>S_n</i> = 1 + <i>x + x</i>² + ... + <i>xⁿ</i>.  Докажите...

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

На собрание пришло <i>n</i> человек  (<i>n</i> > 1).  Оказалось, что у каждых двух из них среди собравшихся есть ровно двое общих знакомых.

  а) Докажите, что каждый из них знаком с одинаковым числом людей на этом собрании.

  б) Покажите, что <i>n</i> может быть больше 4.

Рассмотрим граф, у которого вершины соответствуют всевозможным трёхэлементным подмножествам множества  {1, 2, 3, ..., 2<i>^k</i>},  а рёбра проводятся между вершинами, которые соответствуют подмножествам, пересекающимся ровно по одному элементу. Найдите минимальное количество цветов, в которые можно раскрасить вершины графа так, чтобы любые две вершины, соединённые ребром, были разного цвета.

<img align="right" src="/storage/problem-media/116673/problem_116673_img_2.gif">Кузнечик умеет прыгать только ровно на 50 см. Он хочет обойти 8 точек, отмеченных на рисунке (сторона клетки равна 10 см). Какое наименьшее количество прыжков ему придётся сделать? (Разрешается посещать и другие точки плоскости, в том числе не узлы сетки. Начинать и заканчивать можно в любых точках.)

Клетчатый квадрат 2010×2010 разрезан на трёхклеточные уголки. Докажите, что можно в каждом уголке отметить по клетке так, чтобы в каждой вертикали и в каждой горизонтали было поровну отмеченных клеток.

Назовём компанию <i>k-неразбиваемой</i>, если при любом разбиении её на <i>k</i> групп в одной из групп найдутся два знакомых человека. Дана 3-неразбиваемая компания, в которой нет четырёх попарно знакомых человек. Докажите, что её можно разделить на две компании, одна из которых 2-неразбиваемая, а другая – 1-неразбиваемая.

В некотором государстве система авиалиний устроена таким образом, что каждый город соединен авиалиниями не более чем с тремя другими, и из каждого города можно попасть в любой другой, сделав не более одной пересадки. Какое наибольшее количество городов может быть в этом государстве?

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

В стране 100 городов и несколько дорог. Каждая дорога соединяет два каких-то города, дороги не пересекаются. Из каждого города можно добраться до любого другого, двигаясь по дорогам. Докажите, что можно объявить несколько дорог главными так, чтобы из каждого города выходило нечётное число главных дорог.

Оля и Максим оплатили путешествие по архипелагу из 2009 островов, где некоторые острова связаны двусторонними маршрутами катера. Они путешествуют, играя. Сначала Оля выбирает остров, на который они прилетают. Затем они путешествуют вместе на катерах, по очереди выбирая остров, на котором еще не были (первый раз выбирает Максим). Кто не сможет выбрать остров, проиграл. Докажите, что Оля может выиграть.

На доске выписано  (<i>n</i> – 1)<i>n</i>  выражений:   <i>x</i>₁ – <i>x</i>₂,  <i>x</i>₁ – <i>x</i>₃,  ...,  <i>x</i>₁ – <i>x_n</i>,  <i>x</i>₂ – <i>x</i>₁,  <i>x</i>₂ – <i>x</i>₃,  ...,  <i>x</i>₂ – <i>x_n</i>,  ...,  <i>x_n</i> – <i>x</i>_<i>n</i>–1,   где  <i>n</i&...

В некой стране 100 городов (города считайте точками на плоскости). В справочнике для каждой пары городов имеется запись, каково расстояние между ними (всего 4950 записей).   а) Одна запись стёрлась. Всегда ли можно однозначно восстановить её по остальным?   б) Пусть стёрлись <i>k</i> записей, и известно, что в этой стране никакие три города не лежат на одной прямой. При каком наибольшем <i>k</i> всегда можно однозначно восстановить стёршиеся записи?

На плоскости отметили 4<i>n</i> точек, после чего соединили отрезками все пары точек, расстояние между которыми равно 1 см. Оказалось, что среди любых  <i>n</i> + 1  точек обязательно есть две, соединённые отрезком. Докажите, что всего проведено не менее 7<i>n</i> отрезков.

В некоторых клетках квадрата 20×20 стоит стрелочка в одном из четырёх направлений. На границе квадрата все стрелочки смотрят вдоль границы по часовой стрелке (см. рис.). Кроме того, стрелочки в соседних (возможно, по диагонали) клетках не смотрят в противоположных направлениях. Докажите, что найдётся клетка, в которой стрелочки нет. <div align="center"><img src="/storage/problem-media/115497/problem_115497_img_2.gif"> </div>

На дне рождения у Васи было 10 ребят (включая Васю). Оказалось, что у каждых двух из этих ребят есть общий дедушка.

Докажите, что у семи из них есть общий дедушка.

  В королевстве <i>N</i> городов, некоторые пары которых соединены непересекающимися дорогами с двусторонним движением (города из такой пары называются <i>соседними</i>). При этом известно, что из каждого города можно доехать до любого другого, но невозможно, выехав из некоторого города и двигаясь по различным дорогам, вернуться в исходный город.

  Однажды Король провел такую реформу: каждый из <i>N</i> мэров городов стал снова мэром одного из <i>N</i> городов, но, возможно, не того города, в котором он работал до реформы. Оказалось, что каждые два мэра, работавшие в соседних городах до реформы, оказались в соседних городах и после реформы. Докажите, что либо найдётся город, в котором мэр после реформы не поменялся, либо найдётся пара сос...

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

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

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

Любознательный турист хочет прогуляться по улицам Старого города от вокзала (точка <i>A</i> на плане) до своего отеля (точка <i>B</i>). Турист хочет, чтобы его маршрут был как можно длиннее, но дважды оказываться на одном и том же перекрестке ему неинтересно, и он так не делает. Нарисуйте на плане самый длинный возможный маршрут и докажите, что более длинного нет. <div align="center"><img align="absmiddle" src="/storage/problem-media/111897/problem_111897_img_2.gif"></div>

У выпуклого многогранника одна вершина <i>A</i> имеет степень 5, а все остальные – степень 3. Назовём раскраску рёбер многогранника в синий, красный и лиловый цвета <i>хорошей</i>, если для каждой вершины степени 3 все выходящие из нее ребра покрашены в разные цвета. Оказалось, что количество хороших раскрасок не делится на 5. Докажите, что в одной из хороших раскрасок какие-то три последовательных ребра, выходящие из <i> A </i>, покрашены в один цвет.