당사의 퍼즐 작업 지난 달은 저장하는 것이 었습니다 스타 트렉 가 이끄는 XNUMX인의 표면당 Enterprise 통신 장교 우후라 중위 (늦은 사람이 연주 Nichelle 니콜스). 승무원들은 외계 종족인 카테나티에 의해 지구에 있는 행성에 갇히게 됩니다. 목걸이 성운. 탈출하려면 처음에는 성공 확률이 낮아 보이는 작업을 수행할 확률을 최대화해야 합니다.
XNUMX명의 승무원은 자유롭게 의사소통하고 전략을 세울 수 있는 휴게실에 임시로 수용되어 있는 동안 작업에 대한 정보를 받습니다. 몇 시간 후에 그들은 한 번에 하나씩 룰렛 챔버라고 불리는 방으로 안내될 것입니다. 이 방에는 일렬로 배열된 XNUMX개의 버튼이 있으며, 각 버튼은 다른 승무원에게 응답하도록 프로그래밍되어 있습니다. 승무원을 오도하기 위해 각 버튼에는 무작위로 다른 승무원의 이름이 잘못 표시되어 있습니다. 각 승무원은 순서에 상관없이 최대 XNUMX개의 버튼을 누를 수 있습니다. 버튼을 누를 때마다 버튼이 실제로 누구에게 속하는지 알 수 있습니다. 네 번의 시도 내에서 그들은 자신에게 할당된 버튼을 찾아야 합니다. 선원들이 풀려나기 위해서는 모두 이 임무에 성공해야 합니다. 하나라도 실패하면 모두 실행됩니다. 승무원이 시도를 완료한 후에는 승무원에게 정보를 전달할 방법 없이 격리되어야 합니다.
성공 가능성은 희박해 보인다. 승무원이 무작위로 버튼을 선택하면 각자 버튼을 찾을 확률이 1/2입니다. 1명 모두 성공할 확률은 256분의 0.4, 즉 약 XNUMX%에 불과합니다.
그러나 무작위로 버튼을 누를 필요는 없습니다. 성공 확률을 높이는 한 가지 방법은 어떤 방식으로든 모든 버튼 누름을 균일하게 만드는 것일 수 있습니다. 이것은 우리를 첫 번째 퍼즐 질문으로 이끕니다.
퍼즐 1
무작위로 네 개의 버튼을 누르는 대신 각 버튼을 똑같이 자주 누르면 승무원의 생존 확률이 얼마나 향상됩니까?
롭 콜렛 과 제이파예트 그들은 다른 모든 질문을 했던 것처럼 이것에 잘 대답했습니다. 이 칼럼의 퍼즐 뒤에 숨겨진 핵심 아이디어는 Rob Corlett, JPayette 및 주니 세파넨 그것을 아름답게 묘사하면서 사차 부뇽 컴퓨터 솔루션에 기여했습니다.
Rob Corlett의 답변은 다음과 같습니다.
각 버튼을 같은 횟수로 누르도록 하는 한 가지 방법은 죄수를 동일한 크기의 4명씩 두 그룹으로 나누는 것입니다.
각 그룹은 해당 그룹의 구성원에 해당하는 버튼만 누릅니다. 따라서 A, B, C 및 D가 모두 동일한 하위 그룹에 있으면 A, B, C 및 D에 대한 버튼만 누릅니다.
이것은 문제를 모든 죄수가 올바른 그룹에 할당될 확률을 묻는 것으로 변경합니다. 그러면 네 번 이하로 버튼을 누를 수 있기 때문입니다.
첫 번째 그룹(따라서 두 번째 그룹도)을 4명으로 채우는 방법의 수는 C(8, 8) = 4인 70에서 70를 선택하는 방법의 수입니다. 따라서 모든 사람을 두 그룹에 할당하는 것은 XNUMX입니다.
각 죄수를 올바른 그룹에 올바르게 할당하는 할당이 하나만 있으므로 모든 사람이 올바른 그룹에 있고 모든 죄수가 살아남을 확률은 1/70이며 이는 이전 전략의 3.66/1보다 256배 더 좋습니다. [하지만 아직 아주 작은 확률입니다. 1.4%의 확률입니다.]
퍼즐 2
원래 암울한 확률을 90배 이상, 약 36.5%로 개선하는 방법이 있는데, 이는 기적처럼 보입니다! 이 전략은 추측의 고리나 연쇄를 사용하는 것과 관련이 있습니다. 따라서 목걸이 성운과 카테나티(체인 사슬을 뜻하는 라틴어). 전략의 기본 형태에서 각 승무원은 자신의 이름이 있는 버튼을 누르는 것으로 시작하여 첫 번째 버튼이 실제로 속한 승무원의 이름이 있는 버튼으로 이동하는 식으로 일련의 이름을 만듭니다.
이것이 실제로 어떻게 작동하는지 봅시다. 다이어그램에서 단추는 레이블이 흰색으로 표시됩니다. 아래의 파란색 문자는 버튼의 실제 소유자를 나타냅니다. 첫 번째 승무원 A는 룰렛 챔버에 들어가자마자 A 버튼을 먼저 누른다. 이것은 C의 버튼이므로 그녀는 다음으로 버튼 C를 누른 다음 버튼 E를 누르고 마지막으로 버튼 F를 누릅니다. 이 버튼은 실제로 A 자신의 버튼이므로 네 번의 시도에서 성공적으로 찾았습니다. 버튼 ACEF는 XNUMX개 버튼의 닫힌 루프를 형성합니다. 크루 C, E, F도 차례대로 돌아가면 각자의 자리에서 같은 폐회로를 돌고 네 번의 시도 끝에 자신의 버튼을 찾게 된다.
이 배열에는 각각 BD 및 GH라는 두 개의 버튼이 있는 두 개의 작은 루프도 있습니다. 이 네 명의 승무원은 두 번의 시도 안에 자신의 버튼을 찾을 수 있습니다. 따라서 이러한 배치로 모든 승무원이 성공하고 자유를 얻게됩니다. 배열에 길이가 4 이하인 루프만 포함되어 있으면 모든 승무원이 성공하고 풀려날 것입니다. 반면에 5개 이상의 단일 루프가 있는 경우 해당 루프의 모든 승무원은 5번의 시도에서 버튼을 찾지 못하고 해당 승무원은 처형됩니다. 성공 확률을 찾기 위해 루프가 6, 7, 8 또는 1일 확률을 찾아 더하고 5에서 해당 합계를 뺍니다. 이것은 다른 방법보다 계산하기 쉽습니다. 버튼에는 6, 7, 8 또는 XNUMX명의 멤버가 있는 단일 루프만 있을 수 있습니다.
8개가 있습니다! 8개의 버튼을 배열하는 다양한 방법. 그러나 루프를 만들 때 동일한 루프가 이러한 배열 중 8개를 설명합니다(ABCDEFGH는 BCDEFGHA와 동일한 루프를 형성하며 이는 CDEFGHAB 등과 동일함). 따라서 크기가 8인 루프가 있을 확률은 (8!/1)/8!이며, 이는 단순히 7/1입니다. 유사하게, 크기 7의 루프를 가질 확률은 6/1, 크기 6의 루프가 5/1, 크기 5의 루프가 있을 확률은 1/1입니다. 따라서 우리의 대담한 승무원의 성공 확률은 앞서 언급했듯이 5 - (1/6 + 1/7 + 1/8 + 36.5/XNUMX) 또는 XNUMX%입니다.
위의 전략은 모든 수의 죄수에게 적용되며 무작위 접근 방식에 대한 확률의 개선은 그 수가 증가함에 따라 빠르게 증가합니다. 24명의 죄수는 약 93배, 3.8명의 경우 10배, XNUMX명의 경우 XNUMX배, 그리고 놀라운(XNUMX × XNUMX)29) - 100명의 죄수를 위해 접습니다. 이 엄청난 증가를 이해하는 열쇠는 방법이 그룹의 각 구성원의 성공 또는 실패를 다른 구성원의 성공 또는 실패와 묶는다는 것입니다. 매우 광범위하게, 그들은 모두 함께 성공하거나 실패합니다. 집단의 성공확률은 50인에 비해 크게 떨어지지 않고, 30.69인의 경우 XNUMX%에 불과했지만, 수감자가 무한정 늘어나면서 XNUMX%로 떨어졌다. 반면에 무작위 접근 또는 심지어 "짝수 버튼 누름" 접근이 성공할 확률은 적은 수의 수감자에 대해서도 거의 XNUMX에 가깝게 빠르게 감소합니다.
이 전략의 논리가 여전히 모호한 것 같으면 여기에서 100명의 죄수 문제에 대한 분석이 있습니다. Veritasium의 우수한 비디오.
퍼즐 3
이 퍼즐은 본질적으로 같은 퍼즐이지만 여섯 명이 할 수 있는 어린 시절 게임을 기억하는 Uhura 중위의 이야기였습니다. 힌트로 XNUMX명이서 문제를 푸는 것을 제안했습니다. 이제 공식이 있으므로 확률을 쉽게 계산할 수 있습니다.
2명의 경우 가장 긴 루프가 1 또는 1일 확률은 1 - (3/1 + 4/41.7) 또는 XNUMX%이며 무작위 선택보다 XNUMX배 이득이 있습니다.
3명의 경우 가장 긴 루프가 2, 1 또는 1일 확률은 1 - (4/1 + 5/1 + 6/38.3) 또는 24%이며 무작위 선택보다 XNUMX배 이상 증가합니다.
퍼즐 4
우리의 이야기가 계속되면서, 카테나티 중 한 명이 Enterprise 승무원을 원격으로 모니터링하고 있습니다. 그는 그들이 Uhura의 다이어그램을 기반으로 몇 가지 효과적인 전략을 생각해 냈다고 의심합니다. 그는 룰렛이 시작되기 전에 방으로 들어가 의도적으로 버튼 레이블의 순서를 변경하여 그들의 계획을 저지하기로 결정했습니다. 그는 성공적으로 계획을 좌절시킬 수 있습니까? 상륙 당사자가 특히 조심해야 할 것은 무엇입니까?
승무원의 전략 논의 초기에 Uhura의 눈이 갑자기 가늘어졌습니다. 그녀는 승무원에게 신호를 보냈고 니콜라스로 말하기로 전환했으며 "모든 추가 논의는 니콜라스로 부탁드립니다."라고 발표했습니다. Nicholese는 Uhura가 만능 번역가의 사용을 피하기 위해 이러한 상황에서 경력 초기에 발명한 새로운 언어였습니다. "당신은 의심스러운 카테나티를 눈치채셨을 겁니다." 그녀가 말을 이어갔다. “그는 우리를 방해할 수 있으므로 계획을 수정해야 합니다. 여기 우리가해야 할 일이 있습니다 ... "
Uhura는 그녀의 모든 승무원이 그것을 완벽하게 알고 있다고 만족할 때까지 새로운 계획을 설명했습니다. 그런 다음 그녀는 멀리 바라보는 눈으로 생각했습니다. Starfleet이 우리의 모든 선박에 표준으로 만들도록 주장하게 되어 기쁩니다.”
그녀는 다시 승무원에게로 돌아갔다. “그게 다야, 장교들. 넌 뭘해야 할 지 알 잖아!"
우리는 Uhura가 그녀의 팀에게 정확히 무엇을 말했는지 모릅니다. 그러나 JPayette와 Rob Corlett는 꽤 좋은 아이디어를 가지고 있었습니다. 여기 Rob Corlett가 있습니다.
사악한 카테나티는 그들이 이 전략을 사용하고 있다는 소식을 듣고 4보다 긴 주기가 있는지 확인하기 위해 디스플레이에 표시된 이름을 전환할 수 있습니다.
이것을 깨기 위해 죄수들은 순서를 무작위로 지정하는 비밀 순서에 동의해야 합니다. 그들은 "Uhura의 이름이 보이면 Chekov라고 표시된 버튼으로 이동하십시오. Chekov의 이름이 표시되면 Smith 등으로 표시된 버튼으로 이동하십시오.”
이렇게 하면 승무원이 디스플레이의 이름에 응답하는 방식을 알고 있는 경우에만 작동하므로 Catenati에 의한 재정렬은 중요하지 않습니다. 그들은 재정렬 비밀을 유지해야 합니다. 그렇지 않으면 다시 깨질 수 있습니다.
우리가 보았듯이 Uhura는 비밀이 안전하게 유지되도록 보장했습니다. 승무원의 각 구성원은 동일한 비밀 명령을 사용하고 사악한 카테나티가 그것이 무엇인지 알지 못하도록 하기만 하면 됩니다. 사실, 사악한 카테나티에 의한 변경된 질서는 실제로 승무원의 성공 확률을 높였습니다!
이것이 일어난 일입니다. Uhura는 룰렛 챔버에 처음으로 데려간 사람이었습니다. 그녀는 세 개의 버튼을 눌렀다. 아무도 그녀의 것이 아니었다. 그녀는 슬퍼해야합니까 아니면 기뻐해야합니까? 그녀는 숨을 죽이고 네 번째를 눌렀다. 그녀는 자신의 진정한 버튼을 찾았습니다!
그녀는 그들이 모두 구원받을 것이라는 것을 알고 있었습니다.
퍼즐 5
랜딩 파티의 규모가 무한정 증가함에 따라 최대 성공률에 도달하는 한계는 무엇입니까? 이 방법이 임의의 버튼을 누르는 것보다 훨씬 더 효율적인 이유를 설명할 수 있습니까?
JPayette는 다음과 같이 썼습니다.
위의 모든 것은 2명의 승무원으로 간단하게 일반화됩니다.n 각 회원은 최대 누를 수 있습니다. n 버튼. 퍼즐 2에서 우리는 그들의 성공 가능성이
1 - (합계 k 사이에 n + 1 및 2n 1 // XNUMXk).
합계는 1/의 적분과 비교할 수 있습니다.x 간격 동안 [n, 2n], 이를 통해 우리는 다음과 같이 증명할 수 있습니다. n 무한대로 커지면 위의 확률이 감소하여 놀라운 1 − ln(2) ≈ 30.6%로 수렴됩니다. [실제로는 30.69%에서 소수점 이하 두 자리까지입니다.]
Rob Corlett는 다음과 같이 덧붙였습니다.
적분을 모르는 경우 스프레드시트를 사용하여 계산하여 대략적인 답을 빠르게 얻을 수 있습니다. 나는 한 번 0.307에 도착했다 n 소수점 750자리까지 정확한 약 3에 도달했습니다.
이 방법이 작동하는 이유는 위에서 이미 설명했습니다. 1보다 긴 모든 루프는 여러 승무원이 공유합니다. 따라서 그들의 성공과 실패는 매우 밀접한 관련이 있습니다. “하나를 위한 모든 것, 모두를 위한 하나”라는 원칙의 실례입니다. Starfleet 설명서에서 바로!
모든 기여자에게 감사드립니다. JPayette와 Rob Corlett는 모두 이 솔루션 열이 거의 중복된 것처럼 보이게 하는 가치 있는 답변을 제출했습니다. 아아, 퍼즐 열당 한 명의 승자를 선택하는 우리의 규칙을 고수해야 합니다. Insights 상은 여기와 이전 퍼즐의 기여를 인정하여 JPayette에게 돌아갑니다. 축하합니다! Rob Corlett, 귀하의 기여는 잊지 않을 것입니다.
다음 달에 새로운 인사이트로 만나요!
