推 LPH66 : 提示: 簡化題目, 如果只問 3 個人的話如何? 10/09 18:40
→ LPH66 : 這個過程以及結果要怎麼應用到 4 個人的狀況上? 10/09 18:41
→ LPH66 : 其中特別注意可以從 3 人狀況套用到 4 人狀況的性質 10/09 18:43
謝謝您！！我試著看看～不知道有沒有錯
假設ABC三人，沒有遞迴關係時就是有人贏兩場：（之前沒考慮到）
A打敗B，A打敗C （但B和C有兩種關係：B贏或C贏）= 2種可能
B打敗A，B打敗C （但A和C有兩種關係：A贏或C贏）= 2種可能
C打敗A，C打敗B （但A和B有兩種關係：A贏或B贏）= 2種可能
沒有遞迴關係：6種可能
有遞迴關係就是最多只有贏一場
(a) (第一種) A>B>C>A , (第二種) A>C>B>A
(b) B>A>C>B（和第二種一樣）, B>C>A>B (和第一種一樣)
(C) C>A>B>C（重複第一種）, C>B>A>C（重複第二種）
修改：畫成三角形時就發現我之前那樣寫重複了，
所以遞迴的關係只有兩種，而不是之前算的六種
這樣的話總共就是8種可能，符合2^3
這樣列出來的話，三個人的遞迴關係有6種？
^^^^^^^^^^^^^^^^^^^^^^
這裡錯了，三個人的遞迴關係是2種
修改後，的確三個人的話需要3場比賽，每一場都有輸贏的話是2^3種可能，
（四個人就需要六場比賽，輸贏是2^6種可能）
可以再給我一點提示嗎？
還有我對於幾場比賽和幾種可能的觀念是對的嗎？
謝謝！！
※ 編輯: cornerstone (36.238.181.248 臺灣), 10/09/2022 22:42:04
→ cornerstone : 謝謝！！我試著從3個人開始推，但還需要多點提示.. 10/09 22:42
推 LPH66 : (1) 3 人的遞迴關係不是 6 種喔, 你仔細看看你列的 10/09 23:38
→ LPH66 : (2) 3 人無遞迴關係的也不只這 3 種, 你少指定東西 10/09 23:38
→ LPH66 : (3) 上兩個加起來要是 2^3 = 8 沒錯 10/09 23:38
→ LPH66 : (4) (1) 和 (2) 有一個很容易可以推廣到 4 人 10/09 23:39
→ LPH66 : 還是不知道是哪個的話: 試著把條件換句話說 10/09 23:41
※ 編輯: cornerstone (36.238.181.248 臺灣), 10/10/2022 00:53:13
→ cornerstone : 真的真的非常謝謝您！我修改了(1)和(2)，這樣(3) 10/10 00:53
→ cornerstone : 就吻合了，可是總覺得我這樣列，思慮不周全，常出錯 10/10 00:57
→ cornerstone : 我試著修改內文，把錯誤的地方修改...但不確定目前 10/10 01:03
→ cornerstone : 這樣是否正確，從三人推到四人遞迴的部分還沒想通 10/10 01:05
→ cornerstone : 請問四個人時，沒有遞迴關係時就是一個人贏三場？ 10/10 14:07
→ cornerstone : 假設A贏三場的情況下，共有4種情況是沒有遞迴的？ 10/10 14:07
推 LPH66 : 方向對了: 這題要從沒有遞迴關係的下去考慮比較簡單 10/10 14:32
→ LPH66 : 考慮一下沒有遞迴關係的狀況所有人的輸贏關係 10/10 14:33
→ LPH66 : 三人的 6 種狀況其實有一個簡單說明可以獲得 10/10 14:35
→ LPH66 : 這正是為何這個部份能夠容易推廣到 4 人的原因 10/10 14:36
→ LPH66 : 這個「簡單說明」即是我上面「換句話說」想提的 10/10 14:37
→ cornerstone : 太謝謝您！所以從沒有遞迴的地方開始想：3人6種是 10/10 16:31
→ cornerstone : n(n-2)2，這個公式可以推到四個人，有16種沒有遞迴? 10/10 16:31
→ cornerstone : L大您真的太厲害了！但16種贏三場沒有遞迴的方式後 10/10 16:33
→ cornerstone : 感覺如果我能「換句話說」我好像就能懂了..真抱歉阿 10/10 16:35
→ cornerstone : 下一步是不是要從贏兩場贏一場繼續推呢？謝謝！ 10/10 16:37
→ cornerstone : 請問3人比賽時，需要三場，共8種狀況，有6種是沒有 10/10 17:58
→ cornerstone : 遞迴關係，4人時需要有6場比賽，在64種可能的結果下 10/10 17:59
→ cornerstone : 有16種是沒有遞迴，這樣說來，是否在每一場比賽中， 10/10 18:02
→ cornerstone : 一定有人可以打敗其他人？ 10/10 18:02
推 LPH66 : 首先, 4 人的不只 16 種, 不過要細找怎麼列比較麻煩 10/10 20:31
→ LPH66 : 注意到沒有遞迴的對戰性質: 如果有甲贏乙乙贏丙 10/10 20:32
→ LPH66 : 則因為不能有迴圈的關係甲一定贏丙 10/10 20:32
→ LPH66 : 這就是你之前觀察到的 3 人時一定有人兩勝這回事 10/10 20:32
→ LPH66 : 思考一下這個性質如果套用到 4 人的話 10/10 20:33
→ LPH66 : 這 4 人之間的勝負關係會如何? 10/10 20:33
→ LPH66 : 然後你就知道 4 人無遞迴時有多少種了 10/10 20:33
→ LPH66 : (我會這樣說也就表示 n(n-2)*2 這個公式是錯的了 10/10 20:48
→ LPH66 : 實際公式是什麼把上面這問題想通了就知道了) 10/10 20:49
→ cornerstone : 謝謝！！竟然有解答，而且還有兩種方式..太感激了！ 10/11 15:54
→ cornerstone : 不過我還在想LPH66給的提示，因為沒想通即使看完了 10/11 17:00
→ cornerstone : 解答，好像還是沒有辦法完全理解（唉，數感不好） 10/11 17:00
推 LPH66 : 我想導引你的方向是上圖的解法二 10/11 18:06
→ LPH66 : 主要重點在於觀察到勝場有這種「遞推」的關係後 10/11 18:07
→ LPH66 : 我們總是能找出一個「排名」使得所有戰績都是 10/11 18:07
→ LPH66 : 高排名贏過低排名的, 而這即是無迴圈關係的充要條件 10/11 18:08
→ LPH66 : 既然我們總能找出排名, 那總排法數就是全排列數 N! 10/11 18:08
→ LPH66 : 注意到上圖解法二過程中有出現一個四人的順序關係 10/11 18:09
→ LPH66 : 這就是我在說的「排名」 10/11 18:09
→ LPH66 : 這個「總能找出排名」的性質很容易由三人推廣至四人 10/11 18:10
→ LPH66 : 甚至是多人, 因此才能確定 N! 就是無迴圈數的公式 10/11 18:10
→ LPH66 : 我上面的提示刻意不提「排序」、「勝場遞推」等詞 10/11 18:12
→ LPH66 : 因為這個關係正是這個題目能找出公式的關鍵所在 10/11 18:12
→ cornerstone : 真的真的很感謝您一步一步的引導思考和這麼詳細的 10/11 20:40
→ cornerstone : 解說，真的超有幫助的！不過懂大概的方向，細節還真 10/11 20:41
→ cornerstone : 的需要再想，我目前是用畫圖，三人是畫三角形，四人 10/11 20:42
→ cornerstone : 是畫正方形，但還沒辦法從觀察到遞推，真的很佩服大 10/11 20:43
→ cornerstone : 可以這麼輕鬆的就融會貫通，不過還是很高興有進展！ 10/11 20:44
→ hwanger : 並不是很重要, 不過我解法二中的 "第一位選手勝過 10/11 21:21
→ hwanger : 第二位、第二位勝過第三位、第三位勝過第四位" 的四 10/11 21:21
→ hwanger : 人排序關係並不是假設沒有三人迴圈才有的, 而是所 10/11 21:21
→ hwanger : 有的對戰表都有的. 其也並非從三人對戰時、無三人迴 10/11 21:21
→ hwanger : 圈的情況下推出來的, 實際上這才是解法二中的關鍵(R 10/11 21:21
→ hwanger : edei's theorem), 所謂的"三勝兩勝一勝零勝" 是在確 10/11 21:21
→ hwanger : 保有"四人排序關係"的存在性、並假設無三人迴圈後 10/11 21:21
→ hwanger : 的立即推論. 10/11 21:21
→ hwanger : 另外這四人排序關係只有在沒有三人迴圈下才一定與 10/11 21:21
→ hwanger : 實際排名一致, 例如在解法一中subcase2.2, 我們是可 10/11 21:21
→ hwanger : 以有C勝D勝A勝B這種排序關係. 10/11 21:21
→ hwanger : 額外補充一點 解法二是用圖論的基本手法證的 並非是 10/11 22:41
→ hwanger : 從三人對戰無三人迴圈的情況下再對四人對戰的情況作 10/11 22:41
→ hwanger : 歸納的 我會建議原po如果要看解法二 可能就不要再去 10/11 22:41
→ hwanger : 考慮三人對戰會發生什麼事 因為解法二並沒有用到這 10/11 22:41
→ hwanger : 件事 反而只有解法一才有用到這件事 10/11 22:41
→ hwanger : (實際上從 "先任意選三位選手" 一直到 "不失一般性" 10/11 23:11
→ hwanger : 這裡只是照搬Redei的證明 我們不需要假設無三人迴 10/11 23:11
→ hwanger : 圈發生) 10/11 23:11
→ hwanger : 如果可以直接用 Redei's theorem, 則我們可以直接 10/11 23:18
→ hwanger : 證N人對戰的情況 不需要什麼遞推 10/11 23:18
推 LPH66 : 我之所以要說「換句話說」就在於: 我期待你可以從 10/11 23:52
→ LPH66 : 三人的狀況中析取出「三人結果有其順序但何序皆可」 10/11 23:53
→ LPH66 : 這樣一個性質出來用 10/11 23:53
→ LPH66 : 注意到這個「有其順序但何序皆可」正是解法二的核心 10/11 23:54
→ LPH66 : (並且最後變成其所提的那個定理敘述) 10/11 23:55
→ LPH66 : 而這中間有一個可能的連接點在於: 三人狀況的 6 種 10/11 23:56
→ LPH66 : 無迴圈的取法正好是三人的所有排列 10/11 23:56
→ LPH66 : 觀察到這個「所有排列」然後聯想到「何序皆可」 10/11 23:58
→ LPH66 : 這個才是我期待你(原PO)發現這個性質的方向 10/11 23:58
→ LPH66 : 既然「何序皆可」, 那重要的應該是這些排序的共同點 10/12 00:00
→ LPH66 : 然後得到「有其順序」這個發想, 這就能推到四人了 10/12 00:01
→ cornerstone : 真的真的太謝謝hwanger和LPH66大的幫忙，你們的講解 10/12 11:52
→ cornerstone : 真的超有幫助的，我會好好從對戰關係裡面想...而且 10/12 11:53
→ cornerstone : 這問題竟然還有數學理論，真的覺得很有趣！謝謝你們 10/12 11:54