各位仁兄帮忙做两道数学题目,做出有奖

lizheng · 发表于 2004-12-4 18:09:54

<

>15人,7天,每人每天拍一张三人合影,使所有人全部互相合影留念,应该如何安排?
<

>63人,31天,每人每天拍一张三人合影,使所有人全部互相合影留念,应该如何安排?
<

>有人做出来有奖,1000元,发EMAIL给我

btluo · 发表于 2004-12-4 23:40:23

<

>是不是真的有钱奖先？有的话我倒是想到了一种方法，不过必须编程才能求解。大意如下：先以a1为“中心”，找出没有和a1合照过的a2，再找出没有和a1合照过也没有和a2合照过的a3，然后a1、a2、a3合照一张；接下来找出没有和a1合照过的a4，再找出没有和a1合照过也没有和a4合照过的a5，然后a1、a4、a5也合照一张；...直到再也找不到没有和a1合照过的人为止。然后再以b1为“中心”，找出没有和b1合照过的b2，再找出没有和b1合照过也没有和b2合照过的b3，然后b1、b2、b3合照一张；接下来找出没有和b1合照过的b4，再找出没有和b1合照过也没有和b4合照过的b5，然后b1、b4、b5也合照一张；...直到再也找不到没有和b1合照过的人为止。...一直到所有人都成为一次“中心”。那时，必然会得到一大叠相片。在这叠相片中，总是可以找到一组相片，包含了所有的人，并且没有一个人被重复拍过照，以这组相片作为第一天拍摄的相片。然后，在余下的相片中，也总是可以找到一组相片，包含了所有的人，并且没有一个人被重复拍过照，以这组相片作为第二天拍摄的相片。...一直到这一大叠相片被瓜分完为止，则得到了所要求的答案<IMG src="http://www.shumo.com/bbs/Skins/Default/emot/em02.gif">[em02][em02]

huihong · 发表于 2004-12-5 22:26:04

<

>把这15个人遍上号码1。2。。。15，这样构造一个15阶的矩阵A（15*15），严格上三角（不包括对角线）上的元素a（i，j），就表示在一次照相中第i个人和第j个人之间的关系，这些元素共有15*7个，一开始都为0，第一天，在这些元素中任选三个使他们连线组成一个直角三角形，其中直角顶点在斜边的右上方。这三个顶点所在的位置就表明了哪三个人组成一组，把这些元素的记为11，即第一天的第一组；然后再选第二组：象上面的方式一样任选三个点，注意这些任一个点都不在前面选好的点所在的行和列中，把它们标记为12。依此方法把第一天组合好。进行第二天的时候，把标记的元素都画好圈，然后在剩下的元素中按第一天的方法组队，标上21，22，。。。等等。最后一天把上三角的元素都圈完了。可以编程实现。<

>一千块，呵呵[em02][em02]

btluo · 发表于 2004-12-6 00:07:59

<DIV class=quote>以下是引用huihong在2004-12-5 14:26:04的发言：
<

>把这15个人遍上号码1。2。。。15，这样构造一个15阶的矩阵A（15*15），严格上三角（不包括对角线）上的元素a（i，j），就表示在一次照相中第i个人和第j个人之间的关系，这些元素共有15*7个，一开始都为0，第一天，在这些元素中任选三个使他们连线组成一个直角三角形，其中直角顶点在斜边的右上方。这三个顶点所在的位置就表明了哪三个人组成一组，把这些元素的记为11，即第一天的第一组；然后再选第二组：象上面的方式一样任选三个点，注意这些任一个点都不在前面选好的点所在的行和列中，把它们标记为12。依此方法把第一天组合好。进行第二天的时候，把标记的元素都画好圈，然后在剩下的元素中按第一天的方法组队，标上21，22，。。。等等。最后一天把上三角的元素都圈完了。可以编程实现。
<

>一千块，呵呵[em02][em02]</DIV>
<

