인상 깊은 MO 문제 #4: USAMO 2019 3번

문제

\(K\)는 십진법 표현에서 \(7\)을 포함하지 않는 자연수의 집합이다. 

다음 조건을 만족하는 모든 계수가 음이 아닌 정수인 다항식 \(f\)를 모두 찾아라. $$ n \in K \implies f(n) \in K $$

스포 방지선

________________________________________________________________________________________________________

_________________________________________________________________________________________________________

꽤 재밌는 문제다. 먼저 문제를 단항식으로 압축해준다.

Claim: \(f(x) = \sum_{i=0}^n a_i x^i\)가 조건을 만족하면, 각각의 \(a_i x^i\)도 조건을 만족한다.

증명은 간단하다. 모든 \(x \in K\)에 대해 \(\sum_{i=0}^n a_i x^i \in K\)라면, 모든 자연수 \(N\)에 대하여 \(\sum_{i=0}^n a_i (10^Nx)^i  = \sum_{i=0}^n a_ix^i \cdot 10^{Ni} \in K\)이다. 이는 \(10^Nx \in K\)이기 때문.

\(N\)을 매우 크게 잡으면 \(a_ix^i\)가 그대로 십진법 표현에 나오고, 결국 \(x \in K \implies a_i x^i \in K\)를 얻는다.  

이제 단항식을 보자. 먼저 1차식에 대한 논의를 진행한다.

Claim: \(f(x)=cx\)가 조건을 만족한다면, \(c\)는 \(10^e\) 형태로 쓸 수 있는 자연수다. 

\(c \neq 10^e\)라면, 적당한 \(x \in K\)가 있어서 \(cx \not\in K\)임을 보이면 된다. 

실제로는 \(cx\)의 첫 번째 자릿수가 \(7\)이 되도록 할 수 있다. \(c\)의 범위를 세세하게 나누고, 각 경우에서 \(x\)를 대응시켜주자. 

이제 2차 이상의 단항식을 보자. 모두 불가능함을 보여주자.

Claim: \(f(x)=cx^k\)는 \(k \ge 2\)라면 조건을 만족할 수 없다.

\(x \in K\)를 잡고 \(f(10x+3)\)을 생각하자. \(10x+3 \in K\)이므로, $$f(10x+3)=c(10x+3)^k = c \cdot 3^k + c \cdot 10 \cdot k \cdot 3^{k-1} x + \cdots $$는 \(K\)에 속한다. 앞선 Claim에서 \(10ck3^{k-1}x\)는 조건을 만족시키는 단항식이고, 이는 위 Claim에 의해 \(10ck3^{k-1}\)이 \(10^e\) 형태의 자연수임을 의미한다. 하지만 \(k \ge 2\)면 \(10ck3^{k-1} \equiv 0 \pmod{3}\)이므로 이는 불가능하다. 

결국 답은 \(f(x)=10^e x\), \(f(x)=k\) (단, \(k \in K\)), \(f(x)=10^ex + k\) (단, \(10^e > k, k \in K\)) 뿐임을 알 수 있다.