7개의 댓글이 있습니다.
-
-
Being -
조금 더 예를 들어 보겠습니다.
원판 하나를 6등분하여 각 칸마다 n가지 색 중 하나를 칠하는 경우의 수를 생각해 봅시다. 즉,
가능한 변환이
(1, 2, 3, 4, 5, 6), (2, 3, 4, 5, 6, 1), (3, 4, 5, 6, 1, 2), (4, 5, 6, 1, 2, 3), (5, 6, 1, 2, 3, 4), (6, 1, 2, 3, 4, 5)
의 여섯 가지인 경우입니다.
(1, 2, 3, 4, 5, 6)의 경우, 어떤 채색에 대해 이 변환을 적용하여도 같은 결과를 얻으려면 각 칸에 아무렇게나 채색해도 됩니다. => n^6
(2, 3, 4, 5, 6, 1)의 경우, 한 칸에 어떤 색을 칠할 경우 다른 모든 칸에도 같은 색을 칠해야 합니다. 이 순열을 cyclic form으로 쓰면 (1 2 3 4 5 6)인데, 각 cycle은 같은 색을 칠해야 하는 집합을 의미함을 알 수 있죠. => n
(3, 4, 5, 6, 1, 2)의 경우 (1 3 5)(2 4 6)으로 나타낼 수 있습니다. 즉, 1번, 3번, 5번 칸에는 같은 색을 칠해야 하고 2번, 4번, 6번 칸에는 같은 색을 칠해야 합니다. => n^2
(4, 5, 6, 1, 2, 3)의 경우 (1 4)(2 5)(3 6)으로 나타낼 수 있습니다. => n^3
(5, 6, 1, 2, 3, 4)의 경우 (1 3 5)(2 4 6) => n^2
(6, 1, 2, 3, 4, 5)의 경우 (1 2 3 4 5 6) => n
따라서, 전체 경우의 수는
(n^6 + n^3 + 2n^2 + 2n) / 6 가지가 됩니다.
15년 전 link
-
-
-
시영(unbing) -
아 글자가 너무 작아져서 애매한가? ㅋㅋ;; (N^2-1)/2 = (N^2-1)C2 니까 둘다 맞습니당 ㅋㅋ
15년 전 link
-
-
-
Taeyoon_Lee -
안녕하세요? 출제자입니다.
해법은 오시영님이 잘 써주셨고, Being님의 보충설명까지 들어가서 'ㅁ' 제가 따로 설명할 게 없네요.
사실 출제 의도는 "만점을 방지하자." 였는데, 생각보다 문제들이 어려워서 그럴 필요가 없었네요..
Burnside's lemma를 쓰는 문제는 UVA Contest를 풀면서 2번이나(?) 만났는데,
국내 대회에서는 본 적이 없어서 국내 도입이 시급하다고 판단되어(''?) 출제 했습니다.
UVA/11255 Necklace
UVA/11540 Sultan's Chandelier
UVA에 있는 Burnside's lemma를 쓰는 문제 입니다. 연습삼아 풀어볼만 합니다..''
15년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
시영(unbing)
안녕하세요? 처음으로 이런 에디토리얼을 쓰게 되네요 ㅎㅎ
대회 주관하느라 고생하신 분들에게 조금이나마 도움이 될까하고 씁니다 ㅋㅋ
1. 문제 설명
다들 아실만한 유명한 게임, 바둑에 대한 문제입니다.
단 바둑판의 사이즈는 2~1500까지 될 수 있다는 점이 약간 다르지요.
바둑이라는 게임은 항상 흑돌을 먼저 두고, 그 다음 백돌, 다시 흑돌 이런 식으로 진행 됩니다.
이 문제에서 우리는 흑이 두번 두고, 백이 한 번 둘 때까지의 상황만을 고려합니다.
이렇게 흑이 두 번 두고, 백이 한 번 두었을 때(같은 좌표에 여러 돌이 올 수는 없습니다.), 생길 수 있는 경우를 모두 세어라 하는 것이 문제입니다. 단, 회전하거나 뒤집어서 모양이 같은 경우는 한 번만 셉니다.
2. 문제 접근
Burnside's Lemma를 이용하면 이 문제가 쉽게 접근이 가능합니다. 하지만 이를 모를 경우는 어떻게 거의 접근이 불가능하죠 :(
이 이론을 간단히 설명하자면 rotation들이 존재할 때, 이를 중복하지 않고 셀 때 굉장히 유용한 이론입니다. (딱 이런 문제를 위한 이론이죠)
우선 가능한 rotation을 모두 고려해봅니다. 바둑판을 두고 보았을 때, 총 8개의 가능한 경우가 있는데 이는 다음과 같습니다.
0도 회전, 90도 회전, 180도 회전, 270도 회전 / 수평선을 기준으로 뒤집기, 수직선을 기준으로 뒤집기, 대각선을 기준으로 뒤집기(2가지)
(이 회전들은 group theory에서 말하는 group을 형성합니다. 뒤집거나 회전하는 연산에 의해서 닫혀 있기 때문인데, 회전하거나 뒤집는 연산을 반복하여 사용한다고 하여도 이들 이의외 모양을 얻을 수는 없습니다. 혹시 더 관심이 있으시면 이 렉쳐를 참고 하세요 ㅋ 깊이 있게 배우지는 않았지만 이 회전들에 대해서는 잘 설명된 듯 합니다.)
Burnside's Lemma의 핵심은 전체의 총 가능한 갯수는 각각의 rotation을 고정했을 때(말이 애매하니까 예를 아래서 들겠습니다.)의 가짓수의 평균이라는 것입니다.
예를 들어 "90도 회전"으로 고정했다는 얘기는 어떤 모양에 대해서 90도로 회전해도 그 모양이 유지된다는 것입니다. 마찬가지로 수평선으로 뒤집는 것을 고정했다는 것은 수평선으로 뒤집었을 때 그 모양이 유지된다는 것입니다.
이제 우리가 할 일은 각각의 rotation을 고정했을 때의 가짓수를 세서 8로 나눠주면 됩니다!
1) 0도 회전: 어떤 모양이라도 0도 회전하면 그 모양이 유지됩니다. 그러니 단순히 모든 경우를 세주면 됩니다. 총 고를 수 있는 범위가 N2개 있으니까(돌이 어디든 있을 수 있습니다.) 답은 N2C3 * 3이 됩니다. (세 돌을 놓을 곳을 고르는 것이 N2C3 이고, 이 중 흰돌이 있을 수 있는 자리가 세 곳입니다.)
2) 90도 회전 or 270도 회전: 돌이 세개밖에 없기 때문에 90도 회전해서 모양이 유지되는 경우는 없습니다. 이는 270도도 마찬가지입니다. N이 홀수 일 경우 가운데에 돌을 두면 그 돌은 유지가 되지만 나머지 두 돌은 유지가 안됩니다. 이는 모든 가능한 포지션이 크기가 4인 cycle을 형성하기 때문인데 금방 이해하실 수 있을 듯합니다. :)
3) 180도 회전: 180도 회전은 정 가운데 점(N이 홀수일 때만 존재)을 제외하면 모든 포지션이 크기가 2인 cycle을 형성합니다. 흰돌은 하나만 있기 때문에 180도 회전 후에도 모양을 유지하려면 흰 돌은 무조건 가운데에 있어야 합니다!
이제 남은 흑돌들의 자리만 정하면 됩니다. 흑돌의 자리를 정하면 나머지 흑돌의 자리는 당연히 정해지기 때문에(180도 회전후에도 모양이 유지되어야 하므로) 총 (N2-1)C2가지가 가능합니다.
4) 수평으로 혹은 수집으로 뒤집기: 이 역시 N이 홀수일 때만 가능합니다. 왜냐하면 N이 홀수인 경우만 가운데에 고정되는 라인이 존재하기 때문입니다.(흰돌은 하나뿐이므로 고정되는 포지션이 필요합니다!) 나머지 흑돌을 두는 경우는 두가지 경우로 나누어 생각해봅니다.
두 돌 모두 고정되는 라인에 있는경우 / 두 돌 모두 고정되는 라인에 존재하지 않는 경우
각각은 N-1C2와 (N-1)*N/2C2가 됩니다.
5) 대각선으로 뒤집기(2가지): 이 경우 N이 짝수냐 홀수냐에 관계없이 대각선에 놓여있는 포지션들은 유지가 됩니다. 따지고 보면 결국 위와 같은 식이 나오죠. -> N-1C2 + (N-1)*N/2C2
이렇게 구한 수를 마지막에 8로 나누어주면 됩니다. 저는 중간에 long long의 범위를 넘어갈까봐 그냥 java BigInteger를 이용해서 코딩했습니다. 사실 식을 다 정리하면 코딩은 정말 짧죠 ㅋㅋ 중간에 카운팅에 약간 실수가 있어서 두번 섭밋하긴 했지만;;;
음 사실 이 이론을 공부한 다음에 쓸 기회가 없었는데 이렇게 쓰게 되네요. ㅎㅎ 사실 Petr 님의 블로그에서 본 다음에 와~ 그러다가 실제로 써본건 처음이에요 ㅋㅋ 그래서 아직 증명은 이해가 잘 안되는;;; 아무튼 여기서는 새벽 여섯시에 일어나서 했는데 신기한 문제 풀어봐서 뿌듯하네요 ㅋㅋㅋㅋ 혹시 이상한점 있으면 댓글 남겨주세요 ㅋㅋ
15년 전