[求助]一个排列组合问题，解答有奖！

whjman

[这个贴子最后由whjman在 2007/01/08 05:27pm 第 6 次编辑] 题目： 第一次将1、2、3、。。。、36分成四组，每组9个数。 第二次将1、2、3、。。。、36分成四组，每组9个数。 。 。 。 第n次将1、2、3、。。。、36分成四组，每组9个数。 1、要求第i(i取1到n)次中的任何一组，与非第i次中的任何一组相同的数字个数为2或者3个,问n最大为多少？如果与非第i次中的任何一组相同的数字个数为1或者2或者3个,n最大又为多少？能证明吗？ 2、用什么方法实现这种排列和组合？ 敬请请多多指点！报酬：500元人民币 最新结论：相同为2或3的次数n=7（有待证明） 问题简单化： 简化一： 第一次将1、2、3、。。。、9分成3组，每组3个数。 第二次将1、2、3、。。。、9分成3组，每组3个数。 。 。 。 第n次将1、2、3、。。。、9分成3组，每组3个数。 要求第i(i取1到n)次中的任何一组，与非第i次中的任何一组相同的数字个数为1个,问n最大为多少？ 如下分法： 第1次 a1 a2 a3 b1 b2 b3 c1 c2 c3 第2次 a1 b1 c1 a2 b2 c2 a3 b3 c3 第3次 a1 b2 c3 a2 b3 c1 a3 b1 c2 第4次 a1 b3 c2 a2 b1 c3 a3 b2 c1 最多只能分4次，有谁能分第5次吗？ 简化二： 第一次将1、2、3、。。。、16分成四组，每组4个数。 第二次将1、2、3、。。。、16分成四组，每组4个数。 。 。 。 第n次将1、2、3、。。。、16分成四组，每组4个数。 要求第i(i取1到n)次中的任何一组，与非第i次中的任何一组相同的数字个数为1个,问n最大为多少？ 如下分法： 第1次 a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 d1 d2 d3 d4 第2次 a1 b1 c1 d1 a2 b2 c2 d2 a3 b3 c3 d3 a4 b4 c4 d4 第3次 a1 b2 c3 d4 a2 b3 c4 d1 a3 b4 c1 d2 a4 b1 c2 d3 最多只能分3次，有谁能分第4次吗？ 推论： 以上分法称为均匀分法，也就是尽可能的将小组中的数均匀分配到别的小组中去，只要是均匀分法， 就满足(数字个数开平方-1)<=n<=(数字个数开平方+1)。 n=sqr(36)+1=7

zhaolu48

[这个贴子最后由zhaolu48在 2006/10/05 03:54pm 第 1 次编辑]

自认为对于排列组合方面，我很在行，
可这个问题的难度，远远超过了我的能力！

zhaolu48

　　仔细一想也并不算难，下面只就“与非第i次中的任何一组相同的数字个数为2或者3个”的情况解之。

“非第i次中的任何一组相同的数字个数为1或者2或者3个”的情况也就容易求n的最大值了。

whjman

zhaolu48兄弟：
    你已经进入状态了，你的初步想法与我的相同，但你上面的结果只是第2次的组合种数(最后不是加1，而是乘1),其中有许多相同4个数字的。
   我的观点：  
    1、第一次随机分组：a1 a2 a3 a4 a5 a6 a7 a8 a9
                       b1 b2 b3 b4 b5 b6 b7 b8 b9
                       c1 c2 c3 c4 c5 c6 c7 c8 c9
                       d1 d2 d3 d4 d5 d6 d7 d8 d9
    2、第二次：（与第一次相关联）
                a1 a2 b1 b2 c1 c2 d1 d2 d3
                a3 a4 b3 b4 c3 c4 c5 d4 d5
                a5 a6 b5 b6 b7 c6 c7 c8 c9
                a7 a8 a9 b8 b9 d6 d7 d8 d9   
    3、第三次：（与第一、二次相关联）
                a1 a2 b8 b9 c3 c4 c5 d6 d7
                a3 a4 b5 b6 b7 c1 c2 d8 d9
                a5 a6 b3 b4 c8 c9 d1 d2 d3   
                a7 a8 a9 b1 b2 c6 c7 d4 d5
    4、第四次：（与第一、二、三次相关联）依此类推
   到底可以分多少次？怎么计算？

zhaolu48

“最后不是加1，而是乘1”
是加1，而不是乘1。
注意我的说明“因非第一次任意一次的分组方法为：”
“加1”是加第一次的“1”，就是说，那三个数的乘积，只是非第一次的组合数。
我的年龄虽然不算大，但也接近耳顺之年了。不知老“哥哥”高寿？

zhaolu48

[这个贴子最后由zhaolu48在 2006/10/07 04:26pm 第 1 次编辑]

　　“只是第2次的组合种数(最后不是加1，而是乘1),其中有许多相同4个数字的”。
　　不会有许多相同4个数字的。
　　因为第一次分组，一个数字不会在两个组中重复出现的。
　　我的组合法的错误是：
　　只是保证了非第一次的任意一组与第一次的任意一组有两个或三个相同数字的，但不能保证非第i(i>1)次的任意一组与非第i次的任意一组也有两个或三个相同数字的。
　　因此n的真值要远小于3266533992960001的！
　　n的最大值应当是：
　　2+C(4,2)*3^2+2*C(4,3)*3^3+3*2*C(4,4)*3^4
   =2+54+216+486=758。
