2020-01-03

Xmas Contest 2019

Xmas Contest 2019 にご参加いただいた皆様，どうもありがとうございました！

大変遅くなりましたが解説記事が準備できました．今年も相変わらずのばたばた準備をしていましたが，いつの間にか問題がいくつも分裂してすごいことに．皆様何かしら楽しめる問題を見つけていただければ幸いです．

わたしが原案を出した問題の解説はこちらです．

それ以外の問題へのコメントはこちらです．

A: 適当に隣接具合調べるプログラム書いた後は HTML でせっせと並べてました．1 時間くらい．
B: これ個人的に Xmas Contest っぽさを感じる構築でよい．解くのは google ですんなり．
F: 似て非なる問題がよくある気がするのではまりがちかもしれません．
G: きれいな出題．
H: writer 陣揃って data structure．
I: 横位置を揃えて必死に DP みたいなのを考えていました．データミス申し訳ありません (clar をご確認ください)．
L: 単語リストがわかる勢ですがちゃんとプログラム書いてちゃんとはまってました．

2020-01-03

Xmas Contest 2019 K: Set of Trees

Xmas Contest 2019

https://atcoder.jp/contests/xmascon19/tasks/xmascon19_k

問題概要

根付き木の順序を，子を降順に並べたものの辞書順として再帰的に定める．根付き木がいくつかあって， $1$ つ選んで「小さく」するという行動ができる $2$ 人ゲームを考える．初期状態が与えられるので，先手必勝か後手必勝かゲームが無限に続くかを判定せよ．

こたえ

盤面の根付き木を $T_1, \ldots, T_l$ とし， $T_i = \{\!\!\{T_{i,1}, \ldots, T_{i,k_i}\}\!\!\}$ とします．後手が勝つ条件は「任意の根付き木 $X$ について， $T_{i,1}, \ldots, T_{i,k_i}$ のうち $X$ と同型なものの個数を $a_i$ としたとき， $a_1 \operatorname{XOR} \cdots \operatorname{XOR} a_l = 0$ である」です．そうでないときは先手が勝ちます (必ず終わります)．このことを後ほど説明していきます．

実装

根付き木を整数に対応させる単射を用意すればよいです．部分木の頂点数が少ない順あるいは最大深さが小さい順などで頂点を見て，

map := 整数列から整数への連想配列
num := 0
foreach 頂点 u:
  v_1, ..., v_k := u の子
  f(v_1) >= ... >= f(v_k) となるようにソート
  if [f(v_1), ..., f(v_k)] !in map:
    map[[f(v_1), ..., f(v_k)]] := num
    num += 1
  f(u) := map[[f(v_1), ..., f(v_k)]]

というように f(u) を定めていけばよいです．この問題の入力形式なら頂点番号が大きい順でも OK です．時間計算量は，次数 $d$ の頂点で $O(d \log N)$ なので全体で $O(N \log N)$ です．

根付き木に対する適切なハッシュ関数をとってもよいです．こちらなどを参照．

順序数

順序数とそれらの演算が出てきます．ある程度既知として進めるのでちゃんとやるのは他の文献に任せます．演算の定義とかはこれで行きます：

順序数は， $0 = \{\}$ と，何かの successor であるもの $\alpha = \beta \cup \{\beta\}$ と，そうではないもの (limit) $\alpha = \sup \alpha$ に分かれる．
- $= \alpha$ ( $\beta = 0$ のとき)
- $= (\alpha + \gamma) \cup \{\alpha + \gamma\}$ ( $\beta = \gamma \cup \{\gamma\}$ のとき)
- $= \sup \{\alpha + \gamma \mid \gamma \lt \beta\}$ ( $\beta$ が limit のとき)
- $= 0$ ( $\beta = 0$ のとき)
- $= (\alpha \cdot \gamma) + \alpha$ ( $\beta = \gamma \cup \{\gamma\}$ のとき)
- $= \sup \{\alpha \cdot \gamma \mid \gamma \lt \beta\}$ ( $\beta$ が limit のとき)
- $= 1$ ( $\beta = 0$ のとき)
- $= (\alpha + \gamma) \cdot \alpha$ ( $\beta = \gamma \cup \{\gamma\}$ のとき)
- $= \sup \{\alpha^\gamma \mid \gamma \lt \beta\}$ ( $\beta$ が limit のとき)

