→ Desperato : 又找到漏洞了WWW 等等我想要怎麼補qw q 06/16 00:18
※ 編輯: Desperato (140.112.25.105), 06/16/2017 00:49:24
推 cuttlefish : 讚 原來我應開始猜錯方向了 難怪做不出來XD 06/16 07:06
※ 引述《cuttlefish (無聊ing ><^> .o O)》之銘言：
: 是否存在整數集合X使得對於每個整數n存在唯一的a,b in X使得a+2b=n
: 謝謝
S為任何整數集合
令 A_S : Sx S -> Z
(a, b) -> z = a+2b
題目表示是否存在整數集合X
使得 A_X 同時是 injective 與 surjective 那就只好是 bijective
我們要用下面這個lemma 直接construct出所求的 X
(Lemma) S 有限整數集合，|S|>1，A_S injective，給定任意 z not in Im(A_S)
則存在集合S' = S 聯集 {x, y}，其中x, y為S以外的相異整數
滿足 A_S' injective，且 z in Im(A_S')
(pf) 令 S 中最小整數為 x', 最大整數為 y', d = y'-x' > 0
顯然 Im(A_S) 也是有限整數集合, 且最小值為 3x',最大值為 3y'
我們希望加入 x < x' 和 y > y' 只會生出新的數
(簡單來說，只要固定 z = 2x+y，x和y同時往外拉
就能拉到大家都不重複)
新加入的 x 可能形成的數為 3x, 2x+s, x+2s, s in S
新加入的 y 可能形成的數為 3y, 2y+s, y+2s, s in S, 以及 2x+y, x+2y
選擇 x < x'-2d = 3x'-2y' <= 3x'-2s
以及 y > y'+2d = 3y'-2x' >= 3y'-2s
則 3x < 2x+s < x+2s < 3x' < 3y' < y+2s < 2y+s < 3y, for all s in S
因此可能會重複的數字只剩下 2x+y 和 x+2y
現在考慮 x = x'-2d+1, y = y'+2d+1
如果 2x+y >= z 則把 x 調小使得 2x+y = z (y有可能要+1)
如果 2x+y < z 則把 y 調大使得 2x+y = z
固定 2x+y = z 之後
把 y 往上調至 y > 4y'-z, 此時會有 4y' < z+y = 2x+2y
2y' < x+y
y+2s < y+2y' < x+2y < 2y+s
x+2s < x+2y' < 2x+y < y+2s
其中 y+2s < x+2y < 2y+s 代表新的 x+2y 不會和別人重複
x+2s < 2x+y < y+2s 代表新的 2x+y 不會和 x, y加入後的新數字重複
而 z = 2x+y 本來就不會和 Im(A_S) 重疊
因此 Im(A_S') 是 injective，以及 z = 2x+y in Im(A_S')
以下證明就只是在說，反正 X 就用lemma一個一個加出來就好了
(Prop) 存在整數集合X 使得 A_X injective 且 Im(X) = Z
(pf) 為了方便起見，令 N_0 = {0}
N_(2k-1) = N_(2k-2) 聯集 {-k} for all k in N
N_(2k) = N_(2k-1) 聯集 { k}
N_(2k)其實就是 {0, -1, 1, -2, 2, -3, 3, ... -k, k}
令 X_0 = {0, 1}，顯然 A_(X_0) 是 injective
如果有限整數集合 X_n 滿足 (1) A_(X_n) injective
(2) N_n 是 Im(A_(X_n)) 的子集
必可找到最小正整數 m>=n
使得 N_m 是 Im(A_n) 的子集，但 N_(m+1)不是
設 z 是唯一一個在 N_(m+1)裡，但不在 N_m 裡的整數
根據 Lemma 可以找到一個 X_(n+1)
滿足 (1) A_(X_(n+1)) injective
(2) z in Im(A_(X_(n+1)))
因此 N_(n+1) 包含於 N_(m+1) 包含於 Im(A_(X_(n+1)))
根據上述可以遞迴定義 X_n for all n>=0
inf
令 X = union X_n
n=0
(1) N_n 包含於 Im(A_(X_n)) 包含於 Im(A_X) for all n>=0
因此 Im(A_X) 就只能是全整數集合
(2) 給定任意整數 z = A_X(a, b) = A_X(c, d)
存在 X_(k_a) 使得 a 在 X_(k_a) 裡面
令 k = k_a, k_b, k_c, k_d 中最大的
則 a, b, c, d 都在 X_k 裡面
因此 z = A_(X_k)(a, b) = A_(X_k)(c, d)
但是 A_(X_k) 是 injective，所以 (a, b) = (c, d)
以上得到 X 為所求集合
...想法明明很簡單 打起來莫名其妙累=A=
這是個非常浪費的構造方法
如果 X_n 中最大最小值相減是 d_n 的話
那 d_n 會輕鬆超過 5^n XD
--
嗯嗯ow o
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1497543207.A.B06.html