カークマンの女子高生問題

カークマンの女学生問題は、 1850年にトーマス・ペニントン・カークマンが『淑女と紳士の日記』 （48ページ）のクエリVIとして提起した組み合わせ論の問題である。その問題は以下の通りである。

学校の15人の女子生徒が7日間連続で3列縦隊で歩く。毎日、2人が2回横並びにならないように配置する必要がある。^{[ 2 ]}

この問題の解決策は、カークマン三重システムの例です^{[ 3 ]。}これは、並列性を持つシュタイナー三重システム、つまり、三重システムのブロックを並列クラスに分割し、その並列クラス自体が点を互いに素なブロックに分割するものです。このような並列性を持つシュタイナーシステムは、可解とも呼ばれます。

フランク・ネルソン・コールが1922年にカークマン・パレードで最初に挙げたように、女子生徒問題には正確に7つの非同型解が存在する。 ^{[ 4 ]} 7つの解は下の表にまとめられており、15人の女子生徒はAからOの文字で示されている。

各解に対する自己同型写像​​の数と自己同型群の定義から、同型解を含む解の総数は次のようになる。

${\displaystyle 15!\times \left({\frac {1}{168}}+{\frac {1}{168}}+{\frac {1}{24}}+{\frac {1}{24}}+{\frac {1}{12}}+{\frac {1}{12}}+{\frac {1}{21}}\right)}$

${\displaystyle =15!\times {\frac {13}{42}}}$

${\displaystyle =404,756,352,000}$

${\displaystyle =2^{10}\times 3^{5}\times 5^{3}\times 7\times 11\times 13^{2}}$。

この問題には長く複雑な歴史がある。このセクションは、ロビン・ウィルソン^{[ 5 ]}とルイーズ・ダフィールド・カミングス^{[ 6 ]}がそれぞれ異なる時期に行った歴史的研究に基づいている。その歴史は以下のとおりである。

