Math 板


LINE

※ 引述《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://webptt.com/m.aspx?n=bbs/Math/M.1497543207.A.B06.html
1F:→ Desperato : 又找到漏洞了WWW 等等我想要怎麼補qw q 06/16 00:18
※ 編輯: Desperato (140.112.25.105), 06/16/2017 00:49:24
2F:推 cuttlefish : 讚 原來我應開始猜錯方向了 難怪做不出來XD 06/16 07:06







like.gif 您可能會有興趣的文章
icon.png[問題/行為] 貓晚上進房間會不會有憋尿問題
icon.pngRe: [閒聊] 選了錯誤的女孩成為魔法少女 XDDDDDDDDDD
icon.png[正妹] 瑞典 一張
icon.png[心得] EMS高領長版毛衣.墨小樓MC1002
icon.png[分享] 丹龍隔熱紙GE55+33+22
icon.png[問題] 清洗洗衣機
icon.png[尋物] 窗台下的空間
icon.png[閒聊] 双極の女神1 木魔爵
icon.png[售車] 新竹 1997 march 1297cc 白色 四門
icon.png[討論] 能從照片感受到攝影者心情嗎
icon.png[狂賀] 賀賀賀賀 賀!島村卯月!總選舉NO.1
icon.png[難過] 羨慕白皮膚的女生
icon.png閱讀文章
icon.png[黑特]
icon.png[問題] SBK S1安裝於安全帽位置
icon.png[分享] 舊woo100絕版開箱!!
icon.pngRe: [無言] 關於小包衛生紙
icon.png[開箱] E5-2683V3 RX480Strix 快睿C1 簡單測試
icon.png[心得] 蒼の海賊龍 地獄 執行者16PT
icon.png[售車] 1999年Virage iO 1.8EXi
icon.png[心得] 挑戰33 LV10 獅子座pt solo
icon.png[閒聊] 手把手教你不被桶之新手主購教學
icon.png[分享] Civic Type R 量產版官方照無預警流出
icon.png[售車] Golf 4 2.0 銀色 自排
icon.png[出售] Graco提籃汽座(有底座)2000元誠可議
icon.png[問題] 請問補牙材質掉了還能再補嗎?(台中半年內
icon.png[問題] 44th 單曲 生寫竟然都給重複的啊啊!
icon.png[心得] 華南紅卡/icash 核卡
icon.png[問題] 拔牙矯正這樣正常嗎
icon.png[贈送] 老莫高業 初業 102年版
icon.png[情報] 三大行動支付 本季掀戰火
icon.png[寶寶] 博客來Amos水蠟筆5/1特價五折
icon.pngRe: [心得] 新鮮人一些面試分享
icon.png[心得] 蒼の海賊龍 地獄 麒麟25PT
icon.pngRe: [閒聊] (君の名は。雷慎入) 君名二創漫畫翻譯
icon.pngRe: [閒聊] OGN中場影片:失蹤人口局 (英文字幕)
icon.png[問題] 台灣大哥大4G訊號差
icon.png[出售] [全國]全新千尋侘草LED燈, 水草

請輸入看板名稱,例如:BuyTogether 或 站內搜尋

TOP