유도 퍼즐

시리즈의 일부
퍼즐
종류들 추측 수수께끼 상황. 논리 절개요 인덕션 로직 그리드 자기 참조 기계 조합 건설 분리 잠그다 Go 문제 접이식 막대기 타일링 관광 슬라이딩 체스 메이즈(로직 메이즈) 단어와 숫자 크로스워드 스도쿠 퍼즐 비디오 게임 메이지 메타푸즐
토픽 브레인 티저 딜레마 착시 포장 문제 패러독스 문제 해결 퍼즐헌트 삼단논법 고정관념에서 벗어나다
리스트 불가능한 퍼즐 메이즈 비디오 게임 니콜리 퍼즐 타입 퍼즐 비디오 게임 퍼즐 토픽
v t

유도 퍼즐은 논리 퍼즐로, 다중 에이전트 추론의 예입니다. 여기서 솔루션은 유도 ^[1][2]원리와 함께 진화합니다.

퍼즐의 시나리오는 항상 같은 추론 능력을 가진 여러 명의 플레이어가 같은 추론 단계를 거치게 됩니다.유도 원리에 따르면, 가장 단순한 경우의 해법은 다음 복잡한 경우의 해법을 명확하게 한다.유도 퍼즐의 가장 간단한 경우가 해결되면 전체 퍼즐은 그 후에 해결된다.

이러한 퍼즐의 대표적인 표시 기능에는 각 참가자가 다른 모든 참가자에 대한 정보(일반적으로 상식으로서)를 가지고 있지만 자신에게는 없는 퍼즐이 포함된다.또한, 보통, 참가자들이 서로의 지능을 믿을 수 있다는 것을 암시하기 위해 어떤 힌트가 주어집니다 - 그들은 심리 이론을 할 수 있습니다 ("모든 참가자들이 모더스 포넨을 알고 있다"는 것은 상식입니다).^[3]또한, 참가자의 무활동은 참가자의 지식 부족에 대한 비언어적 의사소통이며, 이것은 그 무활동 상태를 관찰한 모든 참가자에게 상식이 된다.

진흙투성이 어린이 퍼즐은 인식론적 ^[4][5]논리에 관한 과학 문헌에서 가장 자주 등장하는 유도 퍼즐이다.2020년 2월 구글 스콜라 조회수 437건에 진흙투성이 어린이 ^[6]퍼즐이 언급됐다.진흙투성이 어린이 퍼즐은 잘 알려진 현인이나 바람피우는 아내/남편 ^[7]퍼즐의 변형이다.

모자 퍼즐은 ^[8]1961년부터 시작된 유도 퍼즐 변형입니다.많은 변형에서 모자 퍼즐은 ^[9][10]죄수들의 맥락에서 묘사된다.다른 경우, 모자 퍼즐은 ^[11][12]현자의 맥락에서 묘사된다.

머디 칠드런 퍼즐

묘사

주의 깊은 아이들이 한 세트 있다.그들은 완벽하게 논리적으로 생각한다.아이들은 얼굴이 흙탕물일 가능성이 있다고 생각한다.어느 아이도 자신의 얼굴 상태를 스스로 판단할 수 없다.하지만, 모든 아이들은 다른 모든 아이들의 얼굴 상태를 알고 있습니다.관리인은 적어도 그들 중 한 명은 얼굴이 흙탕물이라고 아이들에게 말한다.아이들은 각자 자신의 얼굴이 흙탕물인 것을 알면 앞으로 나와야 한다고 한다.그 후, 관리인은 숫자를 세기 시작하고, 모든 진흙투성이의 아이들은 ^[4][5][13]앞으로 나아갈 기회를 갖게 된다.

논리 솔루션

자녀가 2명뿐이라고 가정합니다.앨리스와 밥.앨리스만 지저분하다면, 다른 더러운 얼굴을 볼 수 없기 때문에 그녀는 단번에 앞으로 나갈 것이다.밥도 마찬가지야.만약 앨리스가 밥이 첫 번째 스트로크에 나서지 않는 것을 본다면, 그녀는 밥이 틀림없이 또 다른 진흙탕 아이를 보고 두 번째 스트로크에 두 사람이 동시에 앞으로 나설 것이라고 결론지어야 한다.

아이가 3명밖에 없다고 가정해 봅시다.앨리스, 밥, 찰리.진흙투성이의 아이가 3명 미만일 경우, 2명의 아이가 있는 경우와 같이 퍼즐이 진화합니다.만약 찰리가 앨리스와 밥이 진흙탕이 되어 두 번째 스트로크에서 앞으로 나가지 않는 것을 본다면, 세 번째 스트로크에서는 모두 함께 앞으로 나갈 것이다.

X($디스플레이 스타일$ X$)$ 스트로크 ^[4][14]$후{\displaystyle }$ X$($디스플레이$$ 스타일 X) 진흙투성이$$ 어린이가 앞으로 나아간다는 $것$을 증명할 수 있다.

게임 이론 솔루션

진흙투성이의 어린이 퍼즐은 ^[13]게임 이론의 역유도를 이용해 풀 수도 있다.진흙투성이 어린이 퍼즐은 불완전한 정보의 광범위한 형태 게임으로 표현될 수 있다.모든 플레이어에게는 두 가지 행동이 있습니다. 뒤로 물러서는 것과 앞으로 나아가는 것.게임 시작에는 선천적으로 진흙투성이의 얼굴과 진흙투성이의 얼굴을 가르는 움직임이 있다.아이들은 비협조적인 게임처럼 의사소통을 하지 않는다.모든 스트로크는 아이들의 동시 동작이다.그것은 길이가 무제한인 연속적인 게임이다.게임 이론 솔루션에는 다음과 같은 추가 전제 조건이 필요합니다.

