能不能找到这样的排列组合?

有一个N个数的组合(N>6),对这个组合进行6个数的排列组合。这个排列组合应该满足:从N个数中选出5个数,都能在排列组合中找出唯一的一组包含这5个数。
例如:对7个不同的数进行排列3,要求7个当中任选2个都能在这排列3中找到唯一一组包含着2个数
排列3的组合有:123,145,167,246,257,347,356.
现在我们在7个数中选出4和7.在上面的组合中就只有347的组合同时包含4和7.

题目应该表达不清吧。
意思是这样吧,有N个不同的数字,N>6,在这N个数字钟抽出6个数字来形成一个排列,可以抽M次,这样就有一个含有M个排列的一个组合。现在要求满足以下条件:从N个数字中抽出任意5个数字,要求组合中这M个排列有且仅有一个排列包含这5个数。
举例:N=7,不妨假设为1到7,那么从7个数中取6个,共有7种排列,如下
1.2.3.4.5.6;1.2.3.4.5.7;1.2.3.4.6.7;1.2.3.5.6.7;1.2.4.5.6.7;1.3.4.5.6.7;2.3.4.5.6.7;
这个组合就不满足条件,因为第一个、第二个排列都含有1-5,第二个、第三个排列也都含有1.2.3.4.7,也是重复了。
那么当N=7的时候,其实是不存在这样的组合的。我们先选出一个排列,如1-6,那么第二个排列也是6个数字,不管怎么选,都至少与1-6有5个数字相同;
那么当N=8的时候,我们看看:
1.2.3.4.5.6;1.2.3.4.5.7;1.2.3.4.5.7;1.2.3.5.6.7;1.2.4.5.6.7;1.3.4.5.6.7;2.3.4.5.6.7;
1.2.3.4.5.8;1.2.3.4.6.8;1.2.3.5.6.8;1.2.4.5.6.8;1.3.4.5.6.8;2.3.4.5.6.8;
1.2.3.4.7.8;1.2.3.5.7.8;1.2.4.5.7.8;1.3.4.5.7.8;2.3.4.5.7.8;
1.2.3.6.7.8;1.2.4.6.7.8;1.3.4.6.7.8;2.3.4.6.7.8;
1.2.5.6.7.8;1.3.5.6.7.8;2.3.5.6.7.8;
1.4.5.6.7.8;2.4.5.6.7.8;
3.4.5.6.7.8;
以上是28个排列;
规律是第一行空缺8.7;8.6;8.5;8.4;8.3;8.2;8.1;
第二行空缺7.6;7.5;7.4;7.3;7.2;7.1;
依此类推;
这样28个排列明显不符合。是否减去一些后可以满足呢?
反过来想,要6个数字的排列有且仅有一个含任意5个数字,那么这6个数字就是要最少有2个不同;
还是用N=8的情况来说,从8个数字取6共有C6/8=28种情况,取5个有C5/8=56种情况,从题目中知道,起码要C6/N>=C5/N时才成立;
当N=11时,明显的C6/11=C5/11;这个时候,1.2.3.4.5.6;1.2.3.4.5.7;1.2.3.4.5.8这些中还是都含有了1-5;还是不够;
当N>11开始,C6/N>C5/N了。那应该N=多少时,才能满足呢?继续。。。
回归简单的先,当取3个数字,然后任意取2个数字的情况;
当N=3时,取3个,得到1.2.3;随便从3个数字取2个,都是有且仅有一个对应;
当N=4时,取3个,得到1.2.3;1.2.4;2.3.4;这个组合就不行了,重复了;
当N=4时,不管怎么取,都是不满足条件。为什么呢
当N=5时,1.2.3;1.4.5;这两个含有了1+任何一个的;但是2.4;2.5;3.4;3.5;这4个都不能在这里找到。也是不满足条件;
有事先忙,回头有空再来探讨。
当N=8的时候,是不存在的,以下是证明:
不妨第一个排列为1.2.3.4.5.6;那么第二个排列需要满足的条件是必须含有7.8,要不就有5个以上数字跟第一个排列重复了。所以第二个排列设为1.2.3.4.7.8;第三个排列需要满足同时含有7.8跟5.6,那么假设为1.2.5.6.7.8;第四个必须同时含有7.8.5.6.3.4,那么就是3.4.5.6.7.8;这4个排列已经是满的了,不能再增加其他排列进去了。各自的规律是分别不含7.8;5.6;3.4;1.2;但像1.3.5.7.8;1.4.5.7.8这样的在这4个排列中找不到。
得出一个规律:当N=8时,只能有4组,但是4组不够满足。
还要继续探索....有点晕了,上班先。
当N=9时,存在这样的组合如下:
4.5.6.7.8.9;2.3.6.7.8.9;2.3.4.5.8.9;2.3.4.5.6.7;1.3.5.7.8.9;1.3.4.6.7.9;
1.3.4.5.6.8;1.2.5.6.7.8;1.2.4.6.8.9;1.2.4.5.7.9;1.2.3.5.6.9;1.2.3.4.7.8;
共12组,包含了1-9任何5个数字,而且也只有一个组合对应。
思路是这样的:
9个数字中拿6个出来,剩下的3个为P,(P为3个数字的组合)那么上面就有12个P,这些P应该包含了从1-9任意取出的两个数字,而且这些P之间不能有两个数字以上相同。
假如有两个相同,那么对应的那两组6个数字就只有一个数字不同,例如P1和P2都含有1和2,那么P1和P2对应的两个组合肯定会含有相同的5个数字(如3.4.5.6.7.8和3.4.5.6.7.9)。
所以这些P不能有两个数字以上相同。同时这些P要含有任何2个数字的组合。就是说这些P要含有1.2;1.3;1.4;1.5;1.6;1.7;1.8;1.9;2.3;2.4;2.5;2.6;2.7;2.8;2.9;3.4;3.5;3.6;3.7;3.8;3.9;4.5;4.6;4.7;4.8;4.9;5.6;5.7;5.8;5.9;6.7;6.8;6.9;7.8;7.9;8.9;但是又不能重复含有。这样就将N=9,取6个数字,任意5的原题转换成
N=9,取3个数字(即P),任意2.这个情况就满足了。
温馨提示:答案为网友推荐,仅供参考
第1个回答  2013-09-06
这个题目叙述的再清楚一点啊 什么叫对6个数进行排列组合 没听过这个说法 是你自己写出的题目么?追问

有N个不同是数,按要求取出不同的6个数组成一组,这样就可以组成M组嘛。其要求是现在在N个数中任选5个不同的数都能在这M组中找到唯一的一组同时包含这5个数。问这M个组合应该如何排列(能不能找到这样的组合)。(N>6)

相似回答
大家正在搜