AoPS 링크
A1.
다음을 만족하는 최소의 집합 \(S\)에 속하지 않는 원소로는 어떤 것이 있겠는가?
- \(2 \in S\).
- \(n^2 \in S \implies n \in S\).
- \(n \in S \implies (n+5)^2 \in S\).
답은 \(1, 5k\).
나는 그냥 bound 줄여나가면서 풀었는데, 훨씬 깔끔한 풀이가 있어서 가져왔다.
\(n \in S\)에 대해서 \(n + 5 \in S\)가 자명하다.
또 2가 원소면 49가 원소고, \(54^2 = 2916\)이 \(S\)의 원소다.
이는 \(5k+1\)꼴이고, 따라서 \(2916\) 이상의 \(5k+1\) 꼴은 모두 \(S\)에 포함된다.
임의의 \(5 \not{|} x\)에 대해 \(x^{16} \equiv 1 \ (\mod 5)\)이므로, \(x^{16} > 2916\)인 \(x\)는 모두 \(S\)에 들어가야 한다.
따라서 2 이상의 수 중 5의 배수가 아닌 수는 전부 \(S\)에 들어가야 하고, \(1\)과 \(5k\)꼴의 수는 들어가지 않아도 아무런 문제가 없다.
A2.
다음의 점화식을 만족하는 함수열 \(Q_{n}\)이 모두 정수계수 다항식임을 보여라.
- \(Q_{0}(x) = 1, Q_{1}(x) = x\)
- \(Q_{n}(x) Q_{n-2}(x) = \{ Q_{n-1} (x) \}^{2} - 1\)
\(x\)에 특정 수를 집어넣으면 여러 정수 수열을 얻을 수 있는데, 합리적 의심으로부터 다음의 관계식을 유추할 수 있다.
$$ Q_{n} = xQ_{n-1} - Q_{n-2} $$
귀납으로 보이면 끝.
A3.
함숫값이 양수인 연속함수 \(f,g\)를 생각하자. \(\int_{a}^{b} f = \int_{a}^{b} g \)이지만 \(f \not\equiv g\)이다. 이 때 다음의 수열 \(\{I_{n}\}\)을 생각하자.
$$ I_{n} := \int_{a}^{b} \frac{f^{n+1}}{g^{n}} dx $$
\(I_{n}\)이 증가수열이고, \(\lim_{n\to\infty}I_{n} = \infty\)임을 보여라.
Cauchy - Schwarz 부등식으로부터 다음을 얻을 수 있다.
$$I_{n} I_{n-2} \ge I_{n-1}^{2}$$
이때 등호성립조건이 \(f = \pm g\)인데, \(f, g > 0\)이고 \(f \not\equiv g\)이므로 등호는 성립하지 않는다.
다음의 귀납을 걸 수 있다:
모든 \(n\)에 대해 \(\frac{I_{n}}{I_{n-1}} > 1 + \epsilon\)인 (\(n\)과 무관한) \(\epsilon > 0\)이 존재한다.
\(\displaystyle \frac{I_{2}}{I_{1}} = 1 + \epsilon_{0}\)인 \(\epsilon_{0} > 0\)가 존재하고, 위의 Cauchy - Schwarz부등식 결과에 의해
$$ \frac{I_{n}}{I_{n-1}} > \frac{I_{n-1}}{I_{n-2}} > \cdots > \frac{I_{2}}{I_{1}} = 1 + \epsilon_{0}. \blacksquare$$
따라서 \(I_{n+1} > I_{n} \cdot \frac{I_{n}}{I_{n-1}} > I_{0}(1+\epsilon_{0})^{n}\)이 성립하므로 수열 \(I_{n}\)은 적당한 등비수열보다 빠르게 증가하고, 따라서 무한으로 발산한다.
A5.
NacChal에 나왔다.
B3.
0 또는 1의 값을 갖는 수열 \(c_{i}\)에 대해, \(f(x) = \sum_{i=0}^{\infty} c_{i}x^{i}\)를 정의하자.
\(f(\frac{2}{3}) = \frac{3}{2}\)일 때, \(f(\frac{1}{2})\)는 무리수임을 보여라.
\(f(\frac{1}{2})\)가 유리수라고 하자.
\(f(\frac{1}{2})\)는 결국 이진수로 \(c_{0}.c_{1}c_{2}c_{3}\ldots\)를 나타낸 것이므로, 이 값이 유리수가 되기 위해서는 이 binary expansion이 순환마디를 가져야 한다.
따라서, 충분히 큰 \(i > N\)에 대해서 \(c_{i}\)는 주기 \(T\)를 가져야 한다.
이제 \(f(\frac{2}{3})\)을 생각하자.
\(i \le N\) : \(c_{i} \frac{2^{i}}{3^{i}}\)꼴.
\(i > N\) : \(c_{i} \frac{2^{i}}{3^{i} \cdot (3^{T} - 2^{T})}\)꼴.
그런데 이 수들은 전부 분모가 홀수고, 홀수 분모인 유리수를 유한 개 더한다고 \(\frac{3}{2}\)를 만들 수 없으므로 모순.