해답, 퍼즐] 눈 감고 비교하기. 2

다양한 해답이 나왔는데요,

제가 생각한 정답과 가까운(응칠이) 사람도 있었고,

제 3자를 이용하는 방법(먹는거야?),

전교생 수가 아주 많다면 가능한 방법(MGS) 등이 나왔습니다.

제가 생각한 해답은 아래와 같습니다.

1. 전교생 수 만큼의 컵을 준비합니다. 컵은 모두 동일하게 생겼다고 가정합시다.

2. 컵을 일렬로 세워놓고, 컵 앞에 전교생의 이름표를 하나씩 준비해 놓습니다.

3. A는 노트에 yes나 no를 적어서 그걸 안 보이게 잘 접은 후에, 각각의 컵에 집어 넣습니다.

3-2. yes는 오유 하는 친구의 이름표 뒤의 컵에만, 나머지 컵에는 no를 넣습니다.

4. B도 똑같이 합니다.

5. 컵의 위치를 무작위로 뒤섞습니다.

6. 각 컵을 보면서 yes가 2개 있는 컵이 있다면 YES, 하나도 없다면 NO.

이 방법의 장점은 다음과 같습니다.

(1) 간단합니다. (전교생 수가 적다면) 누구나 할 수 있습니다.

(2) 제3자가 확인 과정을 보고 있어도, 누가 그 친구인지 알아내기 힘듭니다. (먹는거야?, MGS)

+++ shuffling은 눈 깜짝할 새에 일어난다고 가정합시다.. ㅜㅜ

---

하지만 이 방법에는 문제가 하나 있습니다.

만약 상대방이 흑심을 품고 알고리즘에 따라주지 않으면, 제 친구를 알 가능성이 있습니다.

예를 들어서, 제 방법에서는 상대방이 모두 "yes"를 집어넣으면?

아니면, 응칠이님 방법에서 상대방이 종이에 모두 구멍을 뚫어놓으면?

그러니까,

Q2) 상대방이 협조하지 않을 때, 누가 내 친구인지 알지 못하도록 알고리즘을 보완하시오.

(전교생 수는 충분히 작아서 해싱이 뚫릴 가능성이 있다고 하자.)