AMC 10 · 2013 · #21

학년 7 counting

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

recursive-sequencelinear-diophantinegcd extremal-constructionpattern-recognition ↑ 선수 지식: gcd

📏 중간 풀이 💡 3 개 인사이트

문제

음이 아닌 정수로 이루어진, 감소하지 않는 두 수열의 첫째 항이 서로 다르다. 각 수열은 셋째 항부터 각 항이 바로 앞 두 항의 합이 되는 성질을 가지며, 두 수열의 일곱째 항은 모두 $N$ 이다. $N$ 이 가질 수 있는 가장 작은 값은 얼마인가?

답을 골라 클릭하세요.

(A)

(B)

(C)

104

(D)

144

(E)

273

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

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 음이 아닌 정수로 이루어진 두 수열이 있다. 둘 다 감소하지 않으며, 세 번째 항부터는 각 항이 바로 앞 두 항의 합인 피보나치식 규칙을 따른다. 두 수열의 첫째 항은 서로 다르지만 일곱째 항은 둘 다 같은 값 N이다. 이런 일이 가능한 가장 작은 N을 구하라.

주어진 것: 각 수열은 감소하지 않고 음이 아닌 정수로 이루어진다; 세 번째 항부터 각 항 = 바로 앞 두 항의 합; 두 수열의 첫째 항은 서로 다르다; 두 수열의 일곱째 항은 같은 값 N이다

구하는 것: 두 수열이 공유하는 일곱째 항 N의 가장 작은 값

이해

계획

주요 도구: #14 극단의 원리

보조 도구: #4 변수 도입하기, #5 패턴 찾기, #2 빠짐없이 나열하기

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

실행 — 정답: C

#4 변수 도입하기 5.OA.B.3 단계 1

일곱째 항을 변수로 쓰기

첫 두 항을 a, b라 하자.
'각 항은 앞 두 항의 합'이라는 규칙으로 나머지를 쌓으면 a, b, a+b, a+2b, 2a+3b, 3a+5b, 그리고 일곱째 항 5a+8b가 된다.
따라서 모든 수열의 일곱째 항은 N = 5a + 8b이고, a와 b는 그 수열의 첫 두 항이다.

$$a,\; b,\; a{+}b,\; a{+}2b,\; 2a{+}3b,\; 3a{+}5b,\; 5a{+}8b \;\Rightarrow\; N = 5a + 8b$$

💡 시작하는 두 수에 이름을 붙이면 고정된 덧셈 규칙이 그 둘을 일곱째 항의 한 식으로 끝까지 실어 나른다.

#4 변수 도입하기 6.EE.B.6 단계 2

두 수열, 같은 N

