компания некоторые пары людей дружат оказалось что среди каждых 100 человек в компании количество пар дружащих людей нечетно. Какое максималтное количество людей в компании
Это мысли не просветлённого человека, поэтому на верность не претендую.
Представим 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.
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.