艦隊を盤面に詰める話
ランデヴー
やりたいこと
今日もバトルシップがテーマです。ルールについては以前の記事を参照ください。
今回考えるのは「サイズ b の standard fleet を n×n の盤面に詰めるとき、n の下限は？」という問題です。
例として、b=5 だと n=9 にすっぽり収まります。
こういう、いい感じの例を見つけたいわけですね。
評価する
ナナメ隣接禁の配置系では、盤面の頂点に注目するのがセオリーでした。
上の例でだと、b=5 の standard fleet が占める頂点の個数は、
4×5+6×4+8×3+10×2+12×1=100
となります。一方、n=9 の盤面にはもともと頂点が 10×10=100 個なので、ちょうど使い尽くせるというわけですね。
一般にサイズ b のstandard fleet が占める頂点の個数を計算すると (シグマ計算で簡単に出せます)、b(b+1)(b+5)/3 個になります。これが (n+1)^2 になればいいですね。
と思ったら少し違います。実際には n が偶数のときこんなにうまく詰められません。
それを見るために、まずは n が奇数の例を倒しておきましょう。
奇数の場合は、図のように 1 列とばしに詰めるとうまくいきます。艦隊隣接禁を「右に 1 マス空白を入れて詰める」と思えば、これで頂点数の評価と同じ式が出てきます。実際に詰めれるかどうかは構成しないとダメですが、まあ艦隊のサイズが盤面より明らかに小さいのできっと大丈夫です。
というわけで問題の n が偶数のケース。これは盤面を 2×2 のブロックに割って考えましょう。するとこのブロックに艦影は高々 2 個しか入りません。それどころか、艦隊のも 2 個ずつに切ってみると、それぞれのパーツが必ず 1 つのブロックを占有してしまいます。特に、奇数の長さの艦でロスがでてしまいますね。
これを丁寧に計算すると、
・b = 2k のとき、必要ブロック数は k(k+1)(4k+5)/6.
・b = 2k-1 のとき、必要ブロック数は k(k+1)(4k-1)/6.
となります。これが、もともとある n^2/4 以下でないといけません。
なおこれも、奇数ケースのように 1 列とばしで構成できると思います。
そして、この評価は先ほどの頂点注目の評価より少しだけきついものになっています。(計算するとわかる/オーダー自体は変わらない)
実際、 b = 7, n = 14としましょう。このケースでは頂点評価だと
・必要な頂点数 (7×8×12)/3 = 224
・盤面の頂点数 15×15 = 225
とギリギリ入りそうに見えます。
しかし、ブロックで評価すると
・必要なブロック数 上の b = 2k-1, k=4 の場合で、(4×5×15)/6 = 50
・盤面のブロック数 7×7 = 49
となり、ギリギリ入らないことが示せました。
すなわち、
「サイズ 7 の standard fleet は 14×14 の盤面に収まらない」
とわかりました。
ちなみに、 b = 6, n = 12 だと、34 < 36 となって収まります。どこかで見たサイズですね。
いい感じのケース
あとは、人として、艦隊がギリギリ詰まるようなケースが気になりますよね？
はい。少し調べました。
・n が奇数のとき
n = 2m-1 とおきます。
この場合、頂点評価の b(b+1)(b+5)/3 <= 4m^2 について、等号を満たす例がいくつか存在します。
パソコンさんに探索してもらったところ、(b, m) = (1, 1), (5, 5), (15, 20), (49, 105) という例が見つかりました。ちゃんと書くと
・サイズ 1 の standard fleet は サイズ 1 の正方形盤面にぎりぎり配置できる←それはそう
・サイズ 5 の standard fleet は サイズ 9 の正方形盤面にぎりぎり配置できる←さっきのやつやね
・サイズ 15 の standard fleet は サイズ 39 の正方形盤面にぎりぎり配置できる←？！
・サイズ 49 の standard fleet は サイズ 209 の正方形盤面にぎりぎり配置できる←？！？！？！
となります。
b = 15 で適当に詰めるとこんな感じ。一番下のはもうやりません。
なお、この (b の 3 次式) = (m の 2 次式) という形の式は、整数解を有限個しか持たないことが、数論 (楕円曲線) の定理として知られています (Siegel の定理/非特異とかあるけど詳しくは略/証明はめちゃたいへん)。
もう少し大きいところまでパソコン先生に調べてもらっても出てこなかったので、たぶんこれらで解が出尽くしていると予想します。定理自体は有限性しか保証していないですが、全探索アルゴリズムはあるそうです。しかり具体的にはわかってません。知ってる方はご報告ください。
・n が 偶数, b が偶数のとき
これも n = 2m, b = 2k とおきます。
ブロック評価は k(k+1)(4k+5)/6 <= m^2 です。これもパソコン先生に聞くと、イコールになる例はなさそうでしたが、k(k+1)(4k+5)/6 +1 = m^2 となる例がいくつかありました。その解は
k=1,15,32,96,406,1679
だそうな (m は省略)。1679 って何？？？？？てかなんで 6 個もあるの...
まあこれが有理数だといろいろ出てきそうですが (cf. Mordell の定理)、6 個もあるのはなかなか奇跡的な気がします。なおこれもさっきと同じで、これ以外に解はなさそうです。
・ n が偶数、 b が奇数のとき。
これも評価式の 1 つ少ないギリギリのケースとして (b, n) = (189, 1518) というものみ見つかりました。
というわけで
ギリギリのケースが見つかったので、みんなもこれを使って問題作ろう！！！
......
ここだけの話、作ったソルバーを用いて、実際に b = 5, n = 9 のまだ作れそうな例で問題を作ろうとしたのですが、ソルバーくんはこの評価に気付けないらしく (そりゃそうだ)、解をぜんぜん返してくれませんでした。なのでソルバー破りにはもってこいかもしれない...？(頂点占有を制約の式に入れれば解いてくれるかもだけど)
まあでも実際、サイズ 15 とかを詰めてるの見たいですよね！(間違いなく観賞用ですが......)
.....
あこれ、このまえ大域手筋の記事にのっけたやつのネタバレになってんな。まいっか。
