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

Можно ли нарисовать 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 не привели никого. Сколько туристов отправились в Страну Пирамид бесплатно?

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

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

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

25 мальчиков и несколько девочек собрались на вечеринке и обнаружили забавную закономерность. Если выбрать любую группу не меньше чем из 10 мальчиков, а потом добавить к ним всех девочек, знакомых хотя бы с одним из этих мальчиков, то в получившейся группе число мальчиков окажется на 1 меньше, чем число девочек. Докажите, что некоторая девочка знакома не менее чем с 16 мальчиками.

В Совершенном городе шесть площадей. Каждая площадь соединена прямыми улицами ровно с тремя другими площадями. Никакие две улицы в городе не пересекаются. Из трёх улиц, отходящих от каждой площади, одна проходит внутри угла, образованного двумя другими. Начертите возможный план такого города.

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

Докажите, что найдётся пара и не соседних чисел с таким же свойством.

В норке живёт семья из 24 мышей. Каждую ночь ровно четыре из них отправляются на склад за сыром.

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

На третье занятие кружка по математике пришло 17 человек. Может ли случиться так, что каждая девочка знакома ровно с тремя из присутствующих на занятии кружковцев, а каждый мальчик ровно с пятью?

В квадрате 6×6 отмечают несколько клеток так, что из любой отмеченной можно пройти в любую другую отмеченную, переходя только через общие стороны отмеченных клеток. Отмеченную клетку называют<i>концевой</i>, если она граничит по стороне ровно с одной отмеченной. Отметьте несколько клеток так, чтобы получилось   а) 10,  б) 11,  в) 12 концевых клеток.

Резидент одной иностранной разведки сообщил в центр о готовящемся подписании ряда двусторонних соглашений между пятнадцатью бывшими республиками СССР. Согласно его донесению, каждая из них заключит договор ровно с тремя другими. Заслуживает ли резидент доверия?

Как, не отрывая карандаша от бумаги, провести шесть отрезков таким образом, чтобы оказались зачёркнутыми 16 точек, расположенных в вершинах квадратной сетки 4&times4?

Метро города Урюпинска состоит из трёх линий и имеет по крайней мере две конечные станции и по крайней мере два пересадочных узла, причём ни одна из конечных станций не является пересадочной. С каждой линии на любую из остальных можно перейти по крайней мере в двух местах. Нарисуйте пример такой схемы метро, если известно, что это можно сделать, не отрывая карандаша от бумаги и не проводя два раза один и тот же отрезок.

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

Докажите, что число марсиан, у которых нечётное число рук, чётно.

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

В основании призмы лежит <i>n</i>-угольник. Требуется раскрасить все 2<i>n</i> её вершин тремя красками так, чтобы каждая вершина была связана рёбрами с вершинами всех трёх цветов.

  а) Докажите, что если <i>n</i> делится на 3, то такая раскраска возможна.

  б) Докажите, что если если такая раскраска возможна, то <i>n</i> делится на 3.

При каком  <i>n</i> > 1  может случиться так, что в компании из  <i>n</i> + 1  девочек и <i>n</i> мальчиков все девочки знакомы с разным числом мальчиков, а все мальчики – с одним и тем же числом девочек?

а) Может ли случиться, что в компании из 10 девочек и 9 мальчиков все девочки знакомы с разным числом мальчиков, а все мальчики – с одним и тем же числом девочек?

б) А если девочек 11, а мальчиков 10?

Каждый из 450 депутатов парламента дал пощёчину ровно одному своему коллеге.

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

В каждой клетке квадрата  8×8  клеток проведена одна из диагоналей. Рассмотрим объединение этих 64 диагоналей. Оно состоит из нескольких связных частей (к одной части относятся точки, между которыми можно пройти по одной или нескольким диагоналям). Может ли количество этих частей быть

  а) больше 15?

  б) больше 20?

Муравей ползает по проволочному каркасу куба, при этом он никогда не поворачивает назад.

Может ли случиться, что в одной вершине он побывал 25 раз, а в каждой из остальных – по 20 раз?

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

(В королевстве действовал закон: "вассал моего вассала – не мой вассал".)