AMC 10 · 2011 · #11

학년 8 number-theorygeometry-2d

유형 Branching State Enumeration └ 세부 유형 Numeric Operation Tree

parityinteger-pythagorean-triplesinvariant-monovariant systematic-enumeration ↑ 선수 지식: parity

📏 긴 풀이 💡 3 개 인사이트

문제

모든 도약이 같은 거리이고 정수 점에 내려앉아야 한다. 가까운 목표까지 필요한 최소 도약 수를 구하여라.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 다르게 정리하기

실제 위치를 하나하나 쫓는 것은 가망이 없다 — 세 번만 뛰어도 도달 가능한 점이 이미 수천 개다. 결정적인 수는 도구 #15이다: 쌍 (x,y)를 통째로 추적하는 대신, 그중 단 하나의 정보인 "x+y가 짝수인가 홀수인가"만 추적한다. 이 값은 완전히 예측 가능한 방식으로 변하므로 "개구리가 도달할 수 있는가?"라는 물음이 "점프 횟수의 홀짝이 맞는가?"로 바뀐다. 도구 #4로 한 번의 점프를 a²+b²=25라는 식으로 바꾸고, 도구 #2로 그 정수해를 모두 나열하면 홀짝 주장이 실제로 확인 가능해진다. 그다음 도구 #3으로 불가능한 선택지를 지운다. 마지막으로, 최소 횟수를 묻는 문제는 하한만으로는 절반밖에 답하지 못하므로 도구 #11(도착점에서 거꾸로 풀기)로 그 하한을 실제로 달성하는 경로를 만든다.

1STEP 1

점프 한 번을 식으로 쓰기

도약 하나는 하나의 정수 방정식이다.

√(a²+b²)=5 ⟺ a²+b²=25, a,b 는 정수

2STEP 2

가능한 점프를 모두 나열하기

가능한 도약은 12가지뿐이다.

(± 5, 0), (0, ± 5), (± 3, ± 4), (± 4, ± 3) — 모두 12가지

3STEP 3

모든 점프는 홀짝을 뒤집는다

모든 도약이 좌표 합의 홀짝을 뒤집는다.

a²+b² = 25는 홀수 → a,b 중 정확히 하나만 홀수 → a+b는 홀수

4STEP 4

뒤집힌 횟수를 세기

따라서 도약 수는 홀수여야 한다.

x+y ≡ n (mod 2); 목표점의 합 = 1은 홀수 → n은 홀수

5STEP 5

두 번 점프를 다른 방법으로도 지우기

두 번은 다른 이유로도 안 된다.

p²+q² = (p-1)²+q² = 25 → 2p-1 = 0 → p = 1/2 ∉ Z

6STEP 6

한 번 점프를 지우기

한 번은 명백히 거리가 맞지 않는다.

√((1-0)²+(0-0)²) = 1 ≠ 5 → n ≠ 1, 따라서 n ≥ 3

7STEP 7

세 번짜리 경로 만들기

세 번짜리 경로가 있으므로 답은 3이다.

(0,0) → (3,4) → (6,0) → (1,0)

정답

"최소"를 묻는 문제가 요구하는 두 가지가 모두 닫혔다. 하한: 홀짝 논증이 모든 짝수 횟수를 지우고 거리 불일치가 한 번을 지우므로 n ≥ 3이다. 상한: 실제로 적법한 경로가 3번으로 해낸다. 두 번 점프를 공격한 두 논증은 서로 공유하는 것이 전혀 없는데도 — 하나는 x+y의 홀짝 뒤집힘을 세고, 다른 하나는 두 원의 방정식을 빼서 p = 1/2을 얻는다 — 같은 결론에 도달하며, 이는 추론이 건전하다는 강한 증거다. 12가지 점프 벡터를 모두 확인해도 두 사실이 직접 확인된다: (0,0)과 (1,0) 양쪽에서 거리가 5인 벡터는 하나도 없고, (1,0)을 세 점프 벡터의 합으로 쓰는 방법은 순서를 무시하면 (3,4)+(3,-4)+(-5,0) 단 하나뿐이므로 찾아낸 경로가 사실상 유일하다. 선택지 (D) 5는 설계된 함정이다: 홀짝은 맞고 길이 5인 경로도 실제로 존재하지만 최소가 아니다. (A), (C), (E)는 짝수라 홀짝 조건에서 탈락한다.

💡핵심 정리

격자 위에서 길이 5인 점프는 언제나 x+y를 홀수만큼 바꾸므로 개구리의 짝수-홀수 색은 매번 뒤집힌다. (1,0)에 닿으려면 홀수 번이어야 하는데 한 번은 너무 짧고, 세 번이면 실제로 도달한다.

점프 한 번을 식으로 쓰기
가능한 점프를 모두 나열하기
모든 점프는 홀짝을 뒤집는다
뒤집힌 횟수를 세기
두 번 점프를 다른 방법으로도 지우기
한 번 점프를 지우기
세 번짜리 경로 만들기