2023 FKMO Day 1 풀이

 여유가 생기면 풀어보려 했는데, 결국 종강 이후 풀어보게 되었습니다.

 

 

1. $AB<AC$인 삼각형 $ABC$에서 변 $AB$, $AC$ 위에 각각 점 $D(\ne A,B)$, $E(\ne A,C)$를 잡고, $PB=PD$이며 $PC=PE$인 점 $P$를 잡자. $B$를 포함하지 않는 호 $AC$ 위의 점 $X(\ne A,C)$를 잡고, 직선 $AX$와 삼각형 $ADE$의 외접원의 교점을 $Y(\ne A)$라 하자. 이때 $PX=PY$임을 보여라.

 

풀이. 나선닮음을 쉽게 생각해볼 수 있다.

삼각형 $ABC$의 외접원과 $ADE$의 외접원의 교점을 $T$라 하면, $\triangle TDB \sim \triangle TEC \sim \triangle TYX$이다.

선분 $DB$, $EC$, $YX$의 중점을 각각 $M, N, K$라 하면, 닮음비에 따라 $\triangle TDM$, $\triangle TEN$, $\triangle TYK$도 닮음이다.

따라서 $\angle DMT=\angle ENT=\angle YKT$이며, 이는 $(A, M, N, K, T)$가 한 원 위에 있음을 뜻한다.

이때 $\angle AMP=\angle ANP = 90^\circ$이므로 $AP$가 이 원의 지름이 된다.

따라서 $\angle AKP=90^\circ$, $PX=PY$이다.    $\blacksquare$

 

2. 함수 $f:\mathbb{R}^+\rightarrow\mathbb{R}^+$가 다음 조건을 만족한다.

(조건) 임의의 양의 정수 $x$에 대해, $(x+f(y))(y+f(x))\leq 4$를 만족하는 양의 정수 $y$가 존재하며 그 개수는 유한하다.

이때 $f$가 강감소함수임을 보여라.

 

풀이. 양의 정수 $x$에 대해 조건을 만족하는 양의 정수 $y$의 집합을 $C_x$라 하자. 이때 $C_x$는 공집합이 아닌 유한집합이다. 또한, $y\in C_x$이면 자명하게 $x\in C_y$이다. 만약 $f$가 강감소함수가 아니라면, $a<b$이고 $f(a)\leq f(b)$인 양의 정수 $a, b$가 존재해야 한다.

 

$a$와 $b$ 사이의 실수 $x$에 대하여 $f(x)\geq f(a)$인 $x$들의 집합을 $A$, $f(x)\leq f(b)$인 $x$들의 집합을 $B$라 하자. $f(a)\leq f(b)$이므로 $A\cup B=(a, b)$이다. 따라서 둘 중 원소가 무수히 많은 집합을 선택할 수 있다.

 

만약 $A$가 무한집합이면, 임의의 $A$의 원소 $x$에 대해 $C_x$의 원소 $p_x$를 선택할 수 있다.

이때 $(a+f(p_x))(p_x+f(a))\leq (x+f(p_x))(p_x+f(x))\leq 4$이므로 $p_x\in C_a$이다.

그러나 $C_a$가 유한집합이므로, 어떤 양의 실수 $p$가 존재해 무수히 많은 $x$에 대해 $p_x=p$가 되어야 한다.

그런데 $p=p_x\in C_x$이므로 $x \in C_p$이다. 이는 $C_p$가 무수히 많은 원소를 가진다는 뜻으로 모순이다.

 

만약 $B$가 무한집합이면, $C_b$의 아무 원소 $y$를 잡자.

그러면 $B$에 속한 임의의 원소 $x$에 대해 $(x+f(y))(y+f(x))\leq (b+f(y))(y+f(b))\leq 4$이므로 $x\in C_y$이다.

즉 유한집합인 $C_y$가 무한집합인 $B$를 포함해야 하므로 모순이다.

 

따라서 $f$는 강감소함수이다.    $\blacksquare$

(전 이 문제를 풀 때 그래프를 그렸는데, 그러면 위 풀이가 시각적으로 당연하다는 것을 알 수 있습니다)

 

3. 홀수인 소수 $p$가 주어져 있다. 양의 정수 $n$에 대해 $\{1, 2, \cdots, n\}$의 부분집합 중 원소의 합이 $p$의 배수인 것의 개수를 $A(n)$이라 정의하자. (공집합의 원소의 합은 0이다.) $2^{p-1}-1$이 $p^2$으로 나누어 떨어지지 않을 때, 임의의 정수 $k$에 대해 다음을 만족하는 양의 정수 $m$이 무수히 많이 존재함을 보여라.

$\displaystyle\frac{A(m)-k}{p}\in \mathbb{Z}$

 

풀이.  $A(n)$ 들을 mod p로 나열하였을 때 모든 나머지가 무수히 많이 등장함을 보이면 충분하다. 이를 위해 $A(n)$을 계산해볼 필요가 있다. 가장 단순한 방법은 생성함수를 이용하는 것이다.

$f_n(x)=(1+x)(1+x^2)\cdots(1+x^n)$와 $w^p=1$에 대해 $A(n)=\displaystyle\frac{1}{p}\sum_{i=0}^{p-1}f_n(w^i)$임이 잘 알려져있다.

$w$의 주기성을 생각해보면 $n=p$일 때 결과값을 쉽게 계산할 수 있다. $f_p(w)=f_p(w^2)=\cdots=f_p(w^{p-1})=(1+1)(1+w)(1+w^2)\cdots(1+w^{p-1})$인데, $x^p-1=(x-1)(x-w)\cdots(x-w^{p-1})$을 고려하면 그 값이 $1-(-1)^p=2$가 됨을 쉽게 알 수 있다.

이 아이디어를 이용하면 일반적인 점화식을 유도해볼 수 있다.

 

$A(n+p)=\displaystyle\frac{1}{p}\sum_{i=0}^{p-1}f_{n+p}(w^i)=\frac{1}{p}(2^p f_n(1)+2\sum_{i=1}^{p-1} f_n(w^i))=\frac{1}{p}((2^p-2)f_n(1)+2\sum_{i=0}^{p-1}f_n(w^i))=2A(n)+\frac{2^p-2}{p}2^n$

 

이 점화식을 이용하면 임의의 $0\leq r<p$에 대해 $A(pk+r)$을 표현할 수 있지만, 이 문제는 $r=0$, 즉 $p$의 배수만 다뤄도 해결된다. 

 

$2^{p-1}-1=pt$로 두고 $n=pk$에 대해 $A(p(k+1))=2A(pk)+\displaystyle\frac{2^p-2}{p}2^{pk}$를 풀어보면

$A(pk)=2^{k}(A(0)+\displaystyle\frac{2^{p-1}-1}{p}\frac{2^{(p-1)k}-1}{2^{p-1}-1})\equiv 2^k(1+tk) (\text{mod p})$이다.

 

이제 모든 양의 정수 $s$에 대해 $k=(p-1)s$일 때를 생각해보면 $2^k$은 mod p로 일정하고, $t$가 $p$의 배수가 아니므로 $1+tk$는 mod p로 완전잉여계를 형성한다. 따라서 모든 나머지가 무수히 많이 등장한다.    $\blacksquare$