비둘기집 원리 계산기

물건 n개를 상자 k개에 나눠 담으면, 어떻게 나누더라도 적어도 한 상자에는 ⌈n/k⌉(n/k를 올림한 값)개 이상 들어간다는 원리입니다. 흔히 "비둘기 n+1마리를 집 n개에 넣으면 한 집에 두 마리 이상"이라는 형태로 알려져 있는데, 이는 n=n+1, k=n인 특수한 경우입니다.

반증으로 증명됩니다. 모든 상자가 ⌈n/k⌉−1개 이하만 담았다고 가정하면 전체 개수는 최대 k·(⌈n/k⌉−1)개인데, 이 값은 항상 n보다 작습니다. 그런데 물건은 전부 n개를 담아야 하므로 모순이 생기고, 따라서 적어도 한 상자는 ⌈n/k⌉개 이상을 담아야 합니다.

n이 k로 나누어떨어지면 그렇습니다. 이때는 물건을 정확히 n/k개씩 고르게 나눌 수 있어서, 그 이상을 보장할 방법이 없습니다. 나누어떨어지지 않으면 몫보다 하나 더 담는 상자가 최소 하나는 생길 수밖에 없습니다.

예를 들어 "동시에 태어난 두 사람이 있을 확률"(생일 문제), 해시 충돌이 반드시 일어나는 최소 데이터 개수, 나머지가 같은 두 수가 반드시 있다는 것을 보이는 정수론 문제 등에서 자주 등장합니다.

모든 물건이 그 하나의 상자에 들어가야 하므로 최소 보장값은 물건 개수 n 그대로입니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.