翻转点灯谜题(IBM Ponder This Apr 2023)

作者: , 共 1823 字 , 共阅读 0

原题:https://research.ibm.com/haifa/ponderthis/challenges/April2023.html

一个正方形棋盘,每个格子里都有一个灯泡,有些亮着有些没亮。我们每次可以选择其中一个熄灭的灯泡,点亮它的同时,翻转同行和同列的其它所有灯泡(亮着的关闭,熄灭的打开)。

问从任意给定的状态,求操作,使得最后将所有的灯泡打开。

解答:

如果操作不要求选定熄灭的灯泡,问题就相当简单了。

假设灯泡状态是$w_{i, j}$, 0 表示打开, 1 表示熄灭(注意和题目给的表示方法相反)。我们假设对$(i, j)$的灯泡做的操作为$s_{i, }$,也是 0 , 1 变量(显然此时操作顺序没有关系,而且对于同一个灯泡操作多次无意义)。那么我们有方程:

$$ w_{i, j} = s_{i, j} + \sum_{k\neq i} s_{k, j} + \sum_{k \neq j} s_{i, k} \label{eq}$$

这里的加法是基于 0 , 1 的异或。当棋盘边长为偶数时,我们可以直接猜出其表达式解:

$$ s_{i, j} = w_{i, j} + \sum_{k\neq i} w_{k, j} + \sum_{k \neq j} w_{i, k} $$

此时,对偶数大小的棋盘,我们直接解决了问题。

另一个问题:奇数大小的棋盘怎么弄?答案是,奇数的时候,我们不一定能打开所有的灯。我们记:

$$WR_i = \sum_j w_{i, j}$$
$$WC_j = \sum_i w_{i, j}$$
$$SR_i = \sum_j s_{i, j}$$
$$SC_j = \sum_i s_{i, j}$$
$$S = \sum_{i, j} s_{i, j}$$

那么上面的方程( \ref{eq})可以写作:

$$ w_{i,j}=s_{i, j} + SR_i + SC_j \label{eq1} $$

对上面式子( \ref{eq1})的$j$求和,可得:

$$ RW_i = (n + 1) SR_i + \sum_j SC_j = S$$

同理对$i$求和,可得:

$$RW_j = S $$

这意味着原来状态每一行每一列,其状态之和(在 1,0 的 mod 2 加法下)相等。直观地说,要么每一行每一列熄灭的灯都是偶数个,要么每一行每一列熄灭的灯都是奇数个。

直接从单次操作上也可以看出,每次操作都改变了每一行每一列熄灭灯个数的奇偶性。但最终状态每一行每一列都是偶数。所以最初状态的奇偶性也必定相同。

这个条件也是充分的。因为我们先不管第一行第一列,对剩下的$(n-1)\times(n-1)$棋盘做操作,可以将这些灯全部打开。这时候第一行和第一列的灯要么全是打开的(已经 OK ),要么全是熄灭的,此时对第一行第一个灯做一次操作即可。

不过这种解也不是唯一的。上面的操作选择任何一行一列作为例外,都能得到一组解。

更多:

但如果操作要求每次选定熄灭的灯泡,这时候问题就复杂了。显然,上述的$s_{i, j}$仍可能是一个可行的解,我们需要谨慎地安排先后顺序,使得每次选择系列的灯泡。直接暴力搜索的代码附在后面。

可能存在某种特殊的状态,使得需要某个灯泡操作两次或多次,这就不在上面的搜索路径。问题就变得复杂很多。

Q. E. D.

类似文章:
数学 » Ponder this, 几何
今年 IBM 七月份的 Ponder This 问题(原题在这里,英文):
数学 » Ponder this
IBM Ponder this 每个月会出一道谜题。这个月的题目是求所有的整数,它既是一个平方数,又是一个 triangular number (即可以表示为$1+2+\cdots+m$)。
IBM 的 Ponder This 项目每个月会发出一个谜题,这个月的题目是加倍交换数字游戏
相似度: 0.105
前两天贴出了一个硬币游戏,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答,因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣,请飘至原问题
题目来源:《A practical Guide to quantitative finance interviews》,解答和书上的可能不一样。
利用线性代数可以给某些问题很精妙的证明,Matrix67 就给出了一个这样的例子,这也让我想起以前看见的另外一个例子,分享如下:
相似度: 0.070
Alice 和 Bob 两人玩一种硬币游戏。游戏在一个$ 2\times2$ 的棋盘上进行,棋盘上每个格子上都有一枚硬币。在每一回合, Alice 可以决定选择翻转某两枚或者一枚硬币,接着 Bob 可以选择将棋盘旋转 90 , 180 或者 270 度,也可以什么都不做。
相似度: 0.066
数学 » 概率, 测试
所有大学生都应该学的两门课程,一是经济学,二是概率论,这两门课分表代表着一种生活中的思维方式。来测试一下你的概率论学得怎么样吧。题目作者: wzz12346@newsmth, 原发 Mathematics@newsmth。解答亦来自 wangzz。题目顺序和答案经过调整。
相似度: 0.061
数学 » 数学游戏
问题:
在 MIT BBS 上看到一个有趣的题目
数学 » Ponder this
IBM Ponder this 每个月会出一道谜题。这个月的题目是求所有的整数,它既是一个平方数,又是一个 triangular number (即可以表示为$1+2+\cdots+m$)。
风雨中,绿野童军 7 个孩子, 2 天半时间完成了逆朝大五台山,共 45 公里,爬升约 1800 米。网上有一个很经典的路线图,我们基本也是按照这个走的: