Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.
Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.Рассмотрим дополнение графа знакомств в полном графе -- это удобно, так как рёбер мало. Степень каждой вершины не больше 2, и в графе нет треугольников. Рассмотрим связную компоненту. Это или линейный граф (возможно, из одной вершины), или цикл. Будем в каждой компоненте выбирать подмножество вершин, в котором нет соединений. Если мы в сумме наберём 12 человек, то задача решена: представители разных компонент между собой знакомы.
Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.Рассмотрим дополнение графа знакомств в полном графе -- это удобно, так как рёбер мало. Степень каждой вершины не больше 2, и в графе нет треугольников. Рассмотрим связную компоненту. Это или линейный граф (возможно, из одной вершины), или цикл. Будем в каждой компоненте выбирать подмножество вершин, в котором нет соединений. Если мы в сумме наберём 12 человек, то задача решена: представители разных компонент между собой знакомы.Для линейного графа раскрасим вершины через одну, и возьмём тот цвет, представителей которого не меньше. Это даст как минимум половину. Если цикл имеет чётную длину, то мы также выбираем половину -- через одного. Наконец, пусть цикл имеет длину 2k+1, где k>=2. Тогда можно взять k человек с номерами 2, 4, ... , 2k. Доля числа взятых равна k/(2k+1)>=2/5. Отсюда следует, что мы можем взять как минимум 2/5 от общего числа, а это и есть 12. Они попарно знакомы.
Пусть х - цена яблок, у - цена груш, тогда
х - 0,4х = 0,6х - цена яблок после снижения на 40%
у + 0,5у = 1,5у - цена груш после повышения на 50%
Составим систему уравнений по условию задачи:
{5х + 3у = 60
{5 · 0,6х + 3 · 1,5у = 63
- - - - - - - - -
{5х + 3у = 60
{3х + 4,5у = 63
- - - - - - - - -
Разделим обе части второго уравнения системы на 3
х + 1,5у = 21
х = 21 - 1,5у
Подставим значение х в первое уравнение системы
5 · (21 - 1,5у) + 3у = 60
105 - 7,5у + 3у = 60
105 - 60 = 7,5у - 3у
45 = 4,5у
у = 45 : 4,5
у = 10 (грн.) - первоначальная цена груш
х = 21 - 1,5 · 10
х = 21 - 15
х = 6 (грн.) - первоначальная цена яблок
10 + 6 = 16 (грн.) - сумма грн.
Вiдповiдь: 16 грн.
взял