Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.
Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.Рассмотрим дополнение графа знакомств в полном графе -- это удобно, так как рёбер мало. Степень каждой вершины не больше 2, и в графе нет треугольников. Рассмотрим связную компоненту. Это или линейный граф (возможно, из одной вершины), или цикл. Будем в каждой компоненте выбирать подмножество вершин, в котором нет соединений. Если мы в сумме наберём 12 человек, то задача решена: представители разных компонент между собой знакомы.
Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.Рассмотрим дополнение графа знакомств в полном графе -- это удобно, так как рёбер мало. Степень каждой вершины не больше 2, и в графе нет треугольников. Рассмотрим связную компоненту. Это или линейный граф (возможно, из одной вершины), или цикл. Будем в каждой компоненте выбирать подмножество вершин, в котором нет соединений. Если мы в сумме наберём 12 человек, то задача решена: представители разных компонент между собой знакомы.Для линейного графа раскрасим вершины через одну, и возьмём тот цвет, представителей которого не меньше. Это даст как минимум половину. Если цикл имеет чётную длину, то мы также выбираем половину -- через одного. Наконец, пусть цикл имеет длину 2k+1, где k>=2. Тогда можно взять k человек с номерами 2, 4, ... , 2k. Доля числа взятых равна k/(2k+1)>=2/5. Отсюда следует, что мы можем взять как минимум 2/5 от общего числа, а это и есть 12. Они попарно знакомы.
Предложу решение, но мне кажется, есть что-то попроще, но не могу найти.
Рассуждаем так. Допустим до встречи 1 шёл со скоростью х км/ч, тогда второй шёл со скоростью (10-х) км/ч ( потому что км за 5 часов, значит их общая скорость была 10 км/ч)
За 5 часов х км, ему осталось идти (50-5х) км, тогда второму осталось идти 50 -(50-5х) = 5х (км) (т.к. после встречи им всё равно в сумме надо 50 км пройти.
их новые скорости: у первого:( х-1) (км/ч), у второго 1+(10-х) = 11-х (км/ч)
Теперь делим оставшиеся расстояния на скорости , получим время и зная, что первый пришёл раньше на 2 ч. составляем уравнение:
5х/(11-х) - (50-5х)/(х-1) = 2
5х/(11-х) - (50-5х)/ (х-1) - 2 = 0
приводим к общему знаменателю это (11-х)(х-1), и я буду писать только числитель:
5х(х-1) -(50-5х)(11-х) - 2(11-х)(х-1) = 0 ( т.к. дробь равно 0, если числитель равен 0, а знаменатель не равен 0)
5х^2-5x-550+55x+50x-5x^2-22x+22+2x^2-2x = 0
2x^2+76x-528 = 0
x^2+38x -264 = 0
D=2500
x=(-38-50)/2 -видно, что отриц. число, нам не подходит
или х= (-38+50)/2 = 6 (км/ч)
ответ: 6 км/ч
