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