MathDB
Problems
Contests
National and Regional Contests
Germany Contests
QEDMO
2005 QEDMO 1st
3 (C2)
3 (C2)
Part of
2005 QEDMO 1st
Problems
(1)
Chain in a turnament
Source: QEDMO 2005
11/8/2005
At a turnament between
n
n
n
persons, everyone playes exactly one time against everyone else, and at one game there is everytime a winner and a looser. Prove that one can arrange the participants in a chain
P
1
→
P
2
→
.
.
.
→
P
n
P_1 \to P_2 \to ... \to P_n
P
1
→
P
2
→
...
→
P
n
such that the
i
i
i
-th person has won against the
(
i
+
1
)
(i+1)
(
i
+
1
)
-th person.
induction