Считаем рёбра
Ошибка.
Попробуйте повторить позже
В школе любые два ребёнка либо дружат друг с другом, либо нет. Назовём ребёнка общительным, если он дружит хотя бы с тремя другими
детьми. Известно, что в школе есть 
общительных детей, а также ровно 
детей, у которых всего один друг. При каком наименьшем
заведомо найдётся несколько детей, которых можно посадить за круглый стол так, чтобы каждый знал обоих своих
соседей?
Подсказка 1
Давайте переведём условие на язык графов и поймëм, что от нас хотят. Если считать детей вершинами, и пусть всего их N, а дружбу - рëбрами, то тогда круглый стол, описанный в условии - это цикл. То есть нас спрашивают, при каком наименьшем n в графе найдется хотя бы 1 цикл.
Подсказка 2
Давайте вспомним критерий наличия цикла в графе. Он есть тогда и только тогда, когда граф не является деревом, то есть когда в нëм количество рëбер не меньше количества вершин.
Подсказка 3
Почитайте сумму степеней графа и посмотрите, при каком n она будет не меньше 2N.
Будем представлять детей в виде вершин графа, а факт дружбы между детьми в виде ребра, соединяющие вершины, соответствующие
друзьям. Давайте сразу предварительно удалим изолированные вершины, то есть детей, которые ни с кем не дружат. Они
никак не повлияют на задачу. Оставшееся число обозначим за 
Если 
то сумма степеней вершин не меньше
чем
Сумма степеней вершин четная, есть то она равна как минимум 
а тогда ребер хотя бы 
из чего следует, что найдется цикл, а
значит при 
заведомо найдётся несколько детей, которых можно посадить за круглый стол так, чтобы каждый знал обоих своих
соседей (очевидно, что друзья знают друг друга). Если же 
то можно построить пример, когда цикла не будет и, следовательно,
указанная рассадка не возможна. Например, возьмем 
вершин, соединим их путем (
ребер) и затем ко всем вершинам, кроме концов
добавим “висячую” вершину.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
