모자 퍼즐: 유한/무한 죄수 문제와 선택공리
Source
Evernote/Article Scraps/오늘의유머 - 수학의 부스러기 3. 모자 퍼즐.md
Summary
이 문서는 ‘모자 퍼즐’이라는 수학 논리 문제를 통해 유한한 경우의 모듈러 연산 전략과 무한한 경우의 선택공리(Axiom of Choice) 적용을 설명한다. 유한 명(100 명)의 죄수 문제에서는 맨 뒤 사람이 앞사람 모자 색의 개수 합을 모듈러 연산 (mod n) 으로 전달하면, 나머지 죄수들은 이를 통해 자신의 모자 색을 100% 정확히 추론할 수 있다. 반면, 무한 명(자연수 개)의 죄수가 앞사람의 말을 들을 수 없는 상황에서는 직관에 반하는 결과가 나온다. 선택공리를 이용해 모든 가능한 모자 배열을 ‘유한 개 이후로 일치하는 것’으로 동치류 (equivalence class) 로 분류하고 대표원을 선택하면, 각 죄수는 자신이 속한 동치류의 대표 배열을 추측함으로써 유한 명을 제외한 나머지 무한 명의 죄수가 모두 석방되는 전략이 존재함을 보인다.
Key Points
- 유한 죄수 문제 (n 명, k 색): 맨 뒤 사람이 보이는 모자 색의 합을 k 로 나눈 나머지를 말하면, 나머지 n-1 명은 자신의 모자 색을 100% 맞출 수 있다. (모듈러 산술 활용)
- 무한 죄수 문제 (자연수 개, 앞사람 말 듣지 못함): 직관적으로는 불가능해 보이나, 선택공리를 통해 해결 가능한 전략이 존재한다.
- 동치류 (Equivalence Class) 정의: 두 모자 배열이 유한 개 지점 이후부터 완전히 일치하면 같은 클래스로 간주한다.
- 선택공리의 적용: 각 동치류에서 하나의 ‘대표 배열’을 선택한다. 죄수들은 자신이 본 앞의 무한한 모자 배열이 속한 클래스의 대표 배열을 자신의 전체 배열로 추측한다.
- 결과: 실제 배열과 추측한 대표 배열은 유한 개만 다르므로, 유한 명만 실패하고 나머지 무한 명은 모두 성공한다. 이는 직관에 위배되는 선택공리의 성질을 잘 보여준다.