[AOPS - 직접 풀이] #001. 더블카운팅

안녕하세요 탐레프입니다!

첫 포스팅을 뭘로 할까 고민하다가, 시간도 없고 해서 그냥 간단한 문풀 포스팅을 하려고 해요. 아직 LaTeX를 못 익혀서 결국 다음 수식편집기로 하겠지만요...라고 다짐하다가 다음 수식편집기가 펑하고 터져서 결국 모르는 텍을 부랴부랴 배워서 포스팅했습니다. 그 때문에 가독성은... 광팡팡

...텍 익히고 고칠게요.

------------------------------------------------------------------------------------

문제는 다음과 같습니다!

"교실에 n명의 학생이 있다. 이 때 각 학생은 10명 또는 11명의 친구를 가지고 있으며, 아무렇게나 두 학생을 잡았을 때 그들과 공통으로 친구인 학생이 정확히 5명 있다. 이 때 가능한 학생의 수를 모두 구하시오!"

---------------------------------------------------

[SOL]

(표기)

친구 관계는 양방항 관계이므로, "학생 A와 학생 B는 친구이다"라는 명제를 

$A-B$ 라고 정의하자.

집합 S를 

$S=\{ (x,y,z) | x-z, y-z \}$라고 잡고, S의 원소를 세도록 하자.

관점 1) z는 x, y의 공통된 친구이다!

따라서 아무렇게나 학생 x, y를 잡는 경우의 수가 $\begin{pmatrix}n\\2\end{pmatrix}$가지이고, 그들의 공통친구가 각각 5명이므로,

$|S|=5\cdot\begin{pmatrix}n\\2\end{pmatrix}=\frac{5n(n-1)}{2}$이다.

관점 2) x, y 모두 z의 친구이다!

따라서 x, y는 z의 친구 중 아무렇게나 둘을 고른 것이다.

따라서 학생 z를 잡는 경우의 수가 $n$이고, 친구 10명 또는 11명 중 2명을 고르는 것이므로, $45n\le |S|\le 55n$이 된다.

따라서 관점 1과 관점 2를 연립하면 $19\le n\le 23$이 된다.

이 때, 10명의 친구를 가지는 학생이 $k$명이라고 하면, 전체 친구 관계의 수, 즉 그래프로 따질 때 차수의 합은 $55n-10k$개가 되므로,$n$이 홀수라면 

차수의 합이 홀수가 되어 악수정리에 모순이다. 

따라서, 가능한 $n=20,22$뿐이다.

이 둘의 실례는 나도 잘 모르겠다. 짐작이 가는 게 있기는 하지만....

수잘알 분들 도와주세요!

---------------------------------------------------

이렇게 첫 수학 포스팅을 어떻게 잘 마쳤습니다... 볼만하셨나요?

혹시나 모르는 게 있으시다면, 질문 달아주시면 24시간 안에 답변해드릴테니 부담 갖지 마시고 물어봐 주세요.

탐레프였습니다!