100명의 사람이 광장에 모여있습니다. 그 중 몇 명의 얼굴에는 그림이 그려져 있습니다.
그들 각자는 자신의 얼굴은 볼 수 없고 오직 다른 사람의 얼굴만 볼 수 있습니다. 또한 다른 사람에게 그 사람의 얼굴에 그림이 그려져 있는지 아닌지 어떤 방법으로든 알려 줄 수 없습니다.
자신들의 얼굴에 그려진 그림을 지우기 위해 이들이 선택한 방법은 아래와 같습니다.

1. 먼저 광장에 모여 서로의 얼굴을 확인합니다.
2. 집으로 돌아가 자신의 얼굴에 그림이 그려져 있다고 판단되면 얼굴을 씻습니다.
3. 다시 광장에 모여 서로의 얼굴을 확인합니다.
4. 모든 사람의 얼굴에서 그림이 지워질 때까지 위의 과정을 반복합니다.

드디어 모든 사람이 광장에 모이고 서로의 얼굴을 확인 한 후 각자 집으로 돌아갔습니다.
그러나 아무도 얼굴을 씻지 않았습니다.
두 번째로 광장에 모두가 모여서 얼굴을 확인 한 뒤 모두 집으로 돌아갔지만 역시 아무도 얼굴을 씻지 않았습니다.
세 번째 모임 후에도 마찬가지였습니다.
네 번째도 역시 마찬가지...

이렇게 모임이 반복되어 열 한 번째 모임에서 몇 명인가가 얼굴을 씻고 나타났고 더 이상 얼굴에 그림이 그려진 사람은 없었으며 열 두 번째 모임 또한 필요가 없게 되었지요.

그렇다면 열 번째 모임 뒤에 얼굴을 씻은 사람의 숫자는 모두 몇 명일까요?

PS. 얼굴에 그림이 그려진 사람은 반드시 한 명 이상 존재하며, 자신의 얼굴에 그림이 없는데도 얼굴을 씻은 자는 없습니다.


엘리스의 해설 | http://www.designeralice.com

해결 전략 : 거꾸로 생각하기 + 간략화하기 + 규칙 찾기

얼굴에 그림이 그려진 사람의 수를 알고 있다는 전제 하에서(거꾸로 생각하기), 얼굴에 그림이 있는 사람의 수가 1인 경우부터 시작하여(간략화하기), 그림이 있는 사람의 수를 차츰 늘리면서 규칙을 찾아보자.
디자이너엘리스닷컴
편의상 얼굴에 그림이 그려진 사람의 수를 n이라고 하자.

n=1이라면?
첫 날 사람들이 모여 얼굴을 확인한다. 얼굴에 그림이 그려진 사람은 모든 타인의 얼굴에 그림이 없는 것을 보게 된다. 그런데 얼굴에 그림이 있는 사람이 적어도 한 명 존재하므로 자신의 얼굴에 그림이 있음을 알게 된다. 따라서 첫 날 집에 돌아가서 얼굴을 씻는다.

n=2라면?
첫 날 사람을이 모여 얼굴을 확인한다. 얼굴에 그림이 있는 사람은 타인 중 1명의 얼굴에 그림이 있는 것을 보게 된다. 얼굴에 그림이 없는 사람은 타인 중 2명의 얼굴에 그림이 있는 것을 보게 된다. 아직은 자신의 얼굴에 그림이 있을 것이라고 짐작하는 사람은 없다. 왜냐하면 타인의 얼굴에 그림이 있는 것을 모두 보았기 때문이다.
둘째 날 사람들이 모여 얼굴을 확인한다. 얼굴에 그림이 있는 사람 A는 또 다른 얼굴에 그림 있는 사람B가 그림을 지우지 않고 왔음을 보게 된다. A는 B 외에 또 다른 사람의 얼굴에 그림이 있음을 알게 되는데 다른 타인의 얼굴에는 그림이 없으므로 그것이 자신임을 알게 된다. B도 A와 마찬가지로 자신의 얼굴에 그림이 있음을 알게 된다. 따라서 A와 B는 둘째 날 집에 돌아가서 얼굴을 씻는다.

n=3이라면?
첫 날 사람들이 모여 얼굴을 확인한다. 얼굴에 그림이 있는 사람은 타인 중 2명의 얼굴에 그림이 있는 것을 보게 된다. 그리고 얼굴에 그림이 있는 사람이 2명 또는 3명임을 짐작한다. 얼굴에 그림이 없는 사람은 타인 중 3명의 얼굴에 그림이 있는 것을 보게 된다. 이들은 얼굴에 그림이 있는 사람이 3명 또는 4명이라고 짐작한다.
둘째 날 사람들이 모여 얼굴을 확인한다. 첫 날과 마찬가지로 다른 사람들의 얼굴을 확인한다.
셋째 날 사람들이 모여 얼굴을 확인한다. 얼굴에 그림이 있는 사람은 타인 중 2명의 얼굴에 그림이 있는 것을 보고 생각한다 ㅡ 만약 얼굴에 그림이 있는 사람이 2명이라면 이 둘은 그림을 지우고 왔어야 한다, (n=2인 경우 참고) 그러나 2명의 타인은 얼굴의 그림을 지우지 않고 왔기 때문에 2명이 아닌 3명의 얼굴에 그림이 있는 것이다, 자신 외에 얼굴에 그림이 있는 사람은 2명이므로 자신의 얼굴에 그림이 있다. 따라서 이날 얼굴에 그림이 있는 사람은 집에 돌아가서 얼굴을 씻는다.

일반화하면 n=k인 경우에는, k번째 날 사람들이 모여 자신의 얼굴에 그림이 있는지 없는지 알게 된다. (수학적 귀납법을 이용하면 증명된다.) 문제에서 11번째 모임에서 얼굴을 씻고 온 사람이 있다고 했으므로 10번째 모임에서 사람들은 자신의 얼굴에 그림이 있는지의 여부를 알게 된 것이다. 따라서 얼굴에 그림이 있는 사람은 10명이고 이들은 모두 10번째 모임이 끝난 후 집에 돌아가서 얼굴을 씻었다.