| [ QuizWit ] in KIDS 글 쓴 이(By): pinkrose (쭈쭈바) 날 짜 (Date): 1999년 6월 23일 수요일 오후 04시 17분 12초 제 목(Title): re: 마이크로 소프트. 벌써 빌게이트의 옵티말 전략도 해답이 나왔었군요. 뭐 그래도 복습하지요. ^^ 종대씨 포스팅이 이해가 잘안되는데, 왜 빌게이트가 100을 고르는전략이 0을 고르는전략보다 옵티말 전략인지 다시한번 설명해주시면 좋겠군요. 바이나리써치가 candidate에겐 가장 좋은 전략일테니, 여기에 대한 방어만 빌게이트가 하면 될것같은데, 그렇다면 1부터 100까지 숫자의 시메트리상 1을 고르나 100을 고르나 똑같쟌아요. (정정: 위의 0은 1로 고쳐주세요.) 이문제 minimax 문제쟌아요. candidate 의 전략은 그냥 단순 옵티마이제이션인데 왜냐면 그냥 min E(X) 를 주는 전략만 고르면 되쟌아요. where E= expectation, X = number of guesses X=1, P(X)= 1/100 X=2, P(X)= 1/100+1/99 처음에 일단은 요런식으로 확률분포가 주어집니다. 이런분포상황에서 min E(X)를 최소화하는 전략을 구하면 되거든요. 즉 이거 바이나리 써치. 바이나리 써치가 정말 min E(X)를 주는지 누구 손쉽게 설명할수있는사람 손들기~ 그런데 빌게이트의 경우는 약간 달라지는데, 그건 왜냐면 max ( min E(X) ) 를 주는 그런 숫자 n을 골라야하쟌아요. 시메트리에 의해 1을 고르나 100을 고르나 당연히 candidate입장에선 똑같쟌아요. 이거 진짜 증명하려면 다음과 같이 하면 되쟌아요. 1,2,3... ,100 이렇게 숫자를 늘려놓는대신에 100,99,98,... ,1 꺼꾸로 인덱싱해놓고 바이나리 써치하는걸로 그렇다면 종대씨 주장대로라면 100을 빌게이트가 골라야하는데 which is originally 1이니까 역시 1도 빌게이트한테는 옵티말 전략이라는 소리쟌아요. 흠, 제가 뭘 잘못이해했거나, 종대씨가 혹시 다른문제 푼거아닐까요? ^^ 혹시 100이란 숫자는 1이란 숫자보다 컴퓨터 메모리를 더잡아먹어서 100찾는거보다 1찾는게 더쉽다는 황당한 풀이는 아닐까 똘을 골똘히 굴려봤지만 여전히 아리송 하군요. 컴퓨터의 귀재들, 이렇게 아름다운 핑크로즈여사가 똘을 굴리며 헤멜때 이때다~ 하고 포스팅을 하셔야합니다. 제발 포스팅좀 해주세요 흑흑흑... "인생은 예측불허. 그리하여 쭈쭈바의 의미를 찾는다" 쭈쭈바의 네딸들에서 "언제 오줌을 쌀건지는 예측불허. 그리하여 난 전봇대를 찾아헤멘다." 너의 쭈쭈바가 하늘을 날게하려면, 쭈쭈바에게 나는법을 가르쳐라. - McGill 수학과 1층 남자화장실에 쓰인 낙서. |