無限の迷路で進歩は可能ですか?

Inspired by Maze Solving
Robot
and the related one on code golf
SE

ルール

  1. セルを無限大の直交格子で開始します。 各セルには4つのエッジがあり、最大4つの方法で入力または終了できます。
  2. グリッド内のすべてのエッジは、壁でも壁でもありません。
  3. 「北」、「南」、「東」、「西」の指示で構成される一連の移動を実行することを選択します。
  4. 指示が指示する方向に壁がある場合、指示はスキップされます。
  5. 開始セルからアクセスできるセルの数が無限であると仮定できます。つまり壁では無限のセルの一部にはまっていません。

チャレンジ
  実行可能な命令の最短シーケンスを見つけます。迷路の詳細に関わらず、実行が完了すると、開始したのと同じセルに終わらないことを保証できます。

P.S.私はそのようなシーケンスが存在するかどうかはわかりません。それができなければ、それを証明してください。

P.P.S.この質問のタグ付けに私を助けてください….関連するものは見つかりません。

ベストアンサー

そのようなシーケンスが存在すると仮定し、作業シーケンスを修正しましょう。明らかに、このシーケンスには等しい数のNORTHおよびSOUTH方向が含まれていません。そうでない場合、ロボットは無限の1ワイド南北回廊の開始セルに戻ります。
WESTとEASTの場合も同じです。

一般性を失うことなく、西部よりも北部と西部より多くの北があると推測できます。さあ、シーケンスをテストするための迷路を作ってみましょう。空の平面から始めましょう。まず、東から西に伸びるまっすぐな無限の壁を建てようとしています。この壁の緯度は重要です。シーケンスに$
a $ NORTHと$ B $ SOUTHの方向がある場合は、この壁が正確に$(a-b)$
NORTH方向をブロックするようにします。これは、次のステートメントを参照することによって実行できます。

出発セルから$ y $セル北にある無限の南向きの壁がシーケンスから$ n $北を吸収すると、開始から無限の南向きの壁$
y + 1 $が北になる少なくとも$(n-1)$
NORTHsをブロックします。
これは、ロボットが初めて壁に衝突すると、壁の前にあり、残りのシーケンス壁が北に1セル以上押し込まれたのと同じように実行されます。

始動セルの北端にある無限の壁は、明らかに少なくとも$(a-b)$
NORTHsをブロックします。それ以上ブロックする場合は、壁1のセルを北に移動します。それでも解決しない場合は、もう一度1セル移動してください。ある時点では、正確に$(a-b)$
NORTHの方向をブロックします。それがこの壁の最後の場所になります。

同じ方法で私たちは無限の西向きの壁を作り、東西の動きを全滅させます。

シーケンスはこの「迷路」の開始点に戻ります。この矛盾は、あらゆる無限の迷路において進歩を起こすことができる配列がないことを示している。

編集:

@NeilWが指摘しているように、南向きの壁を配置すると、開始セルの左右の端に無限の垂直壁を構築することによって、水平移動を完全に無視することができます。もちろん、彼らは無限である必要はありません。それらはシーケンス自体よりも長くなければなりません。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です