Олимпиадные задачи по теме «Комбинаторика» - сложность 3-5 с решениями
300 бюрократов разбиты на три комиссии по 100 человек. Каждые два бюрократа либо знакомы друг с другом, либо незнакомы. Докажите, что найдутся два таких бюрократа из разных комиссий, что в третьей комиссии есть либо 17 человек, знакомых с обоими, либо 17 человек, незнакомых с обоими.
Имеются три комиссии бюрократов. Известно, что для каждой пары бюрократов из разных комиссий среди членов оставшейся комиссии есть ровно 10 бюрократов, которые знакомы с обоими, и ровно 10 бюрократов, которые незнакомы с обоими. Найдите общее число бюрократов в комиссиях.
На вечеринку пришли 100 человек. Затем те, у кого не было знакомых среди пришедших, ушли. Затем те, у кого был ровно один знакомый среди оставшихся, тоже ушли. Затем аналогично поступали те, у кого было ровно 2, 3, 4, ..., 99 знакомых среди оставшихся к моменту их ухода.
Какое наибольшее число людей могло остаться в конце?
На встречу выпускников пришло 45 человек. Оказалось, что любые двое из них, имеющие одинаковое число знакомых среди пришедших, не знакомы друг с другом. Какое наибольшее число пар знакомых могло быть среди участвовавших во встрече?
В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более <i>N</i> различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на <i>N</i> + 2 республики так, чтобы никакие два города из одной республики не были соединены дорогой.
В кабинете президента стоят 2004 телефона, любые два из которых соединены проводом одного из четырёх цветов. Известно, что провода всех четырёх цветов присутствуют. Всегда ли можно выбрать несколько телефонов так, чтобы среди соединяющих их проводов встречались провода ровно трех цветов?
В компании из 2<i>n</i> + 1 человека для любых <i>n</i> человек найдётся отличный от них человек, знакомый с каждым из них.
Докажите, что в этой компании есть человек, знающий всех.
Клетки таблицы 100×100 окрашены в 4 цвета так, что в каждой строке и в каждом столбце ровно по 25 клеток каждого цвета.
Докажите, что найдутся две строки и два столбца, все четыре клетки на пересечении которых окрашены в разные цвета.
В городе Цветочном<i>n</i>площадей и<i>m</i>улиц (<i>m</i>≥<i>n</i>+ 1). Каждая улица соединяет две площади и не проходит через другие площади. По существующей в городе традиции улица может называться либо Синей, либо Красной. Ежегодно в городе происходит переименование: выбирается площадь и переименовываются все выходящие из неё улицы. Докажите, что можно назвать улицы так, что переименованиями нельзя добиться одинаковых названий у всех улиц города.
В Швамбрании некоторые города связаны двусторонними беспосадочными авиарейсами. Рейсы разделены между тремя авиакомпаниями, причём если какая-то авиакомпания обслуживает линию между городами А и Б, то самолёты других компаний между этими городами не летают. Известно, что из каждого города летают самолёты всех трёх компаний. Докажите, что можно, вылетев из некоторого города, вернуться в него, воспользовавшись по пути рейсами всех трёх компаний и не побывав ни в одном из промежуточных городов дважды.
Петя поставил на доску 50×50 несколько фишек, в каждую клетку – не больше одной. Докажите, что у Васи есть способ поставить на свободные поля этой же доски не более 99 новых фишек (возможно, ни одной) так, чтобы по-прежнему в каждой клетке стояло не больше одной фишки, и в каждой строке и каждом столбце этой доски оказалось чётное количество фишек.