Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.
Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.Рассмотрим дополнение графа знакомств в полном графе -- это удобно, так как рёбер мало. Степень каждой вершины не больше 2, и в графе нет треугольников. Рассмотрим связную компоненту. Это или линейный граф (возможно, из одной вершины), или цикл. Будем в каждой компоненте выбирать подмножество вершин, в котором нет соединений. Если мы в сумме наберём 12 человек, то задача решена: представители разных компонент между собой знакомы.
Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.Рассмотрим дополнение графа знакомств в полном графе -- это удобно, так как рёбер мало. Степень каждой вершины не больше 2, и в графе нет треугольников. Рассмотрим связную компоненту. Это или линейный граф (возможно, из одной вершины), или цикл. Будем в каждой компоненте выбирать подмножество вершин, в котором нет соединений. Если мы в сумме наберём 12 человек, то задача решена: представители разных компонент между собой знакомы.Для линейного графа раскрасим вершины через одну, и возьмём тот цвет, представителей которого не меньше. Это даст как минимум половину. Если цикл имеет чётную длину, то мы также выбираем половину -- через одного. Наконец, пусть цикл имеет длину 2k+1, где k>=2. Тогда можно взять k человек с номерами 2, 4, ... , 2k. Доля числа взятых равна k/(2k+1)>=2/5. Отсюда следует, что мы можем взять как минимум 2/5 от общего числа, а это и есть 12. Они попарно знакомы.
а) N = 8; б) S(0-8) = 360
Пошаговое объяснение:
45 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9
а) Это набор от 0:0 до 8:8.
б) Сумма всех костей от 0:0 до 6:6 S(0-6) = 168, это давно известно.
Остальные кости дают сумму:
S(7-8) = (0+7) + (1+7) + (2+7) + (3+7) + (4+7) + (5+7) + (6+7) + (7+7) +
+ (0+8) + (1+8) + (2+8) + (3+8) + (4+8) + (5+8) + (6+8) + (7+8) + (8+8) =
= 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 =
= (7+14) + (8+13) + (9+12) + (10+11) + (8+16) + (9+15) + (10+14) + (11+13) + 12 =
= 21*4 + 24*4 + 12 = 84 + 96 + 12 = 192
Общая сумма костей от 0:0 до 8:8 составляет:
S(0-8) = S(0-6) + S(7-8) = 168 + 192 = 360
VМиши=100/15=6,7м/с
VМиши больше на 6,7-6=0,7 м/с