체스판 위에 도미노 깔기 2

 도미노 깔기 1에서, 체스판의 같은 색깔을 없앴을 경우 절대로 도미노들을 덮을 수 없음을 알았다. 그렇다면, 다른 색깔 두 개를 제거하였다면 어떻게 될까? 두개의 칸은 그야말로 완전히 무작위하게 제거됨을 명심하자. 이 때, 이 조각난 체스판을 항상 덮을 수 있을까, 아니면 덮을 수 없는 반례가 존재할까?

 

 

 

 설명

 

 

 

 매우 깔끔한 증명이다.

 

이제 남은 일은 무작위로 제거된 칸을 두고 기차놀이하는 것 뿐이다.

 

 

 

 

IBM의 랄프 고모리(Ralph Gomory)의 증명이다.