Теннис

[buka]

Продолжение.
1. Начнём с простейшего - турнир 2-х. Требуется один результат по любому.
2. Турнир из 3-х. Будем считать, что у всех - разное кол-во очков, т.е. 0,1,2 (случай когда одинаковое рассм. отдельно):
    3! = 6, log₂6 > 2, т.е. требуется 3 результата (т.е. все), как ни крути. Тоже никакой экономии.
2а. Если у всех одинаковое число очков, то требуется 1 рез-т, любой и по нему восстановятся остальные. Это частный случай, конечно, но можно догадаться, что максимум рез-тов требуется, когда у всех - разные очки - от 0 до К-1.
3. Турнир 4-х. Все рез-ты разные - 0,1,2,3. Всего таблица (треугольная) будет иметь (К-1)*К/2 = 6 клеток.
4!=24>4, т.е. требуется 5 бит/рез-тов из 6. Экономия - всего 1 бит. Итак, какой рез-т можно не спрашивать?
Пусть участники - А,Б,В,Г
Я бы запросил: А-Б, А-В, Б-В, Б-Г, В-Г, оставив за бортом рез-т А-Г.
Если мы получили 00000, то порядок ГВБА и рез-т А-Г - 0 (А проиграл). Иначе можно убедится, что не все набрали разные очки.
Если же рез-т 11111, то порядок АБВГ и А выиграл у Г.
Аналогично можно высказаться о каждой комбинации 5 бит. Кстати, не все 32 комбинации релевантны при условии, что у всех разное кол-во очков.
Перебирать все 32 комбинации, выделять из них 24 и определять рез-т А-Г я не буду - муторно
Как видите, уже для 4-х участников выбрать 5 из 6 рез-тов - это работа более чем нудная.
Например, запросить рез-ты А-Б,А-В,А-Г, Б-В,Б-Г и опустить - В-Г было бы неверным (если у всех разное кол-во очков), поскольку результат В-Г - существенен.
Другими словами уже для 4-х участников редакции нужен комп и программа, чтоб отбросила 1 из 6 рез-тов.
А я описал лишь случай, когда все набрали разное кол-во очков...
Для 5: всего - 5*4/2=10, 5!=120>64, т.е. нужно 7 рез-тов из 10.
Для 6: 6*5/2=15, 6!=720>512-> 9.
Ну, для 16 - 16*15/2=120, 16!>2⁴⁴ -> 45.
Но чтоб выбрать 45 из 120 я думаю требуется неслабая программа и нехилый комп...

[Tim]

А вроде просто в теннис поиграли ))))