YLL討論網

某次棋賽中，參賽者恰好和其它每位參賽者比賽一次。
規定每局勝者得一分，
敗者得0分；
平手各得0.5分。
賽程全部結束後，我們稱“爆冷門”的賽局
為總得分高者竟然輸給總得分低者。
試證：無論比賽的結果如何，“爆冷門”的賽局局數小於全部賽局總數的3/4 。

For there are 2n players:
When players is re-ordered with the score descendingly,
A1, A2, A3, A4,.... ,A2n
let F(Ai,Aj)=1 if Ai win Aj; =0 if Aj win Ai; =0.5 if Ai Aj tie.( i<>j)
then
(0) total score=n(2n-1)
(1) Score of Ak= Sigma{ F(Ak, Aj)|j=1 to 2n, j <> k}
(2) 爆冷門賽局 <=sigma{ F(Aj,  Ai)|1<=i<j<=2n}
(3) Sigma{ Score of Ak|k=1 to n}>= total score/2=n(2n-1)/2
(4) F(Ai,Aj)+F(Aj,Ai)=1
==>
(2n-1)*n
=Sigma{ F(Ak, Aj)+F(Aj,Ak)|k=1 to n,j=1 to 2n, j <> k}
=Sigma{ F(Ak, Aj)|k=1 to n,j=1 to 2n, j <> k}+ Sigma{ F(Aj, Ak)|k=1 to n,j=1 to 2n, j <> k}
=Sigma{ Score of Ak|k=1 to n}+   Sigma{ F(Aj, Ak)|k=1 to n,j=1 to 2n, j <> k}

so,
{ F(Aj, Ak)|k=1 to n,j=1 to 2n, j > k} (this is part 1 of 爆冷門賽局)
<={ F(Aj, Ak)|k=1 to n,j=1 to 2n, j <> k}
<= (2n-1)*n/2

(5) consider A(n+1) to A2n:
part 2 of 爆冷門賽局<= A(n+1) to A2n賽局<=n(n-1)/2

Total 爆冷門賽局=part1+part2
<=n(2n-1)/2+ n(n-1)/2
=n(2n-1)/2+n(2n-2)/4
<n(2n-1)/2+n(2n-1)/4
=3n(2n-1)/4
=total score*(3/4) ##

For there are (2n+1) players: do it by yourself. ^_^

都沒意見,表示都看得董

This is only your think

Meowth 寫到:都沒意見,表示都看得董

This is only your think

"  This is only your think "  <---- Who wrote this?
自首打3下!!! 不自首的自己切腹.

你的圖像和簽名檔真棒！

翻譯:

當有 2n 選手:  
將選手依分數遞減排列為
A1, A2, A3, A4,.... ,A2n
---
令 函數F(Ai,Aj)表示 選手Ai 與選手Aj 對打時,選手Ai的當局得分:
如果 Ai 贏 Aj 則 F(Ai,Aj)=1
如果 Aj 贏 Ai 則 F(Ai,Aj)=0
如果 Ai Aj 平手, 則 F(Ai,Aj)=0.5
如果 i=j (Ai,Aj同一人,沒打,沒分), 則 F(Ai,Aj)=0

---
則
(0) 全部分數=局數=(2n)(2n-1) /2= n(2n-1)

(1) 選手Ak的分數 =(選手Ak 與選手A1 對打時,選手Ak的當局得分)
+(選手Ak 與選手A2 對打時,選手Ak的當局得分)
+....+(選手Ak 與選手A2n 對打時,選手Ak的當局得分)
=Sigma{ F(Ak, Aj)|j=1 to 2n}

(2) 令 函數 G(Ai,Aj)=1表示 選手Ai 與選手Aj 對打時爆冷門:且令i<j
(i) 如果選手Ai,Aj總分數相同, 則 G(Ai,Aj)=0 <= F(Aj,Ai)
(ii)如果Ai總分數> Aj總分數,則
如果 Ai 贏 Aj 則 G(Ai,Aj)=0 =F(Aj,Ai)
如果 Aj 贏 Ai 則 G(Ai,Aj)=1 =F(Aj,Ai)
如果 Ai Aj 平手, 則 G(Aj,Ai)=0 <0.5=F(Aj,Ai)

比較G,F, 可知: G(Ai,Aj)<=F(Aj,Ai); (對每一個i<j)..... (2-a)

故,爆冷門賽局數 =sigma{ G(Ai, Aj)|1<=i<j<=2n}
<= sigma{ F(Aj, Ai)|1<=i<j<=2n}

(3) 前半選手的總分數>=後半選手的總分數
==> 前半選手的總分數>=總分數/2
==> 前半選手的總分數=Sigma{ 選手Ak的分數 |k=1 to n}>= 總分數/2= n(2n-1)/2

(4)每局比賽都會全部總分增加一分; F(Ai,Aj)+F(Aj,Ai)=1 (i<>j)
==>
前半選手有參與的總局數=n*(2n-1)
=Sigma{ F(Ak, Aj)+F(Aj,Ak)|k=1 to n,j=1 to 2n, j <> k}
=Sigma{ F(Ak, Aj)|k=1 to n,j=1 to 2n, j <> k}+ Sigma{ F(Aj, Ak)|k=1 to n,j=1 to 2n, j <> k}
=Sigma{ Ak分數|k=1 to n}(前半選手的總分數)+ Sigma{ F(Aj, Ak)|k=1 to n,j=1 to 2n, j <> k}

and from (3), 得
sigma{ F(Aj, Ak)|k=1 to n,j=1 to 2n, j <> k}
=前半選手有參與的總局數-前半選手的總分數
<=n(2n-1) -n(2n-1)/2
<= n(2n-1)/2

故,
前半選手有參與的爆冷門賽局數(這是 爆冷門賽局的第一部分)
=sigma{ G(Ak, Aj)|k=1 to n,j=1 to 2n, j > k}
<=sigma{ F(Aj, Ak)|k=1 to n,j=1 to 2n, j > k}  (因為 (2-a))
<=sigma{ F(Aj, Ak)|k=1 to n,j=1 to 2n, j <> k}
<= (2n-1)*n/2

(5) 考慮 後半選手 A(n+1) to A2n:
只有後半選手的參與的爆冷門賽局(爆冷門賽局第2部分) <= A(n+1) to A2n賽局數 <= n(n-1)/2

==>
全部 爆冷門賽局
=爆冷門賽局的第一部分+爆冷門賽局第2部分
<=n(2n-1)/2+ n(n-1)/2
=n(2n-1)/2+n(2n-2)/4
<n(2n-1)/2+n(2n-1)/4
=3n(2n-1)/4
=總分數*(3/4) ##