2027 6월 모평 · 공통수학 · 수열(수학Ⅰ) · 킬러 · 난이도 ★★★★★
점화식을 “인덱스 키우는 연산”으로 읽기
세 점화식은 사실 번호 n에 거는 세 가지 연산입니다.
값 10은 “출발값 + 누적 증가량”. 그래서 답은 풀이가 아니라 경우의 수 세기로 바뀝니다.
문제
수열 \{a_n\}은 a_1=1, a_3=4이고, 모든 자연수 n에 대하여
a_{2n}=a_n+1,\qquad a_{4n+1}=a_{4n+3}=a_n+4
를 만족시킨다. a_k=10을 만족시키는 자연수 k의 개수를 구하시오. [4점]
한 번에 이해하는 핵심
세 점화식 = 번호에 거는 세 연산 (값은 +1 또는 +4)
번호 n에서 출발해
D: n\to2n (값 +1),
Q_1: n\to4n+1 (값 +4),
Q_3: n\to4n+3 (값 +4).
모든 번호는 출발점 a_1=1 또는 a_3=4에서 이 연산들을 유일한 순서로 거쳐 만들어집니다(역추적이 결정적).
그래서 a_k=10은 증가량 합 = 10−출발값이 되는 연산열의 개수.
1에서: \#D+4\#Q=9 → 25가지. 3에서: \#D+4\#Q=6 → 7가지.
정답 k의 개수 =25+7=32
▶핵심을 눈으로 확인
k마다 a_k를 점으로 찍었습니다. 초록 = a_k=10.
슬라이더로 k의 상한을 늘리면 초록 개수가 늘다가 마지막 k=512에서 32에 멈춥니다(그 뒤엔 값이 모두 10 초과).
a_k
a_k=10
y=10
1풀이 1 — 인덱스 연산 + 경우의 수 (정석)
“값 = 출발값 + 연산별 증가량 합”으로 환원하면 순열 세기 문제가 됩니다.
세 연산과 증가량
D:n\mapsto2n (값 +1), Q_1:n\mapsto4n+1 (값 +4), Q_3:n\mapsto4n+3 (값 +4). 시작 a_1=1 또는 a_3=4.
번호↔연산열 일대일
임의의 k\ge2는 “짝수면 D 역, 4m+1이면 Q_1 역, 4m+3이면 Q_3 역”으로 유일하게 출발점까지 거슬러 간다. ⇒ 연산열 하나 = 번호 하나. 그래서 번호의 개수 = 연산열의 개수.
값 조건을 식으로
D는 +1, Q(=Q_1또는Q_3)는 +4. 출발 1: \#D+4\#Q=9. 출발 3(\text{값}4): \#D+4\#Q=6.
출발 1: 25가지
(\#D,\#Q)=(9,0),(5,1),(1,2). 길이 \#D+\#Q 순열에 Q 자리 고르기 \binom{\cdot}{\#Q} × 각 Q가 Q_1/Q_3 2가지 2^{\#Q}:
\binom90 +\binom61\!\cdot2+\binom32\!\cdot4=1+12+12=25.
출발 3: 7가지 → 정답
(\#D,\#Q)=(6,0),(2,1): \binom60+\binom31\!\cdot2=1+6=7. 총 25+7=32.
2풀이 2 — 값으로 층을 쌓는 직접 열거 (BFS)
공식 대신 손으로 셀 때의 표준. 값 10에 이르는 번호를 역으로 펼쳐 빠짐없이 셉니다.
역연산으로 부모 찾기
a_k=10인 k를 만들려면, 정연산의 역으로 “값을 줄이며” 출발점 (1) 또는 (3)까지 닿는 길을 모두 센다. 역: 값 -1(D의 역) 또는 값 -4(Q의 역, 분기 2).
증가량 분해(같은 식, 손으로)
출발 1→10: +9를 \{+1\}와 \{+4\}로 분해. 4\!\cdot\!0+9(D 9개), 4\!\cdot\!1+5(Q 1·D 5), 4\!\cdot\!2+1(Q 2·D 1). 각 분해의 순서·Q종류가 서로 다른 번호.
실제 번호로 확인
예: Q_3 후 D 5회 = 1\!\to\!7\!\to\!14\!\to\!28\!\to\!56\!\to\!112\!\to\!224, a_{224}=1+4+5=10 ✓. 순수 D 9회 = 2^9=512, a_{512}=10 ✓ (가장 큰 번호).
전수 목록 = 32개
이렇게 얻는 번호들: 37,39,41,\dots,62 (18개) ,\,129\text{–}132,134,136,140,144,152,160,176,192,224 (13개) ,\,512 (1개) — 합 32. 위 인터랙티브의 초록 점과 일치.
검산 — 왜 32에서 멈추나?
D만 9회면 번호 2^9=512로 최대. 연산을 더 걸면 값이 11 이상으로 넘어가므로, a_k=10인 번호는 k\le512에서 정확히 32개로 유한·완결. (프로그램 전수조사로도 k\le2\times10^5에서 32개 확인.)
Comments
Comments (0)
Leave a Comment