1. 少ない回数で全員とペアを作るグループ分け問題 #

条件

• $v$人いる
• 毎日$k$人ずつの$g$個のグループに分ける ($v=gk$が満たされる$v,k,g$に限る)
• どの2人も、少なくとも一度は同じグループになるように分けたい
• 特定の2人がいつも同じグループにならないようにしたい。

問題

• 上記の条件が満たされるようになる、最も少ない日数とその時の組み合わせを求めたい。

1.1. グループ分け具体例 #

ここで示すのは私が手元で計算した解の上限です。すべての組み合わせを試すのは計算資源が足らないため、解が見つかった中で日数が少なかった組み合わせをいくつか提示します。

• 合計人数$v$
• 1グループ当たりの人数$k$
• $(d, m)$: 全要素対（ペア）を作成するのに必要な日数$d$, 同じ2人が同じグループになる最大回数$m$

もし下記表に存在しない人数だった場合、多めの人数（5人）で表を参照して適当な番号を欠番として考えてください。

本稿では、1グループあたりの人数 $k=10$人までの場合を提示していますが、下記のリンク先では $k=25$人まで提示しています。

Optimization of Grouping for Complete Element Pairing -sikinote

2. 問題の説明 #

2.1. 問題の由来 #

プリクラ問題¹がきっかけで、その問題の条件を厳しくした問題になります。少し言葉を硬く表現するならば、

となるでしょうか。プリクラ問題との違いとして下記の点が挙げられます。

• プリクラ問題では、いつも全員の中から適当な人を抜き出せばよい一方で、今回のグループ分けでは全員をグループ分けしきるまで、同じ人をグループに配置することはできないという違いがあります。

2.2. 問題の具体例 #

具体例があった方が問題が分かりやすいと思うので、実際に考えてみます。

あなたは、ある研修の主催者で参加者の班分けを考えています。
研修参加者は、それぞれ初対面の参加者が多いため、研修中に少なくとも一回は全ての人と同じ班になるようにしたい、という問題です。
まとめると下記のような状況です。

• 研修は 合計 $v=15$人 が参加します。
• 研修は 7日間 行われます。
• 研修は 1班当たり$k=3$人 (合計$g=5$班) で行うグループワーク形式で行われます。
• グループは毎日入れ替わります。

この時、どのように班分けをすれば、研修中に全ての人が全ての人と少なくとも一回は一緒の班になることができるでしょうか、またそもそもこれは研修日数で実現可能なのでしょうか？
という問題です。

3. 詳細 #

3.1. 問題の分類 #

これは、組合せ数学におけるブロックデザインや実験計画法に属する問題です。

その中の、Covering design²とシュタイナーシステム (Steiner-System)³に関係する問題になります。

3.1.1. カバーデザイン (Covering design) #

Covering designとは、

covering design is a collection of k-element subsets, called blocks, of {1,2,…,v}, such that any t-element subset is contained in at least one block.

と説明されています²。日本語訳すれば下記の通りです。

カバーデザインとは、${1,2,…,v}$のk要素の部分集合であるブロックの集まりで、任意のt要素の部分集合が少なくとも1つのブロックに含まれるようなデザインです。

カバーデザインは、$v$, $k$, $t$を使用してその組み合わせ数の上限$C(v,k,t)$で与えられます。

$t=2$の具体的なカバーデザインの問題として、

• プリクラ問題 $C(v,k,v=2)$

があります¹。

カバーデザインと本稿の問題の違いとして、全ての人を毎日余りなくグループ分けをする区別が無い、という点が挙げられます。 そのため、カバーデザインから得られる日数は、問題の下限の日数を与えることになります。

3.1.2. シュタイナーシステム (Steiner-System) #

Covering designに似た問題として、シュタイナーシステム (Steiner-System)³があります。 だたし、シュタイナーシステムという場合は、少なくとも一度同じグループという条件ではなく、一度しか同じにならないという条件で本稿の問題よりも条件を厳しくしたものとなります。

本稿の問題の厳密解は、シュタイナーシステムの$t=2$に対応します。これに対して任意の$v, k$でシュタイナーシステムを見つけることができれば、本稿の問題の厳密解となります。 ただし、$t=2$のシュタイナーシステムはそもそも任意の$v,k$で成り立たないので、もし見つかれば、という条件付きです。

シュタイナーシステムの特別な場合ですら、名称をつけて問題が提起されるほど容易ではない問題として議論されてきました。例えば、下記の2つの問題が挙げられています。

• カークマンの女学生問題⁴ (Kirkman’s schoolgirl problem) $S(t=2,k=3,v=15)$
• 社会的ゴルファー問題⁵ (Social golfer problem) $S(t=2,k=4,v=32)$

k=3の時、これは特に Steiner triple system (スタイナー三元系)と呼ばれており、カークマンの女学生問題は$STS(15)$と表現されます。

さらに多くの例として下記のページで多くの例が挙げられています。 Social Golfer Problem -Math Games

4. 参考文献 #