확률 1000000000000000000000000000000배 높이기
HTML-код
- Опубликовано: 22 сен 2022
- 처음 설명을 들었을 때 예상하는 반응 03:55
하지만 듣다 보면 수학의 재미에 빠져들 겁니다!!
(설마 제목에 0몇 개 인지 세보는 분은 없겠죠....?)
#확률 #수수께끼 #베리타시움
Special thanks to Destin of Smarter Every Day (ve42.co/SED), Toby of Tibees (ve42.co/Tibees), and Jabril of Jabrils (ve42.co/Jabrils) for taking the time to think about this mind bending riddle.
Huge thanks to Luke West for building plots and for his help with the math.
Huge thanks to Dr. Eugene Curtin and Dr. Max Warshauer for their great article on the problem and taking the time to help us understand it: ve42.co/CurtinWarshauer
Thanks to Dr. John Baez for his help with finding alternate ways to do the calculations.
Thanks to Simon Pampena for his input and analysis.
Other 100 Prisoners Riddle videos:
minutephysics: www.youtube.com/watch?v=C5-I0...
Vsauce2: www.youtube.com/watch?v=kOnEE...
Stand-up Maths: www.youtube.com/watch?v=a1DUU...
TED-Ed: www.youtube.com/watch?v=vIdSt...
▀▀▀
References:
Original paper: Gál, A., & Miltersen, P.B. (2003). The Cell Probe Complexity of Succinct Data Structures. BRICS, Department of Computer Science, University of Aarhus. All rights reserved. - ve42.co/GalMiltersen
Winkler, P. (2006). Seven Puzzles You Think You Must Not Have Heard Correctly. - ve42.co/Winkler2006
The 100 Prisoners Problem - ve42.co/100PWiki
Golomb, S. & Gaal, P. (1998). On the Number of Permutations on n Objects with Greatest Cycle Length k. Advances in Applied Mathematics, 20(1), 98-107. - ve42.co/Golomb1998
Lamb, E. (2012). Puzzling Prisoners Presented to Promote North America's Only Museum of Math. Observations, Scientific American. - ve42.co/Lamb2012
Permutations - ve42.co/PermutationsWiki
Probability that a random permutation of n elements has a cycle of length k greater than n/2, Math SE. - ve42.co/BaezProbSE
Counting Cycle Structures in Sn, Math SE. - ve42.co/CountCyclesSE
What is the distribution of cycle lengths in derangements? In particular, expected longest cycle, Math SE. - ve42.co/JorikiSE
The Manim Community Developers. (2021). Manim - Mathematical Animation Framework (Version v0.13.1). - www.manim.community/
▀▀▀
Special thanks to Patreon supporters: RayJ Johnson, Brian Busbee, Jerome Barakos M.D., Amadeo Bee, Julian Lee, Inconcision, TTST, Balkrishna Heroor, Chris LaClair, Avi Yashchin, John H. Austin, Jr., OnlineBookClub.org, Matthew Gonzalez, Eric Sexton, john kiehl, Diffbot, Gnare, Dave Kircher, Burt Humburg, Blake Byers, Dumky, Evgeny Skvortsov, Meekay, Bill Linder, Paul Peijzel, Josh Hibschman, Timothy O’Brien, Mac Malkawi, Michael Schneider, jim buckmaster, Juan Benet, Ruslan Khroma, Robert Blum, Richard Sundvall, Lee Redden, Vincent, Stephen Wilcox, Marinus Kuivenhoven, Michael Krugman, Cy 'kkm' K'Nelson, Sam Lutfi, Ron Neal
▀▀▀
Written by Derek Muller and Emily Zhang
Filmed by Derek Muller and Petr Lebedev
Animation by Ivy Tello and Jesús Rascón
Edited by Trenton Oliver
Additional video/photos supplied by Getty Images
Music from Epidemic Sound and Jonny Hyman
Produced by Derek Muller, Petr Lebedev, and Emily Zhang 
Наука
도저히 직관적으로 이해가 안돼서 직접 프로그래밍해서 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퍼씩 낮아진다고 계산해서 생긴 오차인듯 합니다.
제 설명을 통해 직관적 이해에 도움이 되셨으면 좋겠습니다.
하지만 100여명의 죄수들은 이해를 하지 못했고, 결국 모두 처형당했다고 합니다....
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
이해해도 죽을 확률이 69%....
현실은 이게맞다
거기 석호필이 있었다..
흑흑 너무 슬프다
이거 본 채널에서 봤을때 정말 재미있었는데 이렇게 만들어주시다니 감사합니다 ㅎㅎ
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ진짜 올해 본 영상중에 제일 감탄사 나오는 영상이다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
본채널에서 본 영상인데 흥미롭고 재밌는 영상입니다ㅎㅎ 유튜브가 있어서 책으로 보면 어려운 문제도 재밌게 접근할수있어서 좋네요
4:47 이 계산이 효율적인 결정적인 이유
항상 재밌게 보고있어요 ㅎㅎ
거의 불가능에 가까운 확률을 30% 라는 어느정도 가능한 확률로 만들어버리네요 대단합니다! 위에 코딩하시는분들도 멋지구요!
자신의 번호를 고른 죄수의 숫자가 이항분포를 따르지 않는것이 인상적이네요. 어치피 100 밑의 결과는 패배니까 성공한 죄수의 수를 0부터 100까지 분포시키는게 아니라 100 아니면 그 밑의 값들로 극단화 시키는게 멋지네요. 다른 "완벽한 성공" 문제에도 충분히 적용시킬 수 있어보여서 더욱 좋은 것 같습니다
불규칙의 조건에 규칙으로 대응하는 전략이네요!! 오 정말 멋진 아이디어 입니다. 그 뒤의 확률계산보다 죄수들에게 똑같은 규칙을 만들어주는 부분이 더 놀라웠습니다.
교도소장이 정성껏 번호가 적힌 상자에 하나씩 넣어줘서 그런거임. 그냥 주머니 안에 넣고 하나씩 뽑게 시켰으면 이런일 없었음
진짜 이런영상들 너무 재밌습니다
영상이 정말 흥미롭고 재밌었어요
좋은 영상 만들어주셔서 감사합니다
빨리 드음 영상 가져와!!!! 재밌게 수학 배우고 싶단 말이야!!!!!!
이분 더빙?이 정말 좋은게 약간 재밌는 수학 이야기 할때 목소리에 행복해하고 흥미를 정말 드러내 주시는 것 같아서 좋아요
맞아요 목소리도 좋고
@@PSYsAudianceㅆㅇㅈ
솔직히 좋은 더빙은 아니죠.. 너무 웅얼웅얼 거리는 게 개선이 쭉 안 되서 아쉬워요 쿠르츠게작트는 진짜 전문 성우 같이 좋던데
@@user-oz3lg2cj2e전 좋은 더빙이라고 생각해요ㅎㅎ
진짜 너무 흥미롭고 재밌어요
제가 죄수였다면 이미 좌절하고 저런생각을 할 시도조차 하지 못했을거 같은데 신기하네요 ㅋㅋㅋㅋ 확률의 신비함을 다시 한번 느낍니다. 처음 설명을 들었을때는 이해가 잘 안됬지만 두세번 돌려보니 이해가 가네요.. 좋은 영상 감사합니다
예전에 교란순열 관련 문제를 풀면서 일대일대응을 집합을 루프들로 분할하는 아이디어를 썼는데... 이런 문제에서도 쓰이는게 신기하네요
오 저도 ㅋㅋ
자신의 번호를 고른 죄수의 숫자가 이항분포를 따르지 않는것이 인상적이네요. 어치피 100 밑의 결과는 패배니까 성공한 죄수의 수를 0부터 100까지 분포시키는게 아니라 100 아니면 그 밑의 값들로 극단화 시키는게 멋지네요. 다른 "완벽한 성공" 문제에도 충분히 적용시킬 수 있어보여서 더욱 좋은 것 같습니다
.
맞춘 사람은 살려준다고 했을 때도 루프 전략을 쓰기로 합의 본다면 재밌는 점이
교도관은 1명 이상이 죽을 확률은 사실상 100%라고 생각했을텐데 사실은 70%라는거죠..
만약에 돈을 걸고 하는 게임 같은건데 교도관 맡으면 질 수가 없다고 생각했다가
틀린 사람이 한명도 없는 순간 이게 가능할리가 없는데 하면서 멘탈 나가
정말 완벽한 영상입니다! 경이로워요
진짜 너무너무 재밌다 최고야
애니메이션 덕분에 이해하기 백배 쉬워진 것 같습니다. 쉽고 재밌는 영상 감사합니다
진짜 아이디어 좋고 신기하네요
와 이 채널 열심히 자막 해석하면서 낑낑대다가 한 15분 보고 포기하고 그랬었는데 한국어 채널이 생겼군요 흥해라~~~
넘 재밌네용ㅎㅎ😊
100명의 죄수에게 상자를 60번 열라고 하면 전부 생존할 확률이 50%를 넘어가네요 ㄷㄷㄷ
이야 재밌네요 ㅋㅋㅋ
각각 개인의 확률은 50퍼지만 전체가 성공할 확률은 31퍼로 극단적이게 되는 확률분포라니 ㅋㅋㅋ 대신 실패할때는 다들 못 찾아버리는 것도 재밌네요.
같이 성공하거나 같이 폭망하거나
10:30 이 그래프 설명 너무 좋았습니다 👍
좀 무식해서 그런데 개인의확률이 50퍼이면 전체 확률도 50%아닌가요 저략을 저렇게 설명하지 말고 그냥 1~50번에서만 찾으라하면 적어도 50명은 사는거 아닌가? 고로 50%
@@lijingnan5409 100명이 다 찾아야 살아요
@@lijingnan5409 자기 번호 찾은 사람만 살아나가는 규칙이 아니에요
@@user-on9jh2or4s 네 저도 처음에 그렇게 이해했지만 30%가 된들 80%가 된들 죄수에는 속하고 싶지 않네요 좀 태클을 거는거같은데 퍼센트가 늘어나도 도전은 해보고 싶지않습니다 ㅜㅜ
@@lijingnan5409 ㄹㅇ 멍청한게 킬포네 ㅋㅋㅋㅋㅋ
개쩔어요!
자신이 찾은 쪽지를 가지고 나가버리면 이 문제가 성립이 안되는군요.
영상의 접근방법이 제가 떠올린 의문의 순서와 동일한게 정말 멋졌어요
자신의 번호의 상자부터 시작하면 무조건 그 루프안에 해당번호를 찾을 수 있다는걸 이해했을때 소름이 쫙 ㅋㅋㅋ
10:55 핵심적 질문에대한 답은 이미
4:40 ~5:14 에 잘 설명돼있네요
너무 신기하네..
12:06 와 미친 이 부분에서 소름이 쫙.. 천재다
와 이런거 너무 재밌는거 같아요 역시 수학은 대단하네요
좋은 영상 감사합니다
상자 열기 시행의 독립성을 제거하다니 대단하네요 ㅋㅋㅋㅋㅋㅋ 이건 마치 박스의 위치를 가지고 다른 사람과 서로 소통하고 있는 것과 다름 없군요
번호가 새겨진 상자에 하나씩 넣어준 교도소장의 정성엔 다 이유가 있었던거라고....
논리적으로는 그럴수도 있겠다 싶긴 하지만 너무나 직관에 반하는 결과죠. 예전에 직접 시뮬레이션 해보고 받아들이긴 했는데, 여전히 신기합니다.
뭔가 아닌것같은데 2명인걸로 생각해봐도 되는게 신기함
@@user-tr7dz2ll1e 두명일 때는... 다른거 아닌가요?
@@user-tr7dz2ll1e 2명일땐 사용불가.. 그냥 50퍼.......
@@user-tr7dz2ll1e 원태야...
2명일때도 적용됩니다
루프전략 안썼을땐 1/2 × 1/2로 25%확률로 생존하지만
루프전략 사용한 경우 1번박스에 1번종이, 2번박스에 2번종이 들어있다면 (루프길이 1인경우) 성공, 1번박스에 2번종이, 2번박스에 1번종이(루프길이 2) 인경우 실패이기 때문에 50% 확률로 생존합니다.
와 이번 영상 진짜 재밌다
재밌었습니다 감사합니다
1명만 틀려도 모두가 죽는 상황을 결국 아무도 안 틀릴 수 있는 전략으로 파훼하는거네요.
그 반대급부로 모두가 틀려버릴수도 있지만, 1명만 틀려도 죽는 상황에서 그건 중요한게 아니니까요.
모두가 틀릴 확률이 아마 저 전략 안쓰고 모두가 살아남을 확률이랑 비슷할듯. 제일 큰 루프가 100이라는건 100개 다열었을때 자기 번호가 맨 마지막에 있다는 거니까
@@user-hv5qu7kz1m ㄴㄴ 틀림
모두가 틀릴 확률은 약69%임
@@user-lr7he8ml9d ㄴㄴ 틀림 1%임
감사합니다! 감방에 들어가서 상자 고르기 전에 99명의 재소자들에게 보여주기 좋은 영상이네요..!
미쳤다 유튜브 영상 보면서 감탄하는건 처음...
너무 재밌어요!! 이런 수학퍼즐 나오는 책 좀 추천해주세요!?
와 ln2나오는거 개소름돋음..
상자 안에 무슨 쪽지가 있는지 사전에 알 수가 없으니까 전략을 아무리 짜도 의미가 없다고 생각했는데 그게 전혀 아니었네 ㅋㅋㅋ 머리가 띵하네요
최고입니다.
굉장히 흥미롭다.... ㄷㄷ..
못 믿겠어서 코딩으로 실험해봤는데 진짜 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 실험이라고 해봤자 코드 짜고 돌리는건데 몇십줄 짜리코드를 짜는데 몇분 코드 돌리는데 몇초에요..
맞춘 사람은 살려준다고 했을 때도 루프 전략을 쓰기로 합의 본다면 재밌는 점이
교도관은 1명 이상이 죽을 확률은 사실상 100%라고 생각했을텐데 사실은 70%라는거죠..
만약에 돈을 걸고 하는 게임 같은건데 교도관 맡으면 질 수가 없다고 생각했다가
틀린 사람이 한명도 없는 순간 이게 가능할리가 없는데 하면서 멘탈 나가는거죠...ㅋㅋㅋㅋㅋㅋㅋ
하지만 70프로로 51명 이상 죽는
라이어게임이나 카이지에 나올법한 게임이네
@@kuroneco0009 한 명이라도 실패하면 전부 죽으니, 오히려 (사악한) 간수 입장에서는 좋을 지도요.
재밌는건 루프전략을 써도 개개인의 생존률은 딱 50%라는거. 고의적으로 51이상 루프되도록 상자를 배치하지 않는 한 아무튼 쓰는게 유리한 전략이긴 하네요.
아그러면 맞춘사람은 살려준다고 했을때도 쓰는게 이득인거네요 개개인 입장에서 봐도
잘 모르겟어요 7:34 부터 조금 막히네용 졸려서 그런가ㅜㅜ 근데 영상 너무 재밌어용 정주행 하러 갑니당ㅎㅎㅎ
게임 하기전에 전략을 정함으로써 독립시행을 종속사행으로 바꾼거군요 루프 말고 더 효율적인 방법도 존재할까요?
뭔가 사람이 늘어날수록 중간에 하라는대로 안해서 멸망할것같다ㅋㅋㅋ
그래도 그사람이 50퍼 확률만 뚫어낸다면 사는거 아닌가...?
@@unarmed_civilian 50% 병
@@공략 ㅋㅋㅋㅋㅋㅋㅋㅋ 병 한글자에 감정이 담겨있네
길이가 51이상인 루프가 있는 경우에도 방법만 바꾸면 손쉽게 재배열이 되어버리네요. 정말 신기합니다.
그런데 회로의 개수를 구하는 과정에서 회로의 길이로 나눠주는 이유가 뭔가요?(길이 99짜리면 99로 나누는 등) 원순열 개념은 아는데 저 경우에는 모든 회로가 다 다른 것 아닌가요? 원순열은 회전하면 같지만 저건 한칸만 회전해도 한 박스에 들어간 숫자가 모두 달라지니까요.
주어진 상황이 같더라도 랜덤일 경우와 규칙을 세웠을 경우 확률이 극적으로 달라지는게 재밌네요
운빨X망으로 보이는 게임이라도 수학적인 이해를 바탕으로 적절한 전략을 사용하면 이렇게까지 가능성을 높일 수 있다는게 대단하네요
운빨x망 ㅋㅋㅋㅋ 근데 진짜 신기하네요
그래도 31%의 기적이 일어나야 해요!
그래도 제 솔랭은 운빨x망입니다. 그렇게믿어야 제 맘이 편해요
@@user-ch6nc5lc3c 31%면 개 혜자네 ㅋㅋ
@@user-ch6nc5lc3c 어차피 죽을 거 31%로 확률을 늘려준 것에 감사해야...
확률이 높아지는 이유는 좀더 개념적으로 쉽게 설명하면,
죄수들마다 서로 다른 고유 번호 있고 그 번호로 인해 죄수들이 서로 겹치게 않게 시작 번호 상자를 여는 겁니다. 죄수들 모두가 랜덤하게 아무 상자나 열면서 시작하는 것과는 완전 다르죠.
이게 확률을 높이는 키워드입니다. 상자의 시작 번호가 고유적으로 다 다르게 되어 100명이든 100만명이든 그 죄수 만큼 상자 여는 시작 위치가 서로 달라 그 만큼 다시 상쇄됩니다.
그래서 결과적으로 죄수가 아무리 늘어나도 상자 50루프 해당되는 1/3정도 확률만 비슷하게 계속 남게 되는 겁니다.
핵심 이해를 잘못하신듯 합니다. 중요한 것은 서로 다른 상자를 열었기 때문이 아니라, 박스를 연 다음 다음 상자를 선택하는 방법에 있는 겁니다. 영상에 나오는 "링크"가 이 해법의 핵심이죠.
팩트)둘다 중요함
천재적이네요.
오랜만에 다시 봐도 재밌다
이 영상을 보고 감옥에 들어가지 않기 위해 착하게 살아야겠다는 생각이 들었습니다
그냥 쉽게 100명을 2명으로 줄이기만 해도 이해하기 편할듯. 2명이 상자 두개 중 자신의 번호를 찾는 독립시행을 한다면 둘다 맞출 확률은 25%지만, 자신의 번호가 적힌 상자만 연다는 가정을하면 50%가 되죠.
혹시 루프전략이 생존가능성이 최대확률임은 증명이 된건가요?
13:13
여기서 질문을 한 번 더 할 수 있겠네요. 이 전략마저 엿들은 사악한 간수가 어떻게 번호를 배열하더라도, 죄수들이 임의로 정한 k를 듣지 못했다면 죄수들의 최소 생존 확률이 30%를 넘길 수 있을까요?
진짜 빡대가린가
이런 수학은 마지막에 갑자기 익숙한 함수가 나오는게 소름그자체인듯 처음엔 그저 랜덤에서 규칙찾기 인데 갑자기 1/x 함수라니
맞죠 마지막 그 그래프 나오자마자 소름..
내 죄수번호와 "같은" 번호를 가진 박스를 까는 것이 시작이 중요함.
아 진짜 감사해요 이거 보다가 불면증이 사라졌네요 ㅠㅠㅠ
콜라츠 추측이 생각나는 풀이네요 흥미롭습니다 🤣🤣 저걸 낸 사람은 컴퓨터 데이터 접근 방식 연구하던 사람이었을라나요
@@TheManaka0504 ㅇㅎ 감사요
@@TheManaka0504 다른 대댓에서 각각의 성공확률이 69.7%다 라고 하신 분이 다른사람 보고는 제대로보라고하네요 그냥 놀랍
이해가 좀 안되는 부분이 있어요 ㅠㅠㅠ
영상 마지막에 모두성공하거나 모두실패하며 소수의 인원만 숫자를 찾는 아쉬움이 없다고 했는데요
만약 1-100까지 중에 예를들어 1-10 11-70 71-100 이렇게 세개의 루프가 있다면 1-10과 71-100의 죄수들은 본인의숫자를 찾을 수있는거 아닌가요??
모두성공이라는게 50이하의 루프에서 30프로 확률로 자기루프에 있는 사람들 전원이 성공하거나 70확률로 전원이 실패하거나 이 말인가요?
루프전략을 사용했을때와 그냥 무작위로 선택했을때의 차이를 말하는거 같아요
그냥 무작위 50%확률로 하면 99명이 찾았지만 1명이 못찾는다던지 해서 아쉽게 실패하는 경우가 있지만,
루프전략은 30% 확률로 ( 루프길이가 50이하일 확률 ) 모두 성공하거나
70%확률로 ( 루프길이가 50 이상일 확률 ) 와장창 실패하니까요,
한명이라도 틀린다면 실패한다는점이 중요한거같아요
그런의미 같네요
가장 최소치인 루프가 51개만 되도 그때는 숫자 못찾는 사람이 51명이니까
절반이상 박살나냐
운없게 한두명 틀려서 떨어지냐 이런차이?
요런거 게임처럼 만들면 수많은 사람이 참여할거고 더 정확히 분석이 될거같네요.
진짜 내 번호가 루프에 포함됐다는 걸 경험해보고 싶어요.
ㄹㅇㅋㅋㅋ 방금 그림판으로 그려봤는데도 루프에 내번호가 있는게 와닿지않음
@@탈론장인 모든 박스는 루프를 무조건 만듬
중간에 끊기는건 있을수없음
그렇기때문에 내 번호의 박스를 연다는 것 = 내 번호가 들어간 루프를 시작한다는것
남자들끼리 기차놀이를 한다고 생각해보세요. 첫번째 남자는 두번째 남자 X구멍에 넣어야겠죠? 두번째 남자는 또 다시 세번째 남자 X구멍에 넣구요. 그럼 마지막 남자는 어디에 넣어야 할까요? 첫번째 남자 X구멍만 남았겠죠? 이게 바로 1대1 대응함수의 매력이랍니다.
@@lllilllililill 아니 ㅋㅋㅋㅋㅋㅋㅋ
@@lllilllililill이게 시발 ㅋㅋㅋㅋㅋ 루프의 직관적인 설명이라는 게 빡치네
확률은 진짜 신기한게 파도파도 나오네.. 재밌게 잘보고 갑니다
독립시행으로 했을때 가우시안 분포를 따르는것이
독립성을 없애고 서로 연결 correlated 시키게 되면 분포가 변화하는 것과 같군요
마치 입자의 움직임을 한방향으로 유도하면, 결과가 가우시안이 아니게 되는 것 처럼요
굉장히 흥미로운데요 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이 맞아요?
@@---qm5yb 영상을 좀 보세요..
@@---qm5yb 개개인으로 보면 50프로가 맞죠. 전체가 성공할 확률이 30프로라 죄수 한명이 성공할 확률이 50프로라 생각할 수 있지만 죄수 모두가 성공 49명성공, 48명성공 ... 등등에서 개인이 성공할 확률까지 모두 더하게 된다면 결국 50프로가 됩니다
@@---qm5yb 계산기 돌려보니 50정도 나옴. 최대길이가 50이하라 무조건 성공(31퍼) + n->1~50 (50 - n) / {(50 + n) * 100} 하면 약 18.x퍼 부동소수점연산 오차 생각하면 50퍼 나올듯
상자마다 무작위로 1부터 100까지 숫자를 적어넣었으면 절대 불가능했을텐데, 1부터 100까지의 숫자가 적힌 종이를 1부터 100까지 숫자가 적힌 상자에 넣으면 결국 종이와 상자가 1대1로 매칭된다는 점을 노련하게 이용한 해결법이네여. 굉장히 똑똑합니다 ㅎㅎ
근데 상자에 숫자가 안 적혀있어도 죄수들이 왼쪽 위에 있는 것부터 1이고 쭉 번호를 매겨서 오른쪽 아래가 100이라고 하자고 약속하고 루프 전략을 쓰면 같은 거 아닌가요?
@@dayservant네 맞아요 상자의 위치만으로 번호를 정해도 문제없습니다
ㅋㅋㅋ원댓글 제대로 이해못한거같은데
영상제대로 안봤지.... ㅋㅋ
ㅋㅋ정확하게 이해 못했네
우오아 ... 신기행..
감사합니다.
개쩌는 확률업 이벤트인가
ㅔ 잘 찾아오셨습니다
처음엔 직관적으로 이해가 안 되었는데 개인이 생존할 확률은 그대로고 전원 생존의 확률이 올라간다니까 이해가 되네요. 재밌게 봤습니다
개인 성공 확률은 그대로 1/2 아닌가요?
개인은 결국엔 상자의 절반을 까게 되는데 왜 31퍼센트일까요? 제가 이해를 잘못했나 다시 봐야겠네요
네 단순하게 결국 모든 개인이 상자의 절반을 깐다는 걸 생각하면 개인의 성공 확률은 1/2이 맞는 것 같아요~
둘다 뭐함?
내 번호의 루프가 50보다 클확률이 69/100 니깐 당연히 개개인의 실패확률도 69/100 일수밖에 없는거 아닌가요
레고 설명이 굉장히 좋네요
이렇게 되는 이유는 독립시행이 아니기때문이 아닐까 독립시행이라는건 앞의 결과가 뒤에 영향을 끼치면 안되는데 앞에서 상자를 열었을 때의 결과가 만약 1이라면 그 뒤에 상자는 1이 나오면 안된다는 영향을 주게되니까 결국 독립시행이 아닌거지.
아쉽게도 0.31의 확률을 뚫지 못하고 모두 처형되었답니다 ㅠㅠ
문제를 보고 즉흥적으로 바로 떠올랐던 생각이 '무작위의 죄수들이 같은 규칙으로 상자를 열게 해서 무작위성을 줄이면 확률이 획기적으로 확 오르지 않나?'
였는데 이렇게 일상적인 언어로 그 방법까지 자세하게 풀이된 걸 정독하니 지적 허영이 채워지는 것 같아 기분이 좋아지네요
이게 교양이 갖는 힘이겠죠. 저같은 멍청이들도 마치 스스로가 똑똑해지는 것 같은 기분을 느끼게 해 주니 아주 유쾌해지네요 좋은 영상 잘 보고 갑니다
굿
내용은 얼추 이해가는데 그래도 반례가 잇지않을까해서 직접 해봤는데 예를들어 내가1번이고
1번 상자안에3이 3번 상자안에 5가, 이런식으로 쭉 이어갓을때, 이걸 간단히 1-3-5-...이라고 표현하면
저 간단히 표시한 식이 무조건 루프를 형성한다는 가정하에 저 루프안에서 언젠가 어떤 숫자(x)는 무조건 x-1이 되어야만 루프가 완성되기때문에 본인 숫자가 잇을수밖에 없네요.
예를들어 ...-97-99-1-3-5-...처럼.
진짜 미쳣다...
여기서 초반 박스를 선택하는 추가적인 방법을 하나 더 설정하면 성공확률을 31퍼센트에서 37퍼센트로 높일 수 있습니다!!
뭐야 어떻게요
알려주셈
@@deepblue003 초반박스를 1번부터 50번까지 한명씩 정하게하면 최대확률이나올것같은데
이 영상에서 설명하는 전략이 optimal 입니다. 더 나은 전략은 존재하지 않습니다.
수능 확률 문제에서 항상 주머니 안에 넣고 하나씩 뽑게 시키는 이유가 있었음.... 야바위처럼 개별 상자에 넣든지, 컵에 넣든지 하면 순서, 모양, 위치 때문에 연번을 매길 수 있게 되고 루프 전략을 적용시킬 수 있게 됨
수능에서는 특별한 언급이 없으면 말 그대로 "무작위"로 뽑도록 하니까 애초에 "전략"이 개입하지 않았다고 보는게 맞습니다. 루프전략을 세운 순간 "무작위"가 아니게 되죠.
루프전략이 개사기인 이유
무작위로 뽑는다고 할때 보통 균등분포임을 생략합니다. 수능에서는 특별한 언급이 없는 한 균등분포라고 생각하는게 맞을 것 같습니다.
수학보다 정보 분야에서 더 중히 사용될 논문일것 같습니다. 천재적이고, 저는 교도관이 51이상 길이의 루프를 일부러 만들어도, 각 숫자에 무작위 숫자를 더해서 루프를 따라가면 의도성을 리셋하여 다시 30%로 돌아올 수 있다는 부분에서 더 경악했습니다…
‘닫힌 단방향 연결리스트가 1개 이상 섞여있는 모음’이 정렬되지 않은 상태에서 자료를 찾는다는 문제로 치환했을때, 노드가 10개 있고 찾아야하는 숫자도 10개가 있을때, 그냥 앞에서부터 찾으면 평균 50회의 엑세스로 10개 숫자를 모두 찾아낼수 있습니다.
위 해법을 적용할시, 30% 확률(최장 리스트의 길리가 전체 길이의 반이하일 확률)로 50회 이내로 모두 찾을 수 있고, 70% 확률로 50회 이상이 필요해집니다.
그러므로 전체 모음에 섞여있는 리스트 중 최장 리스트의 길이가 전체 모음 길이의 반 이하라는게 보장이 되면 위 해법대로 자료를 찾으면, 앞에서부터 순서대로 찾는것보다 무조건 빠르게 찾을 수 있죠.
그러므로 이 자료 모음의 메타데이터에 최장 리스트 길이를 넣어놓고, 최장 리스트의 길이가 전체 반 이상이면 앞에서부터 순서대로 자료를 찾고, 아니라면 루프해법으로 자료를 찾는다면 자료찾기를 더 효율화할 수 있는데, 이와 같이 특수한 방식으로 정보가 저장되는 경우를 잘 모르겠네요 아직…
@@supleehum7656 엑세스->액세스
놀랍게도 51개 까지도 살수있습니다! ㅎㅎ 바로 루프에 실패한경우 마지막 상자속 종이가 가르키는 숫자의 상자를 자신의 상자로 지목하는 방법입니다 이로써 길이 51의 루프를 가진 경우까지도 생존이 가능해집니다!
@@7Itruthㅋㅋㅋ 그러네요 문제의 조건을 명확히 해서 "자신의 쪽지가 들어있는 상자를 열면" 성공이라고 보완해야할 것 같네요
와 이건 진짜 재밌네요
요컨데 확률을 거의 무한대로 끌어올릴 수 있다는 말이군요. 아주 멋진 전략입니다.
ㅋㅋㅋ현실은 100명중에는 분명 똥멍청이가 있을거기 때문에... 쪽지 찾았다고 신나서 가지고 나오는 놈이 있을거고
루프는 이어지지 않을거임...
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 가지고 나오는 순간 간수 표정 씨익~ ^^
루프를 타다보니 아무것도 들어있지 않은 상자가 나왔다..
만약 한명만 못 찾아도 전부 처형 당하는게 아니라 자기 번호를 찾은 죄수는 살리고 못 찾은 사람만 죽이는 걸로 규칙을 바꾼다면 살아남는 인원의 평균은 무작위로 뽑든 루프 규칙을 따라 뽑든 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부터 50까지 열어보고 나가는 시간을 정해서 몇 분 이전에 나가면 1부터 50 사이에 2가 있는거고 후에 나가면 51부터 100 사이에 있는 거다 이런 식으로 하면 안됨?
100루프를 깨기위해 각상자에 5를 더한다고 했는데
특정 선형함수로 박스번호를 바꿔서 무조건 가장 긴 루프를 50이하로 만들수 있을까요?
아니면 그저 랜덤으로 재배열하는거라 31%라는 확률은 변함이 없는걸까요
어떠한 방식으로 박스 번호를 정하든 ~31%가 나올 것입니다. 특정 함수로 박스번호를 매기더라도 결국은 루프전략이라는 기본 동작원리는 동일하니까요.
아 30%면 개혜자 맞지ㅋㅋㅋ
이해가 안되서 하는 질문은 상대방도 한번 더 생각해보게하고 유익하다 생각하는데.. 끝까지 개소리로 틀렸다고 GR하는 인간들은 진짜..... 감사하다. 상대적으로 내가 똑똑해질 수 있는 이유니까.
되서->돼서
13:13 뭔가 죄수들이 단순히 상자번호에 특정 수를 더하는 "간단한" 방법으로 루프 전략을 쓰는 걸로는 그 전략을 미리 예상한 간수 입장에서 할 수 있는 게 있을 거 같긴 한데 잘 모르겠네요...... 더하기에 의해 전체 구조가 보존되기에 사실상 안 섞이면서 가장 긴 루프의 길이가 50 이상이 되도록 할 수 있을 거 같은데......
이 영상은 진짜로 감탄하면서 봤다
아주 간단하고 직관적으로 설명해드릴게요
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%라는거고? 살 확률과 죽을 확률은 교도관이 상자에 숫자를 배치할때 이미 정해지는거기 때문에? 제가 이해한게 맞나요?
@@user-cf6jo5qb7m 거의 다 이해하신것같아요
중요한건 본인의 숫자가 적힌 상자로부터 루프를 시작해야 한다는것이구요
그래야 마지막에 본인의 숫자를 찾으며 루프를 닫게되니까요
@@ChaengLover 엥 왜 굳이 내 숫자부터 시작해야해요? 왜 그래야만 루프가 닫히는거죠? 다른 숫자로 가도 상관 없지 않나요?
결국 죄수는 전부 총살이라는거죠?
좋습니다
왜 각각의 확률은 1/2 고정인가요? 본인이 속한 루프가 50보다 길이가 길 확률은 것보다 낮지 않나요?