| [ QuizWit ] in KIDS 글 쓴 이(By): ilusion (환상) 날 짜 (Date): 1997년06월19일(목) 19시33분54초 KDT 제 목(Title): re^3 MS 연속 스티브에게 언제나 이길수는 없습니다. 당연히 biased binary search를 한다고해도 search 자체가 probabilistic한거니까 어쩔수가 없습니다. 그러나 아까침에 말한대로 어떠한 worst case에서도 4번선택을 하면 숫자 3개뿐이 안남습니다. 당연히 worst case보다는 case들이 다 좋습니다. 결국 평균적으로가면 5번째 선택때 남는 숫자가 평균적으로 2개보다 적다면 평균적으로 승리하는 전략이됩니다. ------ 그리고 biased binary search는 5번째 선택때 스티브가 악날할경우 남는숫자의 갯수를 2개이하로 줄입니다. 평균적으로. ---------- 이걸 이렇게도 생각할수있습니다. 스티브가 악날할경우 스티브가 숨을수있는 숫자의 갯수는 한정되어있습니다. 100개에서 몇십개가 빠집니다. 100 - 몇십개 < 2^6 가 될테니까 직관적으로 승산이 있습니다. 왜냐면 이미 보인바와같이 6번 선택으론 기대치 > 0 이니까. 언제나의 필승전략은 당연히 없지요. 그러나 평균적으로 승리하는 전략은 있습니다. Applied Math Mathematical Statistics Department of Math. Department of Math. and Stat. University of Toronto McGill University 정 무경 : chung@math.toronto.edu |