拡張カークマン問題                     戻る

 当HPがいつもお世話になっているHN「GAI」さんからのご投稿です。
                                       (平成30年2月12日付け)

 従来のカークマン問題は、「15人を毎日3人ずつの5班に分けて散歩させ、これを7日間続
けると、どの人も他のメンバーの14人と散歩をすることが出来る組み合わせを探す」という
テーマであるので、これを拡張して、「21人を毎日3人ずつの7班に分け散歩させ、これを10
日間続けたとき、どの人も他の20人のメンバーと行動を共にすることが可能か」に挑戦して
みた。

 全部で3人の班が70組構成されるが、この組み合わせは何とか探せたものの、これらを10
行7列に構成させたとき、どの行にも1〜21に当たる数字が入る並びを達成することは、いく
らやっても不可能な感じなんです。(ここ1週間挑戦し続けていますが、未だに不可能です。)

 この構成が可能か不可能か判定ができる方は教えて下さい。また、いくらネットを探しても
この構成を示している例を探しきれません。

 もし、こんな例が出来ますよ、というのを完成されてしまう方がおられましたら、ぜひ具体例
を上げて教えて下さい。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年2月12日付け)

 vを人数として、 v ≡ 3 (mod 6) のときには解があることが既に示されているの【かも】し
れません。15 や 21 や 27 など……。こちらを見ましたがちんぷんかんぷんでした。

 21人でのカークマンですが…、こちらよりコピペしてきましたが、これであっていますでしょ
うか?

Day0 ABF EGM DKR INP CJT HOU LQS
Day1 DEJ HIK BNO AQR CLU FMS GPT
Day2 AHL JKO EIQ CNR BGS DMT FPU
Day3 BCD FHN ELP GOQ AKT IMU JRS
Day4 EFK IGL COM BRP AJU DNS HQT
Day5 BIJ KLM FGR AOP CHS ENT DQU
Day6 CAE DIO FJQ HMR BLT GNU KPS
Day7 FDL GHJ AMN CPQ BKU EOS IRT
Day8 CGK LJN DHP BMQ AIS FOT ERU
Day9 STU ADG BEH CFI JMP KNQ LOR


 DD++さんからのコメントです。(平成30年2月13日付け)

 10日を7日と3日に分けて使います。21人にABCと0123456の組み合わせでA:0やC:5のよう
に名前をつけます。以下で名前の数字側が7以上になったら、7で割った余りを取るものとし
ます。

1日目〜7日目: n日目には、

(A:n, A:n+1, A:n+3)、(B:n, B:n+2, B:n+6)、(C:n, C:n+3, C:n+9)、(A:n+2, B:n+4, C:n+6)
(A:n+4, B:n+8, C:n+12)、(A:n+5, B:n+10, C:n+15)、(A:n+6, B:n+12, C:n+18)

の7組に分けます。

8日目〜10日目: 0≦k≦6 として、

8日目は (A:k, B:k, C:k)
9日目は (A:k+1, B:k+2, C:k+3)
10日目は (A:k+3, B:k+6, C:k+9)

で、7組に分けます。


 GAIさんからのコメントです。(平成30年2月14日付け)

 ハンニバル・フォーチュンさんから紹介されたもの、A〜Uを1〜21に置きなおして分析して
みました。

 この3人組70個を横一列に並べ1〜21が一度ずつ現れる組み合わせの総パターンが次の
43通り可能で、目的の配列がこれから*のものをそれぞれ選び出していることに相当してい
ました。

 当初、自分も他の組み合わせの70個でやっていたものでは全部で53パターンが発生して
これをどうにか選んで達成しようと無駄な努力を繰り返していたことがわかりました。

 いくら70組が条件に合うように取り出したとしても、単にそれは必要条件に過ぎず、十分条
件ではないことなんですね。

 紹介されたサイトには他にも興味あるものがたくさん掲載されており、とても重宝します。

[1, 2, 6, 3, 12, 21, 4, 14, 19, 5, 9, 17, 7, 16, 20, 8, 13, 18, 10, 11, 15]
[1, 2, 6, 3, 10, 20, 4, 11, 18, 5, 7, 13, 8, 15, 21, 9, 14, 16, 12, 17, 19]*
[1, 2, 6, 3, 8, 19, 4, 5, 10, 7, 16, 20, 9, 13, 21, 11, 14, 17, 12, 15, 18]

[1, 3, 5, 2, 12, 20, 4, 9, 15, 6, 10, 17, 7, 14, 21, 8, 13, 18, 11, 16, 19]*
[1, 3, 5, 2, 11, 21, 4, 8, 16, 6, 13, 19, 7, 15, 17, 9, 18, 20, 10, 12, 14]
[1, 3, 5, 2, 7, 19, 4, 6, 12, 8, 15, 21, 9, 18, 20, 10, 13, 16, 11, 14, 17]

[1, 4, 7, 2, 9, 10, 3, 14, 18, 5, 15, 19, 6, 16, 21, 8, 17, 20, 11, 12, 13]
[1, 4, 7, 2, 5, 8, 3, 6, 9, 10, 13, 16, 11, 14, 17, 12, 15, 18, 19, 20, 21]*

