Eсли же передавать только победы...
И каким тогда должно быть доказательство для n игроков? 1. Итак, у редакции есть итоговая таблица по которой можно понять, сколько побед у первого места, сколько у второго и т.д.
2. У журналиста - вся инфа, но он хочет её как-то сжать, зная, чем располагает редакция.
3. Естественно, редакция умная и догадается об алгоритме сжатия
4. Теперь - сама стратегия.
4.1 Сначала журналист перечислит все победы последнего игрока (назовём его - Вася) в порядке снизу вверх. Побед будет немного, раз он последний. Остальные - будут поражения и их редакция сразу пометит. Назовём это число побед - Х.
4.2 Затем перейдём предпоследнему игроку. Надо учесть, что если он выиграл у последнего, эта победа уже будет фигурировать и для него потребуется перечислить на одну победу меньше. И так далее.
Это - в целом стратегия. Обратите внимание, что у меня таблица получается задом наперёд.
Если же передавать не победы, а поражения, то таблица бы была бы в привычном порядке.
4.4. Давайте оценим максимальное Х. Это тогда, когда у всех примерно очков/побед поровну и фиг их знает, почему наш Вася - последний.
Итак, всего имеется 16*15/2 = 120 встреч, т.е. 120 побед т.е. 7.5 побед на брата. Т.е. для Васи - это 7 побед где-то. При этом 8 побед он как бы "отдаёт" бесплатно - их передавать не надо.
То есть из общего числа побед 8 можно вычесть.
Обратите внимание - мы заполнили не более половины строки, но это эквивалентно всей строке.
4.5 Перейдём к следующей строке (предпоследнему игроку). Её длина на один меньше (мы помним что таблица представляет собой треугольник и она у нас задом наперёд). Очевидно и для неё потребуется заполнить только где-то меньше половины - и то, в худшем случае)
Короче, для каждой строки требуется где-то К/2 -1, что и даёт 45... Первого игрока вообще перечислять не надо.
Конечно, это не претендует на строгость, но подход имхо вырисовался.
Записан