Putnam 2017 풀이 - 풀리는 것만

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}$를 만들 수 없으므로 모순.