2. 3인서로사람을 만족하는 최소 인원 찾기
임의의 2명에 대해 서로사람 관계인 어떤 집단이 있다.
이 집단에서 임의의 m명을 뽑으면 그 중에서 어떤 3명이 서로사람이 되는 경우가 반드시 있다고 한다. 이때, m의 최소값을 구하고자 한다.
2.1. m=4일 때
4명 중 어떤 2명에 대해서도 서로사람 관계에 있으며, 4명 중 2명씩 지을 수 있는 관계쌍은 모두 6가지이다. 그들의 관계는 각각 서로 아는 경우(1)이거나 서로 모르는 경우(0)이다.
4명 중 3명에 대해 서로사람이 되는지 조사해야 한다. 이렇게 체크해야할 3명에 대한 쌍을 체크쌍이라고 하자. 그러면, 체크쌍의 수는 4가지이다.
![](images/mantoman_04.png)
4인 관계의 총 수는 2^6인 64개이다.
이 64가지 경우에 대해 각각 4가지 체크쌍으로 조사한다. 이때, 4가지 중에 한 가지라도 3인서로사람이 존재하면 통과이며, 64가지 4인 관계에 대해 모두 통과되면 m은 4로 정답이 되며, 64가지 중 하나라도 3인서로사람이 존재하지 않으면 m은 4보다 커야 한다.
* 사실 64가지 모두 체크해볼 필요는 없다. 중복된 거 빼면 16가지(혹은 그 이하)만 체크해도 충분하며, 이에 대한 건 추후에 기회가 되면 별도로 다룬다.
m=4일 때, 관계번호 13에서 3인서로사람이 존재하지 않음이 아래와 같이 발견되었다.
즉, m은 4보다 커야 한다.
![](images/mantoman_04_2.png)
2.2. m=5일 때
5명 중 2명씩 지을 수 있는 관계쌍은 모두 10가지이다.
5명 중 3명에 대해 서로사람이 되는지 조사해야 하는 체크쌍 역시 10가지이다.
![](images/mantoman_05.png)
5인 관계의 총 수는 2^10인 1024개이다.
이 1024가지 경우에 대해 각각 10가지 체크쌍으로 조사한다. 이때, 10가지 중에 한 가지라도 3인서로사람이 존재하면 통과이며, 1024가지 5인 관계에 대해 모두 통과되면 m은 5로 정답이 되며, 1024가지 중 하나라도 3인서로사람이 존재하지 않으면 m은 5보다 커야 한다.
m=5일 때, 관계번호 237에서 3인서로사람이 존재하지 않음이 아래와 같이 발견되었다.
즉, m은 5보다 커야 한다.
![](images/mantoman_05_2.png)
여기까지 보면 궁금증이 생길 것이다.
기하학적인 방법으로 간단하게 증명할 방법은 없을까? -> 필자는 발견하지 못함.
확인해야할 양이 엄청난데 이걸 어떻게 손으로 일일이 할 수 있을까? -> 그렇다, 필자는 컴퓨터 프로그램을 짜서 계산했다.
원리를 이해했다면 엑셀로도 계산할 수 있다.
그러면, m이 아무리 커져도 프로그램으로 간단하게 계산될까? -> 그건 별도 글에서 다루고자한다.
2.3. m=6일 때
이제 확인해야할 양이 상당히 늘어난다.
관계쌍의 수는 15, 체크쌍의 수는 20, 관계번호의 수는 32768이다.
즉, 32768가지 각각에 대해 20번씩 체크를 해야한다.
![](images/mantoman_06.png)
이번에도 답이 아니면 m=7에 대해서도 조사해야한다. 결과는 다행히 m=6에서 그쳤다.
즉, 임의의 6명을 뽑더라도 그 중 어떤 3명은 서로 알거나 서로 모르는 경우(3인서로사람)가 항상 존재한다.
![](images/mantoman_06_2.png)
3. 정리
문제) 임의의 2명에 대해 그 두 명은 서로 알거나 서로 모르는 사이인 어떤 집단이 있다. 이 집단에서 임의의 m명을 뽑으면 그 중에서 어떤 3명이 서로 알거나 서로 모르는 경우가 항상 존재하는 m의 최소값은 얼마인가?
풀이)
m=4일 경우, 아래와 같은 예외사례(4명 중 어떤 3명을 뽑아도 그 3명이 서로 아는 경우나 서로 모르는 경우가 존재하지 않음)가 있으므로 4는 정답이 아님.
마찬가지로 m=5일 경우에도 아래와 같은 예외사례가 있으므로 5는 정답이 아님.
m=6일 경우, 이러한 예외사례가 없이 임의의 6명에 대해 그 중 3명은 서로 알거나 서로 모르는 경우가 항상 존재한다(이에 대한 증명은 32768가지 경우를 출력하면 되는데 여기선 생략한다).
![](images/mantoman_07_02.png)
정답) 6명
다음 과제
m이 커질수록 체크해야할 수는 급격히 늘어난다.
다행히 3인서로사람에 대한 최소값은 6으로 마무리되었다.
![](images/mantoman_07.png)
그렇다면, 4인서로사람에 대한 m의 최소값은 얼마일까?
최초 작성일 : 2019.2.6