1. 모든 아이들은 이성적이고 모든 아이들의 합리성은 상식이다.이것은 앨리스가 이성적이라는 것을 의미하고, 앨리스가 밥이 이성적이라는 것을 알고, 앨리스가 밥이 찰리가 이성적이라는 것을 알고 있다는 것을 의미하며, 그 반대도 마찬가지입니다.
2. 얼굴에 흙탕물을 묻히지 않고 앞으로 나서는 것은 큰 벌칙을 낳는다.
3. 얼굴에 흙탕물을 묻히고 앞으로 나서는 것은 보상을 낳는다.
4. 모든 뇌졸중은 그들 중 한 명이 나설 때까지 모든 어린이에게 마이너스의 패널티 할인 요인을 초래한다.사소한 벌칙의 배수는 항상 큰 벌칙보다 덜 나쁜 것이다.

만약 앨리스만 진흙탕이라면, 마지막 추측은 앨리스가 망설이는 것을 불합리하게 만든다.앨리스와 밥이 흙탕물이라면 밥이 첫 번째 스트로크 이후 물러서는 유일한 이유는 흙탕물 없이 앞으로 나아가는 큰 벌을 받기 위해서라는 것을 앨리스는 알고 있다.$진흙투성이$ 어린이$X의$$,$ $X의$작은$$ 벌칙을 $받는{\displaystyle }$ 것이 여전히 큰 벌칙보다 낫다.

왕의 현인 모자 퍼즐

묘사

왕은 자신의 새로운 조언자가 누가 될 것인지를 결정하기 위해 나라에서 가장 현명한 세 사람을 궁전으로 불러들였습니다.그는 그들의 머리에 각각 모자를 씌웠다. 그래서 각 현명한 사람들은 다른 모든 모자를 볼 수 있었지만, 그들 중 누구도 그들 자신의 모자를 볼 수 없었다.각각의 모자는 흰색이거나 파란색이었다.왕은 현명한 사람들에게 그들 중 적어도 한 명은 파란 모자를 쓰고 있다고 약속했습니다. 다시 말해, 하나, 둘 또는 세 개의 파란 모자가 있을 수 있지만, 0은 될 수 없습니다.왕은 또한 이 대회가 세 남자 모두에게 공평할 것이라고 발표했다.현명한 사람들은 또한 서로 말하는 것이 금지되었다.왕은 어떤 사람이 먼저 일어나서 자신의 모자 색깔을 정확하게 발표하면 그의 새로운 조언자가 될 것이라고 선언했다.현명한 사람들은 한 사람이 일어서서 정답을 정확하게 발표하기 전에 매우 오랜 시간 동안 앉아 있었다.그가 뭐라고 말했고, 어떻게 알아냈을까요?

솔루션

왕의 현자는 가장 간단한 유도 퍼즐 중 하나이며 사용된 방법에 대한 가장 명확한 지표 중 하나이다.

• 파란색 모자가 하나 있다고 가정해봅시다.그 모자를 쓴 사람은 두 개의 하얀 모자를 보게 될 것이고, 왕이 적어도 한 개의 파란 모자가 있다고 명했기 때문에, 그 현명한 사람은 그의 모자의 색깔을 즉시 알 수 있을 것이다.그러나 나머지 두 마리는 파란색과 흰색 모자 하나를 보게 될 것이며 관측 결과로부터 어떤 정보도 즉시 추론할 수 없을 것이다.따라서, 이 시나리오는 각자에게 공평할 것이라는 왕의 규정을 위반하는 것이다.그래서 적어도 두 개의 파란 모자가 있어야 합니다.
• 그러면 파란색 모자가 두 개 있다고 가정해봅시다.파란 모자를 쓴 각 현명한 사람은 파란색과 하얀색 모자를 하나씩 보게 될 것이다.(앞의 시나리오를 사용하여) 단 하나의 모자가 존재할 수 없다는 것을 이미 알고 있다면 적어도 두 개의 파란 모자가 있어야 한다는 것을 알 수 있으며, 따라서 각각 파란색 모자를 쓰고 있다는 것을 즉시 알 수 있습니다.하지만 하얀 모자를 쓴 남자는 두 개의 파란 모자를 보게 될 것이고 그의 관찰로부터 어떤 정보도 즉시 추론할 수 없을 것이다.따라서 이 시나리오는 또한 경합이 각자에게 공정하다는 규정에도 위배된다.그럼 파란색 모자가 세 개 있는 게 틀림없어요.

파란 모자가 세 개 있어야 하니까 그걸 가장 먼저 알아챈 사람이 일어나서 파란색이라고 할 거예요.

대체 솔루션:이것은 각자에게 공정한 경기라는 규칙을 요구하지 않는다.오히려 그들이 모두 현명한 사람이라는 사실과 그들이 해결책을 찾기까지는 시간이 좀 걸린다는 사실에 의존한다.파란색 모자 1개, 파란색 모자 2개, 파란색 모자 3개 등 세 가지 시나리오만 사용할 수 있습니다.만약 파란색 모자가 하나밖에 없다면, 그 모자를 쓴 사람은 두 개의 하얀 모자를 보게 될 것이고, 곧 그가 파란색 모자를 써야 한다는 것을 알게 될 것입니다. 그래서 그는 일어서서 바로 이것을 알리게 될 것입니다.이런 일이 일어나지 않았으니 적어도 두 개의 파란 모자가 있을 것이다.만약 두 개의 파란 모자가 있다면, 파란 모자를 쓴 사람들 중 한 명은 건너다보고는 한 개의 파란 모자와 한 개의 하얀 모자를 보겠지만, 그들 자신의 모자의 색은 알 수 없을 것이다.만약 파란 모자를 처음 쓴 사람이 그가 하얀 모자를 썼다고 가정한다면, 그는 파란 모자를 쓴 다른 사람이 두 개의 하얀 모자를 보고 있다는 것을 알게 될 것이고, 따라서 파란 모자를 쓴 두 번째 사람은 이미 일어나서 그가 파란 모자를 썼다고 발표했을 것이다.따라서, 이 일이 일어나지 않았기 때문에, 파란 모자를 처음 쓴 사람은 그가 파란 모자를 썼다는 것을 알게 될 것이고, 일어나서 이것을 알릴 수 있을 것이다.한두 개의 파란 모자가 너무 쉽게 풀리고, 아무도 빨리 일어서지 않았기 때문에, 그들은 모두 파란 모자를 쓰고 있을 것이다.

