>위에 홍성호씨가 요구하신 것은 별거 아닙니다. 만약 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방진에 대해
>전에 어떤 분이 잠깐 컴퓨터를 돌려서 구하셨듯이 그냥 무작정 하나씩 대입해 보며
>시행착오를 거듭하면 되니까요. 이것은 매우 나쁜 알고리즘입니다만, 어쨌든
>알고리즘이 분명합니다. 그래서 문제는 할 수 있는가가 아니라 얼마나 효율적으로
>할 수 있는가의 문제입니다. 구조체 해법은 얼마나 효율적인 알고리즘입니까?
>무작정 대입하는 것보다는 최소한 효율적인 방법이겠지요? 알고리즘의 복잡성에
>대한 분석은 해 보셨습니까?
>
>만약에 만약에 이정구씨의 답이 그냥 마방진이라는 대상과 구조체라는 대상의
>단순한 일대일 대응이라면 최소한 저는 그것을 답이라고 받아들이지 않을 것입니다.
>(물론 설마 그러지는 않겠지만, 노파심에 한번 덧붙여 봤습니다.)
>Aaram Yun wrote:
>: 이 이야기를 보니까 자꾸 생각나는 것은 전에 어떤 잡지에선가 읽은 Herbert Wilf
>: 라는 조합수학자의 'What is an answer?'라는 재미있는 제목의 글이었습니다.
>: 그의 글의 요지는, 어떤 문제를 풀었다고 할 때, 그 답이란 상당히 다양한 형태를
>: 띨 수 있다는 것입니다. 이 사람이 생각하는 문제의 전형은 그러니까 어떤
>: 조합수학적인 대상입니다. 마방진이라고 하면 좋겠지요. 그런 조합적 대상이
>: 있으면 그에 대한 문제는 '그것들이 어떻게 생겨먹었냐?'라는 것이 될 것입니다.
>: 가장 좋은 답은 그 대상들을 체계적으로 모두 생성할 수 있는 방법을 보이고
>: 그 갯수 및 그 대상들을 규정할 만한 다른 중요한 정보들을 제공하는 것입니다.
>: 식으로 쓸 수 있으면 좋을 것입니다.
>
>급히 덧붙이자면 위에서 이야기한 '답 다움'의 리스트는 , 꼭 그 리스트의 뒷쪽에
>나와 있다고 해서 나쁘다는 것은 아닙니다. 리스트의 위쪽에 있을 수록 좋은
>것임은 분명하고, 그리고 리스트의 위쪽에 있는 답을 얻을 수 있는 상황에서
>아래쪽에 있는 답 밖에 얻지 못했다면 문제가 있기는 할 것입니다. 하지만 문제에
>따라서는 원래부터 그런 깨끗한 답이 나오지 않는 성격의 문제들이 있습니다.
>아마도 이 리스트의 거의 맨 바닥에 있는 것이 최대로 기대할 수 있는 것일 그런
>비관적인 상황도 있을 것입니다. 그런 경우에는 그런 답이라도 얻어낸다면 좋은
>답으로 인정될 수 있습니다.
>
>마방진의 경우 여태까지 알려진 모든 'n차 마방진의 총 갯수'가 컴퓨터를 돌려서
>알려지거나 그런 데다가 n=5까지밖에 알려진 것이 없는 불쌍한 상황입니다.
>짐작에 그 '답 다움'의 리스트에서 맨 위에 있는 것과 같은 깨끗한 답을 얻는 것이
>원천적으로 불가능한 문제인지도 모릅니다. 그렇다면 아마도 이정구씨의 답 같은
>형태의 답이 유일한 가능성인지도 모르지요. 이제 따져보아야 할 것은 그 답이
>, 또는 답들이 얼마나 효율적인 알고리즘인가입니다. 계산은 어차피 n이 커지면
>못하니까 계산에 치이지 말고 ...라고 말하더라도 알고리즘의 효율성을 따지는
>것은 필수적입니다. 왜냐하면, 만일 알고리즘의 효율성을 따지지 않는다면 저도
>사실은 n차 마방진을 완벽히 풀었기 때문입니다: n차 마방진이 모두 몇 개
>있냐고요? n차 마방진을 모두 다 생성해 보십시오. 정확히 그 갯수만큼 있습니다.
>어떻게 생성하냐고요? 하나 하나 숫자를 넣어 봅시다. 그 결과가 마방진이면
>좋고, 아니면 다른 숫자를 넣으면 됩니다. 에헴.
>
>근데 전산학 하시는 분들 혹시 이런 것에 대한 결과 모르십니까? 예를 들어
>n차 마방진을 모두 생성하는 문제의 time complexity같은 것에 대해 나와있는
>결과가 있는지요.
>