안녕하세요.
각종 정보를 드리고 있는 쀼웅입니다.
이번에는 어떤 정보를 드릴지 고민하다가
구글입사시험 수학 창의력 문제를 결정해봤어요.
다들 궁금하실 텐데 거두절미하고
본론으로 들어가도록 하겠습니다. Let's go!!
이번에 알려드릴 구글입사시험 수학 창의력 문제는
꽤 유명한 문제 중 하나라고 할 수 있습니다.
이미 관련해서 여러 가지 문제들이 나와 있던데
와전된 것이 있어서 오리지널 문제를 알려드릴게요.
그 문제는 바로
"당신은 해적선 선장인데 금괴를 발견했습니다.
당신의 금 배분 방안을 놓고
해적 절반(50%) 이상이 지지하지 않을 경우,
가장 높은 계급의 해적이 죽임을 당하고
그다음 높은 계급의 해적이 배분 방안을 제안합니다.
참고로 당신(해적선 선장)도 투표에 참여합니다.
이 과정은 배분 방안이 채택될 때까지 반복합니다."
또한, 모든 해적이 완벽하게
이성적(perfectly rational)이라고 가정하되,
모든 해적은 :
1순위로 생존을 원합니다.
2순위로 금괴를 가지고 싶어 합니다.
-이는 금괴보다 생존이 우선이라는 뜻입니다.
3순위로 해적들은 다른 사항이 동등할 때
(if given a choice between otherwise equal outcomes)
해적선의 해적 수가 적기를 희망합니다.
자 그럼 문제를 풀어볼까요?
동적 프로그래밍(Dynamic Programming)과
게임이론을 섞어서 풀이가 가능합니다.
쉽게 설명을 드리면
금괴가 100개 있다고 가정을 합니다.
게다가 당신은 해적선 선장이므로 No.1이죠.
여기서 숫자가 높아질수록 순서도 높다고 가정을 해봅니다.
# 해적이 총 2명이라면 (n = 2)
해적선 선장이 자신에게 투표를 하면
50% 이상이므로 금괴를 다 가지면 됩니다.
# 해적이 총 3명이라면 (n = 3)
해적3(해적선 선장)은 자신의 방안이 채택되지 않는다면
해적1은 아무것도 가질 수 없다는 것을 알죠.
그러나 해적1에게 금괴를 한 개도 주지 않는다면
해적1은 해적3의 방안에 투표하지 않을 것이고,
해적3은 죽게 됩니다.
그렇기 때문에 해적3은 해적1에게 금괴 1개를 주는 조건으로
해적1과 해적3(선장)의 투표를 받아 살아남을 수 있습니다.
이때 해적 3은 99개의 금괴를 가집니다.
# 해적이 총 4명이라면 (n = 4)
해적4는(선장) 자신의 방안이 채택되지 않는다면,
해적2는 아무것도 못 가지게 될 것을 알고 있습니다.
그렇기 때문에 해적2는 금괴 1개로 만족을 하죠.
이때 해적4는 금괴 99개를 가질 수 있습니다.
투표는 해적2, 해적4의 표를 받아 50%가 됩니다.
# 해적이 총 5명이라면 (n = 5)
해적5는(선장) 자신의 방안이 채택되지 않을 경우,
해적1과 해적3 모두 아무것도 못 가지게 될 것을 알고 있습니다.
그렇기 때문에 해적1과 해적3은
금괴 1개씩으로 만족할 수 있을 것입니다.
이때 해적5는 98개의 금괴를 가질 수 있죠.
투표는 해적 1, 3, 5에 의해 총 60%를 받습니다.
이와 같은 방법으로 풀이를 한다면 정답은 다음과 같습니다.
* 2n+1명이라면
해적 선장은 해적 1, 3,..., 2n-1에게 금괴 1개씩만 주고,
자신이 나머지를 모두 가진다면 살 수 있습니다.
* 2n 명이라면
해적 선장은 해적 2, 4,...,2n에게 금괴 1개씩만 주고,
자신은 나머지를 모두 가지면서 살 수 있습니다.
* 특이한 경우인 n=2라면
자신은 다 가지게 됩니다.
최대한 쉽게 풀이를 해드렸는데 이해하셨는지 모르겠네요.
기회가 된다면 다음 번에는
또 다른 구글 문제를 가지고 오겠습니다~!!
'정보공유 > 기타' 카테고리의 다른 글
아스파탐 특징으로 본 구조와 부작용 (0) | 2017.03.22 |
---|---|
MSG 진실을 파헤치며 본 뜻과 약자 (4) | 2017.03.21 |
얼굴 여드름없애는법 이거면 충분해요 (0) | 2017.03.21 |
책읽는 남자 쀼웅의 오늘의 소설책 추천 (0) | 2017.03.17 |
봄맞이 쉽게 읽을 수 있는 소설책 추천 (0) | 2017.03.16 |