馬杉：奇数は無理？偶奇が市松模様になってるから
平山：最初はどこも偶奇が隣接してるからね
渡辺：最小手数を求めねば
平山：偶数の場合もできるだけ上下で操作がしたく…
渡辺：$n=2$ で最小 $3$ 手
平石：とりあえず、各 $2\times 2$ について $3$ 回ずつやればいける
宿田：$3n^2/4$ で良さそうよね
馬杉：それで明らかに少なくとも $n^2/2$ は要る
平山：$0$ じゃないやつがどんくらい出てくるかみたいなところで
渡辺：$2$ 回操作されるのが何個とかも考えられそう
馬杉：帰納法使えないの
平山：盤面の見た目結構変わるし渋くない？
馬杉：確かに
兒玉：まず全部正にしようとすると $n^2/2$ かかって、
兒玉：どの隣り合う $2$ つも相異ならせようとすると余計かかるみたいな
平石：全部 $0$ から始めて逆向きに見ているのか
平山：でも必ずしも最初に全部正にするのが最善と保証できない気がしている
馬杉：それなんですけど、多分 $6$ マスくらいを $4$ 手で何とかする方法があり
平山：やっぱりそうだよね
渡辺：ある操作で選んだ $2$ マスの少なくとも一方はさらに操作されてるとかダメかな
馬杉：終わりそう
平山：すぐには終わらない？でも今のところ一番近そう
兒玉：$1$ 回だけ操作されるマスは隣り合わないはずで？
平山：それが一般に嘘なのがキツいです
馬杉：でも大体そんな感じだと思っていて
兒玉：部分 $2\times 2$ を見る？ダメそう
平山：それは $2$ 部分にまたがる操作がつらくて
兒玉：いずれにせよ左下から右下への単調増加性はどっかで使いそう
宿田：各マスを頂点として、操作されたところを辺にしたグラフを考えています
平山：悪くなさそう
宿田：連結成分の頂点数は最低でも $4$？
平山：ん、正しそうだけど
馬杉：それでいけるの？
平山：$3$ 頂点以下がダメなのは個別撃破すればよくて
宿田：出来そうな気がしてきた
平山：連結成分の数が多いほうが得なはずで
平石：いけてそう
宿田：$a$ と $b$ の間に $a+b$ が無いから大丈夫なのかな
馬杉：ヤバすぎて草
渡辺：えらい

• 工事中

$(i,j)$ で $i$ 行目 $j$ 列目のマス目を表すものとする.

まず $n$ が奇数のとき, はじめマス目に書かれた数の総和は $n^2(n^2+1)/2$ であり, $n^2+1\equiv 2(\mathrm{mod}4)$ よりこの値は奇数であるが, 操作により総和の偶奇は変化しないので示された.

次に $n$ が偶数のとき, 各 $1\leqq i,j\leqq n$ に対して以下のように操作すれば, 全てのマス目に書かれた数は $0$ になる.

• $(2i-1,2j-1),(2i-1,2j)$ で $m=-((2i-1)(n-1)+2j-1)$
• $(2i,2j-1),(2i,2j)$ で $m=-(2i(n-1)+2j-1)$
• $(2i-1,2j),(2i,2j)$ で $m=-1$

このとき操作回数は $3n^2/4$ である. 以下, これが最善であることを示す.

各マス目を頂点とし, 操作が行われた $2$ マスの間に辺を張ったグラフ $G$ を考える.

$G$ の各連結成分の辺数は $(\text{頂点数})-1$ 以上であるから, 辺の総数は $n^2-(\text{連結成分数})$ 以上である. ここで, 補題より $G$ の連結成分は $n^2/4$ 個以下であるから, 操作回数は $3n^2/4$ 以上である.