조세핀의 문제

묘사

조세핀 왕국에서는 모든 여성이 결혼을 ^[15]허락받기 전에 논리 시험을 통과해야 한다.모든 기혼 여성들은 자신의 남편을 제외한 왕국의 모든 남성들의 정절을 알고 있으며, 에티켓은 어떤 여성에게도 남편의 정절에 대해 말해선 안 된다고 요구한다.또한 킹덤의 어느 집에서나 총성이 울릴 겁니다조세핀 왕비는 왕국에서 적어도 한 명의 바람난 남자가 발견되었고, 그녀의 남편이 바람을 피운 것을 아는 모든 여성은 그가 바람을 피운 다음날 자정에 그를 쏴야 한다고 발표했다.아내들은 어떻게 이 일을 처리했을까요?

솔루션

조세핀의 문제는 일반적인 사례의 또 다른 좋은 예이다.

• 불성실한 남편이 단 한 명이라도 있다면 왕국의 모든 여성은 그 사실을 알고 있습니다. 그의 아내는 모든 사람이 충실하다고 믿습니다.그래서 여왕으로부터 불성실한 남자가 있다는 말을 듣자마자 그녀는 남편이 불성실한 것이 틀림없다는 것을 알고 그를 쏜다.
• 불성실한 남편이 두 명이라면, 두 아내 모두 불성실한 남편은 한 명뿐이라고 생각합니다.따라서, 그들은 위의 사례가 적용될 것이고, 다른 남편의 아내가 다음날 자정에 그를 쏠 것이라고 예상할 것이다.총성이 들리지 않을 때, 그들은 위의 사례가 해당되지 않는다는 것을 깨닫게 될 것이고, 따라서 불성실한 남편이 한 명 이상일 것이고, (다른 모든 사람이 충실하다는 것을 알고 있기 때문에) 추가 한 명은 자신의 남편이어야 한다.
• 불성실한 남편이 3명일 경우 아내는 각각 2명이라고 생각하기 때문에 위의 사례가 적용되어 두 남편 모두 이틀째 총살될 것으로 예상하고 있습니다.총성이 들리지 않을 때, 그들은 위의 사례가 해당되지 않는다는 것을 알게 될 것이고, 따라서 불성실한 남편이 2명 이상일 것이고, 이전처럼 그들의 남편이 유일한 추가 후보자가 될 것이다.
• 일반적으로 불성실한 남편이 없는 경우, 각각의 아내는 n-1이 있다고 믿고 n-1일 자정에 총소리를 듣기를 기대합니다.그렇지 않을 때, 그들은 자신의 남편이 n번째라는 것을 안다.

이 문제는 바람피는 남편 문제, 불성실한 아내 문제, 진흙투성이 아이들 문제로도 알려져 있습니다.이것은 블루아이즈 문제와 논리적으로 동일하다.

이 문제는 류시원의 고전 교과서 '이산수학 원소'^{[citation needed]}에서도 검은 모자와 흰 모자와 관련된 문제로 나타난다.

논리학자회의 앨리스

묘사

논리학자 비밀회의에서 논리학자 마스터는 참석자의 머리에 띠를 달아 다른 사람들은 볼 수 있게 했지만 자신들은 볼 수 없었다.밴드에는 많은 다른 색깔들이 있었다.논리학자들은 모두 둥글게 둘러앉아 있었고, 마스터는 숲에 일정한 간격으로 종이 울리도록 지시했습니다: 논리학자가 자신의 이마에 색깔을 아는 순간, 그는 다음 벨을 울릴 것입니다.그들은 말을 하지 말거나 거울이나 카메라를 사용하지 말거나 논리적으로 밴드 색상을 결정하는 것을 피하도록 지시받았다.만약 어떤 사기꾼들이 회의에 잠입했다면, 누구든지 제 시간에 떠나지 않으면, 적절한 시기에 무뚝뚝하게 제거될 것이다.마찬가지로, 조퇴를 시도하는 사람은 누구든 퉁명스럽게 제자리에 붙잡혀 있다가 정확한 시간에 제거될 것이다.마스터는 그 퍼즐이 어떤 참 논리학자에게도 불가능하지 않을 것이라고 말하면서 그룹을 안심시켰다.어떻게 ^[16]한 거지?

솔루션

논리학 컨벤션에서 앨리스는 일반적인 유도와 비약적인 논리학이다.

• 비약적인 논리:모든 색상은 원 둘레에 두 번 이상 표시되어야 한다.왜냐하면 마스터가 논리학자가 퍼즐을 푸는 것이 불가능하지 않을 것이라고 했기 때문이다.만약 어떤 색이 원 주위에 단 한 번만 존재한다면, 그 색을 가진 논리학자는 그 색이 문제에 존재한다는 것을 알 길이 없을 것이고, 그들이 대답하는 것은 불가능할 것이다.
• 논리학자들은 각각 원을 둘러보고 각각의 색을 보는 횟수를 셀 수 있습니다.당신이 논리학자 중 한 명이고 다른 색을 한 번만 본다고 가정해 봅시다.각 색상이 원 둘레에 적어도 두 번 존재해야 한다는 것을 알고 있기 때문에, 싱글톤 색상에 대한 유일한 설명은 자신의 밴드 색이라는 것입니다.같은 이유로, 그러한 싱글톤 색상은 한 가지 밖에 없기 때문에, 첫 번째 벨이 울리면 출발합니다.
• 마찬가지로 다른 색을 한 번만 보는 논리학자는 자신의 색을 결정할 수 있어야 하며, 위엄 있게 떠나거나 잠입자로 쫓겨날 것입니다.마찬가지로 해당 색상의 띠가 두 개뿐인 색상은 첫 번째 벨이 울린 후 사라집니다.그 후 남은 색상의 밴드가 3개 이상 있어야 한다.
• 색상이 한 번 보이지 않지만 색상이 두 번 보인다고 가정합니다.만약 이 색깔의 띠가 이것뿐이었다면, 이 두 논리학자는 첫 번째 벨이 울렸을 때 떠났어야 했다.그렇게 하지 않았기 때문에, 그것은 당신의 밴드가 같은 색이기 때문에, 당신은 두 번째 벨에서 떠날 수 있습니다.
• 따라서, 모든 논리학자들은 그들이 떠날 것으로 예상한 특정 색깔의 집단이 떠날 때까지 지켜볼 것이다.그러면 그들은 그들이 그 색깔을 가졌다는 것을 알고 다음 벨을 울리면 떠날 것이다.
• 한 가지 색상만 남아 있으면 다른 색상을 가질 수 없다는 것을 알 수 있기 때문에 다음 벨에 그 색상이 모두 남습니다(그때부터 색깔을 알 수 없게 됩니다).

