AMC 10 · 2011 · #11

학년 6 arithmetic

유형 Modular Cycle Frequency Count └ 세부 유형 Floor Count Across Residue Bins

pigeonhole-principlefloor-function extremal-construction ↑ 선수 지식: floor-function

📏 중간 풀이 💡 2 개 인사이트

문제

한 방에 $52$ 명의 사람이 있다. "이 방에 있는 사람들 중 적어도 $n$ 명은 생일이 같은 달에 속한다"라는 명제가 항상 참이 되도록 하는 $n$ 의 최댓값은 얼마인가?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

AMC 10 2011 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $52$명이 있는 방에서 각 사람의 생일은 $12$개월 중 한 달에 들어간다. 생일이 어떻게 분포하든 "같은 달에 태어난 사람이 적어도 $n$명 있다"는 문장이 항상 참이 되도록 하는 가장 큰 $n$을 구하라.

주어진 것: 방에 $52$명이 있다.; 모든 생일은 한 해의 $12$개월 중 한 달에 속한다.; "항상 참"이므로 어떤 분포에서도 예외 없이 성립해야 한다.; 선택지: (A) $2$, (B) $3$, (C) $4$, (D) $5$, (E) $12$.

구하는 것: 어떤 달이 반드시 적어도 $n$명을 포함하게 되는 가장 큰 $n$.

이해

계획

주요 도구: #14 극단의 원리

보조 도구: #3 가능성 지우기

"어떤 경우에도 보장된다"는 도구 #14(극단의 원리)의 신호다. 모든 달을 최대한 적게 유지하려고 애쓰는 분포를 상상하고, 그런 경우에도 가장 붐비는 달이 어쩔 수 없이 도달하는 인원을 살핀다. 가장 공평한 분배는 사람을 달마다 최대한 고르게 나누어 찾는다. 이어서 도구 #3(가능성 지우기)으로, 가장 붐비는 달이 정확히 이 값인 분포가 실제로 존재함을 보여 그보다 큰 값은 보장될 수 없음을 확정한다.

실행 — 정답: D

#14 극단의 원리 6.EE.B.5 단계 1

가장 공평한 분배를 목표로

무엇이 보장되는지 알려면 문장에 가장 강하게 맞서는 분포를 떠올린다.
$52$개의 생일을 $12$개월에 최대한 고르게 펼치는 것이다.
이렇게 가장 균형 잡힌 분포조차 어떤 달을 $n$명으로 밀어 올린다면, 모든 분포가 그렇게 된다.
한쪽으로 치우친 분포는 한 달에 더 많이 쌓을 뿐이기 때문이다.

$$52 \text{ 명} \longrightarrow 12 \text{ 개월에 최대한 고르게}$$

💡 항상 성립해야 하는 주장은 가장 인색한 분포가 결정하므로, 그 분포를 먼저 만든다.

#14 극단의 원리 4.NBT.B.6 단계 2

사람을 달마다 나누기

$52$를 $12$로 나누어 고르게 배분한다.
몫은 $4$, 나머지는 $4$다.
즉 $12$개월이 각각 $4$명씩 가져가 $12 \times 4 = 48$명을 쓰고, $4$명이 남는다.

$$52 \div 12 = 4 \text{ 나머지 } 4 \quad (12 \times 4 = 48,\ \ 52 - 48 = 4)$$

💡 나눗셈은 고른 기준선을 알려 주고, 나머지는 고르게 나눌 수 없는 부분이다.

#14 극단의 원리 4.OA.A.3 단계 3

남은 사람 배치하기

남은 $4$명도 어느 달엔가 들어가야 하고, 한 명씩 어떤 달을 $4$명에서 $5$명으로 끌어올린다.
이 가장 공평한 분배에서도 네 개의 달이 $5$명을 갖게 된다.
따라서 생일이 어떻게 분포하든 어떤 달은 반드시 적어도 $5$명을 갖는다.

$$4 \text{ 개월} \to 5 \text{ 명}, \quad 8 \text{ 개월} \to 4 \text{ 명}$$

💡 남은 사람은 사라질 수 없어, 하나씩 어떤 달을 고른 기준선 위로 밀어 올린다.

