d라이브러리

주어진 문제만 생각하지 않고, 학자나 연구자가 된 듯이 그 문제로부터 뻗어 나갈 수 있는 다양한 변형과 일반화를 생각해보는 것이 때로, 주어진 문제를 해결하는 데에 큰 도움이 될 수 있습니다. 올림피아드는 어렵고 열심히 공부해야 하는 것이라고 생각하지 말고, 그런 자유로운 호기심이 뛰어놀 수 있도록 즐거운 마음으로 공부하면 좋겠습니다.


도시대항 국제수학토너먼트(TOT) 2003년 봄 고등부 O레벨 4번

두 개의 숫자로 된 패턴들 00, 01, 02, 03, …, 99를 재배열하는데, 이웃한 두 항은 두 자리 중 한 자리는 같고 다른 한 자리는 차이가 1이 되도록 하려고 한다. 이런 재배열에서 원래의 (오름차순의) 순서와 같은 위치에 있게 되는 항은 최대 몇 개인가?

우선 이런 조건을 만족시키면서 이 100개의 패턴을 모두 나열하는 것이 가능한지부터가 궁금할 것입니다. 일단 가장 간단하게 00↗09, 19↘10, 20↗29, 39↘30, 40↗49, …, 99↘90으로 10개씩 오르락내리락 번갈아 배열하는 것을 생각할 수 있으므로, 이 궁금증은 문제없이 해결됩니다.

게다가, 이 배열에서는 ‘00↗09’, ‘20↗29’, ‘40↗49’, ‘60↗69’, ‘80↗89’ 등 50개나 되는 수가 이미 제자리를 지키고 있습니다. 이제 50개보다 더 많은 수들이 제자리를 지키게 할 수 있는지를 생각해봐야 합니다. 그런데, 시간을 들여 여러 가지 방법을 아무리 시도해 봐도 더 많은 개수가 제자리를 지키게 하는 방법은 잘 발견되지 않음을 경험하게 됩니다. 그럼 이 50개가 위 문제에서 구하는 최댓값일 것이라는 추측이 듭니다.

이제 필요한 것은 이것을 증명하는 논리를 찾아내는 것입니다. 예를 들어, 이 100개의 패턴을 재배열하는 방법의 수는 기껏해야 유한하므로 모든 방법을 다 따져보는 풀이도 불가능하지는 않습니다. 그러나, 그것은 아름답지 않은 방법이고, 특히 10000개의 네 자리의 패턴들로 문제를 확장할 수도 있을 텐데 그럼 이런 방식의 풀이는 점점 더 곤란해질 수밖에 없습니다. 또한, 무턱대고 위와 같은 배열이 최선이라고 주장하려 한다면 그것은 전혀 수학적이지 못한 접근입니다.

좀 더 세심히 여러 예를 관찰해봅시다. 처음의 10개의 수가 제자리에 있으면 다음의 10개의 수는 어느 하나도 제자리에 갈 수 없다는 것을 발견하게 됩니다. 특히, 일의 자리가 홀수인 수는 짝수인 수의 자리에, 짝수인 수는 홀수인 수의 자리에 가게 될 수밖에 없습니다. 여기서 홀짝성에 관한 힌트를 얻을 수 있을까요? 이것은 각각의 패턴을 숫자의 홀짝에 따라 00, 01, 10, 11(짝짝, 짝홀, 홀짝, 홀홀을 대신한 표현)의 네 가지로만 분류해보면 더 확실히 알 수 있습니다. 00이나 11 다음에는 01이나10이 올 수밖에 없고 그 반대도 마찬가지입니다.

조금 다른 관찰로 비슷한 착안을 얻을 수도 있습니다. 이 문제는 꼭 십진법에서 출제할 필요는 없었을 겁니다. 오진법에서 출제했다면 00, 01, 02, 03, 04, 14, 13, 12, 11, 10, … 으로 재배열했을 때 12도 제자리에 놓이기 때문에 십진법에서와 양상이 다릅니다. 일반적으로 짝수 진법에서는 십진법에서와 늘 같은 양상을 나타내고 홀수 진법에서는 그렇지 않습니다. 그럼 짝수 진법 중에서 대표적으로 가장 간단한 이진법의 경우를 살펴봅시다. 그럼 00, 01, 10, 11의 네 가지 패턴뿐이고, 이것은 너무 간단하니까 좀 더 긴 패턴들, 예를 들어 네 자리의 패턴들에서 고려해보자는 생각을 할 수도 있습니다(자리의 길이가 홀수일 때는 또 양상이 다릅니다). 이런 경우라면 이웃한 두 항은 자릿수의 합의 홀짝이 항상 서로 다르다는 관찰을 쉽게 해낼 수 있을 겁니다.

그럼 홀수 진법에서는 답이 어떻게 달라지고 풀이는 어떻게 해야 할까 궁금해지지 않나요? 예를 들어 오진법에서라면, 25개의 패턴 중에서 17개가 제자리를 지키는 것이 최대일까요? 이것의 해결은 여러분에게 남겨둘게요


고봉균 선생님의 풀이

위에 제시한 배열 방법에서 십의 자리가 짝수인 패턴들이 모두 제 위치에 그대로 있으므로 50개의 항이 제자리에 놓이도록 하는 것은 가능하다. 이보다 더 많을 수는 없음을 보이자.

문제의 조건을 만족시키도록 항을 재배열했다면, 이웃한 두 항은 두 개의 자릿수 중에 딱 하나만 1만큼 다르므로 자릿수의 합의 홀짝이 항상 다르다. 따라서, 자릿수의 합이 짝수인 수와 홀수인 수가 한 번씩 번갈아서 나타난다. 즉, 자릿수의 합의 홀짝은‘짝홀짝홀짝홀… 짝홀’로 나타나거나 ‘홀짝홀짝홀짝…홀짝’이 된다.

그런데, 원래 오름차순의 배열 00, 01, 02, 03, …, 99에서는 자릿수의 합의 홀짝이 10개 단위로‘짝홀짝홀…짝홀’과 ‘홀짝홀짝…홀짝’을 번갈아 반복한다. 따라서, 어느 경우에나 자릿수의 합의 홀짝이 맞지 않는 항이 10개씩 5묶음으로 딱 50개가 있으므로, 적어도 이 50개의 수는 제 위치에
있을 수 없다. 따라서, 제자리에 놓이는 항은 50개가 최대이다.