기본 모자 퍼즐

묘사

많은 선수들이 각각 다양한 색깔의 모자를 쓰고 있다.선수들은 적어도 몇몇 다른 선수들의 모자의 색상은 볼 수 있지만 그들 자신의 색상은 볼 수 없다.의사소통이 엄격히 제한되거나 전혀 제한되지 않은 일부 선수들은 모자의 색상을 추측해야 한다.문제는 선수들이 보는 모자와 다른 선수들이 하는 일을 바탕으로 모자의 색깔을 결정하는 전략을 찾는 것이다.어떤 버전에서는, 그들은 정확하게 추측하기 위한 첫 번째가 되기 위해 경쟁하고, 다른 버전에서는, 그들은 협력하고 ^[17]정확한 추측의 확률을 최대화하기 위해 미리 전략을 세울 수 있다.

토드 이버트의 1998년 캘리포니아 대학 ^[18]샌타바바라 박사 논문의 결과로 새로운 변종이 몇 가지 주목을 받았다.대수 코딩 ^[19]이론과 관련이 있는 협동 게임에 대한 전략 질문입니다.

세 명의 선수들은 각각 빨간 모자나 파란 모자를 받게 될 것이라고 한다.그들은 서로 마주보고 원을 그리며 서 있을 때 다른 선수에게 빨간 모자를 쓴 것을 보면 손을 들어야 한다.모자의 색깔을 정확하게 맞힌 사람이 이깁니다.

세 선수 모두 손을 들어주세요.몇 분 동안 서로 눈치 채지 못한 채 본 후, 한 선수가 "빨간색"을 발표하여 승리합니다.우승자는 어떻게 했는가?모자는 무슨 색인가?

솔루션

첫째, 만약 두 사람이 파란 모자를 썼다면, 모든 사람의 손을 들지 않았을 것이다.다음으로, 만약 선수 1이 선수 2의 파란 모자, 선수 3의 빨간 모자를 보았다면, 선수 1은 자신의 모자가 빨간색이어야 한다는 것을 즉시 알았을 것이다.따라서 파란색 모자를 보는 모든 선수는 한 번에 추측할 수 있다.마침내, 승자는 아무도 한번에 추측하지 않기 때문에, 파란 모자는 없어야 하고, 그래서 모든 모자는 ^[20]빨간색이어야 한다는 것을 깨닫는다.

모든 플레이어가 추측을 해야 하지만, 추측할 시기를 자유롭게 선택할 수 있는 경우, 모든 모자가 같은 색이 아니면 모든 플레이어가 정확하게 추측할 수 있는 협력 전략이 있습니다.각 참가자는 다음과 같이 행동해야 합니다.

1. 파란색 모자의 숫자 b와 빨간색 모자의 숫자 r을 세어보세요.
2. b초 또는 r초 중 빠른 것을 기다립니다.
3. 아직 아무도 말을 하지 않았다면, 빨간 모자보다 파란 모자를 적게 볼 수 있다면 파란 모자가, 파란 모자보다 빨간 모자를 적게 볼 수 있다면 빨간 모자가 아닐까 추측해보세요.
4. 아직 말을 하지 않았다면, 당신의 모자는 처음 말을 한 사람의 모자와 반대 색이라고 추측하세요.

총 B개의 파란색 모자와 R개의 빨간색 모자가 있다고 가정합니다.세 가지 경우가 있습니다.

B = R이면 파란색 모자를 쓴 선수는 B-1 파란색 모자와 B 빨간색 모자를 볼 수 있으므로, B-1초를 기다린 후 파란색 모자를 쓴 것으로 정확하게 추측한다.마찬가지로 빨간 모자를 쓴 선수들은 빨간 모자를 썼다는 것을 정확히 추측하기 전에 R-1초 동안 기다립니다.그래서 모든 선수들이 동시에 정확한 추측을 한다.

B < R일 경우 파란색 모자를 쓴 사람은 B-1 파란색 모자와 R 빨간색 모자가 표시되고 빨간색 모자를 쓴 사람은 B-1 파란색 모자와 R-1 빨간색 모자가 표시됩니다.B-1 < B r R-1 r r r r r r , , , , since wearing wearing wearing wearing wearing wearing , , , , , , , , , , , , , ,그러면 다른 선수들은 그들의 모자가 빨간색이라고 정확하게 추측한다.

R < B가 유사한 경우.

투 햇 바리안트

묘사

이 이야기에 따르면, 4명의 죄수가 범죄로 체포되지만, 감옥은 꽉 차서 간수가 그들을 가둘 곳이 없다.그는 결국 그들에게 퍼즐을 주는 해결책을 생각해냈다. 그래서 그들이 성공하면 그들은 자유로워지지만 실패하면 그들은 실행된다.

간수는 세 명의 남자를 한 줄로 앉힌다.B는 벽을 향하고, C는 B를 향하고, D는 C와 B를 향한다.네 번째 남자 A는 방충망(또는 별실) 뒤에 놓인다.간수는 네 사람 모두에게 파티 모자를 준다.그는 두 개의 검은 모자와 두 개의 하얀 모자가 있는데, 각각의 죄수들은 그 모자 중 하나를 쓰고 있고, 각각의 죄수들은 자기 자신이나 뒤에 있는 모자만 보고 있다고 설명한다.스크린 뒤에 있는 네 번째 남자는 다른 죄수들에게 보이거나 볼 수 없다.죄수들 간의 의사소통은 허용되지 않는다.

만약 어떤 죄수가 자신의 머리에 어떤 색깔의 모자를 쓰고 있는지 100% 확실히 알 수 있다면, 그는 그것을 발표해야 하고, 네 명의 죄수는 모두 석방되어야 한다.만약 어떤 죄수가 틀린 답을 제안하면, 4명의 죄수는 모두 처형된다.그 퍼즐은 죄수들이 어떻게 탈출할 수 있는지를 찾는 것이다.

솔루션

죄수들은 각 색깔의 모자가 두 개밖에 없다는 것을 안다.그래서 만약 D가 B와 C가 같은 색의 모자를 가지고 있다는 것을 알게 된다면, D는 자신의 모자가 반대 색이라고 추론할 것이다.그러나 B와 C가 다른 색상의 모자를 가지고 있다면 D는 아무 말도 할 수 없다.열쇠는 죄수 C가 적절한 간격을 두고 D가 어떻게 할지 안다면 D가 아무 말도 하지 않으면 B와 C의 모자가 달라야 한다는 것을 추론할 수 있다는 것이다. B의 모자를 볼 수 있다면 그는 자신의 모자 색깔을 추론할 수 있다.

이러한 유형의 많은 퍼즐과 마찬가지로 솔루션은 모든 참가자가 적절한 추론을 할 수 있을 만큼 합리적이고 지능적이라는 가정에 의존합니다.

이 퍼즐을 푼 후, 죄수 D의 의미 있는 침묵이 "소통 금지" 규칙을 위반하는지 곰곰이 생각해봄으로써 의사소통의 본질에 대한 어떤 통찰력을 얻을 수 있다.

스리 햇 바리안트

묘사

이 변종에는 3명의 죄수와 3명의 모자가 있습니다.각 죄수에게는 빨강 또는 파랑의 임의의 모자가 할당됩니다.모두 세 개의 빨간 모자와 두 개의 파란 모자가 있습니다.각자 두 사람의 모자는 볼 수 있지만 자신의 모자는 볼 수 없다.큐에 맞춰, 그들은 각자 자신의 모자 색깔을 맞히거나 통과해야 한다.그들은 적어도 한 사람이 맞혔고 아무도 틀리지 않았을 때 석방을 받는다(합격은 옳지도 그르지도 않다).

이 퍼즐에는 100% 성공 전략이 없기 때문에 다음과 같은 문제가 있습니다.가장 좋은 전략은 무엇입니까?승산이 가장 높은 전략은 무엇입니까?

모자 색상을 비트라고 생각하면 이 문제는 코딩 이론에서 중요한 응용 분야를 가지고 있습니다.

솔루션

이 퍼즐에 대한 해결책과 논의는 여기에서 찾을 수 있습니다(유사 7-hat 퍼즐에 대한 해결책이기도 합니다). 기타 3가지 변형은 이 Logic Puzzz 페이지(Masters of Logic I-IV)에서 확인할 수 있습니다.

4모자 변종

묘사

이 퍼즐의 변형에서, 죄수들은 두 개의 검은 모자와 두 개의 하얀 모자가 있고, A와 B 사이에 벽이 있다는 것을 알지만, 죄수 B, C, D는 그들 앞에 누가 있는지 볼 수 있다.D는 B, C와 벽을 보고, B는 벽을 보고, C는 B와 벽을 본다. (A는 다시 보이지 않고 검은 모자 중 하나를 쓰기 위해 그곳에 있을 뿐이다.)어떻게 의사소통을 하지 않고 그들 모두의 색깔을 추론할 수 있을까?

솔루션

두 가지 경우가 있다: 사소한 경우, 4명의 죄수 중 2명이 검은 모자를 쓴다.다른 두 명의 죄수는 각각 한 명의 죄수가 색상의 모자를 쓰고 있는 것을 볼 수 있다.사소하지 않은 경우, 죄수 4명 중 2명은 같은 색의 모자를 쓰고, A와 C는 검은색 모자를 쓴다.잠시 후, 4명의 죄수 모두 D와 B가 그들 자신의 모자의 색깔을 말할 수 없었기 때문에, A와 C는 검은 모자를 쓰고 있을 것이라고 추론할 수 있을 것이다.

파이브 햇바리안트

묘사

또 다른 변형에서는 3명의 죄수들과 알려진 색상의 5개의 모자(이 예에서는 검은색 2개와 흰색 3개)만이 관련된다.3명의 죄수는 A씨가 앞에, C씨가 뒤에 있는 등 정면을 향해 일직선으로 서도록 명령받았다.그들은 두 개의 검은 모자와 세 개의 하얀 모자가 있을 것이라고 한다.그리고 나서 각 죄수들의 머리에 한 개의 모자를 씌운다. 각 죄수들은 그들 앞에 있는 사람들의 모자만 볼 수 있고 그들 스스로는 볼 수 없다.자신의 모자 색깔을 정확하게 알릴 수 있는 첫 번째 죄수는 석방될 것이다.죄수들 간의 의사소통은 허용되지 않는다.

솔루션

A가 검은색 모자를 쓴다고 가정합니다.

• B씨도 검은 모자를 쓴다면 C씨는 앞에 있는 검은 모자 2개를 보고 하얀 모자를 쓴다는 것을 금방 알 수 있다.
• 만약 B가 하얀 모자를 쓴다면, C는 그의 모자 색깔을 구별할 수 없을 것이다(흑백이 있기 때문이다).그래서 B는 A의 검은 모자와 C의 무응답에서 그가 흰 모자를 쓰고 있다는 것을 재빨리 추론할 수 있다.

그래서 A가 검은 모자를 쓴다면 B나 C로부터 꽤 빠른 응답이 있을 것이다.

A가 흰색 모자를 쓴다고 가정합니다.

• C는 두 개의 검은 모자가 보이지 않아서 그의 모자 색깔을 구별할 수 없다.
• B는 하얀 모자만 보였기 때문에 그의 모자에 대해 아무것도 말할 수 없다.

이 경우 A, B, C는 한동안 침묵을 지켰기 때문에 최종적으로 A가 흰색 모자를 써야 한다는 결론을 내릴 때까지 침묵을 지킨다.

앞서 말한 바와 같이 흰 모자 3개와 검은 모자 2개가 있으며, 세 명의 죄수는 이것을 알고 있다.이 수수께끼에서, 당신은 세 죄수 모두 매우 영리하고 매우 똑똑하다고 가정할 수 있다.만약 C가 자신의 모자 색깔을 추측할 수 없다면 그것은 그가 두 개의 하얀 모자 혹은 각각의 색깔 중 하나를 보았기 때문이다.만약 그가 두 개의 검은 모자를 보았다면, 그는 그가 하얀 모자를 쓰고 있었다고 추론할 수 있었을 것이다.

10-Hat 변종

묘사

이 변종에는 10명의 죄수와 10명의 모자가 있습니다.각 죄수들은 빨간색이든 파란색이든 아무렇게나 모자를 배정받지만, 각각의 색깔의 모자 번호는 죄수들에게 알려지지 않았다.죄수들은 각자 앞에 있는 모자를 볼 수 있지만 뒤에 있는 모자를 볼 수 없는 한 줄로 늘어서게 될 것이다.줄 맨 뒤에 있는 죄수부터 시작해서 앞으로 나아가면, 그들은 각각 "빨간색" 또는 "파란색"이어야 하는 한 단어만 말해야 한다.그 단어가 그들의 모자 색깔과 일치하면 그들은 풀려나고, 그렇지 않으면 그들은 그 자리에서 죽는다.동정심 많은 교도관은 1시간 전에 이 실험에 대해 경고하고 명시된 규칙에 따라 수감자 10명 중 9명은 반드시 생존하고 1명은 생존 확률이 50대 50인 계획을 세울 수 있다고 말한다.목표를 달성하기 위한 계획은 무엇입니까?

솔루션

죄수들은 첫 번째 죄수가 홀수 수의 빨간 모자를 보면 "빨간색"이라고 말하는 것에 동의한다.이렇게 하면, 다른 9명의 죄수들은 뒤에 있는 죄수들이 반응한 후에 그들 자신의 모자 색깔을 알 수 있을 것이다.

10-Hat Variant(청각 없음)

묘사

전과 마찬가지로 10명의 죄수와 10명의 모자가 있다.각 죄수들은 빨간색이든 파란색이든 아무렇게나 모자를 배정받지만, 각각의 색깔의 모자 번호는 죄수들에게 알려지지 않았다.죄수들은 다른 사람들의 모자를 볼 수 있도록 방 안에 분산되어 있지만 자신의 모자는 볼 수 없다.이제, 그들은 각각 "빨간색" 또는 "파란색"이어야 하는 한 단어만 동시에 말해야 합니다.만약 그 단어가 그들의 모자 색깔과 일치한다면 그들은 풀려나고, 충분한 수의 죄수들이 그들의 자유를 재개한다면 그들은 다른 사람들을 구할 수 있다.동정심 많은 경비원이 그들에게 한 시간 전에 이 시험에 대해 경고한다.만약 그들이 정해진 규칙에 따라 계획을 세울 수 있다면, 10명의 수감자 중 5명은 반드시 석방되고 나머지 수감자들을 구조할 수 있을 것이다.목표를 달성하기 위한 계획은 무엇입니까?

솔루션

죄수들은 짝을 지어 갔다.죄수 A는 한 쌍(A, B)으로 B의 머리에 보이는 색을 말하고, B는 A의 머리에 보이는 색과 반대되는 색을 말한다.그리고 둘 다 같은 색의 모자를 쓰면 A가 해방되고(B가 해방되지 않음), 색상이 다르면 B가 해방됩니다(A는 해방되지 않음).총 5명의 죄수가 정답을 맞히고 5명은 정답을 맞히지 않습니다.이 경우 쌍은 누가 A이고 누가 B인지 통신할 수 있다고 가정합니다.이는 허용되지 않을 수 있습니다.

혹은 죄수들은 5명씩 두 개의 그룹을 짓는다.한 그룹은 빨간 모자의 수가 짝수라고 가정하고, 다른 그룹은 빨간 모자의 수가 홀수라고 가정합니다.청각 변종과 유사하게, 그들은 이 가정으로부터 그들의 모자 색깔을 추론할 수 있다.정확히 한 그룹이 맞기 때문에 5명의 죄수는 정답을 맞히고 5명은 정답을 맞히지 않습니다.

죄수들은 5명 이상의 죄수를 석방할 수 있는 전략을 찾을 수 없다는 점에 유의하십시오.사실, 한 명의 죄수에게, 그가 정답을 말하는 것은 그가 정답을 말하지 않는 것보다 더 많은 모자 색깔의 분포가 있다.따라서, 4명 이하의 죄수보다 6명 이상의 죄수들이 정답을 말하는 모자 색깔의 분포가 더 많다.

무청각 무한 모자 바리안트

묘사

이 변형에서는 셀 수 없이 많은 수의 죄수들이 알 수 없는 랜덤으로 할당된 빨간색 또는 파란색 모자를 사용하여 한 줄로 늘어선다.각 죄수들은 줄의 선두에서 얼굴을 돌리고, 각각의 죄수들은 앞에 있는 모든 모자를 볼 수 있지만 뒤에 있는 모자는 볼 수 없다.줄의 시작부터, 각 죄수들은 자신의 모자 색깔을 정확하게 식별해야 하며 그렇지 않으면 그는 그 자리에서 죽는다.전과 마찬가지로 재소자들은 사전에 만날 기회가 있지만, 전과 달리 일단 줄을 서면 다른 재소자들이 하는 말을 들을 수 없다.문제는, 정확히 많은 죄수들만 죽임을 당하도록 보장할 수 있는 방법이 있는가 하는 것이다.

