AMC 10 · 2012 · #23
학년 7 counting애덤, 베닌, 치앙, 디숀, 에스더, 피오나는 인터넷 계정을 가지고 있다. 이들 중 일부는 서로 인터넷 친구이지만 전부가 그런 것은 아니며, 이 그룹 밖에 인터넷 친구를 둔 사람은 아무도 없다. 이들은 각자 같은 수의 인터넷 친구를 가지고 있다. 이런 일이 일어날 수 있는 서로 다른 경우의 수는 몇 가지인가?
답을 골라 클릭하세요.
AMC 10 2012 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.
도구 + CCSS 풀이
이해
문제 재정리: 여섯 명이 서로 인터넷 친구가 될 수 있다. 친구 관계는 서로에게 똑같이 적용된다. 즉 내가 네 친구면 너도 내 친구다. 모두가 모두와 친구인 것은 아니고, 이 여섯 명 밖에 친구가 있는 사람도 없다. 이들을 묶는 단 하나의 규칙은, 여섯 명 모두가 정확히 같은 수의 친구를 가진다는 것이다. 이 조건을 만족하는 친구 관계 배치가 몇 가지인지 세어라.
주어진 것: 사람은 정확히 $6$명이다: ì ë¤, ë² ë, ì¹ì, ëì, ìì¤ë, í¼ì¤ë; 친구 관계는 서로 대칭이다 (순서 없는 쌍); 모든 사람의 친구 수가 서로 같다; "모두가 아니라 일부"만 친구다 — 친구인 쌍이 적어도 하나는 있지만, 가능한 모든 쌍이 친구인 것은 아니다; 선택지: (A) $60$, (B) $170$, (C) $290$, (D) $320$, (E) $660$
구하는 것: 조건을 모두 만족하는 서로 다른 친구 관계 배치(누가 누구와 친구인지)의 개수
이해
문제 재정리: 여섯 명이 서로 인터넷 친구가 될 수 있다. 친구 관계는 서로에게 똑같이 적용된다. 즉 내가 네 친구면 너도 내 친구다. 모두가 모두와 친구인 것은 아니고, 이 여섯 명 밖에 친구가 있는 사람도 없다. 이들을 묶는 단 하나의 규칙은, 여섯 명 모두가 정확히 같은 수의 친구를 가진다는 것이다. 이 조건을 만족하는 친구 관계 배치가 몇 가지인지 세어라.
주어진 것: 사람은 정확히 $6$명이다: ì ë¤, ë² ë, ì¹ì, ëì, ìì¤ë, í¼ì¤ë; 친구 관계는 서로 대칭이다 (순서 없는 쌍); 모든 사람의 친구 수가 서로 같다; "모두가 아니라 일부"만 친구다 — 친구인 쌍이 적어도 하나는 있지만, 가능한 모든 쌍이 친구인 것은 아니다; 선택지: (A) $60$, (B) $170$, (C) $290$, (D) $320$, (E) $660$
계획
주요 도구: #2 빠짐없이 나열하기
보조 도구: #16 관점 바꾸기, #1 그림 그리기, #4 변수 도입하기, #7 작은 문제로 쪼개기
"몇 가지"를 묻는 세기 문제이므로 도구 #2(빠짐없이 나열하기)가 뼈대다. 공통 친구 수 $k$로 경우를 나눠 각각을 깔끔히 나열한다. 먼저 도구 #4(변수 도입하기)로 $k$를 이름 짓고 $\{1,2,3,4\}$로 좁힌다. 그다음 도구 #16(관점 바꾸기)이 큰 짐을 덜어 준다. 모든 친구를 비친구로, 비친구를 친구로 뒤집으면 친구 $k$명짜리 배치가 친구 $5-k$명짜리 배치로 바뀌므로, $k=1$의 개수가 $k=4$의 개수와 같고 $k=2$의 개수가 $k=3$의 개수와 같아 일이 절반으로 준다. 도구 #1(그림 그리기)은 $k=2$의 모양(삼각형들과 육각형)을 눈에 보이게 해 빠뜨리거나 겹쳐 세지 않도록 한다. 도구 #7(작은 문제로 쪼개기)은 마무리를 깔끔히 한다. $k=1$을 세고, $k=2$를 세고, 각각 두 배로 만들어 더한다.
실행 — 정답: B
6.EE.A.2 단계 1 공통 친구 수에 이름 붙이기
- 여섯 명을 여섯 개의 점으로, 친구 관계를 두 점을 잇는 선으로 그린다.
- "모두가 같은 수의 친구를 가진다"는 것은 모든 점에서 나오는 선의 개수가 같다는 뜻이다.
- 그 공통 개수를 $k$라 하자.
- 한 사람은 나머지 $5$명과만 친구가 될 수 있다.
- 문제에서 친구인 쌍이 있으므로 $k\neq 0$, 모든 쌍이 친구는 아니므로 $k\neq 5$이다.
- 그러면 정확히 네 가지 경우가 남는다.
💡 공통 친구 수에 $k$라는 하나의 이름을 붙이면 흐릿한 조건이 셀 수 있는 네 가지 경우로 바뀐다.
7.SP.C.8 단계 2 친구 관계를 뒤집어 경우를 짝짓기
- 임의의 올바른 배치를 뒤집는다.
- 친구였던 모든 쌍은 남남이 되고, 남남이던 모든 쌍은 친구가 된다.
- $k$명의 친구가 있던 사람은 $5-k$명과 남남이었으므로, 뒤집은 뒤에는 친구가 $5-k$명이 된다.
- 이 역시 "모두 같은 수" 조건을 만족하는 올바른 배치다.
- 뒤집기는 되돌릴 수 있으므로 배치들을 일대일로 대응시킨다.
- 따라서 $k=1$ 배치의 개수는 $k=4$ 배치의 개수와 같고, $k=2$ 배치의 개수는 $k=3$ 배치의 개수와 같다.
- 그러므로 $k=1$과 $k=2$만 세고 각각 두 배로 하면 된다.
💡 "친구"와 "남남"을 맞바꾸면 $k$가 $5-k$로 바뀌면서도 개수가 같은 성질은 그대로라, 어려운 절반이 쉬운 절반을 그대로 비춘다.
3.OA.C.7 단계 3 k = 1 세기: 세 쌍으로 나누기
- 모두 친구가 정확히 $1$명이면, 여섯 명은 다른 선 없이 $3$개의 서로 떨어진 친구 쌍으로 나뉜다.
- 이 짝짓기를 빠짐없이 센다.
- ì ë¤은 자기 한 명의 친구를 고를 때 $5$가지 선택이 있다.
- 이제 아직 짝이 없는 사람 중 이름 순서가 가장 앞선 사람을 보면 남은 선택은 $3$가지다.
- 마지막 두 사람은 서로 친구가 될 수밖에 없어 $1$가지다.
- 서로 독립인 선택들을 곱한다.
💡 한 번에 한 사람씩 짝을 고르며, 각 선택이 서로 독립이므로 개수는 그냥 곱해진다.
7.SP.C.8 단계 4 k = 2, 첫 번째 모양: 삼각형 두 개
- 모두 친구가 정확히 $2$명이면 각 점에 선이 두 개씩이라, 선들은 모든 점을 쓰는 닫힌 고리를 이룬다.
- 점이 여섯 개면 고리는 삼각형 두 개($3$짜리 고리 둘)이거나 $6$짜리 큰 고리 하나다.
- 길이 $1$이나 $2$인 고리는 불가능하다.
- 먼저 삼각형 두 개를 다룬다.
- 여섯 명을 세 명씩 두 무리로 나눠 각 무리를 서로 친구인 삼각형으로 만드는 것은, 어느 세 명이 한 삼각형을 이루는지 고르는 것과 같다.
- 나머지 세 명은 자동으로 정해진다.
- $6$명 중 $3$명을 고르는 것은 $\binom{6}{3}=20$가지지만, 이는 각 나눔을 두 번씩 센다(무리 $A$를 고르든 무리 $B$를 고르든 같은 나눔이다).
- 그래서 $2$로 나눈다.
💡 세 명 무리에서 친구 $2$명 모양은 삼각형뿐이라, 한 삼각형에 누가 들어갈지만 고르면 되고 각 나눔은 두 번 불린다.
4.OA.A.3 단계 5 k = 2, 두 번째 모양: 육각형 하나
- 다른 차수 $2$ 모양은 여섯 명 전체를 지나는 고리 하나 — 육각형이다.
- 각 사람이 고리에서 양옆 두 이웃과 친구다.
- 이 고리들을 센다.
- 여섯 명을 원 둘레에 늘어놓는 순서는 $6! = 720$가지다.
- 그러나 같은 친구 고리가 여러 번 세어진다.
- 원을 돌려 $6$개의 시작 위치 어디로 맞춰도 같은 친구 관계이고, 시계 방향이든 반시계 방향이든($2$가지) 같은 친구 관계다.
- 이 중복을 나눠 없앤다.
- 두 모양을 더해 $k=2$ 전체 개수를 얻는다.
💡 친구 고리는 어디서 읽기 시작하든 어느 방향으로 읽든 상관없으므로, 그 $6\times 2$개의 닮은꼴이 하나로 뭉쳐진다.
4.OA.A.3 단계 6 각 경우를 두 배로 하고 더하기
- 2단계의 뒤집기에 따라 $k=4$는 $k=1$과 개수가 같고 $k=3$은 $k=2$와 개수가 같다.
- 그래서 네 경우를 합하면 $N_1 + N_2 + N_3 + N_4 = 2N_1 + 2N_2$이다.
- $N_1 = 15$, $N_2 = 70$을 대입한다.
💡 여집합 짝짓기 덕분에 두 경우만 계산해 거울처럼 반사하면 되므로, 총합은 그 둘의 합의 두 배일 뿐이다.
6.EE.A.2 여섯 명을 여섯 개의 점으로, 친구 관계를 두 점을 잇는 선으로 그린다. "모두가 같은 수의 친구를 가진다"는 것은 모든 점에서 나오는 선의 개 7.SP.C.8 임의의 올바른 배치를 뒤집는다. 친구였던 모든 쌍은 남남이 되고, 남남이던 모든 쌍은 친구가 된다. $k$명의 친구가 있던 사람은 $5-k$명과 3.OA.C.7 모두 친구가 정확히 $1$명이면, 여섯 명은 다른 선 없이 $3$개의 서로 떨어진 친구 쌍으로 나뉜다. 이 짝짓기를 빠짐없이 센다. ì ë¤ 7.SP.C.8 모두 친구가 정확히 $2$명이면 각 점에 선이 두 개씩이라, 선들은 모든 점을 쓰는 닫힌 고리를 이룬다. 점이 여섯 개면 고리는 삼각형 두 개( 4.OA.A.3 다른 차수 $2$ 모양은 여섯 명 전체를 지나는 고리 하나 — 육각형이다. 각 사람이 고리에서 양옆 두 이웃과 친구다. 이 고리들을 센다. 여섯 4.OA.A.3 2단계의 뒤집기에 따라 $k=4$는 $k=1$과 개수가 같고 $k=3$은 $k=2$와 개수가 같다. 그래서 네 경우를 합하면 $N_1 + N_2 검토
합리성 확인: 합계 $170$은 선택지 $60$과 $290$ 사이에 있고, 어떤 부분 개수와도 같지 않아 한 경우만 성급히 답하면 여기에 닿지 않는다. 부분 개수를 교차 확인하면, $k=1$은 완전 짝짓기 $15$가지이고 이는 이중계승 $5!! = 5\cdot 3\cdot 1 = 15$와 일치한다. $k=2$의 $6$-고리 개수는 잘 알려진 $\frac{(6-1)!}{2} = \frac{120}{2} = 60$과 맞고, 삼각형 두 개 나눔은 $10$이라 $N_2 = 70$이다. 두 배로 하여 더하면 $2(15+70) = 170$이다. 여집합 대칭도 자기 정합적이다. 네 경우의 개수는 $15, 70, 70, 15$로 가운데를 중심으로 대칭이며, 이는 친구와 남남을 뒤집는 논리가 예측하는 그대로다.
대안 접근: 여집합 지름길을 쓰지 않고 네 경우를 직접 세어도 된다. 위에서처럼 $k=1$은 $15$, $k=2$는 $70$이다. $k=4$는 각 사람이 정확히 다른 $1$명과 남남이므로 "남남" 선들이 $3$쌍을 이루어 $k=1$과 같은 $15$가지다. $k=3$은 각 사람이 정확히 다른 $2$명과 남남이므로 남남 선들이 삼각형들 또는 육각형을 이루어 $k=2$와 같은 $70$가지다. 합하면 $15+70+70+15 = 170$으로, 대칭 논증에 기대지 않고도 답이 확인되고 왜 뒤집기가 통하는지도 드러난다.
사용된 CCSS 표준 (최저 학년 7)
6.EE.A.2Write, read, and evaluate expressions in which letters stand for numbers (공통 친구 수 $k$에 이름을 붙이고, 조건을 이용해 $\{1,2,3,4\}$로 제한하는 데 사용.)7.SP.C.8Find probabilities of compound events using organized lists, tables, and simulations (경우별로 세기를 정리하고, 친구/남남 뒤집기로 $k$를 $5-k$와 짝짓고, 삼각형 두 개 배치를 나열하는 데 사용.)3.OA.C.7Fluently multiply and divide within 100 ($k=1$ 짝짓기에서 서로 독립인 짝 선택 $5\times 3\times 1 = 15$를 곱하는 데 사용.)4.OA.A.3Solve multi-step word problems using the four operations with whole numbers (육각형 개수 $\frac{720}{12}=60$에서 회전과 반사를 나눠 없애고, 경우들을 두 배로 하여 더해 $170$에 이르는 데 사용.)
⭐ 모두가 같은 수의 친구를 가져야 할 때는 그 공통 수 $k$로 경우를 나눠라. 그러면 "친구"와 "남남"을 맞바꾸면 친구 $k$명이 $5-k$명으로 바뀌는 것을 알아채, 절반의 경우만 세고 두 배로 하면 된다: $2(15+70)=170$.
⭐ 모두가 같은 수의 친구를 가져야 할 때는 그 공통 수 $k$로 경우를 나눠라. 그러면 "친구"와 "남남"을 맞바꾸면 친구 $k$명이 $5-k$명으로 바뀌는 것을 알아채, 절반의 경우만 세고 두 배로 하면 된다: $2(15+70)=170$.
비슷한 유형 더 풀어보기
같은 archetype · 비슷한 학년부터.