#3 가능성 지우기 3.OA.A.3 단계 4

$6$은 강제되지 않음을 확인

$6$을 보장할 수 있을까?
없다.
여덟 달이 $4$명, 네 달이 $5$명인 분배는 $8 \times 4 + 4 \times 5 = 32 + 20 = 52$로 이미 모두를 담고, 그 가장 붐비는 달은 $5$명뿐이다.
가장 큰 달이 $5$인 분포가 존재하므로 $6$은 항상 도달하지는 않는다.
따라서 항상 참인 가장 큰 값은 $5$, 즉 선택지 (D)다.

$$8 \times 4 + 4 \times 5 = 32 + 20 = 52 \;\Rightarrow\; \max = 5 \;\Rightarrow\; \textbf{(D)}$$

💡 한 유효한 분포가 $5$에서 멈춘다면 $6$은 피할 수 있으니, 약속할 수 있는 최대는 $5$다.

[1] #14 6.EE.B.5 무엇이 보장되는지 알려면 문장에 가장 강하게 맞서는 분포를 떠올린다. $52$개의 생일을 $12$개월에 최대한 고르게 펼치는 것이다. 이렇게 가

[2] #14 4.NBT.B.6 $52$를 $12$로 나누어 고르게 배분한다. 몫은 $4$, 나머지는 $4$다. 즉 $12$개월이 각각 $4$명씩 가져가 $12 \times 4

[3] #14 4.OA.A.3 남은 $4$명도 어느 달엔가 들어가야 하고, 한 명씩 어떤 달을 $4$명에서 $5$명으로 끌어올린다. 이 가장 공평한 분배에서도 네 개의 달이

[4] #3 3.OA.A.3 $6$을 보장할 수 있을까? 없다. 여덟 달이 $4$명, 네 달이 $5$명인 분배는 $8 \times 4 + 4 \times 5 = 32 + 2

검토

합리성 확인: 한 달당 평균 인원은 $52 \div 12 \approx 4.3$명이므로 가장 붐비는 달은 적어도 그다음 자연수인 $5$명이어야 한다. 답과 일치한다. 선택지도 이를 자연스럽게 감싼다. $2$, $3$, $4$는 보장할 수 있는 최댓값이라기엔 너무 약하고, $12$는 각 달에 $12$명씩 들어가려면 최소 $52$명보다 훨씬 많아야 하므로 불가능하다.

대안 접근: 비둘기집 원리를 곧바로 쓴다. 비둘기 $52$마리를 둥지 $12$개에 넣으면 어떤 둥지는 적어도 $\left\lceil \dfrac{52}{12} \right\rceil = \lceil 4.33\ldots \rceil = 5$마리를 갖는다. 몫의 올림값이 보장되는 최솟값을 한 번에 주며, 다시 $5$, 즉 (D)가 나온다.

사용된 CCSS 표준 (최저 학년 6)

6.EE.B.5 방정식이나 부등식을 참이 되게 하는 값을 찾는 과정으로 이해하기 ("항상 참이 되는 가장 큰 $n$"을 경계 조건으로 읽고, 최악의 분포가 여전히 만족하는 $n$ 값을 따지는 데 사용.)
4.NBT.B.6 네 자리 이하의 나눗셈에서 몫과 나머지 구하기 ($52 \div 12 = 4$ 나머지 $4$를 계산해 고른 기준선과 남는 인원을 찾는 데 사용.)
4.OA.A.3 네 연산을 이용한 여러 단계 문장제 해결하기 (남은 $4$명이 각각 어떤 달을 $4$명에서 $5$명으로 밀어 올려 가장 붐비는 달이 $5$가 됨을 추론하는 데 사용.)
3.OA.A.3 100 이내의 곱셈과 나눗셈 문장제 해결하기 ($8 \times 4 + 4 \times 5 = 52$를 확인해 최댓값이 $5$인 분포가 실제로 존재함을 보여 $6$을 배제하는 데 사용.)

⭐ 최대한 고르게 나눠도 남는 것들이 가장 꽉 찬 칸을 위로 밀어 올린다. 그래서 $52$명을 $12$개월에 나누면 언제나 어떤 달에 $5$명이 몰린다.