※ 引述《pikahacker (Beat Cal)》之銘言：
: 1. Prove that every tournament contains a Hamiltonian path.
: (Tournament map: a directed graph such that for every pair of distinct vertices
: u and v, there is either an edge from u to v or v to u, but never both.)
: (I can prove this easily by double induction, but I heard there is a classic
: proof by strong induction. How?)
Assume this holds for all k-tournament
Consider first k people in k+1-tournament, by induction hypothesis,
there is a k-HamPath, say a1->a2->a3->...->ak
If a wins a1, then a ->a1->a2->...->ak is a (k+1)-HamPath
k+1 k+1
Similar result could be obtained if a wins a
k k+1
If a1->a and a ->ak
k+1 k+1
there exists i such that a ->a and a ->a
i k+1 k+1 i+1
Thus a1->a2->...->a ->a ->a ->...->ak is a (k+1)-HamPath. Q.E.D.
i k+1 i+1
回darkseer，沒有interestingly，請愛用it is interesting that...:)