タイルを永遠に置き続けるゲーム

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

A問題の盤面サイズを一般化したとき、永久に出来るH,Wの条件は？

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

実はまだ解けてないんですが、min(H,W)=1がダメなのは自明でそれ以外は全部できるという仮説を持っている。 - Wが偶数 -- H=2：自明 -- H>=3：縦を上２行に、横を下１行に割り当てればいい Hが偶数の時も同様なので、本質は奇数*奇数。とりあえず3*3は出来た。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

H=2が自明は嘘で、W=2なら自明、W>=3なら"H>=3"の方法でできる。（まぁ簡単だけど）

かつっぱ@ 競プロYouTuber @catupper

@snuke_ W＝偶数、H=3のときうっかり縦に消えたりしませんか？(とはいえ反例が見つかったわけではない)

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

@catupper たしかに。これも本質だった。

きり @kiri8128

@snuke_ H,W>=4のとき、 左下から詰めて2×2の正方形にグリッドを分けておきます（奇数のときは右1列and/or上1行が余る）。 なるべく各正方形がきれいに埋まるように置いていく（縦だけおいたグリッドがあって縦がもうひとつ来たら埋める。右と上の隙間には消えるとき以外置かない）方針でうまくいきます。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

@kiri8128 どちらかが偶数の時はなにか変なことが起こりそうな気がちょっとするんですが、H,W>=3かつ奇数*奇数はかなり綺麗に出来てそうですね。これは美しい...

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

補足（奇数*奇数）：切羽詰まった状態というのは、2*2のグリッドのうち１つを除いて全て埋まっているという状況で、H,W>=5なら全てのグリッドが埋まっている列と行が少なくとも１つ以上ずつはあるのでそこを消せばいい。

きり @kiri8128

@snuke_ H=3かつW>=3のときは、 「各列では、ある箇所から下のみ（ゼロもありえる）が埋まっている」 「各列の埋まっているマスの個数は左から右にいくにつれて単調減少」 を守る置き方が必ず存在するので、これに従うとうまくいきそうです。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

@kiri8128 確かに出来てそうですね。sugoi...

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

@kiri8128 いや、ダメなケースが１つだけある気がしてきました。画像の状況で横が来ると条件を満たす置き方がありません。 pic.twitter.com/27xMDfE310

拡大

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

N=4の場合は図１の15状態から外れることなく遷移できる。N>4の場合は右にどんどん列が追加されていくだけで、縦棒を置くときに右から詰めて置く感じでやれば自然に拡張できると思う（図２）。Nが1増えるたびに6状態ずつ増える感じ。（🐘すぎる・・・） pic.twitter.com/FXRMHJWq8C

拡大

拡大