Задача № 217016
Можно ли нарисовать 1006 различных 2012-угольников, у которых все вершины общие, но при этом ни у каких двух нет ни одной общей стороны?
Олимпиадные задачи по теме «Теория графов» - сложность 1-3 с решениями
Найдите задачу для урока, кружка или самостоятельной работы.
Задача № 216993
Куб с ребром n составлен из белых и чёрных кубиков с ребром 1 таким образом, что каждый белый кубик имеет общую грань ровно с тремя чёрными, а каждый чёрный – ровно с тремя белыми. При каких n это возможно?
Задача № 216911
При каких n можно оклеить в один слой поверхность клетчатого куба n×n×n бумажными прямоугольниками 1×2 так, чтобы каждый прямоугольник граничил по отрезкам сторон ровно с пятью другими?
Задача № 216875
Туристическая фирма провела акцию: "Купи путевку в Египет, приведи четырёх друзей, которые также купят путевку, и получи стоимость путевки обратно". За время действия акции 13 покупателей пришли сами, остальных привели друзья. Некоторые из них привели ровно по четыре новых клиента, а остальные 100 не привели никого. Сколько туристов отправились в Страну Пирамид бесплатно?
Задача № 216762
В некотором городе сеть автобусных маршрутов устроена так, что каждые два маршрута имеют ровно одну общую остановку, и на каждом маршруте есть хотя бы 4 остановки. Докажите, что все остановки можно распределить между двумя компаниями так, что на каждом маршруте найдутся остановки обеих компаний.
Задача № 216699
На собрание пришло n человек (n > 1). Оказалось, что у каждых двух из них среди собравшихся есть ровно двое общих знакомых. а) Докажите, что каждый из них знаком с одинаковым числом людей на этом собрании. б) Покажите, что n может быть больше 4.
Задача № 216673
Кузнечик умеет прыгать только ровно на 50 см. Он хочет обойти 8 точек, отмеченных на рисунке (сторона клетки равна 10 см). Какое наименьшее количество прыжков ему придётся сделать? (Разрешается посещать и другие точки плоскости, в том числе не узлы сетки. Начинать и заканчивать можно в любых точках.)
Задача № 216441
В некотором государстве система авиалиний устроена таким образом, что каждый город соединен авиалиниями не более чем с тремя другими, и из каждого города можно попасть в любой другой, сделав не более одной пересадки. Какое наибольшее количество городов может быть в этом государстве?
Задача № 216409
Среди участников олимпиады каждый знаком не менее чем с тремя другими. Докажите, что можно выбрать группу из чётного числа участников (больше двух человек) и посадить их за круглый стол так, чтобы каждый был знаком с обоими соседями.
Задача № 216272
В стране 100 городов и несколько дорог. Каждая дорога соединяет два каких-то города, дороги не пересекаются. Из каждого города можно добраться до любого другого, двигаясь по дорогам. Докажите, что можно объявить несколько дорог главными так, чтобы из каждого города выходило нечётное число главных дорог.
Задача № 216219
На доске выписано (n – 1)n выражений: x1 – x2, x1 – x3, ..., x1 – xn, x2 – x1, x2 – x3, ..., x2 – xn, ..., xn – xn–1, где n ≥ 3. Лёша записал в тетрадь все эти выражения, их суммы по два различных, по три различных и т. д. вплоть до суммы всех выражений. При этом Лёша во всех выписываемых суммах приводил подобные слагаемые (например, вместо (x1 – x2) + (x2 – x3) Лёша запишет x1 – x3, а вместо (x1 – x2) + (x2 – x1) он запишет 0). Сколько выражений Лёша записал в тетрадь ровно по одному разу?
Задача № 216047
В некой стране 100 городов (города считайте точками на плоскости). В справочнике для каждой пары городов имеется запись, каково расстояние между ними (всего 4950 записей). а) Одна запись стёрлась. Всегда ли можно однозначно восстановить её по остальным? б) Пусть стёрлись k записей, и известно, что в этой стране никакие три города не лежат на одной прямой. При каком наибольшем k всегда можно однозначно восстановить стёршиеся записи?
Задача № 215467
На дне рождения у Васи было 10 ребят (включая Васю). Оказалось, что у каждых двух из этих ребят есть общий дедушка. Докажите, что у семи из них есть общий дедушка.
Задача № 215396
В стране некоторые пары городов соединены дорогами, которые не пересекаются вне городов. В каждом городе установлена табличка, на которой указана минимальная длина маршрута, выходящего из этого города и проходящего по всем остальным городам страны (маршрут может проходить по некоторым городам больше одного раза и не обязан возвращаться в исходный город). Докажите, что любые два числа на табличках отличаются не более чем в полтора раза.
Задача № 215371
В компании из семи человек любые шесть могут сесть за круглый стол так, что каждые два соседа окажутся знакомыми. Докажите, что и всю компанию можно усадить за круглый стол так, что каждые два соседа окажутся знакомыми.
Задача № 211897
Любознательный турист хочет прогуляться по улицам Старого города от вокзала (точка A на плане) до своего отеля (точка B). Турист хочет, чтобы его маршрут был как можно длиннее, но дважды оказываться на одном и том же перекрестке ему неинтересно, и он так не делает. Нарисуйте на плане самый длинный возможный маршрут и докажите, что более длинного нет.
Задача № 211817
300 бюрократов разбиты на три комиссии по 100 человек. Каждые два бюрократа либо знакомы друг с другом, либо незнакомы. Докажите, что найдутся два таких бюрократа из разных комиссий, что в третьей комиссии есть либо 17 человек, знакомых с обоими, либо 17 человек, незнакомых с обоими.
Задача № 211793
В классе учится 15 мальчиков и 15 девочек. В день 8 Марта некоторые мальчики позвонили некоторым девочкам и поздравили их с праздником (никакой мальчик не звонил одной и той же девочке дважды). Оказалось, что детей можно единственным образом разбить на 15 пар так, чтобы в каждой паре оказались мальчик с девочкой, которой он звонил. Какое наибольшее число звонков могло быть сделано?
Задача № 211780
25 мальчиков и несколько девочек собрались на вечеринке и обнаружили забавную закономерность. Если выбрать любую группу не меньше чем из 10 мальчиков, а потом добавить к ним всех девочек, знакомых хотя бы с одним из этих мальчиков, то в получившейся группе число мальчиков окажется на 1 меньше, чем число девочек. Докажите, что некоторая девочка знакома не менее чем с 16 мальчиками.
Задача № 211685
Барон Мюнхгаузен рассказывал, что у него есть карта страны Оз с пятью городами. Каждые два города соединены дорогой, не проходящей через другие города. Каждая дорога пересекает на карте не более одной другой дороги (и не более одного раза). Дороги обозначены жёлтым или красным (по цвету кирпича, которым вымощены), и при обходе вокруг каждого города (по периметру) цвета выходящих из него дорог чередуются. Могут ли слова барона быть правдой?
Задача № 211260
Клетчатая прямоугольная сетка m×n связана из верёвочек единичной длины. Двое делают ходы по очереди. За один ход можно разрезать (посередине) не разрезанную ранее единичную верёвочку. Если не останется ни одного замкнутого верёвочного контура, то игрок, сделавший последний ход, считается проигравшим. Кто из игроков победит при правильной игре и как он должен для этого играть?
Задача № 210222
Каждая деталь конструктора "Юный паяльщик" – это скобка в виде буквы П, состоящая из трёх единичных отрезков. Можно ли из деталей этого конструктора спаять полный проволочный каркас куба 2×2×2, разбитого на кубики 1×1×1? (Каркас состоит из 27 точек, соединённых единичными отрезками; любые две соседние точки должны быть соединены ровно одним проволочным отрезком.)
Задача № 210136
На вечеринку пришли 100 человек. Затем те, у кого не было знакомых среди пришедших, ушли. Затем те, у кого был ровно один знакомый среди оставшихся, тоже ушли. Затем аналогично поступали те, у кого было ровно 2, 3, 4, ..., 99 знакомых среди оставшихся к моменту их ухода. Какое наибольшее число людей могло остаться в конце?
Задача № 210126
На встречу выпускников пришло 45 человек. Оказалось, что любые двое из них, имеющие одинаковое число знакомых среди пришедших, не знакомы друг с другом. Какое наибольшее число пар знакомых могло быть среди участвовавших во встрече?
Задача № 210068
Множество клеток на клетчатой плоскости назовем ладейно связным, если из каждой его клетки можно попасть в любую другую, двигаясь по клеткам этого множества ходом ладьи (ладье разрешается перелетать через поля, не принадлежащие нашему множеству). Докажите, что ладейно связное множество из 100 клеток можно разбить на пары клеток, лежащих в одной строке или в одном столбце.
1–25 из 333