最少翻动硬币的次数

manthanein

给定n个硬币，都是正面向上，规定每次翻动n-1个硬币，最少翻动多少次可以使所有硬币都正面向下？

自己观察了一下：
当n是奇数时，似乎不可能办到。
当n是偶数时，规定第m次除了第m号硬币，其他都翻动，这样要翻n次。

mathe

结论没错，很显然

manthanein

mathe 发表于 2015-11-15 18:54
结论没错，很显然

能严格证明吗？

mathe

第一问很简单，奇偶性可得.第二问可用线性代数理论证明

kastin

楼主的猜想是正确的。
对原问题进行代数抽象为如下运算
定义:
算子A——翻转其中n-1个硬币。
算子B——把所有的硬币全部翻面。
算子C——翻转某一个硬币。
算子I——不做任何操作。
定义算子之间的乘法 `*` 表示一次复合作用。

问题便转化为“至少多少个A作用在n个硬币上才能与一次B作用在n个硬币上等价？”换成符号表达就是$$\mathrm{Minimize}\;k\\
\mathrm{s.t.}\;\;A_1*A_2*A_3*\cdots*A_k=B\tag{1}$$
注意到 `A` 和 `C`是对偶的，即 `A=B*C`，而算子 `B` 和 `C` 是可交换的，于是`A_1*A_2*A_3*\cdots*A_k=(B*C_1)*(B*C_2)*\cdots*(B*C_k)=B^k*(C_1*C_2*\cdots*C_k)`.
显然`B^{2p+1}=B,\,B^{2p}=I\;(p=0,1,2,3,\cdots)`，于是要满足 `(1)` 中的条件，只有两种可能：

a) `C_1*C_2*\cdots*C_k=I` 且 `k` 为奇数。
由于 `C_s*C_s=I`，因此 `k` 必须为偶数，显然不可能，舍去。

b) `C_1*C_2*\cdots*C_k=B`，且`k`为偶数。
这个是可能的，只需要 `k\geqslant n` 且保证每个硬币总共被翻奇数次即可。因此最小情形是保证 `k=n`，且 `n` 为偶数(该情形下`C_1,C_2,\cdots`互不等价，即每个硬币只翻动一次)。

于是原问题一种最简单的翻动方法就是，“当且仅当n为偶数时，n个全部朝上的硬币进行至少翻动n次（第m次除了第m号硬币不动，其他都翻动）便能使得全部硬币朝下”。
当然还有其他的方法，只要保证每次剩下未翻动的硬币遍历所有n个硬币各一次即可，不必保证顺序。

对于这种类型的题目，这里讨论了一般情形：
http://www.guokr.com/post/643485/
总结一下就是：