4안 설계 메모
처음 구상에서는 적용 횟수를 하나 늘릴 때마다 허용 구간의 왼쪽과 오른쪽이 번갈아 줄었다. 이를 거꾸로 읽어 보았다. 정확히 번 할 수 있는 입력 중 가장 큰 값이 주어졌을 때, 그 값에서 오른쪽으로 조금 움직이면 몇 번 더 할 수 있을까? 횟수의 변화를 물으면 구간에서 탈락하는 순서와 수직선을 따라 만나는 순서가 다른 현상이 드러난다.
수학적 근거
라 두고 를 번 합성한 함수를 이라 쓰자. 처음 입력에 정확히 번 적용할 수 있는 것은 번째 함숫값 가 이하인 것과 같다. 따라서 그런 입력 전체는 이다. 실제로 어느 에서 출발하든 로 되감은 중간값이 모두 양수이므로, 되감아서 얻은 입력에는 를 번 적용할 수 있다.
이 홀수이면 은 감소한다. 어느 를 골라도 더 작은 가 있어, 그 상에는 최댓값이 없다. 따라서 은 짝수이고 이다. 이때 의 오른쪽을 조사하려면 마지막 값 의 오른쪽에서 로그를 몇 번 더 취할 수 있는지 살피면 된다. 이면 이고 이므로 정확히 두 번 더 적용된다. 역으로 정확히 두 번 더 적용되려면 이고 이어야 하므로 이 범위 전체가 나온다.
정확히 번 적용할 수 있는 입력 전체는 증가함수 이 를 옮긴 이다. 이므로 오른쪽 끝은 이다. 열린 왼쪽 끝과 닫힌 오른쪽 끝이 요구한 것과 맞는다. 충분히 작은 에서 이미 횟수는 로 정해지며, 이 구간 밖에는 그 횟수의 입력이 없으므로 , 이다.
우회와 한계
횟수가 일 때 정확히 그 횟수에서 끝나는 입력들을 차례로 구하면, 두 단계마다 같은 쪽 경계에서 구간이 이어질 것이라고 짐작할 수 있다. 그 관찰로 임의의 에 대한 결론을 내려면 한 번에 두 단계 되감는 증가함수가 구간을 어디로 보내는지 설명해야 한다. 다른 짧은 풀이로는 처음부터 을 예상하고 마지막 값 근처만 조사하는 방법이 있다. 이 방법에서도 의 존재가 어떤 쪽 변화를 보장하는지 확인해야 한다. 실제 핵심에 비해 ‘정확히 몇 번’이라는 정의를 읽는 부담이 있고, 두 물음 중 횟수만 선지로 제시하면 작은 짝수 하나를 그려 일반형을 추측할 수 있다. 수능 18번으로 다듬거나 판단하는 일은 이번 원안의 범위 밖이다.