AMC 10 · 2010 · #25

학년 11 countinggeometry-2d
cyclic-quadrilateralpolygon-inequalitystars-and-barsprinciple-of-inclusion-exclusionburnsides-lemma complementary-countingsymmetry-argument ↑ 선수 지식: cyclic-quadrilateral
📏 긴 풀이 💡 4 개 인사이트
문제
정수인 네 변의 합이 정해져 있고 네 꼭짓점이 한 원 위에 있다. 서로 다른 도형의 수를 세어라.

답을 골라 클릭하세요.

(A)
560
(B)
564
(C)
568
(D)
1498
(E)
2255
풀이 과정
전략 관점 바꾸기

원도 무수히 많고 놓는 자리도 무수히 많으므로, 도형을 유한한 무언가로 바꾸기 전에는 셀 수가 없다. 도구 #16(관점 바꾸기)이 그 역할을 한다. 네 변의 길이를 반시계 방향으로 읽으면 사각형은 구슬 네 개짜리 목걸이 (a,b,c,d)가 되고, 네 번의 순환 이동을 같은 것으로 본다. 이 맞바꿈이 정당하려면 목걸이가 도형의 완전한 대역이어야 하고, 그러려면 서로 다른 두 도형이 같은 목걸이를 갖지 않는다는 것과 정당한 목걸이는 모두 실제 도형으로 실현된다는 것, 두 가지를 각각 증명해야 한다. 둘 다 결정적이고 둘 다 건너뛰기 쉽다. 도구 #7(작은 문제로 쪼개기)이 첫째를 준다. 대각선으로 자르면 코사인법칙이 한 각을, 따라서 도형 전체를 확정한다. 도구 #14(극단의 원리)가 둘째의 경계를 준다. 도형은 어떤 코사인 값이 [-1,1] 안에 엄격히 머무는 동안에만 존재하고, 그 조건은 '모든 변이 15 이하'로 번역된다. 도구 #1(그림 그리기)은 삼각형 두 개를 다시 붙여 그 도형이 정말로 있음을 보인다. 세기는 그다음이며, 도구 #16은 여백을 세는 방식으로 전체 4-순서쌍에서 큰 변이 있는 것을 뺀다. 마지막 단계가 보기 세 개를 갈라놓는다. 목걸이 세기는 '4로 나누기'가 아니다. 순환 이동으로 자기 자신이 되는 목걸이가 몇 개 있기 때문이다. 그래서 도구 #2(빠짐없이 나열하기)로 순서쌍을 회전대칭 정도에 따라 분류한다. 도구 #3과 #15는 함정 보기를 지우고 다른 방식으로 다시 세어 마무리한다.

1STEP 1

도형을 목걸이로 바꾸기

세는 대상은 순환 목록이다.

(a,b,c,d) ∼ (b,c,d,a) ∼ (c,d,a,b) ∼ (d,a,b,c), a+b+c+d=32, a,b,c,d는 양의 정수
2STEP 2

목걸이가 도형을 확정한다

원 위에서는 목록이 도형을 결정한다.

AC²=a²+b²-2abcos B=c²+d²+2cdcos B ⟹ cos B=(a²+b²-c²-d²)/(2(ab+cd))
3STEP 3

어떤 목걸이가 가능한가

어떤 변도 나머지 을 넘지 않으면 목록이 가능하다.

|t| < 1⇔ |a-b| < c+d 이고 a+b > |c-d| ⇔ 모든 변 < 나머지 세 변의 합 ⇔ 1 ≤ a,b,c,d ≤ 15
4STEP 4

가능한 목걸이는 모두 실제로 만들어진다

가능한 목록은 모두 실제로 어떤 도형이 만든다.

cos∠ B=t, cos∠ D=-t, ∠ B+∠ D=180^° ⟹ A,B,C,D 가 그 순서로 한 원 위에 있다
5STEP 5

먼저 순서쌍을 세기

먼저 순서쌍을 세면 2255다.

C(31, 3)-4C(16, 3)=4495-2240=2255개의 가능한 순서쌍
6STEP 6

회전대칭으로 분류하기

회전대칭이 그것을 세 묶음으로 나눈다.

크기 1인 목록 1개, 14/2=7개의 크기 2인 목록, 2240/4=560개의 크기 4인 목록
7STEP 7

세 묶음을 더하기

묶음을 더하면 568, 보기 (C).

560+7+1=568 (C)
8STEP 8

대칭 유형으로 다시 세기

대칭 유형으로 다시 세도 568이다.

1 · 1+4 · 1+7 · 2+45 · 3+69 · 6=1+4+14+135+414=568
정답
568
서로 독립인 세 가지 점검이 일치한다. 첫째, 범위로 가두기. 가능한 2255개의 순서쌍 중 2240개는 정확히 크기 4인 묶음에 들어가 사각형 560개를 만들고, 남은 15개는 많아야 15개, 적어도 1개를 더할 뿐이므로 총합은 [561,575]에 갇힌다. 이것만으로 (A) 560, (D) 1498, (E) 2255가 지워지고 568은 그 안에 편안히 들어간다. (B) 564는 남지만, 대칭적인 순서쌍 15개를 실제로 묶어 1+7=8을 얻는 순간 568로 확정된다. 둘째, 궤도 세기(번사이드) 항등식. 네 번의 이동 각각이 고정하는 순서쌍의 수를 평균하면 항등이동은 2255개, 한 칸 이동은 1개, 두 칸 이동은 15개, 세 칸 이동은 1개이므로 (2255+1+15+1)/4=2272/4=568이다. 여기서 568 · 4=2272=2255+17은 진짜 산술 제약이어서 틀린 총합이면 어긋난다. 셋째, 문장 표현에 대한 민감도 점검. 거울상까지 같은 것으로 본다면 군의 원소가 넷이 아니라 여덟이 되어 개수가 316으로 떨어지는데, 이는 보기에 없다. 즉 문제의 '회전과 평행이동'은 실제로 일을 하고 있으며, 이를 그냥 합동으로 읽으면 다른 문제가 된다.
💡핵심 정리

원에 내접한 사각형은 변 네 개의 순환 순서만으로 완전히 결정되므로 도형 세기는 사실 구슬 네 개짜리 목걸이 세기이고, 목걸이 세기는 결코 그냥 4로 나누는 일이 아니다.

  • 도형을 목걸이로 바꾸기
  • 목걸이가 도형을 확정한다
  • 어떤 목걸이가 가능한가
  • 가능한 목걸이는 모두 실제로 만들어진다
  • 먼저 순서쌍을 세기
  • 회전대칭으로 분류하기
  • 세 묶음을 더하기
  • 대칭 유형으로 다시 세기