AMC 10 · 2010 · #25
학년 8 number-theory답을 골라 클릭하세요.
이 곱은 천문학적으로 크므로 아무도 직접 계산하지 않는다. 핵심은 도구 #7 (작은 문제로 쪼개기)이다: 2010=2 · 3 · 5 · 67은 제곱인수가 없으므로 "가장 큰 m 은?" 이라는 하나의 질문이 네 개의 독립된 세기 문제 — 곱 안에 2, 3, 5, 67이 각각 몇 개 있는가 — 로 갈라지고, m 은 그 넷 중 최솟값이다. 도구 #14 (극단의 원리)는 두 번 등장한다: pow 자체가 n 의 가장 큰 소수로 정의되고, 최종 답은 소수들에 대한 최솟값이다. 도구 #15 (다르게 정리하기)는 위압적인 곱을 정렬된 집계로 바꾼다: n 을 2부터 5300까지 훑는 대신, 가장 큰 소수가 무엇인지에 따라 n 을 묶는다. 이어서 도구 #2 (빠짐없이 나열하기)와 도구 #3 (가능성 지우기)으로 67 기여자를 층별로 정확히 세면서 더 큰 소수를 몰래 품은 것들을 걸러낸다. 도구 #9 (더 쉬운 문제로 줄이기)는 작은 소수 셋을 다룬다: 정확한 집계는 필요 없고 각각이 67의 집계를 넘는다는 것만 보이면 되는데, 여유가 생각보다 얇아서 이 확인은 장식이 아니라 반드시 해야 하는 단계가 된다.
네 소수의 세기로 쪼개기
나누는 수가 네 소수로 쪼개진다.
사슬의 세기는 가장 약한 고리로 정해지고, 네 소수가 각각 하나의 고리다.
사슬은 가장 약한 고리만큼만 튼튼하며, 네 소수가 저마다 하나의 고리다.
▸ 왜?
모든 수의 소인수 조리법은 하나뿐이므로, 네 소수는 완전히 따로 세어진다.
▸ 왜?
전체 곱은 가장 모자란 재료가 허락하는 만큼만 올라갈 수 있으므로, 가장 작은 개수가 결정한다.
가장 큰 소수로 항 분류하기
각 수는 자기 최대 소인수에만 기여한다.
각 n 은 자기 몫 전부를 가장 큰 소수라는 이름표가 붙은 통 하나에 넣으므로, 통끼리 섞이지 않는다.
8.EE.A.1Organize Information In More Ways67 기여자를 모두 기술하기
기여자들이 기술 가능한 집합을 이룬다.
n 에서 67을 모두 벗겨내면 남는 것은 더 작은 소수로만 이루어져야 한다. 아니면 67이 가장 큰 소수가 아니게 된다.
4.OA.B.4Identify Subproblemsa = 1 층 세기
첫 층이 75를 준다.
80 아래에서는 67 보다 큰 소수가 합성수 안에 숨을 자리가 없으므로, 그 큰 소수 자신만 걸러진다.
6.NS.B.2Eliminate Possibilitiesa = 2 층 세기
둘째 층이 2를 더한다.
4489는 곱 안에 67을 하나 숨긴 것이 아니라 둘 숨긴 것이다. pow는 소수만이 아니라 거듭제곱 전체를 남기기 때문이다.
6.EE.A.1Make A Systematic List2의 개수 확인 — 아슬아슬한 쪽
2의 개수가 아슬아슬한 경쟁자다.
가장 큰 소수가 2 인 수는 2의 거듭제곱뿐이라 이 집계는 짧은 합이고, 그 값이 67의 개수를 간신히 넘는다.
6.EE.A.1Extreme Principle3과 5의 개수 확인
나머지 두 소수는 넉넉히 크다.
작은 소수는 큰 소수보다 훨씬 많은 수의 가장 큰 소수가 되므로, 그 집계가 멀찍이 앞서 나간다.
8.EE.A.1Solve An Easier Related Problem최솟값 취하기
가장 작은 개수는 77, 보기 (D).
가장 귀한 재료가 요리를 몇 인분 만들 수 있는지를 정한다.
7.EE.B.4Extreme Principle2010=2 · 3 · 5 · 67 이므로 소수마다 따로 세고 가장 작은 값을 고르면 된다. 67이 77 에서 먼저 바닥나고, 2는 정확히 하나 남기고 살아남는다.
- 네 소수의 세기로 쪼개기
- 가장 큰 소수로 항 분류하기
- 67 기여자를 모두 기술하기
- a = 1 층 세기
- a = 2 층 세기
- 2의 개수 확인 — 아슬아슬한 쪽
- 3과 5의 개수 확인
- 최솟값 취하기