数学研发论坛

 找回密码
 欢迎注册
查看: 229|回复: 29

[讨论] 最少取反几次

[复制链接]
发表于 2020-9-10 23:07:14 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
本帖最后由 aimisiyou 于 2020-9-10 23:08 编辑

题目如图。若矩阵为
1011010
0110101
0010111
1010011
最少几次操作使得都变成0?
123.jpg
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-9-10 23:16:56 | 显示全部楼层
是否先要判断初始状态能否满足达到全部熄灭的要求?还是说对于任意初始状态,经过有限次操作,都能使得所有灯都能熄灭?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-9-11 00:45:29 | 显示全部楼层
aimisiyou 发表于 2020-9-10 23:16
是否先要判断初始状态能否满足达到全部熄灭的要求?还是说对于任意初始状态,经过有限次操作,都能使得所有 ...

考虑1x2只有一盏灯亮的情形,你的“是否先要判断初始状态能否满足达到全部熄灭的要求”这一问题是不证自明的。
这题最难的地方就是遍历第一行的全部可能状态然后对其余行解方程组
解方程组的意思是,如果我们知道顶部所在行不需要进行任何操作,那么顶部亮灯的列就是我们需要操作的下一行开关所在列。
这样搜起来,在n<16的情况下最多搜65536种可能(或许还可以化简但我懒得化了,反正够快)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-9-11 00:54:36 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-9-11 01:10 编辑
.·.·. 发表于 2020-9-11 00:45
考虑1x2只有一盏灯亮的情形,你的“是否先要判断初始状态能否满足达到全部熄灭的要求”这一问题是不证自 ...


1*2的情况太明显了,复杂一点怎么判断呢?如3*3只有左上角一灯是亮的初始状态,好像也是不能满足的。有没有通用的判断法则?先来简单的,m*n只有左上角一灯是亮的,m、n满足什么条件使得初始状态经变换可以全部为0。(至少1*1、1*3、2*2是满足的。)
089.png

点评

枚举第一行的全部状态是指初始状态变换后第一行所能得到的全部状态么?解方程也很繁琐,有无简洁判断法则?  发表于 2020-9-11 10:20
枚举第一行的全部状态,然后剩下的行直接解方程,这应该是通用法则(这个方法可以顺便可以求得最小步数)  发表于 2020-9-11 10:09
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-9-11 19:22:12 来自手机 | 显示全部楼层
这是关灯问题,可转化为解方程https://blog.emath.ac.cn/guandengyouxihesaoleiwenti/
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-9-11 20:29:40 | 显示全部楼层
根据 https://oeis.org/A159257
3×3总是有解的

点评

n大于3时,还有没有对于任意初始情况都有解的n*n?  发表于 2020-9-13 15:32
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-9-11 21:46:10 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-9-11 22:17 编辑


那你能给出3*3,初始状态只有左上角一灯为亮,如何达到所有灯都灭么?
089.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-9-11 22:17:29 | 显示全部楼层
3*3,第一行第1、2灯亮,可以到达目标状态(全熄)。
332.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-9-11 22:29:27 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-9-11 22:45 编辑
aimisiyou 发表于 2020-9-11 21:46
那你能给出3*3,初始状态只有左上角一灯为亮,如何达到所有灯都灭么?


确实是可以的。如图,最后一图可以看成332图顺时针旋转90度的状态。

最少5步操作。
331.png
331..png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-9-11 22:46:48 | 显示全部楼层
只要找出任意一个解,就能得到最少步数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-9-26 18:46 , Processed in 0.070408 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表