AMC 10 · 2013 · #21

학년 7 counting
유형 Small-Domain Constrained Search └ 세부 유형 Sum-Target Search
recursive-sequencelinear-diophantinegcd extremal-constructionpattern-recognition ↑ 선수 지식: gcd
📏 중간 풀이 💡 3 개 인사이트
문제
음이 아닌 정수로 이루어진 두 수열이 있다. 둘 다 감소하지 않으며, 셋째 항부터는 각 항이 바로 앞 두 항의 합인 피보나치식 규칙을 따른다. 두 수열의 첫째 항은 서로 다르지만 일곱째 항은 둘 다 같은 값 N이다. 이때 N이 가질 수 있는 가장 작은 값은 얼마인가?

답을 골라 클릭하세요.

(A)
55
(B)
89
(C)
104
(D)
144
(E)
273

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

풀이 과정
전략 극단의 원리

'가장 작은 값'이라는 말은 곧장 극단의 원리를 부른다. 조건이 모두 성립하는 선에서 N을 최대한 낮추면 된다. 먼저 첫 두 항을 a, b로 이름 붙이면 일곱째 항이 a, b에 대한 깔끔한 식이 된다. 그 식 덕분에 '일곱째 항이 같은 두 수열'은 '같은 값을 주는 서로 다른 두 (a, b) 쌍'으로 바뀌고, 극단의 원리로 a ＜ = b라는 순서 규칙이 허락하는 가장 작은 값을 쫓는다.

1STEP 1

일곱째 항을 변수로 쓰기

첫 두 항을 a, b라 하고 규칙대로 쌓으면 일곱째 항은 N = 5a + 8b가 된다.

a, b, a+b, a+2b, 2a+3b, 3a+5b, 5a+8b → N = 5a + 8b
2STEP 2

두 수열, 같은 N

일곱째 항이 같다는 것은 5a + 8b = 5a' + 8b', 즉 5(a' - a) = 8(b - b')이고 양변은 0이 아니다.

5a + 8b = 5a' + 8b' ⟹ 5(a' - a) = 8(b - b')
3STEP 3

해 사이의 가장 작은 간격

5와 8은 서로소이므로 a' - a는 8의 배수, b - b'는 5의 배수여야 하고, 최소 변화는 (a + 8, b - 5)이다.

gcd(5,8)=1 → a' = a + 8, b' = b - 5
4STEP 4

순서 규칙을 적용해 최소화하기

감소하지 않으려면 b ≥ a + 13이어야 하므로 N = 5a + 8b의 최솟값은 a = 0, b = 13에서 나온다.

a + 8 ≤ b - 5 → b ≥ a + 13; min N at a=0, b=13
5STEP 5

두 수열을 확인하고 N 읽기

(0, 13)은 0, 13, 13, 26, 39, 65, 104를, (8, 8)은 8, 8, 16, 24, 40, 64, 104를 준다.

N = 5(0) + 8(13) = 104 = 5(8) + 8(8)
정답
104
경계는 양쪽에서 딱 맞는다. b ≥ a + 13이라는 강제된 간격 아래에서 N = 5a + 8b는 5(0) + 8(13) = 104 밑으로 내려갈 수 없고, 구체적인 두 수열 0,13,...,104와 8,8,...,104가 서로 다른 첫째 항으로 104를 실현함을 보여 준다. 더 작은 선택지 55와 89는 피보나치 수라 자연스러운 한 쌍으로만 나오므로 서로 다른 두 시작에서 나올 수 없다. 104가 5a + 8b로 순서에 맞게 두 가지로 표현되는 첫 값이다.
💡핵심 정리

일곱째 항을 5a + 8b라는 식으로 바꾼 뒤, 커지는 순서 규칙이 허락하는 한 시작하는 두 수를 최대한 낮추면 공유되는 가장 작은 값이 나온다.

  • 일곱째 항을 변수로 쓰기
  • 두 수열, 같은 N
  • 해 사이의 가장 작은 간격
  • 순서 규칙을 적용해 최소화하기
  • 두 수열을 확인하고 N 읽기

비슷한 유형 더 풀어보기

같은 archetype · 비슷한 학년부터.