※ 引述《FAlin (FA（バルシェ應援）)》之銘言： : 1. Prove that for any two positive integers k , n there exist positive : integers m_1 , m_2 , ... , m_k such that : 2^k - 1 1 1 1 : 1 + ------- = ( 1 + --- )( 1 + --- )...( 1 + --- ) . : n m_1 m_2 m_k 怕看到其他解答會受到影響 所以沒看直接回一篇 如果解答有重複請見諒 (防雷頁) 想法: 考慮一嚴格遞增數列 令 a_1 = n , a_(k+1) = ( n + 2^k - 1 ) 右邊想辦法配成 ( a_2 / a_1 ) * ( a_3 / a_2 ) ... ( a_(k+1) / a_k ) 然後各項約分後要成功變成 ( ( m_i + 1 ) / m_i ) 關鍵: a_(k+1) - a_1 = 2^k - 1 = 1 + 2 + 4 + ... + 2^(k-1) 剛好有k個數 可以拿來分配給 ( a_(i+1) - a_i ) , i = 1,2,...,k 解法: 考慮一嚴格遞增數列 <a_i> 令 a_1 = n , a_(k+1) = ( n + 2^k - 1 ) 令集合 P = { x | x為1~k之間的整數 , 且 a_(k+1) 寫成二進位的第x位為1 } Q = { x | x為1~k之間的整數 , 且 a_(k+1) 寫成二進位的第x位為0 } 將 P 當中的元素遞增排序 p_1 , p_2 , ... p_s Q 當中的元素遞增排序 q_1 , q_2 , ... q_t (顯然s+t=k) 則令 a_k = a_(k+1) - 2^(p_1 - 1) , a_(k-1) = a_k - 2^(p_2 - 1) ...(依序減下去) , a_(k-s+1) = a_(k-s+2) - 2^(p_s - 1) 然後 a_(k-s) = a_t = a_(t+1) - 2^(q_t - 1) , a_(t-1) = a_t - 2^(q_(t-1) - 1) , ... a_2 = a_3 - 2^(q_2 - 1) , a_1 = a_2 - 2^(q_1 - 1) 首先 P 跟 Q 當中的元素合起來是正整數 1~k ,所以這樣一路減下來 1, 2, ... 2^(k-1) 各減一次 a_1 會回到 n 無誤 接著檢查 a_(i+1) / a_i 約分到最簡的狀況 : (I) 若 i 介於 k 到 k-s+1 之間, 因為 a_(i+1) 恰為 2^(p_(k-i+1) - 1) 的倍數, 而非 2^(p_(k-i+1)) 的倍數 所以 a_(i+1) / a_i 上下約掉 2^(p_(k-i+1) - 1) 後, 分子恰比分母多1 (II) 若 i 介於 k-s 到 1 之間, 也就是 t 到 1 之間 因為 a_i 恰為 2^(q_i - 1) 的倍數, 而非 2^(q_i) 的倍數 所以 a_(i+1) / a_i 上下約掉 2^(q_i - 1) 後, 分子也恰比分母多1 故依此構造法 對於所有的 k 跟 n, 相對應的 m_1 , ... , m_k 存在 # --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.194.225.84