Re: [代數] 多項式2
※ 引述《cuttlefish (無聊ing ><^> .o O)》之銘言：
: 試證明對於每一個整數n, 存在唯一的多項式P,
: 使得其係數在{0,1,2,...,9}之中且滿足P(-2)=P(-5)=n.
: 謝謝
實在想不到V大那個方法...qw q 只能自己錯誤嘗試
(i) 如果有P存在，P是唯一的
令 P = (x+2)(x+5) Q + n
P' = (x+2)(x+5) Q'+ n
則 P-P' = (x+2)(x+5)(Q-Q')
由於 P-P' 每一項絕對值都小於10
Q-Q'的常數項為0, 一次項為0, 二次項為0, ...
因此 Q=Q', P=P'
(ii) 多項式P存在
簡單來說 做了一串整係數 P_i 之後 從裡面擷取 P
(以下的[]都是高斯記號)
n = 0 時顯然 P = 0
n > 0 令 P_0 = n
n < 0 令 P_0 = k(x+2)(x+5) + n, 非負整數 k 滿足 P_0(0) >= 0
令 P_i 的第i項係數為 a_i, (第i+1項係數為 b_i, 第i+2項係數為 c_i)
定義 P_(i+1) = P_i + [a_i/10] (x+2)(x+5)(x-1) x^i
for all i >= 0 (n > 0), i >= 1 (n < 0)
注意 (x+2)(x+5)(x-1) = x^3 + 6x^2 + 3x - 10
實際上就是把第i項係數的十位數以上數字分解後往前丟
容易得知以下幾點
(1) deg P_i <= i+2
(2) P_i 每項係數皆為非負整數，滿足 P_i(-2) = P_i(-5) = n
(3) 所有 P_i 的係數和皆相同
(4) 對所有 t<i, P_i 的第t項係數為 (a_t)%10 (C++表示法)
結合以上我們其實可以表示
i-1
P_i = c_i x^(i+2) + b_i x^(i+1) + a_i x^i + sum (a_t)%10 x^t
t=0
其中 for all i>=0
a_(i+3) = [a_i/10] + 6[a_(i+1)/10] + 3[a_(i+2)/10]
b_(i+3) = [a_(i+1)/10] + 6[a_(i+2)/10]
c_(i+3) = [a_(i+2)/10]
s
因此係數和 >= sum (a_i)%10 for all s>=0
i=0
(Lemma) 若存在正整數 j 滿足 (a_i)%10 = 0 for all i >= j
則 a_i = a_j for all i >= j
(pf) 這代表 [a_i/10] = a_i/10
因此 a_(i+3) = ( 1 a_i + 6 a_(i+1) + 3 a_(i+2) )/10
x^3 = (1+6x+3x^2)/10, x = 1, -1/2, -1/5
所以 a_i = A 1^i + B (-1/2)^i + C (-1/5)^i
可是 a_i 是整數，因此 a_i = A for all i >= j
現在來創造多項式 P 滿足每項係數皆為0到9整數
由於 (a_i)%10 是非負整數，係數和是有限定值(upper bound)
因此必定有個 j 滿足 Lemma 的條件
令 a_j = 10d, 則 c_(j+3) = d, b_(j+3) = 7d, a_(j+3) = 10d
j+2
所以 P_(j+3) = d (x^2+7x+10) x^(j+5) + sum (a_t)%10 x^t
t=0
令 P = P_(j+3) - d(x^2+7x+10)x^(j+5) 即為所求多項式
總覺得最近變得很愛用constructive硬幹法...
可是又不像V大那麼酷的做法
--
嗯嗯ow o
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1498898401.A.056.html
→
07/01 23:49, , 1F
07/01 23:49, 1F
推
07/02 19:54, , 2F
07/02 19:54, 2F
實際上進位無限多次的情況很常見 用excel跑一下就知道
我是證明最後P_i會進入一種循環狀態 把循環部分丟掉就是P
(2)(3)的用處是導出lemma的前題 強迫P_i進入循環狀態
※ 編輯: Desperato (101.10.36.239), 07/02/2017 20:06:41
推
07/02 21:25, , 3F
07/02 21:25, 3F
討論串 (同標題文章)