Research Space for Linear Algebra & Discrete Mathematics
第一題是證有理數a.只要把(p+q)/2就是介在這兩者之間就是r了b.接下來要證無限多有理數p+(q-p)/n p+2(q-p)/n p+3(q-p)/n....依此類推用矛盾證法 不存在無限多個有理數則n有限 改成p+(q-p)/(n+1) 也是有理數 造成矛盾
2. (a) 這個問題叫做 Josephus problem, 舉個例子來說, 假設 n=8, 一開始我們會先把偶數的item都刪掉, 再刪完一輪後, 若想要觀察再繼續做下去最後會剩下哪一個item, 那我們可以去query若對剩下的items 1,3,5,7 進行同樣的process最後會剩下誰, 而query的方法就相當於是問假設今天有 4 個 item 1,2,3,4 時所剩餘的item會是第幾個, 再把那一個的編號抓出來對應到n=8時的編號即可, 也就是說因為 1 = 2*1 - 13 = 2*2 - 15 = 2*3 - 17 = 2*4 - 1且 f(4)=1, 所以當只剩1,3,5,7時一定是1,3,5,7的第一個item最後會留下, 而在這裡第一個item剛好就是 1, 因為 2*f(4)-1=1 所以in general, 若把總數有偶數個item與有奇數個的情形分開來討論, 可歸納出:f(2n) = 2f(n)-1, for n≧1f(2n+1) = 2f(n)+1, for n≧1f(1)=1(b) 至於要如何導出closed form, 你可以往 n 的二進位表示的方向去想, 把 n 寫成 n=2^m+l 的形式去觀察, 最後用歸納法可證 f(2^m+l)=2l+1, for m≧0, 0≦l<2^m
謝謝AIdrifter~助教，看不懂你寫的耶= ="可以在淺顯一點嗎..XD
再說明一個 n=6 的例子, 不過建議你也可以自己先用例子try看看, 因為要解一個問題我覺得要自己試過後才會更有感覺, 也更能理解別人的想法是甚麼你可以把 1~6 這八個數字依序繞成一個cycle來看, 然後順時針每往下數兩個還沒被刪的item就把他刪掉, process 的過程如下:1 2 3 4 5 6- x - x - x在第一輪把偶數都刪掉後, 會剩下 1,3,5 共 3 個item, 所以我們會想要知道那當只有 3 個 item 時, 也就是 f(3) 會是什麼, 因為如果知道當 n=3 時最後剩下的會是第幾個, 結果就差不多都出來了而當 n=3 時, process 如下:1 2 3| 1 3- x -| x 最後剩下來的是 3, 所以 f(3)=3現在要把 f(3)=3 的結果對應回去 n=6 時的情形, 因為 f(3)=3 告訴我們當有三個item時是第 3 個會留下, 所以 1,3,5 會留下來的是 5, 所以 f(6)=5, 而 f(2n)=2f(n)-1 就是在做上面這件事, 也就是把那個對應回去的原編號用式子推出來而已, i.e., 2*3-1=5, 所以得到 f(6)=5完整的跑一次來驗證一下結果:1 2 3 4 5 6| 1 3 5| 1 5- x - x - x| - x -| x
喔喔，這樣我了解了。原來要將sequence看成"cycle"來解就比較明顯了。大約帶了2,3,4,5,6就可以得出助教給的conclusion~感謝！
張貼留言
5 則留言:
第一題是證有理數
a.只要把(p+q)/2就是介在這兩者之間就是r了
b.接下來要證無限多有理數
p+(q-p)/n p+2(q-p)/n p+3(q-p)/n....依此類推
用矛盾證法 不存在無限多個有理數
則n有限 改成p+(q-p)/(n+1) 也是有理數 造成矛盾
2. (a) 這個問題叫做 Josephus problem, 舉個例子來說, 假設 n=8, 一開始我們會先把偶數的item都刪掉, 再刪完一輪後, 若想要觀察再繼續做下去最後會剩下哪一個item, 那我們可以去query若對剩下的items 1,3,5,7 進行同樣的process最後會剩下誰, 而query的方法就相當於是問假設今天有 4 個 item 1,2,3,4 時所剩餘的item會是第幾個, 再把那一個的編號抓出來對應到n=8時的編號即可, 也就是說因為
1 = 2*1 - 1
3 = 2*2 - 1
5 = 2*3 - 1
7 = 2*4 - 1
且 f(4)=1, 所以當只剩1,3,5,7時一定是1,3,5,7的第一個item最後會留下, 而在這裡第一個item剛好就是 1, 因為 2*f(4)-1=1
所以in general, 若把總數有偶數個item與有奇數個的情形分開來討論, 可歸納出:
f(2n) = 2f(n)-1, for n≧1
f(2n+1) = 2f(n)+1, for n≧1
f(1)=1
(b) 至於要如何導出closed form, 你可以往 n 的二進位表示的方向去想, 把 n 寫成 n=2^m+l 的形式去觀察, 最後用歸納法可證 f(2^m+l)=2l+1, for m≧0, 0≦l<2^m
謝謝AIdrifter~
助教，看不懂你寫的耶= ="
可以在淺顯一點嗎..XD
再說明一個 n=6 的例子, 不過建議你也可以自己先用例子try看看, 因為要解一個問題我覺得要自己試過後才會更有感覺, 也更能理解別人的想法是甚麼
你可以把 1~6 這八個數字依序繞成一個cycle來看, 然後順時針每往下數兩個還沒被刪的item就把他刪掉, process 的過程如下:
1 2 3 4 5 6
- x - x - x
在第一輪把偶數都刪掉後, 會剩下 1,3,5 共 3 個item, 所以我們會想要知道那當只有 3 個 item 時, 也就是 f(3) 會是什麼, 因為如果知道當 n=3 時最後剩下的會是第幾個, 結果就差不多都出來了
而當 n=3 時, process 如下:
1 2 3| 1 3
- x -| x
最後剩下來的是 3, 所以 f(3)=3
現在要把 f(3)=3 的結果對應回去 n=6 時的情形, 因為 f(3)=3 告訴我們當有三個item時是第 3 個會留下, 所以 1,3,5 會留下來的是 5, 所以 f(6)=5, 而 f(2n)=2f(n)-1 就是在做上面這件事, 也就是把那個對應回去的原編號用式子推出來而已, i.e., 2*3-1=5, 所以得到 f(6)=5
完整的跑一次來驗證一下結果:
1 2 3 4 5 6| 1 3 5| 1 5
- x - x - x| - x -| x
喔喔，這樣我了解了。
原來要將sequence看成"cycle"來解就比較明顯了。大約帶了2,3,4,5,6就可以得出助教給的conclusion~感謝！
張貼留言