Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.
Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.Рассмотрим дополнение графа знакомств в полном графе -- это удобно, так как рёбер мало. Степень каждой вершины не больше 2, и в графе нет треугольников. Рассмотрим связную компоненту. Это или линейный граф (возможно, из одной вершины), или цикл. Будем в каждой компоненте выбирать подмножество вершин, в котором нет соединений. Если мы в сумме наберём 12 человек, то задача решена: представители разных компонент между собой знакомы.
Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.Рассмотрим дополнение графа знакомств в полном графе -- это удобно, так как рёбер мало. Степень каждой вершины не больше 2, и в графе нет треугольников. Рассмотрим связную компоненту. Это или линейный граф (возможно, из одной вершины), или цикл. Будем в каждой компоненте выбирать подмножество вершин, в котором нет соединений. Если мы в сумме наберём 12 человек, то задача решена: представители разных компонент между собой знакомы.Для линейного графа раскрасим вершины через одну, и возьмём тот цвет, представителей которого не меньше. Это даст как минимум половину. Если цикл имеет чётную длину, то мы также выбираем половину -- через одного. Наконец, пусть цикл имеет длину 2k+1, где k>=2. Тогда можно взять k человек с номерами 2, 4, ... , 2k. Доля числа взятых равна k/(2k+1)>=2/5. Отсюда следует, что мы можем взять как минимум 2/5 от общего числа, а это и есть 12. Они попарно знакомы.
движение ВА с начальной скоростью = 1час.30 мин
увеличение скорости = 25 км/час
выигрыш ВА во времени 1 час 30 мин
Найти: первоначальную скорость.
Решение: Основная формула путь равен произведению скорости и времени. 1 час 30 мин = 1,5 часа
Пусть Х, км/час первоначальная скорость; тогда:
300/Х, час время на пути АВ:
1,5Х, км расстояние, пройденное на пути ВА с первоначальной скоростью;
(Х + 25), км/час увеличенная скорость
(300 - 1,5Х), км расстояние, пройденное с увеличенной скоростью;
(300-1,5Х)/(Х+25), час время движения с увеличенной скоростью;
(300-1,5Х)/(Х+25) + 1,5 общее время обратного пути ВА
300/Х - [(300-1,5Х)/(Х+25) + 1,5] = 1,5 по условию.
Решим данное уравнение:
300/Х - (300-1,5Х)/(Х+25) = 3;
300(Х+25) - (300 - 1,5Х)Х = 3Х(Х+25);
300Х + 7500 - 300Х + 1,5Х² = 3Х² + 75Х;
-1,5Х² - 75Х + 7500 = 0 |: -1,5
Х² + 50Х -5000 = 0
D = 50² + 4*5000 = 2500 + 20000 = 22500; D>0
Х₁ = (-50 + √D)/2 = (-50 + 150)/2 = 50 (км/час)
Х₂= (-50-150)/2 = -100 не имеет смысла.
ответ: 50 км/час начальная скорость.
Проверка: 300/50 - [(300-1,5*50)/(50+25) -1,5] = 1,5