◆新潟県 ぽぽぽさんからの解答。
タイルを貼ることはできないでしょう。
といって説明が論理的にできる訳ではないのでとりあえずこんなもんかなぁということで回答してみます。
「準備」
１．タイルに○、×の記号をつけます。
２．下地にもちょうど市松模様になるように○、×をつけます。
「作業」
下地にタイルを貼る際に、タイルと下地の記号が一致するように貼っていきます。
→タイルの向きを変えることにより、必ず市松模様になるようにできると思います
（ここの説明が非常に弱い。直感的なものなので）
「結果」
しかし、下地の○と×の数を数えると、１９と２１になっています。
もし、タイルできっちりと貼れるとしたら、下地の○と×の数は同じになっていなければなりません。
ということは、きっちりとは貼れないということになります。
「感想」
この手のパズルっぽい問題は何とか考えることが出来ますが、（もちろん考えるだけで、自分なりの回答もなかなか出てきませんが）、ちょっと専門数学っぽく
なると全然わかりません。
数学は基本的には好きなのですが。
これからも楽しい問題をお願いします。
【コメント】
鮮やかな説明ですね。
市松模様にするのはなかなか気がつきにくいと思います。
それではさっそく次の問題です。
【問題】
下図の異なる記号のマス（○と×）ならばどこの２枚を取り除いても、残った部分を必ず２×１のタイルで埋めることができます。
その理由を考えてください。
◆愛知県 重永 大介 さんからの解答。
本来の問題では、○が１９個、×が２１個ある。
タイルを１枚張る毎に○×の数が１つずつ隠されていくので、最終的には×が２個残り、すべてを埋めることはできない。
次に一般の場合を証明します。
「縦、横が偶数、奇数の長方形を市松模様に分け、そこから色の違う任意のマスを１つずつ取り除いても、ドミノ牌で埋められる。」
この２マスを選んだとき、この２マスを向かい合う２つの頂点とする長方形は縦・横が偶数・奇数の長方形であることに注意する。
補題１．
「縦、横が偶数、奇数の長方形はタイルで埋められる。」
偶数の列に沿ってタイルを一列に並べ、それを奇数の列の分だけ並べる。
補題２．
「縦、横が偶数、奇数の長方形から向かい合う隅の２マスを除いても埋められる。」
図１で、縦が偶数、横が奇数とすると、補題１より３つの長方形は埋められる。
長方形の縦の長さを偶数、横の長さを奇数とする。
縦・横の偶奇が入れかわっても同じような証明である。
長方形から２つのマスを取り除いたとき、その２マスを２つの隅とする長方形とそれ以外の周の部分を考える。
（２マスが隣接、または１直線上、またはコの字の場合は後で考える。）
まず内側の長方形は補題２より埋められる。
内側の長方形の縦をｐ、横をｑとする。
外周を図２のように８つの部分に分け、各文字またはその和の偶奇により場合分けをする。
ｐが奇数、ｑが偶数とする。
（図３）
aが偶数、bが奇数のとき、図３−１、図３−２のように分け、各長方形を埋める。
図３−１
図３−２
aが奇数、bが偶数のとき、図３−３、図３−４のように分け、各長方形を埋める。
図３−３
図３−４
ｐが偶数、ｑが奇数とする。
aが偶数、bが偶数のとき、図４−１、図４−２のように分け、各長方形を埋める。
図４−１
図４−２
aが奇数、bが奇数のとき、図４−３、図４−４のように分け、各長方形を埋める。
図４−３
図４−４
（図４−４に注意。実線で分けられた５つの領域を埋める。）
２マスが隣接しているとき、
それが横になっているなら、図３− のどれかに属する。
それが縦になっているなら、図４− のどれかに属する。
２マスが１直線上にある場合、それを両端とする長方形を考えると、２マスの間にあるマスは偶数個なので埋められる。
この長方形が横長なら図３− のどれか、縦長なら図４− のどれかに属する。
長方形を取り除いたとき、残った領域が輪にならずコの字になっているとき、
図５またはその裏返しの場合、
図５−１，図５−２のどちらかで、埋められる。
図５−１
図５−２
図６またはその裏返しの場合、
図６−１，図６−２のどちらかで、埋められる。
図６−１
図６−２
最後に、長方形を取り除いたとき、残った領域が２つに分かれているときを考える。
問題にすべきは２マスが左右の列にくっついて、上下に隙間がある場合である。
（その他の場合は以前と同様に長方形を作ると、２つまたは１つの長方形は偶数・奇数の長方形になるので埋められる。）
上下の隙間の縦が偶数の場合は以前のように長方形に分ける。
上下の隙間の縦が奇数の場合は図７−１または図７−２のように分ければ、できた７つの長方形は偶数・奇数の長方形である。
図７−１
図７−２
＜コメント＞
証明後半ではかなり省略しましたが、ほぼ自明なことと思います。
また、逆にくどいところもあると思いますがご容赦ください。
もしくはこんな長い証明でなく、エレガントな証明があるかもしれません。
これから自然に
（問題１）
縦、横がともに偶数の長方形を市松模様に分け、そこから色の違う任意のマスを１つずつ取り除いても、ドミノ牌で埋められるか。
（問題２）
縦、横がともに奇数の長方形から任意の１マスを取り除いて、ドミノ牌で埋められるか。
という問題が考えられますが、どなたか暇なら証明してください。
問題１は同様に場合分けして証明できるかもしれません。
問題２は簡単です。
◆東京都 Asami さんからの解答。
いわゆる二重帰納法という手法によって、
| (命題)
少なくとも一辺が偶数ならば、 ………★が真であることを示します。 |
また、以下において(ｔ,ｕ)と書けば、ｔ行,ｕ列目のタイルを取り除いたことを表し、
＜ｔ,(ｕ,ｕ+１)＞で、ｔ行,ｕ列,ｔ行,ｕ+１列目を埋めるドミノ牌を、
＜(ｔ,ｔ+１),ｕ＞で、ｔ行,ｕ列,ｔ+１行,ｕ列目を埋めるドミノ牌を表すことにします。
(補題１)２×ｎ型の長方形について★は成立する
(証明)
(ａ)： (１,ｕ),(２,ｕ)のとき
残り部分は
＜(１,２),１＞,＜(１,２),２＞,……,＜(１,２),ｕ-１＞,＜(１,２),ｕ+１＞,………
と埋めることが可能
(ｂ)： (１,ｕ),(２,ｖ) ；ｕ＜ｖのとき
(注：ｕ＞ｖのときは長方形を180度回転させれば(ｂ)に帰着)
＜(１,２),１＞,＜(１,２),２＞,……,＜(１,２),ｕ-１＞,
＜１,(ｕ+１,ｕ+２)＞,＜１,(ｕ+３,ｕ+４)＞,……,＜１,(ｖ-１,ｖ)＞,
＜２,(ｕ,ｕ+１)＞,＜２,(ｕ+２,ｕ+３)＞,……,＜２,(ｖ-２,ｖ-１)＞,
＜(１,２),ｖ+１＞,……… と埋めることが可能
これはｖ-ｕ≡０(mod２)だから可能なのである。
(ｃ)： (１,ｕ),(１,ｖ) ；ｕ＜ｖのとき
(注：(２,ｕ),(２,ｖ)のときは長方形を180度回転させれば(ｃ)に帰着)
＜(１,２),１＞,＜(１,２),２＞,……,＜(１,２),ｕ-１＞,
＜１,(ｕ+１,ｕ+２)＞,＜１,(ｕ+３,ｕ+４)＞,……,＜１,(ｖ-２,ｖ-１)＞,
＜２,(ｕ,ｕ+１)＞,＜２,(ｕ+２,ｕ+３)＞,……,＜２,(ｖ-１,ｖ)＞,
＜(１,２),ｖ+１＞,……… と埋めることが可能
これはｖ-ｕ≡１(mod２)だから可能なのである。
(補題証明終了)
★が真であることを示すためには、
今、長方形がｐ×ｑであるときの命題をＲ(ｐ,ｑ)とおいたときに
(T)；Ｒ(２,２),Ｒ(２,３),Ｒ(２,４),Ｒ(２,５),………がすべて真
(U)；Ｒ(２,２),Ｒ(４,２),Ｒ(６,２),Ｒ(８,２),………がすべて真
(V)；Ｒ(２ｍ,ｎ+１),Ｒ(２ｍ+２,ｎ)が真 ⇒ Ｒ(２ｍ+２,ｎ+１)が真
を導けばよいが、(T),(U)は(補題１)によって示されている。
だから、今から(V)を示そう。
長方形ＡＢＣＤ (ＡＢ＝２ｍ+２,ＢＣ＝ｎ+１)において
ＡＥ：ＥＢ＝ＤＧ：ＧＣ＝２ｍ：２,
ＡＨ：ＨＤ＝ＢＦ：ＦＣ＝ｎ：１となるようにＥ,Ｆ,Ｇ,Ｈをとる。
ＥＧとＨＦの交点をTとおく。
すると今、取り除くタイルのうちの１つはＡＥTＨの中にあるとしてよい。
(∵回転または折り返しでこれに帰着できるから)
もう１つの取り除くタイルが、ＡＢＦＨまたはＡＥＧＤの中にあれば、
帰納法の仮定“Ｒ(２ｍ,ｎ+１),Ｒ(２ｍ+２,ｎ)が真”によって、
Ｒ(２ｍ+２,ｎ+１)が真であることを見るのは容易である。
したがってＡＥTＨ,TＦＣＧの中にそれぞれ１つずつ“取り除いたタイル”があるとしてよい。
実は、同様な考察によって、
ＡＪ：ＪＤ＝ＢＫ：ＫＣ＝１：ｎ,
ＡＭ：ＭＢ＝ＤＮ：ＮＣ＝２：２ｍとなるようにＪ,Ｋ,Ｍ,Ｎをとって
ＪＫとＭＮの交点をＯとすれば、
ＡＥTＨの中にあるとした“取り除いたタイル”はＡＭＯＪの中にあるとして良いのである。
従って以下の３つの場合について見ればよい。
(ア)：取り除くタイルが(１,１),(２ｍ+２,ｎ+１)のとき
(イ)：取り除くタイルが(２,１),(２ｍ+１,ｎ+１)のとき
(ウ)：取り除くタイルが(１,１),(２ｍ+１,ｎ+１)のとき
(ア)のときは
ｎ≡０(mod２)を意味しているので
＜(２ｍ+１,２ｍ),ｎ+１＞,……,＜(３,２),ｎ+１＞,＜１,(ｎ,ｎ+１)＞,
＜(２,３),ｎ＞,……,＜(２ｍ,２ｍ+１),ｎ＞,＜２ｍ+２,(ｎ,ｎ-１)＞,
………,
＜２ｍ+２,(２,１)＞,＜(２ｍ+１,２ｍ),１＞,……,＜(３,２),１＞
という風にして埋めることが可能である。
(イ)
やはりｎ≡０(mod２)を意味しているので
＜１,(１,２)＞,＜(２,３),２＞,＜(３,４),１＞,＜(４,５),２＞,……
……,＜(２ｍ+１,２ｍ+２),１＞,＜２ｍ+２,(２,３)＞,＜(２ｍ+１,２ｍ),３＞,
……………,＜(３,２),ｎ-１＞,＜１,(ｎ-１,ｎ)＞,＜(１,２),ｎ+１＞,
＜(２,３),ｎ＞,……,＜(２ｍ,２ｍ+１),ｎ＞,＜２ｍ+２,(ｎ,ｎ+１)＞
という風にして埋めることが可能である。
(ウ)
ｎ≡１(mod２)を意味しているので
＜２ｍ+２,(ｎ+１,ｎ)＞,＜(２ｍ+１,２ｍ),ｎ＞,＜(２ｍ,２ｍ-１),ｎ+１＞,
………,＜(３,２),ｎ＞,＜(２,１),ｎ+１＞,＜１,(ｎ,ｎ-１)＞,
＜(２,３),ｎ-１＞,……………＜２ｍ+２,(２,１)＞,＜(２ｍ+１,２ｍ),１＞,
………,＜(３,２),１＞
という風にして埋めることが可能である。
以上によって (V)が示され、
|
少なくとも一辺が偶数ならば、 ｐ×ｑなる長方形を市松模様に塗ったとき、 異色のタイルを１つずつ取り除いた残りのマスを １×２のドミノ牌で埋め尽くすことができる。 |
◆東京都 goya さんからの解答。
「一辺が偶数の長方形から異なる色のマスを１つずつ取り除いてドミノ牌で埋められるか？」
に関して、難しい解答が続いたので簡単（論理的な説明をしなければ、小学生でも多分納得できる）な解答をします。
愛知県 重永 大介さんからの（問題２）への解答
縦、横がともに奇数の長方形から任意の１マスを取り除いて、ドミノ牌で埋められるか。
[前提]
市松模様の塗り分けは隅のマスの色が白となる白と黒の市松模様とする。
◎取り除くマスが黒の時
全体では白のマスが黒のマスより１個多いので、黒マスを取り除くと、白マスが黒マスより２個多くなり、すべてを埋めることはできない。
◎取り除くマスが白の時
以下の証明により、すべてを埋めることができる。
準備−１
下記の要領ですべてのマスを１度ずつ通るように一筆書きする。
@左下から始め、最上段まで上がる。
A１列右に移動し、最下段まで下がる。
B１列右に移動し、最上段まで上がる。
以下A、Bを繰り返す。
※奇数列なので終端は右上になり、次のような線になる。
準備−２
一筆書きの線に沿って、マスに１から連番を振る。
この結果、白マスは奇数、黒マスは偶数になる。（＜補足＞参照）
証明
（取り除くマスの番号をＰとする）
Ｐを取り除くと一筆書きは １〜(Ｐ−１) と (Ｐ＋１)〜最大値(右上) の２本の線に分かれる。
Ｐは奇数なので、２本の線は共に偶数個のマスを通ることになるから線に沿ってドミノ牌を置いていけばすべてのマスが埋められる。
＜補足＞
証明を見れば分かるように下記の条件を満たす一筆書きであれば筆順に依存しない。
・線は斜めに結べない(縦または横に結ぶ)
・線は交差しない。
・線は長方形の外に出ない。(マスの上を通る)
例えば、こんなのもＯＫです。
「準備−２」に記した内容の説明
@市松模様に縦または横に線を引くので白／黒のマスを交互に通る。
A全体では白マスが１個多いので一筆書きするには始端／終端とも白マスになる。
「２本の線に分かれる」と書いているが取り除くマスが始端または終端の時は「線は１本」ですが、その線は偶数個のマスを通ります。
「一辺が偶数〜」も、上記の応用で証明できます。
◆東京都 Asami さんからの解答。
【タイルの３次元版】です。
比較的簡単な手順で示すことができましたので、ご報告致します。
| 直方体を市松模様(と呼ぶかは知りませんが)に塗ります。 これらのうち異なる２色の(1×1×1の)ブロックをどのように取り除いたとしても、３辺のうち少なくとも１辺が偶数辺ならば、２色の1×1×2のブロックで埋め尽くせる。 |
(証明)：
わかりやすいように、直方体の“ある”頂点を原点に、偶数辺がχ軸方向にくるように直方体を置く。
(その際、χ軸方向の辺の長さをｎとしておく)
そしてｚ軸方向へ向かって、１段目,２段目,……とスライスして行きます。
(T)：取り除く２つのブロックが同じ段にあるとき。
その段は２次元版での結果通りに埋めて、他の段に関しては、それぞれの段において、自然な形で埋めることができる。
(U)：取り除く２つのブロックが異なるｔ段,ｕ段(ｔ＜ｕ)にあるとき。
(ア)：ｔ段,ｕ段の間に偶数個の段があるとき
(即ちｕ-ｔ≡1(mod2))
例えばｔ段において白ブロック、ｕ段において黒ブロックを取り除くとしよう。
すると、ｔ段の４隅のうち、(1,1)または(1,n)成分のどちらかは黒色の隅になっている(これはどの段に関してもいえること)から、例えば、(1,n)が黒色の隅であるとしよう。
ｔ段目の(1,n)の黒色
t+1段目の(1,n)の白色
t+2段目の(1,n)の黒色
t+3段目の(1,n)の白色
………
………
u-1段目の(1,n)の黒色
ｕ段目の(1,n)の白色
これらをｚ軸方向に２段ずつに渡って埋める。
ｔ段,ｕ段の間にある偶数個の段に関しては、残り部分を自然な形で
(つまり、どの1×1×2ブロックも長い辺がｚ軸に平行になるようにして並列させる感じで並べる！)
埋めることができ、ｔ,ｕ両段に関しては２次元版での結果通りに埋める。
(イ)：ｔ段,ｕ段の間に奇数個の段があるとき
(即ちｕ-ｔ≡0(mod2))
例えばｔ段において白ブロック、ｕ段において黒ブロックを取り除くとしよう。
そして(ア)と同様に、例えばｔ段の(1,n)が黒色の隅であるとしよう。
{ｔ段目の(1,n)の黒 ,t+1段目の(1,n)の白}
{t+1段目の(1,1)の黒 ,t+2段目の(1,1)の白}
………
{u-2段目の(1,n)の黒 ,u-1段目の(1,n)の白}
{u-1段目の(1,1)の黒 ,ｕ段目の(1,1)の白}
このようにして埋め、ｔ段目からｕ段目までにかけて、各段においてそれぞれ２次元版での結果通りに埋める。