AMC 10 · 2013 · #18

학년 6 logicpattern
modular-arithmeticpattern-recognitionlogical-deductioncasework work-backwardspattern-recognitioneasier-related-problem ↑ 선수 지식: modular-arithmeticpattern-recognition
📏 긴 풀이 💡 3 개 인사이트
문제
두 사람이 서로 다른 허용량을 가져가고 마지막을 가져간 쪽이 이긴다. 두 가지 더미 크기에 대해 승자를 판정하여라.

답을 골라 클릭하세요.

(A)
Barbara will win with $2013$ coins and Jenna will win with $2014$ coins
(B)
Jenna will win with $2013$ coins, and whoever goes first will win with $2014$ coins
(C)
Barbara will win with $2013$ coins, and whoever goes second will win with $2014$ coins
(D)
Jenna will win with $2013$ coins, and Barbara will win with $2014$ coins
(E)
Whoever goes first will win with $2013$ coins, and whoever goes second will win with $2014$ coins
풀이 과정
전략 거꾸로 풀기

2013개짜리 게임을 앞에서부터 끝까지 두어 볼 수는 없다. 하지만 게임의 끝은 완전히 알고 있다 — 마지막 동전을 가져가면 이긴다. 그러므로 모든 국면의 승패를 끝에서부터 거꾸로 밀어 올릴 수 있다: 어떤 국면이 두는 쪽의 승리라는 것은, 상대에게 상대의 패배 국면을 넘길 수 있는 수가 하나라도 있다는 뜻이다. 두 사람의 가능한 수가 다르므로 국면은 (동전 개수, 누구 차례) 쌍으로 기록해야 하고, 두 경우를 나란히 추적해야 한다. 작은 무더기에 이 역방향 계산을 돌리면 표가 나오고, 그 표는 주기 5로 반복된다. 이 반복이 문제의 전부인데, 이것은 믿을 대상이 아니라 증명할 대상이다. 앞의 열 줄에서 보이는 규칙성은 2013번째 줄에 대해 아무것도 말해 주지 않는다. 따라서 계획은 이렇다. 표에서 특징을 읽어 내어 나머지 n mod 5의 말로 적고, 강한 수학적 귀납법으로 증명한다. 그것이 "주기적으로 보인다"를 "영원히 주기적이다"로 바꿔 주는 단계다. 그 뒤에야 2013과 2014를 나머지로 줄이는 것이 안전해진다. 각 동전 개수마다 가능한 선공 두 경우를 따로 판정해 모두 네 개의 판정을 얻는다. 선택지가 'X가 이긴다'와 '먼저 두는 사람이 이긴다'를 구별하고 있으며, 이 둘은 서로 다른 근거로 갈리기 때문이다.

1STEP 1

국면에 이름 붙이기

각 더미 크기마다 이름 붙일 국면이 이다.

B(n) from {J(n-2), J(n-4)}, J(n) from {B(n-1), B(n-3)}
2STEP 2

작은 무더기를 손으로 채우기

작은 더미는 손으로 채워진다.

n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 ; B(n) & J & B & J & B & J & J & B & J & B & J ; J(n) & J & J & J & J & B & J & J & J & J & B
3STEP 3

패턴을 나머지로 읽기

그 패턴은 나머지 규칙으로 읽힌다.

Conjecture: B(n) = Barbara ⇔ n ≡ 2, 4 (mod 5); J(n) = Jenna ⇔ n ≢ 0 (mod 5)
4STEP 4

Barbara 쪽 절반을 귀납법으로 증명

귀납법이 한쪽의 절반을 증명한다.

n ≥ 6: Barbara wins ⇔ n-2 ≡ 0 or n-4 ≡ 0 (mod 5) ⇔ n ≡ 2, 4 (mod 5)
5STEP 5

Jenna 쪽 절반을 귀납법으로 증명

같은 논증이 나머지 절반도 덮는다.

n ≥ 6: {n-1, n-3} ∩ {0,1,3} ≠ ∅ (mod 5) ⇔ n ∈ {1,2,3,4} (mod 5) ⇔ n ≢ 0 (mod 5)
6STEP 6

2013과 2014를 5로 나누기

두 더미 크기의 나머지는 34다.

2013 = 5 · 402 + 3 ≡ 3, 2014 = 5 · 402 + 4 ≡ 4 (mod 5)
7STEP 7

두 판정을 선택지에 맞추기

그것이 두 판정을 지목한다, 보기 (B).

2013 coins → Jenna; 2014 coins → first mover
정답
2013개면 Jenna가 이기고, 2014개면 먼저 하는 사람이 이긴다
세 가지를 따로 확인한다. 첫째, 이 특징 서술은 고정점으로서 자기 일관적이며, 이는 그것이 옳은 서술이라는 강한 신호다. {0,1,3}을 Barbara의 패배 나머지 집합, {0}을 Jenna의 패배 나머지 집합이라 부르자. Barbara가 n에서 이기는 것은 n-2 또는 n-4가 ≡ 0일 때뿐이므로 n ≡ 2, 4가 되고, 따라서 그녀의 패배 집합은 가정한 대로 {0,1,3}이다. Jenna가 n에서 이기는 것은 n-1 또는 n-3이 {0,1,3}에 들어갈 때뿐이므로 n ≢ 0이 되고, 따라서 그녀의 패배 집합은 가정한 대로 {0}이다. 두 집합이 서로를 재생산한다. 둘째, 주기 5라는 주장은 나머지에 대한 어떤 추측도 없이 확인할 수 있다. n ≥ 6에서 쌍 (B(n), J(n))은 바로 앞의 네 쌍에 의해, 그리고 n 자체에 의존하지 않는 규칙에 의해 정해진다. 그러므로 n = 6,7,8,9에서의 연속한 네 쌍의 창이 그 뒤 전체를 결정한다. 그 창은 (J,J), (B,J), (J,J), (B,J)이고, n = 11,12,13,14에서의 창도 같은 네 쌍이다. 갱신 규칙이 매 단계 동일하므로 수열은 그 이후 영원히 주기 5로 반복될 수밖에 없다. 이는 반복되는 상태에 대한 비둘기집 식 논증만으로 주기성에 도달하는 독립적인 경로다. 셋째, 손으로 만든 표를 2013, 2014와 나머지가 같은 n = 48, n = 49까지 늘려 보면 48에서는 누가 먼저 두든 Jenna가 이기고 49에서는 먼저 두는 사람이 이긴다 — 2013과 2014의 판정과 일치한다. 여기서 답의 글자만 맞춰 보는 것은 약한 증거였을 것이다. (B)와 (D)는 2013에 대해 완전히 같은 말을 하고 오직 2014의 분석만이 둘을 갈라놓기 때문이다. 두 절반을 각각 독립적으로 확정했으므로 (B)는 안전하다.
💡핵심 정리

Barbara는 2개나 4개, Jenna는 1개나 3개를 가져가고 두 짝이 모두 5가 되므로, 중요한 것은 무더기를 5로 나눈 나머지와 지금이 누구 차례인가뿐이다.

  • 국면에 이름 붙이기
  • 작은 무더기를 손으로 채우기
  • 패턴을 나머지로 읽기
  • Barbara 쪽 절반을 귀납법으로 증명
  • Jenna 쪽 절반을 귀납법으로 증명
  • 2013과 2014를 5로 나누기
  • 두 판정을 선택지에 맞추기