推 cmrafsts : 像我這種比較笨的人就會只想先寫個生成函數XD 11/23 03:51
推 fragmentwing: 推詳解 11/23 15:57
推 alan23273850: 讚讚讚 推一個 我就不發錢了 11/23 21:41
※ 引述《TimcApple (肥鵝)》之銘言：
: FALL 2021 AMC12 A
: 25. 設 m >= 5 且為奇數
: 並設 D(m) 表示四元數組 (a_1, a_2 ,a_3 ,a_4) 的組數
: 其中 a_i 為相異的整數，1 <= a_i <= m (i=1,2,3,4)
: 且 m 可以整除 a_1+a_2+a_3+a_4
: 若有一個多項式 q(x)=c_3 x^3+c_2 x^2+c_1 x+c_0
: 對所有的奇數 m >= 5 滿足 D(m) = q(m)，則 c_1=？
: (A) -6 (B) -1 (C) 4 (D) 6 (E) 11
應推文要求回覆解答
設 C_m = { (a_1, a_2, a_3, a_4) : a_i 相異且 1 <= a_i <= m }
在這裡面切成不同組 E，切法如下：
如果 a_i-b_i (mod m) 全都相等
則 (a_1, a_2, a_3, a_4) 和 (b_1, b_2, b_3, b_4) 就在同一個 E 裡面
Ex: m = 5, 則 1534, 2145, 3251, 4312, 5423 會在同一組
則每一組 E 都有以下特性：
(1) E 有 m 個元素
(2) 不同的 E 不會有一樣的元素
(3) C_m 中每個元素都在某個 E 裡面
(4) 每個元素的總和取餘數 即 a_1 + a_2 + a_3 + a_4 (mod m) 都不一樣
也就是說 E 內的元素 取餘數剛好跑過一遍 0, 1, ..., m
這個性質只有在 gcd(m, 4) = 1, 即 m 是奇數的時候成立
由於 D(m) 特指 a_1 + a_2 + a_3 + a_4 = 0 (mod m) 的情況
不難得到 D(m) = |C_m| / m
= m(m-1)(m-2)(m-3) / m
= (m-1)(m-2)(m-3)
其餘顯然。
========================================================
以上事實上就是用了 group action，只是沒有寫出專有名詞而已
我之前見過的另一個類似的題目是這樣：
平面上，設 A(0, 0), B(m, n), 其中 gcd(m, n) = 1
從 A 走到 B，若每步只能往右或往上走 1 格
且整條路徑都不能在 AB 直線上方，試問有幾種走法？
(pf) 若沒有不能在 AB 上方的條件，原題有 C(m+n, n) 種路徑（走捷徑）
考慮範圍 D = {(x, y): x, y in Z, 0 <= x <= m, 0 <= y <= n}
設函數 h: D -> Z, (x, y) |-> my-nx
給定任意路徑 p : A -> v1 -> v2 -> ... -> vk -> B, k=m+n-1
考慮其高度折線圖 H = H_p
H(0) = h(A) = 0
H(i) = h(vi) i = 1,...,k
H(m+n) = h(B) = 0
然後將 (j, H(j)), j = 0,...,m+n 連成折線圖
則這個折線圖 H 有以下特點
(1) H(0) = H(m+n) = 0
(2) H(0), H(1), ..., H(k) 皆相異 (Why?)
現在將路徑重新表示成 p = X1 X2 ... X(m+n), 其中 Xi = U (上) 或 R (右)
設其輪換 pC = X2 X3 ... X(m+n) X1
則折線圖 H_p 可以透過以下方式變成 H_pC：
首先將第一段線 (0, 0) -> (1, H_p(1)) 平移到 (n, 0) -> (1+n, H_p(1))
然後將整個折線圖往左平移 1, 再往下平移 H_p(1), 就會得到 H_pC 了
注意輪換雖然會改變高度，但不會改變各點的相對高度
考慮 E = { p, pC, pC^2, ..., pC^k }，則
(1) E 有 m+n 個元素
(2) 每個 pC^i 都不一樣 (Why?)
(3) 每個路徑 p 都會在某個 E 裡面
(4) E 內剛好會有一條路徑 pC^i, 其折線圖 H_pC^i 完全不在 x 軸上方
這在幾何上很明顯，因為 H_p 會在某個 (n, H_p(n)) 有唯一的最高點
最高點怎麼輪換都是最高點，會在 x 軸上方，除了輪換到 pC^n 時
(n, H_p(n)) 被換到 (0, 0)，導致其他點都會在 x 軸下方
由於不能在 AB 上方的條件，對應整條 H 都不在 x 軸上方
因此本題答案就是 C(m+n, n) / (m+n)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.234.191 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1637609224.A.BFB.html