PGR21.com
- tvN '더 지니어스' 관련 게시글을 위한 임시 게시판입니다.
- 방송 기간 한정 임시로 운영됩니다. (선거, 올림픽, 월드컵 게시판과 같음)
Date 2014/02/26 19:20:06
Name 마술사
Subject [분석] 진실탐지기 binary search+α 방법
binary search 에 진실탐지기 룰 (상대방이 진실을 말했을때 숫자하나 공개) 을 감안한 방법입니다

예) 내가 원주율을 10자리 까지 알고 있고
       상대방이 모를경우

질문1: 당신의 첫자리 숫자는 원주율 10자리 숫자보다 큰가?
상대가 답을 알경우) binary search와 동일
모를경우) 찍어서 맞출경우) 숫자하나 공개됨
                  찍어서 틀릴경우) binary search와 동일

  질문2: 당신의 둘째자리 숫자는 원주율 9자리 숫자보다 큰가?
위와 동일....

이런식으로 할경우, (상대방이 답을 모른다는 가정하에)1/2확률로 숫자하나가 공개되고 (이때 탐색영역의 6/10 제거), 원래 물었던 답도 알수 있으므로 binary search에 의해 탐색영역이 또 1/2가 됩니다.
즉 참을 말할경우 탐색영역의 4/5가 질문한방에 제거됩니다.

아닐경우 binary search식으로 탐색영역이 1/2로 줄기 때문에, 그냥 binary search보다는 훨씬 빠르게 됩니다. 평균적으로 질문한번에 검색영역의 13/20이 제거됩니다.4개의 숫자가 다 나오면 그다음엔 다시 binary search로 하면, 10번정도의 질문으로 답이 나옵니다.

또한 상대가 답을 알더라도 일반 binary search와 같기 때문에, risk가 거의 없습니다.

제생각엔 이게 제작진이 예상한 필승법이 아닐까 하는데...
여러분의 생각은 어떠신지요?

모바일로 써서 오타나 문단이 이상하게 보일수 있으니 미리 양해바랍니다.

통합규정 1.3 이용안내 인용

"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.
법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
14/02/26 19:35
수정 아이콘
제가 쓴거랑 같네요. 저도 이게 가장 필승법에 가깝다고 생각합니다. 상대에게 페널티를 안기면서 의도한 정보도 가져올 수 있는 방법은 이거밖에 나온게 없는거같은데
14/02/26 20:40
수정 아이콘
근데이러면..

상대도 똑같이 할 수 있지 않나요?

하다못해 원주율을 몰라도 내 주민등록번호 뒷자리 4번째 숫자보다 큰가? 라고 할 수 있지 않나요?
14/02/26 20:51
수정 아이콘
원주율은 보통은 외우겠지만 자연법칙이기도 하고 남휘종쯤 되면 몇자리정도는 앉은자리에서 쓱쓱 작도해서 알아낼수도 있지만 그건 그냥 비대칭 정보잖아요.
14/02/26 21:15
수정 아이콘
그럼 원주율 말고 뭐 상대는 모르고 자신만이 아는 정보를 물으면 되겠죠. 예를들면 서대문구 무슨 동 어느 건물의 우편번호의 몇번째 자리수 이런식으로.. 그럼 결과는 아이템빨로 이상민씨 승리 아닐까 싶은데..
IdoIdoIdoIdo
14/02/27 02:08
수정 아이콘
계산이 잘못됐습니다. 경우의수가 10^4 에서 9^4로 줄어들어 제거율이 50%에 못미칩니다. 따라서 초기 오답을 한두개 말하는건 이론적으론 방어법이지 공격법이 아닙니다.
마술사
14/02/27 09:16
수정 아이콘
오답을 말하더라도, 페널티로인한 숫자공개뿐만아니라 원래 질문에 대한 대답도 들을수 있으므로 binary search보다 나쁠수가 없습니다...
14/02/27 10:32
수정 아이콘
좋은 방법이라고 생각됩니다. 패널티와 바이너리 서치를 같이 이용하는 방법이니..
3.1415926535 89793 23846 26433 83279
보통 3.141952 정도까지는 안다고 보면 그보다 낮은 순서에 값이 있어야 하는데
이번 케이스에 적용해 보면 첫자리가 1이므로
10번째 5보다 작다 이니 다음 3 이 나오는 자리는 15번째 자리입니다.

