■既約性判定基準(その74)

[Q]目盛りのついていない長さ6の定規に(両端以外に)目盛りを2つ刻んで,長さ1から6まですべてはかれるようにするにはどうすればいいか?

[A]目盛り間隔の配置を{1,3,2},目盛りを{0,1,4,6}とする.

===================================

[Q]目盛りのついていない長さ9の定規に(両端以外に)目盛りを3つ刻んで,長さ1から9まですべてはかれるようにするにはどうすればいいか?

[A]目盛り間隔の配置を{1,3,3,2},目盛りを{0,1,4,7,9}とする.

あるいは

[A]目盛り間隔の配置を{1,1,4,3},目盛りを{0,1,2,6,9}とする.

===================================

この問題の環状版を考える。

[Q]目盛りのついていない長さLの環に目盛りをm個刻んで,長さ1からLまですべてはかれるようにするにはどうすればいいか?

===================================

 具体例をといくつかあげておきたい.

[1]m=3,L=7:{1,2,4}

[2]m=4,L=13:{1,4,6,2},{1,7,2,3}

[3]m=5,L=21:{1,3,10,2,5}

[4]m=6,L=31:{1,2,5,4,6,13}

[5]m=7:存在しない

===================================

[6]m=10,L=91:

{1,3,9,11,6,8,2,5,28,18}

{1,5,4,13,3,8,7,12,2,36}など6種類

 一般に,m=p^k+1のとき,オイラー関数を用いて

  φ(m^2−m+1)/6k通り

  φ(91)=91(1−1/7)(1−1/13)=72

  m=10=3^2+1→φ(91)/12=6,L=m^2−m+1

===================================