■剰余系と整数生成定規(その48)

[Q]目盛りのついていないマスで,1からnまですべてはかれるようにするにはどうしたらいいか?

 n=41が可能な集合として,

  t={12,13,16,25,28,29,41}

がある.

 差分集合

  d={12,13−12,16−13,25−16,28−25,29−28,41−29}

={12,1,3,9,3,1,12}

={1,1,3,3,9,12,12}

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

 各1回まで使うことができるから

  {1,3,9,12}

の9を除き,2回使えると考えてよい.面倒くさがらずに計算すると

1=1

2=2・1

3=3

4=1+3

5=2・1+3

6=2・3

7=1+2・3

8=2・1+2・3

9=9

10=1+9

11=2・1+9

12=3+9

14=2・1+3+9

15=2・3+9

16=1+2・3+9

17=2・1+2・3+9

 ここまでは{1,1,3,3,9}で生成できた.

  17+1=12+6 30=2・12+6

  17+k=12+5+k 30+k=2・12+5+k

  29=12+17 41=2・12+17

 こうして,1から41まですべて生成することができる.

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