Question

компания некоторые пары людей дружат оказалось что среди каждых 100 человек в компании количество пар дружащих людей нечетно. Какое максималтное количество людей в компании​

Answer 1

Ответ:

197

Пошаговое объяснение:

Это мысли не просветлённого человека, поэтому на верность не претендую.

Представим 99 человек, которые дружат между собой (эх, мечты) в виде графа с 99 вершинами, соответственно ребёр в таком графе будет  4851 рёбер (высчитываем по формуле n*(n-1)\2 где n - количество вершин), т.е. нечетное количество (можно было полностью и не считать, только последнею цифру узнать). Спросите, почему мы сразу не взяли 100 друзей? Ну, во-первых их бы было четное количество пар, а во-вторых нам максимум вообще-то надо найти, а это явно больше 100.
Далее, по лемме о хороводах (забейте, если не понимаете, там всё наглядно объяснено) соединяем 98 вершин. Почему не 99, не 100, а именно 98? Количество ребёр в таком графе будет равно количеству вершин только в случае, если мы возьмём максимально значение, в ином случая ребёр меньше на 1. => если мы возьмём 100 из этого графа , то будет четное кол-во пар, что нас не устраивает. А 99 не возьмём, потому что, если мы возьмём 98 человек (97 пар) из хоровода и 2 (1 пара) из другого графа, то будет четное количество пар.
А вот в случае, когда в "хороводе" 98 человек всё складывается (98 пар (т.к. макс. значение) + 1 пара -нечетная сумма). Если мы возьмём 198, 298 и т.д. ситуация будет такой же, как и 99.

Answer 2

Давайте предположим, что в компании есть N человек. Тогда количество пар дружащих людей будет равно N(N-1)/2, так как каждый человек может быть другом с каждым, кроме себя самого, и порядок пар не имеет значения.

Мы знаем, что количество пар дружащих людей нечетно, поэтому N(N-1)/2 должно быть нечетным числом. Это возможно только в том случае, если N и N-1 оба являются четными числами. Таким образом, N должно быть нечетным числом.

Максимальное нечетное число, которое может быть выражено в виде N(N-1)/2, - это N=9. Тогда количество пар дружащих людей будет равно 9*8/2 = 36, что является нечетным числом.

Таким образом, максимальное количество людей в компании - 9.