• 1844年、当時『レディーズ・アンド・ジェントルマンズ・ダイアリー』の編集者であったウェズリー・ウールハウスは、「 n個の記号から作れる組み合わせの数を決定せよ。各記号はp個である。ただし、いずれか1つに含まれるq個の記号の組み合わせは、他のいずれにも重複してはならない」という制約がある。回答は2つしか得られず、1つは誤り、もう1つは正しく質問に答えていた。${\textstyle {\frac {n!}{q!(nq)!}}\div {\frac {p!}{q!(pq)!}}}$質問では組み合わせの数以外に何も求められていなかったため、そのような解が得られる条件となるn、p、qについては何も得られませんでした。
• 1846年、ウールハウスは「 n個の記号から、どの記号のペアも複数回含まれないような三つ組をいくつ作ることができるか？」と問いかけた。これは、 p = 3、q = 2の値で1844年の問いを繰り返すことと同等である。^{[ 5 ]}
• 1847年、41歳のトーマス・カークマンは、「組み合わせの問題について」（Kirkman 1847 ）という論文を発表し、 n = 1または3 ( mod 6) の次数nの三重システムを構築する問題を包括的に記述し解決した。完全なバランスは不可能であるにもかかわらず、彼はnの他の値も考慮した。彼は、 n = 7、15、19、27などの2つの異なる三重システムのシーケンスと、 n = 9、13、25などの別のシーケンスを示した。これらの命題を使用して、彼はn = 1または3 (mod 6)のすべての値に対して三重システムが存在することを証明した^{[ 6 ]} （必ずしも分解可能なものではなく、一般的な三重システム）。彼はまた、その論文で、特にn = 9と15の場合の分解可能な三重システムを詳細に記述した。分解可能な三重システムは現在、カークマン三重システムとして知られている。彼は、他のnの値に対して分解可能な三重システムが存在するかどうかを決定的に言うことはできなかった。その問題は1960年代まで解決されなかった（下記参照）。
• 1850年、カークマンは15人の女学生問題を提起したが、これは彼がすでに書いていた1847年の論文よりもはるかに有名になった。いくつかの解が寄せられた。カークマン自身も解を与えた^{[ 7 ]}が、後に上記の解Iと同型であることが判明した。カークマンはそれが唯一の可能な解だと主張したが、それは間違いだった。アーサー・ケイリーの解^{[ 8 ]}は、後に解IIと同型であることが判明した。どちらの解もPG(3,2)に埋め込むことができたが、その幾何学は当時知られていなかった。しかし、女学生問題の解を発表する際、カークマンは読者に自身の1847年の論文を参照させることを怠り、この省略は後述するように発明と優先権に重大な影響を与えることになった。
• また1850年には、ジェームズ・ジョセフ・シルベスターは、15人の女学生の問題に対して、すべての${\textstyle {15 \選択 3}=455}$全体でちょうど1回三塁打を記録し、${\displaystyle 455=13\times 35}$つまり、13週間毎日行進する中で、2人の少女が毎週ちょうど1回一緒に行進し、3人の少女が13週間の間にちょうど1回一緒に行進することは可能でしょうか？この問題ははるかに難しく、最終的に1974年にRHFデニストンによって計算による解が提示されました（下記参照）。
• 1852年、ロバート・リチャード・アンスティスは、15個の記号0ABCDEFGabcdefgの上に、最初の日の5つのトリプルを0Gg、AbC、aDE、cef、BdFと構成し、その後、0は変更せずに（大文字は大文字のまま、小文字は小文字のまま）毎日1文字ずつ周期的にずらすことで、巡回解を提供した。^{[ 5 ]} 0要素を含まない4つのトリプル（AbC、aDE、cef、BdF）を取り、大文字を小文字に変換すると（abc、ade、cef、bdf ）、後にパッシュ構成と呼ばれるものが形成される。^{[ 9 ]}パッシュ構成は、20世紀の同型棄却技術において重要になる。
• 1853年、ヤコブ・シュタイナーは、カークマンの1847年の論文を全く知らずに、「組み合わせ的課題」と題する論文を発表し、三重系の概念を再導入したが、別々の並列クラスへの分解可能性については言及しなかった。シュタイナーは、nが1または3（mod 6）である必要があると指摘したが、これがいつ実現されるかについては未解決の問題を残した。カークマンが1847年にすでにその問題を解決していたことを知らなかった。この論文がヨーロッパの数学界で広く読まれたため、三重系は後にシュタイナー三重系として知られるようになった。^{[ 5 ]}
• 1859年、ミシェル・ライスはシュタイナーが提起した疑問に答えたが、その方法論と記法はカークマンの1847年の著作と非常に似ていた（カークマンに言及することなく）。そのため、ルイーズ・カミングスなどの後世の著者は彼を盗作だと非難した。^{[ 6 ]}カークマン自身も憤慨していた。
• 1860年、ベンジャミン・パースはこれまで提示されてきたいくつかの異なる解を統一し、アンスティスの研究に対応するもの、カークマンの解に基づくもの、ケイリーの解に基づくものの3つの可能な循環解構造があることを示した。^{[ 5 ]}
• 1861年、ジェームズ・ジョセフ・シルベスターはこの問題を再び取り上げ、自分がそれを発明したと主張し、カークマンの研究の源泉は自分のケンブリッジでの講義だったと主張しようとした。カークマンはすぐに彼の主張を否定し、論文を書いたときにはケンブリッジに行ったことも、シルベスターの研究について聞いたこともなかったと述べた。^{[ 5 ]}この優先権争いは、シルベスターとカークマンの間の仲違いにつながった。
• 1861年から1862年にかけて、カークマンはアーサー・ケイリーと別の件（ケイリーがカークマンの群論と多面体に関する一連の論文を出版しなかったため、ヨーロッパの数学界でカークマンの評価が下がったこと）で仲違いし、数学界からさらに疎外されることになった。特に1847年の彼の包括的な論文は忘れ去られ、多くの後世の著者は、その経緯を知らずにシュタイナーかライスに功績を帰していた。
• カークマンの学問上の対立は、女子生徒パズル自体の人気には影響せず、19 世紀後半から 20 世紀初頭にかけて、このパズルはエドゥアール・リュカ^{[ 10 ]} 、ラウズ・ボール^{[ 11 ]} 、ヴィルヘルム・アーレンス[ ¹² ] 、ヘンリー・デューデニー^{[ 13 ]}による娯楽数学の本にいくつか掲載された。カークマンは生前、女子生徒問題の人気によって自身の真面目な数学研究が影を潜めてしまったと不満を漏らしていた [ 6 ]。^{カークマンは1895年に亡くなっ}た。
• 1918年、カークマンの真摯な数学研究は、ルイーズ・ダフィールド・カミングスによる「過小評価されたカークマン論文」^{[ 6 ]}という論文で再び広く注目を集め、この分野の初期の歴史について論じ、歴史的な見落としを正した。
• ほぼ同時期に、カミングスはフランク・ネルソン・コールとヘンリー・シーリー・ホワイトと共に三重系について研究していた。その成果は、1919年に発表された彼らの有名な論文「 15要素の三重系の完全分類」^{[ 14 ]}に結実した。この論文は、15要素のシュタイナー三重系の80個の解を初めて提示したもので、解ける系と解けない系の両方が含まれていた。
• 1922年、コールは論文「カークマン・パレード」^{[ 4 ]}を発表し、15人の女学生問題に対する7つの非同型解を初めて列挙し、1850年代以来の長年の疑問に答えた。7つのカークマン解は、並列クラスへの分解可能性を制約から取り除いた場合、4つの異なるシュタイナーシステムに対応する。3つのシュタイナーシステムは、並列クラスに分割できる方法が2つあり、それぞれ2つのカークマン解が存在するが、4つ目は1つしかなく、合計で7つのカークマン解が存在する。
• 1960年代には、すべての次数n = 3 (mod 6) に対してカークマン三重系が存在することが証明されました。これは、 1965年に陸家羲(中国語:陸家羲) によって最初に証明され、^{[ 15 ]}彼はそれをActa Mathematica Sinicaに投稿しましたが、同誌は問題がすでに解決されていると誤って考え、1966 年に彼の論文を却下しました。これは後に重大な間違いであることが判明しました。^{[ 16 ]}その後の彼の学術的貢献は文化大革命によって中断され、再び却下されました。1968 年、一般化された定理はDK Ray-ChaudhuriとRM Wilsonによって独立に証明されました。^{[ 17 ]}
• 1974年、RHFデニストンは、13個の互いに素なカークマン解を構築し、それらを使用して15人の少女の455個のトリプルすべてをカバーするというシルベスター問題を解決しました。^{[ 18 ]}彼の解については以下で説明します。

