【問題】網球公開賽

[曾阿牛 10]

在網球公開賽程裡　任兩名選手恰遭遇一次並且分出勝負

賽程結束後　如果有選手的戰績滿足以下的條件：

對於任何異於自己的選手 A 來說　　要嘛打敗 A　要嘛打敗某個打敗 A 的選手　

則該名選手得到 Dean 的頭銜　　　　以下是題目的原文

In the Open Tennis Tournament, every player plays every other player exactly once and either wins or loses.

Define a Dean to be a player who, for every other player A, either beats A or beats a player B who beats A.

問題來了　　請問..

1. 說明在一個網球公開賽程結束後　可能會有超過一個 Dean

2. 說明在一個網球公開賽程結束後　至少會有一個 Dean

[arthurduh1 10]

我曾經看過一題等價的題目XD

1.這小題舉例即可：

設有A,B,C,D四人，

比賽結果是：

A勝B

A勝C

D勝A

D勝B

C勝B

C勝D

那麼A,C,D皆是Dean，因

A勝B

A勝C

A勝C 且 C勝D

C勝D 且 D勝A

C勝B

C勝D

D勝A

D勝B

D勝A 且 A勝C

2.用數學歸納法證明

(i)若選手共2人，令為D,B，不失一般性，令D勝B，則D是Dean，即Dean存在。

(ii)令選手共n人時Dean存在，且其名為D，則可依下列規則將其他n-1個人分成兩個集合A,B：

集合A裡的選手皆勝D，集合B裡的選手皆敗給D。注意因為要符合Dean的定義，集合A中的任何一個人必定敗給集合B中的其中一位(不一定是相同一位)

如今多出一人N使得人數增為n+1人，

　　若N敗給D，那麼可以直接將N歸類於集合B，D仍為Dean

　　若N勝D，

　　　　　假設N敗給集合B中其中一人，那麼可以直接將N歸類於集合A，D仍為Dean

　　　　　假設N勝過集合B任何一人，那麼N是Dean，因N勝D，N勝集合B中任何人，而集合A中任何人又都直接被集合B中一人打敗。

(iii)綜合(i),(ii)及數學歸納法，不論n為何(n>=2)，n人網球公開賽皆有一人為Dean

如果有敘述不清之處再提問吧！

[曾阿牛 10]

嗯嗯　是了　答得漂亮　　　個人想看看您所謂的等價的題目　感謝

[arthurduh1 10]

嗯嗯　是了　答得漂亮　　　個人想看看您所謂的等價的題目　感謝

等價的題目也沒什麼特別的啦！

它是說有n個城市

兩兩城市間皆有單行道，

那麼必定有一個城市可以到達所有其他城市，且最多路過一個城市。

當然最直接的就是把它還原成圖論裡的有向圖。

但基本上它們都是同義的！

[曾阿牛 10]

arthurduh1 大大如果是自己解出這問題的話　那就真的有點不簡單

像是第一個問題　我自己想到的例子是用甲乙丙三人　

其中　甲勝乙勝丙勝甲　則三人皆是 Dean　

[arthurduh1 10]

其實我第一次解決這題時，沒想到可以用集合觀念，敘述語句笨拙許多XD

記住數學歸納法，在很多時候都會發揮很好的效用的。像這一題只要想到數歸，接下來的就不是難事了！

對呀！三個人應該是數目最小的例子了。

這幾天我有持續地在想這一題，我發現除了2,4人之外(不考慮一個人)，其他的人數都有可能產生所有人皆為Dean的情況呢！

對了，你這一題是在哪看到的？我想要到時候把相關結果Po上網誌時引用一下XD

Thanks！

[曾阿牛 10]

這題我是故意沒有提示要用歸納法做　為的是要讓讀者從自己對題目的觀感來想辦法解題

個人認為　就算有提示(甚至是限制)要用歸納法做　這問題也沒有那麼簡單　關鍵在歸納步驟的推導是否過得去

此題是從 書名為　Funndations of Higher Mathematics　(3rd Edition)　

作者是　Peter Fletcher　和　C. Wayne Patty

的 Chapter 3 的 Exercise 72.

而該書的 Chapter 3 正好講的是 induction 與 recurrence

關於 除了 2, 4 人之外 ，其他的人數都有可能產生所有人皆為 Dean 的情況！？！？

這真是個大膽的敘述耶　　如果是真的　那 2 與 4 究竟有哪裡特別哩？

又該怎麼造 n 個人皆為 Dean 的戰績呢？　　實在有些超乎想像

我突然又體會到　我老師常說的：數學問題真的很多

[曾阿牛 10]

關於 除了 2, 4 人之外 ，其他的人數都有可能產生所有人皆為 Dean 的情況

後來還是想了一想　　便讓我聯想到　當初　

本來想加一個自己想到的小問題上來考考各位大大

但後來因為覺得太過簡單而作罷

該小問題是　試說明　一位 Dean 的戰績　其勝場數 會大於等於 ( n - 1 ) / 2

由此可以推論出　當 n 是偶數時　

一個 n 名選手的網球公開賽程 不可能存在 n 人皆為 Dean 的情況

＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿

以上紅色的部分是錯的　謹此註明

[arthurduh1 10]

Thx !

嗯......因為紅字部分是錯的，所以結果應該也不是正確的。

可以舉六人的例子：

　ＡＢＣＤＥＦ

Ａ　ｘｘｏｏｘ

Ｂ　　ｏｏｘｘ

Ｃ　　　ｘｘｏ

Ｄ　　　　ｏｏ

Ｅ　　　　　ｘ

Ｆ

「o」代表此格所對的左方選手勝過所對的上方選手

「x」代表此格所對的左方選手敗給所對的上方選手

你可以試著驗證看看，會發現每一個人皆是Dean。

也可以把他們的關係用單向圖畫出(正六邊形)，會看到這個例子的圖是十分對稱、規律的。

我是用建構法，單數從三個選手、雙數從六個選手皆是Dean開始建構，

四人以下則是靠窮舉法，所以我也找不出一個漂亮的解釋。

主要觀念是

當多增加一位選手時，

想辦法創造許多A勝B B勝C C勝A 的循環鏈。

你也可以試著想看看呀！

(我剛剛還發現一件更神奇的事：

就是網球公開賽不可能恰有兩個Dean！！！)