Задача 31373

Темы:    [ Ориентированные графы ] [ Турниры и турнирные таблицы ] [ Сочетания и размещения ]

Сложность: 4- Классы: 6,7,8,9

Условие

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

Решение

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

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

Ответ

54 ничьих.

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

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