AMC 10 · 2016 · #25

학년 8 arithmetic

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

floor-functionsystematic-enumerationpattern-recognition casework ↑ 선수 지식: floor-function

📏 긴 풀이 💡 4 개 인사이트

문제

각 실수 x ≥ 0 에 대해 f(x)=Σ_k=2¹⁰(⌊ kx⌋ - k⌊ x⌋) 로 정의한다. 여기서 ⌊ r⌋ 은 r 을 넘지 않는 가장 큰 정수이다. x 가 0 이상의 모든 값을 지날 때, f(x) 가 가질 수 있는 서로 다른 값의 개수를 구하라.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

infinitely many

AMC 10 2016 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

풀이 과정

전략 더 쉬운 문제로 줄이기

x 가 아무리 커질 수 있어서 식이 무섭게 보이지만, 도구 #9(더 쉬운 문제로 줄이기)로 단순해진다. x 를 정수 부분과 소수 부분의 합으로 쓰면 각 항 ⌊ kx⌋ - k⌊ x⌋ 이 x 의 소수 부분에만 의존함이 드러난다. 도구 #4(변수 도입하기)로 그 소수 부분을 t 라 두면 실수 전체가 구간 0 ≤ t ＜ 1 하나로 줄어든다. 도구 #1(그림 그리기)로 그 결과를 특정 분수에서만 올라가는 계단으로 그리고, 도구 #5(패턴 찾기)로 각 계단이 새로운 값에 닿음을 보인다. 마지막 개수 세기는 도구 #16(관점 바꾸기)을 쓴다. 출력 값을 직접 세는 대신 계단이 올라가는 입력 분수를 세는데, 그것이 바로 분모가 2 부터 10 까지인 기약분수들이다.

1STEP 1

x 를 정수 부분과 소수 부분으로 나누기

x = n + t 로 쓰자. n=⌊ x⌋ 은 정수, t={x} 는 0 ≤ t ＜ 1 인 소수 부분, 각 항에 대입한다.

x = n + t, n=⌊ x⌋∈{0,1,2,…}, 0 ≤ t ＜ 1

2STEP 2

각 바닥 함수에서 정수 부분 빼내기

kn 이 정수라 바닥 함수 밖으로 빠져 상쇄되고 각 항은 ⌊ kt⌋ 만 남아 f 는 t 에만 의존: f(x)=g(t).

⌊ kx⌋ - k⌊ x⌋ = (kn+⌊ kt⌋) - kn = ⌊ kt⌋ → f(x)=Σ_k=2¹⁰⌊ kt⌋ =: g(t)

3STEP 3

g(t) 를 올라가는 계단으로 보기

각 ⌊ kt⌋ 은 0 이다가 t=a/k 에서 1 씩 올라, g(t) 는 g(0)=0 에서 시작하는 감소하지 않는 계단이다.

g(0)=0; ⌊ kt⌋ 는 t=1/k,2/k,…,(k-1)/k 에서 1 만큼 올라감

4STEP 4

서로 다른 도약점마다 새로운 값이 생긴다

각 도약 분수 t=a/d(기약)에서 k=d 조각이 올라 g 는 오르기만 해 값이 반복 안 됨: #값 = 1 + #서로 다른 도약 분수.

#{g 의 값} = 1 + #{a/k∈(0,1) : 2 ≤ k ≤ 10, 1 ≤ a ＜ k}_서로 다른

5STEP 5

도약 분수를 기약분수로 세기

모든 분수를 기약분수로 줄이면, 분모 d(2 ≤ d ≤ 10)의 분자 개수는 d 와 서로소인 φ(d) 이다.

#{분모 d 의 분자} = φ(d) = #{a: 1 ≤ a ＜ d, gcd(a,d)=1}

6STEP 6

토션트들과 시작값을 더하기

d=2…10 의 φ(d) 합: 1+2+2+4+2+6+4+6+4 = 31 개 도약 분수, 시작값을 더해 31+1 = 32 = (A).

1+2+2+4+2+6+4+6+4 = 31, 31+1 = 32 = (A)

정답

개수가 유한하므로 '무수히 많음'(E)은 제외된다 — f 가 한 유계 구간에 사는 소수 부분 t 에만 의존하므로 타당하다. t=1/2 근처에서 계단을 확인하면, 거기서는 짝수 k(k=2,4,6,8,10)만 kt 가 정수이므로 g 가 한 번에 5 만큼 올라간다 — 도약이 1 보다 클 수 있지만 항상 양수여서 값이 반복되지 않음을 확인한다. 가장 흔한 실수는 2/4=1/2 같은 등가 분수를 합치지 않는 것인데, 기약분수(토션트)를 쓰면 해결되며, 그래서 32 가 과대 계산값 36, 45, 46 을 이긴다. 토션트 합 31 에 시작값 1 을 더한 32 가 선택지 (A)와 일치한다.

💡핵심 정리

x 의 소수 부분만 중요해서 합이 계단이 되고, 분모가 2부터 10까지인 기약분수마다 한 번씩 올라간다 — 그 분수들(31개)을 세고 시작값을 더하면 32 가 된다.

x 를 정수 부분과 소수 부분으로 나누기
각 바닥 함수에서 정수 부분 빼내기
g(t) 를 올라가는 계단으로 보기
서로 다른 도약점마다 새로운 값이 생긴다
도약 분수를 기약분수로 세기
토션트들과 시작값을 더하기