マス目に数を書き込んだときの隣接する数の和

100

数学力のなさ

　私が作問しOMCに出題された以下の問題について、一般化を考えたい。

OMC027-B

$3 \times 3$ のマス目に $1$ 以上 $9$ 以下の整数を $1$ つずつ書き込みます。このとき、どの隣り合う $2$ マスについても、数の和が $11$ 以下となるような書き込み方は $M$ 通りあります。 $M$ を解答してください。ただし、回転や反転で一致するものも区別するものとします。
（ https://onlinemathcontest.com/contests/omc027/tasks/3 より）

　 $11$ という数は、限界の値である。つまり、これを $10$ にすることはできない。どのマスも少なくとも $2$ つのマスと隣接しており、 $9$ と隣接する数を考えれば、和の最大値は $11$ 以上にならざるを得ないからである。
　では、 $n \times n$ ではこの限界の値はどうなるか。次が成り立ちそうである。

$n \times n$ のマス目に $1$ から $n^{2}$ までの整数を $1$ つずつ書き込むとき、隣り合う $2$ マスの数の和の最大値としてありうる最小値は、 $n^{2} + ⌊ \frac{n}{2} ⌋ + 1$ である。すなわち、どの隣り合う $2$ マスについても数の和が $n^{2} + ⌊ \frac{n}{2} ⌋ + 1$ 以下となる書き込み方は存在するが、どの隣り合う $2$ マスについても数の和が $n^{2} + ⌊ \frac{n}{2} ⌋$ 以下となる書き込み方は存在しない。

$n^{2} + ⌊ \frac{n}{2} ⌋ + 1$ のときは、以下のように数を書き込んでいけばよい。(図は $n = 9$ のとき)
左上から大きい数と小さい数を交互に埋めていく

あとは $n^{2} + ⌊ \frac{n}{2} ⌋$ が無理であることを証明すればよいが……。証明が思いつかないので、置いとこう。

　最初のOMC問題の一般化としては、次の問題を解くことが一旦の目標となる。

一般化

n \times n

$n \times n$ のマス目に $1$ 以上 $n^{2}$ 以下の整数を $1$ つずつ書き込む。このとき、どの隣り合う $2$ マスについても、数の和が $n^{2} + ⌊ \frac{n}{2} ⌋ + 1$ 以下となるような書き込み方は何通りあるか。ただし、回転や反転で一致するものも区別するものとする。

$n = 4$ のときを実際に求めてみよう。

4×4雑解説

　 $16, 15$ の位置関係で場合分けを行う。★は $1, 2, 3, 4$ のいずれかを表す。
(14,5),(13,6),…を順にはめ込んでいく方法を考えると、数えられる

以上により、合計は $11520$ 通りである。

一般化検討

　 $n \times n$ のときも $4 \times 4$ と同様に、最初のいくつかの数を与えておけば、あとは $2 \times 1$ の長方形で埋める方法を数えていけばよい。が、結局場合分けが大量発生するような気がする……。よくわからん。

もっと一般化できるくね？

a_{1} \times a_{2} \times \dots \times a_{n}

　 $a_{1} \times a_{2} \times \dots \times a_{n}$ の $n$ 次元直方体のマス目に $1$ 以上 $a_{1} a_{2} \dots a_{n}$ 以下の整数を $1$ つずつ書き込む。このとき、どの隣り合う $2$ マスについても、数の和が $N$ 以下となるような書き込み方は何通りあるか。ただし、回転や反転で一致するものも区別するものとする。

　 $3$ 次元の一番簡単な場合だけやってみる。 $2 \times 2 \times 2$ で、 $N = 11$ とする。
　 $8$ の場所が $8$ 通り、 $1, 2, 3$ の場所が $6$ 通り、 $7$ と $4$ の場所が $3$ 通り、 $5$ と $6$ の場所が $2$ 通りなので、 $8 \times 6 \times 3 \times 2 = 288$ 通り。