柯克曼女生问题

在寄宿学校里有十五名女学生，她们总是三人成行进行日常散步。如何安排才能使每周每两位女生都恰好同排散步一次？这个问题的解等价于构造一个阶为的柯克曼三元组系统。

Falcone 和 Pavone (2011) 给出了一些引人入胜的可视化表示，以及该问题的可视化证明。上面的可视化展示了一个解决方案，其中每天的三元组表示为一组（七个）不同颜色的弧线 (E. Pegg, Jr., 私人通信，2022 年 1 月 29 日)。

下表给出了该问题的 7 个不同的（直到字母排列）解之一。

周日	ABC	DEF	GHI	JKL	MNO
周一	ADH	BEK	CIO	FLN	GJM
周二	AEM	BHN	CGK	DIL	FJO
周三	AFI	BLO	CHJ	DKM	EGN
周四	AGL	BDJ	CFM	EHO	IKN
周五	AJN	BIM	CEL	DOG	FHK
周六	AKO	BFG	CDN	EIJ	HLM

(Dörrie 1965 年的表格包含四处遗漏，其中星期三和星期四的和条目被简单地写为。)

有趣的是，将解决该问题的 35 个三元组中的每一个都视为图的顶点，并在共享一个女生的顶点之间绘制边，会得到一个图，该图与格拉斯曼图同构 (E. Pegg, Jr., 私人通信，2022 年 1 月 29 日)。

另请参阅

格拉斯曼图, 约瑟夫问题, 柯克曼三元组系统, 社交高尔夫球手问题, 斯坦纳三元组系统

使用探索

更多尝试

参考文献

Abel, R. J. R. and Furino, S. C. "Kirkman Triple Systems." §I.6.3 in The CRC Handbook of Combinatorial Designs (Ed. C. J. Colbourn and J. H. Dinitz). Boca Raton, FL: CRC Press, pp. 88-89, 1996.Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 287-289, 1987.Carpmael. Proc. London Math. Soc. 12, 148-156, 1881.Cole, F. N. "Kirkman Parades." Bull. Amer. Math. Soc. 28, 435-437, 1922.Dörrie, H. §5 in 100 Great Problems of Elementary Mathematics: Their History and Solutions. New York: Dover, pp. 14-18, 1965.Falcone, G. and Pavone, M. "Kirkman's Tetrahedron and the Fifteen Schoolgirl Problem." Amer. Math. Monthly 118, 887-900, 2011.Frost, A. "General Solution and Extension of the Problem of the 15 School Girls." Quart. J. Pure Appl. Math. 11, 26-37, 1871.Kirkman, T. P. "On a Problem in Combinatorics." Cambridge and Dublin Math. J. 2, 191-204, 1847.Kirkman, T. P. Lady's and Gentleman's Diary. 1850.Kraitchik, M. §9.3.1 in Mathematical Recreations. New York: W. W. Norton, pp. 226-227, 1942.Peirce, B. "Cyclic Solutions of the School-Girl Puzzle." Astron. J. 6, 169-174, 1859-1861.Ryser, H. J. Combinatorial Mathematics. Buffalo, NY: Math. Assoc. Amer., pp. 101-102, 1963.Woolhouse. Lady's and Gentleman's Diary. 1862-1863.

请引用为

Weisstein, Eric W. “柯克曼女生问题。” 来自 —— 资源。 https://mathworld.net.cn/KirkmansSchoolgirlProblem.html