메모
면접 문제
6.3 도미노
- 8x8 크기의 체스판이 있는데, 대각선 반대 방향 끝에 있는 셀(cell) 두 개가 떨어져 나갔다. 하나의 도미노로 정확히 두 개의 정사각형을 덮을 수 있을 때, 31개의 도미노로 보드 전체를 덮을 수 있겠는가? 여러분의 답이 옳다는 것을 증명하라(예를 들거나, 왜 불가능한지를 보이면 된다).
6.4 삼각형 위의 개미
- 개미 세 마리가 삼각형의 각 꼭짓점에 있다. 개미 세 마리가 삼각형 모서리를 따라 걷기 시작했을 때, 두 마리 혹은 세 마리 전부가 충돌할 확률은 얼마인가? 각 개미는 자신이 움직일 방향을 임의로 선택할 수 있는데, 같은 확률로 두 방향 중 하나를 선택한다. 또한 그들은 같은 속도로 걷는다. 이 문제를 확장해서 n개의 개미가 n각형 위에 있을 때 그들이 충돌할 확률을 구하라
6.5 물병
- 5리터짜리 물병과 3리터짜리 물병이 있다. 물은 무제한으로 주어지지만 계량컵은 주어지지 않는다. 이 물병 두 개를 사용해서 정확히 4리터의 물을 계량하려면 어떻게 해야 할까? 물병의 형태가 좀 괴상해서, 물을 정확히 ‘절반만’ 담는 것 따위는 불가능하다.
6.6 푸른 눈동자의 섬
- 어떤 섬에 이상한 명령서를 든 방문자가 찾아왔다. 이 섬에 사는 사람들 중에서 눈동자가 푸른 사람들은 매일 저녁 8시에 출발하는 비행기를 타고 섬을 떠나야 한다. 사람들은 남의 눈동자 색은 볼 수 있지만 자신의 눈동자 색은 볼 수 없다. 또한 다른 사람의 눈동자 색을 발설해서는 안 된다. 그들은 적어도 한 명의 눈동자 색이 푸르다는 사실은 알지만, 정확히 몇 명인지는 모른다. 눈동자가 푸른 사람을 모두 떠나보내는 데 최소 며칠이 필요하겠는가?
6.7 대재앙
- 대재앙 이후에 여왕은 출산율 때문에 근심이 이만저만이 아니다. 그래서 그녀는 모든 가족은 여자 아이 하나를 낳거나 어마어마한 벌금을 내야한다는 법령을 만들어 발표했다. 만약 모든 가족이 이 정책을 따른다면(즉, 여자 아이 한 명을 낳을 때까지 아이를 계속 낳는다면) 다음 세대의 남녀 비율은 어떻게 되겠는가? 남자 혹은 여자를 임신할 확률은 같다고 가정한다.
댓글