14

市松模様テクニック

1603
0

0.市松模様とは

市松模様 市松模様
こんな感じの模様です。

1.有名なテクニック

問題1
10×10のマス目をT型テトロミノで敷き詰められない事を示せ。

Tmino Tmino
 
背理法で示します。
マス目を白と青の市松模様に塗ると、T型テトロミノ(以下T)を置いた時、
①白1マス、青3マスにかかる
②青3マス、白1マスにかかる
のどちらかになります。
Tichimatu Tichimatu
盤面の白と青の個数は同じなので、
①を満たすTと②を満たすTの個数は等しくなければいけません。
しかし、Tの個数は25個なのでそんなことはありえません。
よって背理法により示されました。

2.さらなるテクニック

問題2
10×10のマス目をI型テトロミノで敷き詰められない事を示せ。

Imino Imino
これも背理法で示します。
マス目を市松模様を2倍に引きのばしたように塗ります。
bigichimatu bigichimatu
I型テトロミノを置くと、必ず白2マス、青2マスにかかります。
Ioki Ioki
白いマスは48マスしかないのでI型テトロミノは24個より多く置けません。
しかし、I型テトロミノは25個置かなければならないので矛盾します。
よって背理法により示されました。

3.おわりに

何かこれだけじゃ物足りないので、最後にかなり難しめの自作問題を出します。(というか、今までのが前座です)

問題3
3×6のマス目を白と黒で塗ります。その塗り方のスコアを、
2p (p=()+())とします。
この時、塗り方2^18通り全てのスコアの和を求めてください。

(例)下の図の場合、白の連結成分は3つで、黒の連結成分も3つなのでスコアは64です。
36 36
解答は載せません。

投稿日:20201110
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

simasima
simasima
195
31852
OMC橙(2499/5位)OMC030,034,036,038優勝/OMC015,OMC032単独writer/AtCoder橙

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 0.市松模様とは
  2. 1.有名なテクニック
  3. 2.さらなるテクニック
  4. 3.おわりに