※ 引述《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