免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 十男十女相亲(报名开始,得先解决猜想)

本帖最后由 realnumber 于 2018-5-5 09:32 编辑

改自这个连接
http://kuing.orzweb.net/viewthre ... page%3D1&page=1
十男十女的相亲节目,本来节目是这样安排的,轮换如图
16080509208a4d4a19bcf360ac.png
2016-8-7 18:55

其中有若干个特别漂亮的美女,以致前两轮不小心打乱了节目安排的次序.问接下来应该怎样安排,才能使得每个男女都恰好约会一次 .
不许男男,不许女女,只许一男一女,不许重复盯上同一个美女.
余姚三中 朱世杰  写这个是因为应付年度论文,说明不是抄袭。
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

本帖最后由 realnumber 于 2016-8-8 07:17 编辑

1楼安排方案可以任意两列或两行交换,仍旧成立.
集合{1,2,3,4,5,6,7,8,9,10}到自身的一个一一映射,用来替换图中1,2,..,10.则约会方案仍旧成立.

某方案P经若干次交换两列或两行或一一映射得到一个方案Q,(这两种似乎算一样的)称P,Q同构.
下面出现循环5+5等说明至少和本帖的循环10不是同构的.
假设出现这样情景,(说明1:A~J表示男人;o~x以及1~10表示女人;A(o,p)表示A第一次和o,第二次和p;A(2,4,7)表示前三次依次约会对象是2,4,7),
情景1.A(o,p), B(p,q),C(q,r),D(r,s),E(s,t),F(t,u),G(u.v),H(v,w),I(w,x),J(x,o)那么作这样一一映射
o~x依次对应1~10,正好是12楼图中已解决的问题.这只是情景1的一个解决方案,其他办法应该会很多吧,余下同.


情景2.A(o,p), B(p,o),C(q,r),D(r,q),E(s,t),F(t,s),G(u.v),H(v,u),I(w,x),J(x,w)
这样参考5男5女问题且只进行了一轮,把AB暂时看做一整体,op暂时看做一整体,其余同.(要没有节操才想得到,说错了,是要有创意)
本情景如下解答:
A(o,p,q,r,s,t,u,v,w,x)
B(p,o,r,q,t,s,v,u,x,w)
C(q,r,s,t,u,v,w,x,o,p),
D(r,q,t,s,v,u,x,w,p,o),
E(s,t,u,v,w,x,o,p,q,r),
F(t,s,v,u,x,w,p,o,r,q),
G(u.v,w,x,o,p,q,r,s,t),
H(v,u,x,w,p,o,r,q,t,s),
I(w,x,o,p,q,r,s,t,u,v),
J(x,w,p,o,r,q,t,s,v,u)

情景3.A(o,p),B(p,q),C(q,r),D(r,s),E(s,o),F(t,u),G(u,v),H(v,w),I(w,x),J(x,t)
模仿情景2,暂时把ABCDE,FGHIJ分别看做一整体,这样是2男2女问题,也类似解决.

(这样是找到了一个解决方案还是歧路呢?继续说明.说明2:这样前2轮的方案称为循环:A(o,p),B(p,o),为区别起见,称循环2;
这样称循环3:A(o,p),B(p,q),C(q,o);那么情景1是循环10,情景2是循环2+2+2+2+2,情景3是循环5+5;)

情景4:循环5+3+2
3+2解决如下A(o,p,s,r,q),B(p,q,r,o,s),C(q,o,p,s,r),D(r,s,o,q,p),E(s,r,q,p,o).再模仿情景3,这样就解决了情景4.

这样什么是尽头啊,再解决几条看看:
情景5: 循环5+4+1,呵呵,循环1不会出现,不会有5+2+2+1等等.这样说明出现循环5的情景已经全部考虑遍了.
还有6+4,6+2+2,7+3,8+2,4+4+2,4+3+3,4+2+2+2,3+3+2+2,没有其他了.

情景5:循环6+4,有可能同时解决了6+2+2,有公因数2,可以模仿情景2处理本条,有其它公因数也类似.
3+2在情景4中已经解决,所以6+4,6+2+2都成立.3+3+2+2看做(3+2)+(3+2)也解决了.

情景6.8+2,4+4+2以及4+2+2+2同情景5.解决了.

