Страниц: [1] 2 3
  Печать  
Автор Тема: Теннис  (Прочитано 9311 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Александр Кремень
Гость
: Июль 09, 2013, 15:52:25 �

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

Сообщений: 335

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


Просмотр профиля
Ответ #1 : Июль 09, 2013, 15:54:23 �

"Мамой клянусь!"
Записан
artem123
Давненько
**
Offline 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 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 Offline

Сообщений: 1079

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



Просмотр профиля
Ответ #5 : Июль 10, 2013, 00:08:18 �

Мда, не для моих познаний задача, похоже графы и логорифмы
Записан
Tim
Гений-Говорун
*
Offline Offline

Сообщений: 1079

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



Просмотр профиля
Ответ #6 : Июль 12, 2013, 00:09:46 �

Ну что нет никого кто в графах силен?
Записан
buka
Гений
*****
Offline 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 Offline

Сообщений: 1079

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



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

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

Сообщений: 335

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


Просмотр профиля
Ответ #9 : Июль 12, 2013, 00:47:55 �

Eсли же передавать только победы...
И каким тогда должно быть доказательство для n игроков?
Записан
Tim
Гений-Говорун
*
Offline Offline

Сообщений: 1079

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



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

Eсли же передавать только победы...
И каким тогда должно быть доказательство для n игроков?
Вот с этим у меня и затык, частный случай понятен, а общий как-то не догоняю
Записан
Питер Пен
Свой человек
***
Offline Offline

Сообщений: 335

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


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

Eсли же передавать только победы...
И каким тогда должно быть доказательство для n игроков?
Вот с этим у меня и затык, частный случай понятен, а общий как-то не догоняю
Кодировка битов… направление ребер между игроками…биекция… изоморфизм графов… – ну нах...!
Пусть Замат доказывает.
Записан
Tim
Гений-Говорун
*
Offline Offline

Сообщений: 1079

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



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

Eсли же передавать только победы...
И каким тогда должно быть доказательство для n игроков?
Вот с этим у меня и затык, частный случай понятен, а общий как-то не догоняю
Кодировка битов… направление ребер между игроками…биекция… изоморфизм графов… – ну нах...!
Пусть Замат доказывает.

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

Сообщений: 335

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


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

Eсли же передавать только победы...
И каким тогда должно быть доказательство для n игроков?
Вот с этим у меня и затык, частный случай понятен, а общий как-то не догоняю
Кодировка битов… направление ребер между игроками…биекция… изоморфизм графов… – ну нах...!
Пусть Замат доказывает.

Во ты загрузил на ночь глядя )))) кроме слов игроки и нах... ни одного знакомого ))), а если серьезно вот интересно, на пальцах частный случай легко решается, а как общий вид решить непонятно нефига
Замат тебе еще должен быть известен...
Я себя ощущаю как ворона из анекдота - время 3 часа ночи, а я сижу еще на работе и долблю по клавишам... Пиз..ц я еба...уый!!!!
Последнее редактирование: Июль 12, 2013, 01:11:20 от Питер Пен Записан
Tim
Гений-Говорун
*
Offline Offline

Сообщений: 1079

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



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

Eсли же передавать только победы...
И каким тогда должно быть доказательство для n игроков?
Вот с этим у меня и затык, частный случай понятен, а общий как-то не догоняю
Кодировка битов… направление ребер между игроками…биекция… изоморфизм графов… – ну нах...!
Пусть Замат доказывает.

Во ты загрузил на ночь глядя )))) кроме слов игроки и нах... ни одного знакомого ))), а если серьезно вот интересно, на пальцах частный случай легко решается, а как общий вид решить непонятно нефига
Замат тебе еще должен быть известен...
Я себя ощущаю как ворона из анекдота - время 3 часа ночи, а я сижу еще на работе и долблю по клавишам... Еб....ый!!!!
Moscow never sleeps ))))))
Записан
Страниц: [1] 2 3
  Печать  
 
Перейти в: