퀴즈 302 풀이

beoped(69)

Published in

#dclick

Words

298

Reading

2 min

Listen

Play

퀴즈 302 모임의 참석자

12 k [12의 배수] 명으로 이루어진 어떤 모임에 각 사람은 3k+6 명의 다른 사람과 인사를 나누었다. 임의의 두 사람에 대하여 이들 모두와 인사를 나눈 사람들의 수는 일정하다.

이 때 이 모임에는 모두 몇 명의 사람들이 있는가?

풀이

이 문제를 푸는 방법은 "더블 카운팅" 이라는
방법인데, 이는 하나의 경우의 수를 두가지 이상의 방법으로 기술하고 거기서 생겨나는 방정식을 풀어 답을 구하는 기술을 말한다.

먼저 문제의 조건을 분석해보자.

임의의 두 사람에 대하여 이들 모두와 인사를 나눈 사람들의 수는 일정하다 이를 해석하는 것이 이 문제의 핵심이다.

임의의 두 사람을 a,b라 하고 이들 모두와 인사를 나눈 사람의 수를 n 명이라 하자

전체 인원수는 12k 이니까 먼저 a,b, 두 사람을 뽑고 12k choose 2 (12k C_2 )그리고 이 두 사람이 동시에 인사를 나눈 사람이 n 명이니까 이 전체 인사를 한 횟수를 N 이라 하면 이 N 은 N=n x 12k C_2 가 된다.

자 이제 전체 악수한 횟수를 다른 방식으로 풀어보자. 먼저 한명을 고려하고 그 뒤 이 사람과 인사를 나눈 두 사람을 뽑으면 이는 저 N 과 같아야 한다.

전체가 12k 명이니까 한명을 뽑을 경우는 12k 가 되고, 이 사람과 인사를 나눈 사람 두명을 뽑을 경우의 수는 [이 사람이 인사를 한 경우가 3k+6 이니] 3k+6 C_2 가 된다. 그래서 총 경우의 수는 N = 12k x (3k+6) C_2 가 된다.

n은 자연수 이니까 3(k+2)(3k+5) 는 12k-1 의 배수가 되어야 한다. 그런데 12k-1 과 3 은 서로소이니까 결국 (k+2)(3k+5) 가 12k-1 의 배수여야 하고, 이를 풀면 45k+40 이 12k-1 의 배수, 이를 풀면 175 가 12k-5 의 배수가 되어야 한다. 175 의 약수 중 12k-1 꼴은 35 뿐이기에 12k=36 이 된다.

풀이과정을 자세히 적으면 다음과 같다.