找回密码
 欢迎注册
查看: 22620|回复: 1

[求助] 毒酒问题延伸出的一道组合题目?

[复制链接]
发表于 2019-12-24 00:45:17 | 显示全部楼层 |阅读模式

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

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

×
有数对(A,B,C),其中A从a1a2a3a4任取其一,B从b1b2b3b4任取其一,C从c1c2c3c4任取其一
则数对anbmcl,共有4 ^3=64种情况
如果ABC三位中有两位相同,比如a1b1c2与a1b1c1,a1b3c1与a1b4c1,则称这两个数为一对
任取16个不同的ABC,是否必然可分为七对?


——————————————————————————————
起因是对毒酒问题的简化版本,16瓶酒有2瓶毒酒,问最少需要几个人
有人提出了一种构造方法

我们可以将16个瓶子如下编号
000 110 020 130
201 311 221 331
002 112 022 132
203 313 223 333
此时需要3*3=9只老鼠
老鼠分为三组,第一组的三只分别喝第一位为012的毒酒,若死两只确认两位,若死一只确认该数字和3有毒
第二组和第三组分别处理第二位和第三位数字

尽管这个构造是有问题的,被人挑出了错误

但是我还是想尝试一下这种构造能否改良
经过推理我发现 对三位数ABC
如果存在两位相同,比如ABX和ABY,或者AXB和AYB,那我们称为出现一对
一对会影响构成的原因在于,如果出现两对
那么就会出现以下情况
ABX1 CDX2
ABY1 CDY2
这时如果X1Y1的构成和X2Y2的构成相同,那么就会导致(AC,BD,X1Y1)无法拆分
因为此时X1无法等于Y1,所以规避方法只有一种
X1Y1和X2Y2的构成不同,即(X1,Y1,X2,Y2)一共有三个数
考虑到四进制情况下,此时X1Y1位置共有C(2,4)=6种情况
也就是如果构成七对,那么由于抽屉原理就会使得整体构造无效

现在需要思考,是否能够避免出现七对
接下来就不知怎么证明或思考了,也就绕到了最上面的题目,求解答

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-12-24 00:57:25 | 显示全部楼层
AAB
ABC
ACD
ADA

BAA
BBB
BCC
BDD

CAD
CBA
CCB
CDC

DAC
DBD
DCA
DDB

这个构造是不是成功了??
能解决16瓶2毒酒问题?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-5-20 01:52 , Processed in 0.062132 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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