[1, 8, 12, 2, 7, 19, 3, 14, 18, 4, 13, 20, 5, 9, 17, 6, 16, 21, 10, 11, 15]
[1, 8, 12, 2, 13, 17, 3, 7, 11, 4, 9, 15, 5, 14, 20, 6, 16, 21, 10, 18, 19]
[1, 8, 12, 2, 14, 15, 3, 7, 11, 4, 13, 20, 5, 9, 17, 6, 16, 21, 10, 18, 19]
[1, 8, 12, 2, 9, 10, 3, 13, 15, 4, 17, 21, 5, 14, 20, 6, 7, 18, 11, 16, 19]
[1, 8, 12, 2, 9, 10, 3, 14, 18, 4, 17, 21, 5, 7, 13, 6, 15, 20, 11, 16, 19]
[1, 8, 12, 2, 16, 18, 3, 10, 20, 4, 14, 19, 5, 6, 11, 7, 15, 17, 9, 13, 21]
[1, 8, 12, 2, 13, 17, 3, 6, 9, 4, 14, 19, 5, 18, 21, 7, 16, 20, 10, 11, 15]
[1, 8, 12, 2, 7, 19, 3, 13, 15, 4, 5, 10, 6, 16, 21, 9, 18, 20, 11, 14, 17]*

[1, 9, 19, 2, 13, 17, 3, 7, 11, 4, 8, 16, 5, 18, 21, 6, 15, 20, 10, 12, 14]*
[1, 9, 19, 2, 13, 17, 3, 12, 21, 4, 8, 16, 5, 14, 20, 6, 7, 18, 10, 11, 15]
[1, 9, 19, 2, 13, 17, 3, 10, 20, 4, 8, 16, 5, 6, 11, 7, 14, 21, 12, 15, 18]
[1, 9, 19, 2, 14, 15, 3, 7, 11, 4, 6, 12, 5, 18, 21, 8, 17, 20, 10, 13, 16]
[1, 9, 19, 2, 16, 18, 3, 10, 20, 4, 6, 12, 5, 7, 13, 8, 15, 21, 11, 14, 17]
[1, 9, 19, 2, 3, 4, 5, 6, 11, 7, 14, 21, 8, 17, 20, 10, 13, 16, 12, 15, 18]

[1, 10, 21, 2, 7, 19, 3, 14, 18, 4, 8, 16, 5, 9, 17, 6, 15, 20, 11, 12, 13]
[1, 10, 21, 2, 13, 17, 3, 14, 18, 4, 6, 12, 5, 15, 19, 7, 16, 20, 8, 9, 11]
[1, 10, 21, 2, 16, 18, 3, 13, 15, 4, 14, 19, 5, 6, 11, 7, 9, 12, 8, 17, 20]*
[1, 10, 21, 2, 3, 4, 5, 15, 19, 6, 7, 18, 8, 17, 20, 9, 14, 16, 11, 12, 13]

[1, 11, 20, 2, 9, 10, 3, 16, 17, 4, 6, 12, 5, 15, 19, 7, 14, 21, 8, 13, 18]
[1, 11, 20, 2, 7, 19, 3, 14, 18, 4, 6, 12, 5, 9, 17, 8, 15, 21, 10, 13, 16]
[1, 11, 20, 2, 7, 19, 3, 16, 17, 4, 5, 10, 6, 8, 14, 9, 13, 21, 12, 15, 18]
[1, 11, 20, 2, 3, 4, 5, 12, 16, 6, 8, 14, 7, 15, 17, 9, 13, 21, 10, 18, 19]*

[1, 13, 14, 2, 9, 10, 3, 7, 11, 4, 8, 16, 5, 18, 21, 6, 15, 20, 12, 17, 19]
[1, 13, 14, 2, 11, 21, 3, 16, 17, 4, 6, 12, 5, 15, 19, 7, 8, 10, 9, 18, 20]*
[1, 13, 14, 2, 9, 10, 3, 8, 19, 4, 17, 21, 5, 6, 11, 7, 16, 20, 12, 15, 18]

[1, 15, 16, 2, 11, 21, 3, 8, 19, 4, 13, 20, 5, 9, 17, 6, 7, 18, 10, 12, 14]
[1, 15, 16, 2, 9, 10, 3, 8, 19, 4, 17, 21, 5, 14, 20, 6, 7, 18, 11, 12, 13]*
[1, 15, 16, 2, 9, 10, 3, 7, 11, 4, 13, 20, 5, 18, 21, 6, 8, 14, 12, 17, 19]
[1, 15, 16, 2, 13, 17, 3, 12, 21, 4, 14, 19, 5, 6, 11, 7, 8, 10, 9, 18, 20]
[1, 15, 16, 2, 11, 21, 3, 14, 18, 4, 5, 10, 6, 13, 19, 7, 9, 12, 8, 17, 20]
[1, 15, 16, 2, 5, 8, 3, 7, 11, 4, 17, 21, 6, 13, 19, 9, 18, 20, 10, 12, 14]
[1, 15, 16, 2, 12, 20, 3, 8, 19, 4, 5, 10, 6, 7, 18, 9, 13, 21, 11, 14, 17]

[1, 17, 18, 2, 12, 20, 3, 8, 19, 4, 9, 15, 5, 6, 11, 7, 14, 21, 10, 13, 16]
[1, 17, 18, 2, 14, 15, 3, 12, 21, 4, 5, 10, 6, 13, 19, 7, 16, 20, 8, 9, 11]*
[1, 17, 18, 2, 12, 20, 3, 7, 11, 4, 5, 10, 6, 13, 19, 8, 15, 21, 9, 14, 16]

 一方、DD++さんから提示された構成方法を組み立てると、まあものの見事に出来上がって
くるではありませんか!

 10を7+3に分割したり、21を3*7に分解するなんて、まるで手品を見る思いです。なんか東
芝創業者の田中久重が精魂込めて作り上げた万年時計の精密機械を見る思いです。こん
なアイデア何処から思い付くものなんですか?


 DD++さんからのコメントです。(平成30年2月14日付け)

 元のカークマンの問題やGAIさんの班分けの問題について考察しているうちに、3人グル
ープを作る話の場合は、

 「3N+1人で円を作るのと相性がいい」、「3N+2人で円を作るのと相性が悪い」
 「2N人で円を作ると少し面倒な事態になる」

ということには気づいていました。21人の場合に循環型で解を構成するなら、1+10+10は10日
という数字と合うけど面倒が起きそう、7+7+7は10日とは合わないけど綺麗に行きそう、と直
感した次第です。

 次の27人の場合は、1+13+13で、その2つ次の39人の場合は、13+13+13か1+19+19で作る
ことになるんだと思います。33人はどうするんだろう、というのを現在考え中。


 GAIさんからのコメントです。(平成30年2月15日付け)

 DD++さんの表し方を研究してみると、この構成方法を正調カークマン問題(15人を3人の5
班に分け7日間続ける)に適応すれば、15人を、A,B:0,1,2,3,4,5,6とCで表せば、

 n日目(n=1,2,3,4,5,6,7)に組む5班のメンバーを

(A:n,B:n,C),(A:n+1,A:n+2,A:n+4),(A:n+3,B:n+1,B:n+5),(A:n+6,B:n+2,B:n+3),(A:n+5,B:n+4,B:n+6)

で構成できると簡潔に表現できるんですね。なんかスッキリです。


 りらひいさんからのコメントです。(平成30年2月21日付け)

 私もひとつ作りました。(結局コンピュータの力を借りてしまいました…。)

 21人に、A:0〜D:4 および E と名前を付けます。以下において、Eを除く名前の数字側は
5を法とする剰余によって同一視します。

1〜5日目の組は、k=1〜5として、

(A:k+0, B:k+0, E)、(A:k+1, A:k+2, C:k+3)、(B:k+1, B:k+4, D:k+2)、(C:k+1, C:k+2, A:k+3)
(D:k+0, D:k+1, C:k+4)、(A:k+4, B:k+3, D:k+3)、(B:k+2, C:k+0, D:k+4)

6〜10日目の組は、k=6〜10として、

(C:k+0, D:k+0, E)、(A:k+0, A:k+2, B:k+3)、(B:k+1, B:k+2, C:k+2)、(C:k+1, C:k+3, B:k+4)
(D:k+1, D:k+3, A:k+1)、(A:k+3, B:k+0, D:k+4)、(A:k+4, C:k+4, D:k+2)

 15人のときの例から、(12M+3)人のときは、 [ 1 + (6M+1) + (6M+1) ] のタイプの構成の可
能性に期待が持てそうなのと同様に、この21人の例から、(24L+21)人のときは、
[ 1 + (6L+5) + (6L+5) + (6L+5) + (6L+5) ] で二巡のタイプの可能性の夢が見えますね。

 ただ、実際にそういう構成が存在するのかは全然わかりませんので、次の人数でダメにな
るかもしれませんけど。


 GAIさんからのコメントです。(平成30年2月22日付け)

 5日ずつに分けるアイデア面白いですね。これを図形的に解釈しようと、中心にEを配置し、
4つの同心円を書いて、各円を5等分する点に、

 外円からA:0〜4 、次の円にB:0〜4 、次を  C:0〜4 、最内円にD:0〜4

の計21個の点を打ち、第1日目と第6日目のメンバーを三角形として描くと、他のメンバーは
これらを各1/5回転することで出来ていく各三角形の頂点に当たるメンバーで組んでいくこと
になる。

 なかなか複雑な図形が現れるものですね。(よくこのパターンを発見できましたね。)

 更に人数を増やす。
(次は27人を3人ずつの9班に分け13日間でしょうが、挑戦する意欲が今は起きません。ただ
し完成されている表はサイトで入手できました。)

 その前に、プレカークマン問題として、9人を3人ずつの3班に分け4日間の散歩の組合わせ
に挑戦してみて下さい。

 また、これを図形的に構成する方法も探ってみてください。(自己流の方法は編み出しまし
たが、もっと華麗な方法があるような気がしています。)


 ハンニバル・フォーチュンさんからのコメントです。(平成30年2月22日付け)

 プレカークマンの件ですが、知人に以下のように教わりました。

【1】円に内接する正9角形を考えます。右回りに接点に以下の名前をつけます。
   0,1,2,3,4,5,6,7,8

【2】点0が二等辺三角形の頂点となるような4種類の二等辺三角形をつくります。

  (1) 801 、(2) 702 、(3) 603 、(4) 504

【3】円に描かれる二等辺三角形全体で三回対称となるように、(1)から(4)までのそれぞれ
  で合同な二等辺三角形を2つづつ追加します。

  (1) 801 234 567 、(2) 702 135 468 、(3) 603 714 825 、(4) 504 837 261

【4】上がプレカークマンの解となっています。(※これを聞いたときにはかなり驚きました。)

 これに mod 9 で、1 を加えたものが以下となります。

  (1) 012 345 678 、(2) 813 246 570 、(3) 714 825 036 、(4) 615 048 372

 上記の(2)と(4)とが、以下の魔方陣の各行(2)およびに、各列(4)に出現しています。

183
642
507

 同様に、(1)と(3)とが、以下の方陣の各行(1)およびに、各列(3)に出現しています。

012
345
678


 DD++さんからのコメントです。(平成30年2月23日付け)

 3n人で3人グループn個を作っていく方法が1つわかれば、それを利用して、9n人のときの
グループの作り方を1つ見つけることができます。

 なので、3人で3人グループを作る自明解から一般の3^k人で3人グループを作っていく方法
が構成できますね。

 カークマンの15人の解からは45人や135人の解が作れますし、21人の解から63人の解や
189人の解が作れます。

 これは、グループ人数が3人に限らず素数である場合に一般化できるようです。また、4人
グループの場合もできそうなので、素数の累乗の場合にまで一般化できるのかもしれませ
ん。(6人の場合はどうも無理そう)


 ハンニバル・フォーチュンさんからのコメントです。(平成30年2月23日付け)

 プレカークマン問題についてです。先に「プリクラ問題」をご案内します。

●「プリクラ問題」より引用します。

(引用開始)

 プリクラ問題とは、@hiroko_TB あしやまひろこ氏による、次のような問題である。

 n人いる
 1回でm人を同時に撮れるプリクラ機がある
  このとき、どんな2人のペアも必ずどれかの写真に一緒に写っているようにするには、そ
 のプリクラ機による撮影が何回必要か?

(引用終了)

 さて、次のような問題と、その解を示しておきます。

問A 13人いる。1回で4人を同時に撮れるプリクラ機がある。このとき、どんな2人のペアも必
  ずどれかの写真に一緒に写っているようにするには、そのプリクラ機による撮影が13回で
  十分か?

解A  13人に0から12までの背番号をつける。

0  1  5 11
1  2  6 12
2  3  7  0
3  4  8  1
4  5  9  2
5  6 10  3
6  7 11  4
7  8 12  5
8  9  0  6
9 10  1  7
10 11  2  8
11 12  3  9
12  0  4 10

が求める解のひとつである。

※円周を13等分して、その境目の点に0から12までの名前を右回りに順につけていきます。
四辺形 0  1  5 11 を順に右回りに円のなかで回転していったものが解となります。

 このあたりは、既に本掲示板の常連の皆様には馴染みの深いものだと思います。

 次に、上のプリクラ問題(問A,解A)をもとに、プレカークマン問題を考えます。

問B  0番から12番までの学生が13人いる。0番、1番、5番、11番は男子学生である。残り
   は女子学生である。

  1回で4人を同時に撮れるプリクラ機がある。このとき、どんな2人のペアも必ずどれかの
 写真に一緒に写っているようにするには、そのプリクラ機による撮影が13回で十分か?

解B(繰り返しですみません)

0  1  5 11
1  2  6 12
2  3  7  0
3  4  8  1
4  5  9  2
5  6 10  3
6  7 11  4
7  8 12  5
8  9  0  6
9 10  1  7
10 11  2  8
11 12  3  9
12  0  4 10

が求める解のひとつである。

問C  プレカークマン問題。

解C  解Bで撮影された写真を、男子学生が写っているもの別に分類します。

0  1  5 11

2  3  7  0
8  9  0  6
12  0  4 10

3  4  8  1
9 10  1  7
1  2  6 12

7  8 12  5
4  5  9  2
5  6 10  3

6  7 11  4
10 11  2  8
11 12  3  9

 初日は、男子学生0番が写っている写真ごとに女子学生を班別けします。
 二日目は、男子学生1番、三日目は、男子学生5番、四日目は、男子学生11番が写ってい
る写真ごとに女子学生を班別けします。(男子学生のみが写っている写真は使いません。)

……これも一種の図形による解法といえなくもないと存じますがいかがでしょうか。

 GAIさんからのコメントです。(平成30年2月23日付け)

 プレカークマン問題に対する面白い2通りの構成方法、とても参考になります。

 自分が思い付いた構成法はちょっと長くなりますが、次のようなものを考えていました。

 9人をとりあえず3人ずつA、B、C班のどれかに所属させます。
(a1,a2,a3;b1,b2,b3;c1,c2,c3)

 2つの同心円を描き、外円にはA、内円にはBの3人を12、4、8時の位置に立たせる。

 中心にはCの一人を立たせる。この図形配置をfig1とする。

 次に、外円の3人は円周上を各自中心に対して120°移動する。

 内円の3人は同じく-120°移動する。

 中心はCの2人目に交代する。この図形配置をfig2とする。

 同じく、各円上3人は各自円周上を移動し、中心はCの3人目に交代。この図形配置をfig3
とする。

 こうしたfig1,fig2,fig3で、

1日目:12時の位置に並ぶ3人組の3班で散歩:(a1,b1,c1)、(a2,b3,c2)、(a3,b2,c3)
2日目: 4時の位置に並ぶ3人組の3班で散歩:(a2,b2,c1)、(a3,b1,c2)、(a1,b3,c3)
3日目: 8時の位置に並ぶ3人組の3班で散歩:(a3,b3,c1)、(a1,b2,c2)、(a2,b1,c3)
4日目:A、B、C班での3人組の3班で散歩:(a1,a2,a3)、(b1,b2,b3)、(c1,c2,c3)


 りらひいさんからのコメントです。(平成30年2月27日付け)

 素数とは便利なものですね。DD++さんが書いたものとハンニバル・フォーチュンさんが書い
たものを参考にして私も少し書いてみます。

 pを奇素数とする。pn人の女生徒が毎日p人ずつpn-1班に分かれて散歩に出かけることを
(pn-1)/(p-1)日繰り返したとき、どの二人も一回だけ同じ班になった。班分けの方法は?

という問題に対して、統一的に説明できる編成方法があります。そして、n=2のときには、その
方法を次のように言い直すことができます。

 p行×p列のマスを用意し、0からp2-1までの数を、次の(A)、(B)ようにマスに並べる。

(A) 次のように数字を順番に並べて方陣[※]を作る。

     0      1   …     p-1
     p    p+1   …    2p-1
    …     …           …
(p-1)p     …   …   p^2-1


(B) 次のように魔方陣[i] ( i=1,2,…,(p-1)/2 ) を作る。

 pは奇数なので中心にはマスがある。(上下左右どこから数えても(p+1)/2マス目。)

iが奇数のときは、中心のマスから右に(i-1)/2列・下に(i+1)/2行移動したマスをスタートとして
"0"を入れる。

iが偶数のときは、中心のマスから左に(p-i+1)/2列・上に(p-i-1)/2行移動したマスをスタート
として"0"を入れる。

 以下では、最下行のひとつ下は最上行であり、最右列のひとつ右は最左列であるというよ
うにつなげて考える。(トーラス)

 "0"を入れたマスから左下に向かってひとマスずつ順番に数字を入れていく。

 jを整数として"jp-1"となる数を入れたら、そのマスから右にi-1列・下にi+1列移動したマス
に次の数"jp"を入れ、また左下に向かいながら入れていく。

 このようにしてすべてのマスを埋めて魔方陣を作る。

 各日の班分けは次のように行うことができる。

  1日目 方陣[※]の各行を班とする。
  2日目 方陣[※]の各列を班とする。
  3日目 魔方陣[1]の各行を班とする。
  4日目 魔方陣[1]の各列を班とする。
  …
  p日目 魔方陣[(p-1)/2]の各行を班とする。
p+1日目 魔方陣[(p-1)/2]の各列を班とする。

 例をあげましょう。p=7とします。

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


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


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


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


 それぞれの行と列で8日間の班分けができます。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年2月27日付け)

 とてつもなく素晴らしいです。ため息が出ます。プリクラ問題に応用しますと、

《cyclic difference sets with Singer parameters (v,k,λ)=(n^2+n+1,n+1,1) for any n prime》

についての等価な、'cyclic'に頼らない新たな構成方法がある、ということのようですね。

 なお、nとしてはp(prime)の他に、pの巾乗についても'cyclic difference sets'が見つかってい
るようです。

※cyclicというのは円周を等分にしておいて分割された円弧どうしの接点をいくつか選んで
 回転させていくやつです( (v,k,λ)=(n^2+n+1,n+1,1) のとき。)

 vが13、kが4、λが1では、男女織り混ぜ13人いて、4人づつでプリクラ写真を撮り……なの
ですが、円周を13等分しておいて、0, 1, 5,11 から写真を撮り、以下、

1, 2, 6,12
2, 3, 7, 0
3, 4, 8, 1
……

と撮影していくのでした。そして、個々の男子学生別に写真をよりわけて女子だけ(3^2人)
についての「プレカークマン」の解になっていたのでした。

 方陣・魔方陣による解は男女おりまぜ13人、女子だけで9人の特殊なケースだけであら
われる面白さだと思っていましたが、女子人数が奇素数の自乗のときにでも構成できると
のこと、驚きました。勉強になりました。ありがとうございます。


 りらひいさんからのコメントです。(平成30年2月28日付け)

 スタート位置を小難しく決めたけれど、実際はどのマスから始めても班分け自体には影響
しません。ただ、斜めの列の和がそろわないので魔方陣にならないだけです。

 斜めをそろえて魔方陣にするために、スタート位置を計算しています。魔方陣にするには
