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