| 作者 |
 [原创]喜欢数学的请进，请讨论。俺有根据的作了一种新的“三值逻辑算法“，如何扩展，如何找到实际的应用模式？ |
 |
| 所跟贴 |
交换律没戏了。 -- 勤劳 - (0 Byte) 2008-6-21 周六, 13:17 (422 reads) |
秀才
[博客]
[个人文集]
头衔: 海归少将
声望: 博导
性别: 
加入时间: 2005/06/16
文章: 8355
来自: 日本/上海
海归分: 232964
|
|
|
作者：秀才 在 海归茶馆 发贴, 来自【海归网】 http://www.haiguinet.com
Kirkman女生散步问题-播种机定理
播种机
Kirkman女生散步问题:女子学校的一班级有15个女生，她们每天3人一组地散步。问如何安排在一周内使任何女生
可以与其他女生在同组散步。
定义1: 符合Kirkman女生散步问题解的35种3人一组的组合为C(x,y,z),x,y,z为同一组女生的编码。
定理1(Kirkman女生散步问题-播种机定理1):
符合Kirkman女生散步问题解的一天的5个C(x,y,z)组合的最大可能组合数为56种.
证明: 首先任意选取定义1中35种C中的任意一种，标记为C１(1,2,3)，作为第１层，符合定义１而且包含1
的c1有７种，符合定义１包含2但是不包含1的c2有6种,符合定义１包含3但是不包含1的c3有6种,共7+6+6=19种.因为
C(1,2,3)已经出现，所以据定义１不存在c(2,3,x),即是上述19种没有重叠。
然后选取第２层，符合定义１的第２层可以选取C的种类有35-19=16种.标记已经选取的第２层为C2(4,5,6)。
假设不包含C2但是包含４的c为c4, 不包含C2但是包含5的c为c5,不包含C2但是包含6的c为c6,那么所有不包含C2但是包含4／5／6的cC2-456种类为c4+c5+c6=6+6+6=18种,加上C2，就是所有包含4/5/6的c456为19种。
据定义１，包含4／5／6的c1有3种，标记为c1-456,同样包含4/5/6的c2有3种,标记为c2-456,包含4/5/6的c3有3种
标记为c3-456。c1-456 + c2-456 + c3-456 =3+3+3=9,即是包含4／5／6但是不包含1/2/3的c456-123共有9种。
所有c456减去c456-123为19-9=10,就是按定义１与C2(4,5,6)不能同排在同一天的c有10种。也就是第３层符合定义１的
可选种类只有(35-19)-10=6种。
最后选取第３层，显然第3层C3选定后，第４，５层C4,C5只有唯一选择。以下证明按照定义１如果存在3层C1C2C3，那么一定存在符合定义1的第4，5层C4C5。反证法，假设对于所有符合定义1的任意选定的C1C2C3，不存在符合定义1的C4C5。
那么由于定义1一定有一种解的条件，对于解的某特定C1C2C3，存在4C5，即是假设不成立。所以如果任意选定符合定义1的３层C1C2C3，那么一定存在符合定义1的第4,5层特定C4C5。
定义1的一天有５层C，５层C中任意排列1层C的所有可能的排列数为5x4x3=60种。
从任意35种中选出符合定义1的3层的所有可能的排列数为35x16x6=3360种。
按照定义1选定3层的所有可能组合数为3360/60=56种.由于前述选定3层就是决定第4,5层，所以定理1中最大可能组合数为56种的命题成立。
定理2: (Kirkman女生散步问题-播种机定理2): 符合Kirkman女生散步问题解(一周)的最大可能组合数为240种.
已经完成借助计算机程序的证明，人工证明未完成。
参考，中国实用新型专利87202939，发明人播种机。
作者：秀才 在 海归茶馆 发贴, 来自【海归网】 http://www.haiguinet.com
|
|
|
| 返回顶端 |
|
 |
|
| |
|
|
|
您不能在本论坛发表新主题, 不能回复主题, 不能编辑自己的文章, 不能删除自己的文章, 不能发表投票, 您 不可以 发表活动帖子在本论坛, 不能添加附件不能下载文件, |
|
|
