20230312 이산수학 6일차_계수와 비둘기집 원리 [이상준 경희대 수학과 교수]

비둘기집 원리는 한정된 공간에 어떤 다른 원소들을 채우려고 할때 최소한 어느정도의 경우를 생각해야 하는가의 문제이다.
이상준 교수는 이 원리의 이름을 가지고 재밌는 일화를 알려줬는데 이 개념의 이름이 왜 피죤! 비둘기 원리를 불리는 가에 대해 설명해줬다.

용산에 정사각형둘이 서로 붙어있는 외벽 디자인인 건물이 있었는데 거기에 특이하게도 정사각형 당 비둘기가 한마리 혹은 두마리씩 앉아 있는거였다.
비둘기 특성상 공간을 공유하지 않고, 서로 다른 공간을 한마리씩 쓰는 습성이 있었던 거다.

그런 비둘기 습성 처럼, 컴퓨터 구조에서 특히 데이터는 특정 주소값을 가지는데 데이터가 비둘기라고 하면 데이터의 공간이 비둘기집이 아닐까싶다.
하여튼, 문제 예시에서

비둘기가 13마리, 비둘기집이 12개에 비둘기를 넣는다고 하면 적어도 하나의 방에는 비둘기가 두마리 이상 들어간다고 한다.

라는 가정법에서

귀류법으로 증명을 한다면,
두마리 이상 들어간 집이 없다고 치면, 집에 한마리씩 넣었을 때 총 12마리 비둘기만 집을 가지게 되어서
한 개의 집은 꼭 두마리가 되어야 하는 상황이라 위 가정은 참이다.

평균값 증명으로도 가능한데,
13을 12로 나누면 1.XXX라는 값이 나올거고, 평균적으로 1 이상의 비둘기가 한 집에 들어가는 경우가 있으니, 위 가정이 참이라고 할 수 있다.

위는 아주 기본적인 비둘기 원리의 예시이고, 컴퓨터 연결선 예시로 문제를 풀어볼 수도 있다.

서버실습실에 서버가 10대, 워크스테이션이 15대라고 했을 때, 서버는 한대의 워크스테이션만 작동시킬 수 있다. 10대 이하의 워크스테이션이 늘 작동하게 하려면 최소 연결선이 얼마나 필요한가.

정답은 60이었는데, 10대 서버와 10대 워크스테이션을 일대일로 연결하고, 나머지 5개는 10대의 서버에 다 연결 시켜놓으면 되는 것이었다.