Давайте представим последовательность команд, в которых играл каждый игрок, как бинарную строку. Например: если игрок играл сначала в первой, потом во второй, потом снова в первой то можем записать его серию игр как 010 (0 -- играл в первой команде, 1 -- играл во второй команде). В каком случае два игрока сыграют в разных командах хотя бы один раз? Если их бинарные строки отличаются хотя бы на один бит (в одном числе).
У нас есть n игроков, мы хотим чтобы любая пара игроков сыграла хотя-бы один раз в разных командах, значит мы хотим, чтобы все n бинарных строки были различные.
Нам нужно минимальное кол-во игр, значит нам нужно понять, какой минимальной длины могут быть n строк так, чтобы они были разными. Чтобы найти эту длину, давайте посмотрим как соотносится максимальное кол-во строк и их длина. Если у нас длина 1, мы можем взять 2 различные бинарные строки, если длина 2, то 4, если длина k, то 2**k. Получается минимальное кол-во игр, это минимальное k, такое что 2**k >= n. Итого находим что нам нужно ceil(log n) игр.
Теперь, как нам распределить игроков по командам в эти ceil(log n) игр? Как один из вариантов, мы можем поделить их на группы по наличию i-го бита в двоичном представлении их номера (от 1 до n). Несложно доказать, что групп будет так же ceil(log n). Каждую игру поставим i-ю группу в первую команду, остальных во вторую. Это будет гарантировать то, что каждый сыграет с каждым, так как для каждого игрока не найдется такого, что все игры они находятся в одной команде. Это означало бы, что все их биты совпадают, значит совпадают номера.
