2023 KMO 고등부 2차 풀이

1. 양의 실수 수열 $\{ a_n \} $이 다음과 같이 정의된다.

$$ a_0=1, a_1=3, a_{n+2}=\frac{a_{n+1}^2+2}{a_n}(n\geq 0)$$

모든 음이 아닌 정수 $n$에 대해 $a_n$은 양의 정수임을 보여라.

 

풀이. 작은 항들을 계산해보면 $a_{n+2}=4a_{n+1}-a_n$임을 추측해볼 수 있습니다. 이런 선형 점화식으로 수열 $\{ a_n \}$을 정의했을 때 조건식을 만족함을 보이면 충분합니다. 이는 다음과 같은 식 정리로 쉽게 알아낼 수 있습니다. $\blacksquare$

$$\frac{a_{n+2}+a_n}{a_{n+1}}=4=\frac{a_{n+3}+a_{n+1}}{a_{n+2}}$$

 

2. 집합 $A_0, A_1, \cdots, A_{2023}$이 다음 두 조건을 모두 만족한다.

• $A_0=\{ 3 \}$
• $n=1,2,\cdots,2023$에 대하여 $A_n=\{ x+2 | x\in A_{n-1} \} \cup \left\{ \displaystyle\frac{x(x+1)}{2} | x \in A_{n-1} \right\}$이다.

집합 $A_{2023}$의 원소의 개수를 구하여라.

 

답. $\boxed{2^{2023}}$

풀이. 기본적으로 $A_n$은 $A_{n-1}$의 원소들에 $f(x)=x+2$를 취하거나 $g(x)=\displaystyle\frac{x(x+1)}{2}$를 취한 원소들을 모아놓은 집합입니다. 몇몇 집합들을 계산해보면, 이렇게 계산된 원소들이 모두 다르다는 것을 관찰할 수 있습니다. 따라서 임의의 $n$에 대해 $|A_n|=2^n$이 됨을 보이면 될 것 같습니다.

 

이를 귀납적으로 증명해보도록 하겠습니다. 정확히는, $3$이라는 원소에서 시작해 $f$ 또는 $g$를 $n$번 합성했을 때 나올 수 있는 $2^n$개의 수가 전부 다름을 보이려합니다. $n-1$일 때 이것이 성립한다고 가정하고, $n$일 때 반례가 존재한다고 가정합시다. 만약 두 수가 $n$번째에 같은 함수가 합성되었다면, 각 함수가 주어진 자연수 범위에서 단사이므로 그 전까지의 값 또한 같았어야 합니다. 이는 귀납 가정에 의해 모순이므로, $n$번째에 합성된 함수는 서로 달라야 합니다. $n$번째에 $f$가 합성된 수를 $A$, $g$가 합성된 수를 $B$라 합시다. 이때 $B=g(b)$라 표현할 수 있으며, $b$는 $3$에서 $f$ 또는 $g$를 $n-1$번 합성한 결과값입니다. 전부 $f$를 택할 때가 가장 최소이며, 이때 $b\geq 3+2(n-1)=2n+1$입니다.

 

$A$에서 $n$번째 함수부터 거꾸로 살펴볼 때, $f$가 정확히 $k$개 만큼 연속하여 등장한다고 가정합시다. (만약 전부 $f$였다면, $k=n$입니다) 이때 $1\leq k\leq n$이고, $k+1$번째 합성된 함수는 $g$가 될 것입니다. ($k=n$일 경우 $g(2)=3$이라는 사실을 이용하면 똑같은 논의를 할 수 있습니다) 그 직전까지의 계산값을 $a$라 하면, $A=(f^k \circ g)(a)$가 됩니다.

 

 $A=B$라는 식을 정리하면, $g(b)=f^k (g(a))$, $\displaystyle\frac{b(b+1)}{2}=\frac{a(a+1)}{2}+2k$가 됩니다.

$\displaystyle\frac{b(b+1)}{2}>\frac{a(a+1)}{2}$이므로 $a<b$, 즉 $a\leq b-1$입니다. 이를 대입하면

$\displaystyle\frac{b(b+1)}{2}=\frac{a(a+1)}{2}+2k\leq \frac{b(b-1)}{2}+2k$이므로 $b\leq 2k$임을 알 수 있습니다.

그러나 $b\geq 2n+1 > 2n \geq 2k$이며, 이는 모순입니다.

 

따라서 귀납적으로 $2^n$개의 수들이 모두 다르다는 사실을 증명할 수 있습니다. $\blacksquare$

 

