혹시나 도움이 될지 몰라 제가 직관적으로 이해한 방식을 설명드리자면 자신의 번호에 맞는 숫자의 상자를 열게 됨으로써 모든 죄수들이 열게되는 첫 상자는 전부 다른 상자가 됩니다. 그리고 모든죄수들이 두번째로 열게 되는 상자도 전부 다른 상자가 되죠 모든 죄수들이 매 스텝마다 여는 상자가 전부 다르다는 조건을 이용해서 이 문제를 변형시킬 수 있습니다. 각 죄수가 한명씩 들어가서 자신의 번호를 찾는다고 생각하지 마시고 백명의 죄수가 한방에 동시에 들어가서 차례대로 상자에 선 뒤 상자를 하나씩 열어본다고 생각하는겁니다 첫번째 상자를 열고나면 그 다음상자를 열고 차례대로 한칸씩 움직이면서 50번을 여는것이죠 이렇게 하면 전원 생존할수 있는 확률은 내가 서있던 상자에서 50번의 이동 안에 내 숫자를 찾을 수 있는지에 따라 결정됩니다. 이 방식을 사용하면 1번 사람이 통과할 확률은 50/100 대략 50% 1번사람이 통과했다는 가정하에 2번사람이 통과할 확률은 1/100 * 50/99 (1번사람이 자기 자리에서 번호를 뽑을확률) + 99/100 * 49/99(1번사람이 자기자리에서 번호를 못뽑아서 2번사람의 50개의 후보군중에서 자기번호를 뽑을 확률) = 대략 49.5% 같은원리로 3번사람의 확률은 1/100 * (1/99 * 50/98+ 98/99 * 49/98) + 99/100 * (98/99 * 48/98 + 1/99 * 49/98) (1번 사람이 첫번째에 뽑고 2번 사람도 첫번째에 뽑을확률 + 1번사람 첫번째 2번사람 두번째이후 + 1번사람 두번째이후 2번사람 두번째 이후 + 1번사람 두번째 이후 2번사람 첫번째) = 대략 49% ... 50번 사람까지 통과했다면 전체 100개의 상자중에 50개는 이미 다른 사람들의 번호가 들어있어서 통과된것이므로 51~100번째 사람들은 거의 100%에 가까운 확률로 50번의 이동 안에 자신의 번호를 찾을 수 있게됩니다. 물론 극악의 확률로 못찾는 경우도 있을수 있지만 이미 1~50번의 사람들이 모두 통과했다는 가정을 했기때문에 통과하지 못하는 경우의 수는 거의 남아있지 않게됩니다. 이렇게 계산했을때 1번사람이 통과할확률 50퍼, 1~2번사람 모두 통과할확률 대략 49.5퍼, 1~3번 확률 대략 49퍼 이를 50번 한다고 치면 약 25퍼센트의 확률이 나오고 이는 30퍼센트와 비슷한 수치를 나타냅니다. 5퍼센트의 오차는 제가 정확히 계산하지 않고 소수점 아래자리를 버려서 0.5퍼씩 낮아진다고 계산해서 생긴 오차인듯 합니다. 제 설명을 통해 직관적 이해에 도움이 되셨으면 좋겠습니다.
자신의 번호를 고른 죄수의 숫자가 이항분포를 따르지 않는것이 인상적이네요. 어치피 100 밑의 결과는 패배니까 성공한 죄수의 수를 0부터 100까지 분포시키는게 아니라 100 아니면 그 밑의 값들로 극단화 시키는게 멋지네요. 다른 "완벽한 성공" 문제에도 충분히 적용시킬 수 있어보여서 더욱 좋은 것 같습니다
자신의 번호를 고른 죄수의 숫자가 이항분포를 따르지 않는것이 인상적이네요. 어치피 100 밑의 결과는 패배니까 성공한 죄수의 수를 0부터 100까지 분포시키는게 아니라 100 아니면 그 밑의 값들로 극단화 시키는게 멋지네요. 다른 "완벽한 성공" 문제에도 충분히 적용시킬 수 있어보여서 더욱 좋은 것 같습니다 . 맞춘 사람은 살려준다고 했을 때도 루프 전략을 쓰기로 합의 본다면 재밌는 점이 교도관은 1명 이상이 죽을 확률은 사실상 100%라고 생각했을텐데 사실은 70%라는거죠.. 만약에 돈을 걸고 하는 게임 같은건데 교도관 맡으면 질 수가 없다고 생각했다가 틀린 사람이 한명도 없는 순간 이게 가능할리가 없는데 하면서 멘탈 나가
파이썬입니다 import random N = 100 numbers = [i for i in range(100)] random.shuffle(numbers) summation = 0.0 for k in range(10000): random.shuffle(numbers) is_good = True for i in range(100): my_num = i is_flag = False for j in range(50): if numbers[my_num] == i: is_flag = True break my_num = numbers[my_num] if is_flag == False: is_good = False break if is_good == True: summation +=1.0 print(summation / 10000.0)
맞춘 사람은 살려준다고 했을 때도 루프 전략을 쓰기로 합의 본다면 재밌는 점이 교도관은 1명 이상이 죽을 확률은 사실상 100%라고 생각했을텐데 사실은 70%라는거죠.. 만약에 돈을 걸고 하는 게임 같은건데 교도관 맡으면 질 수가 없다고 생각했다가 틀린 사람이 한명도 없는 순간 이게 가능할리가 없는데 하면서 멘탈 나가는거죠...ㅋㅋㅋㅋㅋㅋㅋ
굉장히 흥미로운데요 12:56 이 문제의 해법에서 숫자를 5를 더한다고 하더라도 결국 루프의 길이는 변하지 않기에 30퍼센트가 아닌것 아닌가요? 루프의 길이가 100이라면 결국 0퍼센트에서 50퍼센트로 올라가지만 각자다른 여러개의 루프가 있다면 본인이 속하지 않은 루프로 빠질 수 있지 않을까요? 최초에 해법이 본인의 루프에서 벗어나지 못하므로 루프가 50이하인 경우에 모두 50회 이하의 도전에서 본인의 번호를 찾을 수 있다는 전제와 다른 것 아닌가요?
퍼즐 자체도 상당히 비 직관적이기 때문에 실제로 어떻게 될지 따져보는 쪽이 빠릅니다. 예를들어 가장 간단한 루프인 1->2->3->... 루프를 생각해봅시다. 여기서 중요한건 상자의 숫자만 바뀌는거지 종이의 숫자가 바뀌지는 않습니다. 만약 상자의 숫자를 모조리 1을 더한다면, 모든 상자 안에 자신의 숫자가 들어있게 됩니다. 잘 생각해보세요. 1이 2를 가리키고 있는 이유는 1상자 안에 2종이가 들어있기 때문입니다. 어째서 이런일이 일어났냐하면, 루프의 진행방식이 원래는 1씩 진행이었다면 상자의 숫자를 1 더하는것은 진행 숫자에서 -1을 하는것과 같기 때문입니다. 따라서, 루프의 진행이 0씩 진행이 되고 루프의 끝이 자기 자신의 숫자라는 규칙에 의해 모든 상자 안에 자신의 숫자가 들어가게 됩니다. 이것을 조금 더 복잡하게 생각해봅시다. 어떤 숫자가 있어서 이 숫자가 1에서 뺐을때, 1이 아닌 100의 최대 공약수를 만들수 있는 숫자라고 생각해봅시다. 가령 숫자를 5 더한다면, 1씩 진행이 1-5=-4씩 진행하게 되니까 최대공약수는 4지요. 이것은 루프의 진행이 정방향이나 역방향이나 루프는 변함이 없고, 성공조건이 루프의 길이뿐이기 때문에 가능합니다. 즉 이 루프는 1씩 진행이 아니라 -4씩 진행이고, 최대 루프의 묶음은 25가 될것입니다. 만약에 이 사실을 모른다고 하더라도 100보다 작은 100의 서로소는 1을 제외하고 39개입니다. 조금 더 복잡하게 생각해봅시다. 만약 죄수들끼리 의논해서 만든 새로운 숫자배열이 있어서, (예를들어, 1->33->23->64->71->... 라는 무작위 100길이의 루프형 숫자배열) 그 순서대로 진행한다면? 이걸 반대로 생각했을때 죄수들이 정상적인 숫자를 가지고 있고, 간수가 배열해 놓은 길이가 100인 루프를 아까 말한 새로운 숫자배열이라고 생각한다면? 아주 놀라운 결과입니다.
문제를 보고 즉흥적으로 바로 떠올랐던 생각이 '무작위의 죄수들이 같은 규칙으로 상자를 열게 해서 무작위성을 줄이면 확률이 획기적으로 확 오르지 않나?' 였는데 이렇게 일상적인 언어로 그 방법까지 자세하게 풀이된 걸 정독하니 지적 허영이 채워지는 것 같아 기분이 좋아지네요 이게 교양이 갖는 힘이겠죠. 저같은 멍청이들도 마치 스스로가 똑똑해지는 것 같은 기분을 느끼게 해 주니 아주 유쾌해지네요 좋은 영상 잘 보고 갑니다
확률이 높아지는 이유는 좀더 개념적으로 쉽게 설명하면, 죄수들마다 서로 다른 고유 번호 있고 그 번호로 인해 죄수들이 서로 겹치게 않게 시작 번호 상자를 여는 겁니다. 죄수들 모두가 랜덤하게 아무 상자나 열면서 시작하는 것과는 완전 다르죠. 이게 확률을 높이는 키워드입니다. 상자의 시작 번호가 고유적으로 다 다르게 되어 100명이든 100만명이든 그 죄수 만큼 상자 여는 시작 위치가 서로 달라 그 만큼 다시 상쇄됩니다. 그래서 결과적으로 죄수가 아무리 늘어나도 상자 50루프 해당되는 1/3정도 확률만 비슷하게 계속 남게 되는 겁니다.
그런데 회로의 개수를 구하는 과정에서 회로의 길이로 나눠주는 이유가 뭔가요?(길이 99짜리면 99로 나누는 등) 원순열 개념은 아는데 저 경우에는 모든 회로가 다 다른 것 아닌가요? 원순열은 회전하면 같지만 저건 한칸만 회전해도 한 박스에 들어간 숫자가 모두 달라지니까요.
이해가 좀 안되는 부분이 있어요 ㅠㅠㅠ 영상 마지막에 모두성공하거나 모두실패하며 소수의 인원만 숫자를 찾는 아쉬움이 없다고 했는데요 만약 1-100까지 중에 예를들어 1-10 11-70 71-100 이렇게 세개의 루프가 있다면 1-10과 71-100의 죄수들은 본인의숫자를 찾을 수있는거 아닌가요??
루프전략을 사용했을때와 그냥 무작위로 선택했을때의 차이를 말하는거 같아요 그냥 무작위 50%확률로 하면 99명이 찾았지만 1명이 못찾는다던지 해서 아쉽게 실패하는 경우가 있지만, 루프전략은 30% 확률로 ( 루프길이가 50이하일 확률 ) 모두 성공하거나 70%확률로 ( 루프길이가 50 이상일 확률 ) 와장창 실패하니까요, 한명이라도 틀린다면 실패한다는점이 중요한거같아요
왜 차이가 나는지 직관적 이해를 돕기 위하여.. 죄수들 끼리 논의를 하지 않았을 경우, 모든 죄수들은 무작위로 상자를 열 것이고, 서로 영향을 주지 않으므고 모든 사건은 독립 사건이 되며 미션 성공 확률은 1/2의 100승이 됩니다. 하지만 죄수들이 미리 두가지 규칙을 정할 경우 더이상 독립 사건이 되지 않습니다. 모든 죄수들이 여는 첫번째 상자는 절대로 중복되지 않으며, 따라서 모든 죄수들은 절대로 같은 루프를 통하지 않습니다. 그러므로 전체를 분석해 보면, 독립사건이 아니기에 정규분포를 따르지 않는 것입니다. 또한 규칙을 아는 교도관이 통제도 가능하고, 그걸 아는 죄수들도 대응이 가능해집니다. 무작위라는 독립사건에서는 이것이 불가능하죠.
아주 간단하고 직관적으로 설명해드릴게요 1. 본인의 숫자가 적힌 상자로 시작한 루프에는 본인의 숫자가 무조건 존재한다 2. 상자는 50개까지 열 수 있기때문에 본인의 루프를 구성한 상자의 갯수가 51개 이상이라면 실패한다 3. 100개의 상자와 숫자를 무작위로 배치했을때 51개 이상의 상자로 구성된 루프가 생성될 확률은 약 70% 이다 4. 그러므로 약 30% 의 확률로 죄수들은 생존할 수 있다 이해가 안되는 부분이 있다면 답글 ㄱㄱ
? 설명이 아주 직관적으로 1도 안됐는뎁쇼? 그냥 영상에 나온 내용 똑같이 정리해놓은 거잖아요 ㅋㅋㅋㅋ 이해가 안되는게, 내가 루프 방법을 따라서 내 숫자를 찾을 확률이 30% (이거 맞나요?) 그리고 내 다음 죄수가 자기 번호를 찾을 확률도 30%, 이 다음도, 또 그 다음도 30%. 그럼 결국 100명이 다 찾을 확률은 0.3^100 아닌가요? 오히려 무작위로 고르는 것보다 확률이 낮아지는게 아닌지..
@@user-cf6jo5qb7m 루프 방법으로 내 숫자를 찾을 확률은 100%이고 중요한건 그 루프의 길이입니다 열수있는 상자의 갯수가 50개로 제한이 되어있어서 루프의 길이가 50개를 넘어버리면 모두 죽는거구요 무작위로 배열했을때 길이가 50이 넘는 루프가 만들어질 확률이 약 70% 반대로 길이가 50이 넘는 루프가 없을 확률이 약 30%로 이 경우엔 모든 죄수가 본인의 루프에서 숫자를 찾아 살아남을 수 있습니다
@@ChaengLover 아? 그니까 상자에 숫자를 배포할때 생성되는 모든 루프들의 길이가 50이 안넘을 확률이 30%라는 건가요? 그래서 죄수들이 한명씩 들어가서 어떤 상자에서 시작하든 루프만 따르면 모두 살아나갈 확률이 30%라는거고? 살 확률과 죽을 확률은 교도관이 상자에 숫자를 배치할때 이미 정해지는거기 때문에? 제가 이해한게 맞나요?
직관적으로 이해 하기 위한 전략의 특징 - 한사람이 틀리면 다른 사람이 맞던 틀리던 다같이 죽는게 포인트 - 내 루프가 50개 이상의 루프면 내 루프 안에 포함된 50명 이상의 사람은 앞으로 다함께 틀리게 됨. '50개 이상의 루프가 있느냐'가 게임의 유일한 승패요인이 되어버림. 어쨌건 같은 고리를 공유한 사람들은 같은 승패결과를 가진 셈이니까. - 그리고 랜덤 배치에서 루프가 50개 이상일 확률은 대략 70% 메모리 위치(seq)를 서로 링크해서 가지고 있고, 검색시에는 이 링크된 메모리를 따라서 검색하다가, 만일 메모리 조회 횟수가 전체 데이터 갯수의 절반 이상인 검색이 발생하면 이 해당 검색이 시작된 메모리의 링크와 다른 (랜덤)메모리의 링크를 바꿔버리면(루프를 바꿔버리면) 검색을 할수록 검색 시간이 단축되겠네....
100개짜리 루프가 존재할 확률이 1/100 인건 이해하겠는데 그 이하부터는 계산방법이 달라져야 할 것 같은데. 99개짜리 루프가 있을 확률이 어떻게 1/99 이지? 분모는 여전히 100!이어야 하는거 아닌가? 90개짜리 루프가 존재할 경우의 수는 90개의 루프를 만들 수 있는 경우의 수에 나머지 10개로 만들 수 있는(1개 9개루프, 1개 2개 3개 4개 루프.... 등) 모든 루프의 수를 곱해야 하는거 아닌가? 분모는 여전히 100!이고
‘닫힌 단방향 연결리스트가 1개 이상 섞여있는 모음’이 정렬되지 않은 상태에서 자료를 찾는다는 문제로 치환했을때, 노드가 10개 있고 찾아야하는 숫자도 10개가 있을때, 그냥 앞에서부터 찾으면 평균 50회의 엑세스로 10개 숫자를 모두 찾아낼수 있습니다. 위 해법을 적용할시, 30% 확률(최장 리스트의 길리가 전체 길이의 반이하일 확률)로 50회 이내로 모두 찾을 수 있고, 70% 확률로 50회 이상이 필요해집니다. 그러므로 전체 모음에 섞여있는 리스트 중 최장 리스트의 길이가 전체 모음 길이의 반 이하라는게 보장이 되면 위 해법대로 자료를 찾으면, 앞에서부터 순서대로 찾는것보다 무조건 빠르게 찾을 수 있죠. 그러므로 이 자료 모음의 메타데이터에 최장 리스트 길이를 넣어놓고, 최장 리스트의 길이가 전체 반 이상이면 앞에서부터 순서대로 자료를 찾고, 아니라면 루프해법으로 자료를 찾는다면 자료찾기를 더 효율화할 수 있는데, 이와 같이 특수한 방식으로 정보가 저장되는 경우를 잘 모르겠네요 아직…
내용은 얼추 이해가는데 그래도 반례가 잇지않을까해서 직접 해봤는데 예를들어 내가1번이고 1번 상자안에3이 3번 상자안에 5가, 이런식으로 쭉 이어갓을때, 이걸 간단히 1-3-5-...이라고 표현하면 저 간단히 표시한 식이 무조건 루프를 형성한다는 가정하에 저 루프안에서 언젠가 어떤 숫자(x)는 무조건 x-1이 되어야만 루프가 완성되기때문에 본인 숫자가 잇을수밖에 없네요. 예를들어 ...-97-99-1-3-5-...처럼. 진짜 미쳣다...
100명 죽을 확률 = 1/100, 100명 죽을 기댓값 = 100×(1/100) = 1명 99명 죽을 확률 = 1/99, 99명 죽을 기댓값 = 1명 ... 51명 죽을 확률 = 1/51, 기댓값 = 1명 50명 죽을 확률 = 0, 기댓값 = 0명 ... 1명 죽을 확률 = 0, 기댓값 = 0명 0명 죽을 확률 = 0.31, 0명 죽을 기댓값 = 0×0.31 = 0명 기댓값을 다 더하면 딱 50명 나옵니다.
13:13 뭔가 죄수들이 단순히 상자번호에 특정 수를 더하는 "간단한" 방법으로 루프 전략을 쓰는 걸로는 그 전략을 미리 예상한 간수 입장에서 할 수 있는 게 있을 거 같긴 한데 잘 모르겠네요...... 더하기에 의해 전체 구조가 보존되기에 사실상 안 섞이면서 가장 긴 루프의 길이가 50 이상이 되도록 할 수 있을 거 같은데......
@@reryyywwerwghju9549 간단하게 설명하면, 이 게임보다 더 쉬운 버전의 새로운 게임을 가져온 다음에 새로운 게임의 전략이 원래 게임의 루프 전략과 같다는걸 보여서 증명합니다. 자세하세 설명하면, 새로운 게임을 다음과 같은 규칙으로 하는건데요. 1) 100명의 죄수들이 각자 자기 번호가 나올때까지 상자를 열되 50번 초과하면 실패 2) 이전 죄수들이 연 상자는 다시 닫지 않고 다음 죄수가 모두 볼 수 있다. 이때 열린 상자 중에서 자기 상자가 있다면 바로 다음 죄수 차례로 넘어간다. 3) 100명 모두 통과하면 성공 새로운 게임은 원래 게임보다 정보가 더 많기 때문에 성공 확률의 upper bound라 할 수 있고 이 새로운 게임에서 어떠한 전략들을 쓰더라도 승패는 50개 초과의 루프가 있는지에 따라 갈리게 되므로 upper bound와 같은 루프 전략이 항상 최적의 선택이 됩니다
나는 이렇게 생각했음 각 사람이 상자의 번호를 확인하는데 중요한 점은 자신의 번호가 아닌 그다음 사람의 번호까지 같이 확인하며 진행하는 거임 즉 상자 확인에 대한 횟수를 누적하며 진행하는 것 1번 사람은 1~50번까지의 번호를 확인하고 2번의 번호가 있는지 확인해 봄 만약 2번 번호가 1~50까지 상자 중에 있다면 바로 나가고 그게 아니라면 10분 정도 기다렸다가 나가는 거지 이후 2번 사람은 들어가는 시간에 따라 1~50까지 상자를 확인할지 51~100상자를 확인할지 결정하고 자신의 번호를 찾으며 3번 번호를 확인 이런 식으로 계속 가다 보면 모두가 찾을 수 있겠지... 1번만 맞으면
8:55 에서 100개짜리 루프 가 나올 확률 이 100분의 1, 99는 99분의1 이게 이렇게 계산되는게 맞나요? 영상에서는 분모가 100 팩토리얼 , 즉 100개짜리 루프가 생성되는 총 가짓수인데, 이거보다 차라리 100개짜리 루프가 생성되는 총 가짓수+99개짜리 루프가 생성되는 총 가짓수+....+1개짜리 루프 가 생성되는 총 가짓수 이어야 모든 가짓수를 더한 거 아닌가요? 여기서 분자에 100팩토리얼(나누기 100) 해야 모든 가짓수 중에 100개짜리 루프가 나올수 있는 확률이 계산되는거 아닌가요? 여기서 갑자기 확률이 100분의 1 이런식으로 확 증가하니까, 나중에 30프로 확률이 되버리는거 같은 느낌인데 결과적으로 1번이 1번 상자를 열었다는 사실을 2번이 알수있는 방식이 아닌 이상(그래서 겹치는 박스는 열지않는) 유의미한 확률 증가는 안일어날거같은데요..
100!은 길이 100짜리 루프가 생성되는 경우의 수가 아닙니다. 그냥 모든 상자에 숫자를 배열하는 경우의 수일 뿐이죠. 100개짜리 루프를 생성하는 경우의 수는 분자의 100!/100입니다. 참고로 말하신건처럼 길이 100짜리 루프가 생성되는 경우의 수+99짜리 루프가 생성되는 경우의 수.... 와 같은 형태의 계산을 계속해서 1개짜리 루프가 생성되는 경우의 수까지 계산을 하면 100!보다 훨씬 큰 수가 나옵니다. 왜냐하면 길이가 50보다 작은 루프들이 생기는 경우의 수는 계속 중복해서 더해지기 때문이죠.
이해하기 힘든 수수께끼는 아닌데.. 쉽게 이해하려면 숫자를 줄여 생각해 보면 돼요. 예를 들어 100명이 아니라 2명이라면, 전략 없이 고르면 1/4확률이지만, 먼저 들어가는 사람이 자기가 뽑을 상자를 얘기하고 들어가면 (1번이든 2번이든) 나중에 들어가는 사람이 그 상자를 열 일이 없으므로 확률은 1/2이 돼서 살 확률이 두배로 느는거죠.
