作者cornerstone (cornerstone)
看板Math
标题[中学] 建中考题
时间Sun Oct 9 11:34:31 2022
https://imgur.com/a/Zq4Wniu
我想请问这题要怎麽解？
还有这题是运用到哪些国高中的数学观念？
我觉得跟排列组合好像有点关系，
因为假设这四个选手做排列：4！
再看回圈的部分，可是还是不太知道该如何着手。
另外又想过四人比赛的话，就需要六场比赛，
每一个选手，都会和另外3个对手有输赢的关系
所以共有2^3 = 8 种输赢的可能
可是接下来就卡住了...
有试着一个一个列想找规律，但有点复杂
真的不知道该怎麽解
想请版上的朋友们帮忙看看
谢谢！！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.238.181.248 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1665286473.A.B58.html
1F：推 LPH66 : 提示: 简化题目, 如果只问 3 个人的话如何? 10/09 18:40
2F：→ LPH66 : 这个过程以及结果要怎麽应用到 4 个人的状况上? 10/09 18:41
3F：→ 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
4F：→ cornerstone : 谢谢！！我试着从3个人开始推，但还需要多点提示.. 10/09 22:42
5F：推 LPH66 : (1) 3 人的递回关系不是 6 种喔, 你仔细看看你列的 10/09 23:38
6F：→ LPH66 : (2) 3 人无递回关系的也不只这 3 种, 你少指定东西 10/09 23:38
7F：→ LPH66 : (3) 上两个加起来要是 2^3 = 8 没错 10/09 23:38
8F：→ LPH66 : (4) (1) 和 (2) 有一个很容易可以推广到 4 人 10/09 23:39
9F：→ LPH66 : 还是不知道是哪个的话: 试着把条件换句话说 10/09 23:41
※ 编辑: cornerstone (36.238.181.248 台湾), 10/10/2022 00:53:13
10F：→ cornerstone : 真的真的非常谢谢您！我修改了(1)和(2)，这样(3) 10/10 00:53
11F：→ cornerstone : 就吻合了，可是总觉得我这样列，思虑不周全，常出错 10/10 00:57
12F：→ cornerstone : 我试着修改内文，把错误的地方修改...但不确定目前 10/10 01:03
13F：→ cornerstone : 这样是否正确，从三人推到四人递回的部分还没想通 10/10 01:05
14F：→ cornerstone : 请问四个人时，没有递回关系时就是一个人赢三场？ 10/10 14:07
15F：→ cornerstone : 假设A赢三场的情况下，共有4种情况是没有递回的？ 10/10 14:07
16F：推 LPH66 : 方向对了: 这题要从没有递回关系的下去考虑比较简单 10/10 14:32
17F：→ LPH66 : 考虑一下没有递回关系的状况所有人的输赢关系 10/10 14:33
18F：→ LPH66 : 三人的 6 种状况其实有一个简单说明可以获得 10/10 14:35
19F：→ LPH66 : 这正是为何这个部份能够容易推广到 4 人的原因 10/10 14:36
20F：→ LPH66 : 这个「简单说明」即是我上面「换句话说」想提的 10/10 14:37
21F：→ cornerstone : 太谢谢您！所以从没有递回的地方开始想：3人6种是 10/10 16:31
22F：→ cornerstone : n(n-2)2，这个公式可以推到四个人，有16种没有递回? 10/10 16:31
23F：→ cornerstone : L大您真的太厉害了！但16种赢三场没有递回的方式後 10/10 16:33
24F：→ cornerstone : 感觉如果我能「换句话说」我好像就能懂了..真抱歉阿 10/10 16:35
25F：→ cornerstone : 下一步是不是要从赢两场赢一场继续推呢？谢谢！ 10/10 16:37
26F：→ cornerstone : 请问3人比赛时，需要三场，共8种状况，有6种是没有 10/10 17:58
27F：→ cornerstone : 递回关系，4人时需要有6场比赛，在64种可能的结果下 10/10 17:59
28F：→ cornerstone : 有16种是没有递回，这样说来，是否在每一场比赛中， 10/10 18:02
29F：→ cornerstone : 一定有人可以打败其他人？ 10/10 18:02
30F：推 LPH66 : 首先, 4 人的不只 16 种, 不过要细找怎麽列比较麻烦 10/10 20:31
31F：→ LPH66 : 注意到没有递回的对战性质: 如果有甲赢乙乙赢丙 10/10 20:32
32F：→ LPH66 : 则因为不能有回圈的关系甲一定赢丙 10/10 20:32
33F：→ LPH66 : 这就是你之前观察到的 3 人时一定有人两胜这回事 10/10 20:32
34F：→ LPH66 : 思考一下这个性质如果套用到 4 人的话 10/10 20:33
35F：→ LPH66 : 这 4 人之间的胜负关系会如何? 10/10 20:33
36F：→ LPH66 : 然後你就知道 4 人无递回时有多少种了 10/10 20:33
37F：→ LPH66 : (我会这样说也就表示 n(n-2)*2 这个公式是错的了 10/10 20:48
38F：→ LPH66 : 实际公式是什麽把上面这问题想通了就知道了) 10/10 20:49
40F：→ cornerstone : 谢谢！！竟然有解答，而且还有两种方式..太感激了！ 10/11 15:54
41F：→ cornerstone : 不过我还在想LPH66给的提示，因为没想通即使看完了 10/11 17:00
42F：→ cornerstone : 解答，好像还是没有办法完全理解（唉，数感不好） 10/11 17:00
43F：推 LPH66 : 我想导引你的方向是上图的解法二 10/11 18:06
44F：→ LPH66 : 主要重点在於观察到胜场有这种「递推」的关系後 10/11 18:07
45F：→ LPH66 : 我们总是能找出一个「排名」使得所有战绩都是 10/11 18:07
46F：→ LPH66 : 高排名赢过低排名的, 而这即是无回圈关系的充要条件 10/11 18:08
47F：→ LPH66 : 既然我们总能找出排名, 那总排法数就是全排列数 N! 10/11 18:08
48F：→ LPH66 : 注意到上图解法二过程中有出现一个四人的顺序关系 10/11 18:09
49F：→ LPH66 : 这就是我在说的「排名」 10/11 18:09
50F：→ LPH66 : 这个「总能找出排名」的性质很容易由三人推广至四人 10/11 18:10
51F：→ LPH66 : 甚至是多人, 因此才能确定 N! 就是无回圈数的公式 10/11 18:10
52F：→ LPH66 : 我上面的提示刻意不提「排序」、「胜场递推」等词 10/11 18:12
53F：→ LPH66 : 因为这个关系正是这个题目能找出公式的关键所在 10/11 18:12
54F：→ cornerstone : 真的真的很感谢您一步一步的引导思考和这麽详细的 10/11 20:40
55F：→ cornerstone : 解说，真的超有帮助的！不过懂大概的方向，细节还真 10/11 20:41
56F：→ cornerstone : 的需要再想，我目前是用画图，三人是画三角形，四人 10/11 20:42
57F：→ cornerstone : 是画正方形，但还没办法从观察到递推，真的很佩服大 10/11 20:43
58F：→ cornerstone : 可以这麽轻松的就融会贯通，不过还是很高兴有进展！ 10/11 20:44
59F：→ hwanger : 并不是很重要, 不过我解法二中的 "第一位选手胜过 10/11 21:21
60F：→ hwanger : 第二位、第二位胜过第三位、第三位胜过第四位" 的四 10/11 21:21
61F：→ hwanger : 人排序关系并不是假设没有三人回圈才有的, 而是所 10/11 21:21
62F：→ hwanger : 有的对战表都有的. 其也并非从三人对战时、无三人回 10/11 21:21
63F：→ hwanger : 圈的情况下推出来的, 实际上这才是解法二中的关键(R 10/11 21:21
64F：→ hwanger : edei's theorem), 所谓的"三胜两胜一胜零胜" 是在确 10/11 21:21
65F：→ hwanger : 保有"四人排序关系"的存在性、并假设无三人回圈後 10/11 21:21
66F：→ hwanger : 的立即推论. 10/11 21:21
67F：→ hwanger : 另外这四人排序关系只有在没有三人回圈下才一定与 10/11 21:21
68F：→ hwanger : 实际排名一致, 例如在解法一中subcase2.2, 我们是可 10/11 21:21
69F：→ hwanger : 以有C胜D胜A胜B这种排序关系. 10/11 21:21
70F：→ hwanger : 额外补充一点 解法二是用图论的基本手法证的 并非是 10/11 22:41
71F：→ hwanger : 从三人对战无三人回圈的情况下再对四人对战的情况作 10/11 22:41
72F：→ hwanger : 归纳的 我会建议原po如果要看解法二 可能就不要再去 10/11 22:41
73F：→ hwanger : 考虑三人对战会发生什麽事 因为解法二并没有用到这 10/11 22:41
74F：→ hwanger : 件事 反而只有解法一才有用到这件事 10/11 22:41
75F：→ hwanger : (实际上从 "先任意选三位选手" 一直到 "不失一般性" 10/11 23:11
76F：→ hwanger : 这里只是照搬Redei的证明 我们不需要假设无三人回 10/11 23:11
77F：→ hwanger : 圈发生) 10/11 23:11
78F：→ hwanger : 如果可以直接用 Redei's theorem, 则我们可以直接 10/11 23:18
79F：→ hwanger : 证N人对战的情况 不需要什麽递推 10/11 23:18
80F：推 LPH66 : 我之所以要说「换句话说」就在於: 我期待你可以从 10/11 23:52
81F：→ LPH66 : 三人的状况中析取出「三人结果有其顺序但何序皆可」 10/11 23:53
82F：→ LPH66 : 这样一个性质出来用 10/11 23:53
83F：→ LPH66 : 注意到这个「有其顺序但何序皆可」正是解法二的核心 10/11 23:54
84F：→ LPH66 : (并且最後变成其所提的那个定理叙述) 10/11 23:55
85F：→ LPH66 : 而这中间有一个可能的连接点在於: 三人状况的 6 种 10/11 23:56
86F：→ LPH66 : 无回圈的取法正好是三人的所有排列 10/11 23:56
87F：→ LPH66 : 观察到这个「所有排列」然後联想到「何序皆可」 10/11 23:58
88F：→ LPH66 : 这个才是我期待你(原PO)发现这个性质的方向 10/11 23:58
89F：→ LPH66 : 既然「何序皆可」, 那重要的应该是这些排序的共同点 10/12 00:00
90F：→ LPH66 : 然後得到「有其顺序」这个发想, 这就能推到四人了 10/12 00:01
91F：→ cornerstone : 真的真的太谢谢hwanger和LPH66大的帮忙，你们的讲解 10/12 11:52
92F：→ cornerstone : 真的超有帮助的，我会好好从对战关系里面想...而且 10/12 11:53
93F：→ cornerstone : 这问题竟然还有数学理论，真的觉得很有趣！谢谢你们 10/12 11:54