Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.
Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.Рассмотрим дополнение графа знакомств в полном графе -- это удобно, так как рёбер мало. Степень каждой вершины не больше 2, и в графе нет треугольников. Рассмотрим связную компоненту. Это или линейный граф (возможно, из одной вершины), или цикл. Будем в каждой компоненте выбирать подмножество вершин, в котором нет соединений. Если мы в сумме наберём 12 человек, то задача решена: представители разных компонент между собой знакомы.
Из условия следует, что ни у кого нет троих не знакомых с ним, а также то, что нет тройки попарно незнакомых. В противном случае к ним добавляем каких-то двоих, и этих пятерых будет не рассадить.Рассмотрим дополнение графа знакомств в полном графе -- это удобно, так как рёбер мало. Степень каждой вершины не больше 2, и в графе нет треугольников. Рассмотрим связную компоненту. Это или линейный граф (возможно, из одной вершины), или цикл. Будем в каждой компоненте выбирать подмножество вершин, в котором нет соединений. Если мы в сумме наберём 12 человек, то задача решена: представители разных компонент между собой знакомы.Для линейного графа раскрасим вершины через одну, и возьмём тот цвет, представителей которого не меньше. Это даст как минимум половину. Если цикл имеет чётную длину, то мы также выбираем половину -- через одного. Наконец, пусть цикл имеет длину 2k+1, где k>=2. Тогда можно взять k человек с номерами 2, 4, ... , 2k. Доля числа взятых равна k/(2k+1)>=2/5. Отсюда следует, что мы можем взять как минимум 2/5 от общего числа, а это и есть 12. Они попарно знакомы.
2, 8, 16, 24, 66, 150 — делятся на 2, так как последняя цифра этих чисел четная;
3, 7, 19, 35, 77, 453 — не делятся на 2, так как последняя цифра этих чисел нечетная.
Признак делимости на 3Число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3.
Например:75 — делится на 3, так как 7+5=12, и число 12 делится на 3 (12:3=4);
471 — делится на 3, так как 4+7+1=12, и число 12 делится на 3 (12:3=4);
532 — не делится на 3, так как 5+3+2=10, а число 10 не делится на 3 (10:3=313).
Признак делимости на 4Число делится на 4 тогда и только тогда, когда две его последние цифры составляют число, которое делится на 4. Двузначное число делится на 4 тогда и только тогда, когда удвоенное число десятков, сложенное с числом единиц делится на 4.
Например:4576 — делится на 4, так как число 76 делится на 4 (7·2+6=20, 20:4=5);
9634 — не делится на 4, так как число 34 не делится на 4 (3·2+4=10, 10:4=212).
Признак делимости на 5Число делится на 5 тогда, когда последняя цифра делится на 5, т.е. если она 0 или 5.
Например:375, 5680, 233575 — делятся на 5, так как их последняя цифра равна 0 или 5;
9634, 452, 389753 — не делятся на 5, так как их последняя цифра не равна 0 или 5.
Признак делимости на 6Число делится на 6 тогда и только тогда, когда оно делится и на 2, и на 3, то есть если оно четное и сумма его цифр делится на 3.
Например:462 — делятся на 6, по признаку делимости на 2 оно делится на 2 (последняя цифра 2 делится на 2), по признаку делимости на 3 оно делится на 3 (сумма цифр числа делится на 3: 4+6+2=12, 12:3=4);
3456 — делятся на 6, по признаку делимости на 2 оно делится на 2 (последняя цифра 6 делится на 2), по признаку делимости на 3 оно делится на 3 (сумма цифр числа делится на 3: 3+4+5+6=18, 18:3=6);
24642 — делятся на 6, по признаку делимости на 2 оно делится на 2 (последняя цифра 2 делится на 2), по признаку делимости на 3 оно делится на 3 (сумма цифр числа делится на 3: 2+4+6+4+2=18, 18:3=6);
861 — не делятся на 6, так как по признаку делимости оно не делится на 2;
3458 — не делятся на 6, так как по признаку делимости оно не делится на 3;
34681 — не делятся на 6, так как по признаку делимости оно не делится на 2.
Признак делимости на 9Число делится на 9 тогда и только тогда, когда сумма его цифр делится на 9.
Например:468, 4788, 69759 — делятся на 9, так как сумма их цифр делится на девять (4+6+8=18, 4+7+8+8=27, 6+9+7+5+9=36);
861, 3458, 34681 — не делятся на 9, так как сумма их цифр не делится на девять (8+6+1=15, 3+4+5+8=20, 3+4+6+8+1=22).
Признак делимости на 10Число делится на 10 тогда и только тогда, когда оно оканчивается на нoль.
Например:460, 24000, 1245464570 — делятся на 10, так как последняя цифра этих чисел равна нулю;
234, 25048, 1230000003 — не делятся на 10, так как последняя цифра этих чисел не равна нулю.
Признак делимости на 11Число делится на 11 если сумма цифр стоящих на четных местах равна сумме цифр стоящих на нечетных местах или отличается от нее на число кратное 11.
Например:242 — делится на 11, так как сумма цифр на нечетных позициях S2n+1 = 2 + 2 = 4; сумма цифр на четных позициях S2n = 4 и S2n+1 = S2n.
319 — делится на 11, так как сумма цифр на нечетных позициях S2n+1 = 3 + 9 = 12; сумма цифр на четных позициях S2n = 1, а их разность S2n+1 - S2n = 11 - делится на 11.
919380 — делится на 11, так как сумма цифр на нечетных позициях S2n+1 = 9 + 9 + 8 = 26; сумма цифр на четных позициях S2n = 1 + 3 + 0 = 4, а их разность S2n+1 - S2n = 22 - делится на 11.
2838 — делится на 11, так как сумма цифр на нечетных позициях S2n+1 = 2 + 3 = 5; сумма цифр на четных позициях S2n = 8+ 8 = 16, а их разность S2n - S2n+1 = 11 - делится на 11.
244 — не делится на 11, так как сумма цифр на нечетных позициях S2n+1 = 2 + 4 = 6; сумма цифр на четных позициях S2n = 4 и S2n+1 - S2n = 2 - не делится на 11.