솔루션

만약 어떤 사람이 선택의 공리를 받아들이고, 죄수들이 셀 수 없이 많은 양의 정보를 기억하고 셀 수 없이 무한한 계산 복잡성을 가지고 계산을 수행할 수 있는 (비현실적인) 능력을 가지고 있다고 가정한다면, 대답은 "그렇다"이다.사실, 우리가 셀 수 없이 많은 다른 색깔의 모자와 셀 수 없이 많은 죄수들을 허용하더라도, 선택 공리는 각각의 죄수들이 다른 죄수들의 모자를 볼 수 있다면, 완전히 많은 죄수들만이 죽어야 한다는 것을 보장하는 해결책을 제공합니다.ach 죄수는 다른 모자들을 거의 다 볼 수 있다.두 가지 컬러 케이스의 솔루션은 다음과 같으며 셀 수 없이 무한 컬러 케이스의 솔루션은 기본적으로 동일합니다.

일렬로 서 있는 죄수들은 0과 1의 시퀀스를 형성하는데, 여기서 0은 파란색을 나타내고 1은 빨간색을 나타냅니다.포로가 라인에 배치되기 전에, 포로가 배치될 수 있는 모든 가능한 시퀀스에 대해 다음과 같은 동등성 관계를 정의합니다.2개의 시퀀스는 한정된 수의 엔트리에서 동일한 경우 동일합니다.이 동등성 관계로부터 죄수들은 동등성 수업의 컬렉션을 얻는다.선택 공리를 가정하면, 대표 시퀀스의 집합이 존재합니다(각 등가 클래스에서 하나씩). (거의 모든 특정 값을 계산하는 것은 불가능하지만, 선택 공리는 일부 값 집합이 존재한다는 것을 의미하기 때문에 죄수들이 오라클에 접근할 수 있다고 가정합니다.)

각 죄수들은 한정된 수의 모자를 제외하고 모든 것을 볼 수 있고, 따라서 실제 모자 시퀀스가 어느 등가 클래스에 속하는지 알 수 있다(이는 각 죄수들이 셀 수 없을 정도로 무한한 수의 비교를 수행하여 일치점을 찾을 수 있다고 가정하며, 각 클래스 비교는 셀 수 없을 정도로 무한한 수를 필요로 한다).f개별 모자 사용).그런 다음 적절한 동등성 클래스의 대표 시퀀스에 있는 것처럼 모자 색상을 추측합니다.실제 시퀀스와 대표 시퀀스는 같은 등가 클래스에 있기 때문에, 어느 정도의 한정된 수의 N의 죄수 후에 엔트리는 같습니다.첫 번째 N명의 죄수 이후의 모든 죄수들은 구해진다.

죄수들은 그들 자신의 모자의 색깔에 대한 정보가 없고 어떤 색이든 같은 추측을 하기 때문에, 각 죄수들은 죽을 확률이 50%이다.무한한 수의 죄수들이 각각 살해될 가능성이 균등하지만 한정된 수의 죄수들만이 살해된다는 것은 역설적으로 보일 수 있다.이 역설의 해결책은 각 죄수의 추측을 결정하기 위해 사용되는 함수가 측정 가능한 함수가 아니라는 사실에 있다.

