В спортивный лагерь приехали на отдых 155 школьников. Школьники A и B считаются приятелями, если они лично знают друг друга либо если найдутся такие школьники C1,C2,…,Ck, что A знает C1, C1 знает C2, …, Ck знает B. Известно, что в лагере среди любых 8 школьников имеется пара приятелей. Требуется сформировать команду из N школьников так, чтобы любые двое в ней оказались приятелями. Для каких N это гарантированно можно сделать? Выберите все подходящие варианты:
19; 20; 23 (на фото видны только эти варианты, список обрезан)
Рассмотрим граф: вершины — школьники, рёбра — личные знакомства. Двое приятели тогда и только тогда, когда они лежат в одной компоненте связности. Поэтому школьники разбиваются на группы, внутри которых все приятели, а школьники из разных групп приятелями не являются.
Если групп хотя бы
Если групп не больше
в самой большой группе не меньше
Значение
Значит, гарантированно можно сделать команду при
Отношение «приятели» — это принадлежность одной компоненте связности. Условие означает, что компонент не больше
