概要
軸に平行な長方形の4点すべてが O にならないように、たくさんの O を並べる問題です。
$150 \times 150$ の枠に詰め込んで、1700個以上を並べると満点を得ることができます。
適切な数学概念と結び付けることで簡潔に解を構成できることが分かったので，記事にします。
また，1700個で満点を得ることができますが，1800個並ぶ解の構成にも成功しました。
射影平面の復習
以下の記事で扱っているため、詳細はそちらに委ねます。
射影平面の定義と性質を軽く振り返りましょう。$K$ を体とします。本問に関して言えば、最終的には $K = \mathbb{F}_{13} = \mathbb{Z}/13\mathbb{Z}$ の場合に興味を持つことになります。
- $K^3\setminus 0$ を、定数倍で一致する2元を同一視した商集合を、$\mathbb{P}^2(K)$ と書き，$K$ 上の射影平面という。
- 射影平面上の点は，次のいずれかの形で一意に表せる．$K = \mathbb{F}_q$ のとき，$\mathbb{P}^2(K)$ は $q^2 + q + 1$ 個の元からなる．
- $[x:y:1]$ （ただし、$x,y \in K$）
- $[x:1:0]$ （ただし、$x \in K$）
- $[1:0:0]$
- $[a:b:c]\in \mathbb{P}^2(K)$ に対して，集合 $\bigl\{[x:y:z]\in \mathbb{P}^2(K)\mid ax + by + cz = 0\bigr\}$ を直線という．
- 任意の相異なる2点に対し，それらを通る直線が唯一存在する．
- 任意の相異なる2直線に対し，それらの交点が唯一存在する．
体 $K$ 上のふつうの座標平面（アフィン平面 $\mathbb{A}^2(K)$）においては、$K = \mathbb{R}$ の場合によく知られているように，2点を通る直線は1つ存在し，2直線の交点は「平行でなければ」1つ存在します。直線と点の配置に関するこの性質を、無限遠点の付加よりさらに洗練させたものが射影平面といえるでしょう。
本問題の解答
$N = q^2 + q + 1$, $S = (q+1)(q^2+q+1)$ の構成
問題の条件（「長方形」の非存在）を上手く行あるいは列を主体に解釈します。すると、
2列を任意に選んだとき、それら2列ともに O が書き込まれているような行は、高々1つである
という性質として理解できます。「任意の2個に対して、高々1つの〇〇が存在」という形なので、点と直線の関係ですね！したがって、$q$ を素数べきとするとき以下の構成が可能です。
- 有限体 $K = \mathbb{F}_q$ を考える（$q$ 元体の存在に、$q$ が素数べきであることを使う）。$\mathbb{P}^2(K)$ の元の個数を $N = q^2 + q + 1$ と書く。
- 射影平面 $\mathbb{P}^2(K)$ の直線を $l_i$（$1\leq i\leq N$）とする。
- 射影平面 $\mathbb{P}^2(K)$ の点を $p_j$（$1\leq j\leq N$）とする。
- 次のようにしてマス目 $A$ を作る：
- $l_i$ が $p_j$ を通るときに、$A_{ij}$ を O とする。
- そうでないとき、 $A_{ij}$ を . とする。
長方形ルールに違反しない書き込みができました（なお、$N = q^2 + q + 1$ に対する理論最大個数の O を達成しています、公式解説参照）。
部分行列の抽出（乱択）
$q = 13$ に対してこの構成を行い、得られたマス目を $A$ とします。これは、$183\times 183$ のマス目で、このうち $\frac{14}{183}$ の割合で O が書き込まれています。
任意に行・列を $150$ 個ずつランダムに選んだ場合、O が選ばれる期待個数は $150^2 \cdot \frac{14}{183} =1721.31\cdots > 1700$ となります。条件を満たす盤面の存在が証明できました。
実際の構成も、乱択アルゴリズムにのっとればよいです。適当に $150$ ずつ行・列を選んで AC を得ます。（解答例 → ■）
なお、乱数シミュレーションの結果 $1700$ を下回ることはほとんどなく，また単に上から・左から $150$ ずつ選んでくるだけでも条件を満たします。
部分行列の抽出（乱択＋貪欲）
好きに行・列を $150$ ずつ選んで、O の個数を最大化するのが課題です。これはそれほど単純ではない問題であるように思われますが、選ぶ行を固定してしまえば単なる貪欲アルゴリズムにより、O の個数を最大化できます。
「選ぶ行 $150$ 個をランダムに決め打って貪欲に列を選ぶ」を探索することで、$S = 1800$ が実現できました。
コメント
- 乱択＋貪欲の方法に対して、焼きなまし法 ・山登り法などの最適化手法を組み合わせるとさらに高いスコアが出るかもしれません。
- 今回のマス目に必要な性質は、直線・点の言葉でいうと、「相異なる2点を通る直線が1つ以下」「相異なる2直線の交点が1つ以下」のように、「〇〇が1つ以下」という性質に限定されています。そのため、射影平面を考えずとも、アフィン平面（座標平面）を考えたり、一部の直線を考えることで事足ります。例えば次のようにします。
- $K = \mathbb{F}_{13}$ とする。$N = 169$ とする。
- $K^2 = \{(x,y)\mid x,y \in K\}$ （アフィン平面）の元を $p_1,\ldots,p_N$ とする。
- $(a,b) \in K^2$ に対して $y = ax + b$ と書ける直線 $l_1,\ldots,l_N$ を考える。
- これらの点と直線を用いて、$N = 13^2$, $S = 13^3$ に対応するマス目が構成できる。
- ここから $150\times 150$ のマス目の構成も、射影平面の場合と同様にできる。
- $y$ 軸に平行な直線も考えて、$169\times 182$ 行列を出発点にしてもよいですね。
- アフィン平面による構成も十分に自然な解法と言えると思います（点と直線の配置に関する問題だと見るなら、まずは射影平面を考える方が素直かなとは思います）。
- 射影平面を利用して構成した $183\times 183$ 行列から適切に $169$ 個ずつの行・列を抽出すると、アフィン平面を利用した構成と一致します。$150$ 個ずつの行・列を選ぶ上では，射影平面を構成した場合の方が選択肢が単純に広く用意できており、O の個数の最適化のためにも有利かと思います。