ある日、ここクイズ大陸に、あろうことか、ズイーク大陸のきんぐとかいうやつが遊びに来た。


クイズ大陸の住民「きんぐさん、48時間以内の連続投稿はやめてください 」

きんぐ「あれ、そうなのか？すまんすまん。なにせズイーク大陸には、出題するクイズを全てサンスクリット語で書いてはいけない、というルールしかないもので 」

住民「ところで、きんぐさんが今、大事そうに抱えているそれは何ですか？ 」

きんぐ「これか？これは、ズイーク大陸でボケ回答をすると、出題者の判断により贈呈される、ズイーク像というものだ。今回はこれを使った問題を出題した」

問題：

n×nのマス目がある。このマス目に、1マスにつき1個以下、ズイーク像をなるべくたくさん置いていくことを考える。ただし、次の条件を満たす置き方でなければならない。

条件：置いたズイーク像のうちのどれか4つを頂点とする、その辺がマス目の辺に平行な長方形ができてはならない。

例えば、4×4のマス目に、次のようにズイーク像を置いたとする。
(¶がズイーク像が置かれたマス、○がそうでないマスを表す)

○¶○¶
○○○○
○○○○
○¶○¶

このとき、置いたズイーク像によって、(傾いていない)長方形ができてしまっているので、これはダメな置き方である。

きんぐ「この条件に従って、ズイーク像をどれだけたくさん置くことができるかな？という問題だ。例えば、n=2,3,4,5のときは、それぞれ、次のような置き方がある(他にも置き方はいくつかある)」

(2×2)

○¶
¶¶

置けるズイーク像…3個

(3×3)

○¶¶
¶○¶
¶¶○

置けるズイーク像…6個

(4×4)

○¶¶¶
¶○○¶
¶○¶○
¶¶○○

置けるズイーク像…9個

(5×5)

○¶¶¶¶
¶○○○¶
¶○○¶○
¶○¶○○
¶¶○○○

置けるズイーク像…12個

きんぐ「それぞれの個数が最大であることも証明できる。」

住民「うわ〜クイズ大陸の文字装飾というシステムを利用しまっくてますね 」

きんぐ「では、ここでお前に問題だ。同じように、今度は6×6のマス目に、ズイーク像をできるだけたくさん置いてほしい。果たして、最大で何個置けるかな？ 」

きんぐ「答えるときは、その個数と、その置き方の例を一つ囁けばいい。ただ、¶なんていう記号は、KSTがただ自分の問題の見栄えの良さを追求するためだけに使ったものだから、！や、■みたいなもので代用して構わない」

住民「すいませんけど、他にも面白いクイズがたくさんあるので… 」

きんぐ「私の言う通りにしなければ、お前の今後の人生において、なんかかんか精神的にマイナスになるようなことが、きっと起こるぞ！！ そしてその後、なんかかんか精神的にプラスになるようなことが、きっと起こるぞ！！ 」

住民「はいはい、分かりましたよ… 」


・・・というわけで、きんぐの言う通りにしてあげてください。きんぐはきっと、Facebook上でしか友達がいないのです。せめてこのクイズがロックされるまでの間ぐらいは、お相手してあげてください。
きんぐなんか嫌いだもんね！！って方は、遠慮なくスルーしてください。

(オマケ)(上級者向け)
数学の腕に自信のある方は、求めた個数が最大であることを証明してみてください。
また、7×7の場合ではどうかも、考えてみてください！
高校数学の範囲で証明は可能ですが、少々エレガントな閃きが必要なので、挑戦しがいはあると思います