체스 최대배치문제 - 비숍편

 8×8체스판과 함께 수없이 많은 장기말들이 있다고 가정하자. 최대배치문제란 동일한 기물 여러개를 체스판 위에 서로 공격하지않게 하면서 최대한 많이 올리려면 어떻게 해야하는지, 그리고 그 최댓값은 얼마인지 묻는 문제이다. 

 각 메이저 기물들에 대해 최대배치문제의 최댓값이 다음과 같이 알려져있다.

킹 : 16

퀸 : 8

룩 : 8

비숍 : ??

나이트 : ??

여기서 비숍의 경우에 대해 최대배치문제를 풀고 증명하라. 비숍은 양대각선으로 공격한다는 사실을 유념.

(나이트의 경우 다음 체스퍼즐 글을 참조하라.)

풀이

비숍은 최대 14개까지 올릴 수 있다.

 증명을 위해 우선 / 방향 대각선부터 생각하자. 8×8 체스판에서 / 방향 대각선은 총 15개가 있다. 만약 비숍이 16개 이상 판 위에 있었다면 비둘기집 원리에 의해 적어도 한 대각선에 2개의 비숍이 있게 된다. 그렇다면 이 두 비숍이 서로 공격하게되므로, 여기서 최댓값이 16미만임을 알 수 있다.

 비숍이 15개였다고 가정하자. 앞선 논리에 의해 비숍은 모든 / 방향 대각선에 존재해야한다. 그런데 이것은 a8과 h1에 두 비숍이 있어야 함을 의미한다. 이 두 비숍은  방향으로 서로를 공격하므로, 여기서 15는 답이 아님을 알 수 있다.

결국 최댓값은 15미만, 즉 14이하이다. 이제 14일때의 해를 직접적으로 찾음으로서 증명을 마친다.