원래 문제의 주소는 여기입니다. https://arca.live/b/math/22563622

출제자분의 조언은

- 오일러 정리를 사용해서 증명했다.

- Official 풀이는 더 일반적인 명제인, 꼭지점이 격자점이고 각 변이 x, y 축에 평행한 임의의 다각형은 채울 수 없다는 증명이다.

...라고 하셨는데 저는 그냥 직사각형을 채울 수 없다는 것을 증명했습니다. 오일러 정리는 잘 모르겠고요. (사실 오일러의 이름이 붙은 정리들 중 어떤 것을 말씀하시는지 잘 모르겠습니다. )

우선 문제를 좀 단순화시켜 보겠습니다. 주어진 도형을 회전시키거나 뒤집으면 다음의 8가지 도형을 얻을 수 있습니다.

여기에서 직각삼각형에 다음과 같이 1+, 1-, 2+, 2- 라는 이름을 붙입니다.

그러면 2-와 2+가, 그리고 1-와 1+ 가 서로 맞물려야 함을 알 수 있습니다. 

이제 주어진 8개의 도형을 다음과 같이 표시할 수 있습니다.

예컨대 이런 식입니다.

여기에서 간략하게 표기된 8개의 도형을 잘 보면

위쪽에는 항상 - 도형이 붙고 아래쪽에는 항상 + 도형이 붙습니다. 좌우는 1/2 에 따라서 +와 -가 반대고요.

주어진 도형을 조립해서 사각형으로만 만들어진 도형을 만든다는 것은

간략화된 모양들을 1+와 1-가 모두 맞물리고 2+와 2-가 모두 맞물리게 조립해서 폐곡선을 만든다는 것과 같습니다.

예컨대 이런 식입니다.

이 예제에서는 2*2 사각형 5개가 붙은 형상을 만들었지만, 가장 간단하게라면  2*2 사각형 한 개짜리도 만들 수 있습니다.

주어진 문제는 이런 폐곡선(들)로 격자점으로 된 직사각형을 빈 칸 없이 채우기는 불가능하다는 것을 증명하는 것과 같습니다. 위의 예제에서는 속에 빈 칸들이 있지요.

증명의 기본적인 방법은

(1) 주어진 폐곡선은 항상 짝수개의 점을 갖게 되는데

(2) 이러한 폐곡선으로 가장자리를 채운 직사각형은 항상 홀수 * 홀수의 크기를 갖는다는 점을 보이는 것입니다.

(1) 은 자명하지요. 흰 점과 검은 점은 항상 번갈아가면서 나타나야 하니까요. 그리고 원래 주어진 도형의 넓이가 (정사각형 한 변의 길이가 1이라고 할 때) 2이므로, 전체 넓이는 짝수일 수밖에 없다는 점도 있습니다.

따라서 (2)를 보이면 됩니다. 만약 폐곡선으로 속에 구명이 직사각형을 만들고 그 빈 (직사각형이 아닐 수도 있는) 공간을 다른 폐곡선으로 채운다고 하더라도, 어쨌든 폐곡선들을 모아서 직사각형을 채운 것이 되므로 사각형의 전체 점 수는 짝수가 되어야 하기 때문입니다.

흰 동그라미를 W타입, 검은 동그라미를 B 타입이라고 부르겠습니다. 

이제 평면 전체를 체스판처럼 흰색과 검은색이 교차하게 칠한 후 W타입 하나를 흰 칸 위에 놓는다면, W타입은 항상 흰 칸 위에만, 그리고 B타입은 항상 검은 칸 위에만 올라갈 수 있음을 알 수 있습니다. (자명하므로 증명은 생략합니다.)

이제 + 에서 - 로 가는 흐름을 화살표로 나타냅니다. 예컨대 다음과 같은 식입니다.

1+에서 1-로의 흐름은 항상 위에서 아래, 그리고 왼쪽에서 오른쪽으로 향하며

2+에서 2-로의 흐름은 항상 위에서 아래, 그리고 오른쪽에서 왼쪽으로 향합니다.

그런데 행들 속에서의 흐름을 살펴보시면

홀수행에서는 항상 흐름이 오른쪽 (혹은 아래쪽)으로 향하고

짝수행에서는 항상 흐름이 왼쪽 (혹은 아래쪽)으로 향합니다.

이는 1+/1-에 속하는 B타입과 2+/2-에 속하는 B타입은 항상 서로 다른 행에 속하기 때문입니다.

따라서 이제 1+/1- 혹은 2+/2- 의 표기를 던져버리고 다음과 같이 나타낼 수 있습니다.

(1) W타입은 두 흐름이 항상 서로 직각이어야 한다. 

(2) W타입은 두 흐름이 '지나가는' 방향이거나 모두 들어오는 방향, 모두 나가는 방향 세 가지 전부 가능하다.

(3) B타입은 두 흐름이 서로 직각일 수도 있고, 같은 방향을 유지할 수도 있다.

(4) B타입은 두 흐름이 항상 '지나가는' 방향이어야 한다. 즉 하나가 들어오는 방향이면 하나는 나가는 방향이다.

(5) 수직 방향으로 향하는 흐름은 항상 아래쪽으로 향한다.

(6) 수평 방향으로 향하는 흐름은 홀수행에서는 오른쪽으로, 짝수행에서는 왼쪽으로 향한다.

(물론 홀수행 짝수행은 임의로 지정할 수 있습니다.)

================================================================================

(110.11님이 지적하신 대로, 이하의 증명은 외각의 사각형이 여러 폐곡선의 조합인 경우에는 성립하지 않습니다. 일단 참고용으로 삭제는 하지 않고 놓아두겠습니다.)

이제 직사각형의 크기가 홀수*홀수여야 한다는 점을 증명하는 것은 간단합니다.

일반성을 잃지 않고, 직사각형의 위쪽 변이 홀수행에 있다고 가정합니다. 그러면 흐름이 아래쪽과 왼쪽으로 향해야 하므로

왼쪽 위의 모서리에 올 수 있는 것은 W 타입 뿐입니다.

직사각형의 왼쪽 아래의 모서리 역시 W 타입밖에 올 수 없습니다. B 타입이라면 해당 모서리에서는 짝수행에 있어야 하는데 그렇다면 흐름이 왼쪽으로 향해야 하므로 양쪽 흐름이 모두 들어오는 방향이 되어야 하기 때문입니다.

직사각형 왼쪽 아래의 모서리가 W타입이므로 홀수행에 있고, 당연히 직사각형의 오른쪽 아래의 모서리도 홀수행에 있습니다.

마찬가지로 여기에도 B타입은 올 수 없으므로 오른쪽 아래의 모서리도 W타입입니다.

즉 직사각형의 왼쪽 위 모서리, 왼쪽 아래 모서리, 오른쪽 아래 모서리가 모두 W타입입니다.

따라서 직사각형의 가로 길이와 세로 길이가 모두 홀수이므로 직사각형의 크기도 홀수일 수밖에 없습니다. (증명 끝)