전자2012. 2. 9. 18:24

Google에서 입사 문제로 냈다고 소문이 돌고 있는 문제이다.


문제를 푸는데 있어서 직접적으로 패리티 비트와 관련 되어 있다고는 할 수 없지만,

어느정도 맞아 들어가는 것 같아 정리 해본다.


문제는 다음과 같았다.



 키가 모두 다른 100명의 사나이가 있는데, 이들을 키 순서대로 세운 뒤(맨 앞에 제일 작은 사나이),

 다음과 같이 발표를 합니다.


 "이제 당신들에게 흰 모자와 검은 모자 도합 100개를 분배하여 한 사람 당 하나씩  무작위로 

  씌울 것이다. 그리고 뒤(제일 키가 큰 사람)에서부터 한 사람씩 자신이 쓴 모자의 색이 무엇인지 

  질문을 받게 될 것이다. 모자는 위에서 내려오기 때문에 당사자는 자신의 모자색을 알 수 없다. 

  그래도 맞춰야 한다.  맞추지 못하면 탈락할 것이다.

  대신, 여러분은 모자를 쓰기 전에 한번 모두 모여 토의를 할 시간을 얻는다.

  이 토의 시간 동안 최대한 많은 인원이 살아 남을 수 있는 방법을 고안하라.

  단, 일단 모자를 쓰고 질문을 받은 이후에는 '검정색', '흰색'이라는 두 단어 이외에는 

  다른 말을 할 수가 없다는 점에 유의하고 신중하게 답하도록. 줄을 서 있는 상황에서는 상호 간에 

  아무런 대화도 할 수 없으니 토의 때 열심히 이야기하길 바란다."


  그래서 이 사나이들은 모두 모여서 열심히 토의를 했습니다. 그리고 다시 키 순서대로 

  줄을 좌악 선 뒤에 모자가 위에서 내려왔고, 맨 뒤의 제일 키가 큰 사람부터 한 명씩 

  자신의 모자 색을 이야기했습니다. 그리고 99명의 사나이가 시험에 합격했습니다. 

  한번 더 시험을 치뤘을 때에는 100명이 모두 합격하기도 했습니다. 

  아무튼 100명 모두가 합 격하거나 한 사람을 제외하고는 모두 합격할 수 있는 방법을 

  고안해 낸 것입니다. 과연 이들이 고안한 그 방법이란 과연 무엇일까요?


  추가 설명 조건 - 키 순서대로 서 있으므로, 나는 나보다 키가 작은 사람들의 모자 색을 

                         모두 알 수 있습니다. 100명이 좀 많은 숫자이긴 하지만, 제일 키가 큰 사나이는

                         제일 키가 작은 사나이의 모자 색도 알 수 있을 만큼 이 사나이들의 눈이 모두

                         좋다는 점을 전제로 합니다.


출처 : http://kldp.org/node/81176


여기서 패리티 비트를 적용 시켜보면 제일 뒤의 키가 큰 사람이 패리티 비트가 된다고 생각했다.

가장 키가 큰 사람은 자신의 앞에 보이는 모자 중 검은색의 모자 수를 세어 개수가 홀수 이면 "검은색"

이라고 말하고 짝수이면 "흰색" 이라고 말을 한다고 모든 사람이 토의를 했다고 가정을 한다.


여기서 검은색을 1로 흰색을 0으로 두었을 때, 검은색(1)의 개수가 홀수 일때 검은색(1) 이라고

말한다면, 가장 키가 큰 사람은 짝수 패리티가 되고, 검은색(1)의 개수가 짝수 일때 검은색(1) 

이라고 말한다면, 홀수 패리티가 된다고 생각했다. 


99번째 사람은 100번째 사람의 말을 듣고 자신의 앞에 보이는 검은색 모자의 수를 센다.

만약 100번째 사람이 검은색 이라고 말했다면 검은색 모자의 수가 홀수개라는 말인데,

만약 자신의 앞에 보이는 검은색 모자의 수가 홀수개이면 자신의 모자는 흰색이 되므로

흰색이라고 말한다. 마찬가지로 98번째 사람은 100번째 사람이 검은색 모자의 수가 홀수개라는 

것을 알렸고, 99번째 사람이 자신의 모자색이 흰색이라고 말했으므로 98번째 사람 앞에 보이는 

검은 모자의 개수가 그대로 홀수개 이면 자신의 모자는 흰색이고 짝수개 이면 자신의 모자가 

검은색인 것이다.


이런식으로 한다면 맨뒤의 사람이 자신의 모자색깔을 맞출확률은 50%이며

최대 100명, 최소 99명은 자신의 모자 색깔을 맞출 수 있을 것이다.


직접 연관되지 않은 것도 같지만, 마지막 사람이 패리티 비트가 될 수 있다는 사실에서 

연관을 지어보았다.

Posted by 콩알은

댓글을 달아 주세요