AMC 10 · 2013 · #20

학년 7 countingnumber-theory

유형 Small-Domain Constrained Search └ 세부 유형 Sum-Target Search

modular-arithmeticsymmetry-argumentpair-counting identify-subproblemsconvert-to-algebrasystematic-enumeration ↑ 선수 지식: modular-arithmetic

📏 긴 풀이 💡 4 개 인사이트

문제

이기는 관계가 순환하고, 세 항목이 서로를 이기는 고리를 이뤄야 한다. 고리의 수를 세어라.

답을 골라 클릭하세요.

(A)

810

(B)

855

(C)

900

(D)

950

(E)

988

풀이 과정

전략 다르게 정리하기

succ의 정의는 상관없어 보이는 두 규칙을 붙여 놓은 모양이고, 바로 그것이 이 문제를 어렵게 만든다. 가장 쓸모 있는 한 수는 그 두 조건을 하나의 규칙으로 다시 쓰는 것이다. 열쇠가 되는 수는 19다. 두 번째 조건은 첫 번째 조건에 19를 더한 모습 그 자체다. 그래서 1부터 19까지의 줄을 19개 점의 원으로 구부리고, a succ b를 '짧은 한 번의 앞걸음'으로 읽는다. 그다음 세 걸음의 길이에 이름을 붙이고, 원을 도는 세 걸음이 정확히 한 바퀴 만에 닫혀야 함을 보인 뒤, 그렇게 되는 걸음 길이를 센다. 셈은 앞방향(모든 순환이 그런 걸음을 준다)과 뒷방향(그런 걸음 선택은 모두 진짜 순환을 만든다) 양쪽으로 확인한다. 그래야만 셈이 상한이 아니라 정확한 값이 된다.

1STEP 1

두 조건을 하나로 합치기

두 조건이 하나의 나머지 규칙으로 합쳐진다.

a succ b ⇔ (a-b) mod 19 ∈ {1,2,…,9}

2STEP 2

수의 줄을 19각형 원으로 구부리기

그것이 줄을 원으로 구부린다.

positions 1,2,…,19 on a circle; a succ b ⇔ a is 1..9 steps ahead of b

3STEP 3

세 걸음의 길이에 이름 붙이기

세 걸음이 고리 전체를 설명한다.

m ≡ x-y, n ≡ y-z, p ≡ z-x (mod 19), m,n,p ∈ {1,…,9}, m+n+p ≡ 0 (mod 19)

4STEP 4

합을 정확히 한 바퀴로 조이기

그 합은 정확히 한 바퀴여야 한다.

3 ≤ m+n+p ≤ 27 and 19 ∣ m+n+p → m+n+p = 19 → p = 19-m-n, m+n ≥ 10

5STEP 5

거꾸로 되돌려 빠진 것이 없음을 증명하기

되돌려 보면 빠진 것이 없다.

(x,m,n) ⟷ (x, y, z) with y ≡ x-m, z ≡ x-m-n (mod 19)

6STEP 6

조건을 만족하는 걸음 쌍 나열하기

가능한 걸음 쌍은 45가지다.

#{(m,n): 1 ≤ m,n ≤ 9, m+n ≥ 10} = 1+2+…+9 = 45

7STEP 7

19개의 출발점을 곱하기

출발점 수를 곱하면 855다.

19 × 45 = 855

정답

855

서로 독립인 두 가지 검산이 있다. 첫째, 대칭성이 약수를 강제한다. 19각형 원 위에서 세 수에 모두 1을 더해도 순환은 여전히 순환이고, 19는 소수이며 이 이동으로 고정되는 순환은 없으므로 순환들은 19개씩 묶인다. 따라서 답은 19의 배수여야 한다. 또 역할을 돌려서 (x, y, z)를 (y, z, x)로 바꿔도 순환은 순환이고, x, y, z가 서로 다르므로 이 묶음의 크기는 3이다. 따라서 답은 3의 배수이기도 하다. 즉 57이 답을 나눈다. 다섯 선택지 중 855 = 57 × 15만 이를 통과하고 810, 900, 950, 988은 두 검사 중 하나에서 걸린다. 둘째, 크기 감각이다. 서로 다른 a, b에 대해 a succ b와 b succ a 중 정확히 하나만 성립하므로, 서로 다른 세 수의 순서쌍이 순환을 이룰 확률은 대략 여덟 번에 한 번이다. 그런 순서쌍은 19 × 18 × 17 = 5814개이고 5814를 8로 나누면 약 727로, 855와 같은 자릿수다. 구체적인 예도 맞는다. (x, y, z) = (1, 11, 6)이면 11 - 1 = 10 ＞ 9이므로 1 succ 11, 11 - 6 = 5이므로 11 succ 6, 6 - 1 = 5이므로 6 succ 1이다.

💡핵심 정리

1부터 19까지를 원으로 구부리면 그 이상한 두 갈래 규칙이 '1칸에서 9칸 앞서 있다'라는 한 문장이 되고, 제자리로 돌아오는 세 걸음은 정확히 19라는 한 바퀴를 채워야 한다.

두 조건을 하나로 합치기
수의 줄을 19각형 원으로 구부리기
세 걸음의 길이에 이름 붙이기
합을 정확히 한 바퀴로 조이기
거꾸로 되돌려 빠진 것이 없음을 증명하기
조건을 만족하는 걸음 쌍 나열하기
19개의 출발점을 곱하기