これらの演算は非可換です．

考察

不偏ゲームなので，Grundy 数を (考えられるなら) 考えたいです．局面 $G$ の Grundy 数 $g(G)$ は， $G$ から $1$ 手で進める局面 $G'$ によっては $g(G')$ と書けないような最小の順序数です．いくつか例をやってみると ( $\{\!\!\{$ , $\}\!\!\}$ を [, ] で書いています) 次のようになります．

g([]) = 0
g([[]]) = 1
g([[], []]) = 2
g([[], [], []]) = 3
g([[[]]]) = ω

[[[]]] からは任意の非負整数に進めるので， $\{0, 1, \ldots\} = \omega$ です．

g([[[]], []]) = ω + 1

任意の自然数あるいは $\omega$ に進めるので， $\{0, 1, \ldots\} \cup \{\omega\} = \omega + 1$ です．

g([[[]], [], []]) = ω + 2
g([[[]], [], [], []]) = ω + 3
g([[[]], [[]]]) = ω・2
g([[[]], [[]], []]) = ω・2 + 1
g([[[], []]]) = ω^2
g([[[], [], []]]) = ω^3
g([[[], [], []], [[], []], [[], []], [], [], [], []]) = ω^3 + ω^2・2 + 4
g([[[[]]]]) = ω^ω

こんな感じになるので，次のことが予想できます：根付き木 $T = \{\!\!\{T_1, \ldots, T_k\}\!\!\}$ ( $T_1 \ge \cdots \ge T_k$ ) に対し $g(T) = \omega^{g(T_1)} + \cdots + \omega^{g(T_k)}$ と定めると， $T \gt T'$ ならば $g(T) \gt g(T')$ であり，また， $g(T) \gt \alpha$ ならば $g(T') = \alpha$ なる $T'$ が存在する．

前半は， $T' = \{\!\!\{T'_1, \ldots, T'_l\}\!\!\}$ ( $T'_1 \ge \cdots \ge T'_l$ ) について $T_1 = T'_1,\, \ldots,\, T_{j-1} = T'_{j-1},\, T_j \gt T'_j$ のときには $\omega^{g(T_j)} \ge \omega^{g(T'_{j'})+1} = \omega^{g(T'_{j'})} \cdot \omega \gt \omega^{g(T'_{j'})} \cdot (l - j + 1) \ge \omega^{g(T'_j)} + \cdots + \omega^{g(T'_l)}$ なことを使うとできます．後半は丁寧にやると面倒なので省略するのですが，有名事実を用いて理解することができます．

すべての順序数 $\alpha$ は $\beta_1 \ge \cdots \ge \beta_k$ を用いて $\alpha = \omega^{\beta_1} + \cdots + \omega^{\beta_k}$ という形で一意に書けます．これは Cantor 標準形と呼ばれています． $\alpha \lt \omega^{\omega^{\omega^{\cdot^{\cdot^{\cdot}}}}}$ ならば $\alpha \gt \beta_j$ なので，再帰的に展開していくことでそのような順序数がちょうど根付き木に対応していて，順序数としての順序がこの問題で定めた順序と一致することがわかります．つまりこの問題は， $\omega^{\omega^{\omega^{\cdot^{\cdot^{\cdot}}}}}$ 未満の順序数を根付き木の形で見せていただけなのでした．

順序数は整列集合なので，何をどうやってもゲームが無限に続くことはありません．よって Sprague–Grundy の定理が適用できて，盤面に根付き木 $T_1, \ldots, T_l$ が並んでいるときの Grundy 数は $g(T_1) \operatorname{XOR} \cdots \operatorname{XOR} g(T_l)$ となります．あとは XOR をどう計算するかだけですが， $\omega = 2^\omega$ なので $g(T_i) = 2^{\omega \cdot g(T_{k_1})} + \cdots + 2^{\omega \cdot g(T_{k_i})}$ となり， $\alpha \gt \beta \implies \omega \cdot \alpha \ge \omega \cdot \beta + \omega$ を用いると，最初に述べたように同型なものたちごとに数えればよいことがわかります．

統計情報

正解者：TSG さん (3:03:45)，kimiyuki さん (3:38:23)

Grundy 数に無限順序数が出てくる問題，ごくごく稀にある気がしますが，なかなかコンテストの問題にしづらいんですよね．Cantor 標準形が根付き木に見える→解法は同型判定だけでいい，というのが面白かったので出題してみました．

2020-01-03

Xmas Contest 2019 J: Sub-Post Correspondence Problem

Xmas Contest 2019

https://atcoder.jp/contests/xmascon19/tasks/xmascon19_j

問題概要

文字列 $A_1, B_1, \ldots, A_N, B_N$ が与えられるので，ある $i_1, \ldots, i_k$ ( $k \gt 0$ ) に対して $B_{i_1} \cdots B_{i_k}$ が $A_{i_1} \cdots A_{i_k}$ の連続とは限らない部分列となるようにできるか判定せよ (一応，同じ添え字は $2019^{2019}$ 回まで)．

解法

カード $1$ 枚での解 ( $k = 1$ ) があれば YES でなければ NO です．なぜなら， $b b'$ が $a a'$ の部分列ならば， $b$ が $a$ の部分列であるか $b'$ が $a'$ の部分列であるかだからです ( $a$ と $a'$ の境界に対応する場所は $b$ と $b'$ の高々一方にしか入ってこないので)．

$k = 1$ のときの判定は， $B_i$ の文字を $1$ 文字ずつ， $A_i$ の中に貪欲にとっていけば線型時間でできます．

統計情報

正解者：siotouto さん (0:13:54) はじめ 95 チーム

ギャグ枠です． $N \le 16$ はフェイクです．

Post の対応問題は決定不能な問題の中でもパズルっぽい見た目ということで人気があります (?)．問題設定を少し変えた亜種は結構研究されているらしく，決定不能と決定可能の間が見えてくるのが面白いですね．

2020-01-03

Xmas Contest 2019 E: Sum of f(n) 解説

Xmas Contest 2019

https://atcoder.jp/contests/xmascon19/tasks/xmascon19_e

問題概要

$n$ の素因数の個数 (重複込み) を $f(n)$ とする． $N$ が与えられるので $\sum_{n=1}^N f(n)$ を求めよ．

解法 1 (?)

答えを手元で全部計算して，適当な間隔で区切って埋め込みます．狭い区間については区間篩のアルゴリズムで $f$ を効率的に計算できる (素数 $p$ で篩うときに $p$ で割り切れる回数だけ $1$ を足す) ので，これで正解することができます．

終わる確信があったら，手元で D 問題と一緒に計算するとよいと思います！　D 問題より桁数が多かったり時間制限が短かったりでちょっとだけ大変かもしれません．

解法 2

素数 $p$ の影響が何回足されるかを考えると，各 $p$ について， $N$ 以下の $p$ の倍数の個数， $p^2$ の倍数の個数， $p^3$ の倍数の個数，……を足していけば答えになります． $p^2$ 以降の倍数が現れるのは $p \le \sqrt{N}$ なもののみなので，それらについてはひとつずつ処理できます．これで，あとは $\sum_{p:素数} \lfloor\frac{N}{p}\rfloor$ を求めればよくなりました．

$\lfloor\frac{N}{p}\rfloor$ の値は $2 \sqrt{N}$ 通りくらいしかないので，同じ値になる部分をまとめて計算したいです． $\lfloor\frac{N}{p}\rfloor = k \iff \lfloor\frac{N}{k+1}\rfloor \lt p \le \lfloor\frac{N}{k}\rfloor$ なので，「 $\lfloor\frac{N}{k}\rfloor$ 以下の素数の個数」という形のものが数えられれば， $\sum_p \lfloor\frac{N}{p}\rfloor = \sum_k (\pi(\lfloor\frac{N}{k}\rfloor) - \pi(\lfloor\frac{N}{k+1}\rfloor)) k$ と計算できます ( $\pi(n)$ は $n$ 以下の素数の個数)．

これは，賢い DP をするとできます．素数を小さい順に $p_1, p_2, \ldots$ とします． $g(i, n)$ を， $n$ 以下の正の整数であって $p_1, \ldots, p_i$ のいずれでも割り切れないものの個数とおきます． $g(i, n) = g(i - 1, n) - g(i - 1, \lfloor\frac{n}{p_i}\rfloor)$ という漸化式が成り立ちます． $\pi(n) = g(\pi(\sqrt{n}), n) - 1$ なので， $\pi(\lfloor\frac{N}{k}\rfloor)$ の形のものを計算するのに必要な $g(i, n)$ はやはり $n = \lfloor\frac{N}{k}\rfloor$ の形をしています．

このままだとまだ遅いので高速化します． $g(i - 1, n)$ から $g(i, n)$ への変化に注目すると， $n \lt p_i$ では変わらず， $p_i \le n \lt p_i^2$ では $1$ 減るだけになっています．ということをふまえて $g'(i, n) = g(i, n) + \min\{i, \pi(n)\}$ とおき直すと， $n \lt p_i^2$ では $g'(i, n) = g'(i - 1, n)$ ， $n \ge p_i^2$ では $g'(i, n) = g'(i - 1, n) - g'(i - 1, \lfloor\frac{n}{p_i}\rfloor) + i$ となります．これで DP 配列を使い回して $n \ge p_i^2$ の部分のみ更新すればよいことになります．なお， $g'(i, n)$ は $n$ 以下の正の整数に対して Eratosthenes の篩で $p_1, \ldots, p_i$ を処理したときに残るものの個数になっています．

時間計算量を見積もると，更新箇所の個数が

$1 \le i \le \pi(N^{1/4}) \sim N^{1/4} / \log N$ についてそれぞれ $O(N^{1/2})$ 個
$\pi(N^{1/4}) \lt i \le \pi(N^{1/2})$ について合計で $O\left(\frac{1}{\log N} \int_{N^{1/4}}^{N^{1/2}} \frac{N}{x^2} dx\right) = O(N^{3/4} / \log N)$ 個

となり (素数の密度についての定理を用いました) 全体で $O(N^{3/4} / \log N)$ 時間となります．これで $100$ 点がとれます．

なお，素数の個数 $\pi$ の計算については，より高速なアルゴリズムも知られています．

統計情報

45 点：1 チーム

100 点：team_2019 さん (29:26) はじめ 7 チーム

実は冒頭のストーリーは結構実話に近く，D 問題を提案しようとしたら書き間違えて，わたしが気づかないまま snuke さんが解いてくれて答えの大きさを見て気づいてわたしも解きました．高速素数カウントは初めて実装したので勉強になりました！

2020-01-03

Xmas Contest 2019 D: Sum of (-1)^f(n) 解説

Xmas Contest 2019

https://atcoder.jp/contests/xmascon19/tasks/xmascon19_d

問題概要

$n$ の素因数の個数 (重複込み) を $f(n)$ とする． $N$ が与えられるので $\sum_{n=1}^N (-1)^{f(n)}$ を求めよ．

解法 1 (?)

答えを手元で全部計算して，適当な間隔で区切って埋め込みます．狭い区間については区間篩のアルゴリズムで $f$ を効率的に計算できる (素数 $p$ で篩うときに $p$ で割り切れる回数だけ $-1$ 倍する) ので，これで正解することができます．

$45$ 点は割と易しめだと思います． $100$ 点は結構な計算資源を使うかなと思っていたので，解けちゃってもいいかなという感じでした．何なら昔の問題にリンクを貼っていて，パソコンを使いましょうというのを伝えていた感じだったかもしれません．

解法 2

$\lambda(n) = (-1)^{f(n)}$ とおきます．突然ですが，正の整数 $n$ に対し， $\sum_{d|n} \lambda(d)$ は $n$ が平方数のとき $1$ ，そうでないとき $0$ です．理由は例えば $n = 2^3 \cdot 3^4$ なら

    3^0 3^1 3^2 3^3
2^0  +1  -1  +1  -1
2^1  -1  +1  -1  +1
2^2  +1  -1  +1  -1

みたいな感じで多次元の格子点を市松模様で塗るのを考えてみるとわかります． $\lambda$ は Liouville 関数として知られていて，Wikipedia にもこの式は載っています．もうちょっと突然でない導き方については後述します．

さて， $L(N) = \sum_{n=1}^N \lambda(n)$ を求めたいわけですが， $\sum_{d|n}$ みたいなのを見たら累積和をとるという知る人ぞ知る典型テクニックがありまして， $\sum_{n=1}^m \sum_{d|n} \lambda(d) = \sum_{k=1}^m L(\lfloor\frac{m}{k}\rfloor)$ となります ( $\frac{n}{d}$ を先に固定して和をとるとわかります)．一方 $n$ が平方数なら $1$ というのを $1 \le n \le m$ で和をとると $\lfloor\sqrt{m}\rfloor$ なので， $\sum_{k=1}^m L(\lfloor\frac{m}{k}\rfloor) = \lfloor\sqrt{m}\rfloor$ が得られました．これを $L(m) = \lfloor\sqrt{m}\rfloor - \sum_{k=2}^m L(\lfloor\frac{m}{k}\rfloor)$ と書くと $L$ の漸化式を得たことになります．

この形の漸化式をどうするかも知る人ぞ知る典型テクニックなのですが， $L(N)$ を計算するのに必要な $L$ の値は $L(\lfloor\frac{N}{k}\rfloor)$ の形だけになっていて ( $\left\lfloor\frac{\lfloor\frac{N}{k}\rfloor}{k'}\right\rfloor = \lfloor\frac{N}{k k'}\rfloor$ に注意)，異なる $\lfloor\frac{N}{k}\rfloor$ の値は $2 \sqrt{N}$ 通りくらいしかありません． $\sum_{k=2}^m L(\lfloor\frac{m}{k}\rfloor)$ の計算は同じ $\lfloor\frac{m}{k}\rfloor$ の値のものをまとめることで $O(\sqrt{m})$ 時間でできるので，

$1 \le m \le \lfloor\sqrt{N}\rfloor$ について $L(m)$ を求めるのに $O(\sqrt{\sqrt{N}}) \times \sqrt{N} = O(N^{3/4})$ 時間
$1 \le k \le \lfloor\sqrt{N}\rfloor$ について $L(\lfloor\frac{N}{k}\rfloor)$ を求めるのに $O\left(\int_{k=1}^{\sqrt{N}} \sqrt{\frac{N}{k}}\right) = O(N^{3/4})$ 時間

となり，全体で $O(N^{3/4})$ 時間の解法が得られました．実装によりますが $45$ 点の想定です．メモ化再帰で連想配列の類を使うと実行時間がちょっと厳しいかもしれません (配列 $2$ つでできます)．

さらなる高速化ですが，小さい方の答えを定義に戻って計算します．Eratosthenes の篩を用いると $1 \le m \le M$ について $L(m)$ を求めるのが $O(M \log \log M)$ 時間でできます．大きい方は $k \le \frac{N}{M}$ まででよくなって $O(N^{1/2} M^{-1/2})$ 時間になるので， $M = (N / \log \log N)^{2/3}$ くらいにとるのがよく， $O(N^{2/3} (\log \log N)^{1/3})$ 時間解法が得られました (高速な篩を用いれば $O(N^{2/3})$ 時間)．これで $100$ 点です．

Dirichlet 級数

最初に天下った部分の話です． $\lambda$ は乗法的関数なので，(形式的) Dirichlet 級数を考えてみたくなりますね！　Euler 積の形で計算すると， $\sum_{n=1}^\infty \lambda(n) n^{-s} = \prod_{p:素数} (1 - p^{-s} + p^{-2s} - \cdots) = \prod_p \frac{1}{1 + p^{-s}} = \prod_p \frac{1 - p^{-s}}{1 - p^{-2s}} = \frac{\zeta(2 s)}{\zeta(s)}$ となり Riemann の $\zeta$ 関数で表すことができました． $\zeta(s)$ をかけるという操作は $\sum_{d|n}$ をとることに対応していて， $\zeta(2 s)$ は平方数だけ $1$ な級数を表しているので，先ほど使った式が示せました．この辺の話は，例えば maspy さんの HP で丁寧に解説されています．

さっきやった方法は Liouville 関数に限った話ではなく，累積和が簡単に書けている数論的関数を $\zeta(s)$ で割ったもの (つまり，Möbius 変換したもの) の累積和を高速に求める一般的な手法になっています．なので，Möbius 関数 $\mu$ や Euler の $\varphi$ 関数なんかの累積和も同様に高速に求まります (それらのほうがたぶん有名なので， $\mu$ の累積和に帰着させて解くという方針も見られました)．

統計情報

45 点：3 チーム

100 点：chocorusk さん (1:00:49) はじめ 6 チーム

Project Euler の回し者ですか？　はい……．数学寄りの問題が集まっているサイトですが，この手の sublinear algorithm の数論問題もたくさんあります．解法共有は正解者のみという文化なので，皆さんもぜひ頭 and/or パソコンを駆使して問題を解いていきましょう．

テストデータには，制約内で答えが最大になる $L(906\,316\,571) = 829$ が (無意味に) 入っています．この関数の漸近的な振る舞いは，かなり謎に満ちてますね……．

2020-01-03

Xmas Contest 2019 C: Sokoban 解説

Xmas Contest 2019

https://atcoder.jp/contests/xmascon19/tasks/xmascon19_c

問題概要

倉庫番の盤面が与えられるので (入力公開)，解くのに必要な最小手数を求めよ．

sample, 01, 02

小さいので，手で遊んで解けます．しかし，解くだけなら簡単ですが最小手数は非自明だったりします．コンテストでは，見つかった解から $1$ 手ずつ減らして提出してみるのもありだと思います．

確実なプログラミング解ももちろん可能で，盤面の状態数を考えてみると，たとえば 02 ではうさぎの位置は $33$ 通り，そのそれぞれに対し箱の位置が $\binom{32}{4}$ 通り，と抑えられて，特に枝刈り等せずとも BFS で最小手数を求めることができます．

01 は，解くだけなら本当に簡単なのを適当に作ってみました． $23$ 手の解がとても見えやすいと思いますが，うまいことやると減って不思議です．

02 は，左上の空間を利用できる問題を作ってみました (パズルとしての問題ならよくありそう)．左上に何度も行くのをやめるのが大事でそれをすると $69$ 手の解が見えやすいと思うのですが，やっぱりうまいことやると減って，よくわかりません……．ちなみに最後に片づく荷物が左上か右下しかありえないので，奇数手であることがわかって提出を少し節約できたりします．

03

荷物が壁の直角の隅に置かれてしまうと，そこがゴールでない限り詰んでしまいます．このことから，入力にたくさん現れる

###########
####....###
...#.##....
##.@..#####
###...#####
###########

という部分が一方通行の役割を果たすことがわかります (上の図の向きでは左から右へのみ，一定の手数で，荷物の位置を変えずに通れます)．入力の右下の荷物を片付けに行けばよいので， $3 \times 3$ の部屋のようなものを頂点とした最短路問題として解くことができます．

04

$11$ 列ごとに

###########
########...
##...##.@..
#.@..##.#.#
..#.###.#..
#.#.@.@..##
#..#...#.##
##.#.....##
#.@####.#..
#....##..@.
#..#...##..
###..#.##@.
##.@##.....
##....###..
##..#.#####
#####.#####
...........
###########

というパターンが繰り返される構造になっています．左から右へ抜けたいのですが，そのためには右下を回って箱を一度ずらす必要があり，そうすると一旦下から出て一番左まで戻らないといけません．よって，右から $1$ 番目のブロックを左から右へ抜けるためには $2$ 回来なければならない，そのそれぞれに対して右から $2$ 番目のブロックを左から右へ抜けるために $2$ 回ずつ， $4$ 回来なければならない，そのそれぞれに対して……，というようにして，右から $i$ 番目のブロックに $2^i$ 回来なければなりません．これに，各ブロックでかかる手数 (手で遊んで数えるのがよいと思います) を掛けて足すことで答えが求まります．

この入力は，盤のサイズに対して指数手数かかる例になっています．手でクリアしようとすると絶望を感じられると思います．

05

03 で使われていた一方通行のパターンが荷物が片付いていない状態で登場しています．左上の部分は最後に訪れないといけないので，グラフの問題で言い換えると「すべての辺を少なくとも $1$ 回通ってスタート位置に戻ってくるための最小コスト」を求める問題になっています．

これは，(有向) 中国人郵便配達問題として知られた問題です．辺を通る回数分増やして考えると，すべての辺をちょうど $1$ 回ずつ通ってスタート位置に戻って来られる条件は (グラフが強連結かつ) すべての頂点の出次数と入次数が等しいことです (Euler circuit)．ということで，最初のグラフに辺を足して出次数と入次数を等しくする問題と言い換えられますが，その最小コストは入次数が余っている点から出次数が余っている辺へ流す最小費用流問題を解くことで求めることができます．

omake

html にのみ入っているこのデータ，パズルガチ勢であるところのすぬけさんが作りました．最短手数の証明が怪しくて出題を見送ったのですが，参加者の方によってすごく縮められていて，こわいです．わたしは，解けません．

統計情報

得点 01 02 03 04 05 人数
 100  o  o  o  o  o    1
  60  o  o  o  o       7
  43  o  o     o       8
  35  o  o  o          6
  18  o  o            39
  11     o             5
   7  o               53

正解者：DEGwer さん (2:39:03)

倉庫番の盤面が与えられたとき解の有無を判定する問題は PSPACE 完全であることが知られています．倉庫番のパーツを作って Turing machine をエミュレートするという証明です．この論文の見どころは，平面交差です．

そんなわけで実質任意の決定可能問題は倉庫番で表せるのですが，自然なのはグラフの問題で，その中でコンテストであまり頻繁には見かけない (気がする) 郵便配達が思いついたので出してみたくてこのような形になったのでした．

2019-05-31

無限直積の双対加群こわい

代数

概要・参考文献

$\operatorname{Hom}_\mathbb{Z} (\prod_{i=0}^{\infty} \mathbb{Z}, \mathbb{Z}) = \bigoplus_{i=0}^{\infty} \mathbb{Z}$ を示します．

https://mathoverflow.net/q/10239 ←これを読み解いたよというような話です．

何がすごいの？

$\operatorname{Hom}_\mathbb{Z} (\bigoplus_{i=0}^{\infty} \mathbb{Z}, \mathbb{Z}) = \prod_{i=0}^{\infty} \mathbb{Z}$ は簡単です．直和の普遍性と，同一視 $\operatorname{Hom}_\mathbb{Z} (\mathbb{Z}, \mathbb{Z}) = \mathbb{Z}$ ですね．こっちは $\mathbb{Z}$ を任意の単位的可換環にしても成り立ちます．一方，直積からの準同型というのは，なんだかよくわからないものです．

また， $\mathbb{Z}$ じゃなくて体 $K$ だったら様子が異なってきます．無限次元線型空間の双対をとると次元が真に大きくなることが知られていて， $\dim_K \bigoplus_{i=0}^{\infty} K \lt \dim_K \prod_{i=0}^{\infty} K \lt \dim_K \operatorname{Hom}_K (\prod_{i=0}^{\infty} K, K)$ です．

体だったら基底がとれるので双対をとれば単に大きくなるところが， $\mathbb{Z}$ だと直積からの準同型というのが意外ときつい制約で，小さくなってなぜかちょうど直和くらいになってしまう．そんな不思議な定理です．

証明の流れ

準同型 $\Phi\colon \operatorname{Hom}_\mathbb{Z} (\prod_{i=0}^{\infty} \mathbb{Z}, \mathbb{Z}) \to \prod_{i=0}^{\infty} \mathbb{Z}$ を $f \mapsto (f(e_i))$ ( $e_i$ は第 $i$ 成分だけ $1$ で他が $0$ のやつ) で定めたとき，

$\Phi$ が単射であること
$\operatorname{Im} \Phi = \bigoplus_{i=0}^{\infty} \mathbb{Z}$ であること

を示します．この 1. は当たり前と思いきやそうではなくて，各 $i \in \mathbb{Z}_{\ge 0}$ に対して $f(e_i)$ を決めたからといって $f((x_i)_i) = \sum_{i=0}^\infty x_i f(e_i)$ とはできない (有限和になってない！) のが罠です．直積の厄介なところですね．

1. 単射性

$\Phi(f) = 0$ ，つまり任意の $i \in \mathbb{Z}_{\ge 0}$ に対して $f(e_i) = 0$ であることを仮定して， $f = 0$ を示す．

任意の $x = (x_i)_i \in \prod_{i=0}^{\infty} \mathbb{Z}$ をとる．各 $i \in \mathbb{Z}_{\ge 0}$ について， $2^i$ と $3^i$ は互いに素なので， $x_i = 2^i a_i + 3^i b_i$ となる $a_i, b_i \in \mathbb{Z}$ がとれる．

任意の $n \in \mathbb{Z}_{\ge 0}$ に対して， $(2^i a_i)_i = \sum_{i=0}^{n-1} 2^i a_i e_i + 2^n (\underbrace{0, \ldots, 0}_n, 2^0 a_n, 2^1 a_{n+1}, \ldots)$ なので，仮定より $f((2^i a_i)_i) = 2^n f(\underbrace{0, \ldots, 0}_n, 2^0 a_n, 2^1 a_{n+1}, \ldots) \in 2^n \mathbb{Z}$ ．よって $f((2^i a_i)_i) = 0$ ．

同様に $f((3^i b_i)_i) = 0$ なので， $f(x) = f((2^i a_i)_i) + f((3^i b_i)_i) = 0$ ．以上で $f = 0$ が示せた．

これは， $\mathbb{Z}$ の「PID だが局所環ではない」という性質を使っています．体でない局所環で反例が作れるかは，よくわかりません……．

2. 像が直和に入ること

任意に $f \in \operatorname{Hom}_\mathbb{Z} (\prod_{i=0}^{\infty} \mathbb{Z}, \mathbb{Z})$ をとったとき， $\Phi(f) \in \bigoplus_{i=0}^{\infty} \mathbb{Z}$ ，つまり $i \in \mathbb{Z}_{\ge 0}$ のうち有限個を除いて $f(e_i) = 0$ となることを示す．

$x = (x_i)_i \in \prod_{i=0}^{\infty} \mathbb{Z}$ を， $0 \lt x_0 \lt x_1 \lt \cdots$ かつ $x_0 \mid x_1 \mid \cdots$ (整除) かつ任意の $n \in \mathbb{Z}_{\ge 0}$ で $\sum_{i=0}^{n-1} x_i \lvert f(e_i) \rvert \lt \frac12 x_n$ が成り立つようにとれる (順番に，十分大きい倍数をとっていけばよい)．

任意の $n \in \mathbb{Z}_{\ge 0}$ について， $x = \sum_{i=0}^{n-1} x_i e_i + x_n (\underbrace{0, \ldots, 0}_n, \frac{x_n}{x_n}, \frac{x_{n+1}}{x_n}, \ldots)$ なので， $y_n = (\underbrace{0, \ldots, 0}_n, \frac{x_n}{x_n}, \frac{x_{n+1}}{x_n}, \ldots) \,(\in \prod_{i=0}^{\infty} \mathbb{Z})$ とおくと $f(x) = \sum_{i=0}^{n-1} x_i f(e_i) + x_n f(y_n)$ となる．すると三角不等式と $x_i$ のとり方より $x_n \lvert f(y_n) \rvert \lt \lvert f(x) \rvert + \frac12 x_n$ が成り立つ．ここで，十分大きい $n$ では $\lvert f(x) \rvert \lt \frac12 x_n$ なので $f(y_n) = 0$ である．

$x_n y_n = x_n e_n + x_{n+1} y_{n+1}$ なので，十分大きい $n$ では $f(e_n) = f(y_n) - \frac{x_{n+1}}{x_n} f(y_{n+1}) = 0$ となり，示すべきことが得られた．

お気持ちとしては，「めっちゃ増えてくような無限列も有限値に送らないといけないので，それっぽい列をとれば後ろの方の影響があってはならないことが言える」みたいな感じです．

mathoverflow にリンクが貼られている http://www-users.mat.umk.pl/~gregbob/seminars/2008.11.07b.pdf では不等式評価を用いずに，こちらも局所環でない PID について示そうとしているのですが，PDF でいう $q \not\mid \varphi(f)$ のところが間違っています ( $\varphi(f^{\le 0})$ が $f_0$ ではなく $f_0 \varphi(e_0)$ なので)． $\mathbb{Z}$ の場合なら $p$ とか $q$ とか好きに決められるので簡単に直せるのですが，一般にはダメそうです．上手く修正できる気もしますがあまり考えていません．

無限直和とか無限直積とかはやっぱりこわいですが，好きな定理上位にランクインしました．

間違いを見つけた方は是非教えてください．