Question

На планете Маодао живет 14 жителей. Они объединены в различные партии. По закону, партия должна состоять не менее чем из 3 жителей, и две разные партии не могут состоять из одних и тех же членов. Кроме того, каждый житель может быть членом не более 2 партий. Какое наибольшее число партий может быть на планете Маодао?

Answer 1

Отвечал уже, 9 партий. Вот их составы:
(1,2,3); (1,2,4); (3,4,5); (5,6,7); (6,7,8); (8,9,10); (9,10,11);
(10,11,12); (12,13,14)
Или так:
(1,2,3); (1,4,5); (2,4,6); (3,5,6); (7,8,9); (7,10,11); (8,12,13);
(9,10,12); (11,13,14)

Answer 2

Каждый житель острова может состоять в 2-ух партиях. значит общее число членов во всех партиях 14*2=28.  В  каждой партии по 3 члена.    28:3= 9  И один житель острова состоит только в одной партии. Ответ 9

Answer 3

Для решения задачи воспользуемся методом математической индукции.

База индукции: Если на планете Маодао всего 3 жителя, то они могут быть объединены только в одну партию.

Шаг индукции: Предположим, что на планете Маодао живут $n$ жителей, и мы уже знаем, что наибольшее число партий, которое может быть на планете Маодао равно $P(n)$. Рассмотрим случай, когда на планете появляется еще один житель. Этот житель может быть добавлен в уже существующую партию (в которой уже есть не менее 3 жителей), либо он может создать свою собственную партию. При этом новая партия не может включать в себя жителей, которые уже состоят в другой партии, а также она должна состоять не менее чем из 3 членов.

Получаем формулу: $P(n+1) = P(n) + k$, где $k$ – количество новых партий, созданных при добавлении нового жителя. Так как новые партии могут быть созданы только из незанятых жителей, то $k$ не может превышать количество свободных жителей. Количество свободных жителей можно определить как $S(n) = n - 2P(n)$ (так как каждый житель может быть членом не более 2 партий, то число свободных жителей равно разности между общим числом жителей и числом занятых мест в партиях). Таким образом, получаем следующее неравенство:

$k \leq \left\lfloor \frac{S(n)}{3} \right\rfloor$

Заметим также, что $P(n)$ максимально, когда все партии имеют по 3 члена. Тогда $P(n) = \left\lfloor \frac{n}{3} \right\rfloor$.

Таким образом, получаем формулу:

$P(n+1) = \left\lfloor \frac{n}{3} \right\rfloor + \left\lfloor \frac{S(n)}{3} \right\rfloor$

При $n=14$, мы имеем $S(n) = 14 - 2P(14) = 14 - 2\cdot 4 = 6$. Поэтому:

$P(15) = \left\lfloor \frac{14}{3} \right\rfloor + \left\lfloor \frac{6}{3} \right\rfloor = 4 + 2 = 6$

Таким образом, на планете Маодао может быть не более