원주율 소수점 이하 15자리를 알고 있어야 한다는 어려운 문제가 있겠네요. ^^
IdoIdoIdoIdo
14/02/27 11:31
수정 아이콘
오답을 말해도 바이너리 정보를 알게 된다는 생각을 미처 못 했군요!
14/02/27 12:12
수정 아이콘
각자리수를 하나씩 찾는것보다
수 전체를 활용한 것이 낫겠죠.

log와 2진법, mod 같은것들이 생각나는데요.
비밀번호는 log2를 씌우면 12보다 큽니까?
비밀번호를 2진법으로 나타냈을때 1의 자리는 0입니까?
비밀번호 (mod 2)는 1입니까?
등등이 있겠네요.
14/02/27 17:46
수정 아이콘
원주율 필요 없이 숫자 하나 적어서 딜러한테 준 후에 "제가 방금 딜러한테 적어준 숫자보다 큰가요?" 물어보면 될듯.
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
1456 [분석] 예고편에 나오는 출연자별 카드 정리 및 분석 [14] 파란무테4346 14/10/15 4346
1444 [분석] 오현민의 리스트를 보고, 오현민이 시민 리더일 확률을 계산해 보면 [2] SugarRay5606 14/10/10 5606
1438 [분석] 데스매치 때 빛났던 상대 고르기 [1] 마음속의빛3868 14/10/09 3868
1436 [분석] 배심원 메인매치 강용석은 어떻게 했어야했나. [18] 발롱도르4149 14/10/09 4149
1435 [분석] 시민대표, 범죄자 대표 [22] 잭스3868 14/10/09 3868
1433 [분석] 14%의 확률을 의심하지 않은 범죄자들 [9] 엔타이어4224 14/10/09 4224
1430 [분석] 장동민의 리더쉽 [14] 발롱도르6133 14/10/09 6133
1428 [분석] 시민으로써의 최선, 장동민 [10] MoveCrowd5903 14/10/09 5903
1422 [분석] 강용석씨는 죄수의 딜레마를 이용한 것 같습니다. [6] Alan_Baxter5111 14/10/09 5111
1420 [분석] 김경훈은 승패를 알았지만, 강용석은 승무패를 알았다. - 2화 후기 [42] Leeka6331 14/10/09 6331
1419 [분석] 오늘 메인매치. 방송 얼마 안남은 상태에서 간단한 분석. [1] 세이젤2345 14/10/08 2345
1417 [분석] '배심원'게임에서의 시민측 전략 분석. [12] 줄리3318 14/10/08 3318
1409 [분석] 블랙가넷 1화 메인매치에서 만약 김경훈의 배신이 없었다면? [1] 세뚜아3321 14/10/05 3321
1407 [분석] 지니어스3 1화 데스매치 3라운드의 미스터리(스포있음) [6] Exodus4550 14/10/04 4550
1401 [분석] 시즌1~2에서 이어지는 공통적인 요소들. [3] 세이젤4171 14/10/02 4171
1397 [분석] [1화 메인매치분석]배신만 없었어도... [14] _zzz5170 14/10/02 5170
1396 [분석] 데스매치 7라운드 상황 분석 [스포 유] [4] 콩쥐팥쥐3571 14/10/02 3571
1378 [분석] 제작진이 결승전 콰트로에서 바랬던 모습은 이런게 아니었을까. [9] K-DD5465 14/03/02 5465
1375 [분석] 콰트로 게임에서 임요환의 실책 [8] Duvet8108 14/03/01 8108
1372 [분석] 진실탐지기 binary search+α 방법 [10] 마술사6429 14/02/26 6429
1365 [분석] 아까 불건전PGR아이디 님이 쓰신 모순 분석 [5] 장인어른4280 14/02/24 4280
1360 [분석] 진실탐지기 필승 수비법 [2] sonmal4584 14/02/24 4584
1358 [분석] 진실탐지기: 중복이 주는 혼돈의 미학 [1] 마술피리4154 14/02/24 4154
목록 이전 다음
댓글

+ : 최근 6시간내에 달린 댓글
+ : 최근 12시간내에 달린 댓글
맨 위로