[AtCoder] F – Distribute Numbers(CODE FESTIVAL 2017)

スポンサーリンク

概要

問題文 →
自分の提出 →
公式解説pdf →

公式解説による説明と比べて、より明確な数学概念と結び付けて考察したので、一応書いておきます。最終的な構成方法自体は公式解説の方法と同一になるかと思います。(作問者はこれ想定せずに独立にこれに至ったのかなー?)

今回のは、競プロで何度も役立つテクニックって感じではないかと思います。

本記事は割と数学語でさくっと書いていて、初心者向けではないです。不明な用語があれば、ググりながら読んでいただければと。

射影平面

射影平面の定義

$K$ を体とし、$V = K^3$ を$3$次元空間とします。
$V$ から原点を除いたもの $V\setminus\{0\} = \{x\in V\mid x\neq 0\}$ 上に、次の二項関係 $\sim$ を考えます:

\[x\sim y\iff \exists \lambda \in K\setminus\{0\}, y=\lambda x.\]

この関係は同値関係で、商集合 $(V\setminus\{0\})/\sim$ が定義されます($x\sim y$ となる$x,y$ を同一視する)。この商集合を $\mathbb{P}^2(K)$ と書き、$K$ 上の射影平面といいます。

射影平面の構造

射影平面の1つの理解の方法は、

$\mathbb{P}^2(K)$ は、 $3$ 次元空間 $V$ における、原点を通る直線全体.

というもので、素直に定義を見るとほぼそのままこのような解釈が可能です。ただし「平面」っぽさが足りませんね。

射影平面上の点は、代表元をとって $[x:y:z]$ のように表す(斉次座標)ことにします。同値関係の定め方により、$[x:y:z] = [\lambda x:\lambda y:\lambda z]$ が成り立ちます。したがって

・$z\neq 0$ であるような点 $[x:y:z]$ は、$[x:y:1]$ と表すことができる。
・$z=0, y\neq 0$ であるような点 $[x:y:0]$ は、$[x:y:0]$ と表すことができる。
・$y=z=0$ であるような点 $[x:0:0]$ は、$[1:0:0]$ と表すことができる。

ことが分かります。

\[ \mathbb{P}^2(K) = \{[x:y:1]\mid x,y\in K\}\amalg \{[x:1:0]\mid x\in K\}\amalg\{[1:0:0]\}.\]

$K^2$ と $K^1$ と 1点の和として $\mathbb{P}^2(K)$ を表すことができました。これを「$K^2 + $その他」と見ることで、

・$\mathbb{P}^2(K)$ は、平面 $K^2$ に「無限遠直線」を付け加えたもの

と考えることができます。

平面 $K^2$ 上の点 $(x,y)$ は、斉次座標 $[x:y:1]$ によって $\mathbb{P}^2(K)$ に埋め込まれています。

無限遠直線は座標で書けば $[x:y:0]$ と書ける点全体です。無限遠直線上の点は、無限遠点と言います。

無限遠点の幾何学的な意味

「射影平面 = 平面 + 無限遠点たち」と表示できますが、この無限遠点とは何者でしょうか?$K=\mathbb{R}$ の場合に直感的な動機付けがしやすいです。

無限遠点 $[x:y:0]$ を考えます。ここで雑に $[x:y:0] = \lim_{\varepsilon\to 0} [x:y:\varepsilon]$ と考えてみましょう。$[x:y:\varepsilon] = [x/\varepsilon:y/\varepsilon:1] = (x/\varepsilon,y/\varepsilon)\in K^2$ です。したがって、無限遠点 $[x:y:0]$ は、

\[\lim_{\varepsilon\to 0} (x/\varepsilon,y/\varepsilon) = \lim_{t\to\pm\infty}(tx,ty)\]

を表していると考えられます(実際にはこれが成り立つように位相を定義する)。「$(x,y)$ 方向に無限に進んだ先にある点」をうまく定式化したものが無限遠点と言えそうですね。

射影平面上の直線

$[a:b:c] \in \mathbb{P}^2(K)$ とするとき、集合 $\{[x:y:z]\in \mathbb{P}^2(K)\mid ax+by+cz=0\}$ を射影平面上の直線といいます。このとき、次が成り立つことが分かります:

・任意の相異なる2点 $A, B\in \mathbb{P}^2(K)$ に対して、$A,B$ を通る直線が唯一存在する.
・任意の相異なる2直線 $l,m$ に対して、交点が唯一存在する.

通常の平面においても、平行線を例外としてこの性質はかなり惜しいところまで成り立ちます。この平行線の例外を、無限遠点の付加によって完全に解消しているのが射影平面であり、特に交叉理論において大きな役割を果たします(例:Bezoutの定理)。

なお、直線の方程式の係数比 $[a:b:c]$ は $\mathbb{P}^2(K)$ の点。つまり射影平面上の直線と射影平面上の点との謎の対応があります。これは双対と呼ばれる対応ですが、幾何的に分かりやすい何かだとはとりあえずは思わなくてもよいでしょう。

注意

「平面に無限遠点を加えて良い感じにします」という文脈で、混同しやすいものがあるので、一応注意しておきます。

実座標平面 $\mathbb{R}^2$ ($\mathbb{R}$ 上の 2 次元代数多様体)を良い感じにすると、上で述べた実射影平面 $\mathbb{P}^2(\mathbb{R})$ が出来上がります。

一方で、複素平面 $\mathbb{C}$ ($\mathbb{C}$ 上の 1 次元代数多様体)を良い感じにすると、複素射影直線 $\mathbb{P}^1(\mathbb{C})$ が出来上がります。こちらは複素平面に1つだけ無限遠点を付け加えたもので、実射影平面とは別ものです(同相でないことが証明できます)。複素解析学などで、「平面 + 無限遠点」としてこちらを先に目にする方も多いかと思いますが、混同しないよう注意しましょう。

本問題の解答

「任意の2つが交わり1個」上でも出てきましたね。

構成

問題の集合の構成は、一瞬です。次のようにすればよいです。

・適当な有限体 $K = \mathbb{F}_q$ をとる。
・射影平面 $\mathbb{P}^2(K)$ 上の点を $P_1,\ldots,P_n$ とする。
・射影平面 $\mathbb{P}^2(K)$ 上の直線を $L_1,\ldots,L_n$ とする。
・直線 $L_i$ 上の点全体を $P_{n_1},\ldots,P_{n_{q+1}}$ とするとき、紙 $i$ に整数 $n_1,\ldots,n_{q+1}$ を書き込む。

条件を満たすことの証明も簡単です。任意の2直線はちょうど1点で交わることから、2枚の紙の共通元は一意存在します。

とはいえこれをちゃんと実装するのは、理論の簡明さと比べて少し手間でした。 $\mathbb{P}^2(K) = \{[x:y:1]\mid x,y\in K\}\amalg \{[x:1:0]\mid x\in K\}\amalg\{[1:0:0]\}$ という対応を見ながら全ての直線・点の関係を取り出すため、3種に分けて扱う感じになり。いずれにせよこの構成法が思いつけば、あとはやるだけです。

有限体 $\mathbb{F}_q$ を用いると、$N = q^2+q+1$, $K=q+1$ が実現されます。

参考1

公式解説では、$q = 37$ を用いて $N = 1407$ を実現しています。$N\geqq 1000$ の範囲でより小さい $N$ をとることは可能で、$q = 32$ とした場合の $N = 1057$ が最小値を与えます(構成は上述の通り、最小性は公式解説のように $N=K(K-1)+1$ を示せばよい)。有限体 $\mathbb{F}_{32}$ クラス等を整備することで同様に実装できるはずです。$N$ が最小性の場合の構成を問う問題であれば、結構難易度が高くなりそうですね。

参考2

というか本問、ほとんどそのまま Steiner System $S(2,K,N)$ の構成を問うているので、有名問題そのまんまって感じですね。こういう問題名があったことに気づいたのはこの記事ほぼ書き終わる頃だったので、今回は触れないです…というか私あまり詳しくないです。すべての場合に対する存在判定や構成は困難で、数学背景に基づく特殊な構成がいくつか知られているって感じかな?

タイトルとURLをコピーしました