불변량

 

불변량은 특정 변형이 객체에 적용될 때 변경되지 않고 보존되는 속성을 말합니다.
백문이 불여일견. 사전에 적힌 말은 너무 어려우니 예시를 봅시다.

1 + 2 + 3 + ... + 100 = ?

1부터 100까지 모든 자연수를 더하면 얼마일까요? 수학자 가우스가 손쉽게 풀어낸 일화로 유명한 문제입니다. 가우스가 푼 방법은 아래와 같습니다.

100부터 1까지 거꾸로 더한 식을 하나 더 사용해서 대응되는 항끼리 더합니다. 하나의 식은 1씩 증가하고, 다른 하나의 식은 1식 감소하기 때문에 일정한 규칙을 갖는 모든 대응되는 항의 합은 101로 일정합니다. 전체 항이 100개 이므로 전체 합이 10100이 되고 우리가 구하고자 하는 답은 이 값의 절반인 5050이 됩니다.

가우스는 합을 거꾸로 적는다는 트릭을 통해 101이라는 불변량 찾았고, 등차수열의 합을 매우 쉽게 계산했습니다. 다른 예시도 알아보겠습니다.

여기 8 x 8 체스판이 있습니다. 이 체스판 위에 오른쪽 그림과 같은 1 x 2크기의 도미노 여러 개를 겹치지 않게 놓아 전체 체스판을 덮을 수 있을까요? 도미노는 항상 체스 판의 칸에 맞게 두어야 합니다.

 

당연히 덮을 수 있습니다. 나란히 32개만 두면 덮을 수 있죠.

 

문제가 너무 쉬웠나요? 이번에는 체스판 오른쪽 위 귀퉁이에서 한 칸을 떼어냈습니다. 이번엔 어떤가요? 덮을 수 있나요? 도미노를 반으로 자르는 건 안된다고 합시다.

이번에는 덮을 수 없습니다. 전체 칸이 63개니까 도미노가 31.5개 필요한데 도미노를 자를 수는 없습니다.

이 문제에서 불변량을 찾을 수 있나요?

귀퉁이 한 칸을 뺀 체스판은 총 63개의 칸이 있습니다. 이 값을 2로 나누면 나머지가 1입니다. 이제 아무 곳이나 도미노 하나를 뒀다고 해 봅시다.

이제 덮어야 할 남은 칸은 61개입니다. 이 값을 2로 나누면 역시 나머지가 1입니다. 도미노는 두 칸을 차지하기 때문에 몇 개의 도미노를 덮든 남은 칸의 개수를 2로 나눈 나머지는 변하지 않습니다. 이 문제에서 불변량은 '남은 칸의 수를 2로 나눈 나머지'이며 그 값은 1이겠네요.

전체 체스판을 완벽하게 덮는다면 '남은 칸의 수를 2로 나눈 나머지'가 0이 되어야 하기 때문에 '도미노를 덮는 행위'의 반복을 통해서는 달성할 수 없는 목표가 됩니다.

 

마지막으로 문제 하나를 더 준비했습니다.

이번에는 오른쪽 위 귀퉁이뿐 아니라 왼쪽 아래 귀퉁이도 떼어냈습니다. 덮어야 할 체스판의 칸 수가 62개로 짝수가 되었는데, 이번엔 덮을 수 있을까요? 한 번 생각해 보시기 바랍니다.

정답은 아래에 있습니다.

 

정답: 덮을 수 없습니다.

 

왜 그럴까요? 먼저, 편의를 위해 진한 갈색 칸을 검은 칸, 옅은 갈색 칸을 흰 칸이라고 하겠습니다.

체스판의 마주 보는 두 귀퉁이를 떼어내면서 흰 칸 두 개가 사라졌습니다. 문제에서 덮어야 할 체스판은 총 32개의 검은 칸과 30개의 흰 칸으로 이루어져 있습니다.

첫 번째 도미노를 아무 곳에나 놓아 봅니다. 도미노를 어떻게 놓든 도미노는 검은 칸 1개와 흰 칸 1개를 덮게 됩니다. 이제 이 문제에 맞게 불변량을 새로 정의하겠습니다.

 

불변량 = (남은 검은 칸의 수) - (남은 흰 칸의 수)

 

맨 처음, 32개의 검은 칸과 30개의 흰 칸이 있을 때 불변량의 값은 2입니다. 그리고 우리가 목표하는 '모든 칸을 다 덮은 경우'에는 남은 검은 칸과 흰 칸이 없어야 하므로 이 값이 0이 되어야 합니다. '도미노를 놓는 행위'로는 이 불변량의 값을 바꿀 수 없기 때문에 불가능하다는 결론을 얻을 수 있습니다.

이렇게 불변량은 문제마다 다를 수 있습니다. 문제와 내가 얻고자 하는 결론으로 적절한 값을 찾아야 합니다.

 

마무리

문제를 바라보는 관점을 바꾸면, 겉으로 복잡해 보이는 문제의 핵심을 파악할 수 있습니다. 그리고 상당히 쉽게 해답을 찾게 될 수도 있습니다.

여러분이 마주친 문제의 불변량은 얼마입니까?