본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[대한수학회] 대50. 짝수 치환과 홀수 치환
수학동아 2021.01.29 17:28 조회 1860

양의 정수 n에 대해, 1부터 n까지 정수들을 모아놓은 집합을 X_{n}이라고 하자. 이 때 X_{n}의 원소들을 차례대로 나열하는 한 방법을 치환(permutation)이라고 부른다. 한 치환은 X_{n}에서 X_{n}으로 가는 일대일 대응으로 생각할 수 있고, 따라서 하나의 함수 \sigma : X_{n}\rightarrow X_{n}로도 이해할 수 있다. 치환을 표기하는 방법에는 여러가지가 있으나, 일반적으로 다음과 같은 기호를 사용한다.

\sigma =\begin{pmatrix} 1& 2& 3& \cdots & n \\ \sigma (1)& \sigma (2)& \sigma (3)& \cdots & \sigma (n) \end{pmatrix}

예를 들어, 1을 3으로, 3을 2로, 2를 1로 보내는 치환은 \begin{pmatrix} 1& 2& 3\\ 3& 1& 2 \end{pmatrix}가 된다.

 

양의 정수 n에 대해 모든 치환들을 모아놓은 집합을 S_{n}이라 하면, S_{n}의 원소의 갯수는 n!임을 쉽게 알 수 있다. 또한 치환은 함수로 이해할 수 있으므로, S_{n}에 속하는 임의의 두 치환 \sigma, \gamma에 대해 합성합수 \sigma\circ \gamma를 생각할 수 있고, 이 함수도 S_{n}의 원소가 된다.

 

만약 어떤 치환이 X_{n} 의 원소들 중 a_{1}, a_{2}, \cdots ,a_{k}에 대해서는 a_{1}을 a_{2}로, a_{2}를 a_{3}로, \cdots , a_{k-1}를 a_{k}로, a_{k}를 a_{1}으로 보내고, 나머지 원소들에 대해서는 자기자신으로 보낼 때, 이 치환을 길이가 k인 순환치환(cycle)이라고 부른다. 특히, 길이가 2인 순환치환을 호환(transposition)이라고 부른다. 순환치환의 경우, 더 간단하게 (a_{1}a_{2}a_{3}\cdots a_{k})와 같은 기호로 나타내기도 한다.

 

치환은 많은 학생들이 경우의 수를 찾는 문제나 사다리타기 등에서 이미 접하여 친숙하지만, 대수학에서 중요한 개념중 하나인 군(Group)에 대한 연구에서 핵심적인 역할을 하기도 한다. 

 

1번.

1-1) 임의의 치환은 호환들의 합성으로 나타낼 수 있음을 보여라

1-2) S_{n}의 항등치환(즉, X_{n}의 각각의 원소들은 자기 자신으로 보내는 치환)은, 홀수개의 호환들의 합성으로 나타낼 수 없음을 보여라. 이를 이용하여, 짝수개 호환들의 합성으로 나타낼 수도 있고 홀수개 호환들의 합성으로도 나타낼 수 있는 치환은 존재하지 않음을 보여라.

짝수개의 호환들의 합성으로 나타낼 수 있는 치환을 "짝수 치환", 홀수개의 호환들의 합성으로 나타낼 수 있는 치환을 "홀수 치환"이라고 한다.

 

2번.

S_{n}의 임의의 치환은, 자기 자신을 n!번 합성하면 항등치환이 됨을 보여라.

 

3번.

다음과 같은 4   imes4 숫자퍼즐이 주어져있다. 왼쪽 그림에서 시작하여, 비어있는 칸으로 숫자들을 위/아래/좌/우로 하나씩 움직이는 작업을 진행한다고 할 때, 오른쪽 그림을 완성할 수 있는지 없는지 판별하여라.

 

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15  

 

 

1 2 3 4
5 6 7 8
9 10 11 12
13 15 14  

 

 

 

 

