Страниц: 1 [2] 3
  Печать  
Автор Тема: Теннис  (Прочитано 9310 раз)
0 Пользователей и 1 Гость смотрят эту тему.

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

Сообщений: 1079

СПАСИБО
-вы поблагодарили: 128
-вас поблагодарили: 1145



Просмотр профиля
Ответ #15 : Июль 12, 2013, 01:13:13 �

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

Сообщений: 1079

СПАСИБО
-вы поблагодарили: 128
-вас поблагодарили: 1145



Просмотр профиля
Ответ #16 : Июль 12, 2013, 01:14:58 �


[/quote]
Случай 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 ничьих, а у второй и пятой — не менее одной. Этим количеством «лимит на ничьи» уже исчерпан, так что у последней и третьей команд — ровно две ничьи, у второй и пятой — ровно одна, а у первой и четвертой команд ничьих нет. Если бы матч третьей и последней команды был результативным, то каждая из этих команд должна была бы играть вничью со второй и с пятой, но тогда у тех команд было бы по две ничьи, что невозможно. Значит, третья с шестой командами должны были сыграть вничью.
Артем, вы бы затерли свой пост, а то совсем странно получается, взяли по гуглу ответ к другой задаче, нам предлагаете ее условие восстановить?
Записан
Питер Пен
Свой человек
***
Offline Offline

Сообщений: 335

СПАСИБО
-вы поблагодарили: 92
-вас поблагодарили: 117


Просмотр профиля
Ответ #17 : Июль 12, 2013, 01:17:38 �

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

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

Сообщений: 335

СПАСИБО
-вы поблагодарили: 92
-вас поблагодарили: 117


Просмотр профиля
Ответ #18 : Июль 12, 2013, 01:18:39 �

Да это Спам, а не Артем.
Записан
Питер Пен
Свой человек
***
Offline Offline

Сообщений: 335

СПАСИБО
-вы поблагодарили: 92
-вас поблагодарили: 117


Просмотр профиля
Ответ #19 : Июль 12, 2013, 01:28:02 �

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

Сообщений: 1079

СПАСИБО
-вы поблагодарили: 128
-вас поблагодарили: 1145



Просмотр профиля
Ответ #20 : Июль 12, 2013, 01:33:27 �

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

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #21 : Июль 12, 2013, 02:41:31 �

Eсли же передавать только победы...
И каким тогда должно быть доказательство для n игроков?
Вот с этим у меня и затык, частный случай понятен, а общий как-то не догоняю
Чтож, давайте попробуем.
1. Итак, у редакции есть итоговая таблица по которой можно понять, сколько побед у первого места, сколько у второго и т.д.
2. У журналиста - вся инфа, но он хочет её как-то сжать, зная, чем располагает редакция.
3. Естественно, редакция умная и догадается об алгоритме сжатия Smiley
4. Теперь - сама стратегия.
4.1 Сначала журналист перечислит все победы последнего игрока (назовём его - Вася)  в порядке снизу вверх. Побед будет немного, раз он последний. Остальные - будут поражения и их редакция сразу пометит. Назовём это число побед - Х.
4.2 Затем перейдём предпоследнему игроку. Надо учесть, что если он выиграл у последнего, эта победа уже будет фигурировать и для него потребуется перечислить на одну победу меньше. И так далее.
Это - в целом стратегия. Обратите внимание, что у меня таблица получается задом наперёд.
Если же передавать не победы, а поражения, то таблица бы была бы в привычном порядке.

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

Эти пользователи сказали вам СПАСИБО :

Питер Пен, Tim

За это сообщение 2 пользователи сказали спасибо!
Последнее редактирование: Июль 12, 2013, 02:44:43 от buka Записан
Питер Пен
Свой человек
***
Offline Offline

Сообщений: 335

СПАСИБО
-вы поблагодарили: 92
-вас поблагодарили: 117


Просмотр профиля
Ответ #22 : Июль 12, 2013, 03:49:43 �

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

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #23 : Июль 12, 2013, 04:23:52 �

Я думаю, что формула где-то такая: К*(log2K-1) (естественно - приведённая к целому)
Последнее редактирование: Июль 12, 2013, 04:29:11 от buka Записан
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #24 : Июль 12, 2013, 06:11:42 �

В принципе я получил несколько иную формулу, но могу её обосновать строго в общем виде.
Единственное, что пока не могу - доказать, что нельзя ещё меньше.
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...
Записан
Tim
Гений-Говорун
*
Offline Offline

Сообщений: 1079

СПАСИБО
-вы поблагодарили: 128
-вас поблагодарили: 1145



Просмотр профиля
Ответ #25 : Июль 12, 2013, 07:45:27 �

Buka, респект. Питер Пен, когда биекция с изоморфизмом будут ))))?
Последнее редактирование: Июль 12, 2013, 08:09:15 от Tim0512 Записан
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #26 : Июль 12, 2013, 11:34:26 �

