【問題１】

　　　　３０個


【問題２】

        +---+---+---+---+
        |   |       |   |
        +   +---+---+   +
        | * | * | * |   |
        +---+   +   +---+
        | * | * | * |   |
        +   +---+   +   +
        | * | * | * |   |
        +---+   +---+---+

    (考え方）３ｘ３の答え(*の部分）をもとに上側と右側の部分を拡張した


【問題３−１】

　　(答え）　マッチ棒の数をＬ（ｎ）とすると

　　　　　　Ｌ（ｎ）＝２＊ｎ＊（ｎ＋１）

   （求め方）
　　　　　　Ｌ（１）＝　４
　　　　　δＬ（ｎ）＝　Ｌ（ｎ）−Ｌ（ｎ−１）とすると、δＬ（ｎ）＝４＊ｎとなる。
　　　　　これより、Ｌ（ｎ）＝ΣδＬ（ｋ）として、上記の答えを得る。

　　　　　ｅｘ．Ｌ（４）＝２＊４＊（４＋１）＝４０


【問題３−２】

　　(答え）　正方形の個数をＳ（ｎ）とすると

　　　　　　Ｓ（ｎ）＝ｎ＊（ｎ＋１）＊（２＊ｎ＋１）／６

   （求め方）
　　　　　　ｍｘｍの正方形は、横方向に（ｎ−ｍ＋１）個、縦方向にも（ｎ−ｍ＋１）個を配置できるので
　　　　　　全体では、（ｎ−ｍ＋１）＊＊２個が存在する。従って、
　
　　　　　　Ｓ（ｎ）＝ｎ＊＊２　＋　（ｎー１）＊＊２　＋　（ｎー２）＊＊２　＋．．．＋　１＊＊２

　　　　　　　　　　＝Σｋ＊＊２＝　Σ｛ｋ＊（ｋ−１）＋ｋ｝
　　　　　　　　　　＝ｎ＊（ｎ＋１）（ｎ−１）／３＋ｎ＊（ｎ＋１）／２
　　　　　　　　　　＝ｎ＊（ｎ＋１）＊（２＊ｎ＋１）／６


【おまけ１】

　　（答え）　以下の２個。ただし、対称解を別物として数える場合は、１６個。

 　　　　      ==== 1 / 8 ====
             +---+   +---+---+
             |   |   |   |   |
             +   +---+   +   +
             |   |   |   |   |
             +---+   +   +---+
             |   |   |   |   |
             +   +---+---+   +
             |   |       |   |
             +---+---+---+---+

              ==== 2 / 16 ====
             +---+   +---+---+
             |   |   |       |
             +   +---+---+---+
             |   |       |   |
             +---+---+---+   +
             |           |   |
             +---+---+---+---+
             |       |       |
             +---+---+---+---+

             【問題２】の解は、最初の解を上下反転したものに一致している。

             ｎ＝５の場合は、９１個。ただし、対称解を別物として数える場合は、７２０個。

　　（求め方）　プログラム(最後に添付）による探索で求めた。(プログラムの説明は割愛)

　　　  
【おまけ２】　　

　　（答え）　取り除くマッチ棒の最小数をｍ（ｎ）とすると

　　　　　　　ｍ（ｎ）＝［（ｎ＊＊２＋１）／２］＋１

　　　　　　　ただし、［ａ］はガウス記号で、ａの整数部分を表す。（ｅｘ．［３］＝３，［３．５］＝３）

　　　　　　　ｎ　　ｍ（ｎ）
　　　　　　----------------
　　　　　　　３　　　６　
　　　　　　　４　　　９
　　　　　　　５　　１４
　　　　　　　６　　１９
　　　　　　　７　　２６　

　　（求め方）

　　　　ｎ＝３は、明らか（『正方形の消滅』参照）であるので、ｎ＞＝４について調べることにする。

　　　　１）取り除くマッチ棒の数がｍ（ｎ）となるような解が存在することを以下に示す。
　　　　　　ｎ＝４は、【問題２】で明らかである。
　　　　　　ｎ＞４については、４ｘ４の解をベースとして以下の手順で作ることができる。

　　　　　　ｎが偶数のとき、ｎｘｎから（ｎ＋１）ｘ（ｎ＋１）の解を作る手順
　　　　　　　　ａ）ｎｘｎの上側に左から右へと１ｘ２の長方形を並べる
　　　　　　　　ｂ）ｎｘｎの右側に上から下へと２ｘ１の長方形を並べる　　　
　　　　　　　　ｃ）右下の１ｘ１の正方形の領域は、下の部分を開けたままにする

　　　　　　ｎが奇数のとき、ｎｘｎから（ｎ＋１）ｘ（ｎ＋１）の解を作る手順
　　　　　　　　ｄ）ｎｘｎの左側に上から下へと２ｘ１の長方形を並べる。
　　　　　　　　ｅ）ｎｘｎの下側にある１ｘ１の正方形（下が開いている）は、２ｘ１の長方形にする　　　
　　　　　　　　ｆ）ｅ）で作られた長方形ではさまれた部分を１ｘ２の長方形でうめる
　　　　　　　　ｇ）ｄ），ｅ）にはさまれた１ｘ１の正方形の領域は、下の部分を開けたままにする

　　　　　　上記の手順ａ）〜ｇ）により、ｎ＝４から順にｎ＝５〜８を作成する例を示す。
　　　　　　
                  +--+--+
                  |  a  |は、手順ａ）の操作で作られたことを表す。（ｂ〜ｇも同様）
                  +--+--+
 
　          　ｎ＝４の場合（ベース解）　
                       +---+---+---+---+
                       |   |       |   |
                       +   +---+---+   +
                       |   |   |   |   |
                       +---+   +   +---+
                       |   |   |   |   |
                       +   +---+   +   +
                       |   |   |   |   |
                       +---+   +---+---+
                  
             ｎ＝５の場合　　
                       +---+---+---+---+---+
                       |   a   |   a   |   |
                       +---+---+---+---+ b +
                       |   |       |   |   |
                       +   +---+---+   +---+
                       |   |   |   |   |   |
                       +---+   +   +---+ b +
                       |   |   |   |   |   |
                       +   +---+   +   +---+
                       |   |   |   |   | c |
                       +---+   +---+---+   +

        　　ｎ＝６の場合
                   +---+---+---+---+---+---+
                   |   |       |       |   |
                   + d +---+---+---+---+   +
                   |   |   |       |   |   |
                   +---+   +---+---+   +---+
                   |   |   |   |   |   |   |
                   + d +---+   +   +---+   +
                   |   |   |   |   |   |   |
                   +---+   +---+   +   +---+
                   |   |   |   |   |   |   |
                   + d +---+   +---+---+   +
                   |   | g | e |   f   | e |
                   +---+   +---+---+---+---+

        　　ｎ＝７の場合
                   +---+---+---+---+---+---+---+
                   |   a   |   a   |   a   |   |
                   +---+---+---+---+---+---+ b +
                   |   |       |       |   |   |
                   +   +---+---+---+---+   +---+
                   |   |   |       |   |   |   |
                   +---+   +---+---+   +---+ b +
                   |   |   |   |   |   |   |   |
                   +   +---+   +   +---+   +---+
                   |   |   |   |   |   |   |   |
                   +---+   +---+   +   +---+ b +
                   |   |   |   |   |   |   |   |
                   +   +---+   +---+---+   +---+
                   |   |   |   |       |   | c |
                   +---+   +---+---+---+---+   +

        　　ｎ＝８の場合
               +---+---+---+---+---+---+---+---+
               |   |       |       |       |   |
               + d +---+---+---+---+---+---+   +
               |   |   |       |       |   |   |
               +---+   +---+---+---+---+   +---+
               |   |   |   |       |   |   |   |
               + d +---+   +---+---+   +---+   +
               |   |   |   |   |   |   |   |   |
               +---+   +---+   +   +---+   +---+
               |   |   |   |   |   |   |   |   |
               + d +---+   +---+   +   +---+   +
               |   |   |   |   |   |   |   |   |
               +---+   +---+   +---+---+   +---+
               |   |   |   |   |       |   |   |
               + d +---+   +---+---+---+---+   +
               |   | g | e |   f   |   f   | e |
               +---+   +---+---+---+---+---+---+

　　　　２）解が存在するための,必要条件
　　　　　　ｌ（ｎ）を以下のように定義すると、解が存在するためには、取り除くマッチ棒の数＞＝ｌ（ｎ）を
　　　　　　満たすことが必要である。

　　　　　　　　ｌ（ｎ）=［ｎ＊＊２／２］＋１

　　　　　　　　　　　　　ただし、［ｋ］はガウス記号で、ｋの整数部分を表す。
　
　　　　　　１ｘ１の正方形はｎ＊＊２個存在する。この正方形をもっとも少ない数のマッチ棒で消滅させるには、
　　　　　　２つの１ｘ１の正方形の間の１本を取り除いて、１ｘ２ or ２ｘ１の長方形を作ることである。
　　　　　　ｎ＊＊２個の正方形をこの方法で行うとすると、［ｎ＊＊２／２］本のマッチ棒が必要である。
　　　　　　（ただし、ｎが奇数の場合は、１ｘ１の正方形が1つ余る）一方、この方法では、ｎｘｎの正方形は
　　　　　　消滅しないので、これを消滅させるために、もう1本のマッチ棒が必要となる。
　　　　　　従って、［ｎ＊＊２／２］＋１＝ｌ（ｎ）が必要である。
　　　　　　ｎが奇数の場合、１ｘ１の正方形が１つ残るが、この正方形は、ｎｘｎの正方形と辺を共有してい
　　　　　　れば、ｎｘｎの正方形を消滅させる時に、同時に消滅させることができる。
　　　　　　従って、ｎが奇数の場合も、［ｎ＊＊２／２］＋１＝ｌ（ｎ）本のマッチ棒が必要条件となる。

　　　　３）次に、ｍ（ｎ）が最小解であることを示す　
　　　　　　ｎが偶数の場合、［（ｎ＊＊２＋１）／２］＝［ｎ＊＊２／２］となり、ｍ（ｎ）＝ｌ（ｎ）が成立
　　　　　　するので、ｍ（ｎ）は最小解である。
  
　　　　　　ｎが奇数の場合、ｍ（ｎ）＝ｌ（ｎ）＋１が成り立つ。もし、ｌ（ｎ）となる解が存在しなければ、
　　　　　　ｍ（ｎ）が最小解といえる。


           補題１　下図のように、１ｘ２の長方形Ａの両側をガードされた状態で、ｘ，ｙの位置を１ｘ２と
　　　　　　　　　　２ｘ１の長方形だけで埋めることはできない。　

                     +---+       +---+
                     |   | ｘ  ｙ|   |    Ｇ１，Ｇ２は、２ｘ１の長方形又は端
                     + G1+---+---+ G2+
                     |   |   A   |   | 
                     +---+---+---+---+

　　　　　　　　　　∵　ｘ、ｙを埋めようとすると、どうしても２ｘ２の正方形ができてしまう。

           補題２　下図のように、１ｘ２の長方形がｋ個並んだ両側をガードされた状態で、ｘ１．．．ｘ２ｋ
　　　　　　　　　　の位置を１ｘ２と２ｘ１の長方形だけで埋める場合、１ｘ２の長方形は、高々（ｋ−１）個
　　　　　　　　　　しか並べることができない。　　

                     +---+                       +---+
                     |   | x1  x2   ...       x2k|   |    Ｇ１，Ｇ２は、２ｘ１の長方形又は端
                     + G1+---+---+---+---+---+---+ G2+ 
                     |   |   A1  |  ...  |   Ak  |   | 
                     +---+---+---+---+---+---+---+---+ 

　　　　　　　　　　ｘ１，ｘ２ｋの位置は、２ｘ１の長方形を配置しなければならないので、残りを１ｘ２の長方
　　　　　　　　　　形で埋めたとしても高々（ｋ−１）個となる。
　
　　　　　　補題１，２を使って、ｌ（ｎ）となる解が存在しないことを示す。

　　　　　　もし、ｌ（ｎ）の解が存在すると仮定すると、１ｘ１の正方形がｎｘｎの正方形と辺を共有し、その
　　　　　　辺は取り除かれている。残りの（ｎ＊＊２−１）個の１ｘ１の正方形は、２つが合わさって１ｘ２ or
　　　　　　２ｘ１の長方形となっていなければならない。（ｌ（ｎ）の項で述べたこと）

                     +---+   +---+---+---+
                     |   | A |           |　←-ｎ段
                     +   +---+           + 
                     |                   |
                     +                   + 
                     |  １ｘ２ or ２ｘ１  |　←-３段
                     +  の長方形で埋める  + 
                     |                   |　←-２段
                     +                   + 
                     |                   |　←-１段
                     +---+---+---+---+---+

           上図のように、１段、２段、．．．、ｎ段と順に１ｘ２ｏｒ２ｘ１の長方形を埋めていくことにする。
　　　　　　なお、１ｘ１の正方形Ａは最上段に配置することにする。(こうしても一般性は失われない）

　　　　　　ｎは奇数なので、ｎ＝（２＊ｋ＋１）とすると、１段目には最大でｋ個の１ｘ２の長方形を配置する
　　　　　　ことができる。１段目にｋ個を配置した場合、補題２により、２段目は、高々（ｋ−１）個の１ｘ２
　　　　　　の長方形しか配置できない。これを繰り返していくと、ｋ段目で補題１の状態となり、これ以上は配
　　　　　　置できなくなる。（即ち、解が存在しない）もし、途中で、１ｘ２の長方形の数を少なく配置した場
　　　　　　合は、もっと少ない段数で補題１の状態となる。

　　　　　　例　５ｘ５の場合
            +---+   +---+---+---+     +---+   +---+---+---+     +---+   +---+---+---+
            |   | A |           |     |   | A |           |     |   | A |           |
            +   +---+           +     +   +---+           +     +   +---+           +
            |                   |     |                   |     |                   |
            +                   + --> +                   + --> +   +---+       +---+ -->解なし 
            |                   |     |                   |     |   |   | x   y |   |　 (補題１）
            +                   +     +---+               +     +---+   +---+---+   +　 
            |                   |     |   |               |     |   |   |       |   |
            +                   +     +   +---+---+---+---+     +   +---+---+---+---+
            |                   |     |   |       |       |     |   |       |       |
            +---+---+---+---+---+     +---+---+---+---+---+     +---+---+---+---+---+
　　　　　　（１）初期状態　　　　　　　（２）１段目を埋めた状態　　（３）２段目を埋めた状態　

　　　　　　以上より、１ｘ２の長方形は、高々ｋ段までした積み上げることができないので、解は存在しない。
　　　　　　従って、ｎが奇数の場合、ｌ（ｎ）となる解は存在しないので、ｍ（ｎ）が最小解である。

　　　<<おまけ２のサマリ>>
　　　　少し長くなったので、以上の論旨をまとめると
　　　　　１）取り除くマッチ棒の数がｍ（ｎ）となるような解が存在する。
　　　　　２）解が存在するためには、取り除くマッチ棒の数＞＝ｌ（ｎ）を満たすことが必要である。
　　　　　３）ｎが偶数の場合、ｍ（ｎ）＝ｌ（ｎ）が成立するので、ｍ（ｎ）は最小解である。
  　　　　　　ｎが奇数の場合、ｍ（ｎ）＝ｌ（ｎ）＋１が成り立つ。しかし、ｌ（ｎ）となる解が存在しない
             ことが示されたので、ｍ（ｎ）が最小解となる。

---------　【おまけ１】の探索プログラム　-----------------------------------------------------------
##### 20004.06.06
#
#    
import time

def  exe(N) :
     global AnsCount,DupCount,out

     out = open("s%d-log.txt" % N,"w")

     Init(N)

     L = 2 * N * (N+1)
     S = [0]
     for m in range(1,N+1) :
         mask = 0L
         for k in range(0,L) : mask |= M[m][k]
         S += [mask]

     AnsCount = 0
     DupCount = 0
     maxdepth = (N*N + 1) / 2 + 1

     OuterSearch(maxdepth,0,-1,[],S,N)

     out.close()

##
def  OuterSearch(MaxDepth,nest,Pos,PosList,S,N) :

     if  nest == 0 :
         for p in range(0,(N+1)/2) :
             Line = ("\n=== Search  pos:%d  Started ===  : " % (p)) + time.ctime()
             WriteLog(out,Line)

             SS = [0] 
             for m in range(1,N+1) : SS += [ (S[m] | M[m][p]) ^ M[m][p] ]

             InnerSearch(MaxDepth,nest+1,-1,[p],SS,N)
 
             OuterSearch(MaxDepth,nest+1,p,[p],SS,N)

         Line = "\n=== Search  Ended ===  : " + time.ctime()
         WriteLog(out,Line)
         return

     if  MaxDepth < ((N*N - nest) / 2 + nest + 1) : return

     for pi in range(Pos+1,len(OutPos)) :
         p = OutPos[pi]
         poslist = PosList + [p]
         if DupCheck(poslist,N) < 0  : continue

         SS = [0] 
         for m in range(1,N+1) : SS += [ (S[m] | M[m][p]) ^ M[m][p] ]

         InnerSearch(MaxDepth,nest+1,-1,poslist,SS,N)

         OuterSearch(MaxDepth,nest+1,pi,poslist,SS,N)

##
def  InnerSearch(MaxDepth,nest,Pos,PosList,S,N) :
     global  AnsCount,DupCount

     if  nest == MaxDepth :
         for m in range(1,N+1) :
             if S[m] != 0  :  return
         cnt = DupCheck(PosList,N)
         if  cnt < 0                 :  return

         AnsCount += 1
         DupCount += cnt
         ID = "\n      ==== %d / %d ====" % (AnsCount,DupCount)
         printFig(ID,PosList,N)
         return

     for pi in range(Pos+1,len(InPos)) :
         p = InPos[pi]
         poslist = PosList + [p]

         SS = [0] 
         for m in range(1,N+1) : SS += [ (S[m] | M[m][p]) ^ M[m][p] ]

         if (bitcount(SS[1])+1)/2 + nest >= MaxDepth : continue

         InnerSearch(MaxDepth,nest+1,pi,poslist,SS,N)

##
def  bitcount(Mask) :
     w = Mask
     c = 0
     while w != 0 :
        c += 1
        w  = w & (w-1)
     return c

##
def  DupCheck(PosList,N) :

     NN = N * (N+1)
     C  = []
     for t in range(0,8) :
         Pmask = 0L
         for p in PosList :
             if p < NN  : 
                i = p % N ; j = p / N
                if t & 0x01 :  i = N-1 - i
                if t & 0x02 :  j = N   - j
                q = i + j*N
                if t & 0x04 : q += NN
             else :
                i = (p-NN) % N ; j = (p-NN) / N
                if t & 0x02 :  i = N-1 - i
                if t & 0x01 :  j = N   - j
                q = i + j*N + NN
                if t & 0x04 : q -= NN
             Pmask |= 1L << (NN+NN-q)

         if  t == 0 :  
             P = Pmask
             C =[P]
         else :
             if  (P & OutMask) <  (Pmask & OutMask) :  return -1
             if  (P & OutMask) == (Pmask & OutMask) :  
                 if (P & InMask) < (Pmask & InMask) : return -1

             if Pmask not in C : C += [Pmask]

     return  len(C)

##
def  Init(N) :
     global  M,InPos,OutPos,InMask,OutMask

     NN = N * (N+1)

     M = [[]]
     for m in range(1,N+1) :
         mask = []
         for k in range(0,2*NN) : mask += [0]
         M += [mask]

         for i in range(0,N) :
             if i+m > N : break
             for j in range(0,N) :
                 if j+m > N  : break
                 p = i*N + j
                 q = p + m*N
                 r = i + NN + j*N
                 s = r + m*N 
                 for k in range(0,m) :
                     a = p + k
                     b = q + k
                     c = r + k 
                     d = s + k

                     M[m][a] |= 1L << p
                     M[m][b] |= 1L << p
                     M[m][c] |= 1L << p
                     M[m][d] |= 1L << p

                     Line= " m=%d p=%d  (%d,%d,%d,%d)" % (m,p,a,b,c,d)
                     WriteLog(out,Line)

     InPos  = [] ; InMask  = 0L
     OutPos = [] ; OutMask = 0L
     NN2 = 2 * NN  
     for p in range(0,NN2) :
         if p < NN  : i = p / N
         else       : i = (p-NN) / N
         if (i == 0) | (i == N) :  OutPos += [p] ; OutMask |= 1L << (NN2-p)
         else :  InPos += [p] ; InMask |= 1L << (NN2-p)

##
def  printFig(ID,PosList,N) :

     H = [] ; V = []
     h = '+'; v = '|'
     for k in range(0,N) :
         h += '---+'
         v += '   |'
     for n in range(0,N+1) :
         H += [h]
         V += [v]

     for p in PosList :
         if p < N*(N+1) :
            i = p % N
            j = p / N
            h = H[j]
            h = h[:i*4+1] + '   ' + h[i*4+4:]
            H[j] = h
         else :
            p = p - N*(N+1)
            i = p % N
            j = p / N
            v = V[i]
            v = v[:j*4] + '   ' + v[j*4+3:]
            V[i] = v
 
     WriteLog(out,ID)     
     for k in range(0,2*N+1):
         if (k & 0x01) :  WriteLog(out,'     ' + V[k/2])
         else          :  WriteLog(out,'     ' + H[k/2])

###
def  WriteLog(out,Line) :
     print Line
     out.write(Line+"\n")
     out.flush()

----------------------------------------------------------------------------------------