>huihong兄所提的方法非常巧妙，叹为观止！不过我发现有一个小小的问题，那就是表示一张合照的三个人关系的那个直角三角形的三个顶点并不是都是可以任意选取的。理由如下，例如i，j，k三个人合照，不妨设i<j<k,则表示这三人合照的直角三角形的三个顶点分别为a(i,j)、a(i,k)、a(j,k).那么,只要确定了其中的两个顶点,则第三个顶点也随之确定.在这仲约束条件下,该怎么样选取三角形,才能穷尽所有该有的组合呢?

btluo · 发表于 2004-12-6 00:40:47

<

>还有,其实每天只能拍5张照片,因为如果超过5张,必然会出现有人每天拍的照片超过1张的情况,而小于5张,就会出现有人没有拍的情况,均不合题意.由抽屉原理很容易证明上述结论.也就是说,七天下来,共拍了35张照片.而huihong兄的矩阵所包含的任意直角三角形个数要远远大于35,说明这些直角三角形中有很多是不需要的.那么怎样才能从这些直角三角形中找出需要的35个呢?

huihong · 发表于 2004-12-6 03:36:41

<

>btluo兄提的问题很好，其实一开始我也有这样的问题：就是是不是任意人数都可以以这样方式在一定的天数内刚好照完呢？或者是其它方式，比如四人合影等等。我觉得这个问题跟你提的问题有联系。不过我上面的贴子有措词不当的地方：比如说任意选三个点，这三个点正如btluo兄所说其实并不独立，还有上面所说“这些任一个点都不在前面选好的点所在的行和列中”，更确切的说法应该是它们不在某些对角元所在的行和列中，这些对角元是前面选好的人所对应的对角元，意思就是在选一组的时候不能从已经组好队的那些人中选。<

> 但是如果15个人，7天可以按上面方式照完（我没有证明，假设它成立），那么就肯定可以按矩阵方法找到一种照相的方式，也就是每天都可以在上面找出五个直角三角形，刚好形成五组，然后标上记号，而七天后刚好全部标上记号了。btluo兄很容易从这里知道，每天找这样的五个直角三角形并不是一定是唯一（这就是为什么其实直角三角形很多），也就是每天组队并不一定是唯一的。

huihong · 发表于 2004-12-6 04:02:50

<

> 其实在一种选的照相方式中，甲和乙合影的照片只有一张，假设另一人是丙，而在另一种选的照相方式中，另一人是丁，则在第一中选三角形时一定不会出现甲乙丁三人所对应的三角形。也就是，这七天选的所有三角形（35个）肯定不会是包括所有任意的三角形。<

> 如果在这过程中某一天找不齐五个这样的直角三角形，那么按这种方式就不能刚好照完，这就提出这样的问题：怎样的人数，多少天，每天多少人合影，就可以刚好全部人互相合影。一个很简单的，四个人，三天，每人每天一张两人照就刚好。一般的情形怎样呢，我也不清楚。<

> 还有，我想，其实解决这个问题如果巧妙转化其实应该有很多方法，包括下面：平面上有15个点，把它们两两连起来，共有15*7条，每天选15条，这15条由五组构成，每一组有三条，把三个点相连，选到的线跟所有的点构成五个互不相连的连通图，记下必要的记号，把这些选的线去掉，继续选连线。。。。

btluo · 发表于 2004-12-6 06:34:52

<

>呵呵，我们的方法其实殊途同归，我最上面提到的那种方法的目的其实是用一种算法先找出所有符合要求的35张照片，然后再对这35张照片分组，每组五张，每组一天。

btluo · 发表于 2004-12-6 06:50:25

关于推广，我有如下的设想，不过没有证明。当总人数为n、每张照片拍m人，并且满足n/m、（n-1）/（m-1）均为整数时，总共拍的照片数为（n/m）*[（n-1）/（m-1）]，每天拍n/m张，分（n-1）/（m-1）天拍完<IMG src="http://www.shumo.com/bbs/Skins/Default/emot/em01.gif"><IMG src="http://www.shumo.com/bbs/Skins/Default/emot/em01.gif">

huihong · 发表于 2004-12-7 00:29:26

我想这个猜想应该是对的,我也没证明出来,这几天也很忙,相信可以证明btluo可以证明[em07]

		自动登录	找回密码
密码			注-册-帐-号