Tuesday, March 11, 2008

The first 3 of 8 - about the qualification of Olympic baseball game

今年中華棒球隊參加奧運八搶三資格賽,前三名篤定可以取得北京奧運的入場卷。但是,這個賽制引發了一個數學問題:

究竟至少要贏幾場才能保證晉級(得到前三名)?


當然 ptt 有鄉民提供解答,答案是「六勝」。但是我覺得敘述的方式另我不太滿意(就是「我太笨看不懂」的意思啦),所以我跟 Oshin 大針對六勝的答案討論了一下,我們得到一些想法如下。

我們知道八隊將有 C(8,2) = 28 場對戰,也就是總計有 28 場勝場數。拿下七勝(全勝)當然是篤定晉級,全敗則是鐵定無法晉級。所以我們先考慮只拿下一至三勝的情形。如果只能拿下三勝,則排名篤定為前三名的條件為倒數五名皆最多兩勝,但是這樣一來勝場數總和至多為 26 (勝場數分別為 7, 6, 3, 2, 2, 2, 2, 2),這便違反勝場數總和為 28 的條件,所以矛盾。同理可得知拿下兩或三勝的情形,也是不可能篤定前三名。

如果拿下四勝的話,考慮以下的 case。假設一至八名分別為 A, B, C, D, E, F, G, 與 H。A拿下全勝, B 只輸給 A,另外 C 只輸給 A, B,而 D 只輸給 A, B, C,則 D 雖然拿下四勝,也頂多排在第四名,慘遭淘汰。所以四勝是無法保證篤定晉級的。

接下來考慮拿下五勝的情形。一樣假設一至八名分別為 A, B, C, D, E, F, G, H,而且前四名勝場數分別為 6, 6, 5, 5,以下為這四名的對戰情形

A 只輸給 D;
B 只輸給 A;
C 只輸給 A, B;
D 只輸給 B, C;

那麼我們只能期待中華隊是 C 了。所以五勝不是篤定晉級的保證。

最後我們考慮六勝的 cases。如果只有三隊以下拿下六勝,那麼拿下六勝鐵定晉級。而且這個情形是「可能發生」的。譬如,前三名的隊伍彼此對戰為 A 勝 B, B 勝 C 且 C 勝 A,形成三隊互咬,而其他五隊遇到這三隊則是全敗。如果有五隊以上拿下六勝,這個也不可能,因為如此一來將得到至少 30 場的勝場數,超過 28 的總勝場數的限制。所以我們得以把焦點縮小到「前四名拿下恰好六勝」的情形。

前四名拿下六勝,所以這四隊當中每一隊都各吞下一敗。我們可以分成兩個 cases 討論:
  1. 四隊互咬 (他們的一敗只輸給前四名當中的一隊)
  2. 前四名中至少有一隊輸給後面四名其中一隊
假設有 A, B, C, D, E, F, G, H 八隊,前四名為 A, B, C, D,且這四隊各拿下六勝一敗。針對 1. 的情形,不失一般性可以假設 A-> B, B->C, C->D, D->A,其中 A->B代表「A輸給B」。但是 A 和 C 的比賽結果,不管 A->C 或 C->A,將會造成 A, C 當中其中一隊吞下兩敗,所以我們得到矛盾。針對 2. 的情形,不失一般性我們假設 A->E,則 B, C, D 三隊所吞下的一敗皆貢獻給 A 了。但是如此一來,不管 B, C 的對戰結果如何, B 或 C 其中一隊將會變成兩敗,也因此產生矛盾。所以,我們知道「前四名皆為六勝」的情形是不可能發生的。

結論就是,中華隊贏了 6 場鐵定晉級啦!

好吧,我承認我認真了......


2 comments:

Maggie said...

恩,真的很認真。
如果這是你的論文討論就太好了。

話雖如此,中華隊還是要六勝!!

Mark said...

其實你的分析研究了許久,還是看不太懂,但贏了澳之後就恍然大悟了~~~反正就是前進北京,稱霸奧運就對了阿!!!