一个组合数学问题：错乱的灯和开关

Sirius

请教各位老师一个问题。
一栋建筑里有2^n个房间，每个房间里有一个开关和一个电灯，但是打开任一房间的开关，都是另一个房间的灯亮。
为了知道哪个开关控制哪个房间的灯，领班每次派一些人各到一个房间，他们同时打开所在房间开关，然后报告自己房间的灯是不是亮的，最后同时关闭所在房间的开关离开。

问：1.经过2n次派送，是否可以知道开关和房间的对应关系。
      2.经过2n-1次派送，是否可以知道开关和房间的对应关系。
      3.经过2n-2次派送，是否可以知道开关和房间的对应关系。

王守恩

1，2个房间：经过1次派送，可以知道开关和房间的对应关系。

2，4个房间：经过1次派送分成2+2，然后执行第1条。
  领班派4人各到一个房间，其中2人打开所在房间开关。
  总有：2个房间的灯是亮的，2个房间的灯是不亮的。
  
3，8个房间：经过1次派送分成4+4，然后执行第2条。
  领班派8人各到一个房间，其中4人打开所在房间开关。
  总有：4个房间的灯是亮的，4个房间的灯是不亮的。
  
4，16个房间：经过1次派送分成8+8，然后执行第3条。
  领班派16人各到一个房间，其中8人打开所在房间开关。
  总有：8个房间的灯是亮的，8个房间的灯是不亮的。
  ......

2^n个房间，经过n次派送，可以知道开关和房间的对应关系。
      
错在那里了？

gxqcn

对于2个房间，不用派送，就知道彼此开关在另一个房间。

Sirius

一个开关只控制一个灯。

mathe

灯和开关一一对应，2n次操作就比较简单. 把房间编号换算成n位二进制编码。

第2k次派人进入k比特为0的房间操作开关，第2k+1次派人进入k比特为1的房间，(k=0,1, …, n-1)。
灯的状态亦用n位二进制编码记录，第2k和第2k+1 次记入第 k 位(末位为第0位）：第2k次亮记为0，不亮记为1，第2k+1 次亮记为1，不亮记为0.
只记录有人进入的房间，无人进入的房间无信息，故无记录。所以第2k和第2k+1次记录的是不同的房间，两次各完成一半，不会有冲突。
当派遣2n次后，灯的状态记录就填满了n位，显然对应于控制它的开关的房间号。

考虑到2个房间无需试探，次数应该可以根据记录调整策略，有所减少。

王守恩

1，2个房间：不用派送，可以知道开关和房间的对应关系。

2，4个房间
    第1次派2人至1、2号房间，
    2.1、如果1、2号房间亮灯，对应关系为2143, 完毕。
    2.2、如果1、2号房间不亮，对应关系为3412, 4312, 3421或者4321;
           第2次派2人到2、3号房间，
           2.2.1 如果2、3号房间亮灯，对应关系为4321, 完毕
           2.2.2 如果2、3号房间不亮，对应关系为3412, 完毕
           2.2.3 如果唯 2 号房间亮灯，对应关系为4312, 完毕
           2.2.4 如果唯 3 号房间亮灯，对应关系为3421, 完毕
    2.3、如果唯 1 号房间亮灯，对应关系为2341或者2413;
           第2次派2人到3、4号房间，
           2.3.1 如果 3 号房间亮灯，对应关系为2341, 完毕
           2.3.2 如果 4 号房间亮灯，对应关系为2413, 完毕
    2.4、如果唯 2 号房间亮灯，与2.3同理只需要再探一次。
    所以，4个房间有机会一次探明，用2次总能探明。
  
3，8个房间：经过2次派送分成4+4，然后执行第2条。
  第1次：领班派4人各到一个房间; 第2次：领班派4人各到一个房间。
  总有：第1次灯亮的房间+第2次灯不亮的房间=4。

4，16个房间：经过1次派送分成8+8，然后执行第3条。
  第1次：领班派8人各到一个房间; 第2次：领班派8人各到一个房间。
  总有：第1次灯亮的房间+第2次灯不亮的房间=8。
......

2^n个房间，经过 2n-2 次派送，可以知道开关和房间的对应关系。
      

王守恩

王守恩 发表于 2021-12-16 17:28
1，2个房间：不用派送，可以知道开关和房间的对应关系。

2，4个房间

4个房间也可以这样：
第1次派3人至1,2,3号房间，必是两明一暗，不妨设是3号是暗的，其开关在4号房间。
第2次派2人到1,2号房间，若全亮则对应关系为2143，若仅1号亮则对应关系为2341，若仅2号亮则对应关系为3142。

hujunhua

用图论表示，每个房间视为一个点，房间 i 的开关控制房间 j 的灯，就连一条有向边 i→j。
结果图就是由一个个单向环（箭头朝一个方向，顺时针方向或者逆时针方向）组成，最小的环就是两个点互射，没有箭头接到自己箭尾的单点环。
只有一个环的图应是最废探测次数的情况，没有机会用较少次数探测清楚。
由2^(n-1)个双点环构成的图有机会用n-1次探测清楚, 这是机会最好的情况下需要用到的最少次数。

gxqcn

一栋建筑里有 \(n\) 个房间，每个房间里有一个开关和一个电灯，但开关所控制的电灯不一定在本房间。初始状态：所有的电灯均处于灭灯状态。
为了知道哪个开关控制哪个房间的灯，领班每次派一些人各到指定的一个房间，他们同时打开所在房间开关，然后报告自己房间的灯是不是亮的，最后同时关闭所在房间的开关离开。

请给出一种方案：经过若干次数的派送（派送次数越少越佳），确保可获知开关与房间的对应关系。

/////////////////////////////////////////////

我把楼主的问题改了下：
1、房间数目由 \(2^n\)，变成更普通的 \(n\)；
2、开关与灯的对应，不再强求一定错乱的。

Sirius

感谢各位老师。