奥数题求助

同学在群里发的，被小朋友的奥数题难住了

你被蒙住了双眼，什么都看不见。你的正前方有一张方桌，桌子的四个角上各有一枚硬币。有一个机器人根据你的指令操作硬币。你可以发出指令让机器人翻转任何你指定位置的硬币。例如：翻转左上和右下两枚硬币；翻转全部四枚硬币。机器人每次按你的指令操作完成后，桌子会随机顺时针或逆时针旋转90、180、270、360度，然后等待你下
一次指令。当四枚硬币全部正面朝上时，机器人立即发出声音通知你(其他任何时候它
不会发声），游戏结束。
问题：你可以通过有限次指令保证使得游戏结束吗？若能，请给出你的指令步骤。若不能，请证明。

想起这道题怎么做了。

如果硬币对角状态相同，三步以内结束。

如果没有声音：
第一步，全部翻转。
如果没有声音：
第二步：左上和右下翻转。
如果没有声音：
第三步：全部翻转

如果三步以内没有结束，那么就先翻转左上，然后重复上面的三步。

如果过了三步还是没有结束，那就翻转左上和右上，然后重复那三步。

多谢，我转给朋友研究下

【 在 SLE (嗯，就这样定了。) 的大作中提到: 】
: 想起这道题怎么做了。
: 如果硬币对角状态相同，三步以内结束。
: 如果没有声音：
: 第一步，全部翻转。
: 如果没有声音：
: 第二步：左上和右下翻转。
: 如果没有声音：
: 第三步：全部翻转
: 如果三步以内没有结束，那么就先翻转左上，然后重复上面的三步。
: 如果过了三步还是没有结束，那就翻转左上和右上，然后重复那三步。

部分解：

初始情况 （1 ）有两个相邻朝下 另两个朝上

发出如下指令可以保证达到四个全朝上
翻相邻两个
翻对角两个
翻四个
翻对角两个
翻四个

如果到这里没胜利 说明初始状态 不是两个相邻的朝下

而且 此时的状态 等于起始状态翻了相邻两个

如果起始状态是（2）对角两个朝上 那翻了任意两个相邻棋子之后 会变成相邻两个
棋子朝上

所以重复上面五条指令一次 肯定可以达到四个朝上

这样 只要开始是2上2下 10条指令可解

如果这时还没成功 说明开始是3对1 而这时相当于随机翻了其中两个 三对一 随机翻两个 结果还是三对一 所以这时随机翻一个 会产生四比0或者2比2 那就再先全
翻一次 没成功的话 重复上面两个5个指令序列 应该就可以了

（补充修改 ： 开始也可能是全朝下 所以在所有指令之前加一步全翻即可）

【 在 Huangchong (净坛使者) 的大作中提到: 】
: 部分解：
: 初始情况 （1 ）有两个相邻朝下 另两个朝上
: 发出如下指令可以保证达到四个全朝上
: 翻相邻两个
: 翻对角两个
: 翻四个
: 翻对角两个
: 翻四个
: 如果到这里没胜利 说明初始状态 不是两个相邻的朝下
: 而且 此时的状态 等于起始状态翻了相邻两个
: ...................

这个解法好

【 在 SLE (嗯，就这样定了。) 的大作中提到: 】
: 想起这道题怎么做了。
: 如果硬币对角状态相同，三步以内结束。
: 如果没有声音：
: 第一步，全部翻转。
: 如果没有声音：
: 第二步：左上和右下翻转。
: 如果没有声音：
: 第三步：全部翻转
: 如果三步以内没有结束，那么就先翻转左上，然后重复上面的三步。
: 如果过了三步还是没有结束，那就翻转左上和右上，然后重复那三步。

好像后两种情况的讨论有一些纰漏。修改一下。
开始三步不变。
如果没有结束，就翻转左上和右上，然后重复那三步。
如果还是没有结束，就翻转任何一个，再重复开始三步。
如果还是没有结束，就翻转左上和右上，然后重复开始三步。

【 在 SLE (嗯，就这样定了。) 的大作中提到: 】
: 想起这道题怎么做了。
: 如果硬币对角状态相同，三步以内结束。
: 如果没有声音：
: 第一步，全部翻转。
: 如果没有声音：
: 第二步：左上和右下翻转。
: 如果没有声音：
: 第三步：全部翻转
: 如果三步以内没有结束，那么就先翻转左上，然后重复上面的三步。
: 如果过了三步还是没有结束，那就翻转左上和右上，然后重复那三步。

这道题有些意思，稍微想了一下。
本质上，是一个有穷自动机的问题。在信息不完备的情况下，如何能够到达特定的状态。

一、如何定义状态。
4个硬币是16状态，如果考虑旋转那么一共是64状态。一开始我想以64状态分析，后来
发现没有必要。
现将硬币从左上开始，按顺时针顺序，构成状态，显见有0000-1111共16状态。

二、状态转移
我方的操作其实可以在任意子【两种状态间转移。但因为自身状态未知，这块不好入手。所以先从不可控的机器随机操作开始。
机器的所有操作是旋转，对应的比特状态变化是循环移位操作。

以图的方式来构建，那么将机器操作作为节点间的连接（图中红线），那么整个状态图可以分为几个子图

S0: 1111
S1: 0000
S2: 1010, 0101
S3: 1100, 1001, 0011, 0110
S4.1: 0001, 0010, 0100, 1000
S4.2: 1110, 1101, 1011, 0111

三、策略分析
感谢SLE大佬的分析，非常有启发。本来我的策略是尝试构建子操作集，在特定子集中
可以保证跃迁，从而能确保遍历，实现1111状态。看到SLE关于对角的分析后觉得很有
道理，想归纳出策略，就继续再走了几步，大致就走通了。

引理1：机器操作可且仅可跃迁至当前子图中的任一状态。例如当前处于1001，那么机
器操作后，可能是S3中的任一状态，但不会是S3以外的状态

由此可见，用户操作（蓝线表示）以实现子图间跃迁，机器操作（红线表示）实现子图内跃迁。我们需要寻找最有共性的操作，以确保路径可控。

易知：
S1 -> S0:
通过操作1111（全翻转实现）

S2 -> S0:
1010操作可以使S1跃迁至S1或S0
所以，综合操作步骤为：1010 -> 1111

(S1 + S2) -> S0:
1111操作使S2依然保持在S2状态，因此
步骤为：1111 -> 1010 -> 1111

S3 -> S0:
在S3时选择1100操作，必然跃迁至S0/S1/S2
所以易知，步骤为：
1100 -> 1111 -> 1010 -> 1111

(S1 + S2 + S3) -> S0:
需要注意1100同样会让S1/S2跃迁至S3
1111、1010操作让S3仍然保持S3：
所以一个简单的策略就是叠加（也许不是最优）：
1111 -> 1010 -> 1111 -> 1100 -> 1111 -> 1010 -> 1111
前3条指令解决S1/S2，如果是S3的话，保持在S3
第4条指令跃迁至S0/S1/S2

合并S4.1/S4.2为S4
S4 -> S0:
指令1000可让S4跃迁至S0/S1/S2/S3

(S1 + S2 + S3 + S4) -> S0:
指令1111、1010、1100让S4仍然保持S4
所以依然可采用叠加策略。

综上，最终依次执行指令集如下
1)0000 S0的情况
2)1111 S1的情况
3)1010 -> 1111 S2的情况
4)1100 -> 1111 -> 1010 -> 1111 S3的情况
5)1000 -> 1111 -> 1010 -> 1111 -> 1100 -> 1111 -> 1010 -> 1111