3. 주어진 양의 정수 $n(\geq 2)$에 대하여, 다음 두 조건을 모두 만족하는 $n$차 정수계수 다항식 $P(x)$가 존재하는 가장 큰 양의 정수 $A$를 구하여라.

• $P(1),P(2),\cdots,P(A)$가 모두 $A$의 배수이다.
• $P(0)=0$이고 $P(x)$의 $1$차 항의 계수가 $1$이다. 즉, $P(x)$는 다음과 같은 꼴이다.

$$P(x)=c_n x^n + c_{n-1} x^{n-1} +\cdots+c_2 x^2 +x (c_n \ne 0)$$

 

답. $\boxed{\displaystyle\prod_{p\leq n}p}$

풀이. 우선, 차수가 $n$ 이하인 다항식 $P$가 존재한다는 조건으로 바꾸어도 무관합니다.($c_n$에 $A$를 더해주면 그만입니다) 만약 $A$가 어떤 소수의 제곱 $r^2$을 약수로 가지면, $P(r)\equiv r \:(\text{mod}\: r^2)$이므로 $r^2$의 배수가 아니며, $A$의 배수 또한 아니게 됩니다. 따라서 $A$는 우선 square-free여야 합니다.

 

$A$의 소인수 $q$에 대해, $P(0), P(1), \cdots, P(q-1)$은 모두 $A$의 배수로 당연히 $q$의 배수입니다. 따라서 $\mathbb{Z}_q$ Field에서 $P$는 $x^q-x$으로 나누어져야 하며, 이는 $n\geq q$임을 의미합니다. 따라서 $A$의 모든 소인수는 $n$보다 작거나 같으며, 즉 $A \leq \displaystyle\prod_{p\leq n}p$입니다.

 

실례는 $n$이하의 최대 소수 $p$에 대해, $P(x)=x(1+x)(1+2x)\cdots(1+(p-1)x)$로 잡으면 됩니다. $\blacksquare$

 

4. 오각형 $ABCDE$가 원 $\Omega$에 내접한다. 점 $F$는 두 선분 $AD$와 $CE$의 교점이고, 점 $P(\ne E,F)$는 선분 $EF$ 위의 점이다. 삼각형 $AFP$의 외접원이 원 $\Omega$, 선분 $AC$와 각각 점 $Q(\ne A), R(\ne A)$에서 만난다. 두 선분 $AD$와 $BQ$가 점 $S$에서 만나고, 삼각형 $DES$의 외접원이 직선 $BQ$, $BD$와 각각 점 $T(\ne S), U(\ne D)$에서 만난다. 네 점 $F,P,T,S$가 한 원 위에 있으면 네 점 $P,T,R,U$도 한 원 위에 있음을 보여라.

 

풀이.

 

5. 양의 정수 $n$에 대하여 $f(n)$을 $n$ 이하의 양의 정수 중 $n$과 서로소인 것의 개수, $g(n)$을 $n$의 양의 약수들의 합이라 하자. 예를 들어, $n=10$이면 $n$과 서로소인 $10$ 이하의 양의 정수는 $1,3,7,9$이므로 $f(10)=4$이고 $10$의 양의 약수는 $1,2,5,10$이므로 $g(n)=1+2+5+10=18$이다. 다음 등식을 만족하는 양의 정수 $n$을 모두 구하여라.

$$f(n)+g(n)-2n=8$$

 

답. $\boxed{12}$, $\boxed{343}$

풀이. 편의상 $f(n)=\phi (n)$, $g(n)=\sigma (n)$으로 쓰겠습니다. 양변을 $n$으로 나누면 다음과 같은 식을 얻을 수 있습니다.

$$\prod_{p|n}(1-\frac{1}{p}) + \sum_{d|n}\frac{1}{d} - 2 = \frac{8}{n}$$

$n$의 소인수를 $p_1,\cdots,p_k$라 하면 다음과 같이 표현할 수도 있습니다.

$$\prod_{1\leq i_1<\cdots<i_t\leq k}(-1)^t \frac{1}{p_{i_1}\cdots p_{i_t}} + \sum_{d|n}\frac{1}{d} - 2 = \frac{8}{n}$$

 

