Олимпиадные задачи по теме «Комбинаторика» для 9-11 класса
В некотором городе сеть автобусных маршрутов устроена так, что каждые два маршрута имеют ровно одну общую остановку, и на каждом маршруте есть хотя бы 4 остановки. Докажите, что все остановки можно распределить между двумя компаниями так, что на каждом маршруте найдутся остановки обеих компаний.
Назовём компанию <i>k-неразбиваемой</i>, если при любом разбиении её на <i>k</i> групп в одной из групп найдутся два знакомых человека. Дана 3-неразбиваемая компания, в которой нет четырёх попарно знакомых человек. Докажите, что её можно разделить на две компании, одна из которых 2-неразбиваемая, а другая – 1-неразбиваемая.
В королевстве <i>N</i> городов, некоторые пары которых соединены непересекающимися дорогами с двусторонним движением (города из такой пары называются <i>соседними</i>). При этом известно, что из каждого города можно доехать до любого другого, но невозможно, выехав из некоторого города и двигаясь по различным дорогам, вернуться в исходный город.
Однажды Король провел такую реформу: каждый из <i>N</i> мэров городов стал снова мэром одного из <i>N</i> городов, но, возможно, не того города, в котором он работал до реформы. Оказалось, что каждые два мэра, работавшие в соседних городах до реформы, оказались в соседних городах и после реформы. Докажите, что либо найдётся город, в котором мэр после реформы не поменялся, либо найдётся пара сос...
В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более <i>N</i> различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на 2<i>N</i> + 2 республики так, чтобы никакие два города из одной республики не были соединены дорогой.
В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более <i>N</i> различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на <i>N</i> + 2 республики так, чтобы никакие два города из одной республики не были соединены дорогой.
В стране несколько городов, некоторые пары городов соединены двусторонними беспосадочными авиалиниями, принадлежащими <i> k </i> авиакомпаниям. Известно, что каждые две линии одной авиакомпании имеют общий конец. Докажите, что все города можно разбить на <i>k</i> + 2 группы так, что никакие два города из одной группы не соединены авиалинией.
Дано дерево с <i>n</i> вершинами, <i>n</i> ≥ 2. В его вершинах расставлены числа <i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, <i>x<sub>n</sub></i>, а на каждом ребре записано произведение чисел, стоящих в концах этого ребра. Обозначим через <i>S</i> сумму чисел на всех рёбрах. Докажите, что <img align="absmiddle" src="/storage/problem-media/109782/problem_109782_img_2.gif">
В стране 2001 город, некоторые пары городов соединены дорогами, причём из каждого города выходит хотя бы одна дорога и нет города, соединённого дорогами со всеми остальными. Назовём множество городов <i>D доминирующим</i>, если каждый не входящий в <i>D</i> город соединён дорогой с одним из городов множества <i>D</i>. Известно, что в каждом доминирующем множестве хотя бы <i>k</i> городов. Докажите, что страну можно разбить на 2001 – <i>k</i> республик так, что никакие два города из одной республики не будут соединены дорогой.
В некоторой группе из 12 человек среди каждых девяти найдутся пять попарно знакомых. Докажите, что в этой группе найдутся шесть попарно знакомых.
В стране некоторые пары городов соединены односторонними прямыми авиарейсами (между любыми двумя городами есть не более одного рейса). Скажем, что город <i>A доступен</i> для города <i>B</i>, если из <i>B</i> можно долететь в <i>A</i>, возможно, с пересадками. Известно, что для любых двух городов <i>P</i> и <i>Q</i> существует город <i>R</i>, для которого и <i>P</i>, и <i>Q</i> доступны. Докажите, что существует город, для которого доступны все города страны. (Считается, что город доступен для себя.)