1850年にジェームズ・ジョセフ・シルベスターは、それぞれ35個の3つ組からなる13個の互いに素なカークマンシステムを構築して、すべての${\textstyle {15 \選択 3}=455}$15 人の女子生徒の 3 つ組。1974 年にレスター大学のRHF Denniston がコンピュータで構築するまで、解決策は見つかりませんでした。 ^{[ 18 ]} Denniston の洞察は、サイクル長 13 の特定の順列に従って順列化して、後続の週の互いに素な解決策を作成できるような方法で、1 週間のカークマンの解決策を作成することでした。彼は、(1 2 3 4 5 6 7 8 9 10 11 12 13)(14)(15) のような 1 つの 13 サイクルと 2 つの固定点を持つ順列を選択しました。この順列の下では、123 のような 3 つ組は、234、345、... (11、12、13)、(12、13、1)、(13、1、2) にマッピングされてから繰り返されます。デニストンは、455個の3つ組をそれぞれ13個の3つ組からなる35の行に分類した。各行は、順列の下での特定の3つ組の軌道である。^{[ 18 ]}シルベスター解を構築するには、1週間のカークマン解で同じ行の2つの3つ組を使用することはできない。そうしないと、順列がどちらか一方に適用されたときに、最終的に衝突してしまうからである。シルベスター問題を解くことは、35の行それぞれから1つの3つ組を見つけて、35個の3つ組が一緒にカークマン解になるようにすることと同等である。彼は次に、エリオット4130コンピュータにまさにその検索を実行するように依頼し、この最初の週の解を見つけるのに7時間かかった。^{[ 18 ]} 15人の少女にAからOまでの文字をラベル付けした。

