基本的な数値ボグル
で、この記事は、我々は、A上の数値尻込みのゲームに導入されました$6 \times 6$ ボード、そのルールは次のとおりです
- 各セルには、からの1桁が含まれている必要があります $0$ に $9$。
- 1つのセルから始めて、隣接するセルに移動するときに数字を収集します（8方向すべて）。数字が収集されると、それらは左から右に連結されて1つの数字を形成します。開始桁も収集され、セルに再度アクセスできることに注意してください。
その場合のタスクは、そのようなグリッド（サイズの）を構築することでした $6 \times 6$）構築できない最小の正の数が可能な限り大きくなるようにします。
明らかに、このゲームとその後の最適化は、任意のサイズの正方形のグリッドに一般化できます。 $n \times n$。
さらに、私たちは自分自身をベースに制限する必要はありません$10$。任意の正の整数が与えられます$b$、各セルには次の1桁が含まれている必要があると判断できます。 $0$ に $b-1$ そして、この新しいベースに関して最適化を提起します（単項のみを使用することを除いて） $1$）。
この一般化に動機付けられて、私たちはより小さな基盤で問題を見ることができます。
特にケースを見ると$n=2$ そして $b=2$、最適化タスクは次のような結果になる可能性があります
このグリッド（または実際には $2 \times 2$ 2つのグリッド $0$sと2 $1$s）Numerical Boggleの規則に従ってすべての2進数を作成することが可能です（自分で試してみてください）。そのようなグリッドはベースで無限の範囲を持っていると言います$b$。
さらに、ベースと言います $b$ 無限の範囲のグリッドが有限サイズの正方形のグリッドがあることを認めます（$n \times n$）ベースに無限の範囲がある $b$。これは私たちのパズルにつながります。
最大の正の整数基数は何ですか $b$ これは、無限の範囲の有限の正方形グリッドを許可するか、そのようなことを行います $b$存在しますか？ あなたの答えの証拠を提供してください。
回答
ここでは上限である下の他の回答の下限と一致するように、私は下界マッチしたが、私は尻込みのルールを誤解考えました：
いずれか $k\times k$ ボード、長さの数-$n$ パスは大まかに成長します $8^n$。たとえば、それはによって制限されます$k^2 \cdot 8^n$： 我々は持っています $k^2$ 開始する場所、そしてそこから、各ステップは次のいずれかに進みます $8$行き方。（すべての方向のすべてのステップが常に可能であるとは限りませんが、これは上限です。）
ただし、 $n$-基数の桁数 $b$ 大まかに成長する $b^n$：です $(b-1)b^{n-1}$。だから、$b \ge 9$、長さの可能なパスの数 $n$ 最終的にはの数よりも少なくなります $n$-数字、そして私たちが見つけることができないいくつかの数字があります。ボードを大きくするほど、この大惨事は遅くなりますが、最終的には発生します。
まだギャップがあります
$5 \le b \le 8$、解決策が存在する可能性がありますが、私たちはそれを知りません。
グリッドは有限であり、無限に長いシーケンスを表現できる必要があるため、すべての数字に接続されていない正方形のグリッドに数字Xを追加しても、ほとんど意味がないようです。数字の場合、前のステップで、接続が不十分なXを介して作成できないシーケンスにアクセスできるXのある別の正方形も必要になります。これにより、無限の分岐が発生するようです（可能なすべてのシーケンスに対応する必要があるため、常に私たちにとって最も厄介な道を選ぶ邪悪な敵がいること）、それは私たちが有限の運動場ではできないことです。
上記が実際に当てはまるかどうかはわかりませんが、当てはまると仮定して、すべての桁がすべての可能な桁に接続され、必要な「無限の範囲」を簡単に提供できる「適切に接続された」ボードを構築してみましょう。
基数3は単純に見えます（本当に正方形が必要な場合はランダムな数字で埋めます）：
0 1 1 0
0 2 2 0
または、可能な最小の正方形内に収まる可能な最小の桁数で：
0 0 1 2 1 2
Base-4は少し簡単ではありませんが、それでもかなり実行可能です。
0 0 1 2 3 1 1 3 2 1 0 0
Base-5には問題があります。
一番上の行の左端の「適切に接続された」数字は、下側と右側だけに5つの隣接番号を持つことはできません。
0 4 1 2 3
もちろん、別の番号を追加することでこれを修正できますが、それでも問題があります。
同時に
1.適切に接続された（すべての可能な数字の隣）、
2。一番上の行、および
3.その行の左端の数字である数字は存在できません。
したがって、最初の章の推測が何かの価値があると仮定すると（私はそれがまったく確かではありません）、私たちができることはほとんどです
ベース4、標準の4x4ボグルボードの内側に収まります。
ミシャラブロフの答えにわずかな改善。
長さの異なるパスの数 $nk$ それはで追跡することができます $n\times n$ グリッドはせいぜい $n^2(8^n-3^n)^k$。これは、の各グループが$n$ 連続した動きがすべて上に行くことはできないので、せいぜい $8^n-3^n$ 各グループの方向の許容シーケンス。
ザ・ $k$これのルートは $n^{2/k}(8^n-3^n)<8^n$ ために $k$ 十分に大きい（ $n$）。したがって、あなたは厳密に以下を作ることができます$8^{nk}$ 長さの異なる数 $nk$ のいくつかの値について $k$、だからケース $b=8$ また、不可能です。
残念ながら、これ以上プッシュできるとは思いません。
封筒裏の計算は、十分な大きさの場合、 $n$ 本当に以上のものがあります $7^k$ 長さの異なるパス $k$ すべてのための $k$、ランダムウォークがあるので $8$ 選択肢はすべて $k-O(k/n)$ 確率の高いステップ、および $8^{1-O(1/n)}>7$ 大用 $n$。
私はバスの答えを支持するより強い議論があると思います。
1. Boggleボードの非常に多くのアイランドが共同ですべてのシーケンスを生成できる場合、少なくとも1つのアイランドがすべてのシーケンスのゼロ以外の割合を生成します。
2.アイランドがすべてのシーケンスのゼロ以外の割合を生成できる場合、実際にはすべてのシーケンスを生成できます（したがって、無限の範囲があります）。理論的根拠：特定の有限の長さのシーケンスを生成できない場合$k$、長さに対する生成されたシーケンスの割合 $\ell+1$ は（大まかに） $1-1/2^k$ 長さの倍 $\ell$。したがって、すべての割合$\ell \in [1, \infty)$ゼロに収束します。矛盾。
3.無限の範囲を持つ有限のボードに、それ自体で始まるすべてのシーケンスを生成しないセルがある場合、そのセルは、無限の範囲を損なうことなく削除できます。理論的根拠：結論が誤りであると仮定します。次に、あるシーケンスが問題のセルを通過するように強制され、仮定により、ボードによって生成できないシーケンス（セルに強制するシーケンス+セルから生成できないシーケンス）を構築できます。 。矛盾。
4.すべての有限ボード $b \ge 5$少なくとも、それ自体で始まるすべてのシーケンスを生成できないセルが含まれています。Bassの回答に見られるように、これは些細なことです。一番上の左端のセルのアウトディグリーは常に4以下であるためです。
5. 3と4を組み合わせると、無限の範囲を持つ有限のボードは存在しません。 $b \ge 5$。
上記の主張に論理的な穴がないと仮定すると、答えは
Bassが見つけたように、無限の範囲のボードを許可する最大ベースは4です。
ステップ1と2は、結論として実際には必要ないと思います（
島の有限のコレクションはまだ有限のボードです
）、しかし、IMOは興味深い観察であるため、私はそれらを保持することにしました。
b = 5の解のスケッチ（？）。フィードバックを募集するために、未完成の写真を表示しています。
一般的な考え方：Uターンのある高速道路：
色分けされた青写真。青が背景です。白い線は、それぞれが4つの「車線」を持つ交互の方向の4つのストリップを分離するための視覚的な補助です。これは一般的なレイアウトを示しているだけであることに注意してください。最終的な解決策では、より長く、より多くのストリップが必要になる場合があります。
単一のストリップ内で、各正方形に同じストリップ内で必要なすべての隣接するものがあることに注意してください。
したがって、これを殺す唯一の方法は、動きを一方向に偏らせることです。ここで、隣接するストリップが機能します。必要に応じて、Uターンして元に戻すことができます。
それで、これはすべてを解決しますか？
100％確実ではありません。2つの問題があります：1。すべてではありませんが、多くの場所でUターンできます。2.変更するストリップを常に選択できるとは限りません。そのため、原則として、最後のストリップで終わり、道路が不足する可能性があります。
2.これを強制するには、多かれ少なかれ常に対角線の移動を強制し（直交移動はほぼ確実にあまりにも多くの小刻みに動く余地を与えます）、適切な時間に車線を変更する必要があるため、おそらく実際の問題ではありません。おそらく、いつUターンするかをある程度制御できないようにすることはできないので、この2番目の要件を適用するのは難しすぎるように見えます。
私の直感は、1にも対処できるということです（今のところ、すべてのケースを打ち負かすことはできません。他の誰かがそれをやりたいと思ったら、私の賛成票が保証されます）
注目すべきことの1つは、このセットアップには、前向きな計画によってのみ打ち負かすことができる攻撃が実際にあるということです。敵が予告なしに次の桁を決定できた場合、彼らは私たちを殺す可能性があります。
例は、次の詳細な戦略を使用した上からの攻撃2です。黄色->赤->明るいオレンジ->紫->暗いオレンジを循環して、Uターンを強制します。Uターンが1桁を繰り返すことによって車線変更を強制した直後に、選択の余地がない色を待つだけです。最初からやり直します。車線変更がいつ予定されているかを事前に知っていれば、いつ正確にUターンしてこの攻撃を打ち負かすことができるかは明らかです。