Re: [問卦] 學妹問我一題高中數學 (急線上等

看板Gossiping作者arrenwu (拉姆真可愛)時間5年前 (2020/09/16 06:18)推噓6(6推 0噓 3→)

留言9則, 5人參與討論串3/3 (看更多)

※ 引述《neiltsang (楚留香雞排)》之銘言： : 那麼也不算難啊其實過程的概念寫下來就好了只能說冗長吧 : 或就利用歸納法囉另一個答案: : 寫成二進位然後把第一位移到最後面這解我就真的不會這個問題要直接出手解決那當然是比較難假設n個人的時候，f(n)會活下來但可以先從簡單的例子看起，比如 n 偶數的時候，考慮 n = 10: 1,2,3,4,5,6,7,8,9,10 奇數會先把偶數殺光變成 1,3,5,7,9 然後又從1開始，所以從這邊可以看得出 f(n) = 2f(n/2)-1 if n is even 那n是奇數呢？考慮 n = 9 1,2,3,4,5,6,7,8,9 一樣奇數會把偶數殺光，變成 1,3,5,7,9 但注意的是最後那個奇數還沒有動作，所以下一輪會變成9開始幹活，等於是在問 9,1,3,5,7 這列如果開殺誰會活下來所以可以得到 f(n) = 2[ f( (n+1)/2)-2 mod (n+1)/2 ] +1 if n is odd 整理起來我們就有 f(1) = 1; for n>=2 we have f(n) = 2f(n/2)-1 if n is even 2[ f( (n+1)/2)-2 mod (n+1)/2 ] +1 if n is odd 從而我們就可以進而用數學歸納法證明：給定任何 2^n + k where n>=0 and 0<= k <= 2^n-1 我們都有 f(2^n+k) = 2k+1 -- 「上野的街道，就由我們Colors守護！」 @tochiro0830 https://i.imgur.com/tORmryZ.jpg

-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 71.198.27.180 (美國) ※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1600208313.A.45C.html

推

qa1122z

09/16 06:20, 5年前 , 1^F

09/16 06:20, 1^F

→

qa1122z

09/16 06:21, 5年前 , 2^F

09/16 06:21, 2^F

推

ntnnthree

09/16 06:25, 5年前 , 3^F

09/16 06:25, 3^F

後面部分就數學歸納法啊你是想要這部分的證明嗎？

推

ntnnthree

09/16 06:29, 5年前 , 4^F

09/16 06:29, 4^F

okok f(1), f(2) , f(3) 這個你可以輕鬆驗證。喔對了，我們還可以很簡單地用遞迴關係算出 f(2^n) = 1 for any n>=0 好，讓我們假設這結論對於 f(1) f(2) ..... 到 f(2^N-1) 都正確，下一部我們想要證明的是：對於 0<= k <= 2^(N+1)-1 上面那結論都還是正確的所以現在給你一個 2^(N+1) + k where 0<= k <= 2^(N+1)-1 考慮下列情況 (1) k = 2^(N+1)-1 (這是一個奇數) f(2^(N+1) + k) = f(2^(N+2)-1) = 2( f(2^(N+1))-2 mod 2^(N+1) ) +1 = 2( 1-2 mod 2^N ) +1 = 2(2^N-1) + 1 = 2^(N+1) - 1 = 2k +1 (2) k < 2^(N+1)-1 然後 k 是個偶數 f(2^(N+1) + k) = 2f(2^N+k/2) - 1 = 2( 2*k/2 +1) -1 (歸納假設) = 2k+1 (3) k < 2^(N+1)-1 然後 k 是個奇數 f(2^(N+1) + k) = 2( f(2^(N)+(k+1)/2 )-2 mod 2^(N)+(k+1)/2 ) +1 這情況下保證 (k+1)/2 <= 2^N-1 所以可以用歸納假設得到 = 2( 2*(k+1)/2+1-2 mod 2^(N)+(k+1)/2 ) +1 = 2( k ) +1 = 2k+1 這樣就完成歸納了

→

neiltsang

09/16 06:31, 5年前 , 5^F

09/16 06:31, 5^F

→

neiltsang

09/16 06:32, 5年前 , 6^F

09/16 06:32, 6^F

我不太清楚你的一直寫是啥意思，但我這邊寫的就是大家心中的數學歸納法喔 ※ 編輯: arrenwu (71.198.27.180 美國), 09/16/2020 06:47:01

推

ntnnthree

09/16 07:27, 5年前 , 7^F