[其他] 離散兩題

[LiquidTLO (俊偉)]

題目1:https://imgur.com/a/bwIe3cc
不需要知道(a)(b)(c)部分
跟(d)(e)無關
(d)部分我有證出後半段
想問要如何證明前半段
Hamming distance between any two codewords
in RS[5,3] is at least 3
(e)部分沒什麼想法
題目的max Hamming distance = m-n+1是typo
應該是min Hamming distance = m-n+1

題目2:https://imgur.com/a/pJud5MX
題目裡的Maru還沒開始比
他贏第一場就拿1分
之後贏第i場就拿i分
(a)部分沒甚麼問題
(b)部分
我的想法是把分數i∈{1,2,...,10}
看作x_1+2x_2+3x_3+...+10x_10 > 27
0 <= x_i <= 1
但是不知道怎麼解含係數!= 1的不等式
我只解過x_1+x_2+...x_n = k這種的

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.224.187.128 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1602147303.A.1B1.html
→ hwanger     : 讓F是指定的finite field 給定u1,u2在F^3中 並令P1,
→ hwanger     : P2為其相對應的polynomials 則Hamming distance為
→ hwanger     : ((P1-P2)(a0),(P1-P2)(a1),...,(P1-P2)(a5))的非零
→ hwanger     : 個數 注意到(P1-P2)是一個degree小於等於2的多項式
→ hwanger     : 所以最多兩個零根 故至少三個非零
→ hwanger     : 至於(e) 你的Decode(*)的定義或者所採用的演算法是
→ hwanger     : 啥? 因為一般的error correction code的decoding
→ hwanger     : function就是要滿足圖中的式子 並以此來找decode的
→ hwanger     : 算法 (一般來說 如果我們接收到錯誤的代碼C' 我們糾
→ hwanger     : 正錯誤的方法 就是去找Hamming distance最近的
→ hwanger     : codeword 再以此decording)
→ hwanger     : 至於題目2 我目前也沒有有效率的算法 不過可以用下
→ hwanger     : 列遞迴函數的方式解 令F(n,m)為"從1到n中至少取一個
→ hwanger     : 且其總和小於等於m"的方法數 則我們有
→ hwanger     : F(1,k)=1 for all k in N
→ hwanger     : when m>n, F(n,m)=F(n-1,m)+F(n-1,m-n)+1
→ hwanger     : when m=n, F(n,m)=F(n-1,m)+1
→ hwanger     : when m<n, F(n,m)=F(n-1,m)
→ hwanger     : 則所求為 1023-F(10,27) 至少可以跑程式 冏
→ hwanger     : 題目2的(b)根本不用上面這麼麻煩 XD 當我們從{1,2,
→ hwanger     : 3,...,10}中取一些數出來總和大於27時 剩下來的數總
→ hwanger     : 和就會小於等於27 反之亦然 也就是說我們可以在1024
→ hwanger     : 個子集合中兩兩湊對 所以總共有1024/2=512種方法數
→ hwanger     : 這裡湊對的方式就是子集合和他的補集
→ hwanger     : 所以27這個數字是特別挑過的 (28是1到55的中間)
→ LiquidTLO   : 對，我後來看到程式結果也想到這樣XD
推 hwanger     : XD 我也是
推 hwanger     : 這是個很好的警惕 先跑程式看看答案再說 XD