Re: 마방진에 대한 추억 위에 홍성호씨가 요구하신 것은 별거 아닙니다. 만약 8방진을 전부 생성하는 것이 가능하다면 그게 전부 몇개냐는 거죠. 이 이야기를 보니까 자꾸 생각나는 것은 전에 어떤 잡지에선가 읽은 Herbert Wilf 라는 조합수학자의 'What is an answer?'라는 재미있는 제목의 글이었습니다. 그의 글의 요지는, 어떤 문제를 풀었다고 할 때, 그 답이란 상당히 다양한 형태를 띨 수 있다는 것입니다. 이 사람이 생각하는 문제의 전형은 그러니까 어떤 조합수학적인 대상입니다. 마방진이라고 하면 좋겠지요. 그런 조합적 대상이 있으면 그에 대한 문제는 '그것들이 어떻게 생겨먹었냐?'라는 것이 될 것입니다. 가장 좋은 답은 그 대상들을 체계적으로 모두 생성할 수 있는 방법을 보이고 그 갯수 및 그 대상들을 규정할 만한 다른 중요한 정보들을 제공하는 것입니다. 식으로 쓸 수 있으면 좋을 것입니다. 그런데 때로는 이것이 불가능할 수가 있습니다. 그런 경우에라면 이제 문제는 복잡해 지기 시작하는데, 대상들을 체계적으로 모두 생성할 수 있고 숫자를 세는 방법 등에 대해서도 잘 정립할 수 있지만 식으로 그 대상들에 대해 잘 표현할 수 없는 경우가 있습니다. 예를 들어 생성함수(generating function)등으로 표현된 답의 경우가 그렇지요. 이 경우는 처음의 경우보다는 불만족스럽습니다만 그래도 훨씬 좋은 답인 것이 그 정보로 부터 경우에 따라서는 다른 중요한 정보들을 뽑아낼 수 있기 때문입니다. 생성함수로 표현된 경우 잘만 하면 asymptotic behavior 같은 것도 읽어낼 수 있고 어쨌든 간에 체계적으로 원하는 n에 대해 그 계수를 읽어낼 수 있으므로 좋은 상황입니다. 그것보다 더 상황이 나빠지면 이걸 답이라고 불러야 하나 말아야 하나 이제 고민스러워지기 시작합니다. 예를 들어 생성함수 정도로 간접적인 방법으로라도 식으로 쓸 수 있었던 경우가 아니라 아예 그런 표현을 얻지 못했다고 합시다. 대신에 그 대상들을 하나하나 생성해낼 수 있는 최적의 알고리즘을 개발해 냈다고 하면...좀 만족스럽지는 않아도 답이라고 부를 수 있을 것입니다. 이제 모든 대상들을 다 생성하는 것에도 실패했지만 확률적으로 모든 n에 대해 n에 의해 parametrized된 대상들(예를 들어 모든 n차 마방진들)중에서 일정 비율 이상의 대상들을 생성하는 그런대로 괜찮은 알고리즘을 만들었고 그 알고리즘이 전체의 대상들 중에서 일정 비율(예를 들어 70%) 이상을 항상 생성해낸다는 것을 증명할 수 있었다고 합시다. 위의 것보다 훨씬 덜 만족스럽고, 이제 답이라고 부를 수는 없겠지만 최소한 의미있는 불완전한 결과라고 할 수 있을 것입니다. 그보다 더 나쁜 것에 대해서는 답이라고 부를 수는 없습니다. 가상적인 예로 하나 생각해볼 수 있는 것은 어떤 대상들을 세는 대신에, 생성해내는데 거의 동등한 정도의 계산적 복잡도를 갖는 다른 대상들과 일대일 대응을 주는 경우입니다. 이건 답이 아닙니다. 그 다른 대상들이 특별히 수학적인 의미가 있다면 그 다른 문제와 이 문제를 연결시켰다는 의미에서 경우에 따라서는 문제풀이의 긴 안목으로 볼 때 약간의 진전을 가져왔다고도 볼 수는 있지만 , 최소한 어떤 새로운 정보도 가져다 주지 않는다는 의미에서는 이런 것은 답이 될 수 없습니다. 이건 그냥 말만 다른 말로 바꿔놓은 거죠. 아, Wilf의 원래 글은 아마 지금 이것과는 꽤 다를 가능성이 큽니다. 그때 읽었던 희미한 기억과 제 생각이 짬뽕이 된 결과가 이 글이니까요. 많은 사람들이 궁금했던 것은(궁금했던 이유는 분명한데 이정구씨가 자신의 결과에 대해 충분한 설명을 제공해주시지 않았기 때문입니다.) 이정구씨의 구조체 해법이라는 것이 위에서와 같은 기준에서 '도대체 얼마나 답인가?'라는 질문입니다. 홍성호씨나 제가 전에 '8차나 6차 마방진의 갯수는 몇 개인데요?'라고 여쭈어본 이유는 이정구씨의 '답'이 위에 제가 순위를 매겨둔 답의 리스트에서 맨 위에 있는 것인지 아닌지 알고 싶었기 때문입니다. 즉 님의 답이 임의의 n에 대해 모든 n차 마방진들을 체계적으로 모두 생성하고 또한 간단한 식으로 그들을 표현할 수 있는가, 또는 closed form으로 표현이 불가능하다고 해도 최소한 효율적으로 계산이 가능한 형태인가라는 것이 궁금했던 것이지요. 여전히 이정구씨의 해법이 무엇인지 분명치는 않습니다만 최소한 이 경우에 해당되지는 않는 것 같군요. 그렇다면 위에 제가 매겨놓은 '답 다움'의 리스트에서 한 단계 내려가야 하겠네요. 몇 단계를 더 내려가야 합니까? 구조체 해법은 어느 정도나 답 답습니까? 여러 차례 줏어들은 이정구씨의 설명을 모아보면 그러니까 임의의 n에 대해 n차 마방진들 전체 중에서 어느 정도 이상 비율의 마방진들을 생성할 수 있는 규칙을 찾으신 것인듯한 인상을 받았습니다. 거기까지는 좋습니다. 부분해에 불과하지만 여전히 의미있는 결과일 수 있습니다. 그렇다면: 1. 임의의 n에 대해 님의 해법이 일정 비율 이상의 마방진을 생성한다는 증명이 있습니까? 아니면 모두 다 생성해낼 수 있습니까? 그것에 대한 증명이 있습니까? 2. 마방진을 생성하는 것 자체는 사실 누구나 다 할 수 있습니다. 4방진에 대해 전에 어떤 분이 잠깐 컴퓨터를 돌려서 구하셨듯이 그냥 무작정 하나씩 대입해 보며 시행착오를 거듭하면 되니까요. 이것은 매우 나쁜 알고리즘입니다만, 어쨌든 알고리즘이 분명합니다. 그래서 문제는 할 수 있는가가 아니라 얼마나 효율적으로 할 수 있는가의 문제입니다. 구조체 해법은 얼마나 효율적인 알고리즘입니까? 무작정 대입하는 것보다는 최소한 효율적인 방법이겠지요? 알고리즘의 복잡성에 대한 분석은 해 보셨습니까? 만약에 만약에 이정구씨의 답이 그냥 마방진이라는 대상과 구조체라는 대상의 단순한 일대일 대응이라면 최소한 저는 그것을 답이라고 받아들이지 않을 것입니다. (물론 설마 그러지는 않겠지만, 노파심에 한번 덧붙여 봤습니다.)