翻转硬币难题

pizza49

n个硬币摞成一摞，n个硬币原始状态从上到下都是正面朝上。翻转规则如下：第k次从最上面k个硬币整体翻转（注：不是逐一翻转，这k个看成整体），k以n为周期按上述规则重复翻转。问：1）证明存在某次翻转后n个硬币都是正面朝上（即返回原来状态）；2）求满足问题(1)的最小次数。
以1表示正面、0表示反面，则n=3的情况如下：111->011->011->001->101->101->010->110->000->111,最小次数是9。

补充内容 (2024-10-3 08:25):
q*n+k次(k<=n)按第k次规则翻转

yigo

令\(E_k\)为k阶单位矩阵，\(D_k\)为副对角线都是-1的k阶副对角矩阵，

题目即证明存在m使得：

\(E_n=\prod_{i=m,k=\mod(i,n)}^1  \begin{pmatrix}
D_k && O \\
O && E_{n-k}
\end{pmatrix}\)

不会！！！

用excel列举了n=1~9，需要翻转的次数依次是2,3,9,11,24,35,28,31,80，搜索了下序列是A089645

pizza49

yigo 发表于 2024-10-3 15:21
令\(E_k\)为k阶单位矩阵，\(D_k\)为副对角线都是-1的k阶副对角矩阵，

题目即证明存在m使得：

我明白意思了，你想用1,-1代替正反

pizza49

yigo 发表于 2024-10-3 15:21
令\(E_k\)为k阶单位矩阵，\(D_k\)为副对角线都是-1的k阶副对角矩阵，

题目即证明存在m使得：

其实不一定是最终是单位矩阵，也有可能是某个非单位的置换矩阵。题目应该难在这里，算到单位矩阵只是一个上界；即保证你式子的矩阵连乘首次遇到置换矩阵。

mathe

证明存在性还是比较容易的。但是计算最小次数比较困难。
我们把当前所有硬币状态和下一次翻转的方案组合看成局面的状态，显然这样状态数目是有限的，必然会出现重复现象。
又因为对于每个状态，它的前一个状态是唯一的，所以我们容易得到第一个出现重复的状态就是初始状态，这时所有硬币被翻转会正面朝上。