1日目 ABJ CEM FKL HIN DGO 2日目 ACH DEI FGM JLN BKO 3日目 ADL BHM GIK CFN EJO 4日目 AEG BIL CJK DMN FHO 5日目 AFI BCD GHJ EKN LMO 6日目 AKM DFJ EHL BGN CIO 7日目 BEF CGL DHK IJM ANO 

彼はその時点で捜索を中止し、独自性を確立しようとはしなかった。^{[ 18 ]}

アメリカのミニマリスト作曲家トム・ジョンソンは、デニストンの解決策に基づいて「カークマンの淑女たち」という曲を作曲した。 ^{[ 19 ] [ 20 ]}

2021年現在、シルベスター問題には他にも同型でない解が存在するのか、また解がいくつ存在するのかは不明である。

1日目：123 456 789 2日目：147 258 369 3日目：159 267 348 4日目：168 249 357 

解決策1： 1日目 2日目 3日目 4日目 第 1 週 ABC.DEF.GHI ADG.BEH.CFI AEI.BFG.CDH AFH.BDI.CEG 第2週 ABD.CEH.FGI ACF.BGH.DEI AEG.BCI.DFH AHI.BEF.CDG 3 週目 ABE.CDI.FGH ACG.BDF.EHI ADH.BGI.CEF AFI.BCH.DEG 4 週目 ABF.CEI.DGH ACD.BHI.EFG AEH.BCG.DFI AGI.BDE.CFH 5 週目 ABG.CDE.FHI ACH.BEI.DFG ADI.BCF.EGH AEF.BDH.CGI 6 週目 ABH.CDF.EGI ACI.BDG.EFH ADE.BFI.CGH AFG.BCE.DHI 第 7 週 ABI.CFG.DEH ACE.BFH.DGI ADF.BEG.CHI AGH.BCD.EFI 

解決策2： 1日目 2日目 3日目 4日目 第 1 週 ABC.DEF.GHI ADG.BEH.CFI AEI.BFG.CDH AFH.BDI.CEG 第2週 ABD.CEH.FGI ACF.BGH.DEI AEG.BCI.DFH AHI.BEF.CDG 3 週目 ABE.CGH.DFI ACI.BFH.DEG ADH.BGI.CEF AFG.BCD.EHI 第 4 週 ABF.CGI.DEH ACE.BDG.FHI ADI.BCH.EFG AGH.BEI.CDF 5 週目 ABG.CDI.EFH ACH.BDF.EGI ADE.BHI.CFG AFI.BCE.DGH 6 週目 ABH.CEI.DFG ACD.BFI.EGH AEF.BCG.DHI AGI.BDE.CFH 7 週目 ABI.CDE.FGH ACG.BDH.EFI ADF.BEG.CHI AEH.BCF.DGI 

1910年に、ジョージ・コンウェルはガロア幾何学を用いてこの問題に取り組んだ。^{[ 23 ]}

2つの要素を持つガロア体GF(2)を4つの同次座標で組み合わせ、15個の点、3つの点が1つの直線上に、7つの点と7つの直線が平面上にあるPG(3,2)を形成します。平面は、対角線上の点を通る直線とともに完全な四角形とみなすことができます。各点は7つの直線上にあり、直線は全部で35本あります。

PG(3,2)の直線は、 PG(5,2)におけるプリュッカー座標によって63点で識別され、そのうち35点がPG(3,2)の直線を表す。これらの35点は、クライン二次曲面として知られる曲面Sを形成する。Sから外れた28点それぞれに対して、Sと交わらない直線が6本存在する。^{[ 23 ] : 67}

1週間は7日間なので、7日間という単位は解決策の重要な部分を占めます。

直線ABC上の2点AとBを選んだとき、Aを通る他の5本の直線はそれぞれ、Bを通る他の5本の直線のうち1本とだけ交わる。これらの直線のペアの交点によって決まる5つの点と、2点AとBを合わせて「ヘプタッド」と呼ぶ。^{[ 23 ]： 68}

