科克曼女生问题

Jenny · 发表于 2005-4-12 01:31:40

一个小组7个人，要安排他们做连续7天的值日，每天一组，每组三个人。要求一周下来，每个小组成员都要与小组内其他所有成员同在一组一次（且一次）做值日。按：这是著名科克曼女生问题最简单的特例。这个问题英国人科克曼于1850年提出的，原题是：一位女老师安排15个女生连续7天的散步，每天安排五组，每组3个人，要求7天下来，每个人与其他14个人都在一组一次且一次散步。这道题一般化后，原题就成了一个特例。我国数学家陆家羲于20世纪60年代独立解决了科克曼女生问题。

fzy · 发表于 2005-4-13 00:57:02

This method works for N = any 2^k - 1. For 15, ie Kirkman's original problem, the solution is

{1,2,3}, {1,4,5}, {1,6,7}, {1,8,9}, {1,10,11}, {1,12,13}, {1,14,15}

{2,4,6}, {2,5,7}, {2,8,10}, {2,9,11}, {2,12,14}, {2,13,15}

{3,4,7}, {3,5,6}, {3,8,11}, {3,9,10}, {3,12,15}, {3,13,14}

{4,8,12}, {4,9,13}, {4,10,14}, {4,11,15}

{5,8,13}, {5,9,12}, {5,10,15}, {5,11,14}

{6,8,14}, {6,9,15}, {6,10,12}, {6,11,13}

{7,8,15}, {7,9,14}, {7,10,13}, {7,11,12}

I do not know whether this solution satisfies Kirkman's other condition: Divide the 35 triples into 7 groups, so that every girl appears in each group exactly once.

乱弹 · 发表于 2005-4-12 21:44:36

妙！

fzy · 发表于 2005-4-12 20:22:39

Consider the classic NIM game: Given three piles of stones with 3, 5, and 7 in each pile. The players take any number of stones, but from one pile only. There are 7 winning states when none of the three piles is empty:

{1,2,3}, {1,4,5}, {1,6,7}, {2,4,6}, {2,5,7}, {3,4,7}, {3,5,6}.

These 7 groups also give a solution to this special problem.

In general, a solution exists if and only if N = 1 or 3 mod 6. ( http://mathworld.wolfram.com/SteinerTripleSystem.html )

Harbin · 发表于 2005-4-12 20:19:47

1, 2, 3, 4, 5, 6, 7

123, 145, 167, 246, 257, 347, 356.

		自动登录	找回密码
密码			立即注册

动态微博

科克曼女生问题

回复：An interesting solution

妙！

An interesting solution

回复：科克曼女生问题