显见，无唯一解。给出的解可能不是最少步骤的最优解，但满足题目要求。以上。

【 在 weierstrass (没昵称) 的大作中提到: 】
: 同学在群里发的，被小朋友的奥数题难住了
: 你被蒙住了双眼，什么都看不见。你的正前方有一张方桌，桌子的四个角上各有一枚硬
: 币。有一个机器人根据你的指令操作硬币。你可以发出指令让机器人翻转任何你指定位
: 置的硬币。例如：翻转左上和右下两枚硬币；翻转全部四枚硬币。机器人每次按你的指
: 令操作完成后，桌子会随机顺时针或逆时针旋转90、180、270、360度，然后等待你下
: 一次指令。当四枚硬币全部正面朝上时，机器人立即发出声音通知你(其他任何时候它
: 不会发声），游戏结束。
: 问题：你可以通过有限次指令保证使得游戏结束吗？若能，请给出你的指令步骤。若不
: 能，请证明。

这个是对的。

两对对角线的就只有3种状态。
case 1. 两对对角线都同状态， 第1个3步内成功。
case 2. 两对对角线都不同状态，翻转相邻两个，变成case 1 .

case 3. 一对相同，一对不同，翻转任何一个， 变成，case 1或case 2。

最多15次必定成功


【 在 SLE (嗯，就这样定了。) 的大作中提到: 】
: 好像后两种情况的讨论有一些纰漏。修改一下。
: 开始三步不变。
: 如果没有结束，就翻转左上和右上，然后重复那三步。
: 如果还是没有结束，就翻转任何一个，再重复开始三步。
: 如果还是没有结束，就翻转左上和右上，然后重复开始三步。

如果初始状态是全部朝上,而机器人不提醒。
那就要在开始时加一次保持原状你指令。
这样最多16个指令完成

【 在 llaalways (熊大) 的大作中提到: 】
: 这个是对的。
:
: 两对对角线的就只有3种状态。
: case 1. 两对对角线都同状态， 第1个3步内成功。
: case 2. 两对对角线都不同状态，翻转相邻两个，变成case 1 .
:
: case 3. 一对相同，一对不同，翻转任何一个， 变成，case 1或case 2。
:
: 最多15次必定成功
:
:
: 【 在 SLE (嗯，就这样定了。) 的大作中提到: 】
: : 好像后两种情况的讨论有一些纰漏。修改一下。
: : 开始三步不变。
: : 如果没有结束，就翻转左上和右上，然后重复那三步。
: : 如果还是没有结束，就翻转任何一个，再重复开始三步。
: : 如果还是没有结束，就翻转左上和右上，然后重复开始三步。