Форум умных людей

«После кругового теннисного турнира на 16 человек в редакции оказалась полная таблица турнира, но без имён игроков, и отдельно — полный список игроков. Журналист хочет передать в редакцию результаты нескольких игр так, чтобы по ним было возможно восстановить, кто выиграл в каждой паре. Докажите, что ему для этого хватит 45 результатов.

"Мамой клянусь!"

Случай 1. k = 0. Всего командами набрано 30 очков, то есть все игры закончились вничью. Но тогда все команды должны были набрать одно и то же число очков. Противоречие.

Случай 2. k = 1. Всего командами набрано 36 очков. Если из 15 игр n закончились вничью, то имеем уравнение 2n + 3·(15 – n) = 36, откуда 45 – n = 36, n = 9. Три последних команды сыграли 12 игр — 3 между собой и 9 игр против остальных команд. Поскольку игр, которые не закончились вничью, во всём турнире было 6, то не менее 6 из этих 12 игр закончились вничью. Значит, не менее 3 из этих ничьих были в матчах против первой тройки команд. Но так как они набрали в сумме всего 9 очков, то в трех играх между собой ими было набрано не более 6 очков! Это означает, что все их игры между собой должны были закончиться вничью, что невозможно, так как последняя команда набрала всего одно очко, в то время как две ничьи против 4-й и 5-й команд принесли бы ей минимум 2 очка. Следовательно, и этот случай приводит к противоречию.

(Это, разумеется, не единственное возможное рассуждение, приводящее к противоречию. Вот другой способ рассуждений.
При девяти ничьих и шести результативных играх получается следующее: команда-победительница сыграла не менее трех результативных игр, а команда с 1 очком — ровно 4. Тогда все остальные игры между командами завершились вничью. В частности, пятая (предпоследняя) команда сыграла вничью со второй, третьей и четвертой. Но так как она еще и не проиграла шестой команде, то у нее не может оказаться всего 3 очка. Снова противоречие.)

Случай 3. k = 2. Теперь 6k + 30 = 42, поэтому, рассуждая аналогично предыдущему случаю, получаем, что вничью сыграны ровно 3 игры из 15. Как могли эти 3 ничьих распределиться между командами, набравшими 2, 4, 6, 8, 10 и 12 очков? Поскольку число очков в результативных (победных или проигранных) встречах кратно трем, то у последней и у третьей команд было не менее 2 ничьих, а у второй и пятой — не менее одной. Этим количеством «лимит на ничьи» уже исчерпан, так что у последней и третьей команд — ровно две ничьи, у второй и пятой — ровно одна, а у первой и четвертой команд ничьих нет. Если бы матч третьей и последней команды был результативным, то каждая из этих команд должна была бы играть вничью со второй и с пятой, но тогда у тех команд было бы по две ничьи, что невозможно. Значит, третья с шестой командами должны были сыграть вничью.

Это не та задача. Я про теннис а не про футбол загадываю!!!

Мда, ничья в теннисе, круто

Мда, не для моих познаний задача, похоже графы и логорифмы

Ну что нет никого кто в графах силен?

Чтобы вообще передать всю информацию - требуется передать рез-ты 120 встреч:
15+14+13+...+2+1 (для первых 15 из 16 участников). Eсли же передавать только победы - то в 2 раза меньше, т.е. 60 встреч.
Если нам известны очки, то у каждого из 15 участников можно срезать ещё по одной игре - итого, 45

Так-то на пальцах мне понятно, смущает отсутствие строгости доказательства

И каким тогда должно быть доказательство для n игроков?

Вот с этим у меня и затык, частный случай понятен, а общий как-то не догоняю

Кодировка битов… направление ребер между игроками…биекция… изоморфизм графов… – ну нах...!
Пусть Замат доказывает.

Во ты загрузил на ночь глядя )))) кроме слов игроки и нах... ни одного знакомого ))), а если серьезно вот интересно, на пальцах частный случай легко решается, а как общий вид решить непонятно нефига

Замат тебе еще должен быть известен...
Я себя ощущаю как ворона из анекдота - время 3 часа ночи, а я сижу еще на работе и долблю по клавишам... Пиз..ц я еба...уый!!!!

Moscow never sleeps ))))))

Кстати, подумал еще по задаче. Нефига нельзя откидывать результат первого игрока с последним. По спортивным правилам при равенстве очков более высокое место определяют по результатам личных встреч, т.е. надо 45+1

[/quote] Артем, вы бы затерли свой пост, а то совсем странно получается, взяли по гуглу ответ к другой задаче, нам предлагаете ее условие восстановить?

Вот пусть она и не спит пока я сплю.

Тут вряд ли стоит это учитывать (я про личные встречи). Да и вообще мне это решение не нравится, т.к. когда-то я уже писал о доказательствах.

Да это Спам, а не Артем.

