首次发帖，来一道编码题
不错的首发题以前看到的：你和你的同伴向观众表演节目
一幅牌加大小王共54张，观众每次从中任意抽出5张，然后交给你，但不给你的同伴看见。
现在，你可以自由选择藏起一张牌，然后将剩下4张牌按一定次序摆在桌上给你的同伴看。
要求你的同伴根据桌面牌的大小与排列次序推断出你所藏的牌。但是你的同伴不得利用其它诸如牌张方向，正反等额外信息（比如你放好后，观众可以重新摆牌，除了4张牌的排列次序以外，观众都可以动）。
1. 请设计一个能表演成功的信号系统或者说编码方法。
2. 对于抽5张牌的情况，最多可以处理多少张牌？，抽m张牌的情形呢？ 等价于任何四张牌的排列能表示任何牌
每个牌的信息包括
花色两个比特
大小四个比特
共6个比特信息
所以足够表示54张牌
现在问题是如何表示 原帖由 无心人 于 2008-8-27 20:13 发表 http://bbs.emath.ac.cn/images/common/back.gif
等价于任何四张牌的排列能表示任何牌
。。。
四张牌的排列数只有24种，因此最多只能表示这4张牌以外的24张牌。 很显然,根据$P_n^4>=C_n^5$,我们可以得到$n<=124$
而对于所有的$n<=104$,可以采用下面方法构造一个方案,假设所有牌子编号从1到n,
分别根据5数之和模5为0,1,2,3,4选择将5数中最小,次小,...,最大的数藏起来.
然后对于余下4张牌子,我们可以有24种不同排列方案,
而对于给定的亮出的4张牌子$x_1<x_2<x_3<x_4$,第5张牌子x比$x_1$小的必然有$x+x_1+x_2+x_3+x_4=0(mod 5)$,同样$x_1<x<x_2$的必然有$x+x_1+x_2+x_3+x_4=1(mod 5)$等等
所以小于$x_1$的最多$[(x_1-1+4)/5]$种情况,$x_1<x<x_2$的最多$[(x_2-x_1-1+4)/5]$种情况,...
总共最多$[(x_1-1+4)/5]+[(x_2-x_1-1+4)/5]+[(x_3-x_2-1+4)/5]+[(x_4-x_3-1+4)/5]+[(n-x_4+4)/5]<=+4$
所以对于$n<=104$必然有对于每个亮出的4张牌的,藏起来的牌的情况最多24种 果然厉害！，只差一点点就完美了。 对于n=124的存在性，应该可以使用Hall定理
页:
[1]