ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 31373
Темы:    [ Ориентированные графы ]
[ Турниры и турнирные таблицы ]
[ Сочетания и размещения ]
Сложность: 4-
Классы: 6,7,8,9
В корзину
Прислать комментарий

Условие

12 шахматистов сыграли турнир в один круг. Потом каждый из них написал 12 списков. В первом только он, в (k+1)-м – те, кто были в k-м и те, у кого они выиграли. Оказалось, что у каждого шахматиста 12-й список отличается от 11-го. Сколько было ничьих?


Решение

Рассмотрим ориентированный граф, вершины которого – шахматисты, а стрелки ведут от выигравшего к проигравшему. Условие означает, что для каждого шахматиста есть другой, до которого можно добраться только по 11 стрелкам (это, в частности означает, что от каждого шахматиста можно добраться до любого другого). Рассмотрим такой путь: A1 выиграл у A2, A2 – у A3, ..., A11 – у A12. Заметим, что Ai  (1 < i < 12)  не мог выиграть у A1 (иначе от A2 можно было бы добраться до каждого не более чем по 10 стрелкам). Но кто-то у A1 выиграл (иначе до A1 вообще нельзя было бы добраться), значит, это – A12. Как и выше, показываем, что в полученном цикле каждый мог выиграть только у следующего.

Следовательно, результативных партий всего 12, а ничьих –  12·11 : 2 – 12 = 54.


Ответ

54 ничьих.

Источники и прецеденты использования

книга
Автор Иванов С.В.
Название Математический кружок
глава
Номер 14
Название Разные задачи
Тема Неопределено
задача
Номер 29

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .