$\mathbb{C}$의 open unit disk $\mathbb{D}$에 대해, holomorphic function $f : \mathbb{D} \to \mathbb{D}$를 생각하자. Schwarz Lemma는 이러한 $f$의 성질에 대한 Lemma이고, 이는 $\mathbb{D}$의 Automorphism group을 characterize하는 데 큰 도움을 준다. Lemma (Schwarz) $f : \mb{D} \to \mb{D}$가 holomorphic이고, $f(0) = 0$을 만족한다고 하자. 다음 세 성질이 성립한다. $\abs{f(z)} \le \abs{z}$. 만약 $z_0 \neq 0$에 대해 $\abs{f(z_0)} = \abs{z_0}$가 성립한다면, $f$는 rotation. $\abs{f’(0)} \le 1$. 등호가 성립한다면 $f$는 rotation. 증명은 기초 복소해석을 공부했다면 크게 어렵지는 않다....
SEEMOUS 2019를 풀어보았다. 몇몇 문제는 풀이를 검증하기 위한 배경 지식이 부족해서 나중에 자세히 다루기로 한다. P1 $[0,1]$의 값을 갖는 무한 실수열 $\set{x_{n}}$이 다음 조건을 만족하면 $\set{x_{n}}$을 Devin sequence라고 한다. $ \lim_{n \to \infty} \frac{1}{n}\sum_{i=1}^{n}f(x_{i}) = \int_{0}^{1} f(x)dx $ 이 때, $\set{x_{n}}$이 Devin sequence가 될 필요충분조건은 $ \forall k \ge 0 \quad \lim_{n \to \infty} \frac{1}{n}\sum_{i=1}^{n}x_{i}^{k} = \frac{1}{k+1} $ 인 것임을 보여라. Solution sketch $\implies$는 자명. $\impliedby$는 Weierstrass. P2 $A_{1}, A_{2}, \cdots, A_{m} \in \mathfrak{M}_{n,n}(\mathbb{R})$에 대하여 다음을 만족하는 $\set{\varepsilon_{i}} \in \set{-1,1}^{m}$이 존재함을 보여라....
SWERC 2019 H번 문제이다. BOJ 18300번이기도 하다. ...
SWERC 2019 J번 문제이다. BOJ 18302번이기도 하다. 대회 중에는 rkm0959가 풀었다. 너무 긴 본문이 읽기 싫어서 알큼이 요약해준 문제 설명대로만 코드를 짰다가 중요한 디테일을 누락시켜서 엄청 고생했다… 간단히 말해서, inorder traversal (LDR 순회)이 주어진 수열이 나올 수 있는 binary tree의 개수를 구하는 문제이다. 단, 이 tree는 min-heap의 조건 (자식 $\ge$ 부모)를 만족해야 한다. ...
SWERC 2019 K번 문제이다. BOJ 18303번이기도 하다. rkm0959한테 문제 요약만 들어서 본문을 잘 모른다(…) Unweighted Directed graph에서 어떤 고정된 정점 $T$에 대해 $u \to T$ 간선이 있고, 이 간선을 사용하지 않으면 $u$에서 $T$로 이동할 수 없는 정점 $u$를 모두 구하는 문제이다. 정점 개수와 간선 개수는 $10^{5}$개 이하. ...