[中學] 建中考題

看板Math作者 (cornerstone)時間1年前 (2022/10/09 11:34), 1年前編輯推噓6(6推 0噓 87→)
留言93則, 3人參與, 1年前最新討論串1/1
https://imgur.com/a/Zq4Wniu 我想請問這題要怎麼解？ 還有這題是運用到哪些國高中的數學觀念？ 我覺得跟排列組合好像有點關係， 因為假設這四個選手做排列：4！ 再看迴圈的部分，可是還是不太知道該如何著手。 另外又想過四人比賽的話，就需要六場比賽， 每一個選手，都會和另外3個對手有輸贏的關係 所以共有2^3 = 8 種輸贏的可能 可是接下來就卡住了... 有試著一個一個列想找規律，但有點複雜 真的不知道該怎麼解 想請版上的朋友們幫忙看看 謝謝！！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.238.181.248 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1665286473.A.B58.html
推
10/09 18:40, 1年前 , 1F
提示: 簡化題目, 如果只問 3 個人的話如何?
10/09 18:40, 1F
→
10/09 18:41, 1年前 , 2F
這個過程以及結果要怎麼應用到 4 個人的狀況上?
10/09 18:41, 2F
→
10/09 18:43, 1年前 , 3F
其中特別注意可以從 3 人狀況套用到 4 人狀況的性質
10/09 18:43, 3F
謝謝您！！我試著看看～不知道有沒有錯 假設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
→
10/09 22:42, 1年前 , 4F
謝謝！！我試著從3個人開始推，但還需要多點提示..
10/09 22:42, 4F
推
10/09 23:38, 1年前 , 5F
(1) 3 人的遞迴關係不是 6 種喔, 你仔細看看你列的
10/09 23:38, 5F
→
10/09 23:38, 1年前 , 6F
(2) 3 人無遞迴關係的也不只這 3 種, 你少指定東西
10/09 23:38, 6F
→
10/09 23:38, 1年前 , 7F
(3) 上兩個加起來要是 2^3 = 8 沒錯
10/09 23:38, 7F
→
10/09 23:39, 1年前 , 8F
(4) (1) 和 (2) 有一個很容易可以推廣到 4 人
10/09 23:39, 8F
→
10/09 23:41, 1年前 , 9F
還是不知道是哪個的話: 試著把條件換句話說
10/09 23:41, 9F
※ 編輯: cornerstone (36.238.181.248 臺灣), 10/10/2022 00:53:13
→
10/10 00:53, 1年前 , 10F
真的真的非常謝謝您！我修改了(1)和(2)，這樣(3)
10/10 00:53, 10F
→
10/10 00:57, 1年前 , 11F
就吻合了，可是總覺得我這樣列，思慮不周全，常出錯
10/10 00:57, 11F
→
10/10 01:03, 1年前 , 12F
我試著修改內文，把錯誤的地方修改...但不確定目前
10/10 01:03, 12F
→
10/10 01:05, 1年前 , 13F
這樣是否正確，從三人推到四人遞迴的部分還沒想通
10/10 01:05, 13F
→
10/10 14:07, 1年前 , 14F
請問四個人時，沒有遞迴關係時就是一個人贏三場？
10/10 14:07, 14F
→
10/10 14:07, 1年前 , 15F
假設A贏三場的情況下，共有4種情況是沒有遞迴的？
10/10 14:07, 15F
推
10/10 14:32, 1年前 , 16F
方向對了: 這題要從沒有遞迴關係的下去考慮比較簡單
10/10 14:32, 16F
→
10/10 14:33, 1年前 , 17F
考慮一下沒有遞迴關係的狀況所有人的輸贏關係
10/10 14:33, 17F
→
10/10 14:35, 1年前 , 18F
三人的 6 種狀況其實有一個簡單說明可以獲得
10/10 14:35, 18F
→
10/10 14:36, 1年前 , 19F
這正是為何這個部份能夠容易推廣到 4 人的原因
10/10 14:36, 19F
→
10/10 14:37, 1年前 , 20F
這個「簡單說明」即是我上面「換句話說」想提的
10/10 14:37, 20F
→
10/10 16:31, 1年前 , 21F
太謝謝您！所以從沒有遞迴的地方開始想：3人6種是
10/10 16:31, 21F
→
10/10 16:31, 1年前 , 22F
n(n-2)2，這個公式可以推到四個人，有16種沒有遞迴?
10/10 16:31, 22F
→
10/10 16:33, 1年前 , 23F
L大您真的太厲害了！但16種贏三場沒有遞迴的方式後
10/10 16:33, 23F
→
10/10 16:35, 1年前 , 24F
感覺如果我能「換句話說」我好像就能懂了..真抱歉阿
10/10 16:35, 24F
→
10/10 16:37, 1年前 , 25F
下一步是不是要從贏兩場贏一場繼續推呢？謝謝！
10/10 16:37, 25F
→
10/10 17:58, 1年前 , 26F
請問3人比賽時，需要三場，共8種狀況，有6種是沒有
10/10 17:58, 26F
→
10/10 17:59, 1年前 , 27F
遞迴關係，4人時需要有6場比賽，在64種可能的結果下
10/10 17:59, 27F
→
10/10 18:02, 1年前 , 28F
有16種是沒有遞迴，這樣說來，是否在每一場比賽中，
10/10 18:02, 28F
→
10/10 18:02, 1年前 , 29F
一定有人可以打敗其他人？
10/10 18:02, 29F
推
10/10 20:31, 1年前 , 30F
首先, 4 人的不只 16 種, 不過要細找怎麼列比較麻煩
10/10 20:31, 30F
→
10/10 20:32, 1年前 , 31F
注意到沒有遞迴的對戰性質: 如果有甲贏乙乙贏丙
10/10 20:32, 31F
→
10/10 20:32, 1年前 , 32F
則因為不能有迴圈的關係甲一定贏丙
10/10 20:32, 32F
→
10/10 20:32, 1年前 , 33F
這就是你之前觀察到的 3 人時一定有人兩勝這回事
10/10 20:32, 33F
→
10/10 20:33, 1年前 , 34F
思考一下這個性質如果套用到 4 人的話
10/10 20:33, 34F
→
10/10 20:33, 1年前 , 35F
這 4 人之間的勝負關係會如何?
10/10 20:33, 35F
→
10/10 20:33, 1年前 , 36F
然後你就知道 4 人無遞迴時有多少種了
10/10 20:33, 36F
→
10/10 20:48, 1年前 , 37F
(我會這樣說也就表示 n(n-2)*2 這個公式是錯的了
10/10 20:48, 37F
→
10/10 20:49, 1年前 , 38F
實際公式是什麼把上面這問題想通了就知道了)
10/10 20:49, 38F
→
10/11 09:06, 1年前 , 39F
10/11 09:06, 39F
→
10/11 15:54, 1年前 , 40F
謝謝！！竟然有解答，而且還有兩種方式..太感激了！
10/11 15:54, 40F
→
10/11 17:00, 1年前 , 41F
不過我還在想LPH66給的提示，因為沒想通即使看完了
10/11 17:00, 41F
→
10/11 17:00, 1年前 , 42F
解答，好像還是沒有辦法完全理解（唉，數感不好）
10/11 17:00, 42F
推
10/11 18:06, 1年前 , 43F
我想導引你的方向是上圖的解法二
10/11 18:06, 43F
→
10/11 18:07, 1年前 , 44F
主要重點在於觀察到勝場有這種「遞推」的關係後
10/11 18:07, 44F
→
10/11 18:07, 1年前 , 45F
我們總是能找出一個「排名」使得所有戰績都是
10/11 18:07, 45F
→
10/11 18:08, 1年前 , 46F
高排名贏過低排名的, 而這即是無迴圈關係的充要條件
10/11 18:08, 46F
→
10/11 18:08, 1年前 , 47F
既然我們總能找出排名, 那總排法數就是全排列數 N!
10/11 18:08, 47F
→
10/11 18:09, 1年前 , 48F
注意到上圖解法二過程中有出現一個四人的順序關係
10/11 18:09, 48F
→
10/11 18:09, 1年前 , 49F
這就是我在說的「排名」
10/11 18:09, 49F
→
10/11 18:10, 1年前 , 50F
這個「總能找出排名」的性質很容易由三人推廣至四人
10/11 18:10, 50F
→
10/11 18:10, 1年前 , 51F
甚至是多人, 因此才能確定 N! 就是無迴圈數的公式
10/11 18:10, 51F
→
10/11 18:12, 1年前 , 52F
我上面的提示刻意不提「排序」、「勝場遞推」等詞
10/11 18:12, 52F
→
10/11 18:12, 1年前 , 53F
因為這個關係正是這個題目能找出公式的關鍵所在
10/11 18:12, 53F
→
10/11 20:40, 1年前 , 54F
真的真的很感謝您一步一步的引導思考和這麼詳細的
10/11 20:40, 54F
→
10/11 20:41, 1年前 , 55F
解說，真的超有幫助的！不過懂大概的方向，細節還真
10/11 20:41, 55F
→
10/11 20:42, 1年前 , 56F
的需要再想，我目前是用畫圖，三人是畫三角形，四人
10/11 20:42, 56F
→
10/11 20:43, 1年前 , 57F
是畫正方形，但還沒辦法從觀察到遞推，真的很佩服大
10/11 20:43, 57F
→
10/11 20:44, 1年前 , 58F
可以這麼輕鬆的就融會貫通，不過還是很高興有進展！
10/11 20:44, 58F
→
10/11 21:21, 1年前 , 59F
並不是很重要, 不過我解法二中的 "第一位選手勝過
10/11 21:21, 59F
→
10/11 21:21, 1年前 , 60F
第二位、第二位勝過第三位、第三位勝過第四位" 的四
10/11 21:21, 60F
→
10/11 21:21, 1年前 , 61F
人排序關係並不是假設沒有三人迴圈才有的, 而是所
10/11 21:21, 61F
→
10/11 21:21, 1年前 , 62F
有的對戰表都有的. 其也並非從三人對戰時、無三人迴
10/11 21:21, 62F
→
10/11 21:21, 1年前 , 63F
圈的情況下推出來的, 實際上這才是解法二中的關鍵(R
10/11 21:21, 63F
→
10/11 21:21, 1年前 , 64F
edei's theorem), 所謂的"三勝兩勝一勝零勝" 是在確
10/11 21:21, 64F
→
10/11 21:21, 1年前 , 65F
保有"四人排序關係"的存在性、並假設無三人迴圈後
10/11 21:21, 65F
→
10/11 21:21, 1年前 , 66F
的立即推論.
10/11 21:21, 66F
→
10/11 21:21, 1年前 , 67F
另外這四人排序關係只有在沒有三人迴圈下才一定與
10/11 21:21, 67F
→
10/11 21:21, 1年前 , 68F
實際排名一致, 例如在解法一中subcase2.2, 我們是可
10/11 21:21, 68F
→
10/11 21:21, 1年前 , 69F
以有C勝D勝A勝B這種排序關係.
10/11 21:21, 69F
→
10/11 22:41, 1年前 , 70F
額外補充一點 解法二是用圖論的基本手法證的 並非是
10/11 22:41, 70F
→
10/11 22:41, 1年前 , 71F
從三人對戰無三人迴圈的情況下再對四人對戰的情況作
10/11 22:41, 71F
→
10/11 22:41, 1年前 , 72F
歸納的 我會建議原po如果要看解法二 可能就不要再去
10/11 22:41, 72F
→
10/11 22:41, 1年前 , 73F
考慮三人對戰會發生什麼事 因為解法二並沒有用到這
10/11 22:41, 73F
→
10/11 22:41, 1年前 , 74F
件事 反而只有解法一才有用到這件事
10/11 22:41, 74F
→
10/11 23:11, 1年前 , 75F
(實際上從 "先任意選三位選手" 一直到 "不失一般性"
10/11 23:11, 75F
→
10/11 23:11, 1年前 , 76F
這裡只是照搬Redei的證明 我們不需要假設無三人迴
10/11 23:11, 76F
→
10/11 23:11, 1年前 , 77F
圈發生)
10/11 23:11, 77F
→
10/11 23:18, 1年前 , 78F
如果可以直接用 Redei's theorem, 則我們可以直接
10/11 23:18, 78F
→
10/11 23:18, 1年前 , 79F
證N人對戰的情況 不需要什麼遞推
10/11 23:18, 79F
推
10/11 23:52, 1年前 , 80F
我之所以要說「換句話說」就在於: 我期待你可以從
10/11 23:52, 80F
→
10/11 23:53, 1年前 , 81F
三人的狀況中析取出「三人結果有其順序但何序皆可」
10/11 23:53, 81F
→
10/11 23:53, 1年前 , 82F
這樣一個性質出來用
10/11 23:53, 82F
→
10/11 23:54, 1年前 , 83F
注意到這個「有其順序但何序皆可」正是解法二的核心
10/11 23:54, 83F
→
10/11 23:55, 1年前 , 84F
(並且最後變成其所提的那個定理敘述)
10/11 23:55, 84F
→
10/11 23:56, 1年前 , 85F
而這中間有一個可能的連接點在於: 三人狀況的 6 種
10/11 23:56, 85F
→
10/11 23:56, 1年前 , 86F
無迴圈的取法正好是三人的所有排列
10/11 23:56, 86F
→
10/11 23:58, 1年前 , 87F
觀察到這個「所有排列」然後聯想到「何序皆可」
10/11 23:58, 87F
→
10/11 23:58, 1年前 , 88F
這個才是我期待你(原PO)發現這個性質的方向
10/11 23:58, 88F
→
10/12 00:00, 1年前 , 89F
既然「何序皆可」, 那重要的應該是這些排序的共同點
10/12 00:00, 89F
→
10/12 00:01, 1年前 , 90F
然後得到「有其順序」這個發想, 這就能推到四人了
10/12 00:01, 90F
→
10/12 11:52, 1年前 , 91F
真的真的太謝謝hwanger和LPH66大的幫忙，你們的講解
10/12 11:52, 91F
→
10/12 11:53, 1年前 , 92F
真的超有幫助的，我會好好從對戰關係裡面想...而且
10/12 11:53, 92F
→
10/12 11:54, 1年前 , 93F
這問題竟然還有數學理論，真的覺得很有趣！謝謝你們
10/12 11:54, 93F
‣ 更多 cornerstone 的文章
文章代碼(AID): #1ZGa59jO (Math)