혹시나 도움이 될지 몰라 제가 직관적으로 이해한 방식을 설명드리자면 자신의 번호에 맞는 숫자의 상자를 열게 됨으로써 모든 죄수들이 열게되는 첫 상자는 전부 다른 상자가 됩니다. 그리고 모든죄수들이 두번째로 열게 되는 상자도 전부 다른 상자가 되죠 모든 죄수들이 매 스텝마다 여는 상자가 전부 다르다는 조건을 이용해서 이 문제를 변형시킬 수 있습니다. 각 죄수가 한명씩 들어가서 자신의 번호를 찾는다고 생각하지 마시고 백명의 죄수가 한방에 동시에 들어가서 차례대로 상자에 선 뒤 상자를 하나씩 열어본다고 생각하는겁니다 첫번째 상자를 열고나면 그 다음상자를 열고 차례대로 한칸씩 움직이면서 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%라는거죠.. 만약에 돈을 걸고 하는 게임 같은건데 교도관 맡으면 질 수가 없다고 생각했다가 틀린 사람이 한명도 없는 순간 이게 가능할리가 없는데 하면서 멘탈 나가는거죠...ㅋㅋㅋㅋㅋㅋㅋ
확률이 높아지는 이유는 좀더 개념적으로 쉽게 설명하면, 죄수들마다 서로 다른 고유 번호 있고 그 번호로 인해 죄수들이 서로 겹치게 않게 시작 번호 상자를 여는 겁니다. 죄수들 모두가 랜덤하게 아무 상자나 열면서 시작하는 것과는 완전 다르죠. 이게 확률을 높이는 키워드입니다. 상자의 시작 번호가 고유적으로 다 다르게 되어 100명이든 100만명이든 그 죄수 만큼 상자 여는 시작 위치가 서로 달라 그 만큼 다시 상쇄됩니다. 그래서 결과적으로 죄수가 아무리 늘어나도 상자 50루프 해당되는 1/3정도 확률만 비슷하게 계속 남게 되는 겁니다.
내용은 얼추 이해가는데 그래도 반례가 잇지않을까해서 직접 해봤는데 예를들어 내가1번이고 1번 상자안에3이 3번 상자안에 5가, 이런식으로 쭉 이어갓을때, 이걸 간단히 1-3-5-...이라고 표현하면 저 간단히 표시한 식이 무조건 루프를 형성한다는 가정하에 저 루프안에서 언젠가 어떤 숫자(x)는 무조건 x-1이 되어야만 루프가 완성되기때문에 본인 숫자가 잇을수밖에 없네요. 예를들어 ...-97-99-1-3-5-...처럼. 진짜 미쳣다...
아주 간단하고 직관적으로 설명해드릴게요 1. 본인의 숫자가 적힌 상자로 시작한 루프에는 본인의 숫자가 무조건 존재한다 2. 상자는 50개까지 열 수 있기때문에 본인의 루프를 구성한 상자의 갯수가 51개 이상이라면 실패한다 3. 100개의 상자와 숫자를 무작위로 배치했을때 51개 이상의 상자로 구성된 루프가 생성될 확률은 약 70% 이다 4. 그러므로 약 30% 의 확률로 죄수들은 생존할 수 있다 이해가 안되는 부분이 있다면 답글 ㄱㄱ
? 설명이 아주 직관적으로 1도 안됐는뎁쇼? 그냥 영상에 나온 내용 똑같이 정리해놓은 거잖아요 ㅋㅋㅋㅋ 이해가 안되는게, 내가 루프 방법을 따라서 내 숫자를 찾을 확률이 30% (이거 맞나요?) 그리고 내 다음 죄수가 자기 번호를 찾을 확률도 30%, 이 다음도, 또 그 다음도 30%. 그럼 결국 100명이 다 찾을 확률은 0.3^100 아닌가요? 오히려 무작위로 고르는 것보다 확률이 낮아지는게 아닌지..
@@열심히-y7u 루프 방법으로 내 숫자를 찾을 확률은 100%이고 중요한건 그 루프의 길이입니다 열수있는 상자의 갯수가 50개로 제한이 되어있어서 루프의 길이가 50개를 넘어버리면 모두 죽는거구요 무작위로 배열했을때 길이가 50이 넘는 루프가 만들어질 확률이 약 70% 반대로 길이가 50이 넘는 루프가 없을 확률이 약 30%로 이 경우엔 모든 죄수가 본인의 루프에서 숫자를 찾아 살아남을 수 있습니다
@@BBEOGGEUM 아? 그니까 상자에 숫자를 배포할때 생성되는 모든 루프들의 길이가 50이 안넘을 확률이 30%라는 건가요? 그래서 죄수들이 한명씩 들어가서 어떤 상자에서 시작하든 루프만 따르면 모두 살아나갈 확률이 30%라는거고? 살 확률과 죽을 확률은 교도관이 상자에 숫자를 배치할때 이미 정해지는거기 때문에? 제가 이해한게 맞나요?
왜 차이가 나는지 직관적 이해를 돕기 위하여.. 죄수들 끼리 논의를 하지 않았을 경우, 모든 죄수들은 무작위로 상자를 열 것이고, 서로 영향을 주지 않으므고 모든 사건은 독립 사건이 되며 미션 성공 확률은 1/2의 100승이 됩니다. 하지만 죄수들이 미리 두가지 규칙을 정할 경우 더이상 독립 사건이 되지 않습니다. 모든 죄수들이 여는 첫번째 상자는 절대로 중복되지 않으며, 따라서 모든 죄수들은 절대로 같은 루프를 통하지 않습니다. 그러므로 전체를 분석해 보면, 독립사건이 아니기에 정규분포를 따르지 않는 것입니다. 또한 규칙을 아는 교도관이 통제도 가능하고, 그걸 아는 죄수들도 대응이 가능해집니다. 무작위라는 독립사건에서는 이것이 불가능하죠.
굉장히 흥미로운데요 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인 루프를 아까 말한 새로운 숫자배열이라고 생각한다면? 아주 놀라운 결과입니다.
직관적으로 이해 하기 위한 전략의 특징 - 한사람이 틀리면 다른 사람이 맞던 틀리던 다같이 죽는게 포인트 - 내 루프가 50개 이상의 루프면 내 루프 안에 포함된 50명 이상의 사람은 앞으로 다함께 틀리게 됨. '50개 이상의 루프가 있느냐'가 게임의 유일한 승패요인이 되어버림. 어쨌건 같은 고리를 공유한 사람들은 같은 승패결과를 가진 셈이니까. - 그리고 랜덤 배치에서 루프가 50개 이상일 확률은 대략 70% 메모리 위치(seq)를 서로 링크해서 가지고 있고, 검색시에는 이 링크된 메모리를 따라서 검색하다가, 만일 메모리 조회 횟수가 전체 데이터 갯수의 절반 이상인 검색이 발생하면 이 해당 검색이 시작된 메모리의 링크와 다른 (랜덤)메모리의 링크를 바꿔버리면(루프를 바꿔버리면) 검색을 할수록 검색 시간이 단축되겠네....
이해가 좀 안되는 부분이 있어요 ㅠㅠㅠ 영상 마지막에 모두성공하거나 모두실패하며 소수의 인원만 숫자를 찾는 아쉬움이 없다고 했는데요 만약 1-100까지 중에 예를들어 1-10 11-70 71-100 이렇게 세개의 루프가 있다면 1-10과 71-100의 죄수들은 본인의숫자를 찾을 수있는거 아닌가요??
루프전략을 사용했을때와 그냥 무작위로 선택했을때의 차이를 말하는거 같아요 그냥 무작위 50%확률로 하면 99명이 찾았지만 1명이 못찾는다던지 해서 아쉽게 실패하는 경우가 있지만, 루프전략은 30% 확률로 ( 루프길이가 50이하일 확률 ) 모두 성공하거나 70%확률로 ( 루프길이가 50 이상일 확률 ) 와장창 실패하니까요, 한명이라도 틀린다면 실패한다는점이 중요한거같아요
나는 이렇게 생각했음 각 사람이 상자의 번호를 확인하는데 중요한 점은 자신의 번호가 아닌 그다음 사람의 번호까지 같이 확인하며 진행하는 거임 즉 상자 확인에 대한 횟수를 누적하며 진행하는 것 1번 사람은 1~50번까지의 번호를 확인하고 2번의 번호가 있는지 확인해 봄 만약 2번 번호가 1~50까지 상자 중에 있다면 바로 나가고 그게 아니라면 10분 정도 기다렸다가 나가는 거지 이후 2번 사람은 들어가는 시간에 따라 1~50까지 상자를 확인할지 51~100상자를 확인할지 결정하고 자신의 번호를 찾으며 3번 번호를 확인 이런 식으로 계속 가다 보면 모두가 찾을 수 있겠지... 1번만 맞으면
100개짜리 루프가 존재할 확률이 1/100 인건 이해하겠는데 그 이하부터는 계산방법이 달라져야 할 것 같은데. 99개짜리 루프가 있을 확률이 어떻게 1/99 이지? 분모는 여전히 100!이어야 하는거 아닌가? 90개짜리 루프가 존재할 경우의 수는 90개의 루프를 만들 수 있는 경우의 수에 나머지 10개로 만들 수 있는(1개 9개루프, 1개 2개 3개 4개 루프.... 등) 모든 루프의 수를 곱해야 하는거 아닌가? 분모는 여전히 100!이고
@@reryyywwerwghju9549 간단하게 설명하면, 이 게임보다 더 쉬운 버전의 새로운 게임을 가져온 다음에 새로운 게임의 전략이 원래 게임의 루프 전략과 같다는걸 보여서 증명합니다. 자세하세 설명하면, 새로운 게임을 다음과 같은 규칙으로 하는건데요. 1) 100명의 죄수들이 각자 자기 번호가 나올때까지 상자를 열되 50번 초과하면 실패 2) 이전 죄수들이 연 상자는 다시 닫지 않고 다음 죄수가 모두 볼 수 있다. 이때 열린 상자 중에서 자기 상자가 있다면 바로 다음 죄수 차례로 넘어간다. 3) 100명 모두 통과하면 성공 새로운 게임은 원래 게임보다 정보가 더 많기 때문에 성공 확률의 upper bound라 할 수 있고 이 새로운 게임에서 어떠한 전략들을 쓰더라도 승패는 50개 초과의 루프가 있는지에 따라 갈리게 되므로 upper bound와 같은 루프 전략이 항상 최적의 선택이 됩니다
"죄수들을 도우려는 '교도관'이 '잠입'한다면"이라는 상황과 '상자 속 내용물을 바꿔놓는다'라는 해결책을 제시한 것을 종합하면 해당 상황은 상자 속 내용물을 모두 보고 마음대로 조작할 수 있는 상황임을 알 수 있습니다. 루프가 어떻게 형성되어있는지 관측할 수 있으니 루프가 반으로 잘 쪼개지도록 쪽지 한 쌍만 바꿔놓으면 모두가 살 수 있습니다.
‘닫힌 단방향 연결리스트가 1개 이상 섞여있는 모음’이 정렬되지 않은 상태에서 자료를 찾는다는 문제로 치환했을때, 노드가 10개 있고 찾아야하는 숫자도 10개가 있을때, 그냥 앞에서부터 찾으면 평균 50회의 엑세스로 10개 숫자를 모두 찾아낼수 있습니다. 위 해법을 적용할시, 30% 확률(최장 리스트의 길리가 전체 길이의 반이하일 확률)로 50회 이내로 모두 찾을 수 있고, 70% 확률로 50회 이상이 필요해집니다. 그러므로 전체 모음에 섞여있는 리스트 중 최장 리스트의 길이가 전체 모음 길이의 반 이하라는게 보장이 되면 위 해법대로 자료를 찾으면, 앞에서부터 순서대로 찾는것보다 무조건 빠르게 찾을 수 있죠. 그러므로 이 자료 모음의 메타데이터에 최장 리스트 길이를 넣어놓고, 최장 리스트의 길이가 전체 반 이상이면 앞에서부터 순서대로 자료를 찾고, 아니라면 루프해법으로 자료를 찾는다면 자료찾기를 더 효율화할 수 있는데, 이와 같이 특수한 방식으로 정보가 저장되는 경우를 잘 모르겠네요 아직…
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 이상이 되도록 할 수 있을 거 같은데......
이해하기 힘든 수수께끼는 아닌데.. 쉽게 이해하려면 숫자를 줄여 생각해 보면 돼요. 예를 들어 100명이 아니라 2명이라면, 전략 없이 고르면 1/4확률이지만, 먼저 들어가는 사람이 자기가 뽑을 상자를 얘기하고 들어가면 (1번이든 2번이든) 나중에 들어가는 사람이 그 상자를 열 일이 없으므로 확률은 1/2이 돼서 살 확률이 두배로 느는거죠.
![Eminem - Fuel (feat. JID) [Official Lyric Video]](http://i.ytimg.com/vi/t5H_CewqpKA/mqdefault.jpg)
![[알쓸범잡 부록] 확률을 계산해 카지노를 이긴 수학자부터 항준vs.은희 맞고 대결까지! #알쓸범잡 EP.8](/img/1.gif)
도저히 직관적으로 이해가 안돼서 직접 프로그래밍해서 1000만번 테스트 해봤는데,
성공: 3,119,325 실패: 6,880,675. 성공 확률이 약 31.2%가 나오네요. 정말 신기합니다.
와우 댓글 보고 저도 코드 짜서 1000만번 테스트 해봤는데
성공:3,117,973 실패:6,882,027 나오군요 파이썬으로 짜니 연산만 1시간 걸리네요 ㄷㄷ..
혹시나 도움이 될지 몰라 제가 직관적으로 이해한 방식을 설명드리자면
자신의 번호에 맞는 숫자의 상자를 열게 됨으로써 모든 죄수들이 열게되는 첫 상자는 전부 다른 상자가 됩니다. 그리고 모든죄수들이 두번째로 열게 되는 상자도 전부 다른 상자가 되죠
모든 죄수들이 매 스텝마다 여는 상자가 전부 다르다는 조건을 이용해서 이 문제를 변형시킬 수 있습니다.
각 죄수가 한명씩 들어가서 자신의 번호를 찾는다고 생각하지 마시고 백명의 죄수가 한방에 동시에 들어가서 차례대로 상자에 선 뒤 상자를 하나씩 열어본다고 생각하는겁니다
첫번째 상자를 열고나면 그 다음상자를 열고 차례대로 한칸씩 움직이면서 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퍼씩 낮아진다고 계산해서 생긴 오차인듯 합니다.
제 설명을 통해 직관적 이해에 도움이 되셨으면 좋겠습니다.
@@오한재-o9h 궁금한 게 있는데 왜 위에 분 댓글이랑 다른 결과값이 나올까요?
4:47 이 계산이 효율적인 결정적인 이유
하지만 100여명의 죄수들은 이해를 하지 못했고, 결국 모두 처형당했다고 합니다....
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
이해해도 죽을 확률이 69%....
현실은 이게맞다
거기 석호필이 있었다..
흑흑 너무 슬프다
이분 더빙?이 정말 좋은게 약간 재밌는 수학 이야기 할때 목소리에 행복해하고 흥미를 정말 드러내 주시는 것 같아서 좋아요
맞아요 목소리도 좋고
@@PSYsAudianceㅆㅇㅈ
솔직히 좋은 더빙은 아니죠.. 너무 웅얼웅얼 거리는 게 개선이 쭉 안 되서 아쉬워요 쿠르츠게작트는 진짜 전문 성우 같이 좋던데
@@버존-v6q전 좋은 더빙이라고 생각해요ㅎㅎ
불규칙의 조건에 규칙으로 대응하는 전략이네요!! 오 정말 멋진 아이디어 입니다. 그 뒤의 확률계산보다 죄수들에게 똑같은 규칙을 만들어주는 부분이 더 놀라웠습니다.
교도소장이 정성껏 번호가 적힌 상자에 하나씩 넣어줘서 그런거임. 그냥 주머니 안에 넣고 하나씩 뽑게 시켰으면 이런일 없었음
거의 불가능에 가까운 확률을 30% 라는 어느정도 가능한 확률로 만들어버리네요 대단합니다! 위에 코딩하시는분들도 멋지구요!
이야 재밌네요 ㅋㅋㅋ
각각 개인의 확률은 50퍼지만 전체가 성공할 확률은 31퍼로 극단적이게 되는 확률분포라니 ㅋㅋㅋ 대신 실패할때는 다들 못 찾아버리는 것도 재밌네요.
같이 성공하거나 같이 폭망하거나
10:30 이 그래프 설명 너무 좋았습니다 👍
좀 무식해서 그런데 개인의확률이 50퍼이면 전체 확률도 50%아닌가요 저략을 저렇게 설명하지 말고 그냥 1~50번에서만 찾으라하면 적어도 50명은 사는거 아닌가? 고로 50%
@@lijingnan5409 100명이 다 찾아야 살아요
@@lijingnan5409 자기 번호 찾은 사람만 살아나가는 규칙이 아니에요
@@이세희-t7w 네 저도 처음에 그렇게 이해했지만 30%가 된들 80%가 된들 죄수에는 속하고 싶지 않네요 좀 태클을 거는거같은데 퍼센트가 늘어나도 도전은 해보고 싶지않습니다 ㅜㅜ
@@lijingnan5409 ㄹㅇ 멍청한게 킬포네 ㅋㅋㅋㅋㅋ
12:06 와 미친 이 부분에서 소름이 쫙.. 천재다
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ진짜 올해 본 영상중에 제일 감탄사 나오는 영상이다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
자신의 번호를 고른 죄수의 숫자가 이항분포를 따르지 않는것이 인상적이네요. 어치피 100 밑의 결과는 패배니까 성공한 죄수의 수를 0부터 100까지 분포시키는게 아니라 100 아니면 그 밑의 값들로 극단화 시키는게 멋지네요. 다른 "완벽한 성공" 문제에도 충분히 적용시킬 수 있어보여서 더욱 좋은 것 같습니다
1명만 틀려도 모두가 죽는 상황을 결국 아무도 안 틀릴 수 있는 전략으로 파훼하는거네요.
그 반대급부로 모두가 틀려버릴수도 있지만, 1명만 틀려도 죽는 상황에서 그건 중요한게 아니니까요.
모두가 틀릴 확률이 아마 저 전략 안쓰고 모두가 살아남을 확률이랑 비슷할듯. 제일 큰 루프가 100이라는건 100개 다열었을때 자기 번호가 맨 마지막에 있다는 거니까
@@user-hv5qu7kz1m ㄴㄴ 틀림
모두가 틀릴 확률은 약69%임
@@HyeonsuByeon-h6k ㄴㄴ 틀림 1%임
예전에 교란순열 관련 문제를 풀면서 일대일대응을 집합을 루프들로 분할하는 아이디어를 썼는데... 이런 문제에서도 쓰이는게 신기하네요
오 저도 ㅋㅋ
이거 본 채널에서 봤을때 정말 재미있었는데 이렇게 만들어주시다니 감사합니다 ㅎㅎ
자신의 번호를 고른 죄수의 숫자가 이항분포를 따르지 않는것이 인상적이네요. 어치피 100 밑의 결과는 패배니까 성공한 죄수의 수를 0부터 100까지 분포시키는게 아니라 100 아니면 그 밑의 값들로 극단화 시키는게 멋지네요. 다른 "완벽한 성공" 문제에도 충분히 적용시킬 수 있어보여서 더욱 좋은 것 같습니다
.
맞춘 사람은 살려준다고 했을 때도 루프 전략을 쓰기로 합의 본다면 재밌는 점이
교도관은 1명 이상이 죽을 확률은 사실상 100%라고 생각했을텐데 사실은 70%라는거죠..
만약에 돈을 걸고 하는 게임 같은건데 교도관 맡으면 질 수가 없다고 생각했다가
틀린 사람이 한명도 없는 순간 이게 가능할리가 없는데 하면서 멘탈 나가
100명의 죄수에게 상자를 60번 열라고 하면 전부 생존할 확률이 50%를 넘어가네요 ㄷㄷㄷ
상자 열기 시행의 독립성을 제거하다니 대단하네요 ㅋㅋㅋㅋㅋㅋ 이건 마치 박스의 위치를 가지고 다른 사람과 서로 소통하고 있는 것과 다름 없군요
번호가 새겨진 상자에 하나씩 넣어준 교도소장의 정성엔 다 이유가 있었던거라고....
진짜 이런영상들 너무 재밌습니다
못 믿겠어서 코딩으로 실험해봤는데 진짜 0.3보다 조금 높게 나오네... 수학자들은 대단하구나
대단
파이썬입니다
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)
@Salida 저런 간단한건 한시간 이내 충분히 만들 수 있어요 특히 간단한 학습용 코딩 프로그램인 블럭코딩 프로그램이라면 훨씬 빨리 만들 수 있죠.
@Salida 난 비전공자이고 파이썬밖에 모르는데, 전공자가 하면 10분컷도 가능할것 같은데?
@Salida 실험이라고 해봤자 코드 짜고 돌리는건데 몇십줄 짜리코드를 짜는데 몇분 코드 돌리는데 몇초에요..
빨리 드음 영상 가져와!!!! 재밌게 수학 배우고 싶단 말이야!!!!!!
논리적으로는 그럴수도 있겠다 싶긴 하지만 너무나 직관에 반하는 결과죠. 예전에 직접 시뮬레이션 해보고 받아들이긴 했는데, 여전히 신기합니다.
뭔가 아닌것같은데 2명인걸로 생각해봐도 되는게 신기함
@@황원태-q9e 두명일 때는... 다른거 아닌가요?
@@황원태-q9e 2명일땐 사용불가.. 그냥 50퍼.......
@@황원태-q9e 원태야...
2명일때도 적용됩니다
루프전략 안썼을땐 1/2 × 1/2로 25%확률로 생존하지만
루프전략 사용한 경우 1번박스에 1번종이, 2번박스에 2번종이 들어있다면 (루프길이 1인경우) 성공, 1번박스에 2번종이, 2번박스에 1번종이(루프길이 2) 인경우 실패이기 때문에 50% 확률로 생존합니다.
운빨X망으로 보이는 게임이라도 수학적인 이해를 바탕으로 적절한 전략을 사용하면 이렇게까지 가능성을 높일 수 있다는게 대단하네요
운빨x망 ㅋㅋㅋㅋ 근데 진짜 신기하네요
그래도 31%의 기적이 일어나야 해요!
그래도 제 솔랭은 운빨x망입니다. 그렇게믿어야 제 맘이 편해요
@@물방개구리 31%면 개 혜자네 ㅋㅋ
@@물방개구리 어차피 죽을 거 31%로 확률을 늘려준 것에 감사해야...
10:55 핵심적 질문에대한 답은 이미
4:40 ~5:14 에 잘 설명돼있네요
너무 신기하네..
본채널에서 본 영상인데 흥미롭고 재밌는 영상입니다ㅎㅎ 유튜브가 있어서 책으로 보면 어려운 문제도 재밌게 접근할수있어서 좋네요
맞춘 사람은 살려준다고 했을 때도 루프 전략을 쓰기로 합의 본다면 재밌는 점이
교도관은 1명 이상이 죽을 확률은 사실상 100%라고 생각했을텐데 사실은 70%라는거죠..
만약에 돈을 걸고 하는 게임 같은건데 교도관 맡으면 질 수가 없다고 생각했다가
틀린 사람이 한명도 없는 순간 이게 가능할리가 없는데 하면서 멘탈 나가는거죠...ㅋㅋㅋㅋㅋㅋㅋ
하지만 70프로로 51명 이상 죽는
라이어게임이나 카이지에 나올법한 게임이네
재밌는건 루프전략을 써도 개개인의 생존률은 딱 50%라는거. 고의적으로 51이상 루프되도록 상자를 배치하지 않는 한 아무튼 쓰는게 유리한 전략이긴 하네요.
아그러면 맞춘사람은 살려준다고 했을때도 쓰는게 이득인거네요 개개인 입장에서 봐도
@@tlqkf 개개인의 확률 50프로인건 똑같고 손해보는건 없는데 다 살아나갈 확률이 30프로인 뭔가 이상하면서도 따져보니 맞는 신기한 문제..ㅋㅋ
감사합니다! 감방에 들어가서 상자 고르기 전에 99명의 재소자들에게 보여주기 좋은 영상이네요..!
제가 죄수였다면 이미 좌절하고 저런생각을 할 시도조차 하지 못했을거 같은데 신기하네요 ㅋㅋㅋㅋ 확률의 신비함을 다시 한번 느낍니다. 처음 설명을 들었을때는 이해가 잘 안됬지만 두세번 돌려보니 이해가 가네요.. 좋은 영상 감사합니다
희한하다면 희한한 게... 막상 개개인이 성공할 확률은 여전히 50%라는 점인 듯.
개개인의 확률은 같지만 전략 변화로 전체의 성공률이 달라진다는 게,
뭔가 수학의 미학 같은 느낌도 들고.
개개인이 성공할 확률이 50이 맞아요?
@@---qm5yb 영상을 좀 보세요..
@@---qm5yb 개개인으로 보면 50프로가 맞죠. 전체가 성공할 확률이 30프로라 죄수 한명이 성공할 확률이 50프로라 생각할 수 있지만 죄수 모두가 성공 49명성공, 48명성공 ... 등등에서 개인이 성공할 확률까지 모두 더하게 된다면 결국 50프로가 됩니다
@@---qm5yb 계산기 돌려보니 50정도 나옴. 최대길이가 50이하라 무조건 성공(31퍼) + n->1~50 (50 - n) / {(50 + n) * 100} 하면 약 18.x퍼 부동소수점연산 오차 생각하면 50퍼 나올듯
Veritasium 채널은 늘 생각하게 만드네요. 재밌어요.
와 ln2나오는거 개소름돋음..
자신이 찾은 쪽지를 가지고 나가버리면 이 문제가 성립이 안되는군요.
영상의 접근방법이 제가 떠올린 의문의 순서와 동일한게 정말 멋졌어요
자신의 번호의 상자부터 시작하면 무조건 그 루프안에 해당번호를 찾을 수 있다는걸 이해했을때 소름이 쫙 ㅋㅋㅋ
상자 안에 무슨 쪽지가 있는지 사전에 알 수가 없으니까 전략을 아무리 짜도 의미가 없다고 생각했는데 그게 전혀 아니었네 ㅋㅋㅋ 머리가 띵하네요
확률이 높아지는 이유는 좀더 개념적으로 쉽게 설명하면,
죄수들마다 서로 다른 고유 번호 있고 그 번호로 인해 죄수들이 서로 겹치게 않게 시작 번호 상자를 여는 겁니다. 죄수들 모두가 랜덤하게 아무 상자나 열면서 시작하는 것과는 완전 다르죠.
이게 확률을 높이는 키워드입니다. 상자의 시작 번호가 고유적으로 다 다르게 되어 100명이든 100만명이든 그 죄수 만큼 상자 여는 시작 위치가 서로 달라 그 만큼 다시 상쇄됩니다.
그래서 결과적으로 죄수가 아무리 늘어나도 상자 50루프 해당되는 1/3정도 확률만 비슷하게 계속 남게 되는 겁니다.
핵심 이해를 잘못하신듯 합니다. 중요한 것은 서로 다른 상자를 열었기 때문이 아니라, 박스를 연 다음 다음 상자를 선택하는 방법에 있는 겁니다. 영상에 나오는 "링크"가 이 해법의 핵심이죠.
팩트)둘다 중요함
뭔가 사람이 늘어날수록 중간에 하라는대로 안해서 멸망할것같다ㅋㅋㅋ
그래도 그사람이 50퍼 확률만 뚫어낸다면 사는거 아닌가...?
@@unarmed_civilian 50% 병
@@user-wi6vkq21k9a ㅋㅋㅋㅋㅋㅋㅋㅋ 병 한글자에 감정이 담겨있네
@@user-wi6vkq21k9a맞는말 했는데..?
그 사람이 빡대가리여서 루프 방식을 하지 않더라도 50퍼만 뚫어내면 되기 때문에 루프확률 × 1/2 하면 15퍼정도로 성공은 가능할듯?
미쳤다 유튜브 영상 보면서 감탄하는건 처음...
게임 하기전에 전략을 정함으로써 독립시행을 종속사행으로 바꾼거군요 루프 말고 더 효율적인 방법도 존재할까요?
와 이 채널 열심히 자막 해석하면서 낑낑대다가 한 15분 보고 포기하고 그랬었는데 한국어 채널이 생겼군요 흥해라~~~
애니메이션 덕분에 이해하기 백배 쉬워진 것 같습니다. 쉽고 재밌는 영상 감사합니다
이 영상을 보고 감옥에 들어가지 않기 위해 착하게 살아야겠다는 생각이 들었습니다
그냥 쉽게 100명을 2명으로 줄이기만 해도 이해하기 편할듯. 2명이 상자 두개 중 자신의 번호를 찾는 독립시행을 한다면 둘다 맞출 확률은 25%지만, 자신의 번호가 적힌 상자만 연다는 가정을하면 50%가 되죠.
왜요?
30%인데요
@@sangwoo2256두명이서 1번,2번 상자를 각각 열면 정답이거나 아니거나 50프로니깐요… 둘중에 하나만 맞는다는 선택지를 없애는거죠
@@곽은태-h5v 아 둘이서 박스두개
@@곽은태-h5v 결국핵심은 낭비되는 확률들을 없애고 1or0로 형태를 구축하는거군요
내용은 얼추 이해가는데 그래도 반례가 잇지않을까해서 직접 해봤는데 예를들어 내가1번이고
1번 상자안에3이 3번 상자안에 5가, 이런식으로 쭉 이어갓을때, 이걸 간단히 1-3-5-...이라고 표현하면
저 간단히 표시한 식이 무조건 루프를 형성한다는 가정하에 저 루프안에서 언젠가 어떤 숫자(x)는 무조건 x-1이 되어야만 루프가 완성되기때문에 본인 숫자가 잇을수밖에 없네요.
예를들어 ...-97-99-1-3-5-...처럼.
진짜 미쳣다...
이런 수학은 마지막에 갑자기 익숙한 함수가 나오는게 소름그자체인듯 처음엔 그저 랜덤에서 규칙찾기 인데 갑자기 1/x 함수라니
맞죠 마지막 그 그래프 나오자마자 소름..
너무 재밌어요!! 이런 수학퍼즐 나오는 책 좀 추천해주세요!?
진짜 아이디어 좋고 신기하네요
진짜 너무 흥미롭고 재밌어요
아주 간단하고 직관적으로 설명해드릴게요
1. 본인의 숫자가 적힌 상자로 시작한 루프에는 본인의 숫자가 무조건 존재한다
2. 상자는 50개까지 열 수 있기때문에 본인의 루프를 구성한 상자의 갯수가 51개 이상이라면 실패한다
3. 100개의 상자와 숫자를 무작위로 배치했을때 51개 이상의 상자로 구성된 루프가 생성될 확률은 약 70% 이다
4. 그러므로 약 30% 의 확률로 죄수들은 생존할 수 있다
이해가 안되는 부분이 있다면 답글 ㄱㄱ
? 설명이 아주 직관적으로 1도 안됐는뎁쇼? 그냥 영상에 나온 내용 똑같이 정리해놓은 거잖아요 ㅋㅋㅋㅋ
이해가 안되는게, 내가 루프 방법을 따라서 내 숫자를 찾을 확률이 30% (이거 맞나요?) 그리고 내 다음 죄수가 자기 번호를 찾을 확률도 30%, 이 다음도, 또 그 다음도 30%.
그럼 결국 100명이 다 찾을 확률은 0.3^100 아닌가요? 오히려 무작위로 고르는 것보다 확률이 낮아지는게 아닌지..
@@열심히-y7u 루프 방법으로 내 숫자를 찾을 확률은 100%이고 중요한건 그 루프의 길이입니다
열수있는 상자의 갯수가 50개로 제한이 되어있어서 루프의 길이가 50개를 넘어버리면 모두 죽는거구요
무작위로 배열했을때 길이가 50이 넘는 루프가 만들어질 확률이 약 70%
반대로 길이가 50이 넘는 루프가 없을 확률이 약 30%로 이 경우엔 모든 죄수가 본인의 루프에서 숫자를 찾아 살아남을 수 있습니다
@@BBEOGGEUM 아? 그니까 상자에 숫자를 배포할때 생성되는 모든 루프들의 길이가 50이 안넘을 확률이 30%라는 건가요? 그래서 죄수들이 한명씩 들어가서 어떤 상자에서 시작하든 루프만 따르면 모두 살아나갈 확률이 30%라는거고? 살 확률과 죽을 확률은 교도관이 상자에 숫자를 배치할때 이미 정해지는거기 때문에? 제가 이해한게 맞나요?
@@열심히-y7u 거의 다 이해하신것같아요
중요한건 본인의 숫자가 적힌 상자로부터 루프를 시작해야 한다는것이구요
그래야 마지막에 본인의 숫자를 찾으며 루프를 닫게되니까요
@@BBEOGGEUM 엥 왜 굳이 내 숫자부터 시작해야해요? 왜 그래야만 루프가 닫히는거죠? 다른 숫자로 가도 상관 없지 않나요?
항상 재밌게 보고있어요 ㅎㅎ
길이가 51이상인 루프가 있는 경우에도 방법만 바꾸면 손쉽게 재배열이 되어버리네요. 정말 신기합니다.
잘 모르겟어요 7:34 부터 조금 막히네용 졸려서 그런가ㅜㅜ 근데 영상 너무 재밌어용 정주행 하러 갑니당ㅎㅎㅎ
상자마다 무작위로 1부터 100까지 숫자를 적어넣었으면 절대 불가능했을텐데, 1부터 100까지의 숫자가 적힌 종이를 1부터 100까지 숫자가 적힌 상자에 넣으면 결국 종이와 상자가 1대1로 매칭된다는 점을 노련하게 이용한 해결법이네여. 굉장히 똑똑합니다 ㅎㅎ
근데 상자에 숫자가 안 적혀있어도 죄수들이 왼쪽 위에 있는 것부터 1이고 쭉 번호를 매겨서 오른쪽 아래가 100이라고 하자고 약속하고 루프 전략을 쓰면 같은 거 아닌가요?
@@dayservant네 맞아요 상자의 위치만으로 번호를 정해도 문제없습니다
ㅋㅋㅋ원댓글 제대로 이해못한거같은데
영상제대로 안봤지.... ㅋㅋ
ㅋㅋ정확하게 이해 못했네
영상이 정말 흥미롭고 재밌었어요
좋은 영상 만들어주셔서 감사합니다
요런거 게임처럼 만들면 수많은 사람이 참여할거고 더 정확히 분석이 될거같네요.
진짜 내 번호가 루프에 포함됐다는 걸 경험해보고 싶어요.
ㄹㅇㅋㅋㅋ 방금 그림판으로 그려봤는데도 루프에 내번호가 있는게 와닿지않음
@@탈론장인 모든 박스는 루프를 무조건 만듬
중간에 끊기는건 있을수없음
그렇기때문에 내 번호의 박스를 연다는 것 = 내 번호가 들어간 루프를 시작한다는것
남자들끼리 기차놀이를 한다고 생각해보세요. 첫번째 남자는 두번째 남자 X구멍에 넣어야겠죠? 두번째 남자는 또 다시 세번째 남자 X구멍에 넣구요. 그럼 마지막 남자는 어디에 넣어야 할까요? 첫번째 남자 X구멍만 남았겠죠? 이게 바로 1대1 대응함수의 매력이랍니다.
@@lllilllililill 아니 ㅋㅋㅋㅋㅋㅋㅋ
@@lllilllililill이게 시발 ㅋㅋㅋㅋㅋ 루프의 직관적인 설명이라는 게 빡치네
일단 내가 내 번호의 상자를 고르면 확실하게 내 번호가 포함된 루프에 들어갈 수 있다는게 핵심인거같네요
이제 그 루프가 어지간히 운이 나빠서 50개를 넘어서지만 않으면 성공이 보장된거구요 진짜 기가 막히는 아이디어네요
ㅋㅋㅋ현실은 100명중에는 분명 똥멍청이가 있을거기 때문에... 쪽지 찾았다고 신나서 가지고 나오는 놈이 있을거고
루프는 이어지지 않을거임...
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 가지고 나오는 순간 간수 표정 씨익~ ^^
루프를 타다보니 아무것도 들어있지 않은 상자가 나왔다..
10:34
앞서 설명한 모든 걸 냅다 원점으로 돌려버리는 질문ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
이해가 안되서 하는 질문은 상대방도 한번 더 생각해보게하고 유익하다 생각하는데.. 끝까지 개소리로 틀렸다고 GR하는 인간들은 진짜..... 감사하다. 상대적으로 내가 똑똑해질 수 있는 이유니까.
되서->돼서
왜 차이가 나는지 직관적 이해를 돕기 위하여..
죄수들 끼리 논의를 하지 않았을 경우,
모든 죄수들은 무작위로 상자를 열 것이고, 서로 영향을 주지 않으므고 모든 사건은 독립 사건이 되며 미션 성공 확률은 1/2의 100승이 됩니다.
하지만 죄수들이 미리 두가지 규칙을 정할 경우 더이상 독립 사건이 되지 않습니다.
모든 죄수들이 여는 첫번째 상자는 절대로 중복되지 않으며, 따라서 모든 죄수들은 절대로 같은 루프를 통하지 않습니다.
그러므로 전체를 분석해 보면,
독립사건이 아니기에
정규분포를 따르지 않는 것입니다.
또한 규칙을 아는 교도관이
통제도 가능하고,
그걸 아는 죄수들도 대응이 가능해집니다.
무작위라는 독립사건에서는 이것이 불가능하죠.
굉장히 흥미로운데요 12:56 이 문제의 해법에서 숫자를 5를 더한다고 하더라도 결국 루프의 길이는 변하지 않기에 30퍼센트가 아닌것 아닌가요? 루프의 길이가 100이라면 결국 0퍼센트에서 50퍼센트로 올라가지만 각자다른 여러개의 루프가 있다면 본인이 속하지 않은 루프로 빠질 수 있지 않을까요? 최초에 해법이 본인의 루프에서 벗어나지 못하므로 루프가 50이하인 경우에 모두 50회 이하의 도전에서 본인의 번호를 찾을 수 있다는 전제와 다른 것 아닌가요?
3상자에 6이 적혀져있다고 가정했을때 5를 더한 상자를 열게 바꾸면 8상자에서 값을 찾게 되는데 6이 아닌 숫자가 들어있겠죠. 그 번호에서 5를 또 더한 상자를 찾는거고. 즉 섞는 효과랑 똑같아요
퍼즐 자체도 상당히 비 직관적이기 때문에 실제로 어떻게 될지 따져보는 쪽이 빠릅니다.
예를들어 가장 간단한 루프인 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인 루프를 아까 말한 새로운 숫자배열이라고 생각한다면?
아주 놀라운 결과입니다.
상자에 +5한다면 그렇게 헷갈릴수도있는데
모든 쪽지를 현재 있는 위치에서 -5 숫자의 상자에 넣는다고 생각하면 쉬울듯 결국 상자에 임의로 +5한다는거랑 똑같은 효과를 내니 자기 속하지 않은 루프로 갈확률도 없고 그냥 재배열하는 효과임
감각적으로 이게 이해가 안되시는 분들을 위해서 느낌을 설명드리자면, 한두명이 실패할 확률을 다같이(또는 여럿이) 실패할 확률에 짬처리했다고 생각하면 편합니다
틀린 사람들이 엄청 많이 나올 확률이 올라가는 대신 전부 맞출 확률을 대폭 올리는 전략인 것이죠
내 죄수번호와 "같은" 번호를 가진 박스를 까는 것이 시작이 중요함.
직관적으로 이해 하기 위한 전략의 특징
- 한사람이 틀리면 다른 사람이 맞던 틀리던 다같이 죽는게 포인트
- 내 루프가 50개 이상의 루프면 내 루프 안에 포함된 50명 이상의 사람은 앞으로 다함께 틀리게 됨. '50개 이상의 루프가 있느냐'가 게임의 유일한 승패요인이 되어버림. 어쨌건 같은 고리를 공유한 사람들은 같은 승패결과를 가진 셈이니까.
- 그리고 랜덤 배치에서 루프가 50개 이상일 확률은 대략 70%
메모리 위치(seq)를 서로 링크해서 가지고 있고, 검색시에는 이 링크된 메모리를 따라서 검색하다가, 만일 메모리 조회 횟수가 전체 데이터 갯수의 절반 이상인 검색이 발생하면 이 해당 검색이 시작된 메모리의 링크와 다른 (랜덤)메모리의 링크를 바꿔버리면(루프를 바꿔버리면) 검색을 할수록 검색 시간이 단축되겠네....
처음엔 직관적으로 이해가 안 되었는데 개인이 생존할 확률은 그대로고 전원 생존의 확률이 올라간다니까 이해가 되네요. 재밌게 봤습니다
개인 성공 확률은 그대로 1/2 아닌가요?
개인은 결국엔 상자의 절반을 까게 되는데 왜 31퍼센트일까요? 제가 이해를 잘못했나 다시 봐야겠네요
네 단순하게 결국 모든 개인이 상자의 절반을 깐다는 걸 생각하면 개인의 성공 확률은 1/2이 맞는 것 같아요~
둘다 뭐함?
내 번호의 루프가 50보다 클확률이 69/100 니깐 당연히 개개인의 실패확률도 69/100 일수밖에 없는거 아닌가요
정말 완벽한 영상입니다! 경이로워요
수능 확률 문제에서 항상 주머니 안에 넣고 하나씩 뽑게 시키는 이유가 있었음.... 야바위처럼 개별 상자에 넣든지, 컵에 넣든지 하면 순서, 모양, 위치 때문에 연번을 매길 수 있게 되고 루프 전략을 적용시킬 수 있게 됨
수능에서는 특별한 언급이 없으면 말 그대로 "무작위"로 뽑도록 하니까 애초에 "전략"이 개입하지 않았다고 보는게 맞습니다. 루프전략을 세운 순간 "무작위"가 아니게 되죠.
루프전략이 개사기인 이유
무작위로 뽑는다고 할때 보통 균등분포임을 생략합니다. 수능에서는 특별한 언급이 없는 한 균등분포라고 생각하는게 맞을 것 같습니다.
독립시행으로 했을때 가우시안 분포를 따르는것이
독립성을 없애고 서로 연결 correlated 시키게 되면 분포가 변화하는 것과 같군요
마치 입자의 움직임을 한방향으로 유도하면, 결과가 가우시안이 아니게 되는 것 처럼요
이해가 좀 안되는 부분이 있어요 ㅠㅠㅠ
영상 마지막에 모두성공하거나 모두실패하며 소수의 인원만 숫자를 찾는 아쉬움이 없다고 했는데요
만약 1-100까지 중에 예를들어 1-10 11-70 71-100 이렇게 세개의 루프가 있다면 1-10과 71-100의 죄수들은 본인의숫자를 찾을 수있는거 아닌가요??
모두성공이라는게 50이하의 루프에서 30프로 확률로 자기루프에 있는 사람들 전원이 성공하거나 70확률로 전원이 실패하거나 이 말인가요?
루프전략을 사용했을때와 그냥 무작위로 선택했을때의 차이를 말하는거 같아요
그냥 무작위 50%확률로 하면 99명이 찾았지만 1명이 못찾는다던지 해서 아쉽게 실패하는 경우가 있지만,
루프전략은 30% 확률로 ( 루프길이가 50이하일 확률 ) 모두 성공하거나
70%확률로 ( 루프길이가 50 이상일 확률 ) 와장창 실패하니까요,
한명이라도 틀린다면 실패한다는점이 중요한거같아요
그런의미 같네요
가장 최소치인 루프가 51개만 되도 그때는 숫자 못찾는 사람이 51명이니까
절반이상 박살나냐
운없게 한두명 틀려서 떨어지냐 이런차이?
나는 이렇게 생각했음
각 사람이 상자의 번호를 확인하는데 중요한 점은 자신의 번호가 아닌 그다음 사람의 번호까지 같이 확인하며 진행하는 거임 즉 상자 확인에 대한 횟수를 누적하며 진행하는 것
1번 사람은 1~50번까지의 번호를 확인하고 2번의 번호가 있는지 확인해 봄
만약 2번 번호가 1~50까지 상자 중에 있다면 바로 나가고 그게 아니라면 10분 정도 기다렸다가 나가는 거지
이후 2번 사람은 들어가는 시간에 따라 1~50까지 상자를 확인할지 51~100상자를 확인할지 결정하고 자신의 번호를 찾으며 3번 번호를 확인
이런 식으로 계속 가다 보면 모두가 찾을 수 있겠지... 1번만 맞으면
그 정보가 다음 사람에게 전달될 수 있는 방법이 없음
@@lllilllililill 그러니깐 시간을 이용하자는 거지 다음 사람은 앞 사람이 10분 있다 나오면 앞번호 라인 확인하고 그게 아니면 뒷번호라인 확인하고
영상 잘 보면 문제 조건에도 어긋나지 않고
이거 좋은데요 시간제한 있다는 조건만 없으면 이 전략이 훨 좋은듯 하네요
1~50까지 확인하는시간 개당 5초라고 감안해도 250초 4분이면 충분하고 밖에서 시간을 가늠할수 잇는 수단이 잇고 나온걸 다음사람이 볼수있다면 더 좋은 방법이네요 ㄷㄷ
진짜 본질을 이해못하네ㅋㅋ 그냥 방에 들어간이상 뒷사람에게 그어떤정보도 주지못한다는걸 기본전제로 두고 푸는문제라고요ㅋㅋ 시간이니 뭐니
100개짜리 루프가 존재할 확률이 1/100 인건 이해하겠는데 그 이하부터는 계산방법이 달라져야 할 것 같은데. 99개짜리 루프가 있을 확률이 어떻게 1/99 이지? 분모는 여전히 100!이어야 하는거 아닌가? 90개짜리 루프가 존재할 경우의 수는 90개의 루프를 만들 수 있는 경우의 수에 나머지 10개로 만들 수 있는(1개 9개루프, 1개 2개 3개 4개 루프.... 등) 모든 루프의 수를 곱해야 하는거 아닌가? 분모는 여전히 100!이고
90개 루프일 확률을 그냥 1/90라고 말하지 말고 계산 방법을 설명해줘야지. 계산 해보려다 포기
방금 계산해보니 n개의 루프는 [(n!/n)*nP2)/100! 의 확률이네요. 이걸 생략해서 혼돈을 준 것 같네요. 이렇게 계산하면 맞습니다
n개의 루프를 만드는 경우의 수는 ((100Pn/n)*(100-n)!)/100!
@@hyun-ukshin2397 식을 보니 알겠네요. 감사합니다
@@dhdhas3786 아랫분 식이 정확한거 같네요
콜라츠 추측이 생각나는 풀이네요 흥미롭습니다 🤣🤣 저걸 낸 사람은 컴퓨터 데이터 접근 방식 연구하던 사람이었을라나요
@@TheManaka0504 ㅇㅎ 감사요
@@TheManaka0504 다른 대댓에서 각각의 성공확률이 69.7%다 라고 하신 분이 다른사람 보고는 제대로보라고하네요 그냥 놀랍
더 놀라운건 이 솔루션이 optimal하다는거
어떻게 증명하죠?
@@reryyywwerwghju9549 간단하게 설명하면, 이 게임보다 더 쉬운 버전의 새로운 게임을 가져온 다음에 새로운 게임의 전략이 원래 게임의 루프 전략과 같다는걸 보여서 증명합니다.
자세하세 설명하면, 새로운 게임을 다음과 같은 규칙으로 하는건데요.
1) 100명의 죄수들이 각자 자기 번호가 나올때까지 상자를 열되 50번 초과하면 실패
2) 이전 죄수들이 연 상자는 다시 닫지 않고 다음 죄수가 모두 볼 수 있다. 이때 열린 상자 중에서 자기 상자가 있다면 바로 다음 죄수 차례로 넘어간다.
3) 100명 모두 통과하면 성공
새로운 게임은 원래 게임보다 정보가 더 많기 때문에 성공 확률의 upper bound라 할 수 있고 이 새로운 게임에서 어떠한 전략들을 쓰더라도 승패는 50개 초과의 루프가 있는지에 따라 갈리게 되므로 upper bound와 같은 루프 전략이 항상 최적의 선택이 됩니다
@@productlog5895 오...
12:47 엄청 작은확률일거같긴한데 그러면 반대로 엄청난 우연으로 끊어져 있던 상자를 연결시키는 경우가 될 수도 있지 않나요?
"죄수들을 도우려는 '교도관'이 '잠입'한다면"이라는 상황과 '상자 속 내용물을 바꿔놓는다'라는 해결책을 제시한 것을 종합하면 해당 상황은 상자 속 내용물을 모두 보고 마음대로 조작할 수 있는 상황임을 알 수 있습니다.
루프가 어떻게 형성되어있는지 관측할 수 있으니 루프가 반으로 잘 쪼개지도록 쪽지 한 쌍만 바꿔놓으면 모두가 살 수 있습니다.
아쉽게도 0.31의 확률을 뚫지 못하고 모두 처형되었답니다 ㅠㅠ
수학보다 정보 분야에서 더 중히 사용될 논문일것 같습니다. 천재적이고, 저는 교도관이 51이상 길이의 루프를 일부러 만들어도, 각 숫자에 무작위 숫자를 더해서 루프를 따라가면 의도성을 리셋하여 다시 30%로 돌아올 수 있다는 부분에서 더 경악했습니다…
‘닫힌 단방향 연결리스트가 1개 이상 섞여있는 모음’이 정렬되지 않은 상태에서 자료를 찾는다는 문제로 치환했을때, 노드가 10개 있고 찾아야하는 숫자도 10개가 있을때, 그냥 앞에서부터 찾으면 평균 50회의 엑세스로 10개 숫자를 모두 찾아낼수 있습니다.
위 해법을 적용할시, 30% 확률(최장 리스트의 길리가 전체 길이의 반이하일 확률)로 50회 이내로 모두 찾을 수 있고, 70% 확률로 50회 이상이 필요해집니다.
그러므로 전체 모음에 섞여있는 리스트 중 최장 리스트의 길이가 전체 모음 길이의 반 이하라는게 보장이 되면 위 해법대로 자료를 찾으면, 앞에서부터 순서대로 찾는것보다 무조건 빠르게 찾을 수 있죠.
그러므로 이 자료 모음의 메타데이터에 최장 리스트 길이를 넣어놓고, 최장 리스트의 길이가 전체 반 이상이면 앞에서부터 순서대로 자료를 찾고, 아니라면 루프해법으로 자료를 찾는다면 자료찾기를 더 효율화할 수 있는데, 이와 같이 특수한 방식으로 정보가 저장되는 경우를 잘 모르겠네요 아직…
@@supleehum7656 엑세스->액세스
놀랍게도 51개 까지도 살수있습니다! ㅎㅎ 바로 루프에 실패한경우 마지막 상자속 종이가 가르키는 숫자의 상자를 자신의 상자로 지목하는 방법입니다 이로써 길이 51의 루프를 가진 경우까지도 생존이 가능해집니다!
@@7Itruthㅋㅋㅋ 그러네요 문제의 조건을 명확히 해서 "자신의 쪽지가 들어있는 상자를 열면" 성공이라고 보완해야할 것 같네요
확률은 진짜 신기한게 파도파도 나오네.. 재밌게 잘보고 갑니다
만약 한명만 못 찾아도 전부 처형 당하는게 아니라 자기 번호를 찾은 죄수는 살리고 못 찾은 사람만 죽이는 걸로 규칙을 바꾼다면 살아남는 인원의 평균은 무작위로 뽑든 루프 규칙을 따라 뽑든 50명일까요...?
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명 나옵니다.
당연하죠....
@@TheManaka0504 ㅋㅋ..
@@TheManaka0504 제가 이미 기댓값 50명인거 증명해서 써놨는데 못보셨나요?
와 이런거 너무 재밌는거 같아요 역시 수학은 대단하네요
문제를 보고 즉흥적으로 바로 떠올랐던 생각이 '무작위의 죄수들이 같은 규칙으로 상자를 열게 해서 무작위성을 줄이면 확률이 획기적으로 확 오르지 않나?'
였는데 이렇게 일상적인 언어로 그 방법까지 자세하게 풀이된 걸 정독하니 지적 허영이 채워지는 것 같아 기분이 좋아지네요
이게 교양이 갖는 힘이겠죠. 저같은 멍청이들도 마치 스스로가 똑똑해지는 것 같은 기분을 느끼게 해 주니 아주 유쾌해지네요 좋은 영상 잘 보고 갑니다
굿
요컨데 확률을 거의 무한대로 끌어올릴 수 있다는 말이군요. 아주 멋진 전략입니다.
이렇게 되는 이유는 독립시행이 아니기때문이 아닐까 독립시행이라는건 앞의 결과가 뒤에 영향을 끼치면 안되는데 앞에서 상자를 열었을 때의 결과가 만약 1이라면 그 뒤에 상자는 1이 나오면 안된다는 영향을 주게되니까 결국 독립시행이 아닌거지.
중요한게 내가 내 번호로 시작하는게 아니라 규칙에 따라서 내가 시작한 박스 바로 전 박스가 내 번호가 되는거구나
루프라는 발상이 진짜 대단한 발견이네
100이라는 숫자를 개별로 보지않고 묶을 수 있는 경우의 수로 함축시킨거니까
아...1년만에 까먹고 다시 봄ㅋㅋㅋㅋ
와 간단히 말하자면
각각의 확률이 50%인건 바꿀수 없지만
각 죄수의 확률을 최대루프의 갯수라는 강력한 연관성을 만들어줘서 다같이 성공할 확률이 30퍼센트를 넘게 만들어주는 거군요
반대로 51개가 넘는 순간 그 루프에 있는 사람들은 전부 실패하게 되는거구요
방을 나가고 소통불가능 하다길래 들어가서 나가기전에 소리로 알려주는 줄 ㅋㅋㅋ
@@TheManaka0504 각각의 확률은 50% 동일합니다
@@TheManaka0504 각각은 50퍼센트는 맞는데 죄수끼리 확률이 독립이 아닌거임
갯수->개수
@@d2341a ...
답을보기 전에 상자에 적힌 번호로 이동해서 상자를 연다라는 방법까진 생각했지만 자신의 번호의 상자부터 시작한다는 조건과 그 확률적인 근거가 없어서 틀렸다고 생각해야겠군요
개쩌는 확률업 이벤트인가
ㅔ 잘 찾아오셨습니다
와...신비로운데... 분명히 독립적인 사건인데...이게 왜 이렇게 되는거지....루프가 뭐라고....
아 30%면 개혜자 맞지ㅋㅋㅋ
13:13 뭔가 죄수들이 단순히 상자번호에 특정 수를 더하는 "간단한" 방법으로 루프 전략을 쓰는 걸로는 그 전략을 미리 예상한 간수 입장에서 할 수 있는 게 있을 거 같긴 한데 잘 모르겠네요...... 더하기에 의해 전체 구조가 보존되기에 사실상 안 섞이면서 가장 긴 루프의 길이가 50 이상이 되도록 할 수 있을 거 같은데......
주어진 상황이 같더라도 랜덤일 경우와 규칙을 세웠을 경우 확률이 극적으로 달라지는게 재밌네요
만약 못찾으면 루프의 길이가 51일 확률이 가장 크니까 마지막에 본 숫자가 답일 것이라고 믿고 찍는다면 1/51만큼 확률이 더 커져 33%까지 올릴 수도 있지 않을까요?
그럼 사실상 100개중 51개의 상자를 열 수 있다는건데 당연히 확률이 다르죠...
잠만 머리가 띵했음. 이거도 맞는듯?
@@42_cloud 저는 몇번째 상자에 자신의 숫자가 들어있는지를 알기만 하면 된다고 생각했는데 제가 문제를 잘못 이해한 건가요?
@@한승혁-k8w 1:04 자신의 번호를 모두 "찾으면"
"자신의 번호가 있는 상자를 알면"이 아니니까... 번호가 들어있는 상자를 "찾아야" 통과라고 생각하는게 맞지 않을까요... 그냥 국어 문제인 것 같긴 한데...
50개를 열어서 본인의 숫자를 찾는겁니다
본인의 숫자가 어디에 있다고 지목해서 맞추는게 아니구요
결국 죄수는 전부 총살이라는거죠?
말…..말도안되……
결국50개만 열어볼수잇는건 숫자로만 보면 똑같이 50% 아닌가
숫자는 비밀이 참 많구나.. 다시또 배우고 갑니다.
되->돼
와 진짜 ㅈㄴ재밌네 ㅋㅋㅋㅋㅋㅋㅋ
다른 예시로 죄수들이 모두1~50번만 연다고 하면 확률은 0%가 되겠지요
예상은 했지만 댓글들 보니 이해 못한 사람들 참 많네요. 정말 기가막힌 수학적 원리인데...
여기서 초반 박스를 선택하는 추가적인 방법을 하나 더 설정하면 성공확률을 31퍼센트에서 37퍼센트로 높일 수 있습니다!!
뭐야 어떻게요
알려주셈
@@deepblue003 초반박스를 1번부터 50번까지 한명씩 정하게하면 최대확률이나올것같은데
이 영상에서 설명하는 전략이 optimal 입니다. 더 나은 전략은 존재하지 않습니다.
아 진짜 감사해요 이거 보다가 불면증이 사라졌네요 ㅠㅠㅠ
근데 이게 최고의 방법이라는 증명은 아직 없는 건가요?
P=nP
아쉽게도 이것이 최고의 방법인지 아닌지 증명을 할 수 있다는 게 아직 증명되지 않았습니다...ㅜ
어떤 문제는 인간의 이성으로 증명할 수 없을 수도 있어요. 이 문제가 그 문제인지조차 확실하지 않지만.
상자로 만들어진 루프안에 걸리며, 앞 사람이 열었던 상자의 번호를 최대한 피한다가 핵심이구나. 루프에 걸리면 무조건 자기 번호는 나오니까. (자기 번호에서 시작한 루프이므로 루프가 나오면 자기 번호가 나온게 됨)
이해하기 힘든 수수께끼는 아닌데.. 쉽게 이해하려면 숫자를 줄여 생각해 보면 돼요. 예를 들어 100명이 아니라 2명이라면, 전략 없이 고르면 1/4확률이지만, 먼저 들어가는 사람이 자기가 뽑을 상자를 얘기하고 들어가면 (1번이든 2번이든) 나중에 들어가는 사람이 그 상자를 열 일이 없으므로 확률은 1/2이 돼서 살 확률이 두배로 느는거죠.
위 문제에선 수감자들의 정보교환은 없다고 나오는데요?
@@2w051 뽑은 결과에 대해 정보교환이 불가능한거지 뽑기 전에 수감자들끼리 규칙은 정할 수 있죠
@@꼬꼬꼬-g1h 근데 미리 뭐 뽑을지 말해줘도 앞번호가 뽑지 않은거에 자기 번호가 있을지는 모르니 아무 의미없는거 아닌가요
정보 교환이 없더라도 영상에 나온대로 1번은 1번 상자를 열고 2번이 2번 상자를 열면 같이 죽거나 같이 살거나 라서 확률이 늘잖아요
윗 댓글에서 말한내용은 쉽게 설명하기 위해 정보 교환이 있는 것처럼 그냥 가정한 거고요
@@2w051 그니까 도 아니면 모죠. 둘다 성공하거나 둘다 죽거나. 그래서 전략의 성공 가능성은 1/2!
개인들의 확률을 집단의 확률로 바꿔버리는 마법같은 전략이네요.
이런걸 볼때마다 뭔가 기존 수 체계가 2d면 3d에서 문제를 해결하는 것 같다.