Мутная задача про 45 одноклассников

Попробуем представить как могли бы выполняться условия задачи. Приведу конкретный пример:

N1, N2, N3, N4, N5 - мощность данных подмножеств.

Тогда расчет будет таким

X = 45*44/2  - [ N1*(N1-1)/2 + ... + N5*(N5-1)/2]

Максимизировать Х можно, минимизируя сумму в квадратных скобках.

Рассчитаем пример при разбиении 45 = 10+10+10+10+5

Получим Х = 800

Рассчитаем еще один пример, при условии разбиения 45 = 2+2+...+2+1 (22 пары незнакомых между собой людей, который зато знают всех остальных).

Получим Х = 946

Еще расчет при разбиении 45 = 3+3+...3 (15 троек)

Получим Х = 945

При укрупнении подмножеств Х падает, но строго это утверждение я не исследовал. Только на примерах.

Таким образом, найденный тобой ответ, что якобы 870 - это максимальное количество знакомств, не является максимальным. Скорее всего эту цифру получили на каком-либо конкретном примере...

Последнее изменение: Вторник, 28 июня 2022, 13:21