amori's blog

よろず技術系と趣味関係の雑記です

ドブルの数理(4) ドブル構成の導出 その2: 7×7人総当たり組み合わせ問題

いわゆる16人麻雀総当たり問題の拡張版で、7×7=49人の場合を考えます。

7人でやるゲームというのはパッとは思いつかないので、とりあえず7人1セットのポーカー大会を総勢49名で開催するものとでもお考えください。

一人のプレイヤーは1回で6人と対戦しますので、他の48人全員と対戦するのには8回戦が必要です。ちょうど8回戦で全プレイヤーが、全員と対戦する組み合わせを求める、というのがこの問題です。

以下、手順のみ説明します。理屈については後半で。

1) 49人を7の剰余系の二次元平面に配置します。
具体的には、49人に0から48の番号をふり、例えば0->(0,0), 1->(1,0)・・47->(5,6), 48->(6,6)というように番号と平面の位置と対応させます。
この場合は、番号m, 平面の位置(x,y)は、
x=m (mod 7), y=(m-x)/7
C言語なら、int x=m%7, int y=m/7 ですね。大事なのは平面に漏れなく配置されることでして、それさえ保障されるのならば対応関係はなんでもかまいません。

2) 組み分けの計算式を準備します。
ax+byという式に1)で割り当てた座標をx,yに代入し、その計算結果が組み分けの組番号になります。
例えば、2x+yが組み分け式ならば、(1,1)の組は3になります。

ひとつの式にそれぞれの平面座標を代入して得られる0から6の値がそのまま組み分けになります。異る計算式を8個用意すれば8回戦分の組み分けを求めることができます。
具体的には、
x, y, x+y, x+2y, x+3y, x+4y, x+5y, x+6y
の8個の式です。というかこれ以外の式はこの式と同じになります。

例えば、2x+1を4倍すると8x+4=x+4です。ax+byの式は全部8通りということです。

では、8回戦分の組み合わせを計算しましょう。

1回戦 2回戦 3回戦 4回戦 5回戦 6回戦 7回戦 8回戦
No 座標 y x x+y x+2y x+3y x+4y x+5y x+6y
0 0,0 0 0 0 0 0 0 0 0
1 1,0 0 1 1 1 1 1 1 1
2 2,0 0 2 2 2 2 2 2 2
3 3,0 0 3 3 3 3 3 3 3
4 4,0 0 4 4 4 4 4 4 4
5 5,0 0 5 5 5 5 5 5 5
6 6,0 0 6 6 6 6 6 6 6
7 0,1 1 0 1 2 3 4 5 6
8 1,1 1 1 2 3 4 5 6 0
9 2,1 1 2 3 4 5 6 0 1
10 3,1 1 3 4 5 6 0 1 2
11 4,1 1 4 5 6 0 1 2 3
12 5,1 1 5 6 0 1 2 3 4
13 6,1 1 6 0 1 2 3 4 5
14 0,2 2 0 2 4 6 1 3 5
15 1,2 2 1 3 5 0 2 4 6
16 2,2 2 2 4 6 1 3 5 0
17 3,2 2 3 5 0 2 4 6 1
18 4,2 2 4 6 1 3 5 0 2
19 5,2 2 5 0 2 4 6 1 3
20 6,2 2 6 1 3 5 0 2 4
21 0,3 3 0 3 6 2 5 1 4
22 1,3 3 1 4 0 3 6 2 5
23 2,3 3 2 5 1 4 0 3 6
24 3,3 3 3 6 2 5 1 4 0
25 4,3 3 4 0 3 6 2 5 1
26 5,3 3 5 1 4 0 3 6 2
27 6,3 3 6 2 5 1 4 0 3
28 0,4 4 0 4 1 5 2 6 3
29 1,4 4 1 5 2 6 3 0 4
30 2,4 4 2 6 3 0 4 1 5
31 3,4 4 3 0 4 1 5 2 6
32 4,4 4 4 1 5 2 6 3 0
33 5,4 4 5 2 6 3 0 4 1
34 6,4 4 6 3 0 4 1 5 2
35 0,5 5 0 5 3 1 6 4 2
36 1,5 5 1 6 4 2 0 5 3
37 2,5 5 2 0 5 3 1 6 4
38 3,5 5 3 1 6 4 2 0 5
39 4,5 5 4 2 0 5 3 1 6
40 5,5 5 5 3 1 6 4 2 0
41 6,5 5 6 4 2 0 5 3 1
42 0,6 6 0 6 5 4 3 2 1
43 1,6 6 1 0 6 5 4 3 2
44 2,6 6 2 1 0 6 5 4 3
45 3,6 6 3 2 1 0 6 5 4
46 4,6 6 4 3 2 1 0 6 5
47 5,6 6 5 4 3 2 1 0 6
48 6,6 6 6 5 4 3 2 1 0

