※ 引述《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://webptt.com/cn.aspx?n=bbs/Math/M.1637609224.A.BFB.html