翻硬币问题——数学建模.pdf

摘要摘要 对一摞 m 枚正面朝上的硬币进行翻面 第 k 次翻上面 k 枚硬币 k 1 2 3 m 翻完后再从最上面的硬币开始重复操作 问需经过多少次翻面可 以使所有硬币重新正面朝上 由于本问题问法存在异议 即两种翻面的方法 第一种 k 枚硬币作为整体 全部颠倒 即翻面的同时颠倒硬币顺序 第二种 每一枚硬币翻面后放回 不打 乱硬币顺序 本文将对两种观点进行探讨 得出结论 关键词关键词 翻硬币 二进制 数学归纳法 映射 以下针对第一种观点进行探讨 问题分析 事实上 任意一枚硬币当且仅当翻面为偶数次时才会重新正面朝上 那么问 题的本质就是翻面多少次时 所有硬币的翻面次数都为偶数次 问题求解 本次不采用数学归纳证明之 以直观的图形及表格论述 当硬币为三枚时 假设 A i 1 表示正面朝上 A i 0 表示反面朝上 表 1 三枚硬币的翻面状态 次数 硬币 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 当硬币为四枚时 假设 A i 1 表示正面朝上 A i 0 表示反面朝上 表 2 四枚硬币的翻面状态 次 数 硬币 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 映射关系 翻面次数 图 1 四枚硬币的状态循环 观察发现 在经历三轮循环 4 次 4 次 4 次 翻面后 所有硬币重新 回到初始状态的位置 并且翻面次数的奇偶性一致 在 m 4 时 三轮循环 后全部反面朝上 那么在之前的一次翻面时 必为全部正面朝上 也就是说 41 4 表 示 第 四 枚 硬 币 1 表 示 翻 面 次 数 在3 4 1 11k 时达到全部正面朝上 根据上面的例子我们有如下猜测 f m m枚硬币出现循环的次数 这是唯一由m以及翻面规则决定的 如 3 9 4 12ff 12 1 or 0 mii w m nx xxx x m n 其中 m枚硬币在经历n次 后的状态 那么简单推理可知 12 2 1 mi w mf mx xxx 其中 也 就是说翻面2 f m次后必然全部正面朝上 但是 对多个m考察后发现 1 f mf m在或者次时一般已经成立 这 取决于具体的映射关系 本文针对此映射关系即 f m的具体表达式只做简单探讨 1 1 尝试探求 f m的表达式 表 3 多枚硬币的单次循环后序列 m 位置 1 枚 2 枚 3 枚 4 枚 5 枚 6 枚 7 枚 8 枚 9 枚 10 枚 m 枚 一轮循环 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 根据其基本规律设计了如下图 2 的流程图 编程语言很简单 未附上 思路如下 首先输入硬币数m 指针 p 起始位置为 1 所指位置的值 V 为m 由于m的不同会导致 P V 1 的不同 因此分情况计算 V 1 的位置 p 然后将 P 的值赋予 V 计算 V P 的位置 此时仍需针对 V 的奇偶性确定 P 此后以此类推 直至 P 1 即 P 指向第一个位置 举例以说明之 当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 输出次数为 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 所需次数 2 3 9 11 24 35 28 31 对应 f m 1f m f m 1f m 1f m 1f m f m 1f m 理论上只需要知道一枚硬币翻面的次数即可判断 此处限于篇幅不加讨 论 但取 1f m f m或者的猜想是很可能的 但仍需深入分析 模型检验 当m 8 时 需要 1f m 31 次操作 输入 m p 1 v 2m i 0 m为偶数 P m 2 1 V 1 i 1 V p i i 1 P 1 V为偶数 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为偶数 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 翻面次数 50 60 70 80 18 36 54 72 4 3 2 1 映射关系 73 39 212 610 8 7 6 5 翻面次数 89 411 112 56 4 3 2 1 映射关系 57 414 615 316 8 7 6 5 翻面次数 711 218 813 114 4 3 2 1 映射关系 115 221 321 421 8 7 6 5 翻面次数 515 621 715 815 4 3 2 1 映射关系 经过简单的检验 大胆推测任意m枚硬币经过 f m或者 1f m 次翻面后 再次全部回到正面 其中 f m可以由上述流程图获得 以下针对第二种观点进行探讨 问题分析 硬币有两种状态 背面朝上和正面朝上 可以分别用二进制数 0 和 1 代表 0 代表反面朝上 1 代表正面朝上 第 k 次操作可以看做把后 k 位取反 用 A 代 表硬币的状态 A i 代表第 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 次翻面可以使所有硬币重新正面朝上 假设假设 对 m 枚硬币 操作 k 2m 时 A i 1 i 1 2 3 m 证明证明 m 1 时 显然 k 2 时 A1 1 假设成立 假设 m n n 1 时 k 2n 时 A i 1 i 1 2 3 n 即命题成立 当 m n 1 n 1 时 将第一枚硬币以下 n 枚硬币视为整体 操作 k n 1 时 处理完整摞硬币 此时 A n 1 进行了 n 1 次操作 第一枚硬币以下 n 枚硬币 即 A n A 1 处理了 n 次 此时进行处理至 k 2n 2 此时相当于上述操作重复 一次 即 A n 1 进行了 2n 2 次操作 第一枚硬币以下 n 枚硬币 即 A n A 1 处理了 2n 次 显然 A n 1 1 A i 1 i 1 2 3 n 总上诉述 由数学归纳法知 对 m 枚硬币 需要 2m 次翻面可以使所有硬币 重新正面朝上