AMC 10 · 2011 · #19

학년 11 number-theoryalgebra

유형 Small-Domain Constrained Search └ 세부 유형 Factor / Divisibility Constraint

floor-functionlogarithm-propertiesexponents convert-to-algebrabound-inequality-then-enumerate ↑ 선수 지식: exponents

📏 긴 풀이 💡 3 개 인사이트

문제

내림한 로그로 만든 개수가 정해진 값이 된다. 그렇게 되는 가장 작은 두 크기를 더하여라.

답을 골라 클릭하세요.

(A)

(B)

(C)

154

(D)

406

(E)

1024

풀이 과정

전략 변수 도입하기

도구 #4(변수 도입하기): 어려운 부분은 로그와 바닥 기호뿐인데, m=⌊log₂(N-1)⌋이라고 이름을 붙이면 이 둘이 N에 대한 평범한 부등식 두 개로 바뀐다. 도구 #15(다르게 정리하기): 로그가 사라지고 나면 식이 한 문장으로 읽힌다 — 엘리트 인원수는 N에서 그다음 2의 거듭제곱까지의 거리다 — 그리고 그렇게 읽는 순간 문제 전체가 한눈에 보인다. 도구 #14(극단의 원리): 문제는 가장 작은 N 두 개를 묻고 있으므로, 실제로 할 일은 19만큼의 간격을 담을 수 있을 만큼 넓은 첫 번째 구간을 찾는 것이고, 답은 바로 그 경계에 있다. 도구 #3(가능성 지우기): 순진하게 만든 후보 목록에는 가짜 해가 섞여 있어 걸러내야 하고, 선택지는 살아남은 값을 다른 방식으로 다시 확인할 수단이 된다.

1STEP 1

지수에 이름을 붙여 로그 없애기

지수에 이름을 붙이면 로그가 사라진다.

m=⌊log₂(N-1)⌋ ⇔ 2^m ≤ N-1 ＜ 2^m+1 ⇔ 2^m+1 ≤ N ≤ 2^m+1, 따라서 2¹+⌊log₂(N-1)⌋-N=2^m+1-N

2STEP 2

식을 말로 바꿔 읽기

말로 하면 다음 2의 거듭제곱까지의 차다.

엘리트(N)=(N 이상인 가장 작은 2의 거듭제곱)-N

3STEP 3

인원수를 19로 놓기

개수를 정하면 지수마다 후보가 하나씩 나온다.

2^m+1-N=19 ⟹ N=2^m+1-19

4STEP 4

m이 자기 구간에 맞는지 확인하기

한 후보는 자기 구간 밖으로 떨어져 가짜다.

2^m+1 ≤ 2^m+1-19 ⇔ 2^m ≥ 20 ⇔ m ≥ 5; 그리고 m=4는 가짜 후보 N=13을 주는데, 실제 엘리트 인원수는 16-13=3

5STEP 5

가장 작은 N 두 개

진짜 중 가장 작은 둘은 45와 109다.

m=5: N=2⁶-19=45, 2⁶-45=19; m=6: N=2⁷-19=109, 2⁷-109=19

6STEP 6

더해서 선택지와 맞추기

그 합은 154, 보기 (C).

45+109=154 → (C)

정답

154

두 값 모두 원래 식에 직접 넣어도 통과한다. 2¹+⌊log₂ 44⌋-45=64-45=19이고 2¹+⌊log₂ 108⌋-109=128-109=19이다. 45보다 작은 값은 하나도 될 수 없는데, 후보 목록을 쓰지 않고도 이유를 말할 수 있다. N ≤ 32이면 N은 m ≤ 4인 구간에 있고 그곳의 엘리트 인원수는 많아야 2⁴-1=15라서 19가 될 수 없다. 33 ≤ N ≤ 44이면 m=5이고 엘리트 인원수는 64-N ≥ 20이라 너무 크다. 그러므로 45가 진짜 첫 번째이고, 다음 구간이 109를 준다. 합의 크기도 자연스럽다. 두 N이 각각 2의 거듭제곱 바로 아래에 있으므로 합은 64+128=192보다 조금 작아야 하는데, 154는 여기에 들어맞고 38, 90, 406, 1024는 그렇지 않다.

💡핵심 정리

엘리트 인원수는 N에서 다음 2의 거듭제곱까지의 거리일 뿐이므로, 엘리트가 19명이라는 말은 N이 어떤 2의 거듭제곱보다 19 작다는 뜻이고, 그만한 간격은 폭이 20 이상인 구간에서만 생긴다.

지수에 이름을 붙여 로그 없애기
식을 말로 바꿔 읽기
인원수를 19로 놓기
m이 자기 구간에 맞는지 확인하기
가장 작은 N 두 개
더해서 선택지와 맞추기