한 수열이 a, b로 시작하고 다른 수열이 a', b'로 시작한다고 하자.
두 일곱째 항이 같다는 것은 5a + 8b = 5a' + 8b'이다.
정리하면 5(a' - a) = 8(b - b')이다.
첫째 항이 서로 다르므로(a != a') 양변은 0이 아니다.

$$5a + 8b = 5a' + 8b' \;\Longrightarrow\; 5(a' - a) = 8(b - b')$$

💡 두 일곱째 항 식을 같다고 놓으면 전체 문제가 두 시작 쌍 사이의 한 관계로 바뀐다.

#5 패턴 찾기 6.NS.B.4 단계 3

해 사이의 가장 작은 간격

5(a' - a) = 8(b - b')에서 좌변은 5의 배수, 우변은 8의 배수다.
5와 8은 공약수가 없으므로 a' - a는 8의 배수, b - b'는 5의 배수여야 한다.
0이 아닌 가장 작은 변화는 a' - a = 8, b - b' = 5이다.
따라서 유효한 어떤 쌍 (a, b)에서 다음 쌍은 (a + 8, b - 5)이다.
첫째 항을 8 올리고 둘째 항을 5 내린다.

$$\gcd(5,8)=1 \;\Rightarrow\; a' = a + 8,\quad b' = b - 5$$

💡 5와 8이 공약수가 없기에 첫째 항은 8씩만 뛸 수 있고 둘째 항은 5씩 미끄러진다.

#14 극단의 원리 7.EE.B.4 단계 4

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

두 수열 모두 감소하지 않아야 하므로 a <= b, a' <= b'이다.
둘째 쌍은 a + 8 <= b - 5가 필요하고, 이는 b >= a + 13을 뜻한다.
이제 a >= 0, b >= a + 13 아래에서 N = 5a + 8b를 최소화한다.
두 계수 모두 양수이므로 a, b를 허락되는 한 가장 작게 잡는다.
a = 0으로 두면 b >= 13이 강제되어 b = 13이다.

$$a + 8 \le b - 5 \;\Rightarrow\; b \ge a + 13; \quad \min N \text{ at } a=0,\; b=13$$

💡 시작하는 두 수를 모두 허용되는 최솟값으로 밀면 일곱째 항이 갈 수 있는 가장 낮은 곳까지 내려간다.

#2 빠짐없이 나열하기 4.NBT.B.4 단계 5

두 수열을 확인하고 N 읽기

a = 0, b = 13이면 첫 수열은 0, 13, 13, 26, 39, 65, 104이다.
짝이 되는 쌍은 (0+8, 13-5) = (8, 8)이고, 8, 8, 16, 24, 40, 64, 104을 준다.
둘 다 감소하지 않고, 첫째 항이 서로 다르며(0과 8), 둘 다 일곱째 항으로 104에 도달한다.
따라서 가장 작은 N은 104이고 정답은 (C)다.

$$N = 5(0) + 8(13) = 104 = 5(8) + 8(8)$$

💡 104로 끝나는 두 수열을 실제로 하나 보이면 그 값이 바람이 아니라 진짜 도달 가능함이 증명된다.

[1] #4 5.OA.B.3 첫 두 항을 a, b라 하자. '각 항은 앞 두 항의 합'이라는 규칙으로 나머지를 쌓으면 a, b, a+b, a+2b, 2a+3b, 3a+5b,

[2] #4 6.EE.B.6 한 수열이 a, b로 시작하고 다른 수열이 a', b'로 시작한다고 하자. 두 일곱째 항이 같다는 것은 5a + 8b = 5a' + 8b'이다.

[3] #5 6.NS.B.4 5(a' - a) = 8(b - b')에서 좌변은 5의 배수, 우변은 8의 배수다. 5와 8은 공약수가 없으므로 a' - a는 8의 배수, b

[4] #14 7.EE.B.4 두 수열 모두 감소하지 않아야 하므로 a <= b, a' <= b'이다. 둘째 쌍은 a + 8 <= b - 5가 필요하고, 이는 b >= a +

[5] #2 4.NBT.B.4 a = 0, b = 13이면 첫 수열은 0, 13, 13, 26, 39, 65, 104이다. 짝이 되는 쌍은 (0+8, 13-5) = (8, 8

검토

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

대안 접근: 나눗셈 논증을 건너뛰고, 0 <= a <= b에 대해 5a + 8b 값을 작은 순서로 나열하면서 a가 다른 채로 처음 두 번 나타나는 값을 찾아도 된다. 더 작은 반복이 나오기 전에 (0,13)과 (8,8)이 모두 104를 주므로 N = 104가 확인된다.

사용된 CCSS 표준 (최저 학년 7)

5.OA.B.3 Generate two numerical patterns using two given rules and identify relationships (앞 두 항을 더하는 규칙으로 각 수열을 쌓아 일곱째 항 5a + 8b에 이르기.)
6.EE.B.6 Use variables to represent numbers and write expressions to solve problems (첫 두 항 a, b에 이름을 붙이고 두 일곱째 항 식을 같다고 놓기.)
6.NS.B.4 Find greatest common factor and least common multiple of two numbers (gcd(5,8)=1을 이용해 첫째 항은 8씩, 둘째 항은 5씩 변해야 함을 보이기.)
7.EE.B.4 Use variables to represent quantities and construct simple equations and inequalities (감소하지 않는 규칙을 b >= a + 13으로 바꾸고 그 아래에서 N = 5a + 8b를 최소화하기.)
4.NBT.B.4 Fluently add and subtract multi-digit whole numbers (두 수열의 항들을 계산하고 각 일곱째 항이 104임을 확인하기.)

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