4번

소수 p가 p\equiv 2(mod3)를 만족하고, S_{p}의 원소 \sigma가 임의의 x\in X_{p}에 대해 \sigma (x)\equiv x^{3}(modp)가 성립하도록 주어져 있다. 이 때, \sigma가 짝수 치환이 되도록 하는 p를 모두 구하여라.

 

본 문제는 1, 2, 3번은 hg 학생과 파스칼 학생이, 4번은 기약다항식 학생이 해결한 것으로 확인됐습니다.

모두 함께 힘을 모아줘서 고맙습니다. 수고했어요!

  •  
    해결
    hg Lv.4 2021.01.31 00:23 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      김미래_기자 Lv.6 2021.02.01 11:45

      안녕하세요. 김다인 멘토의 피드백 전달드립니다~. 

      문제의 절반 이상이 해결됐기 때문에, 현윤석 교수님께 확인 요청드리겠습니다!

       

      김다인 멘토 :  (1, 2, 3번) 모두 잘 풀었습니다~! 4번도 조금 더 힘내보세요!

      좋아요0
  •  
    해결
    파스칼 Lv.7 2021.01.31 23:12

    이번 내용은 굉장히 잘 알려진 내용이네요

    먼저 1번은 중요한 정리일 텐데

    1-1은 다시 말해 항등치환에서 원하는 두 원소를 바꾸는 과정을 원하는 만큼 실행했을 때 원하는 치환을 만들 수 있는지 묻는 문제입니다.

    간단히, 먼저 길이 2인 치환은 자명하게 모두 만들어집니다. 수학적 귀납법을 사용하여, 길이 n-1의 치환을 만들 수 있다고 가정합니다. 임의의 길이 n인 치환에 대하여, n에 대응된 원소가 n이라면 나머지에 길이 n-1짜리 치환을 만드는 방법을 그대로 적용하면 됩니다. n에 대응된 원소가 a(not n)이라고 하면 n과 a를 바꾸는 호환을 통해 n에 a를 배치하고 남은 n-1개의 원소에 대해 n을 a처럼 생각하여 길이 n-1짜리 치환을 만든 방법을 적용합니다.

    1-2는 치환에 하나의 값을 정의하면 간단해지는 문제인데 3번과 연관성이 있어 제시된 듯합니다.

    임의의 치환 \sigma에 대하여 sgn(\sigma)를 정의하는데, 치환에서 \sigma(1), \sigma(2), \sigma(3), \sigma​​​​​​​(4),...로 1부터 n까지의 수로 순열을 만든 후 더 큰 수 뒤에 더 작은 수가 나오는 횟수를 세고 홀수이면 치환의 sgn(\sigma) 값을 -1, 짝수이면 sgn(\sigma)값을 1로 정의합니다. 어떤 치환에 한 번 호환을 합성하면, 즉 어느 두 원소 \sigma(a)=\alpha\sigma(b)=\beta(a<b)를 바꾸었을 때를 생각합니다. 이때 바꾼 원소 둘 모두보다 앞 또는 뒤에 있었던 원소들은 sgn(\sigma)에 영향을 주지 않고, 바꾼 원소 둘 사이에 있는 원소도 둘 모두보다 크거나 작으면 영향을 주지 않습니다. 바뀐 원소 둘 사이의 원소가 값 또한 두 원소의 값 사이에 존재한다면, 즉 a<c<b이며 \alpha<\sigma(c)<\beta이거나 \alpha>\sigma(c)>\beta이라면, 앞의 경우 \alpha와 \beta를 바꾸었을 때 (더 큰 수, 뒤에 나오는 더 작은 수)의 순서쌍에서 \sigma(c)가 순서쌍 안에 등장하는 횟수가 2번 늘어났고, 뒤의 경우에서는 2번 줄어들었으므로 sgn(\sigma)에 영향을 끼치지 않습니다. 즉 \alpha와 \beta 중 더 큰 수 뒤에 나머지가 나오는지 여부만 생각하면 되는데, \alpha와 \beta 중 어느 것이 더 큰지에 상관없이 더 큰 수 뒤에 작은 수가 나오는 횟수는 1번 변하게 됩니다.

    즉 임의의 호환을 합성했을 때 sgn(\sigma)는 언제나 변하게 되고(-1배 되고), 항등치환이 나타나기 위해서, 즉 원래대로 돌아가기 위해서는 sgn이 처음과 같아야 하므로 홀수개 호환들의 합성으로 항등치환이 될 수는 없습니다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    해결
    파스칼 Lv.7 2021.01.31 23:24

    이제 2번 문제를 보면, 사실 n!이 아니라 1부터 n까지 모든 자연수의 최소공배수라도 문제의 명제가 성립할 것입니다.

    임의의 수에서 출발하여, 치환을 따라 이동하겠습니다. 즉, a에서 출발했다면 a, \sigma(a), \sigma(\sigma(a)), \sigma(\sigma(\sigma(a))), \sigma(\sigma(\sigma(\sigma(a)))),...으로 순열을 만드는 것입니다. 이때 이 순열에서 최초로 다시 a가 등장하는 순간을 생각해 보겠습니다. 만약 a가 다시 등장하기 전에 같은 수가 두 번 등장했다면, 최초로 전에 등장했던 수가 다시 나오는 순간을 잡습니다. 그리고 앞에서 이 수가 등장한 게 수열에서 m번째 원소, 뒤에서 다시 등장한 게 수열에서 n번째 원소라고 하면, a가 다시 등장하기 전이므로 이 수는 a가 아니고 m>1입니다. 이때 치환은 일대일대응이므로 m-1번째 원소와 n-1번째 원소는 같은 원소입니다. 그러므로 이 n번째 원소가 최초로 다시 등장한 수임에 모순입니다. 따라서 a가 다시 나오기 전에 나올 수 있는 수는 최대 a를 포함해서 n개뿐입니다. 즉, a, \sigma(a), \sigma(\sigma(a)), \sigma(\sigma(\sigma(a))), \sigma(\sigma(\sigma(\sigma(a)))),...의 수열에서 \sigma(a)에서 \sigma^n(a)(\sigma를 n번 합성한 함수에 a를 대입)까지 중 반드시 a가 한 번 등장한다는 것이고, 이는 \sigma^x(a)=a의 해로써 1 이상 n 이하의 자연수 x가 존재한다는 것입니다.

    따라서 같은 치환을 n!번 합성하면, 임의의 a에 대하여 \sigma^x(a)=a인 1 이상 n 이하의 자연수 x가 존재하고 x는 n!의 약수로 이 치환이 n!번 합성되었을 때 a는 다시 a로 돌아갑니다. 즉, 같은 치환을 n!번 합성하면 항등치환이 됩니다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    해결
    파스칼 Lv.7 2021.01.31 23:43

    3번 문제는 15퍼즐이라는 문제인데 과거 이것을 해결하는 데(그림을 완성하는 데) 큰 상금이 걸리기도 했지만 해결 불가능이라는 것이 증명되었습니다.

    빈칸에 16을 쓰고, 언제나 16과 다른 타일을 바꾸기만 하여 위 그림에서 아래 그림을 만드는 문제로 변형하겠습니다.

    처음 위치에서 홀수가 적힌 타일이 있는 공간을 홀수 칸, 짝수가 적힌 타일이 있는 공간을 짝수 칸이라고 부르고, 1번이 적힌 타일이 있는 칸을 1번 칸, 2번이 적힌 타일이 있는 칸을 2번 칸, ...으로 부르겠습니다.

    16이 한 번 움직일 때마다 16은 짝수 칸에서 홀수 칸으로, 홀수 칸에서 짝수 칸으로 움직이며 16은 제자리로 돌아가야 하므로 이 타일은 짝수번의 변형 과정을 거쳤습니다.

    4*4 숫자퍼즐의 임의의 타일 배치를 위부터 1번 칸의 타일의 숫자, 2번 칸의 타일의 숫자, 3번 칸의 타일의 숫자, 4번 칸의 타일의 숫자, 5번 칸의 타일의 숫자,...로 만든 순열로 표기하겠습니다. 그리고 16과 다른 숫자가 있는 타일을 바꾸는 과정은 16과 그 숫자를 바꾸는 호환을 순열에 합성(호환을 함수로 생각했을 때 순열의 각 원소에 호환을 적용)한 것과 같습니다.

    만약 위 그림에서 아래 그림으로 바꾸는 것이 가능하다면, 처음 타일 배치 순열에 16과 다른 숫자를 바꾸는 호환 짝수 개를 합성해서 아래 타일 배치 순열로 만들었다는 것을 의미합니다. 이때 이 순열에 다시 15와 14를 바꾸는 호환을 합성하면, 처음 타일 배치에 호환 홀수 개를 합성하여 다시 처음 타일 배치로 만들 수 있습니다. 즉, 호한 홀수 개를 합성하여 항등치환을 도출한 것입니다. 문제 1-2번에서 이는 모순이며, 위 그림을 변형하여 아래 그림을 완성하는 것은 불가능합니다.

    댓글 작성하기 좋아요0 댓글수1
    •  
      김미래_기자 Lv.6 2021.02.01 11:45

      안녕하세요. 김다인 멘토의 피드백 전달드립니다~. 

      문제의 절반 이상이 해결됐기 때문에, 현윤석 교수님께 확인 요청드리겠습니다!

       

      김다인 멘토 :  (1, 2, 3번) 모두 잘 풀었습니다~!

      좋아요0
  •  
    해결
    기약다항식 Lv.5 2021.02.04 00:15

    4번 문제의 풀이입니다.

    \mod p로 원시근(primitive root) g를 잡자. 그러면, g^0, g^1, \dots, g^{p-2}까지의 원소가 permute된다고 생각할 수 있다. 0 (또는 p)는 항상 0으로 가기 때문이다.

    이때, \sigma : g^i \mapsto g^{3i}이므로, p = 3k + 2라고 하면 \sigma : g^0, g^1, \dots, g^k, g^{k+1}, \dots, g^{2k}, g^{2k+1}, \dots, g^{3k} \mapsto g^0, g^3, \dots, g^{3k}, g^{2}, \dots, g^{3k-1}, g^1, \dots, g^{3k-2}이다. (Fermat's little theorem에 의하여 g^{3k+1} \equiv 1 \pmod p이기 때문이다.)

     

    그러므로, (3,2), (3,1) / (6,2), (6,5), (6,1), (6,4) / (9,2), ..., (9, 7) / ... / (3k, 2), ..., (3k, 3k-2) // (2,1) / (5,1), (5,4) / (8,1), (8,4), (8,7) / ... / (3k-1, 1), ..., (3k-1, 3k-2)와 같이, '뒤집어진' 쌍의 개수가 (2+4+6+\dots+2k) + (1+2+3+\dots+k)=\frac{3k(k+1)}{2}가 된다. \sigma가 짝수 치환임은 이 수가 짝수가 됨과 동치이고, 이는  k \equiv 0,3 \pmod 4임과 동치이므로, \sigma가 짝수 치환이 될 필요충분조건은 p \equiv 2,3 \pmod 4인데, 주어진 조건 p \equiv 2 \pmod 3과 함께 생각해 보면 p=2 또는 p \equiv -1 \pmod {12}이어야 함을 알 수 있다.

    댓글 작성하기 좋아요0 댓글수3
    •  
      hg Lv.4 2021.02.06 03:31

      ! 원시근 아이디어가 있었네요.

       

      하나 궁금한 것은, 같은 집합(여기선 X_{p})를 다른 순서로 정렬할 경우 (여기서는 본래의 수 대신 원시근의 지수 기준 정렬) 치환의 홀짝성이 보존되는가...인데,

      자명한 것 같으면서도 증명이 바로 떠오르지는 않네요.

      좋아요0
    •  
      최기자 Lv.4 2021.02.07 16:55

      김다인 멘토의 검토 결과 잘 푼 것 같다고 합니다.^^

      좋아요0
    •  
      파스칼 Lv.7 2021.02.10 18:57

      @hg

      0,1,2,3,...를 x^3 mod p에 대응되는 수로 보내는 치환을 A라 하고, A를 호환들의 합성으로 표현하여 A=E1E2E3E4E5...En이라 하겠습니다(E1, E2, E3,...En을 순서대로 항등치환에 적용한 것으로 하겠습니다). 또한 이때 모든 1부터 n 사이의 수 a에 대해 Ea를 a1과 a2를 바꾸는 호환이라고 하겠습니다. A가 짝수치환이라면 n이 짝수, 홀수치환이라면 n이 홀수일 것입니다. 이제 0,1,2,3,...를 0,g^0,g^1,g^2,g^3,...g^p-2로 보내는 치환을 B라 하고, 호환 Fa를 B(a1)과 B(a2)를 바꾸는 호환으로 정의합니다. 0,g^0,g^1,g^2,g^3,...g^p-2에 F1,F2,F3,...를 순서대로 적용하면, B(i)가 B(i^3)으로 보내지므로 0,g^3,g^6,g^9,...g^(3k-2)가 됩니다. 즉, A'=F1F2F3F4...Fn(F1, F2, F3,...Fn을 순서대로 항등치환에 적용한 것)은 0,g^0,g^1,g^2,g^3,...g^p-2를 0,g^3,g^6,g^9,...g^(3k-2)로 바꾸는 치환이며, n이 짝수인지 여부에 따라 A'이 짝수치환인지 여부가 정해지므로 A'가 짝수치환임이 A가 짝수치환일 필요충분조건입니다.

       

      좋아요0
  •  
    파스칼 Lv.7 2021.02.04 08:36

    1번 문제에서 제가 sgn을 자신보다 더 큰 수의 개수 총합으로 정의했는데, 더 작은 수로 하더라도 1번과 2번 문제의 결과가 성립합니다. 즉 모든 치환은 호환의 합성으로 표현되며, 이때 2번의 논리로 호환이 하나씩 합성될 때마다 sgn이 -1배 됩니다. 즉 sgn이 1임과 짝수치환임은 동치이며(항등치환이 짝수치환인 동시에 sgn이 1이기 때문), 위 기약다항식님의 4번 풀이에서 언급된 '뒤집어진 횟수'로 sgn이 정의되므로 이 수가 짝수임이 짝수치환일 필요충분조건입니다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    김미래_기자 Lv.6 2021.02.16 15:13

    모든 문제가 다 풀린 것 같아서 마지막으로 출제하신 교수님께 검토받고 해결 딱지 붙이겠습니다!

     

    잘 풀어준 모든 분들 고마워요~!

    댓글 작성하기 좋아요0 댓글수0
  •  
    퍼즐-Scratch Lv.5 2021.03.01 22:35

    문제가 다 풀린 것 같네요! '열세 살 딸에게 가르치는 갈루아 이론'이란 책을 읽다가, 파스칼님의 것과는 다른 1-2) 증명을 찾았습니다. 아직 갈루아 이론을 이해하지 못해서 책을 추천드리지는 못하겠지만 치환에 입문하는 데 많은 도움이 되었습니다. 1~3의 증명이 이 책에 대부분 나와 있기도 하니 관심 있는 분들은 한번 보면 좋을 것 같아요 ㅎㅎ

    책 링크

    댓글 작성하기 좋아요0 댓글수0
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911