中心のマスに真ん中の数(p^2-1)/2が来るようにすればいいだけなので、次のように作るこ
ともできます。(むしろ、こっちのほうが間違えにくいかな。)

 中心のマスに"(p^2-1)/2"を入れ、そこから順番に先のルールに従って数を入れていく。
(または、一番右上のマスに"(p-1)p/2"を入れて、そこから順番に数を入れていく。)

 "p^2-1"まで入れたらその次のマスを"0"として再び順番に数を入れていき、すべてマスが
埋まったら完成。


 DD++さんからのコメントです。(平成30年2月28日付け)

 私は円筒で似たようなことを考えていたのですが、なるほど、n=2の場合はトーラスでもい
けるんですね。ところでこのトーラスを使う方法って、n>2の場合について行うと何が起こる
のでしょう?すなわち、例えばn=3の場合でも同様の方法でマジックキューブを作れるはず
で、それを(p^2+p+1)/3-1回繰り返したら何が起こるのでしょう。

 pが3N+1型素数の場合はこれがきちんと整数になりますが、それでも失敗するのでしょう
か?

 pが3や3N-1型素数だった場合はこれは整数になりませんが、切り上げた個数だけ作った
ときに何が起こるのでしょう?


 GAIさんからのコメントです。(平成30年2月28日付け

 25人をとりあえず5人ずつA,B,C,D,E班のどれかに所属させます。
(a1,a2,a3,a4,a5;b1,b2,b3,b4,b5;c1,c2,c3,c4,c5;d1,d2,d3,d4,d5;e1,e2,e3,e4,e5)

 4つの同心円を描き、最外円にはA,その内円にはBの5人を,さらにその内円にはC,最内円
にはDのメンバーを各円周上の正5角形の頂点の位置に立たせる。

 中心にはEの一人を立たせる。この図形配置をfig1とする。

 次に、外円のAの5人は円周上を各自中心に対して1/5回転移動する。(並んでいる順は崩
さずに移動、以下も同様に)Bの5人は同じく-1/5回転移動する。Cの5人は-2/5回転,Dの5人
は-3/5回転の移動をする。中心はEの2人目に交代する。この図形配置をfig2とする。

 同じく、各円上5人は各自円周上を上記の分を移動し、中心はEの3人目に交代。この図形
配置をfig3とする。

 これを4回繰り返しfig5までを作る。こうしたfig1,fig2,fig3,fig4,fig5で、

1日目:12時の位置に並ぶ5人組の5班で散歩
(a1,b1,c1,d1,e1),(a5,b2,c3,d4,e2),(a4,b3,c5,d2,e3),(a3,b4,c2,d5,e4),(a2,b5,c4,d3,e5)

2日目:1*12/5時の位置に並ぶ5人組の5班で散歩
(a2,b2,c2,d2,e1),(a1,b3,c4,d5,e2),(a5,b4,c1,d3,e3),(a4,b5,c3,d1,e4),(a3,b1,c5,d4,e5)

3日目:2*12/5時の位置に並ぶ5人組の5班で散歩
(a3,b3,c3,d3,e1),(a2,b4,c5,d1,e2),(a1,b5,c2,d4,e3),(a5,b1,c4,d2,e4),(a4,b2,c1,d5,e5)

4日目:3*12/5時の位置に並ぶ5人組の5班で散歩
(a4,b4,c4,d4,e1),(a3,b5,c1,d2,e2),(a2,b1,c3,d5,e3),(a1,b2,c5,d3,e4),(a5,b3,c2,d1,e5)

5日目:4*12/5時の位置に並ぶ5人組の5班で散歩
(a5,b5,c5,d5,e1),(a4,b1,c2,d3,e2),(a3,b2,c4,d1,e3),(a2,b3,c1,d4,e4),(a1,b4,c3,d2,e5)

6日目:A,B,C,D,E班での5人組の5班で散歩
(a1,a2,a3,a4,a5),(b1,b2,b3,b4,b5),(c1,c2,c3,c4,c5),(d1,d2,d3,d4,d5),(e1,e2,e3,e4,e5)

となり、比較的スムーズに班編成を構成することが出来ました。これで7^2=49人も構成でき
るような気分(まだ実際にはやっていませんが・・・)


 DD++さんからのコメントです。(平成30年2月28日付け)

 同心円を4つではなく5つ書いてEの人たちも円周上に並べる(移動させない)と、完全に1枚
の図が1日のグループ分けに対応する図になりますが、それよりも中心にEの人をそれぞれ
置いて5枚の図で考える方に利がある話ってなにかありますかね?


 りらひいさんからのコメントです。(平成30年3月1日付け)

 n=2のときの魔方陣の構築方法のように、数字を規則的に配置して、n>2のマジック(ハイ
パー)キューブを作ることを考えます。このとき、各数をn桁のp進法表記で考えると、同じ列に
はそれぞれの桁について、0からp-1までのものが一つずつ含まれることになると思います。

 つまり、"0"のある列には各桁に0を含む数は入らないので、同じ列に使える数は(p-1)^n個
です。

 一列につき"0"を除いてp-1個、一つのマジックキューブについてn列使うので、作れるマジッ
クキューブは最大で(p-1)^(n-1)/n個になります。

 つまり、n=3でマジックキューブを(p^2+p+1)/3-1個作ったら、"0"を含む列に複数回出てくる
数字があります。

 これを回避するためには、規則的な構築ではないマジックキューブを採用するか、マジック
キューブを(p-1)^(n-1)/n個以下としそれ以外のものは和が一定ではない方陣にするなど、別
のアプローチが必要になると思われます。

 もともと私が考えていた班編成の方法は、特定のキーにより(p^n-1)/(p-1)日それぞれで
別々に班員が求まるものです。

 この編成方法を使用し、n日間の班構成を組み合わせてp×…×pに配列したものの集合
を構成できるか考えていますが、まだわかっていません。

 n=2の場合には、方陣の一つを順番に並べたものにすれば、あとのp-1日はどの二日を組
み合わせても魔方陣が作れてしまいます。すなわち、同じ編成方法であっても魔方陣にする
ときの日にちの選び方は(p-2)!!通りあるわけです。私が先に示したものはその中の一例に
すぎません。どの奇素数pに対しても作れるものとして、ほかには次のようなものもあります。

 i=1,…,(p-1)/2 左下に向かってひとマスずつ順番に数字を入れていく。

 jを整数として"jp-1"となる数を入れたら、そのマスから左に2i列・下に2i+1行移動したマス
に次の数"jp"を入れる。

 i=1,…,(p-1)/2 左下に向かってひとマスずつ順番に数字を入れていく。

 jを整数として"jp-1"となる数を入れたら、そのマスから左にi+1+(p-1)/2列・下にi+1行移動
したマスに次の数"jp"を入れる。

 要は、ジャンプするときの左への移動距離と下への移動距離が、2,3,…,p(mod p)を網羅し
ていればなんでもいいです。(前の投稿で示した例だと左へp-i+1列・下へi+1行になります。)

 左下に向かってk-1マス飛ばしで(k個先のマスへ)順番に数字を入れていくのでもいいです。
(kとpは互いに素。)

 その場合はジャンプするときの左への移動距離と下への移動距離がmod pでkを除く0から
p-1までを網羅させます。

 数字を並べる向きを45度ではない斜めにするとか、飛ばす数や向きをを魔法陣ごとに変
えたりとか、同じ班編成になる魔法陣でもかなり自由に作れます。まあ、見た目が違っても
結局中身は同じことをしているだけなんですけど。


 DD++さんからのコメントです。(平成30年3月1日付け)

 「つまり、n=3でマジックキューブを(p^2+p+1)/3-1個作ったら、
」・・・すみません、ミスりまし
た。p^2の場合には、最初にpの位が一致するものと1の位が一致するものが個別に必要な
ので、2日目までは魔法陣とは別の手段を取ります。

 同様に、p^3の場合は、p^2の位、pの位、1の位のうち2つが一致するものに3日使いますが、
続けて1つが一致するものをp^2方陣を利用して3p-3日かけて行うことになるので、p^3マジッ
クキューブを作る回数は(p^2+p+1)/3-1-(p-1)回とするのが正しかったです。

 ということで、「マジックキューブを(p-1)^(n-1)/n個以下とし」とピタリ一致しているので、綺
麗に構成できる可能性があると思いますが、どうでしょう?


 りらひいさんからのコメントです。(平成30年3月2日付け)

 証明は全然できてないですし、実際の例を組み立てたりもしていませんが、なんとなくでき
そうではありますよね。大雑把に次のようなイメージをしています。

 pを奇素数とする。n次元超立方体に対し、上下,左右,前後,etc.を互いに接続してループ状
にしたものを考える。(トーラスの拡張みたいな感じ。)超立方体の各辺に平行な方向を辺方
向と呼ぶことにする。

 p×…×p個の点を等間隔に格子状に各辺方向に合わせて配置する。

 これらの点のうち任意の二点を通る直線を引くとその直線はループして閉曲線となり、直
線上にはちょうどp個の格子点が存在する。

 すべての格子点に対し、この直線に平行な直線を引くと、直線の数はp^(n-1)本となる。

 格子点を女生徒に対応させ、各平行直線上のp個ずつの点をそれぞれ一つの班とする。

 こうすることで、直線の向き(傾き)によって一日の班分けができる。ただし、直線の向きが
異なっても同じ班分けになる場合がある。このような同じ班分けのものを同一視すると、班
分けの方法は全部で(p^n-1)/(p-1)通り存在するので、それらを各日にちに割り当てる。

 このとき、ある二人が同じ班になるのは一日だけである。

 pはnN+1型の素数とする。(ほかにもOKなのがあるかも?とりあえずで。)各格子点に順
番に0からp^n-1までの番号を振る。
(ある辺方向に進むとそれに対応するp進法表記の桁が順番に変化するようにする。)
(番号の振り方は察してください。普通に考えられる振り方です。)

 班分けをn日分選び、対応する直線群を引く。ただし、このとき、各日にちに対応する向き
のベクトルがn次元空間を張るようにn日を選ぶ。(一点を通るn本の直線がn-1次元面内に
おさまってはいけない。)

 ベクトル(直線群)が互いに直交するように変換する。(線型変換とかアフィン変換みたいな
イメージ。)

 変換後に格子状に点がならぶので、対応する番号をそのまま格子状に記録する。
(変換せずに直線群を直接たどって番号を記録してもよい。)

 かぶらないようにn日ずつをうまく選ぶことができれば、超立方体のマス目に番号を配置し
各辺方向が一日の班分けになる構成ができる。

 また、すべての辺方向と直交しない向きとなる班分けの日だけをn日分組み合わせてでき
る番号配置は、各辺方向の一列の和が一定となり、変換または記録の中心に真ん中の番
号(p^n-1)/2をもってくるようにすることでマジック(ハイパー)キューブにできる。


#大雑把なイメージなので、きちんと証明に落とし込めるかはわかりません。
(ただし、私にはもうそこまでもっていく気力はありません。)

 実際の例の組み立てに関しては、「n日分」の選び方と「変換」または「番号拾い」の処理を
どうするかですね。(さらっと簡単に実装できればいいんですが。)

 あと、「かぶらないようにn日ずつをうまく選ぶことができれば」の部分がうまくいくかどうか
がまだわかっていません。
(でも、選択の自由度は高そうなのである程度どうとでもなりそうな気はします。)


 DD++さんからのコメントです。(平成30年3月4日付け)

 やっぱり、できそうだけど本気で証明する気にはあまりなれない感じですよね。地味な面倒
さが……。

 魔方陣とは話が逸れますが(むしろ元の拡張カークマン問題に戻る感じですが)、前半につ
いては、実は私も大まかには似たような想像をしています。

 一部異なるのは、私はトーラスではなく円筒(n次元の場合はループしない1次元とループす
るn-1次元……トーラス筒の方が正確?)でやっていることですね。

 というのは、りらひいさんと同じ番号付けをしたとして、無数にある組み合わせから重複を
考慮するなんてやらなくても、「片方は0、片方はp進法で0を除いた最上位の数が1」という
p^(n-1)+p^(n-2)+……+p^2+p+1 組でそれぞれ2点を通る線を引けば、それを利用して
(p^n-1)/(p-1) 日分を重複なく構成でき、その場合は p^(n-1) の位の方向はループの必要
がなく、p^(n-1) 本の閉曲線ではなく p^(n-1) 重螺旋(もしくは軸と平行な直線)にしておけば
十分だからです。

 この1つの方向だけ軸として特別視する方法は、トーラスを使うのと比べて対称性が1つ落
ちるため、魔方陣やマジックキューブを作るには向きません。

 しかし反面、グループ作りの面ではp以外の因数を持つ人数への拡張性に優れています。

 p^(n-1)+p^(n-2)+……+p^2+p+1 組を、最初が1である p^(n-1) 組と、最初が0である
p^(n-2)+……+p^2+p+1 組に分ければ、グループの作り方を軸方向にずれていくものとトー
ラス内だけで完結するものに明確に分けて構成することができるからです。

 これを用いると、例えば135人を3人組45個に分けることを67日行う解を以下のように構成
できます。

 まず、135人を9人ずつ15グループに分け、それぞれ3×3のトーラスを構成しておきます。

シーズン1(1日目から13日目)

 トーラスを適当に3個ずつ5ブロックに分け、それぞれを積み重ねます。これを27人組5ブロ
ックと考えて、各ブロックで同じブロックの全員と1度ずつ同じグループになるようにします。
3^2+3+1=13日かかります。(これはシーズン1だけ)

シーズン2(14日目から22日目)

 トーラスを適当に3個ずつ5ブロックに分け、それぞれを積み重ねます。ただし、シーズン1
で同じブロックに入ったトーラス同士は同じブロックに入らないようにします。これを27人組5
ブロックと考えて、各ブロックで軸方向にずれていくタイプのグループだけ作ります。3^2=9日
かかります。

シーズン3(23日目から31日目)

 トーラスを適当に3個ずつ5ブロックに分け、それぞれを積み重ねます。ただし、シーズン1、
シーズン2で同じブロックに入ったトーラス同士は同じブロックに入らないようにします。これを
27人組5ブロックと考えて、各ブロックで軸方向にずれていくタイプのグループだけ作ります。
3^2=9日かかります。

シーズン4(32日目から40日目)

シーズン5(41日目から49日目)

シーズン6(50日目から58日目)

シーズン7(59日目から67日目)

と、同様に繰り返します。

 問題は、「15個のトーラスを3つずつ5ブロックに分けるのを7シーズン繰り返してどのトーラ
ス同士も一度ずつ同じブロックに入るようにする」方法ですが、実は、これは本家のカークマ
ンの問題そのものなので、可能なことも、具体的な手順もわかっています。

 よって、これで135人、3人組、67日の解が構成できました。

 こんな感じで、p人グループを作る場合、p*q 人の場合の解が分かっていれば、p^n*q 人
の場合の解が構成できます。

 有限体の理論を用いれば、pが素数の場合だけでなく素数冪の場合に話を拡張できるよう
です(勉強中)。



  以下、工事中!