이것을 보기 위해, 0명의 죄수가 살해되는 경우를 생각해 보세요.이 문제는 실제 시퀀스가 선택한 대표 시퀀스 중 하나일 경우에만 발생합니다.0과 1의 시퀀스가 0과 1 사이의 실수의 2진수 표현으로 간주되면 대표 시퀀스는 측정할 수 없는 집합을 형성합니다.(이 세트는 Vitali 세트와 유사하며 유일한 차이점은 모든 유리수가 아닌 유한 2진수 표현을 가진 숫자에 관해 동등성 클래스가 형성된다는 것입니다.따라서 죄수 0명이 살해될 확률은 할당되지 않는다.이 주장은 살해되는 다른 유한한 수의 죄수들에 대해서도 비슷하며, 각 대표자들의 유한한 수의 변형에 대응합니다.

청각에 관한 무한 확장 모자 문제

묘사

이 변형은 재소자들이 다른 재소자들이 부르는 색깔을 들을 수 있다는 점을 제외하면 지난 번 것과 같다.문제는, 최악의 경우 가장 적은 수의 수감자들이 죽을 수 있는 최적의 전략은 무엇일까 하는 것이다.

솔루션

죄수들에게 다른 죄수들이 부르는 색깔을 듣게 한다면, 50% 확률로 죽는 첫 번째 죄수들을 제외한 모든 죄수들의 생명을 보장할 수 있다는 것이 밝혀졌습니다.

이를 위해 위와 동일한 동등성 관계를 정의하고 각 동등성 클래스에서 대표 시퀀스를 다시 선택합니다.각 클래스의 모든 시퀀스에 0 또는 1로 라벨을 붙입니다.먼저 대표 시퀀스에 0으로 라벨을 붙입니다.그런 다음 짝수 자리에서는 대표 시퀀스와 다른 모든 시퀀스를 짝수 자리에서는 짝수 자리에서는 대표 시퀀스와 다른 모든 시퀀스를 1로 표시합니다.이와 같이 가능한 모든 무한 시퀀스에 0 또는 1로 라벨을 붙였습니다.이러한 라벨은 1자리 차이밖에 나지 않는2개의 시퀀스에 반대 라벨이 붙는 중요한 속성입니다.

교도소장이 첫 번째 사람에게 색을 말하라고 할 때, 혹은 새로운 해석으로, 0이나 1을 말하라고 할 때, 그는 단순히 그가 보는 순서의 라벨을 부릅니다.이 정보를 통해, 그를 따르는 모든 사람들은 정확히 그의 모자 색깔이 무엇인지 결정할 수 있다.두 번째 사람은 첫 번째 사람이 보는 시퀀스의 첫 번째 숫자를 제외한 모든 숫자를 봅니다.따라서, 그가 아는 한, 첫 번째 사람이 라벨을 붙일 수 있는 두 가지 가능한 시퀀스가 있습니다. 하나는 0으로 시작하고 다른 하나는 1로 시작하는 시퀀스입니다.라벨링 방식 때문에 이 두 시퀀스는 서로 반대되는 라벨을 받기 때문에 첫 번째 사람이 말하는 것에 따라 두 번째 사람이 두 가지 가능한 문자열 중 어떤 것을 봤는지 결정할 수 있으며, 따라서 그는 자신의 모자 색상을 결정할 수 있습니다.마찬가지로, 줄의 모든 후반 사용자는 자신의 모자 색상에 대응하는 숫자를 제외한 모든 숫자를 알고 있습니다.그는 자기보다 먼저 온 사람들을 그들이 불러서 알고 있고, 그를 뒤쫓는 사람들을 볼 수 있기 때문에 알고 있다.이 정보를 통해, 그는 자신의 모자 색깔을 결정하는 데 첫 번째 사람이 부르는 라벨을 사용할 수 있다.그래서 첫 번째 사람을 제외한 모든 사람은 항상 정확하게 맞힙니다.

에버트 버전과 해밍 코드

묘사

Ebert의 문제 버전은 추측하는 모든 플레이어는 미리 정해진 시간에 추측해야 하지만 모든 플레이어가 추측해야 하는 것은 아니라고 말합니다.모든 선수들이 정확하게 추측할 수 있는 것은 아니기 때문에, 적어도 한 명의 선수가 맞히면, 그리고 맞힌 사람들이 모두 이기게 된다.어떻게 하면 선수들이 이길 확률을 극대화할 수 있을까요?

솔루션

이 버전의 모자 문제를 해결하기 위한 한 가지 전략은 데이터 전송 오류를 감지하고 수정하는 데 일반적으로 사용되는 Hamming 코드를 사용합니다.퍼즐 구성의 플레이어 수에 따라 당첨 확률이 50%보다 훨씬 높아집니다. 예를 들어, 7명이 당첨될 확률은 87.5%입니다.

N = 2-1^k 팀 규모에도 유사한 전략을 적용하여 승률(2-1^k)/2를^k 달성할 수 있다.따라서 Hamming 코드 전략은 N 값이 클수록 더 큰 윈률을 산출합니다.

이 버전의 문제에서는 개인의 추측이 맞을 확률이 50%입니다.그러나 Hamming 코드 접근법은 모자의 특정 분포에 잘못된 추측을 집중함으로써 작동합니다.경우에 따라서는 모든 플레이어가 잘못 추측할 수도 있고, 다른 경우에는 한 명의 플레이어만 맞힐 수도 있지만, 정확히 맞힐 수도 있습니다.모든 추측의 절반은 여전히 틀리지만, 이는 플레이어가 50% 이상 승리하는 결과를 낳는다.

이러한 유형의 솔루션에는 3명의 참가자가 참가하고 있는 예가 도움이 됩니다.3명의 선수에게는 8가지 가능성이 있다.그 중 2명의 선수는 모두 같은 색의 모자를 쓰고, 나머지 6명의 선수는 한 가지 색을 가지고, 나머지 6명의 선수는 다른 색을 가지고 있다.

플레이어는 다음 전략을 통해 후자의 경우(75%)에 반드시 승리할 수 있습니다.

1. 서로 다른 색깔의 두 모자를 관찰하는 선수는 침묵을 지킨다.
2. 같은 색의 두 모자를 관찰하는 선수는 반대 색을 추측한다.

세 선수 모두 같은 모자 색깔을 가지고 있는 두 가지 경우, 그들은 모두 잘못 추측할 것이다.그러나 나머지 6개의 경우, 오직 한 명의 선수만이 그의 모자가 동료 ^[21]선수들과 정반대라고 정확하게 추측할 것이다.

스니치빌의 집

묘사

스니치는 닥터의 생물이다.수스의 유명한 이야기 "스니치".스니치에는 별배와 평범한 배 두 종류가 있다.모든 스니치는 제한된 수의 집을 가지고 있고 각 가정에 별배 스니치와 평범한 배 스니치를 한 개 이상 포함할 수 없는 엄격한 주택법을 가진 스니치빌에 살기 위해 논리 테스트를 통과해야 한다.어떤 스니치도 자신의 배는 볼 수 없지만, 다른 스니치의 배는 볼 수 있다.스니치들 간의 더 이상의 충돌을 막기 위해 스니치들이 그들의 배에 대해 논의하는 것을 금지하는 법이 있다.각 스니치는 입주할 수 없는 것이 확실해질 때까지 집을 건너뛸 수 없다.스니치가 법을 어기면 처형된다.스니치 가족은 어떻게 ^[22]집을 고를까?

솔루션

모든 Sneches가 잠재적으로 위험에 처해 있기 때문에 하나의 해결책은 모든 Sneches가 거리에서 만나는 것입니다. 이 모델은 집, 즉 도로, 거리 또는 가까운 곳을 나타냅니다.거기서, 그들은 비슷해 보이고 비슷해 보이는 스니치로부터 멀리 떨어져 있는 스니치 쪽으로 이동하는데 동의한다; 이것은 신체적인 특징, 즉 복부 상태에 대해 구체적으로 의사소통할 필요성을 없애준다.스니치 운동은 브라운 운동에서 시작되지만 진흙투성이 어린이 문제의 논리에서와 같이 뭉치는 운동으로 변한다. 예를 들어, 한 스니치 운동은 두 개의 유사한 스니치 운동으로 이동하거나 거부되고, 결국 두 그룹의 결과인 별배와 평범한 배라는 하나의 상태 공간이다.첫 번째 그룹의 스니치 한 명이 먼저 각 집에 가고, 두 번째 그룹의 스니치 한 명이 각 집에 갑니다.

「 」를 참조해 주세요.

• 인식론적 논리
• 상식(논리)

레퍼런스