主題
Search

柯克曼女生問題


在寄宿學校裡有十五名女學生,她們總是三人成行進行日常散步。如何安排才能使每週每兩位女生都恰好同排散步一次?這個問題的解等價於構造一個階為 n=2柯克曼三元組系統

KirkmansSchoolgirlProblem

Falcone 和 Pavone (2011) 給出了一些引人入勝的視覺化表示,以及該問題的視覺化證明。上面的視覺化展示了一個解決方案,其中每天的三元組表示為一組(七個)不同顏色的弧線 (E. Pegg, Jr., 私人通訊,2022 年 1 月 29 日)。

下表給出了該問題的 7 個不同的(直到字母排列)解之一。

週日ABCDEFGHIJKLMNO
週一ADHBEKCIOFLNGJM
週二AEMBHNCGKDILFJO
週三AFIBLOCHJDKMEGN
週四AGLBDJCFMEHOIKN
週五AJNBIMCELDOGFHK
週六AKOBFGCDNEIJHLM

(Dörrie 1965 年的表格包含四處遺漏,其中星期三和星期四的 a_1=Ba_2=C 條目被簡單地寫為 a。)

有趣的是,將解決該問題的 35 個三元組中的每一個都視為圖的頂點,並在共享一個女生的頂點之間繪製邊,會得到一個圖,該圖與 格拉斯曼圖 J_2(4,2) 同構 (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.tw/KirkmansSchoolgirlProblem.html

主題分類