fortran66のブログ

fortran について書きます。

六角星陣の解

イアン・スチュアート『数学の秘密の本棚』に、いわゆるダビデの星と呼ばれる六芒星の交点上に1〜12までの数を置いて、どの直線上の数の和も等しくなるような、魔方陣様の並びを求める問題があります。更なる制限として、星の頂点6個に置いた数の和もまた同じになるようにするように求められています。ただしヒントとして和は26になることが与えられています。

本文では、星の頂点の和を26にするのは、問題を難しくするためと言っていますが、実際はこれが厳しい条件で、可能な組み合わせをかなり限定してくれて助かります。とりあえず、12と11は星の頂点に来ることが出来ないことと、1,3は頂点に来なければならないことが分かります。

この先の解き方がよく分からないので、我慢強く場合分けをして求めてみたところ、本の解答で1通りとしてある組み合わせのほかに、いくつか条件を満足する数字の並べ方が見つかりました。

(問題を正しく理解していて、かつ)数え落としが無ければ、解は以下の5通りになります。このうち、最初のものは本で与えられているものを回転させたものに一致します。

      3                         4
     / \                      / \
 2─12───11─1          1─12───11─2
  \/      \/             \/      \/
   5      8               7      5
  /\     /\             /\     /\
 6──9───7──4          3──8───9──6
     \ /                  \ /    
      10                        10



      4                         7
     / \                      / \
 3─12───10─1          8─12───4──2
  \/      \/             \/      \/
   8      5               6      10
  /\     /\             /\     /\
 2──6──11──7          1──9──11──5
     \ /                  \ /    
       9                         3



      1                    
     / \                  
 2─12───9──3          
  \/      \/            
   6      11            
  /\     /\            
 7──10──4──5          
     \ /               
       8                 

解き方としては、12と11を対称性により重複を省いた可能な位置に配置して三通りに場合分けし、一直線上に2個以上の数字が並ぶまで、さらに10、場合によっては9を非等価な点に配置してゆく方法をとりました。一直線上に2個の数字が並んだ後は、可能な残りの2個の組み合わせを全て配置してといてゆきます。12と11が一直線上にある場合は簡単ですが、その他の場合は結構複雑で、思ったよりも時間がかかりました。

            12と11の可能な非等価な配置。
 
                       
     / \                 / \          / \      
  ─12───11─       ─12─── ──    ─12─── ── 
  \/      \/       \/      \/    \/      \/
                                   11
  /\     /\       /\     /\    /\     /\
  ── ─── ──       ── ──11──    ── ─── ──
     \ /             \ /          \ /    
                                              

もっと簡単だろうと予想していい加減にやり始めたので、数え落としがあるかもしれません。またもう少し楽な解き方があるかもしれません。