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，发明人播种机。1987年中国上海天使杯智力玩具大奖赛纪念奖，寇克曼女生问题智力玩具,作者播种机。