Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.
Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.Рассмотрим дополнение графа знакомств в полном графе -- это удобно, так как рёбер мало. Степень каждой вершины не больше 2, и в графе нет треугольников. Рассмотрим связную компоненту. Это или линейный граф (возможно, из одной вершины), или цикл. Будем в каждой компоненте выбирать подмножество вершин, в котором нет соединений. Если мы в сумме наберём 12 человек, то задача решена: представители разных компонент между собой знакомы.
Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.Рассмотрим дополнение графа знакомств в полном графе -- это удобно, так как рёбер мало. Степень каждой вершины не больше 2, и в графе нет треугольников. Рассмотрим связную компоненту. Это или линейный граф (возможно, из одной вершины), или цикл. Будем в каждой компоненте выбирать подмножество вершин, в котором нет соединений. Если мы в сумме наберём 12 человек, то задача решена: представители разных компонент между собой знакомы.Для линейного графа раскрасим вершины через одну, и возьмём тот цвет, представителей которого не меньше. Это даст как минимум половину. Если цикл имеет чётную длину, то мы также выбираем половину -- через одного. Наконец, пусть цикл имеет длину 2k+1, где k>=2. Тогда можно взять k человек с номерами 2, 4, ... , 2k. Доля числа взятых равна k/(2k+1)>=2/5. Отсюда следует, что мы можем взять как минимум 2/5 от общего числа, а это и есть 12. Они попарно знакомы.
Ты наверняка знаешь правило, что минус на минус дает плюс.
-8/15-(-0,4)=...
Теперь это же выражение, но словами:
минус восемь деленное на пятнадцать, то есть восемь пятнадцатых, минус минус ноль целых четыре десятых.
Отсюда получается:
минус восемь деленное на пятнадцать плюс(так как минус на минус дает плюс) ноль целых четыре десятых.
Теперь запишем числами:
-8/15+0,4=-8/15+4/10
Откуда мы получили 4/10? Это 0,4(ноль целых четыре десятых) то есть ноль целых - это ничего, четыре десятых - это четыре деленное на десять.
Теперь решаем:
-8/15+4/10=...
1. найдем общий знаменатель, он равен 30, значит первую дробь умножаем на 2, а вторую дробь на 3, получаем:
-16/30+12/30=...
2. это получается, что к минус шестнадцати мы прибавляем плюс 12, это получается минус 4, отсюда:
-16/30+12/30=-4/30=-2/15(так как можем сократить дробь на 2)
Теперь понимаешь? Если все же непонятно, то пиши.