태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.

'MIU System'에 해당되는 글 1건

  1. 2008.10.20 GEB: MU puzzle (4)

GEB: MU puzzle

Tech 2008. 10. 20. 22:08
G.E.B. 에 나온 간단한 퍼즐. 더 읽기 전에 책에서 시킨대로 연습장에 끄적이며 좀 해봤다. 몇번 DAG을 그려보고 나서 "이건 안되는것 같은데?" 라는 생각이 들어서 증명, 혹은 납득할만한 설명을 만들어 보기 위해 고민. 음, 책을 더 읽기 전에 한번 써보고 넘어가고 싶음.

일단 규칙은, 이렇다.

처음, MI 라는 문자열를 가지고 있다.
  1. I가 포함된 문자열은 뒤에 U를 붙일 수 있다.
  2. Mx 형태의 문자열을 Mxx형태로 바꿀 수 있다.
  3. 문자열 안에 III 가 나오면 이를 U로 바꿀 수 있다. 반대 방향으로는 안된다.
  4. 문자열 안에 UU가 나오면 날려버릴 수 있다.
MU 를 만들 수 있겠는가?

MI -> MIU -> MIUIU -> ...
MI -> MII -> MIIII -> MUI -> ...

이런 식으로 가서 마지막에 MU 를 만들면 되는것인데... 불가능하다 - 고 생각한다. 왜 그렇게 생각하는지 한번 이 글을 읽는 당신을 납득시켜 보겠다.

문제의 constraint를 조금 느슨하게 바꾸어보자. 제약 조건이 더 약한 문제인데도 불가능하다면, 조건이 더 강한 문제는 당연히 불가능하다 - 자명하다. 자, 자, 문자열에 포함된 I의 갯수를 n 이라고 해보자.

시작할 때 n = 1 이다. n 은 0 보다 작아질 수 없다.

이건 자명하다. 그러면, 우리가 쓸 수 있는 규칙 4가지가 이 n을 어떻게 변화시키는지 보자.

1번 규칙: n -> n
2번 규칙: n -> 2n
3번 규칙: n -> n - 3
4번 규칙: n -> n

자, 조금 더 쉽게 바꾼 문제는 이렇다. n = 1 에서 시작해서 2를 곱하거나, 혹은 3을 빼는 것을 반복해서, n을 한번도 음수가 되지 않도록 유지하면서 n = 0 을 만들 수 있는가?

... 이렇게 바꾸면 바로 와닿지 않는다. 그래서 문제를 한번 더 바꿔 보았다. 이번에는 문자열 안에 있는 I의 갯수를 3 으로 나눈 나머지를 n 이라 해 보겠다. - 왜 하필 3인가? ... 어쨌든 마지막은 3을 빼서 n = 0 이 되어야 하므로(2를 곱해서 0을 만들려면 이전의 n=0이어야 한다 -_-) n은 반드시 3이 되어야 한다. 연쇄적으로 생각하면 일단 n 이 3의 배수가 되는 순간 0 을 만드는 방법은 자명해진다. 3을 계속 빼면 되니까. 그러니 3의 배수 만들기를 생각해본 것이다.

시작할 때 n = 1 이다, n 은 0, 1, 2 중 하나이다.

역시 이건 자명하다. 이제, n의 값을 각 규칙이 어떻게 바꾸는지 보자.

1번 규칙: (0, 1, 2) -> (0, 1, 2)
2번 규칙: (0, 1, 2) -> (0, 2, 1)
3번 규칙: (0, 1, 2) -> (0, 1, 2)
4번 규칙: (0, 1, 2) -> (0, 1, 2)

조금 더 이해가 쉽도록 중복을 제거하고 세로로 써볼까? 아래와 같은 두개의 mapping 이 가능하다.

0 -> 0
1 -> 1
2 -> 2

0 -> 0
1 -> 2
2 -> 1

이렇게 두 개의 mapping을 가지고 1을 0으로 보낼 수 있는가? 없다. 1, 2 사이에서만 왔다갔다 할 뿐. 즉, I 가 하나 포함되어 있는 문자열에서 I 가 3의 배수개(0, 3, 6, 9 ... 등) 들어있는 문자열은 만들어낼 수 없다는 것.

... 이정도면 스스로는 납득했음. 조금 더 formal 하게 쓰는 연습을 해도 좋겠지만 今日はここまで。

'Tech' 카테고리의 다른 글

CUDA Driver/Toolkit/SDK 설치하기 (Ubuntu 9.04 Jaunty)  (2) 2009.09.17
Parameter vs Argument  (3) 2009.01.21
GEB: MU puzzle  (4) 2008.10.20
MySQL -> XML: CDATA Sanitize?  (2) 2008.09.26
하위 디렉토리에 있는 모든 .svn 을 날리는 법  (5) 2008.09.11
Spiral number galaxy  (4) 2008.08.09
Trackbacks 0 : Comments 4
  1. Favicon of http://grow.egloos.com 지아 2008.10.21 13:22 Modify/Delete Reply

    조금만 더 읽으시면 저런 규칙들이 복잡하게 나오기 시작하는데요....
    저는 거기에서 포기 ㅡ _ ㅡ;;

  2. Favicon of http://deisys.net deisys 2008.10.21 13:59 Modify/Delete Reply

    지아 // 규칙은 거들(?) 뿐 .. =_=/

  3. Favicon of http://ccsakura.egloos.com .櫻. 2008.10.22 18:03 Modify/Delete Reply

    설명은 납득...
    내가 생각한 건 I의 갯수는 두배가 되거나, 3이 빼지거나 밖에 안 되므로, n = 2^a - 3b로 하고 2^a가 3으로 절대 나눠서 안 떨어진다는 걸 증명하면 될 듯... 간단하게 될 것 같긴 한데 금방 안 떠오르네... -_-;

    • Favicon of http://deisys.net dgoon 2008.10.22 18:06 Modify/Delete

      으흐흐 증명 어려워.. 근데 2^a - 3b 로 모든 숫자가 다 나타내어지나? 곱하다가 빼다가 다시 곱하다가 하면 안될것 같은데 =_=

Write a comment