　　式子虽然简单，但关系比较复杂，想说清楚比较难，就不说了。
　　如果是在黑板上讲解还会好一些。
　　

whjman

zhaolu48老师：
    我有点冒失，见谅！
  n的最大值应当是：
　　2+C(4,2)*3^2+2*C(4,3)*3^3+3*2*C(4,4)*3^4=2+54+216+486=758。
是“与非第i次中的任何一组相同的数字个数为2或者3个”的最大值吗？
它的原理是什么呢？
     我的email:fhsoftware@126.com,能发电子邮件给我吗？我想用电
脑编程实现它。

zhaolu48

　　我昨天发完帖子，仔细一琢磨，我的想法还是错了，当然原理也就不用说了。
　　我前一秒钟，又突然想到，我在三楼中的那个大数字减1：32665339296000是第二次的取法，对于n来说，它只是第二次。取其中的任何一个，都是第二次。
　　因此不妨设第一次为：
　　1,2,3,4,5,6,7,8,9   10,11,12,13,14,15,16,17,18
    19,20,21,22,23,24,25,26,27    28,29,30,31,32,33,34,35,36
   第二次为：
　　1,2,3,13,14,22,23,31,32,    4,5,10,11,12,24,25,33,34
    6,7,15,16,19,20,21,35,36    8,9,17,18,24,25,28,29,30,
　　第三次开始，保持4组不变各为三个数：
　　1,2,3     10,11,12     19,20,21      28,29,30
　　每组的其余6个数先按来自第一次分组中同组的两个数分为一小组(如第一组的其余6个数分成的3小组为13,14,  22,23  31,32)，把这种分法称为A型，则每两个数(一小组)只能有两个大组供选择，因此此类分组的次数为：
　　[2*C(3,1)]^4=1296

　　第三次开始，又可以将每小组打乱顺序，重新分组
　　如第一组中的6个数：13,14  22,23  31,32还可分为
　　13,22  14,23  31,32 此种类型有3种。
　　13,22  14,31  23,32 此种类型有32种。
　　这35种分法，称为B型
　　则上面的1296为AAAA分法
　　则分法依次有
　　2、AAAB　4种　4*35*[2*C(3,1)]^3=30240
　　3、AABB　6种  6*35^2*[2*C(3,1)]^2=264600
　　4、ABBB  4种  4*35^3*[2*C(3,1)]=1029000
　　5、BBBB　1种  35^4=1500625
　　5种类型共有1296+30240+264600+1029000+1500625=2825761
以上都是第i次的第j=1,2,3,4与非第i次的第j组有3个数字相同。要改变这种状态，
只能在每组的三个不变数字任取一个(共3^4=81)的任意一个排列(共4!=24个)，即前面的每一个都可变换为81*24=1944
　　从而n的最大值为
　　2825761*1944+2=5493279386。

whjman

[这个贴子最后由whjman在 2006/10/11 07:51pm 第 3 次编辑] 我可以证明：相同数字为2或3的分组，次数n<<337次。 证明：假设可以分m次，那么选第一次分组中的第一组(称为A11)，其数字分布在4(m-1)组中,除第一次外，每一次分的四个组中都包含A11的数字，分配比例为2、2、2、3， 即：除第一次外，每一次分组的四组中都有一组包含A11的3个数字。 1、A11中只有9个数字，按（2、2、2、3）的分法，分布于各次中分法为：C(9,3)=84种。 2、将A11先分84次，在第85次的四组中必定有一组(A33)和前84次中的一组(A22)有相同的3个数字，这一组的其余6个数字不能与A11、A22的数字相同，最多只有C(21,6)种选法。 3、再将A11分84次，在第169次的四组中必定有一组(A44)和A11、A22、A33有相同的3个数字,这一组的其余6个数字不能与A11、A22、A33的数字相同，最多只有C(15,6)种选法。 4、依次类推，到C(9,6)结束，共分4*84=336次,另外加包含A11的第一次，共337次。 因为只考虑了第一次的第一组，还没有考虑其它的组，所以能够分的次数远小于337次。

zhaolu48

[这个贴子最后由zhaolu48在 2006/10/09 09:01am 第 1 次编辑]

　　昨天是第一步没经过仔细考虑，因此有几步考虑不周，但总的原理是对的。
　　“13,22  14,23  31,32 此种类型有3种”，应该是2*C(3,2)=6种。
　　“13,22  14,31  23,32 此种类型有32种”，应该是C(4,1)*C(2,1)=8种。
　　从而B型为6+8=14种。
　　而A型为2*C(3,1)=6种。
　　因此A、B两种类型取4个的元素可重组合的个数为：
　　(14+6)^4=160000
　　“每组的三个不变数字任取一个(共3^4=81)的任意一个排列(共4!=24个)，即前面的每一个都可变换为81*24=1944”，对于每4个的全排列，都存在一个按从小到大的排列，把其按原顺序放回，对应的仍是：
　　“第三次开始，保持4组不变各为三个数：
　　1,2,3     10,11,12     19,20,21      28,29,30”
因此“每一个都可变换为：”81*(24-1)+1=1864。
　　从而n的最大值为：
　　2+1864*160000=298240002
　　对于这个值我敢打保票：是准确无误的！
　　500元的报酬就不必了，
　　我的Email:zhaolu48@163.com
　　通过电子邮件告诉我有关您的资料，以便我有机会去您那里时，叨咬您一次。