2017 일본수학올림피아드 본선 2번문제

$N$을 양의 정수라 하자. 양의 정수 $a_1,a_2,\ldots,a_N$이 주어져 있어, 어떤 것도 $2^{N+1}$의 배수가 아니라고 한다. $N+1$ 이상의 정수 $n$에 대해, 다음과 같은 규칙으로 $a_n$을 정한다고 한다:
– $k=1,2,\ldots,n-1$ 중에서 $a_k$를 $2^n$으로 나눴을 때의 나머지가 가장 작은 $k$를 선택해 $a_n=2a_k$로 잡는다. 단, 그런 $k$가 여러 개 있을 경우에는 그 중 가장 큰 $k$를 택한다.
이 때, $n \geq M$이면 항상 $a_n=a_M$이 성립하는 양의 정수 $M$이 존재함을 보여라.

GD Star Rating
loading...