七和群は、その任意の2点によって決定される。Sの28点のそれぞれが2つの七和群に含まれる。七和群は8つ存在する。射影線形群PGL(3,2)は、8つの七和群上の交代群と同型である。^{[ 23 ] : 69}

女子生徒問題とは、5次元空間において互いに交わらず、かつ任意の2つの直線が常に7つの共通部分を持つような7つの直線を見つけることである。^{[ 23 ]： 74}

PG(3,2)では、点を線に分割することをスプレッドと呼び、線をスプレッドに分割することをパッキングまたは平行性と呼ぶ。^{[ 24 ] : 66}スプレッドは56種類、パッキングは240種類ある。ヒルシュフェルドは著書『3次元有限射影空間』 （1985年）でこの問題を考察した際、いくつかの解がPG(3,2)のパッキングに対応しており、それは基本的にコンウェルが上で述べたものと同じであると指摘し、^{[ 24 ] : 91}そのうち2つを提示した。^{[ 24 ] : 75}

この問題は以下のように一般化できる。${\displaystyle n}$女の子たち、${\displaystyle n}$3の奇数倍でなければならない（つまり${\displaystyle n\equiv 3{\pmod {6}}}$）、三つ子で歩く${\textstyle {\frac {1}{2}}(n-1)}$数日間、ただし、同じ列を2回歩く少女のペアはいないという条件が再び課せられる。この一般化の解は、シュタイナー三重系、すなわち、平行性を持つS(2, 3, 6 t + 3)（つまり、6 t + 3個の要素のそれぞれが、3要素セットの各ブロックでちょうど1回出現するもの）であり、カークマン三重系として知られている。^{[ 25 ]}カークマンが最初に議論したのはこの問題の一般化であり、有名な特殊ケースは${\displaystyle n=15}$後に提案された。^{[ 26 ]}一般的な場合の完全な解は、1968 年にDK Ray-ChaudhuriとRM Wilsonによって発表されたが、 ^{[ 17 ]} 1965 年にLu Jiaxi (中国語:陆家羲)によって既に解決されていたが、 ^{[ 15 ]}当時は発表されていなかった。^{[ 16 ]}

基本的な問題の多くのバリエーションが考えられる。アラン・ハートマンは、どの3人組も4人組の列を1回以上歩かないという条件で、シュタイナー四重システムを使用してこの種の問題を解決している^{[ 27 ]}。

最近では、「ソーシャルゴルファー問題」と呼ばれる同様の問題が注目を集めている。これは、10日間にわたって毎日異なる人と4人ずつのグループでプレーしたいと考える32人のゴルファーに関する問題である。

これはすべてのグループが直交する再編成戦略であるため、2人が同じグループに2度属することのない、大きなグループをより小さなグループに編成するという問題におけるこのプロセスは、直交再編成と呼ばれる。^{[ 28 ]}

解決可能な被覆問題は、一般的な${\displaystyle n}$女の子たち、${\displaystyle g}$グループの場合、各ペアの少女はいつか同じグループにいなければなりませんが、できるだけ少ない日数で済ませたいのです。これは、たとえば、各ペアのゲストがいつか同じテーブルに座らなければならないローテーションテーブルプランをスケジュールするために使用できます。^{[ 29 ]}

完全グラフを与えられた2正則グラフの辺素なコピーに分解するオーバーウォルファッハ問題は、カークマンの女子生徒問題を一般化したものである。カークマンの問題は、 2正則グラフが5つの互いに素な三角形から構成されるオーバーウォルファッハ問題の特殊なケースである。^{[ 30 ]}

• 教室での授業における相互作用を高めるための協同学習戦略
• ドブルカードゲーム^{[ 31 ]}
• プログレッシブディナーパーティーのデザイン
• スピードネットワーキングイベント
• スポーツ競技
• 組み合わせ論
• RMウィルソン
• ディジェン・K・レイ＝チョードゥリ
• 離散数学

• クラライヒ、エリカ（2015年6月9日）「デザインを使わずに解決したデザインのジレンマ」、クアンタマガジン
• String (2015年3月) - ソリューションの視覚化、Stack Exchange