좌변을 자세히 분석해보면 다음과 같습니다. 먼저 곱 항과 합 항에서 $1$이 하나씩 나오며, 이는 $2$와 소거됩니다. 두 번째로 곱 항에서 홀수 개의 소수를 곱한 항은 합 항에서 소거됩니다.(소수들의 곱 또한 $n$의 약수입니다) 곱 항에서 짝수 개의 소수를 곱한 항은 합 항과 합쳐져 두 배가 되고, 나머지는 그대로 나타납니다. 따라서 대부분의 경우 좌변이 우변에 비해 클 것을 예상할 수 있습니다.

 

Case 1. $n$의 소인수가 $3$개 이상($p,q,r$):

좌변은 $\displaystyle\frac{2}{pq}+\frac{2}{qr}+\frac{2}{rp}$ 이상입니다. 그런데 $\displaystyle\frac{2}{pq}+\frac{2}{qr}+\frac{2}{rp}\geq \frac{2(p+q+r)}{pqr}\geq \frac{2(2+3+5)}{n}>\frac{8}{n}$, 모순입니다.

 

Case 2. $n$의 소인수가 $2$개일 때($p,q$):

$n=pq$일 때는 자명히 모순입니다. 일반성을 잃지 않고 $p$의 지수가 $2$ 이상이라 가정하면, 

$$\frac{8}{n}\geq \frac{2}{pq}+\frac{1}{p^2}+\frac{1}{p^2q}=\frac{2p+q+1}{p^2q}\geq\frac{2\times2+3+1}{n}=\frac{8}{n}$$

이므로 $p=2,q=3,n=p^2q=12$이며, 실제로 성립합니다.

 

Case 3. $n$의 소인수가 $1$개일 때($p$):

$n=p^k$으로 두고 식을 정리해보면 $k\geq 3$이며 $p^{k-2}+\cdots+p=7$이 나옵니다. 따라서 $p=7,n=7^3=343$이며 실제로 성립합니다. $\blacksquare$

 

6. 예각삼각형 $ABC(\overline{AB}<\overline{AC})$의 외접원을 $\Omega$, 외심을 $O$라 하자. 직선 $AO$가 변 $BC$와 만나는 점을 $D$, 원 $\Omega$와 다시 만나는 점을 $E(\ne A)$라 하자. 점 $D$를 지나고 $AB$에 수직인 직선이 직선 $AC$와 만나는 점을 $P$, 점 $D$를 지나고 $AC$에 수직인 직선이 직선 $AB$와 만나는 점을 $Q$라 하자. 점 $A$와 $E$에서 원 $\Omega$의 접선이 직선 $BC$와 만나는 점을 각각 $X,Y$라 하자. 네 점 $X,Y,P,Q$가 한 원 위에 있음을 보여라.

 

풀이.

 

7. 양의 실수의 수열 $\{ a_n \}$과 $\{ b_n \}$이 모든 양의 정수 $n$에 대하여 다음 세 조건을 모두 만족한다.

• $a_{n+1}b_{n+1}=a_n^2+b_n^2$
• $a_{n+1}+b_{n+1}=a_nb_n$
• $a_n\geq b_n$

부등식 $\displaystyle\frac{a_n}{b_n}>2023^{2023}$을 만족하는 양의 정수 $n$이 존재함을 보여라.

 

풀이. $p_n=a_n+b_n, q_n=a_nb_n$으로 두면 $p_{n+1}=q_n$, $q_{n+1}=p_n^2-2q_n$입니다.

또한 조건을 만족하는 $a_n$과 $b_n$이 존재해야 하므로 $p_n^2 \geq 4q_n$이 성립합니다.

 

문제에서 요구하는 비율을 계산해보면,

$$\frac{a_n}{b_n}=\frac{p_n^2+p_n\sqrt{p_n^2-4q_n}}{2q_n}-1\geq \frac{p_n^2}{2q_n}-1=\frac{q_{n+1}+2q_n}{2q_n}-1=\frac{q_{n+1}}{2q_n}$$

이므로, $r_n = \displaystyle\frac{q_{n+1}}{q_n}$을 충분히 크게 만들 수 있음을 보이면 충분합니다.

 

$q_{n+1}=p_n^2-2q_n=q_{n-1}^2-2q_n$이므로 $r_nr_{n-1}=\displaystyle\frac{q_{n+1}}{q_{n-1}}=q_{n-1}-2r_{n-1}$, $r_{n-1}(r_n+2)=q_{n-1}$입니다.

이때 $p_n^2\geq 4q_n$이므로 $q_{n+1}=p_n^2-2q_n\geq 2q_n$, 즉 $q_n\geq 2^{n-1}q_1$입니다.

