数学研发论坛

 找回密码
 欢迎注册
查看: 730|回复: 10

[讨论] 一个组合数学问题:错乱的灯和开关

[复制链接]
发表于 2021-12-5 10:03:24 | 显示全部楼层 |阅读模式

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

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

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

问:1.经过2n次派送,是否可以知道开关和房间的对应关系。
      2.经过2n-1次派送,是否可以知道开关和房间的对应关系。
      3.经过2n-2次派送,是否可以知道开关和房间的对应关系。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-12-13 06:22:34 | 显示全部楼层
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次派送,可以知道开关和房间的对应关系。
      
错在那里了?

点评

领班每次派一些人各到一个房间,他们同时打开所在房间开关——好像不能选择一部分人打开开关  发表于 2021-12-26 23:35
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-12-14 08:28:25 | 显示全部楼层
对于2个房间,不用派送,就知道彼此开关在另一个房间。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-12-14 12:19:23 | 显示全部楼层
一个开关只控制一个灯。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-12-15 12:40:42 | 显示全部楼层
灯和开关一一对应,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个房间无需试探,次数应该可以根据记录调整策略,有所减少。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-12-16 17:28:48 | 显示全部楼层
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-20 09:20:09 | 显示全部楼层
王守恩 发表于 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。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-12-23 12:05:59 | 显示全部楼层
用图论表示,每个房间视为一个点,房间 i 的开关控制房间 j 的灯,就连一条有向边 i→j。
结果图就是由一个个单向环(箭头朝一个方向,顺时针方向或者逆时针方向)组成,最小的环就是两个点互射,没有箭头接到自己箭尾的单点环。
只有一个环的图应是最废探测次数的情况,没有机会用较少次数探测清楚。
由2^(n-1)个双点环构成的图有机会用n-1次探测清楚, 这是机会最好的情况下需要用到的最少次数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-12-26 17:57:53 | 显示全部楼层
一栋建筑里有 \(n\) 个房间,每个房间里有一个开关和一个电灯,但开关所控制的电灯不一定在本房间。初始状态:所有的电灯均处于灭灯状态。
为了知道哪个开关控制哪个房间的灯,领班每次派一些人各到指定的一个房间,他们同时打开所在房间开关,然后报告自己房间的灯是不是亮的,最后同时关闭所在房间的开关离开。

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

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

我把楼主的问题改了下:
1、房间数目由 \(2^n\),变成更普通的 \(n\);
2、开关与灯的对应,不再强求一定错乱的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-1-20 17:19:48 | 显示全部楼层
感谢各位老师。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2022-8-10 03:40 , Processed in 0.093181 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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