2019 APMO 풀이

2019년 APMO 문제들에 대한 풀이이다. 사실 2012 SL 풀이 작성이 귀찮아서 새로 문제를 찾아보고 있는거지만...애초에 어떤 셋의 모든 문제가 올라오기를 기대하기보다는 정기적으로 재밌는 문제가 올라온다고 생각하는게 나을 것이다.(계속 작성중)

 

1. 다음 조건을 만족하는 $$f:\mathbb{Z}^+\to \mathbb{Z}^+$$를 구하여라:$$f(a)+b|a^2+f(a)f(b)$$ 

우선, 소수에 대한 함숫값을 먼저 분석하자. P(n,n):f(n)+n|n(n-f(n))인데, n에 소수를 넣고 나면 f(p)+p|p-f(p)라는 사실을 알 수 있고, 여기서 p=f(p)라는 사실을 얻는다. 이제 P(p,b)를 보면 p+b|b^2-bf(b)인데, p를 키울 수 있는데에 반해 우항은 고정되어있기 때문에 f(b)=b가 된다.

 

AoPS에는 다음과 같은 풀이가 적혀있다.

Claim) 2019 초과의 소수 p에 대해, f(p)=p이다.

pf) P(p,p)->f(p)+p|p^2+f(p)^2, f(p)+p|2p^2. 따라서 f(p)=p,p^2-p,2p^2-p중 하나가 된다. 그러나 P(p,1)에 따르면, f(p)+1|p^2-1이기 때문에 f(p)가 p^2-p 혹은 2p^2-p일 수 없게 된다. 즉, f(p)=p이다.

 

이제 n을 고정하고, p>1000*max(f(n)^2-n^2,2019)인 소수 p를 잡자. P(n,p): f(n)+p|n^2+pf(n), P(n,p)|n^2-f(n)^2가 되어, f(n)=n이 된다.

 

comment. 정수함수방정식에서 소수에 대해 함수가 취하는 값을 보는 기법은 상당히 기본적인 테크닉이라고 생각된다. 이런 문제를 만나면 한번 시도해보고 본격적으로 푸는 전략도 나쁘지 않은 것 같다.

2. m은 고정된 양의 정수이고, a_1은 양의 정수이다. 1 이상의 n에 대해, a_n+1을 다음과 같이 정의한다:$$a_{n+1}=\begin{Bmatrix}
a_n^2+2^m(a_n\lt 2^n) \\
a_n/2(else)
\end{Bmatrix}$$

이때, a의 원소가 전부 정수이도록 하는 a_1을 각 m에 대해서 구하시오.

오직 m=2일 때, a_1이 2 이상의 2의 거듭제곱일때만 가능하다.

 

a_n의 홀수부를 b_n이라고 하자. 그렇다면, 만약 두번째 경우를 타고 a_n+1이 정의된다면 b_n+1=b_n이다. 이제 첫 번째 경우의 조건을 분기할 것이다. v_2(a_n)=k라고 하자.

 

1. 2k<m, b_n+1=(b_n^2+2^(m-2k))

2. 2k=m, b_n+1=(b_n^2+1)/2

3. 2k>m, b_n+1=1+2^(2k-m)b_n^2

 

이 경우, 만약 단 한번이라도 1번혹은 3번 경우가 나온다면 b_n이 3 이상이 되며, 이후의 모든 경우에서 강증가하게 된다. 그러나 어느 순간에는 반드시 a의 원소가 2^m 미만으로 떨어지기 때문에 모순이다. 따라서, 오직 b_n이 항상 1이고 항상 2번 경우를 타는 경우만이 가능하다는 사실을 알 수 있다. 자명하게도 m이 홀수일수는 없다. 만약 m이 4 이상의 짝수라면, 어떤 항은 반드시 2^(m/2)여야 하는데 이 이후의 항을 나열해보면 2^m+1,2^m,2^m-1인데, m-1>m/2이므로 불가능하다. 즉, m=2인 경우만이 가능하며, 실제로 2의 거듭제곱을 넣으면 가능함을 확인할 수 있다.

 

AoPS에 올라온 풀이는 v_2를 적극적으로 활용하고 있다. 근데 쓰기 귀찮다. 링크를 첨부하겠다. Strange Conditional Sequence (artofproblemsolving.com) 

4. 2018*2019의, 수들이 적힌 칸으로 나뉜 판이 있다. 이제 어떤 시행을 진행할 것인데, 몇 개의 칸을 고르면 각 칸과 인접한 칸의 수들의 평균을 계산한 다음, 한번에 그 평균으로 각 칸들의 수를 대체한다. 이 시행을 유한번 반복하여 모든 칸에 적힌 수들이 동일해지도록 할 수 있는가?

없다. 법 5에서 보면 보다 직관적인데, 가로로 2018칸이라고 하면 다음과 같은 반례가 존재한다.

1 0 0 1

2 4 4 2

1 0 0 1

이것으로 판을 적당히 채우면 된다. 증명은 말 그대로 법 5이다.