Kirkmanの女学生問題
概要
Kirkmanの女学生問題（Kirkman's schoolgirl problem）とは、15 人の女学生が毎日 3 人ずつ 5 組で散歩するとき、どの 2 人もちょうど 1 日だけ同じ組になるように 7 日分の組分けを決められるかという問題である。解は、Steiner の三重系 $S(2,3,15)$ のブロックを、全員をちょうど 1 回ずつ含む平行類に分けたもの（解決可能な系、Kirkman 三重系）と同じで、$\mathbb{Z}/7\mathbb{Z}$ による巡回的な構成で実際に得られる。Kirkman 三重系が存在するなら点の個数 $v$ は $v\equiv3\pmod 6$ を満たし、逆にこの条件を満たすすべての $v$ で存在することを Ray-Chaudhuri と Wilson が示した。
15 人の女学生が、毎日 3 人ずつ 5 つの組に分かれて散歩する。どの 2 人も、同じ組で歩くのがちょうど 1 日になるように、7 日分の組分けを決められるか。これが Kirkman の女学生問題（Kirkman's schoolgirl problem）である。答えは「できる」で、たとえば 15 人に $\infty,0,1,\dots,6,0',1',\dots,6'$ と名前を付け、第 1 日を
$$
\{\infty,0,0'\},\quad\{1,2,4\},\quad\{3,1',5'\},\quad\{5,4',6'\},\quad\{6,2',3'\}
$$
とし、以後は毎日すべての番号に $1$ を足して $7$ を法として読めばよい（thm-kirk-fifteen）。
どの 2 人もちょうど 1 つの組に入る 3 人組の集まりは Steiner の三重系 $S(2,3,15)$（Steiner系）である。女学生問題では、それに加えて組の全体を「1 日分」ずつ、全員をちょうど 1 回ずつ含む組に分けることが求められる。この性質を 解決可能（resolvable）といい、解決可能な Steiner の三重系を Kirkman 三重系 という。Kirkman 三重系が存在するのは、点の個数 $v$ を $6$ で割った余りが $3$ のときに限る。この必要条件は数え上げで示せ、逆に $v\equiv3\pmod6$ ならば必ず存在することを Ray-Chaudhuri と Wilson が 1971 年に示した（RS88 p. 125）。
この記事では、解決可能性と Kirkman 三重系を定義し、女学生問題が 7 日を超えられないことと、7 日の解が $15$ 点の Kirkman 三重系と同じものであること（prop-kirk-equiv）、存在の必要条件 $v\equiv3\pmod 6$（thm-kirk-necessary）、$9$ 点の例（ex-kirk-nine）、上の 15 人の解が実際に条件を満たすこと（thm-kirk-fifteen）を証明し、Ray-Chaudhuri–Wilson の存在定理を述べる。
定義
以下、$(X,\mathcal B)$ を有限集合 $X$ と、その $k$ 元部分集合（ブロック）からなる集合 $\mathcal B$ の組とする。Steiner系 の定義「Steiner 系」のとおり、$X$ の任意の 2 元部分集合がちょうど 1 つのブロックに含まれるとき、$(X,\mathcal B)$ は $S(2,k,v)$（$v=\lvert X\rvert$）であり、$k=3$ のものを Steiner の三重系という。
- $\mathcal P\subseteq\mathcal B$ の元が互いに交わらず、その和集合が $X$ になるとき、$\mathcal P$ を 平行類（parallel class）という。
- $\mathcal B$ を平行類 $\mathcal P_1,\dots,\mathcal P_m$ の互いに交わらない和に分けたもの $\mathcal R=\{\mathcal P_1,\dots,\mathcal P_m\}$ を、$(X,\mathcal B)$ の 分解（resolution）という。
- 分解をもつ $(X,\mathcal B)$ を 解決可能（resolvable）という。分解可能 ともいう。
平行類の中の各ブロックは $k$ 点を含み、平行類は $X$ を分割するので、平行類のブロックの個数は $v/k$ である。解決可能性はブロックの集まり $\mathcal B$ の性質で、分解そのものは一通りとは限らない。
Steiner の三重系 $(X,\mathcal B)$ と、その分解 $\mathcal R$ の組 $(X,\mathcal B,\mathcal R)$ を Kirkman 三重系（Kirkman triple system）といい、$\lvert X\rvert=v$ のとき $\mathrm{KTS}(v)$ と書く。
この定義は RS88 p. 125 の定義（解決可能な $(v,3,1)$-ブロックデザイン）と同じである。ブロックデザインの一般論は 組合せデザイン にある。女学生問題では、$X$ が女学生の集合、ブロックが組、平行類が 1 日分の組分けにあたる。
女学生問題の言い換え
15 人の女学生の集合 $X$ について、各日 $X$ を 3 人ずつ 5 組に分ける。どの 2 人も同じ組になるのは高々 1 日であるとする。
- 日数は $7$ 以下である。
- 日数がちょうど $7$ なら、どの 2 人もちょうど 1 日だけ同じ組になる。したがって 7 日分の組の全体を $\mathcal B$、各日の組分けを平行類とする $\mathcal R$ とすると、$(X,\mathcal B,\mathcal R)$ は $\mathrm{KTS}(15)$ である。
- 逆に、どの $\mathrm{KTS}(15)$ も平行類をちょうど $7$ 個もち、各平行類を 1 日分とすれば女学生問題の解になる。
- 女学生 $x$ を固定する。$x$ は毎日、自分の組の 2 人と歩く。異なる日の相手は条件により重ならないので、日数を $D$ とすると相手は全部で $2D$ 人いて、$2D\le14$、すなわち $D\le7$ である。
- $D=7$ なら、$x$ の相手は $2\cdot7=14$ 人で、これは $x$ 以外の全員である。よってどの $y\ne x$ も、ちょうど 1 日だけ $x$ と同じ組になる。とくに $x,y$ を含む組はちょうど 1 つで、$(X,\mathcal B)$ は $S(2,3,15)$ である（異なる日の組が集合として一致すると、その中の 2 人が 2 日同じ組になるので、$\mathcal B$ には $35$ 個の相異なる組がある）。各日の組分けは $X$ の分割なので平行類であり、7 日分で $\mathcal B$ が分けられているから $\mathcal R$ は分解である。
- $S(2,3,15)$ のブロックの個数は Steiner系 の定理「$i$ 点を含むブロックの個数」により $\binom{15}{2}/\binom32=35$ で、各平行類は $15/3=5$ 個のブロックからなるので、平行類は $35/5=7$ 個ある。各平行類は 1 日分の組分けで、どの 2 人もちょうど 1 つのブロック、したがってちょうど 1 日だけ同じ組になる。$\square$
存在の必要条件
$\mathrm{KTS}(v)$ が存在するなら $v\equiv3\pmod6$ である。このとき平行類の個数は $(v-1)/2$、各平行類のブロックの個数は $v/3$、ブロックの総数は $v(v-1)/6$ である。
$(X,\mathcal B,\mathcal R)$ を $\mathrm{KTS}(v)$ とする。1 点 $x$ を含むブロックは、$x$ 以外の $v-1$ 点を 2 点ずつに分けるので、その個数は $r=(v-1)/2$ で、$v$ は奇数である。2 点の組 $\binom v2$ 個はそれぞれちょうど 1 つのブロックに含まれ、各ブロックは 3 組を含むので、ブロックの個数は $b=v(v-1)/6$ で、$v(v-1)$ は $3$ で割り切れる。ここまでは $S(2,3,v)$ についての議論で、$v\equiv1,3\pmod6$ が従う（Steiner系 の例「Steiner の三重系の条件」）。
一方、平行類 $\mathcal P\in\mathcal R$ は $X$ を 3 点ずつに分割するので $3\mid v$ である。$v\equiv1\pmod6$ なら $v\equiv1\pmod3$ で $3\nmid v$ だから、$v\equiv3\pmod6$ である。
$x$ は各平行類のちょうど 1 つのブロックに含まれ、$x$ を含むブロックはどれもちょうど 1 つの平行類に属するので、平行類の個数は $x$ を含むブロックの個数 $r=(v-1)/2$ に等しい。各平行類のブロックは $v/3$ 個である。$\square$
ブロックの大きさが一般の $k$ でも同じ議論が使える。解決可能な $S(2,k,v)$ では、1 点を含むブロックの個数 $(v-1)/(k-1)$ が整数であり、平行類があるので $k\mid v$ である。$k$ と $k-1$ は互いに素なので、中国剰余定理 により、$v\equiv0\pmod k$ と $v\equiv1\pmod{k-1}$ をあわせた条件は $v\equiv k\pmod{k(k-1)}$ と同値である（$k$ 自身がこの 2 つを満たす）。$k=3$ で上の $v\equiv3\pmod6$ になる。
$X=(\mathbb Z/3\mathbb Z)^2$ の 9 点と、$a\in X$、$d\in D:=\{(1,0),(0,1),(1,1),(1,2)\}$ による「直線」$L(a,d)=\{a+sd\mid s\in\mathbb Z/3\mathbb Z\}$ の全体 $\mathcal B$ を考える（12 本ある）。Steiner系 の例「Steiner の三重系の条件」のとおり $(X,\mathcal B)$ は $S(2,3,9)$ である。さらに、方向 $d$ を固定した 3 本の直線 $\mathcal P_d=\{L(a,d)\mid a\in X\}$ は平行類で、$\mathcal R=\{\mathcal P_d\mid d\in D\}$ は分解になる。
実際、$L(a,d)$ と $L(a',d)$ が点 $a+sd=a'+s'd$ を共有すれば $a'=a+(s-s')d\in L(a,d)$ で、$L(a',d)=\{a+(s-s'+s'')d\}=L(a,d)$ である。よって方向 $d$ の直線は一致するか交わらないかで、各直線は 3 点、全体は 9 点なので、方向 $d$ の直線はちょうど 3 本あって $X$ を分割する。$L(a,d)$ の相異なる 2 点の差は $\pm d$ であり、$D$ の相異なる 2 元は互いに $\pm$ の関係にないので、方向の異なる直線は異なる。よって $D$ の 4 方向で $4\cdot3=12$ 本の相異なる直線が現れ、$\mathcal B$ は 4 つの平行類に分かれる。$v=9$ では平行類の個数 $(9-1)/2=4$ も thm-kirk-necessary と合う。9 人の女学生を 4 日間、3 人ずつ 3 組で歩かせる問題の解がこれで得られる。
一方、Fano平面 $S(2,3,7)$（Steiner系 の例「Fano 平面」）は Steiner の三重系だが、$7$ は $3$ で割り切れないので平行類を 1 つももたず、解決可能でない。Steiner の三重系であることと解決可能であることは別の条件である。
15 人の解の構成
点の集合を
$$
X=\{\infty\}\cup\{0,1,\dots,6\}\cup\{0',1',\dots,6'\}
$$
とする。番号 $0,\dots,6$ は $\mathbb Z/7\mathbb Z$ の元（剰余類）とみなす。$s\in\mathbb Z/7\mathbb Z$ について、写像 $\tau_s\colon X\to X$ を $\tau_s(\infty)=\infty$、$\tau_s(a)=a+s$、$\tau_s(a')=(a+s)'$ で定める。$\tau_s$ は全単射で、$\tau_s\circ\tau_{s'}=\tau_{s+s'}$ である。
$$
\mathcal P_0=\bigl\{\{\infty,0,0'\},\ \{1,2,4\},\ \{3,1',5'\},\ \{5,4',6'\},\ \{6,2',3'\}\bigr\}
$$
とし、$\mathcal P_s=\{\tau_s(B)\mid B\in\mathcal P_0\}$（$s\in\mathbb Z/7\mathbb Z$）、$\mathcal B=\mathcal P_0\cup\cdots\cup\mathcal P_6$ とおく。このとき $(X,\mathcal B)$ は $S(2,3,15)$ であり、$\mathcal R=\{\mathcal P_0,\dots,\mathcal P_6\}$ はその分解である。したがって $(X,\mathcal B,\mathcal R)$ は $\mathrm{KTS}(15)$ で、$\mathcal P_s$ を第 $s+1$ 日とすれば女学生問題の解になる。
証明では、$X$ の 2 元部分集合（以下「対」という）を、$\tau_s$ で移り合うものごとに 15 種類に分ける。
| 種類 | 対の形 | 個数 |
|---|---|---|
| $I$ | $\{\infty,a\}$ | $7$ |
| $I'$ | $\{\infty,a'\}$ | $7$ |
| $U(\delta)$（$\delta=1,2,3$） | $\{a,a+\delta\}$ | 各 $7$ |
| $U'(\delta)$（$\delta=1,2,3$） | $\{a',(a+\delta)'\}$ | 各 $7$ |
| $M(c)$（$c\in\mathbb Z/7\mathbb Z$） | $\{a,(a+c)'\}$ | 各 $7$ |
ここで $a$ は $\mathbb Z/7\mathbb Z$ を動く。印のない 2 点の対 $\{a,b\}$ では、$b-a$ と $a-b$ の一方がちょうど $1,2,3$ のどれかになり、それを $\delta$ とする。$15$ 種類で $15\cdot7=105=\binom{15}2$ 個であり、どの対もちょうど 1 つの種類に入る。
各 $\mathcal P_s$ は平行類である。 $\mathcal P_0$ の 5 つのブロックに現れる点は $\infty,0,0',1,2,4,3,1',5',5,4',6',6,2',3'$ で、$X$ の 15 点がちょうど 1 回ずつ現れる。よって $\mathcal P_0$ は $X$ の分割であり、$\tau_s$ は全単射なので $\mathcal P_s$ も $X$ の分割である。
種類は $\tau_s$ で保たれ、各種類の 7 個の対は 1 つの対の像として 1 回ずつ現れる。 $\tau_s$ は $\infty$ を動かさず、印の有無と差を変えないので、種類を保つ。種類 $T$ の対 $\pi$ について、$\tau_s(\pi)$（$s=0,\dots,6$）が互いに異なることを示す。$\tau_s(\pi)=\tau_{s'}(\pi)$ なら $u:=s-s'$ について $\tau_u(\pi)=\pi$ である。$\pi$ が $\infty$ を含むか、印のある点とない点を 1 つずつ含むなら、印のない点 $a$（または印のある点 $a'$）が $a+u=a$ を満たし $u=0$ である。$\pi=\{a,a+\delta\}$（または印のある版）で $u\ne0$ なら、$a+u=a+\delta$ かつ $a+\delta+u=a$ となり $2\delta=0$、$7$ は奇数なので $\delta=0$ となって矛盾する。よって $u=0$ で、$\tau_s(\pi)$（$s=0,\dots,6$）は種類 $T$ の 7 個の対をちょうど 1 回ずつ尽くす。
$\mathcal P_0$ は各種類の対をちょうど 1 つずつ含む。 5 つのブロックの 15 個の対の種類は次のとおりである（$M(c)$ の $c$ は印のある点の番号から印のない点の番号を引いた値）。
| ブロック | 含む対の種類 |
|---|---|
| $\{\infty,0,0'\}$ | $I$、$I'$、$M(0)$ |
| $\{1,2,4\}$ | $U(1)$（$\{1,2\}$）、$U(2)$（$\{2,4\}$）、$U(3)$（$\{1,4\}$） |
| $\{3,1',5'\}$ | $M(5)$（$1-3$）、$M(2)$（$5-3$）、$U'(3)$（$\{5',1'\}$、$1-5\equiv3$） |
| $\{5,4',6'\}$ | $M(6)$（$4-5$）、$M(1)$（$6-5$）、$U'(2)$（$\{4',6'\}$） |
| $\{6,2',3'\}$ | $M(3)$（$2-6$）、$M(4)$（$3-6$）、$U'(1)$（$\{2',3'\}$） |
$M(c)$ は $c=0,\dots,6$ がちょうど 1 回ずつ、$U(\delta)$ と $U'(\delta)$ は $\delta=1,2,3$ がちょうど 1 回ずつ現れる。
どの対もちょうど 1 つのブロックに含まれる。 対 $\{x,y\}$ の種類を $T$、$\mathcal P_0$ の中の種類 $T$ のただ 1 つの対を $\pi$、それを含むブロックを $B$ とする。前段により $\{x,y\}=\tau_s(\pi)$ となる $s$ がただ 1 つあり、$\{x,y\}\subseteq\tau_s(B)\in\mathcal P_s$ である。逆に $\{x,y\}\subseteq\tau_{s'}(B')$（$B'\in\mathcal P_0$）なら、$\pi':=\tau_{-s'}(\{x,y\})\subseteq B'$ は $\mathcal P_0$ の中の種類 $T$ の対なので $\pi'=\pi$、$B'=B$ であり、$\tau_{s'}(\pi)=\{x,y\}=\tau_s(\pi)$ から $s'=s$ である。よって $\{x,y\}$ を含むブロックは $\tau_s(B)$ だけで、$(X,\mathcal B)$ は $S(2,3,15)$ である。
分解であること。 ブロックの組 $(s,B)$ と $\tau_s(B)$ の対応で異なる組 $(s,B)\ne(s',B')$ が同じブロック $\tau_s(B)=\tau_{s'}(B')$ を与えると、そのブロックの中の対 $\{x,y\}$ は $\{x,y\}\subseteq\tau_{s'}(B')$ を満たすので、前段により $s'=s$ かつ $B'=B$ となって矛盾する。よって $\mathcal P_0,\dots,\mathcal P_6$ は互いに交わらず、それぞれ平行類なので、$\mathcal R$ は $\mathcal B$ の分解である。$\square$
7 日分の組分けの全体は次のとおりである。
| 日 | 組 |
|---|---|
| 第 1 日 | $\{\infty,0,0'\}$、$\{1,2,4\}$、$\{3,1',5'\}$、$\{5,4',6'\}$、$\{6,2',3'\}$ |
| 第 2 日 | $\{\infty,1,1'\}$、$\{2,3,5\}$、$\{4,2',6'\}$、$\{6,5',0'\}$、$\{0,3',4'\}$ |
| 第 3 日 | $\{\infty,2,2'\}$、$\{3,4,6\}$、$\{5,3',0'\}$、$\{0,6',1'\}$、$\{1,4',5'\}$ |
| 第 4 日 | $\{\infty,3,3'\}$、$\{4,5,0\}$、$\{6,4',1'\}$、$\{1,0',2'\}$、$\{2,5',6'\}$ |
| 第 5 日 | $\{\infty,4,4'\}$、$\{5,6,1\}$、$\{0,5',2'\}$、$\{2,1',3'\}$、$\{3,6',0'\}$ |
| 第 6 日 | $\{\infty,5,5'\}$、$\{6,0,2\}$、$\{1,6',3'\}$、$\{3,2',4'\}$、$\{4,0',1'\}$ |
| 第 7 日 | $\{\infty,6,6'\}$、$\{0,1,3\}$、$\{2,0',4'\}$、$\{4,3',5'\}$、$\{5,1',2'\}$ |
たとえば $0$ と $0'$ は第 1 日、$0$ と $1$ は第 7 日、$0$ と $3'$ は第 2 日だけ同じ組になる。
印のない 7 点の上の組 $\{1,2,4\}+s$ は Fano 平面（Steiner系 の例「Fano 平面」）の 7 本の直線であり、この解は Fano 平面に 7 点と $\infty$ を付け加えて組み立てたものとみることもできる。
存在定理
$v\equiv3\pmod6$ ならば $\mathrm{KTS}(v)$ が存在する。したがって thm-kirk-necessary とあわせて、$\mathrm{KTS}(v)$ が存在するのは $v\equiv3\pmod6$ のときであり、そのときに限る。
この定理は Ray-Chaudhuri と Wilson が 1971 年に発表した（RS88 p. 125 の Theorem (Ray-Chaudhuri and Wilson)。この記事では証明しない）。証明は、小さな位数の Kirkman 三重系とブロックの大きさが限られたデザインを組み合わせて、大きな位数の系を作る構成による。たとえば、$2r+1$ 点の Kirkman 三重系が存在するような $r$ の集合が、ブロックの大きさがその集合に属する「対ごとに均衡なデザイン」（pairwise balanced design）の点の個数をとる操作で閉じていることが鍵の 1 つである（Sti22 §3.2、p. 14）。
Steiner の三重系だけなら、$v\ge3$、$v\equiv1,3\pmod6$ のすべてで存在することを Kirkman 自身が示している（Steiner系 の例「Steiner の三重系の条件」。証明は Steiner三重系 の定理「Kirkmanの存在定理」）。解決可能性を課すと $v\equiv1\pmod6$ が除かれ、残る $v\equiv3\pmod6$ ではすべて実現される。
条件を外した反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| thm-kirk-necessary の解決可能性（Steiner の三重系のままにする） | Fano 平面 $S(2,3,7)$ | $v\equiv3\pmod6$：$7\equiv1\pmod6$ |
| thm-kirk-necessary の「どの 2 点もちょうど 1 つのブロックに含まれる」（高々 1 つに弱める） | $X=\{1,\dots,6\}$、$\mathcal B=\{\{1,2,3\},\{4,5,6\}\}$（平行類 1 つの分解をもつ） | $v\equiv3\pmod6$：$6\equiv0\pmod6$ |
| prop-kirk-equiv の「同じ組になるのは高々 1 日」 | 15 人が同じ 5 組を 8 日続ける | 日数が $7$ 以下 |
| thm-kirk-fifteen の、$\mathcal P_0$ が各種類の対をちょうど 1 つ含むこと | $\mathcal P_0$ を $\{\infty,0,0'\},\{1,2,3\},\{4,5,6\},\{1',2',3'\},\{4',5',6'\}$ に替える（$X$ の分割ではある） | どの対もちょうど 1 つのブロックに含まれる：$\{1,2\}$ が 2 つのブロックに入る |
4 行目：替えた $\mathcal P_0$ では $\{1,2\}$ と $\{2,3\}$ がどちらも種類 $U(1)$ である。$\{1,2\}\subseteq\{1,2,3\}\in\mathcal P_0$ であり、$\tau_6(\{2,3\})=\{1,2\}$ なので $\{1,2\}\subseteq\tau_6(\{1,2,3\})=\{0,1,2\}\in\mathcal P_6$ でもある。よって $\{1,2\}$ は 2 つのブロックに含まれる。2 行目の系では点 $1$ を含むブロックは 1 つだけで、$1$ と $4$ を含むブロックはない。
補足
ex-kirk-nine の議論は、$\mathbb Z/3\mathbb Z$ を位数 $q$ の 有限体 $\mathbb F_q$ に替えてもそのまま通る。$\mathbb F_q^2$ の $q^2$ 点と、$q+1$ 個の方向 $(1,0)$、$(1,\mu)$（$\mu\in\mathbb F_q^\times$）、$(0,1)$ のそれぞれについて方向の等しい $q$ 本の直線をとると、方向ごとに平行類ができ、解決可能な $S(2,q,q^2)$ が得られる（$q$ が素数のときは $\mathbb F_q=\mathbb Z/q\mathbb Z$）。異なる 2 点 $a\ne b$ を通る直線は $\{a+s(b-a)\mid s\in\mathbb F_q\}$ ただ 1 本である（$b-a$ はちょうど 1 つの方向の $\mathbb F_q^\times$ 倍）。$q=3$ が $\mathrm{KTS}(9)$ である。この系は $\mathbb F_q$ 上のアフィン平面であり、射影平面 の記事の射影平面とは平行な直線の有無で異なる。
女学生問題は T. P. Kirkman が出した問題で、Kirkman 三重系の名はこれにちなむ（RS88 p. 125）。15 人の解には、thm-kirk-fifteen とは別の作り方による解も多く知られている（たとえば Sti22 Example 3.2、p. 15 に 7 つの平行類を並べた例がある）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
