Олимпиадные задачи по теме «Теория графов» для 1-6 класса
Теория графов
НазадМожно ли нарисовать 1006 различных 2012-угольников, у которых все вершины общие, но при этом ни у каких двух нет ни одной общей стороны?
Любознательный турист хочет прогуляться по улицам Старого города от вокзала (точка <i>A</i> на плане) до своего отеля (точка <i>B</i>). Турист хочет, чтобы его маршрут был как можно длиннее, но дважды оказываться на одном и том же перекрестке ему неинтересно, и он так не делает. Нарисуйте на плане самый длинный возможный маршрут и докажите, что более длинного нет. <div align="center"><img align="absmiddle" src="/storage/problem-media/111897/problem_111897_img_2.gif"></div>
Кощей Бессмертный похитил у царя трёх дочерей. Отправился Иван-царевич их выручать. Приходит он к Кощею, а тот ему и говорит: "Завтра поутру увидишь пять заколдованных девушек. Три из них – царёвы дочери, а ещё две – мои. Для тебя они будут неотличимы, а сами друг дружку различать смогут. Я подойду к одной из них и стану у неё спрашивать про каждую из пятерых: "Это царевна?". Она может отвечать и правду, и неправду, но ей дозволено назвать царевнами ровно двоих (себя тоже можно называть). Потом я так же опрошу каждую из остальных девушек, и они тоже должны будут назвать царевнами ровно двоих. Если после этого угадаешь, кто из них и вправду царевны, отпущу тебя восвояси невредимым. А если ещё и догадаешься, которая царевна старшая, которая средняя, а которая младшая, то и их...
В Совершенном городе шесть площадей. Каждая площадь соединена прямыми улицами ровно с тремя другими площадями. Никакие две улицы в городе не пересекаются. Из трёх улиц, отходящих от каждой площади, одна проходит внутри угла, образованного двумя другими. Начертите возможный план такого города.
В норке живёт семья из 24 мышей. Каждую ночь ровно четыре из них отправляются на склад за сыром.
Может ли так получиться, что в некоторый момент времени каждая мышка побывала на складе с каждой ровно по одному разу?
На третье занятие кружка по математике пришло 17 человек. Может ли случиться так, что каждая девочка знакома ровно с тремя из присутствующих на занятии кружковцев, а каждый мальчик ровно с пятью?
Пешеход обошёл шесть улиц одного города, пройдя каждую ровно два раза, но не смог обойти их, пройдя каждую лишь раз. Могло ли это быть?
Как, не отрывая карандаша от бумаги, провести шесть отрезков таким образом, чтобы оказались зачёркнутыми 16 точек, расположенных в вершинах квадратной сетки 4×4?
У марсиан бывает произвольное число рук. Однажды все марсиане взялись за руки так, что свободных рук не осталось.
Докажите, что число марсиан, у которых нечётное число рук, чётно.
В каждой клетке квадрата 8×8 клеток проведена одна из диагоналей. Рассмотрим объединение этих 64 диагоналей. Оно состоит из нескольких связных частей (к одной части относятся точки, между которыми можно пройти по одной или нескольким диагоналям). Может ли количество этих частей быть
а) больше 15?
б) больше 20?
Муравей ползает по проволочному каркасу куба, при этом он никогда не поворачивает назад.
Может ли случиться, что в одной вершине он побывал 25 раз, а в каждой из остальных – по 20 раз?
В сказочной стране Перра-Терра среди прочих обитателей проживают Карабасы и Барабасы. Каждый Карабас знаком с шестью Карабасами и девятью Барабасами. Каждый Барабас знаком с десятью Карабасами и семью Барабасами. Кого в этой стране больше – Карабасов или Барабасов?
На кошачьей выставке в ряд сидят 10 котов и 19 кошек, причём рядом с каждой кошкой сидит более толстый кот.
Докажите, что рядом с каждым котом сидит кошка, которая тоньше него.
На кошачьей выставке каждый посетитель погладил ровно трех кошек. При этом оказалось, что каждую кошку погладили ровно три посетителя. Докажите, что посетителей было ровно столько же, сколько кошек.
Школьник сказал своему приятелю Вите Иванову:
– У нас в классе тридцать пять человек. И представь, каждый из них дружит ровно с одиннадцатью одноклассниками...
– Не может этого быть, – сразу ответил Витя Иванов, победитель математической олимпиады.
Почему он так решил?
В турнире участвовали шесть шахматистов. Каждые два участника турнира сыграли между собой по одной партии. Сколько всего было сыграно партий? Сколько партий сыграл каждый участник? Сколько очков набрали шахматисты все вместе?
Можно ли 77 телефонов соединить между собой проводами так, чтобы каждый был соединён ровно с пятнадцатью?
Во время шахматного турнира, несколько игроков сыграли нечётное количество партий. Докажите, что число таких игроков чётно.
Докажите, что в любом графе
а) сумма степеней всех вершин равна удвоенному числу рёбер (и следовательно, чётна);
б) число вершин нечётной степени чётно.
В Тридевятом царстве на каждом перекрёстке сходится ровно три дорожки. Было у царя три сына, старшие умные, а младший Иван – дурак. Послал старик сыновей за молодильными яблоками. Старший, выйдя из дворца, на первом перекрёстке свернул налево, на следующем направо, потом налево, снова направо – и дошёл до волшебной яблони. Средний на первом перекрёстке свернул направо, потом налево, снова направо, снова налево – и тоже дошёл до этой яблони. А Иван на всех перекрёстках поворачивал направо, три раза повернул да и пришёл обратно во дворец несолоно хлебавши. Нарисуйте пример, как может выглядеть схема дорожек в Тридевятом царстве, если известно, что и от царского дворца, и от яблони отходит ровно по одной дорожке.
В параллели 7-х классов 100 учеников, некоторые из которых дружат друг с другом. 1 сентября они организовали несколько клубов, каждый из которых основали три ученика (у каждого клуба свои). Дальше каждый день в каждый клуб вступали те ученики, кто дружил хотя бы с тремя членами клуба. К 19 февраля в клубе «Гепарды» состояли все ученики параллели. Могло ли получиться так, что в клубе «Черепахи» в этот же день состояло ровно 50 учеников?
Среди 49 школьников каждый знаком не менее чем с 25 другими.
Докажите, что можно их разбить на группы из двух или трёх человек так, чтобы каждый был знаком со всеми в своей группе.
Среди актеров театра Карабаса Барабаса прошёл шахматный турнир. Каждый участник сыграл с каждым из остальных ровно один раз. За победу давали один сольдо, за ничью – полсольдо, за поражение не давалось ничего. Оказалось, что среди каждых трёх участников найдётся шахматист, заработавший в партиях с двумя другими ровно 1,5 сольдо. Какое наибольшее количество актеров могло участвовать в таком турнире?
Впишите в пять кружков натуральные числа так, чтобы выполнялись два условия:
- если два кружка соединены линией, то стоящие в них числа должны отличаться ровно в два или ровно в четыре раза;
- если два кружка не соединены линией, то отношение стоящих в них чисел не должно быть равно ни 2, ни 4.<div align="center"><img src="/storage/problem-media/64693/problem_64693_img_2.gif"></div>
Компания из нескольких друзей вела переписку так, что каждое письмо получали все, кроме отправителя. Каждый написал одно и то же количество писем, в результате чего всеми вместе было получено 440 писем. Сколько человек могло быть в этой компании?