プラスサイズのアメーバエスケープ

Dec 01 2020

ここでの@WhatsUpの質問の拡張として、そのルールが以下に含まれていますが、次の違いがあります。

広場の1つに、アメーバが住んでいます(次の写真で円でマークされています)。

いくつかの広場には、アメーバがあります(次の写真で緑/黄色でマークされています)。

グリッド上には、「刑務所」と呼ばれる領域があります(次の写真では灰色で描かれています)。

ここで「刑務所」はすべて黄色と緑色の正方形で構成されています。

  1. 黄色がかった一番下の正方形が空いている場合、アメーバは逃げることができますか?どれくらい難しいですか?

  2. 彼らの脱出が始まる前夜、黄色いセルは新しいアメーバの囚人で満たされています(すべての黄色と緑は満たされていると見なされます)、彼らは今何ができますか?

参照

正方形の無限のグリッドがあります。

広場の1つに、アメーバが住んでいます(次の写真で円でマークされています)。

アメーバは動くことはできませんが、独自のアクションを実行できます。アメーバは、元のアメーバと同じ2つのアメーバに分割でき、それぞれが元の正方形に(直交して)隣接する正方形を占有します。

すべての正方形は1つのアメーバしか収容できないため、分割は、アメーバに少なくとも2つの空の隣接する正方形がある場合にのみ発生します(2つ以上ある場合は、分割する正方形を自由に選択できます)。また、2つのアメーバが同時に分裂しないようにして、競合が発生しないようにします。

グリッド上には、「刑務所」と呼ばれる領域があります(次の写真では灰色で描かれています)。目的は、アメーバを刑務所から脱出させること、つまり、アメーバが刑務所にいない状態に到達することです。

回答

8 PaulPanzer Dec 01 2020 at 09:59

Q2への回答。@Milo Brandtが参照されたQへのコメントで指摘しているように、次の半不変量があります。

(0,0)を十字の中心として、整数座標をグリッドに配置します。重量二乗(n、m)$2^{-\lvert n \rvert - \lvert m \rvert}$。そうすれば、次のことを簡単に確認できます。

1.全体の重量(無限)ボードは、9(CF画像)である

ダウンしたことがないの正方形の重量はアメーバによって占められる2。

十字架全体の重さは $4\frac 1 2$ これは、その(無限の)補集合の重みに等しく、アメーバは有限の数の動きで逃げることができません。