名大 情報学研究科 数理情報学 2022年度 院試 解答例・解説

列ベクトルを並べる

線形写像の表現行列は「第 $i$ 列が $L(e_i)$」である。ここを行と列で取り違えると、後続の核や次元の計算もすべて入れ替わってしまう。

核の判定

$L:\mathbb R^5\to\mathbb R^5$ なので、核が自明であることは全単射、すなわち行列式が非零であることと同じである。行列式は因数分解した形 $a(2a-b)(b^2+c^2)$ まで出すと、実数条件では $b^2+c^2=0$ が $(b,c)=(0,0)$ と同値であることがすぐ読める。

特異点を見る

(1) は上端ではなく $0$ での発散が本質である。$e^x$ は $0$ 近傍で $1$ と同程度なので、$x^{-2}$ の発散に支配される。

指数減衰は多項式に勝つ

(2) では無限大で $\sqrt{1+x^4}$ は $x^2$ と同程度である。指数関数 $e^{-x}$ が掛かっているため、$x^2e^{-x}$ と比較すれば十分である。広義積分では、有限区間上の連続性と無限遠での挙動を分けて書くと答案が安定する。

素因数分解に落とす

条件 (i) は完全乗法性ではなく、互いに素な積に対する乗法性である。したがって $n=\prod p_i^{a_i}$ と素数冪に分けたときだけ、確実に $f(n)=\prod f(p_i^{a_i})$ と書ける。

有限個の例外をまとめる

仮定 (ii) は「大きい素数冪」だけを小さくする条件である。小さい素数冪は有限個しかないので、その寄与を一つの定数 $C$ に吸収するのが要点である。十分大きい $n$ には必ず大きい素数冪因子が含まれるため、そこから任意の小ささを得られる。

最小色数の示し方

「3色で塗れる」だけでは最小性は出ない。三角形の存在から $2$ 色以下が不可能であることを先に示し、そのうえで具体的な $3$ 彩色を与える。

偶閉路条件と二部グラフ

閉路がすべて偶数であることは、グラフが二部グラフであることと同値である。最短距離の偶奇で塗る証明では、同色辺があると最短路木の2本の道とその辺から奇閉路を作れる、という矛盾を明記するのが重要である。

Sierpinski 空間の役割

$S$ は $\{1\}$ だけが非自明な開集合である空間である。したがって $S^N$ の開集合は「有限個の座標が $1$ である」という正の情報で生成される。$0$ を指定する条件は一般には開にならない。

開写像の確認

開性では、任意の開集合を直接扱うより、積位相の基本開集合を調べるのが簡単である。$\mathbb N^N$ 側では値を等号で指定できるが、$S^N$ 側の像では「指定された値がどこかに現れる」という条件が、対応する座標の $1$ 条件に変換される。

観測量とエルミート性

有限次元量子力学では、観測量はエルミート行列で表される。$X$ はパウリ行列の一つで、固有値は $\pm1$ である。

分散の見通し

$X^2=I$ を先に使うと、分散は $1-\langle X\rangle^2$ だけで済む。期待値が $\pm1$ になる時刻では状態が $X$ の固有状態になっており、測定値に揺らぎがないため分散が $0$ になる。

擬多項式時間

$O(nb)$ は、入力値 $b$ の大きさに対する多項式時間であり、ビット長 $\log b$ に対する多項式時間ではない。この問題文では入力サイズに関する多項式時間でなくてもよいとされているため、部分和DPが自然な最速候補になる。

数えるDP

存在判定の $\lor$ を加算に置き換えると、各部分集合を「最後に使うか使わないか」で一度ずつ数えられる。配列を1次元にするときは、同じ $a_i$ を二度使わないように $s=b,b-1,\dots,a_i$ の降順で更新する。

対角化の順序

$P$ の列に固有ベクトルを並べた順序と、$D$ の対角成分の順序を一致させる必要がある。順序が違うと $A=PDP^{-1}$ にならない。

極限は最大固有値の方向

$a$ に最大固有値 $2$ の固有ベクトル成分が含まれているため、$A^n a$ では $2^n$ の項だけが支配的になる。正規化後の極限は、その固有ベクトルを長さ $1$ にしたものになる。

向きの符号

右から左へ動くため、接ベクトルの $x$ 成分は負である。この条件を落とすと $(1,y')/\sqrt{1+(y')^2}$ としてしまい、後の角度公式の符号が合わなくなる。

極座標での確認

$x=r\cos\theta,\ y=r\sin\theta$ を $\theta$ で微分すると、 $$\frac{dy}{dx}=\frac{r'\sin\theta+r\cos\theta}{r'\cos\theta-r\sin\theta}$$ である。これを接線角の公式に代入すると、三角関数の項が消えて $r'=r/\tan\tau$ が残る。

係数比較の問題

指数関数の母関数で $\sum k^m$ を取り出す標準手法である。左辺の $e^{kx}$ から $k^m/m!$ が出るため、最後に $m!$ を掛ける点を忘れない。

添字の整理

$\frac{e^{nx}-1}{x}$ の $x^q$ 係数は $n^{q+1}/(q+1)!$ である。ここで $q=m-j$ と置くと、二項係数 $$\frac{m!}{j!(m+1-j)!}=\frac1{m+1}\binom{m+1}{j}$$ が現れる。

和が区間に入るかだけを見る

サンドイッチ表現では、頂点の位置ではなく重み和だけが辺の有無を決める。具体例では、辺にしたい対の和と非辺にしたい対の和を表にして区間内外を確認するとよい。

5閉路が失敗する理由

$H_3$ の不可能性は、最小重みの頂点を一つ固定すると不等式が一方向に連鎖するために起こる。非辺は「区間の下に外れる」か「上に外れる」かのどちらかだが、最小性により一部の非辺は下に外れざるを得ず、そこから隣接頂点間の大小関係が矛盾する。

商写像の形

(1) は開な全射による商写像の基本性質である。$g^{-1}(V)$ を直接調べるのではなく、$h^{-1}(g^{-1}(V))=f^{-1}(V)$ が開であることから、$h$ の開性で戻す。

第1科目の結果との接続

$\varphi$ は $\mathbb N^N$ から $S^N$ への開な全射である。したがって $\varphi$ を通じて分解する連続な $B$ 値関数は、$S^N$ 上の連続関数に降りる。ここで $S^N\to B$ の連続関数が定数しかないことが効く。

指数関数の計算

$Y^2=I$ なので、$e^{-itY}$ は三角関数で閉じる。これはパウリ行列一般に共通する計算で、偶数次が $I$、奇数次が $Y$ にまとまる。

状態ごとの直交化と全状態の直交化

一つの状態を指定すれば、それを任意の直交状態へ送るユニタリは作れる。しかし、すべての状態に対して同じ線形ユニタリで直交化することはできない。重ね合わせ状態に対する条件が互いに矛盾するためである。

対数の底は固定

オーダー記法では対数の底は固定されていれば定数倍の違いでしかない。ただし $(\log n)^{\log n}$ は $n$ よりも大きくなるため、$O(n)$ へは落とせない。

階乗は対数を取る

$n!=2^{h(n)}$ と見るなら、示すべきことは $h(n)=\log_2(n!)=\Theta(n\log n)$ である。上界は $n^n$、下界は後半の $n/2$ 個の因子を $n/2$ で下から抑えるだけで十分である。