MuPuzzle이란? ¶
GoedelEscherBach책 33~41쪽(영문판)에 나오는 퍼즐.
M,I,U로만 이루어지는 'MU문자열'들의 집합은 다음과 같이 재귀적으로 정의된다.
(단, x,y는 빈 문자열을 포함하는 임의의 문자열.)
- MI는 'MU문자열'이다.
- xI가 'MU문자열'이면 xIU도 그렇다.
- 예) MI -> MIU
- 예) MI -> MIU
- Mx가 'MU문자열'이면 Mxx도 그렇다.
- 예) MIU -> MIUIU.
- 예) MU -> MUU.
- 예) MIU -> MIUIU.
- xIIIy가 'MU문자열'이면 xUy도 그렇다.
- 예) MIIII -> MIU
- 예) MIIII -> MUI
- 예) MIIII -> MIU
- xUUy가 'MU문자열'이면 xy도 그렇다.
- 예) MUUU -> MU
- 예) MUUU -> MU
답안. (마우스로 긁으면 보임)
MU는 'MU문자열'이 아니다.-_-;;; 증명은 다음 링크를 참조. http://uzweb.uz.ac.zw/science/maths/zimaths/51/answers.htm |