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

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

Туристическая фирма провела акцию: "Купи путевку в Египет, приведи четырёх друзей, которые также купят путевку, и получи стоимость путевки обратно". За время действия акции 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>.  Докажите...

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

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

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

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

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

В некой стране 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>

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

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

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

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

В стране есть <i>N</i> городов. Некоторые пары из них соединены беспосадочными двусторонними авиалиниями. Оказалось, что для любого <i>k</i>  (2 ≤ <i>k ≤ N</i>)  при любом выборе <i>k</i> городов количество авиалиний между этими городами не будет превосходить  2<i>k</i> – 2.  Докажите, что все авиалинии можно распределить между двумя авиакомпаниями так, что не будет замкнутого авиамаршрута, в котором все авиалинии принадлежат одной компании.

Имеются три комиссии бюрократов. Известно, что для каждой пары бюрократов из разных комиссий среди членов оставшейся комиссии есть ровно 10 бюрократов, которые знакомы с обоими, и ровно 10 бюрократов, которые незнакомы с обоими. Найдите общее число бюрократов в комиссиях.

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

Клетчатая прямоугольная сетка <i>m</i>×<i>n</i> связана из верёвочек единичной длины. Двое делают ходы по очереди. За один ход можно разрезать (посередине) не разрезанную ранее единичную верёвочку. Если не останется ни одного замкнутого верёвочного контура, то игрок, сделавший последний ход, считается проигравшим. Кто из игроков победит при правильной игре и как он должен для этого играть?

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

В некотором государстве было 2004 города, соединённых дорогами так, что из каждого города можно было добраться до любого другого. Известно, что при запрещённом проезде по любой из дорог по-прежнему из каждого города можно было добраться до любого другого. Министр транспорта и министр внутренних дел по очереди вводят на дорогах, пока есть возможность, одностороннее движение (на одной дороге за ход), причём министр, после хода которого из какого-либо города стало невозможно добраться до какого-либо другого, немедленно уходит в отставку. Первым ходит министр транспорта.

Может ли кто-либо из министров добиться отставки другого независимо от его игры?

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

В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более <i>N</i> различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на  2<i>N</i> + 2  республики так, чтобы никакие два города из одной республики не были соединены дорогой.

Из 54 одинаковых единичных картонных квадратов сделали незамкнутую цепочку, соединив их шарнирно вершинами. Каждый квадрат (кроме крайних) соединён с соседями двумя противоположными вершинами. Можно ли этой цепочкой квадратов полностью закрыть поверхность куба 3×3×3?

Улицы города Дужинска – простые ломаные, не пересекающиеся между собой во внутренних точках. Каждая улица соединяет два перекрёстка и покрашена в один из трёх цветов: белый, красный или синий. На каждом перекрёстке сходятся ровно три улицы, по одной каждого цвета. Перекрёсток называется <i>положительным</i>, если при его обходе против часовой стрелки цвета улиц идут в следующем порядке: белый, синий, красный, и <i>отрицательным</i> в противном случае. Докажите, что разность между числом положительных и числом отрицательных перекрёстков кратна 4.

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

Десять попарно различных ненулевых чисел таковы, что для каждых двух из них либо сумма этих чисел, либо их произведение – рациональное число.

Докажите, что квадраты всех чисел рациональны.

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