各回戦ごとに、0から6の値が7づつ割り振られているのがわかります。
任意の2つNoは必ず何回戦かで一度だけ同じ組になり、他の回戦では必ず違う組になります。
なぜならば、同じ組になるということは振り分けの計算式、つまりこの式が表す同一直線上あるということなので、
もし異なる回戦で同じ組にあるとすると2つの点が異なる直線の上に同時に存在するということになってしまいます。

有限体の平面においても直線の性質は同じで、二点が決まればそれを通る直線は唯一に決まります。
これは、ax+by=cの直線の式が二組のx,yからa,b,cが定ることからわかります。
(先に述べたようにa=1としてokなので)

念のため各回戦の組み合わせで並べ替えてみましょう。
第1回戦

0組 0 1 2 3 4 5 6
1組 7 8 9 10 11 12 13
2組 14 15 16 17 18 19 20
3組 21 22 23 24 25 26 27
4組 28 29 30 31 32 33 34
5組 35 36 37 38 39 40 41
6組 42 43 44 45 46 47 48

第2回戦

0組 0 7 14 21 28 35 42
1組 1 8 15 22 29 36 43
2組 2 9 16 23 30 37 44
3組 3 10 17 24 31 38 45
4組 4 11 18 25 32 39 46
5組 5 12 19 26 33 40 47
6組 6 13 20 27 34 41 48

第3回戦

0組 0 13 19 25 31 37 43
1組 1 7 20 26 32 38 44
2組 2 8 14 27 33 39 45
3組 3 9 15 21 34 40 46
4組 4 10 16 22 28 41 47
5組 5 11 17 23 29 35 48
6組 6 12 18 24 30 36 42

第4回戦

0組 0 12 17 22 34 39 44
1組 1 13 18 23 28 40 45
2組 2 7 19 24 29 41 46
3組 3 8 20 25 30 35 47
4組 4 9 14 26 31 36 48
5組 5 10 15 27 32 37 42
6組 6 11 16 21 33 38 43

第5回戦

0組 0 11 15 26 30 41 45
1組 1 12 16 27 31 35 46
2組 2 13 17 21 32 36 47
3組 3 7 18 22 33 37 48
4組 4 8 19 23 34 38 42
5組 5 9 20 24 28 39 43
6組 6 10 14 25 29 40 44

第6回戦

0組 0 10 20 23 33 36 46
1組 1 11 14 24 34 37 47
2組 2 12 15 25 28 38 48
3組 3 13 16 26 29 39 42
4組 4 7 17 27 30 40 43
5組 5 8 18 21 31 41 44
6組 6 9 19 22 32 35 45

第7回戦

0組 0 9 18 27 29 38 47
1組 1 10 19 21 30 39 48
2組 2 11 20 22 31 40 42
3組 3 12 14 23 32 41 43
4組 4 13 15 24 33 35 44
5組 5 7 16 25 34 36 45
6組 6 8 17 26 28 37 46

第8回戦

0組 0 8 16 24 32 40 48
1組 1 9 17 25 33 41 42
2組 2 10 18 26 34 35 43
3組 3 11 19 27 28 36 44
4組 4 12 20 21 29 37 45
5組 5 13 14 22 30 38 46
6組 6 7 15 23 31 39 47

並べてみるとわかりますますように、2回戦で同一だった組の人を他の回戦ではバラバラの組にして回戦ごとに異なる周期でローテションすることで組み合わせが変わっていることがわかります。
組数が素数なので周期が一巡するまでは組み合わせが重複しないのは直感的にわかりますし、逆に組数が素数でなければ約数の単位で一巡するまでに重複が発生することも想像がつきます。

ドブルの数理(5) に続きます。
http://amori.hatenablog.com/entry/2016/10/23/182058