И потом в задаче сказано о передаче РЕЗУЛЬТАТОВ ИГР, т.е. передача "кодируемой" информации должна быть о том, кто у кого выиграл.

завтра попробую объяснить, спать пора ))

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

В задаче из кубка памяти Колмогорова как раз и предлагалось доказать такой расчет в отношении n участников - вот тут уже и не обошлось без графов!

Я думаю, что формула где-то такая: К*(log₂K-1) (естественно - приведённая к целому)

В принципе я получил несколько иную формулу, но могу её обосновать строго в общем виде.
Единственное, что пока не могу - доказать, что нельзя ещё меньше.
1. Итак, у нас К игроков, каждый играет с каждым, т.е. К-1 встреча для каждого (таблица КхК)
2. У последнего (Васи) число побед Х_к < (К-1)/2.
3. Перечислив эти Х_к <  (К-1)/2 мы покончили с Васей - о нём всё известно и мы можем построить таблицу (К-1)х(К-1) и ранжировать её. Порядок мест может измениться, но консистентно - и у журналиста и у редакции.
4. Для таблицы (К-1)х(К-1) Х_к-1 <  (К-2)/2 и т.д.
5. Когда остаются 2 игрока, то вообще инфа не нужна известно кто победил кого. Но нужна фамилия. Поэтому будем считать ещё один результат.
Итого имеем для турнира из К требуется не больше М данных, где М < [(K-1)/2]+[(K-2)/2]+...+[4/2]+[3/2]+1,
где [N] - целая часть  N. То есть у половины слагаемых надо ещё убрать по единице.
Это даст: (К-1 + K-2 +...+4+3)/2 + 1 - K/2
Для К=16 получается где-то 50...

Buka, респект. Питер Пен, когда биекция с изоморфизмом будут ))))?

Спасибо, конечно, но, увы, - позор мне :(
Я не понял условие и решал не ту задачу. :ass:
Формула должна быть log₂(K!)
В сети я нашёл формулу К*log₂K, но думаю, что моя - даёт лучшее приближение
К*log₂K > log₂(K!), поскольку К*log₂K = log₂(K^K),
a K^K >> K!
По формуле К*log₂K  для 16 мы получаем не 45, а 64, а по моей - 44,25014047, т.е. 45
Соберусь мыслями и объясню почему

ждем-с )))

Да Buka, действительно, та задача, на которую я выше ссылался, как раз и содержит эту формулу. И вот как она сформулирована:
«После кругового теннисного турнира на n человек в редакции оказалась полная таблица турнира, но без имён игроков, и (отдельно) полный список игроков. Журналист хочет передать в редакцию результаты нескольких игр так, чтобы по ним было возможно восстановить, кто выиграл в каждой паре. Докажите, что ему для этого хватит n log_2(n) матчей».
Хотя, с учетом того, что в предлагаемой здесь задаче требуется доказать, что редакции хватит для восстановления таблицы и 45 результатов игр, то доказывать возможность восстановления турнирной таблицы по меньшему числу результатов, уже не нужно.

Начнём с того, где я перепутал.
Я невнимательно прочёл условие и решил, что редакции известно только упорядоченный перечень набранных очков и отдельно - неупорядоченный список участников, а сама таблица - неизвестна - её надо создать и заодно упорядочить под неё список участников.
Зато я считал, что журналист может играть на порядке перечисления этих рез-тов.
Короче, я решал другую задачу :)
Замечу, что она сама по себе - тоже интересна :) - но уже не в этой теме  :laugh:
----------------------------------
Теперь - о нашей задаче.
Редакция имеет полную таблицу (в каждой клетке - 1 или 0 - победа или поражение) и неупорядоченный список игроков. Результат скольких игр ей требуется заполучить из некоторой базы данных, чтобы гарантированно поставить игроков в соответствие с таблицей?
 Журналиста мы выбросим, чтоб он не соблазнял меня игрой на последовательности передачи рез-тов  :P
Подход к решению.
Неупорядоченный список из К можно переставить К! способами (число перестановок). Следовательно, каждая из К! перестановка может быть закодирована log₂(K!) - битным числом, т.е. требуется log₂(K!) бит. Любая игра даёт информацию в 1 бит относительно пары игроков.
То есть, требуется получить инфу о  log₂(K!) играх (естественно, приведённое к целому).
Это - АБСОЛЮТНАЯ нижняя граница и очевидно в общем случае не может быть меньше в общем случае.
Это и даёт нашу формулу.
Но на этом всё изящество заканчивается и начинается проза рутины.
Короче - как закодировать и как раскодировать?
Ведь далеко не любые  log₂(K!) из К*(К-1)/2 игр сойдут для этого...
Чтобы понять насколько это нетривиально, начнём с самых малых чисел (16 - это ОГРОМНОЕ число).
Продолжение - в следующем постинге. Мне надо бежать. Дико извиняюсь.

Продолжение.
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 я думаю требуется неслабая программа и нехилый комп...

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