JMO2019本選問2

答え\(\cdots n(n+1)\)

【分析】

まず、「問題を正しく読めたか」というのが勝負の分かれ目なのではないでしょうか。僕自身も数回読み直してから理解しました。この問題のややこしいポイントは「数字を書き込むたびに点数が入る」ということでしょう。つまり、\(3\times 3\)で具体例を挙げると(書き込む数字は1以上9以下ですが \(mod \ 3\)にしか興味がないので\(0,1,2\)を3つずつ書き込むことにします。)

のような感じで点が入り、この場合であれば\(2+2+2+0+1+1+1+1+2=12\)点というわけです。このように最後の書き込まれている数字を見ても書き込む順番が分からなければ点数はわからないわけです。しかし、実は最後に書き込まれている数字を見るとうまい順番で書き込んでも〇〇点しか入らないというふうに上からおさえることができます。たとえばこの例の3行目は\((1,2,0)\)なわけですがこれらはどのような順番で書き込んでも3行目では2点しか入らないというのは明らかですよね?

【略解】

\(mod \ n\)にしか興味はないので\(n\times n\)のマスに\(1\)以上\(n-1\)以下の整数を\(n\)個ずつ書き込むことを考える。

ゲームが終了した時点での数字の書き込みに注目すると\(m\)行目で入る点数は最大でも

$$(m行目にある0の個数)+\left[\frac{(m行目にある0以外の数の個数)}{2}\right]\ 点\cdots ☆$$

である。(∵\(\ \)0は始めに書き込めばそれぞれ1点になり、0以外の数は他の数と足して0を作らないと点が入らないので足して0になるペアができるときが最大)ここで、[a]でaの整数部分を表すことにした。

☆を各行各列に関して和を取ると書き込まれている数字においての点数の上限を与えることができ、

\begin{eqnarray}&&\sum_{m=1}^n\left\{
(m行目にある0の個数)+\left[\frac{
(m行目にある0以外の数の個数) }{2}\right] \right\} \\
&&+\sum_{m=1}^n\left\{
(m列目にある0の個数)+\left[\frac{
(m列目にある0以外の数の個数) }{2}\right] \right\}\\ =&&
\sum_{m=1}^n\left\{
(m行目にある0の個数)+
(m列目にある0の個数) \right\} \\
&&+\sum_{m=1}^n\left\{
\left[\frac{
(m行目にある0以外の数の個数) }{2}\right] +\left[\frac{(
m列目にある0以外の数の個数 )}{2}\right] \right\}\\ \le&& 2n+
\sum_{m=1}^n\left\{
\frac{(
m行目にある0以外の数の個数 )}{2} +\frac{(
m列目にある0以外の数の個数 )}{2} \right\}\\ =&&2n+(n^2-n)=n(n+1) \end{eqnarray}

となる。(∵\(\ \)1つの数字は行と列で2回点数に関与する。)

よって、\(n\times n\)マスでの点数は\(n(n+1)\)以下ということが分かり、\(n(n+1)\)点のものは簡単に作れる。(省略)

(上の例のように数字を書き込むとできます。)

コメントを残す

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