|
Halt0 |
|
こんにちは.
もう日曜なのでご覧になっている方も少ないかもしれませんが, 結局気になったので, 別の資料を参考にして, 人数 n が n=25,28,37 の場合の解を構成してみました. D. Stinson. Combinatorial Designs: Constructions and Analysis http://mathscinet.ru/files/StinsonD.pdf を参照しました. 直接今回の問題とかかわりがあるのは p.167~ です. 上記 pdf を読んでいただいたほうが早いかもしれませんが, せっかくなのでここに構成およびその証明を書いてみます. 群論の初歩的な知識があれば理解することが可能です. (#45413 に書いたとおり, 人数 n が n≡1,4 (mod 12) を満たすことが必要十分らしく, 上記 pdf もこのことを証明しているみたいなのですが, 私はそこまではフォローできていません. ですが, 上記資料ではそのことを証明するためのステップとして, n=13,16,25,28,37 で個別に具体例を構成しています. 結局, このあたりは統一的なアルゴリズムでは取り扱えないということなのでしょう. なので, n=25,28,37 の構成のみ読んでみました. (n=25 の解は既に掲示板に提示されていますが, n=37 と構成の仕方が同様なので, 読みました) なお, 斜め読みなので, 証明には私の手が入っており, したがって元の資料にはない誤りがある可能性があります.) ---------------------------------------- [記法] ・集合 S の元の数を |S| と書く. ・整数群 Z の n を法とした剰余類群を Z/nZ と書く. ・群 G_1 と G_2 の直積を G_1 × G_2 と書く. [定義] 有限集合の組 (X,β) が 2-(n,4,1) design であるとは, ・《条件0》 |X|=n ・《条件1》 各 B∈β に対し B⊂X, |B|=4 ・《条件2》 任意の x,y∈X, x≠y に対し, {x,y}⊂B なる B∈β がただ 1 つ存在する を満たすことをいう. 2-(n,4,1) design を n=25,28,37 のときに構成しよう. (X が参加者の集合, n がその人数, 各B∈β が行われた試合の組にあたる.) 【n=25 のとき】 G = (Z/5Z) × (Z/5Z) とし, a[1,1]=(0,0), a[1,2]=(0,1), a[1,3]=(1,0), a[1,4]=(2,2) a[2,1]=(0,0), a[2,2]=(0,2), a[2,3]=(2,0), a[1,4]=(4,4) を G の元とする. [補題1] 任意の g∈G, g≠0 に対し ただ 1 つの i∈{1,2} と j,k∈{1,2,3,4}, j≠k があって g=a[i,j]-a[i,k] である. [証明] 2×4×3=24 通りの i,j,k の組について実際に計算して確かめるだけなので略. □ i=1,2, g∈G に対し, B[i,g] = {a[i,1]+g, a[i,2]+g, a[i,3]+g, a[i,4]+g} と定める. X = G, β = {B[i,g] |i∈{1,2}, g∈G} とする. このとき《条件0》《条件1》は明らか. 《条件2》を示そう. x,y∈X, x≠y とする. 補題1より, ただ 1 つの i,j,k (j≠k) があって x-y=a[i,j]-a[i,k] である. そこで g=x-a[i,j] とおけば, x=a[i,j]+g, y=a[i,k]+g より {x,y}⊂β[i,g] であり, また構成の仕方から, このような β[i,g] はただ 1 つに決まる. よって (X,β) は 2-(25,4,1) design である. 【n=37 のとき】 G=Z/37Z とし, a[1,1]=0, a[1,2]=1, a[1,3]=3, a[1,4]=24 a[2,1]=0, a[2,2]=10, a[2,3]=18, a[2,4]=30 a[3,1]=0, a[3,2]=4, a[3,3]=26, a[3,4]=32 を G の元とする. n=25 のときと同様の補題 (i∈{1,2,3} と変えるだけ) が成り立ち, そこから同様に構成できる. 【n=28 のとき】 n=25,37 とは少し違った構成をする. G = (Z/3Z) × (Z/3Z) × (Z/3Z) とし, a[1,1]=(0,0,0), a[1,2]=(0,2,0), a[1,3]=(1,1,1), a[1,4]=(2,1,1) a[2,1]=(0,0,0), a[2,2]=(1,0,2), a[2,3]=(0,1,2), a[1,4]=(1,1,0) を G の元とする. [補題2] 任意の g∈G, g≠0 に対し g=a[i,j]-a[i,k] となるような i,j,k (j≠k) は高々 1 つしかない. (※ 1 つもない場合もある) [証明] 計算するだけなので略. □ G に含まれない元 ∞ を考え, X = G ∪ {∞} とおく. i=1,2, g∈G に対し, B[i,g] = {a[i,1]+g, a[i,2]+g, a[i,3]+g, a[i,4]+g} と定め, また, a,b∈Z/3Z に対し B'[a,b] = {(a,b,0),(a,b,1),(a,b,2),∞} とおく. このとき, B[i,g] の形の元 (2×27=54 個) および B'[a,b] の形の元 (9 個), 計 63 個の元からなる β を考えると, (X,β) は条件を満たす. 《条件0》《条件1》は明らかなので《条件2》を示そう. [補題3] 各 B_1,B_2∈β (B_1≠B_2) に対し, その共通部分が 2 つ以上の元を含まない. [証明] B_1, B_2 のいずれも B'[a,b] の形をしていない場合, 補題2から (n=27 のときの《条件2》の証明と同じようにして) 示せる. また, いずれも B'[a,b] の形をしている場合, 共通部分は明らかに ∞ のみを含む. したがって B'[a,b] と B[i,g] の共通部分の元が 1 つ以下であることを示せば証明が終わるが, これは i,g を固定したときに B[i,g] の 2 つの異なる元を (a_1,b_1,c_1), (a_2,b_2,c_2) とすれば (a_1,b_1)≠(a_2,b_2) となることから明らかである. □ 補題3より, 《条件2》 を弱くした条件, 「任意の x,y∈X, x≠y に対し, {x,y}⊂B なる B∈β は, 存在するとすればただ 1 つである」 がいえる. ここで, |X|=28 より, x,y∈X, x≠y となるような x,y の組み合わせは, 28×27/2=378 通りあることと, |β|=63 より, B∈β および {x,y}⊂B (x≠y) のとりかたは |β|×4C2=378 通りあることから, 結局 1 対 1 対応により《条件2》そのものがいえる. よって (X,β) は 2-(28,4,1) design である. ---------------------------------------- 長文失礼しました. |
|
10月23日（日） 2:35:00
45417 |