Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.
Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.Рассмотрим дополнение графа знакомств в полном графе -- это удобно, так как рёбер мало. Степень каждой вершины не больше 2, и в графе нет треугольников. Рассмотрим связную компоненту. Это или линейный граф (возможно, из одной вершины), или цикл. Будем в каждой компоненте выбирать подмножество вершин, в котором нет соединений. Если мы в сумме наберём 12 человек, то задача решена: представители разных компонент между собой знакомы.
Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.Рассмотрим дополнение графа знакомств в полном графе -- это удобно, так как рёбер мало. Степень каждой вершины не больше 2, и в графе нет треугольников. Рассмотрим связную компоненту. Это или линейный граф (возможно, из одной вершины), или цикл. Будем в каждой компоненте выбирать подмножество вершин, в котором нет соединений. Если мы в сумме наберём 12 человек, то задача решена: представители разных компонент между собой знакомы.Для линейного графа раскрасим вершины через одну, и возьмём тот цвет, представителей которого не меньше. Это даст как минимум половину. Если цикл имеет чётную длину, то мы также выбираем половину -- через одного. Наконец, пусть цикл имеет длину 2k+1, где k>=2. Тогда можно взять k человек с номерами 2, 4, ... , 2k. Доля числа взятых равна k/(2k+1)>=2/5. Отсюда следует, что мы можем взять как минимум 2/5 от общего числа, а это и есть 12. Они попарно знакомы.
Мыят сай пӱртӱсыштӧ канаш йӧратена, сандене мый шукырак яндар южышто каныме дене эртара.Ме ачай дене авай, шуматкечын да эр кынелын, олашке каяш, кошташ, яндар южын тамжым налынат, жаритленыт, тул гоч тӧрштылын шылшопшар.Мыланем келшен, пеш мотор октябрь вет чодыраш.А мый коштам восресение йолташ дене коштыныт.Ондак ме мороженыйым налын, а варажым паркыште велосипед дене мунчалташ каят.Ме эсогыл таҥасымашым ышташ керт,мый сеҥенам! Тиде мый выходныевыходной чаплын эртарыш!
Я люблю хорошо отдыхать на природе, поэтому большую часть своих выходных Я провел на свежем воздухе.В субботу мы с мамой и папой рано встали, поехали за город, гуляли, наслаждаясь свежим воздухом, жарили шашлыки и прыгали через костер.Мне понравилось, ведь лес в октябре очень красив.А в восресенье я ходил гулять с друзьями.Сначала мы купили мороженое, а потом поехали в парк кататься на велосипедах.Нам даже удалось устроить соревнования,в которых Я победил!Я отлично провёл эти выходные
Поделитесь своими знаниями, ответьте на вопрос:
Укажите номера верных утверждений. 1) через любую точку проходит не менее одной прямой. 2) если при пересечении двух прямых третьей прямой соответственные углы равны 65°, то эти две прямые параллельны. 3) если при пересечении двух прямых третьей прямой внутренние накрест лежащие углы составляют в сумме 90°, то эти две прямые параллельны.