團體賽T-6
已知多項式 f(x) 的各項係數均為不大於 3 的非負整數，且滿足 f(2) = 2016。像這樣的多項式一共有若干個？
由 thepiano 老師提示，許介彥教授的大作中，是以 "生成函數" 的方法，得出: 滿足 f(2) = n 的多項式一共有 [n/2] +1 個。("[ ]" 為高斯符號)
由於答案形式簡單，故嘗試構思一個過程簡明的方法，如下。 ( 在此考慮 f(2) = n 的條件 )
解: 令 f(x) = a₀ + a₁x + a₂x² + a₃x³ + a₄x⁴+... 為符合條件的多項式，即:
n = a₀ + a₁2 + a₂2² + a₃2³ + a₄2⁴+... ， {a₀, a₁, a₂...}∈{0,1,2,3}
由係數的限制，聯想到 4 進位表示法，故將上式改寫為:
n = (a₀ + a₂2² + a₄2⁴+...) + 2*(a₁+ a₃2² + a₅2⁴+...)
= (a₀ + a₂4¹ + a₄4² +...) + 2*(a₁+ a₃4¹ + a₅4² +...) [ "( )" 內均為 4 進位的架構 ]
上式可視為將 n 表示為 P + 2Q，即一個序組{a₀, a₁, a₂...}對應一個 "將 n 表示為一非負整數與一非負偶數之和" 的方法 (一對一對應)。
反之，依上式將 n 表示為一非負整數與一非負偶數之和時，亦因任一非負整數恰有一個符合上式形式的 4 進位表示法，
故亦對應一個序組 {a₀, a₁, a₂...} (一對一對應)。
綜上，所求多項式的個數 = "將 n 表示為一非負整數與一非負偶數之和" 的方法數 {如: n+0, (n-2)+2, (n-4)+4...} = [n/2] +1 ("[ ]" 為高斯符號)
原題答案為 [2016/2]+1 = 1009。
-------------------------------------------------------------------------------
本題若用遞迴關係來切入，可得
A(n+1) = A(n)+1 (當 n 為奇數) 或 A(n+1) = A(n) (當 n 為偶數) [A(k)表示滿足 f(2) = k 的多項式個數]，進而得出上述結論，過程亦不複雜。
[ 本帖最後由 cefepime 於 2017-2-22 13:23 編輯 ]
