Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.
Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.Рассмотрим дополнение графа знакомств в полном графе -- это удобно, так как рёбер мало. Степень каждой вершины не больше 2, и в графе нет треугольников. Рассмотрим связную компоненту. Это или линейный граф (возможно, из одной вершины), или цикл. Будем в каждой компоненте выбирать подмножество вершин, в котором нет соединений. Если мы в сумме наберём 12 человек, то задача решена: представители разных компонент между собой знакомы.
Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.Рассмотрим дополнение графа знакомств в полном графе -- это удобно, так как рёбер мало. Степень каждой вершины не больше 2, и в графе нет треугольников. Рассмотрим связную компоненту. Это или линейный граф (возможно, из одной вершины), или цикл. Будем в каждой компоненте выбирать подмножество вершин, в котором нет соединений. Если мы в сумме наберём 12 человек, то задача решена: представители разных компонент между собой знакомы.Для линейного графа раскрасим вершины через одну, и возьмём тот цвет, представителей которого не меньше. Это даст как минимум половину. Если цикл имеет чётную длину, то мы также выбираем половину -- через одного. Наконец, пусть цикл имеет длину 2k+1, где k>=2. Тогда можно взять k человек с номерами 2, 4, ... , 2k. Доля числа взятых равна k/(2k+1)>=2/5. Отсюда следует, что мы можем взять как минимум 2/5 от общего числа, а это и есть 12. Они попарно знакомы.
160 грн заработает первая бригада
80 грн заработает вторая бригада
Пошаговое объяснение:
Весь объём работы примем за 1 (одна целая) часть.
Пусть х часов время выполнения работы первой бригадой.
1/х части поля в час - производительность первой бригады
(x+12) часов - время выполнения работы второй бригадой
1/(х+12) части поля в час - производительность второй бригады
1 : 8 = 1/8 часть поля в час - производительность труда двух бригад вместе
Составим уравнение:
1/х + 1/(х+12) = 1/8 | * 8x(x+12)
8(x+12)+ 8x = x(x+12)
8x+96+8x = x² +12x
16x +96=x²+12x
x²+12x-16x-96 = 0
x²- 4x - 96 = 0
D = 16 - 4*1*(-96) = 16 +384=400=20²
x₁= (4-20)/2= -16/2 = -8 - не удовл. условию
х₂= (4+20)/2 = 24/2 = 12 (ч.) время работы первой бригады
12+12 = 24 (ч.) время работы второй бригады.
Стоимость всей выполненной работы составляет 240 грн.
1/12 * 8 = 8/12 = 2/3 части работы выполнит первая бригада
1/24 * 8 = 8/24 = 1/3 части работы выполнит вторая бригада
240 * 2/3 = 160 грн заработает первая бригада
240 * 1/3 = 80 грн заработает вторая бригада
