Теннисный турнир

[Ktina]

N теннисистов сыграли турнир в один круг (каждый сыграл с каждым из остальных ровно один раз). Ни для кого не секрет, что в теннисе ничьих не бывает. Для каждого $1\le i\le N$ игрок под номером $i$ выиграл $x_i$ партий. Доказать, что необходимым и достаточным условием для того, чтобы нашлись три игрока А, Б и В такие, что А выиграл у Б, Б выиграл у В, а В выиграл у А, является

$\sum x_i^2<\frac{(N-1)N(2N-1)}{6}$
(Putnam Competition)


Упрощённый (сильно) вариант этой же задачи:
$N\ge 3$ теннисистов участвовали в турнире. Известно, что каждые два теннисиста сыграли между собой ровно один раз и не было ни одного теннисиста, проигравшего все встречи. Доказать, что найдутся теннисисты A, B, C такие, что A выиграл у B, B у C, C у A. (В теннисе ничьих не бывает.)
(Московская Математическая Олимпиада)

[Dave]

(Оффтоп)

Я так подозреваю, что Putnam Competition - это некое соревнование, в котором участвует только один человек по фамилии Putnam

Перепишем неравенство так:

$$\sum_{i=1}^N x_i^2 < \sum_{i=1}^N (i-1)^2. \eqno(1)$$

Необходимость следует из примера, когда любой игрок с большим номером выиграл у любого игрока с меньшим номером - тогда в $(1)$ имеется равенство и нетранзитивной тройки игроков нет.
Достаточность доказывается по индукции. При $N=3$ неравенство $(1)$ возможно только в случае $x_1=x_2=x_3=1$, т.е. вся тройка-требуемая. Допустим, что утверждение доказано для $N=n \geqslant 3$. Докажем его для $N=n+1$. Пусть А - игрок, выигравший наибольшее количество партий (или один из таковых). Не ограничивая общности, можно считать, что это игрок под номером $n+1$. Пусть $W$ - множество игроков, у которых А выиграл, а $L$ - которым проиграл. Очевидно, что $W$ непусто. Если множество $L$ пусто, то верно равенство $x_{n+1}=n$, вычитая квадрат которого из имеющегося неравенства $(1)$ для $N=n+1$ получим неравенство $(1)$ для $N=n$, и существование нужной тройки в оставшейся группе из $n$ игроков следует из уже доказанного утверждения для $N=n$. Если множество $L$ непусто, то взяв любого игрока В из $L$, получим, что он должен был проиграть какому-то игроку Б из $W$, иначе он выиграл бы больше партий, чем А (он выиграл по крайней мере у всех из $W$ и у А), что противоречит выбору А. Но это означает, что тройка А,Б,В - требуемая.

[Ktina]

Dave в сообщении #544760 писал(а):

(Оффтоп)

Я так подозреваю, что Putnam Competition - это некое соревнование, в котором участвует только один человек по фамилии Putnam

http://math.scu.edu/putnam/
http://amc.maa.org/a-activities/a7-prob ... ndex.shtml

[Dave]

(Оффтоп)

Ktina в сообщении #544764 писал(а):

Dave в сообщении #544760 писал(а):

Я так подозреваю, что Putnam Competition - это некое соревнование, в котором участвует только один человек по фамилии Putnam

http://math.scu.edu/putnam/
http://amc.maa.org/a-activities/a7-prob ... ndex.shtml

Это была шутка, если кто не понял.

[Dave]

А можно узнать, какого года эта задача? Я хочу посмотреть, как Putnam её решал. По вышеуказанным ссылкам такого условия не нашёл.

[Ktina]

Dave в сообщении #545048 писал(а):

А можно узнать, какого года эта задача? Я хочу посмотреть, как Putnam её решал. По вышеуказанным ссылкам такого условия не нашёл.

18-й Патнэм, 1958-ой год, задача B3.
http://150.19.10.56/www.kalva.demon.co.uk/putnam.html