超难的组合猜想

fuzhineng

有m*n个人,教官A将他们排成n行m列的矩阵,教官B也将他们排成n行m列的矩阵,两者的排列没有任何关联,但是总能在此m*n个人中找出n个人,它们在教官A的排列中任意两个人都不同行,在教官B的排列中任意两个人也都不同行.

fuzhineng

这个猜想还有更进一步的结果,如果成立就算称为着色第一定理都不为过.
有m*n个人参加2个学习班,在每个班中被分为n个小组,每个小组m个人,有m种颜色的彩旗,那么无论小组怎么分,总能找到一种配旗的方案,使得每个小组中m个人每人都拿一种不同颜色的小旗.[br][br]-=-=-=-=- 以下内容由 fuzhineng 在 时添加 -=-=-=-=-
此猜想本人用计算机随机生成分配情况进行验证,验证过数百万种情况没有发现意外.

ccmmjj

这个周末正好思考这个问题。

ccmmjj

[这个贴子最后由ccmmjj在 2013/09/16 10:34am 第 1 次编辑]

我在周末思考了一下，这是个定理。它的证明有点表述上的麻烦，需要新定义。
定义一：由m个1，m个2，……，m个n组成的数组，称为“m*n数组”。每个数称为它的一个元素，共有m*n个元素。字符1，2，……，n称为它的“字”，它只有n个字。
定义二：在“m*n数组”中任取m个元素（不计顺序）作为一个小组，我们称它为“m-集”，简称“集”。一个集中可以包含若干个字，我们就用这若干字加上小括号来表示这个集。集可用它包含的某个字作“代表”，这个“代表”可由我们按照需要选择。
例如；集中只有1，2，3这三种不同的元素，则我们记这个集为（1，2，3）。具体的元素个数不在考虑之内。而这个集的代表可以是1，2，3中的某一个。
定义三：将“m*n数组”任意分成n个集，称为一个“分组”。在一分组中的两个集称为“直接相关”，指的是这两个集至少含有一个相同的字。若干个顺次直接相关的集形成一个“相关链”，若两个集没有相同的字，但处在某相关链的两端，则称它们“间接相关”，“直接相关”和“间接相关”合称“相关”。没有任何相关链连结的两个集称之为“无关”
例如：集（1，2)与(2,3)是直接相关.在相关链(1,2)(2,3)(3,4)中,(1,2)和（3，4）是间接相关。在一分组中，单字集（k）与其它集都无关。
定义四：在一分组中若干个集结合成一“区”。如果这个“区”内有一集与区外的集相关，这个区就称之为“开区”，否则称为“闭区”。
约定：“集”用大写字母A表示，“区”用大写字母G表示。分组中所有集（n个）结合成的“区”称为“整区”，记作I。[br][br][color=#990000]-=-=-=-=- 以下内容由 ccmmjj 在 时添加 -=-=-=-=-
因时间关系，先将定义贴在这里

ccmmjj

推论1：I是一个闭区。 推论2：若G是一个开区，那么I-G也是一个开区。 推论2';：G是一个闭区，那么I-G也是一个闭区。 I-G表示分组中除去G中的集后所有集组成的区。这几个推论可以直接从定义中得到。 命题1：若G是一个闭区且G由k个集组成，那么G中有且只有k个字。 证明：由于G是一个闭区，所以在I-G中没有包含它的字，即G的每个字都含有m个元素。因为G由k个集组成，所以它总共有km个元素，显然km/m=k，即得。 如果一个区包含m个相同元素，则我们说它对这个字是“饱和”的。否则就说它是“不饱和”的。 绪1：闭区对它包含的字都是饱和的。 绪2：如果一个区对它所包含的字都是饱和的，那么它是一个闭区。 绪3：如果一个区对它所包含的字至少有一个是不饱和的，那么它是一个开区。 命题2：开区G由k个集组成，那么它包含的字数一定大于k。 证明：由于G是开区，（含x个字。）所以至少有一字不饱和，它所含元素数小于m。因为每个字最多包含m个元素，于是每个字所含元素的平均数小于m。因为因为G由k个集组成，所以它总共有km个元素，即km/xk.证毕。[br][br]-=-=-=-=- 以下内容由 ccmmjj 在 时添加 -=-=-=-=- 再将几个性质贴上来。待续

ccmmjj

定义五：若一个区所包含的集都是另一区的集，那么就称此区是另一区的“部分”。定义六：如果一个闭区除本身外的任一部分都是开区，那么称这闭区为“单闭区”。 定义六';：如果一个开区的任一部分都是开区，那么称这开区为“单开区”。 单闭区与单开区合称“单区”。 推论：单区的部分是单区。单区没有无关的两部分。 命题3：（饱和代表定理）在含有k个集的单开区G中，如有p个饱和字，则必可将其中ppm即p1,f(2)>2,……,f(p)>p。可见，适当调整这些字的顺序，可以在f(p)个集中选中p个用此p个字代表。 命题4：（插入交换代表定理）将集A=（i1,i2,……,ip）加入一个单开区G中，若G中的集已全部都有不同的字作代表，那么必可作适当调整，使区G+A全部都有不同的字作代表。 证明：1；若G中代表不含i1,i2,……,ip中的某一个，则就以它作为A的代表，要求完成。2；若G中代表已含i1,i2,……,ip。则将此p个字在G中代表的集组成一区Gp。显然这是个开区，它包含的字数大于p，若l1正是其不同于i1,i2,……,ip的字，并不被作为代表，则将此l1所在的集的代表赋与l1，而将它原先代表字（在i1,i2,……,ip之内）赋与集A。若l1是另一集B1的代表，便将B1也加入区Gp,寻找下一个字l2，……这样形成一个链式，因为G是单开区，这个链总是有尽头的，即这个字是可以找到的。找到后按相反的顺序逐步交换代表，于是区G+A的代表是可以理顺的。 [br][br]-=-=-=-=- 以下内容由 ccmmjj 在 时添加 -=-=-=-=- 写到这里基本证明已经结束。

fuzhineng

对猜想的进一步结果思考过后，我发现它很容易由猜想的成立推出。因为如果猜想成立，则可以找到n个人代表2*n个小组，将此n人归为一种颜色，剩下的（m-1)*n个人又是猜想可以满足的形式，继续找出n人的代表归为一种颜色，这样就能够造出满足要求的着色了。
有了上面的思考后，我们可以集中精力思考猜想，也就是找出n个人代表2*n个小组。
ccmmjj的证明我觉得有一点问题，大致上你的证明可以得出找n个人代表n个小组
的情况（和指派问题的匈牙利算法很象）。再有你证明中说 "若l1是另一集B1的代表" 显然将问题想简单了，实际上是 l1可能另二集B1，B2的代表，这样你所谓的链就不那么简单了。
个人感觉猜想应该是正确的，上周五下班开始让电脑跑了随机情况，周一上班也没有输出异常结果。

ccmmjj

若l1是另一集B1的代表" 显然将问题想简单了，实际上是 l1可能另二集B1，B2的代表，这样你所谓的链就不那么简单了。
----------------------------------------------------------
你想得大概复杂了，代表是我们指定的，l1可以是另二集B1，B2的字，却不能同是代表。作为一个单开区，它所含的集可以一个一个的增加，从归纳原理，我们总是认为上一个区是已经理顺的区。所以不存在你说的情况。

fuzhineng

我可以把这个猜想再描述一下:
m*n个人参加A,B 2个学习班,在每个班上它们被分成n个m人的小组,那么总能选出n个人,它们是此2*n个小组的组长.
注意是选n个人代表2*n个组,也就是说1个人代表2个小组(一个在A班,一个在B班)
这个问题当m=2的时候很容易证明,当m>2的时候就不那么容易了.

ccmmjj

算了时间关系，要放假了不说了。