Buka, респект. Питер Пен, когда биекция с изоморфизмом будут ))))?
Спасибо, конечно, но, увы, - позор мне Sad
Я не понял условие и решал не ту задачу. По попе
Формула должна быть log2(K!)
В сети я нашёл формулу К*log2K, но думаю, что моя - даёт лучшее приближение
К*log2K > log2(K!), поскольку К*log2K = log2(KK),
a KK >> K!
По формуле К*log2K  для 16 мы получаем не 45, а 64, а по моей - 44,25014047, т.е. 45
Соберусь мыслями и объясню почему
Записан
Tim
Гений-Говорун
*
Offline Offline

Сообщений: 1079

СПАСИБО
-вы поблагодарили: 128
-вас поблагодарили: 1145



Просмотр профиля
Ответ #27 : Июль 12, 2013, 11:44:07 �

Buka, респект. Питер Пен, когда биекция с изоморфизмом будут ))))?
Спасибо, конечно, но, увы, - позор мне Sad
Я не понял условие и решал не ту задачу. По попе
Формула должна быть log2(K!)
В сети я нашёл формулу К*log2K, но думаю, что моя - даёт лучшее приближение
К*log2K > log2(K!), поскольку К*log2K = log2(KK),
a KK >> K!
По формуле К*log2K  для 16 мы получаем не 45, а 64, а по моей - 44,25014047, т.е. 45
Соберусь мыслями и объясню почему
ждем-с )))
Записан
Питер Пен
Свой человек
***
Offline Offline

Сообщений: 335

СПАСИБО
-вы поблагодарили: 92
-вас поблагодарили: 117


Просмотр профиля
Ответ #28 : Июль 12, 2013, 12:40:28 �

Buka, респект. Питер Пен, когда биекция с изоморфизмом будут ))))?
Спасибо, конечно, но, увы, - позор мне Sad
Я не понял условие и решал не ту задачу. По попе
Формула должна быть log2(K!)
В сети я нашёл формулу К*log2K, но думаю, что моя - даёт лучшее приближение
К*log2K > log2(K!), поскольку К*log2K = log2(KK),
a KK >> K!
По формуле К*log2K  для 16 мы получаем не 45, а 64, а по моей - 44,25014047, т.е. 45
Соберусь мыслями и объясню почему
Да Buka, действительно, та задача, на которую я выше ссылался, как раз и содержит эту формулу. И вот как она сформулирована:
«После кругового теннисного турнира на n человек в редакции оказалась полная таблица турнира, но без имён игроков, и (отдельно) полный список игроков. Журналист хочет передать в редакцию результаты нескольких игр так, чтобы по ним было возможно восстановить, кто выиграл в каждой паре. Докажите, что ему для этого хватит n log_2(n) матчей».
Хотя, с учетом того, что в предлагаемой здесь задаче требуется доказать, что редакции хватит для восстановления таблицы и 45 результатов игр, то доказывать возможность восстановления турнирной таблицы по меньшему числу результатов, уже не нужно.
Последнее редактирование: Июль 12, 2013, 12:44:10 от Питер Пен Записан
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #29 : Июль 12, 2013, 13:56:33 �

Начнём с того, где я перепутал.
Я невнимательно прочёл условие и решил, что редакции известно только упорядоченный перечень набранных очков и отдельно - неупорядоченный список участников, а сама таблица - неизвестна - её надо создать и заодно упорядочить под неё список участников.
Зато я считал, что журналист может играть на порядке перечисления этих рез-тов.
Короче, я решал другую задачу Smiley
Замечу, что она сама по себе - тоже интересна Smiley - но уже не в этой теме  Laugh
----------------------------------
Теперь - о нашей задаче.
Редакция имеет полную таблицу (в каждой клетке - 1 или 0 - победа или поражение) и неупорядоченный список игроков. Результат скольких игр ей требуется заполучить из некоторой базы данных, чтобы гарантированно поставить игроков в соответствие с таблицей?
 Журналиста мы выбросим, чтоб он не соблазнял меня игрой на последовательности передачи рез-тов  Tongue
Подход к решению.
Неупорядоченный список из К можно переставить К! способами (число перестановок). Следовательно, каждая из К! перестановка может быть закодирована log2(K!) - битным числом, т.е. требуется log2(K!) бит. Любая игра даёт информацию в 1 бит относительно пары игроков.
То есть, требуется получить инфу о  log2(K!) играх (естественно, приведённое к целому).
Это - АБСОЛЮТНАЯ нижняя граница и очевидно в общем случае не может быть меньше в общем случае.
Это и даёт нашу формулу.
Но на этом всё изящество заканчивается и начинается проза рутины.
Короче - как закодировать и как раскодировать?
Ведь далеко не любые  log2(K!) из К*(К-1)/2 игр сойдут для этого...
Чтобы понять насколько это нетривиально, начнём с самых малых чисел (16 - это ОГРОМНОЕ число).
Продолжение - в следующем постинге. Мне надо бежать. Дико извиняюсь.
Последнее редактирование: Июль 12, 2013, 13:58:46 от buka Записан
Страниц: 1 [2] 3
  Печать  
 
Перейти в: