◆広島県 清川 育男 さんからの解答
【問題１】
12+22+32+42=30(個)
【問題２】
9本
ー ー ー ｜ ｜ ｜ ｜ ー ー ー ｜ ｜ ｜ ｜ ー ー ー ｜ ｜ ｜ ー ー ー ー ｜ ｜ ｜ ー ー ー ー【問題３】
【問題３−１】
2*n*(n+1) 本
【問題３−２】
12+22+・・・・+n2=n*(n+1)*(2*n+1)/6(個)
【おまけ１】
4*4 1) ー ー ー ｜ ｜ ｜ ｜ ー ー ー ｜ ｜ ｜ ｜ ー ー ー ｜ ｜ ｜ ー ー ー ー ｜ ｜ ｜ ー ー ー ー 2) ー ー ー ｜ ｜ ｜ ｜ ｜ ー ｜ ｜ ｜ ｜ ｜ ー ー ｜ ｜ ｜ ｜ ｜ ー ー ｜ ｜ ｜ ｜ ー ー ー ー回転、裏返しで同じになるもを１通りとすると、２通り。
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
1) 2 8 10 16 22 24 25 33 35
2) 2 10 12 13 20 21 28 31 34
3) 3 6 13 16 19 25 26 33 35
4) 3 10 11 13 20 21 28 31 34
5) 6 8 14 16 22 24 25 33 35
6) 6 8 15 16 22 23 25 33 35
7) 6 8 15 16 22 25 28 35 38
8) 6 8 16 17 19 25 27 33 35
9) 6 8 16 17 19 25 31 33 39
10) 6 8 16 18 19 25 26 33 35
11) 6 12 13 14 20 21 28 31 34
12) 7 10 13 20 21 23 30 31 33
13) 7 10 13 20 21 27 28 29 35
14) 7 10 13 20 21 28 29 31 39
15) 7 10 13 20 21 28 30 31 38
16) 8 10 11 18 20 21 28 31 34
16通り。（固定して）
【おまけ２】
●5×5に並べた場合
ー ー ー ー ｜ ｜ ｜ ｜ ー ー ー ー ｜ ｜ ｜ ｜ ｜ ー ー ー ｜ ｜ ｜ ｜ ｜ ー ー ー ー ｜ ｜ ｜ ｜ ー ー ー ー ｜ ｜ ｜ ｜ ー ー ー ー ー14本
●6*6
ー ー ー ー ー
｜ ｜ ｜ ｜ ｜ ｜
ー ー ー
｜ ｜ ｜ ｜ ｜ ｜ ｜
ー ー ー
｜ ｜ ｜ ｜ ｜ ｜ ｜
ー ー
｜ ｜ ｜ ｜ ｜ ｜ ｜
ー ー ー ー
｜ ｜ ｜ ｜ ｜ ｜
ー ー ー ー
｜ ｜ ｜ ｜ ｜
ー ー ー ー ー ー19本●7*7(3*3,5*5)
ー ー ー ー ー ー ー
｜ ｜ ｜ ｜ ｜
ー ー ー ー ー ー
｜ ｜ ｜ ｜ ｜
ー ー ー ー ー ー
｜ ｜ ｜ ｜ ｜ ｜
ー ー ー ー ー
｜ ｜ ｜ ｜ ｜ ｜
ー ー ー ー ー
｜ ｜ ｜ ｜ ｜ ｜
ー ー ー ー ー
｜ ｜ ｜ ｜ ｜ ｜
ー ー ー ー ー ー
｜ ｜ ｜ ｜ ｜
ー ー ー ー ー ー ー●8*8(2*2,4*4,6*6)
ー ー ー ー ー ー ー ー
｜ ｜ ｜ ｜ ｜
ー ー ー ー ー ー ー ー
｜ ｜ ｜ ｜ ｜
ー ー ー ー ー ー ー
｜ ｜ ｜ ｜ ｜ ｜
ー ー ー ー ー ー ー
｜ ｜ ｜ ｜ ｜ ｜ ｜
ー ー ー ー ー
｜ ｜ ｜ ｜ ｜ ｜ ｜
ー ー ー ー ー ー
｜ ｜ ｜ ｜ ｜ ｜ ｜
ー ー ー ー ー ー
｜ ｜ ｜ ｜ ｜ ｜
ー ー ー ー ー ー ー ー
｜ ｜ ｜ ｜ ｜
ー ー ー ー ー ー ー ー中央から見ると包含されているのが判ります。
●n*n
F(n)=Ceiing(n2/2)+1
n≧2、F(1)=1
◆広島県の中学校２年生 CHEMI さんからの解答
【問題１】
マッチ棒一本の長さを１とします。
このとき、問題図の中には、一辺が１の正方形から最大４の正方形まであります。
ここで、それぞれの大きさの正方形の数は、
「上下にずらせる数」×「左右にずらせる数」
なので、
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ 一辺の長さ｜ 計算 ｜答え ―――――――――――――――― １ ｜４×４＝１６｜１６ ２ ｜３×３＝ ９｜ ９ ３ ｜２×２＝ ４｜ ４ ４ ｜１×１＝ １｜ １ ―――――――――――――――― 合計｜３０ ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊よって３０個。
【問題２】
一辺１の正方形は１６個あります。
他は、それらを消すときに一緒に消せばいいでしょう。
よって、それらを消すのには８本消せばいいことになります。
しかし、
― ― ｜ ｜ ― ―で埋めると、一辺が２の正方形をすべて消すことができません。
また、８本で消そうとすると、一辺が４の正方形を消すことができません。
だから、８本で、一辺が１の正方形一個と一辺が４の正方形を除くすべての正方形を消して、もう一本消して残りの二つの正方形を同時に消します。
細かい証明はしませんが（っていうかできません）感覚的にこれならうまくいくとわかります。
よって、９本消す必要があります。
-例-
ー ー ー ｜ ｜ ｜ ｜ ｜ ー ｜ ｜ ｜ ｜ ｜ ー ー ｜ ｜ ｜ ｜ ｜ ー ー ｜ ｜ ｜ ｜ ー ー ー ー【問題３−１】
n×nから(n+1)×(n+1)にするときに、まず辺を１ずつ伸ばさなければいけません。
そのためには{2×(n+1)}本必要です。
そして、右端の辺と下の辺を作るには、{2×(n+1)}本必要です。
以上のことから、僕は次のような反復式を作りました。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ Ｘ1 ＝ ４ (一辺が１の正方形を作るのに必要なマッチ棒の本数) Ｘm+1 ＝ Ｘm ＋ ４ × (ｍ ＋ １) ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊Ｘnが（ｎ×ｎ）の正方形を作るときに必要なマッチ棒の本数です。
【問題３−２】
これは、【問題１】の考え方を使うと、
| n k=1 |
k2だとわかります。 |
【おまけ２】
これは、【問題２】の考え方を使うと、
n2/2+1
となりますが、ｎが奇数のときに小数点がでます。
このとき、切り捨てるとすべて消すことができないので（少なくなるから）、小数点以下は切り上げたものが答えとなります。
◆千葉県 菜花子 さんからの解答
◆静岡県 medaka さんからの解答
【問題１】 ３０個
【問題２】
(考え方）
３ｘ３の答え(*の部分）をもとに上側と右側の部分を拡張した
【問題３−１】
(答え）
マッチ棒の数をＬ（ｎ）とすると
Ｌ（ｎ）＝２＊ｎ＊（ｎ＋１）
(求め方）
Ｌ（１）＝ ４
δＬ（ｎ）＝ Ｌ（ｎ）−Ｌ（ｎ−１）とすると、δＬ（ｎ）＝４＊ｎとなる。
これより、Ｌ（ｎ）＝ΣδＬ（ｋ）として、上記の答えを得る。
ｅｘ．Ｌ（４）＝２＊４＊（４＋１）＝４０
【問題３−２】
(答え） 正方形の個数をＳ（ｎ）とすると
| Ｓ（ｎ）＝ | ｎ＊（ｎ＋１）＊（２＊ｎ＋１） ６ |
（求め方）
ｍｘｍの正方形は、横方向に（ｎ−ｍ＋１）個、縦方向にも（ｎ−ｍ＋１）個を配置できるので
全体では、（ｎ−ｍ＋１）2個が存在する。従って、
Ｓ（ｎ）
＝ｎ2＋（ｎー１）2＋（ｎー２）2＋．．．＋１2
＝ Σｋ2
＝ Σ｛ｋ＊（ｋ−１）＋ｋ｝
| ＝ | ｎ＊（ｎ＋１）（ｎ−１） ３ | ＋ | ｎ＊（ｎ＋１） ２ |
| ＝ | ｎ＊（ｎ＋１）＊（２＊ｎ＋１） ６ |
【おまけ１】
（答え）
以下の２個。
ただし、対称解を別物として数える場合は、１６個。
【問題２】の解は、最初の解を上下反転したものに一致している。
ｎ＝５の場合は、９１個。
ただし、対称解を別物として数える場合は、７２０個。
（求め方）
プログラム(最後に添付）による探索で求めた。
(プログラムの説明は割愛)
【おまけ２】
（答え） 取り除くマッチ棒の最小数をｍ（ｎ）とすると
| ｍ（ｎ）＝［ | ｎ2＋１ ２ | ］＋１ |
ただし、［ａ］はガウス記号で、ａの整数部分を表す。
（ｅｘ．［３］＝３，［３．５］＝３）
| ｎ | ｍ（ｎ） |
| ３ | ６ |
| ４ | ９ |
| ５ | １４ |
| ６ | １９ |
| ７ | ２６ |
（求め方）
ｎ＝３は、明らか（『正方形の消滅』参照）であるので、ｎ≧４について調べることにする。
１）取り除くマッチ棒の数がｍ（ｎ）となるような解が存在することを以下に示す。
ｎ＝４は、【問題２】で明らかである。
ｎ＞４については、４ｘ４の解をベースとして以下の手順で作ることができる。
ｎが偶数のとき、ｎｘｎから（ｎ＋１）ｘ（ｎ＋１）の解を作る手順
ａ）ｎｘｎの上側に左から右へと１ｘ２の長方形を並べる
ｂ）ｎｘｎの右側に上から下へと２ｘ１の長方形を並べる
ｃ）右下の１ｘ１の正方形の領域は、下の部分を開けたままにする
ｎが奇数のとき、ｎｘｎから（ｎ＋１）ｘ（ｎ＋１）の解を作る手順
ｄ）ｎｘｎの左側に上から下へと２ｘ１の長方形を並べる。
ｅ）ｎｘｎの下側にある１ｘ１の正方形（下が開いている）は、２ｘ１の長方形にする
ｆ）ｅ）で作られた長方形ではさまれた部分を１ｘ２の長方形でうめる
ｇ）ｄ），ｅ）にはさまれた１ｘ１の正方形の領域は、下の部分を開けたままにする
上記の手順ａ）〜ｇ）により、ｎ＝４から順にｎ＝５〜８を作成する例を示す。
は、手順ａ）の操作で作られたことを表す。
（ｂ〜ｇも同様）
ｎ＝４の場合（ベース解）
ｎ＝５の場合
ｎ＝６の場合
ｎ＝７の場合
ｎ＝８の場合
２）解が存在するための,必要条件
ｌ（ｎ）を以下のように定義すると、解が存在するためには、
取り除くマッチ棒の数≧ｌ（ｎ）を満たすことが必要である。
| ｌ（ｎ）＝［ | ｎ2 ２ | ］＋１ |
ただし、［ｋ］はガウス記号で、ｋの整数部分を表す。
１ｘ１の正方形はｎ2個存在する。
この正方形をもっとも少ない数のマッチ棒で消滅させるには、２つの１ｘ１の正方形の間の１本を取り除いて、１ｘ２ or ２ｘ１の長方形を作ることである。
ｎ2個の正方形をこの方法で行うとすると、
| ［ | ｎ2 ２ | ］本のマッチ棒が必要である。 |
一方、この方法では、ｎｘｎの正方形は消滅しないので、これを消滅させるために、もう1本のマッチ棒が必要となる。
| 従って、［ | ｎ2 ２ | ］＋１＝ｌ（ｎ）が必要である。 |
ｎが奇数の場合、１ｘ１の正方形が１つ残るが、この正方形は、ｎｘｎの正方形と辺を共有していれば、ｎｘｎの正方形を消滅させる時に、同時に消滅させることができる。
従って、ｎが奇数の場合も、
| ［ | ｎ2 ２ | ］＋１＝ｌ（ｎ）本のマッチ棒が必要条件となる。 |
３）次に、ｍ（ｎ）が最小解であることを示す。
| ｎが偶数の場合、［ | ｎ2＋１ ２ | ］＝［ | ｎ2 ２ | ］となり、 |
ｎが奇数の場合、ｍ（ｎ）＝ｌ（ｎ）＋１が成り立つ。
もし、ｌ（ｎ）となる解が存在しなければ、ｍ（ｎ）が最小解といえる。
●補題１
下図のように、１ｘ２の長方形Ａの両側をガードされた状態で、ｘ，ｙの位置を１ｘ２と２ｘ１の長方形だけで埋めることはできない。
Ｇ１，Ｇ２は、２ｘ１の長方形又は端
∵ ｘ、ｙを埋めようとすると、どうしても２ｘ２の正方形ができてしまう。
●補題２
下図のように、１ｘ２の長方形がｋ個並んだ両側をガードされた状態で、
ｘ１．．．ｘ２ｋの位置を１ｘ２と２ｘ１の長方形だけで埋める場合、
１ｘ２の長方形は、高々（ｋ−１）個しか並べることができない。
Ｇ１，Ｇ２は、２ｘ１の長方形又は端
ｘ１，ｘ２ｋの位置は、２ｘ１の長方形を配置しなければならないので、残りを１ｘ２の長方形で埋めたとしても高々（ｋ−１）個となる。
補題１，２を使って、ｌ（ｎ）となる解が存在しないことを示す。
もし、ｌ（ｎ）の解が存在すると仮定すると、１ｘ１の正方形がｎｘｎの正方形と辺を共有し、その辺は取り除かれている。
残りの（ｎ2−１）個の１ｘ１の正方形は、２つが合わさって１ｘ２ or２ｘ１の長方形となっていなければならない。
（ｌ（ｎ）の項で述べたこと）
上図のように、１段、２段、．．．、ｎ段と順に１ｘ２ｏｒ２ｘ１の長方形を埋めていくことにする。
なお、１ｘ１の正方形Ａは最上段に配置することにする。
(こうしても一般性は失われない）
ｎは奇数なので、ｎ＝（２＊ｋ＋１）とすると、１段目には最大でｋ個の１ｘ２の長方形を配置することができる。
１段目にｋ個を配置した場合、補題２により、２段目は、高々（ｋ−１）個の１ｘ２の長方形しか配置できない。
これを繰り返していくと、ｋ段目で補題１の状態となり、これ以上は配置できなくなる。
（即ち、解が存在しない）
もし、途中で、１ｘ２の長方形の数を少なく配置した場合は、もっと少ない段数で補題１の状態となる。
例 ５ｘ５の場合
以上より、１ｘ２の長方形は、高々ｋ段までした積み上げることができないので、解は存在しない。
従って、ｎが奇数の場合、ｌ（ｎ）となる解は存在しないので、ｍ（ｎ）が最小解である。
<<おまけ２のサマリ>>
少し長くなったので、以上の論旨をまとめると
１）取り除くマッチ棒の数がｍ（ｎ）となるような解が存在する。
２）解が存在するためには、取り除くマッチ棒の数≧ｌ（ｎ）を満たすことが必要である。
３）ｎが偶数の場合、ｍ（ｎ）＝ｌ（ｎ）が成立するので、ｍ（ｎ）は最小解である。
ｎが奇数の場合、ｍ（ｎ）＝ｌ（ｎ）＋１が成り立つ。
しかし、ｌ（ｎ）となる解が存在しないことが示されたので、ｍ（ｎ）が最小解となる。
【おまけ１】の探索プログラム
##### 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()
◆東京都 ぽこぺん さんからの解答
1×1 の正方形を「単位正方形」，n×n の正方形を「全体正方形」と呼ぶことにする。
また，長さ 1 の辺（マッチ棒 1 本に対応）を単位辺と呼ぶ。
【問題１】
下記【問題３−２】の解で，n = 4 とすれば，
4×5×9/6 ＝30 個
【問題２】
下記【おまけ１】の図において，赤点線の位置にある 9 本の単位辺を取り除くと正方形を含まないようにできる。
【問題３−１】
一つの単位正方形にその上辺と左辺を対応させると，それは単位正方形同士の間で重複しない。
また，全体正方形の右辺と下辺に属する 2n 本の単位辺には対応する正方形がない。
以上から，求める辺の本数は
2n2 + 2n = 2n(n+1) 本 である。
【問題３−２】
1 辺が k (1≦k≦n) の正方形が，
全体正方形の内部で
左右に動ける自由度は n+1-k であり，
上下に動ける自由度も同じく n+1-k であるから，
この大きさの正方形は (n+1-k)2 個ある。
したがって，全部で
| n k=1 | (n+1-k)2 = | n k=1 | k2 = | n(n+1)(2n+1) 6 |
個 |
ある。
【おまけ１】
回転と裏返しによって重ならない解は下図の 2 通り。
これ以外にないことはシラミ潰しにより確かめた。
考え方は【おまけ２】に記す。
【おまけ２】
n≧3 とする。
単位正方形をすべて消すためには，各単位正方形から少なくとも 1 辺ずつを削除する必要があるが，
2 個ずつ隣り合う単位正方形の間の辺を削除すれば，1 辺あたり 2 個ずつの単位正方形が消えることになり，
削除本数は最小で済む。
[1] n が偶数の場合は，これによって n2/2 枚のドミノ片（2×1 の長方形）ができる。
しかし，このドミノ片を適当に配置して全体正方形を埋めただけでは，全体正方形の辺が削除されないまま残っているから，
n2/2 本を削除しただけでは題意を満たすことはできない。
次に，単位辺を n2/2 + 1 本削除することを考えると，この場合は実際に題意を満たす配置がある (下図)。
確かにこの場合，ドミノ片が n2/2 - 2 個，単位正方形が 1 個，1×3 の長方形が 1 個だから，削除した辺数は
| ( | n2 2 | - 2) + 1 + 2 = | n2 2 |
+ 1 本 |
となっている。これが最小本数である。
n×n の場合，この図に掲げた 2 つのタイプのすべての解は，適当に回転や裏返しを行うことにより，外周に接する単位正方形（黄）を (1, 2) に置くことができる (上から i 番目，左から j 番目の単位正方形の位置を (i, j) で表すことにする)。
そのとき，1×3 の長方形（青）の位置は，解の 2 種類のタイプに応じて
(n'-1, n'+1)〜(n'+1, n'+1) または (n'+1, n'-1)〜(n'+1, n'+1) になる。
ただし，n' = n/2 とおいた。
n≧6 の偶数の場合，これ以外のタイプの解が存在するかどうかは確かめていない。
なお，両タイプの配置は，n×n の配置の外周（6×6の図にある赤枠部）にそれぞれ規則的なパターンを付加して， さらに規則的な修正を施すことにより，(n+2)×(n+2) の配置に拡張することができる。
[2] n が奇数の場合は，(n2 - 1)/2 本の単位辺を削除することにより，同数のドミノ片と 1 個の単位正方形ができる。
この単位正方形が全体正方形の外周に接する位置にあり，その共有片を 1 本だけ削除することにより題意を満たすことが
できれば，
(n2 - 1)/2 + 1 本の削除で実現できることになるが，それは不可能である。
なぜなら，下図のように単位正方形 S (黄) の載る辺上で，S から遠い方の頂点にドミノ片を置くには左右 2 通りの 置き方があり (注)，そこから図に示すようなドミノ片の連鎖の配置がそれぞれ必然的に決まるため，右下に 2×2 の正方形ができることになるが，この正方形領域を題意を満たしてドミノ片で埋めることはできないからである。
注： n = 3 の場合，S が辺の中央にある場合は明らかに不可能，頂点にある場合は左側の 1 通りのみ。
n = 5 で S が辺の中央にある場合は左側の 1 通りのみとなる。
次に，(n2 - 1)/2 + 2 = (n2 + 3)/2 本の削除で済む解としては，下図の例に示すような渦巻き型の配置を元にして， 中央の単位正方形の任意の 1 辺を削除してＬ字型のピースを作り，さらに外周の任意の単位辺を削除して全体正方形を 消すことにより得られるものがある。
| この場合が | n2+ 3 2 | 本で最小本数となる。 |
| 以上 [1] と [2] をまとめて，最小本数は [ | n2+ 3 2 | ] 本となる。 |
【感想】
これまで，マッチ棒関係のパズルに真面目に取り組んだことはなかったのですが，この問題は一見平凡に見えて，実際に解いてみると意外に奥深いことに驚きました。
軽い気持ちで取りかかったのですが，難渋してしまいました。
◆愛知県 Y.M.Ojisan さんからの解答。
【問題１】 ３０ 個
【問題２】 ９本
取り方は下図赤破線
【問題３−１】
横方向に Ｎ本のマッチがＮ＋１段ある。従って
２Ｎ（Ｎ+１）本
【問題３−２】
１＋２２＋３２＋・・・・＋N２ で計算すればよい。
従って、| Ｎ（Ｎ＋１）（２Ｎ＋１） ６ |
【おまけ１】
実質 問題２の解答に示す２個である。
４×４の正方形を消去するために、少なくとも１本外周のマッチを採らなければならないが、対称性を考えると頂点隣（系列１）と辺中央寄り（系列２）の２種のみ考えればよい。
この一本により１×１の正方形１個が削除され、１５個が残る。１本のマッチでは、最大２個の１×１の正方形が消去可能であるから、最低あと８本必要であり、合計９本が最小である。この場合、マッチを取り去ったあとに残るタイル図形は、（１）６個のドミノと１個のトリミノか（２）７個のドミノと１個の外周のモノミノで構成されている。
さらに、２×２の正方形が消去されているためには、２個のドミノが平行に並んでいてはいけない。
以上の条件を満足するタイルの並べ方をＰＣで探索すると、下図に示すものだけであった。
なお、系列１の（２）は無かった。系列２の（２）も本当は無かったのであるが、下図にはモノミノが外周上の条件をはずしたものを示した。
さらに３×３の正方形がないものを探すと、系列２の（１）タイプの２個のみであった。
【おまけ２】 ガウス記号 ［ ］を用いて下記である。
ただし Ｎ＞１
| [ | Ｎ２＋３ ２ |
] |
【必要条件】
Ｎが偶数である場合、Ｎ×Ｎの正方形を消去するために外周の１本を取ると、１×１の正方形は１個消去されるだけであり、残り（Ｎ２−１）個を消去するには、（Ｎ２−１）が奇数であるので、Ｎ２の半分のマッチを取り除かなければならない。
よって、最初の外周の１本を加え計算すると 答えと等価である。
Ｎが奇数である場合、偶数の場合と同じ考え方を適用すると、（Ｎ２−１）が偶数であるので、答えより１少ない必要条件としての値が得られる。
しかし実際は下図に示すように、残された（Ｎ２−１）個のセルをその半分個のドミノで２×２の正方形ができないように埋めることは不可能であり、答えと等価となる。
＜下図解説＞
Ｎ≧５の場合、外周から取った１本により消去される１×１の正方形：Ｇと干渉しない対角線およびその両側を見つけることができる。
角にドミノをおいて以降２×２の正方形ができないように対角線上にドミノを置いて行くと「碁の四丁」のように最終的に２×２の正方形を回避できなくなる。
従って、少なくとももう一つ余分にマッチの除去が必要である。
Ｎ＝３の場合も下図に示すように４個のドミノで埋め尽くすことができない。
| Ｎ≧５ | Ｎ＝３ 系列２ | Ｎ＝３ 系列１ |
 |
 |
 |
【十分条件】
Ｎが偶数か奇数かにより、下図のように 棒状トリミノないし凸状テトロミノを中心にドミノが２重渦巻き線を描くようにかつレンガ積みののうに互い違いになるように配置し、Ｎ×Ｎの盤面（点線）を考えれば、十分条件となっている事がわかる。
| 奇数の場合 | 偶数の場合 |
 |
 |
∵ 全体がドミノからテトロミノで埋められているので少なくとも１×１の正方形は消去されている。
２×２以上の正方形で消去されていないものがあるとすると、長さ２以上の直線で構成された８以上の長さの閉じた折れ線が必要である。
渦巻き線に沿う方向には、長い連続折れ線が存在している。
しかし始点に戻るには、２以上の長さに渡って横断しなければならないが、横断方向に２以上の直線は存在しない。
よって、２×２以上の正方形も消去されている。
【ＰＳ】
おまけ１の探索をＰＣで行いましｔが、条件が厳しいので探索数は少なく、実は人間技でも十分可能でした。
◆ 問題へもどる
◆ 今週の問題へ
数学の部屋へもどる