50. Pigeonhole Principle

비둘기집의 원리(Pigeonhole Principle)는 $(n+1)$개의 물건을 $n$개의 상자에 빠짐없이 넣은 경우 최소한 한 개의 상자에는 두 개 이상의 물건이 들어간다는 원리로, 보통 비둘기와 비둘기집에 빗대어 표현하기 때문에 이런 이름을 가지게 되었다. 이를 일반화하면 $n$개의 물건을 $m$개의 상자에 빠짐없이 넣었을 때 $\lceil n/m \rceil$개 이상의 물건이 들어간 상자가 하나 이상 존재한다는 의미가 된다.

 

이 원리를 이용해서 풀 수 있는 문제들의 경우 제대로 접근하지 못하면 괜히 어려운 풀이를 생각하다가 헤매기 쉬우므로 주의해야 한다.

 

[연습문제]

 

BOJ 21099. Four XOR (Platinum V)

$n$개의 수의 범위가 $10$만 이하이므로 여기서 임의로 $2$개의 수를 골랐을 때 그 수들의 XOR 값은 항상 $0$ 이상 $2^{17}$ 미만이다. 이때 $4$개의 수의 XOR 값은 ($2$개의 수의 XOR 값) XOR ($2$개의 수의 XOR 값)과 같으므로 $2$개의 수를 고르는 방법의 수가 $2^{17}$보다 큰 경우 답은 항상 YES이다. 따라서 $n \ge 513$이면 그냥 YES를 출력하면 되고, 그렇지 않은 경우 $2$개의 수의 XOR 쌍을 하나씩 확인하면서 같아지는 경우가 있는지 보면 된다. (원래 선형대수적 특성을 이용해서 답이 항상 YES가 되는 $n$의 범위를 더 줄일 수 있다는 내용이 있었는데, 틀린 것으로 밝혀져서 삭제되었다.)

 

CF 1305C. Kuroni and Impossible Calculation (1600)

$n$이 $m$보다 큰 경우 그중 $m$으로 나눈 나머지가 같은 두 값이 최소 한 쌍 이상 존재해서 답이 $0$이 된다. 그렇지 않다면 $n \le 1000$이므로 가능한 모든 쌍의 곱을 직접 계산하면 된다.

 

CF 1500A. Going Home (1800)

두 수의 합이 최대 $500$만이므로 비둘기집의 원리를 이용할 수 있다. 여기서는 몇 가지 경우를 먼저 처리하는 것이 좋은데, 같은 수가 네 번 이상 등장하는 경우, 두 개의 수가 각각 두 번 이상 등장하는 경우, 한 개의 수가 두 번 이상 등장하는 경우를 차례로 처리하면 모든 수가 서로 다른 경우만 남으므로 가능한 모든 쌍의 합을 하나씩 구하면 서로 다른 합이 최대 $500$만 개밖에 생기지 않으므로 그보다 많은 개수의 쌍을 확인하면 항상 합이 같은 경우가 나온다.

 

CF 1450C1. Errich-Tac-Toe (Easy Version) (2100)

$i$행 $j$열을 $(i, j)$라고 하면 각각의 칸을 $(i+j) \bmod 3$의 값에 따라 세 그룹으로 나눌 수 있다. 이때 세 그룹 중 최소한 한 그룹은 $k/3$개 이하의 X를 포함하고 있으므로 그 그룹에 포함된 X를 모두 O로 바꾸면 그리드는 DRAW 상태가 된다.

 

CF 1450C2. Errich-Tac-Toe (Hard Version) (2300)

Easy Version과 같은 방식으로 칸들을 세 그룹으로 나눈다. 이때 세 그룹 중 한 그룹의 토큰은 모두 X로, 한 그룹의 토큰은 모두 O로 바꾸면 나머지 한 그룹의 토큰들의 상태와 상관없이 그리드를 DRAW 상태로 만들 수 있다. 또한 비둘기집의 원리에 의해 세 그룹에 각각의 상태를 연결하는 $6$가지 방법 중 최소한 하나는 처음 상태에서 k/3개 이하의 토큰만을 반전해서 만들 수 있다. 풀이는 복잡하지 않지만 실제 대회에서 비둘기집의 원리를 적용하는 것이 어려웠기 때문에 C번임에도 *2300을 받은 비운의 문제.

 

→ solved.ac tag: pigeonhole_principle