翻硬幣問題——數(shù)學(xué)建模.pdf

摘要摘要 對一摞 m 枚正面朝上的硬幣進(jìn)行翻面 第 k 次翻上面 k 枚硬幣 k 1 2 3 m 翻完后再從最上面的硬幣開始重復(fù)操作 問需經(jīng)過多少次翻面可 以使所有硬幣重新正面朝上 由于本問題問法存在異議 即兩種翻面的方法 第一種 k 枚硬幣作為整體 全部顛倒 即翻面的同時顛倒硬幣順序 第二種 每一枚硬幣翻面后放回 不打 亂硬幣順序 本文將對兩種觀點(diǎn)進(jìn)行探討 得出結(jié)論 關(guān)鍵詞關(guān)鍵詞 翻硬幣 二進(jìn)制 數(shù)學(xué)歸納法 映射 以下針對第一種觀點(diǎn)進(jìn)行探討 問題分析 事實(shí)上 任意一枚硬幣當(dāng)且僅當(dāng)翻面為偶數(shù)次時才會重新正面朝上 那么問 題的本質(zhì)就是翻面多少次時 所有硬幣的翻面次數(shù)都為偶數(shù)次 問題求解 本次不采用數(shù)學(xué)歸納證明之 以直觀的圖形及表格論述 當(dāng)硬幣為三枚時 假設(shè) A i 1 表示正面朝上 A i 0 表示反面朝上 表 1 三枚硬幣的翻面狀態(tài) 次數(shù) 硬幣 0 1 2 3 順 序 4 5 6 順 序 7 8 9 順 序 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0 1 當(dāng)硬幣為四枚時 假設(shè) A i 1 表示正面朝上 A i 0 表示反面朝上 表 2 四枚硬幣的翻面狀態(tài) 次 數(shù) 硬幣 0 1 2 3 4 順 序 5 6 7 8 順 序 9 10 11 12 順 序 1 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 10 20 30 40 41 23 14 32 4 3 2 1 33 26 45 16 4 3 2 1 17 29 37 47 4 3 2 1 映射關(guān)系 翻面次數(shù) 圖 1 四枚硬幣的狀態(tài)循環(huán) 觀察發(fā)現(xiàn) 在經(jīng)歷三輪循環(huán) 4 次 4 次 4 次 翻面后 所有硬幣重新 回到初始狀態(tài)的位置 并且翻面次數(shù)的奇偶性一致 在 m 4 時 三輪循環(huán) 后全部反面朝上 那么在之前的一次翻面時 必為全部正面朝上 也就是說 41 4 表 示 第 四 枚 硬 幣 1 表 示 翻 面 次 數(shù) 在3 4 1 11k 時達(dá)到全部正面朝上 根據(jù)上面的例子我們有如下猜測 f m m枚硬幣出現(xiàn)循環(huán)的次數(shù) 這是唯一由m以及翻面規(guī)則決定的 如 3 9 4 12ff 12 1 or 0 mii w m nx xxx x m n 其中 m枚硬幣在經(jīng)歷n次 后的狀態(tài) 那么簡單推理可知 12 2 1 mi w mf mx xxx 其中 也 就是說翻面2 f m次后必然全部正面朝上 但是 對多個m考察后發(fā)現(xiàn) 1 f mf m在或者次時一般已經(jīng)成立 這 取決于具體的映射關(guān)系 本文針對此映射關(guān)系即 f m的具體表達(dá)式只做簡單探討 1 1 嘗試探求 f m的表達(dá)式 表 3 多枚硬幣的單次循環(huán)后序列 m 位置 1 枚 2 枚 3 枚 4 枚 5 枚 6 枚 7 枚 8 枚 9 枚 10 枚 m 枚 一輪循環(huán) m 次 后的序列 1 1 2 3 4 5 6 7 8 9 10 m 2 1 1 2 3 4 5 6 7 8 m 2 3 2 1 1 2 3 4 5 6 m 4 4 3 2 1 1 2 3 4 5 4 3 2 1 1 2 6 5 4 3 2 1 1 7 6 5 4 3 8 7 6 5 9 8 7 m 5 10 9 m 3 m 1 f mm 1 2 3 3 5 6 4 4 9 6 根據(jù)其基本規(guī)律設(shè)計了如下圖 2 的流程圖 編程語言很簡單 未附上 思路如下 首先輸入硬幣數(shù)m 指針 p 起始位置為 1 所指位置的值 V 為m 由于m的不同會導(dǎo)致 P V 1 的不同 因此分情況計算 V 1 的位置 p 然后將 P 的值賦予 V 計算 V P 的位置 此時仍需針對 V 的奇偶性確定 P 此后以此類推 直至 P 1 即 P 指向第一個位置 舉例以說明之 當(dāng)m 6 起始 P 1 V 6 計算的 V 1 的位置 P 4 i 1 賦值 V P 4 i 2 計算 V 4 的位置 P 2 賦值 V P 2 i 3 計算 V 2 的位置 P 3 賦值 V P 3 i 4 計算 V 3 的位置 P 5 賦值 V P 5 i 5 計算 V 5 的位置 P 6 賦值 V P 6 i 6 計算 V 6 的位置 P 1 輸出次數(shù)為 i 6 圖 3 分析流程圖 2 嘗試探求何時取 1 f mf m或者 表 4 取 1f m或者 f m的簡單分析 m 1 2 3 4 5 6 7 8 f mm 2 2 3 3 5 6 4 4 f m 2 4 9 12 25 36 28 32 所需次數(shù) 2 3 9 11 24 35 28 31 對應(yīng) f m 1f m f m 1f m 1f m 1f m f m 1f m 理論上只需要知道一枚硬幣翻面的次數(shù)即可判斷 此處限于篇幅不加討 論 但取 1f m f m或者的猜想是很可能的 但仍需深入分析 模型檢驗(yàn) 當(dāng)m 8 時 需要 1f m 31 次操作 輸入 m p 1 v 2m i 0 m為偶數(shù) P m 2 1 V 1 i 1 V p i i 1 P 1 V為偶數(shù) P m v 2 2P m v 1 2 N Y N Y 輸出i Y P m 1 2 V 1 i 1 V p i i 1 P 1 V為偶數(shù) P m v 2 2P m v 1 2 N N Y Y N 10 20 30 40 81 63 45 27 8 7 6 5 翻面次數(shù) 50 60 70 80 18 36 54 72 4 3 2 1 映射關(guān)系 73 39 212 610 8 7 6 5 翻面次數(shù) 89 411 112 56 4 3 2 1 映射關(guān)系 57 414 615 316 8 7 6 5 翻面次數(shù) 711 218 813 114 4 3 2 1 映射關(guān)系 115 221 321 421 8 7 6 5 翻面次數(shù) 515 621 715 815 4 3 2 1 映射關(guān)系 經(jīng)過簡單的檢驗(yàn) 大膽推測任意m枚硬幣經(jīng)過 f m或者 1f m 次翻面后 再次全部回到正面 其中 f m可以由上述流程圖獲得 以下針對第二種觀點(diǎn)進(jìn)行探討 問題分析 硬幣有兩種狀態(tài) 背面朝上和正面朝上 可以分別用二進(jìn)制數(shù) 0 和 1 代表 0 代表反面朝上 1 代表正面朝上 第 k 次操作可以看做把后 k 位取反 用 A 代 表硬幣的狀態(tài) A i 代表第 i 枚硬幣的狀態(tài) 問題求解 m 1 時 顯然需要 2 次操作 m 2時 k 0 A 11 k 1 A 10 k 2 A 01 k 3 A 00 k 4 A 11 需要4次操作 m 3 時 k 0 A 111 k 1 A 110 k 2 A 101 k 3 A 010 k 4 A 011 k 5 A 000 k 6 A 111 需要 6 次操作 猜想猜想 對 m 枚硬幣 需要 2m 次翻面可以使所有硬幣重新正面朝上 假設(shè)假設(shè) 對 m 枚硬幣 操作 k 2m 時 A i 1 i 1 2 3 m 證明證明 m 1 時 顯然 k 2 時 A1 1 假設(shè)成立 假設(shè) m n n 1 時 k 2n 時 A i 1 i 1 2 3 n 即命題成立 當(dāng) m n 1 n 1 時 將第一枚硬幣以下 n 枚硬幣視為整體 操作 k n 1 時 處理完整摞硬幣 此時 A n 1 進(jìn)行了 n 1 次操作 第一枚硬幣以下 n 枚硬幣 即 A n A 1 處理了 n 次 此時進(jìn)行處理至 k 2n 2 此時相當(dāng)于上述操作重復(fù) 一次 即 A n 1 進(jìn)行了 2n 2 次操作 第一枚硬幣以下 n 枚硬幣 即 A n A 1 處理了 2n 次 顯然 A n 1 1 A i 1 i 1 2 3 n 總上訴述 由數(shù)學(xué)歸納法知 對 m 枚硬幣 需要 2m 次翻面可以使所有硬幣 重新正面朝上