그러면 $n>1$에 대해 $(r_{n-1}+2)(r_n+2)>q_{n-1}\geq 2^{n-2}q_1$이므로 $r_{n-1}$과 $r_n$ 중 $\sqrt{2^{n-2}q_1}-2$ 이상인 수가 존재합니다. 이 값은 $n$이 커짐에 따라 발산하므로, 충분히 큰 $r_n$을 찾을 수 있습니다. $\blacksquare$

 

8. 양의 정수 $n$에 대하여, $n$이 서로 다른 두 소수의 곱이고 $n$을 $3$으로 나눈 나머지가 $2$이면, $n$을 "특별한 수"라고 하자. 예를 들어, $50$ 이하의 양의 정수 중에 특별한 수는 $14$, $26$, $35$, $38$ 뿐이다. 특별한 수로 구성된 임의의 유한집합 $S$에 대하여 다음 세 조건을 모두 만족하는 서로소인 두 집합 $A$, $B$가 존재함을 보여라.

• $A \cup B=S$
• $|n(A)-n(B)|\leq 1$
• 임의의 소수 $p$에 대하여, $A$의 원소 중 $p$의 배수의 개수와 $B$의 원소 중 $p$의 배수의 개수의 차이는 $1$ 이하이다.

풀이. $S$의 소인수들의 집합을 $P$라 하고, $P$를 점 집합으로 하는 그래프 $G=(P,E)$를 다음과 같이 정의합니다:

"$p,q\in P$에 대해 $\{ p, q \} \in E \Leftrightarrow pq \in S$"

주어진 그래프는 단순 그래프로 잘 정의됩니다. 또한 $P$에서 $3$으로 나눈 나머지가 $1$인 수를 검은색, $2$인 수를 흰색으로 칠해보면($3$은 당연히 $P$에 없습니다) 같은 색깔이 이웃하지 않는다는 걸 알 수 있습니다. (만약 이웃한다면, 둘의 곱에 해당되는 $S$의 원소가 $3k+1$꼴이 됩니다) 따라서 이 그래프는 이분그래프입니다.

 

이제 $G$에서 다음과 같은 새로운 문제를 해결하면 충분합니다:

이분그래프 $G$가 주어질 때(연결 그래프가 아닐 수 있음), 다음을 만족하는 변 집합의 분할 $A$와 $B$가 존재함을 보여라.

• $|n(A)-n(B)|\leq 1$
• 각 점에 대해, 그 점에 연결된 변들 중 $A$의 원소의 개수와 $B$의 원소의 개수의 차이는 $1$ 이하이다.

이를 점 개수에 대한 귀납법으로 증명할 수 있습니다. 초기 조건은 자명하고, 점이 $n$개 미만일 때 명제가 성립한다고 가정합시다. 편의상 변 집합을 분할하는 과정을 변에 빨간색 또는 파란색을 칠하는 것으로 설명하겠습니다. 다음 두 가지 경우가 있습니다.

 

Case 1. $G$가 forest일 때:

리프에서 리프로 가는 임의의 경로를 하나 잡을 수 있습니다. (리프 하나를 잡고 계속 이동하다 보면, 회로가 없으므로 언젠가 리프에서 종료해야 합니다) 그 경로를 제거한 후 귀납 가정을 적용하여 남은 변에 빨간색과 파란색을 잘 칠합니다. 그 후 원래 경로에서 빨간색과 파란색을 교대로 칠하면, 주어진 조건을 만족함을 알 수 있습니다. 경로 중간의 점들은 빨간색과 파란색이 하나씩 추가되므로 문제가 없고, 양 끝점은 리프였으므로 똑같이 문제가 없습니다. 다만 전체 색깔 개수를 조정하기 위해, 만약 귀납 가정에서 빨간색이 더 많았으면 경로를 칠할 때 파란색부터 교대로 칠해야 합니다.

 

Case 2. $G$가 forest가 아닐 때:

$G$의 회로를 하나 잡을 수 있습니다. 이때 $G$가 이분그래프이므로 이는 짝수 회로입니다. 마찬가지로 짝수 회로를 제거하고 귀납 가정을 적용한 후, 짝수 회로에 두 색깔을 교대로 칠하면 조건을 만족합니다.

 

따라서 수학적 귀납법에 의해 임의의 이분그래프 $G$에 대해 조건을 만족하도록 변을 두 색깔로 칠할 수 있습니다. $\blacksquare$