情景7.循环7+3,最后一条,也许是最难的,倒有些期待是反例,也许会学到更多.
这条解太奇怪,胡乱凑,居然可以了,也许这样的解很多.
如下:
A(1,2,5,10,9,8,6,7,3,4)
B(2,3,6,4,10,9,8,1,7,5)
C(3,4,7,5,6,10,9,8,1,2)
D(4,5,2,6,7,1,10,9,8,3)
E(5,6,4,7,1,2,3,10,9,8)
F(6,7,1,8,2,3,4,5,10,9)
G(7,1,3,9,8,4,5,6,2,10)
H(8,9,10,1,3,5,7,2,4,6)
I(9,10,8,2,4,6,1,3,5,7)
J(10,8,9,3,5,7,2,4,6,1)

结论:这样我们就解决了1楼提出的问题.因为1楼问题经过一一映射可以变换为情景1~情景7.

本来觉得很显然的问题,想不到还是有些弯弯,当然不排除做复杂了.可惜程序水平不是很高,否则也许会找到许多莫名其妙的解答吧.

TOP

本帖最后由 realnumber 于 2016-8-8 11:44 编辑

楼上的解答可以看到循环3+2,7+3,都存在相应的约会方案.
猜想:循环m+n,也存在相应的方案.
显然只需要证明(m,n)=1情景.
循环3+2的条件是:  解答是:
A(1,2)                           A(1,2,3,4,5)
B(2,3)                           B(2,3,5,1,4)
C(3,1)                           C(3,1,4,5,2)
D(4,5)                           D(4,5,1,2,3)
E(5,4)                           E(5,4,2,3,1),  也意味着循环5t+3+2都解决了,下面会用t=2的例子说明.
3 2和10转化为10 3 2.png
2016-8-8 08:36

循环4+3的条件是:  解答是:
A(1,2)                           A(1,2,3,7,5,6,4)
B(2,3)                           B(2,3,4,6,1,7,5)
C(3,4)                           C(3,4,1,2,6,5,7)
D(4,1)                           D(4,1,2,5,7,3,6)
E(5,7)                           E(5,7,6,1,3,4,2)
F(6,5)                           F(6,5,7,3,4,2,1)
G(7,6)                           G(7,6,5,4,2,1,3)
   这下是无穷无尽的问题,如果偶然解决了循环m+n,还有循环m+n+o,......
循环5+2的条件和解答:
A(1,2)                          A(1,2,3,5,7,6,4)
B(2,3)                          B(2,3,5,4,1,7,6)
C(3,4)                          C(3,4,6,1,5,2,7)
D(4,5)                          D(4,5,7,6,2,1,3)
E(5,1)                          E(5,1,4,7,6,3,2)
F(6,7)                           F(6,7,1,2,3,4,5)
G(7,6)                          G(7,6,2,3,4,5,1)

TOP

本帖最后由 realnumber 于 2018-4-20 20:31 编辑

7+2其中两个解决办法(图片上半部是条件,以及将要改动地方,黄色标记,下半部是解答),应该有别的
psb.jpg
2016-12-20 22:42

似乎找到了推广到一般的x+2的办法,试着检验下......
下图显示了循环9+2的解答的构造过程:
psb (1).jpg
2016-12-20 22:43

看来x+2大概就这样了,接下来该是x+3?,m+n,(m,n)=1
http://user.qzone.qq.com/171368366/2

5+3一个解,模仿x+2
QQ截图20161225165124aaa.png
2016-12-25 16:52

下一个8+3
如果也类似的话,m+n可能有简单的解释.
重新填了下循环7+3只能部分模仿x+2,而循环8+3不晓得怎么有规律地填,总感觉解应该有很多个。
QQ截图20180420202754-u.png
2018-4-20 20:29

TOP

本帖最后由 realnumber 于 2018-5-5 09:29 编辑

QQ截图20180505090423-8 3.png
2018-5-5 09:07

完全模仿上面循环m+2的排法没成功,对4~8行作了些行交换,得到一个循环8+3,也说明一般的办法更不好找了.

TOP

本帖最后由 realnumber 于 2018-5-6 21:34 编辑

QQ截图20180430134152---2.png
2018-5-5 21:09

这个循环10+3的排法同7+3,8+3,
毕竟1楼尝的是10种口味,这个是13种口味了
至少到目前例举的例子,两个拉丁方m阶和n阶是可以合并为m+n阶的.m<11,n=2,3

TOP

返回列表 回复 发帖