Александр Кремень
Гость
|
|
� : Июль 09, 2013, 15:52:25 � |
|
«После кругового теннисного турнира на 16 человек в редакции оказалась полная таблица турнира, но без имён игроков, и отдельно — полный список игроков. Журналист хочет передать в редакцию результаты нескольких игр так, чтобы по ним было возможно восстановить, кто выиграл в каждой паре. Докажите, что ему для этого хватит 45 результатов.
|
|
|
Записан
|
|
|
|
Питер Пен
Свой человек
Offline
Сообщений: 335
СПАСИБО
-вы поблагодарили: 92
-вас поблагодарили: 117
|
|
� Ответ #1 : Июль 09, 2013, 15:54:23 � |
|
"Мамой клянусь!"
|
|
|
Записан
|
|
|
|
artem123
Давненько
Offline
Сообщений: 62
СПАСИБО
-вы поблагодарили: 17
-вас поблагодарили: 6
|
|
� Ответ #2 : Июль 09, 2013, 17:16:55 � |
|
Случай 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 ничьих, а у второй и пятой — не менее одной. Этим количеством «лимит на ничьи» уже исчерпан, так что у последней и третьей команд — ровно две ничьи, у второй и пятой — ровно одна, а у первой и четвертой команд ничьих нет. Если бы матч третьей и последней команды был результативным, то каждая из этих команд должна была бы играть вничью со второй и с пятой, но тогда у тех команд было бы по две ничьи, что невозможно. Значит, третья с шестой командами должны были сыграть вничью.
|
|
|
Записан
|
|
|
|
Александр Кремень
Гость
|
|
� Ответ #3 : Июль 09, 2013, 18:26:14 � |
|
Это не та задача. Я про теннис а не про футбол загадываю!!!
|
|
|
Записан
|
|
|
|
Tim
Гений-Говорун
Offline
Сообщений: 1079
СПАСИБО
-вы поблагодарили: 128
-вас поблагодарили: 1145
|
|
� Ответ #4 : Июль 09, 2013, 19:27:39 � |
|
Случай 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 ничьих, а у второй и пятой — не менее одной. Этим количеством «лимит на ничьи» уже исчерпан, так что у последней и третьей команд — ровно две ничьи, у второй и пятой — ровно одна, а у первой и четвертой команд ничьих нет. Если бы матч третьей и последней команды был результативным, то каждая из этих команд должна была бы играть вничью со второй и с пятой, но тогда у тех команд было бы по две ничьи, что невозможно. Значит, третья с шестой командами должны были сыграть вничью.
Мда, ничья в теннисе, круто
|
|
|
Записан
|
|
|
|
Tim
Гений-Говорун
Offline
Сообщений: 1079
СПАСИБО
-вы поблагодарили: 128
-вас поблагодарили: 1145
|
|
� Ответ #5 : Июль 10, 2013, 00:08:18 � |
|
Мда, не для моих познаний задача, похоже графы и логорифмы
|
|
|
Записан
|
|
|
|
Tim
Гений-Говорун
Offline
Сообщений: 1079
СПАСИБО
-вы поблагодарили: 128
-вас поблагодарили: 1145
|
|
� Ответ #6 : Июль 12, 2013, 00:09:46 � |
|
Ну что нет никого кто в графах силен?
|
|
|
Записан
|
|
|
|
buka
Гений
Offline
Сообщений: 960
СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120
|
|
� Ответ #7 : Июль 12, 2013, 00:39:13 � |
|
Чтобы вообще передать всю информацию - требуется передать рез-ты 120 встреч: 15+14+13+...+2+1 (для первых 15 из 16 участников). Eсли же передавать только победы - то в 2 раза меньше, т.е. 60 встреч. Если нам известны очки, то у каждого из 15 участников можно срезать ещё по одной игре - итого, 45
|
|
|
Записан
|
|
|
|
Tim
Гений-Говорун
Offline
Сообщений: 1079
СПАСИБО
-вы поблагодарили: 128
-вас поблагодарили: 1145
|
|
� Ответ #8 : Июль 12, 2013, 00:44:33 � |
|
Чтобы вообще передать всю информацию - требуется передать рез-ты 120 встреч: 15+14+13+...+2+1 (для первых 15 из 16 участников). Eсли же передавать только победы - то в 2 раза меньше, т.е. 60 встреч. Если нам известны очки, то у каждого из 15 участников можно срезать ещё по одной игре - итого, 45
Так-то на пальцах мне понятно, смущает отсутствие строгости доказательства
|
|
|
Записан
|
|
|
|
Питер Пен
Свой человек
Offline
Сообщений: 335
СПАСИБО
-вы поблагодарили: 92
-вас поблагодарили: 117
|
|
� Ответ #9 : Июль 12, 2013, 00:47:55 � |
|
Eсли же передавать только победы...
И каким тогда должно быть доказательство для n игроков?
|
|
|
Записан
|
|
|
|
Tim
Гений-Говорун
Offline
Сообщений: 1079
СПАСИБО
-вы поблагодарили: 128
-вас поблагодарили: 1145
|
|
� Ответ #10 : Июль 12, 2013, 00:54:39 � |
|
Eсли же передавать только победы...
И каким тогда должно быть доказательство для n игроков? Вот с этим у меня и затык, частный случай понятен, а общий как-то не догоняю
|
|
|
Записан
|
|
|
|
Питер Пен
Свой человек
Offline
Сообщений: 335
СПАСИБО
-вы поблагодарили: 92
-вас поблагодарили: 117
|
|
� Ответ #11 : Июль 12, 2013, 01:00:30 � |
|
Eсли же передавать только победы...
И каким тогда должно быть доказательство для n игроков? Вот с этим у меня и затык, частный случай понятен, а общий как-то не догоняю Кодировка битов… направление ребер между игроками…биекция… изоморфизм графов… – ну нах...! Пусть Замат доказывает.
|
|
|
Записан
|
|
|
|
Tim
Гений-Говорун
Offline
Сообщений: 1079
СПАСИБО
-вы поблагодарили: 128
-вас поблагодарили: 1145
|
|
� Ответ #12 : Июль 12, 2013, 01:03:50 � |
|
Eсли же передавать только победы...
И каким тогда должно быть доказательство для n игроков? Вот с этим у меня и затык, частный случай понятен, а общий как-то не догоняю Кодировка битов… направление ребер между игроками…биекция… изоморфизм графов… – ну нах...! Пусть Замат доказывает. Во ты загрузил на ночь глядя )))) кроме слов игроки и нах... ни одного знакомого ))), а если серьезно вот интересно, на пальцах частный случай легко решается, а как общий вид решить непонятно нефига
|
|
|
Записан
|
|
|
|
Питер Пен
Свой человек
Offline
Сообщений: 335
СПАСИБО
-вы поблагодарили: 92
-вас поблагодарили: 117
|
|
� Ответ #13 : Июль 12, 2013, 01:09:12 � |
|
Eсли же передавать только победы...
И каким тогда должно быть доказательство для n игроков? Вот с этим у меня и затык, частный случай понятен, а общий как-то не догоняю Кодировка битов… направление ребер между игроками…биекция… изоморфизм графов… – ну нах...! Пусть Замат доказывает. Во ты загрузил на ночь глядя )))) кроме слов игроки и нах... ни одного знакомого ))), а если серьезно вот интересно, на пальцах частный случай легко решается, а как общий вид решить непонятно нефига Замат тебе еще должен быть известен... Я себя ощущаю как ворона из анекдота - время 3 часа ночи, а я сижу еще на работе и долблю по клавишам... Пиз..ц я еба...уый!!!!
|
|
� Последнее редактирование: Июль 12, 2013, 01:11:20 от Питер Пен �
|
Записан
|
|
|
|
Tim
Гений-Говорун
Offline
Сообщений: 1079
СПАСИБО
-вы поблагодарили: 128
-вас поблагодарили: 1145
|
|
� Ответ #14 : Июль 12, 2013, 01:10:41 � |
|
Eсли же передавать только победы...
И каким тогда должно быть доказательство для n игроков? Вот с этим у меня и затык, частный случай понятен, а общий как-то не догоняю Кодировка битов… направление ребер между игроками…биекция… изоморфизм графов… – ну нах...! Пусть Замат доказывает. Во ты загрузил на ночь глядя )))) кроме слов игроки и нах... ни одного знакомого ))), а если серьезно вот интересно, на пальцах частный случай легко решается, а как общий вид решить непонятно нефига Замат тебе еще должен быть известен... Я себя ощущаю как ворона из анекдота - время 3 часа ночи, а я сижу еще на работе и долблю по клавишам... Еб....ый!!!! Moscow never sleeps ))))))
|
|
|
Записан
|
|
|
|
|