五千年(敝帚自珍)

主题:如何分摊秘密(一)——从《鹿鼎记》中的四十二章经说起 -- 明日枯荷包

共:💬63 🌺987
全看分页树展 · 主题 跟帖
家园 相差一个数量的原因

相差一个数量的原因,我前面说了,其实是锁的结构不同。我的锁是多钥锁,但每把钥匙都不同。M兄的锁是单钥锁,但是允许有多把相同的钥匙。

M兄的方法应该这么理解:对于任何一个m-1人组,我们要有一只“禁制锁”,除了这m-1人外,其他(n-m+1)人都能开这锁。这样一共有C(m-1,n)只禁制锁,它们都并联地锁在门上。

任何m-1个人的话,都有一只对付他们的禁制锁,所以那只锁他们是开不了的。但是只要有m人,无论哪只禁制锁都只最多能对付其中的m-1人(有些锁说不定这m个人里有好几个都有钥匙)于是一定能开。

如果考虑总共8人如3人可开门的情况。我的方法是弄C(3,8)只3钥锁串在一起,而M兄的方法弄C(2,8)只禁制锁并联来一起,每锁有8-2=6把钥匙。

所以我前面的说法有问题,我开始以为可以统一成“一锁一钥”的串联并联法。事实上我们的方法并不等价,一个是先并后串(多钥一起才能开锁可以看成是一锁一钥的并),一个是先串后并(多钥每钥都可单独开锁可以看成一锁一钥的串)。不过这两种方法的钥匙数量总是相同的,就是truth兄底下说的C(m-1,n)*(n-m+1) = C(m-1,n-1)*n = C(m,n)*m。等式左边是M兄的方法,右边是我的方法。不过我相信还是有某种转换的理解方式可以统一这两种方法。

全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河