※ 引述《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...:) -- 人，總是殘缺而完美的... 　　 　　殘缺的是任誰終其一生都無法得到一切， 　　　 　　　　　完美的是任誰少了一點就不再是他本人了... 殘缺的我尋尋覓覓找尋著殘缺的你... 且讓我們共同拼出一片無間的 完 美 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 24.186.210.99