Олимпиада математика решение В волейбольном турнире участвовали 23
команды. Назовем тройку команд (А, В, С)
непонятной, если команда А выиграла у
команды В, команда В-у команды С, а
команда С-у команды А. Найдите
наибольшее количество непонятных троек.

Предыдущий
вопрос Следующий
вопрос

Чтобы найти наибольшее количество непонятных троек, подсчитаем сначала количество возможных троек команд.

Для каждой команды может быть 22 других команд, с которыми она может сыграть. Таким образом, общее количество троек команд равно 23 22 21 = 10626.

Теперь найдем количество "понятных" троек. Для этого каждая тройка должна состоять из трех команд, выигрыш в которых будет транзитивным. Это означает, что если команда А выиграла у команды В, а команда В у команды С, то команда А также выиграла бы у команды С. Таким образом, "понятные" тройки не могут быть непонятными.

"Понятные" тройки могут состоять только из команд, у которых есть общая цепочка побед (A > B, B > C => A > C). Предположим, что одна из команд обыграла все остальные. Это означает, что она образует цепочку побед со всеми остальными командами - 22 "понятные" тройки. Наибольшее количество подобных цепочек - 23 (по количеству команд).

Таким образом, наибольшее количество "понятных" троек равно 22 * 23 = 506.

Теперь найдем количество непонятных троек как разницу между общим количеством троек и "понятными" тройками: 10626 - 506 = 10120.

Итак, наибольшее количество непонятных троек равно 10120.