모자 9 (K색 N개)

거 참...이런 문제에 답이 있다니...아래 '9개의 모자'의 업그레이드판인 바, 훨 어렵습니다.

 

왕이 생일을 맞아 9명의 죄수들을 풀어주려고 모았습니다.
아래 문제를 맞추면 자유입니다. 왕이 규칙을 말합니다.

"이제부터 너희 9명이 일렬종대로 앞을 보고 선다.

앞에서부터 번호를 붙인다고 할 때, 맨 뒤 9번은 앞의 8명을 다 볼 수 있다.
그 다음 8번은 앞의 7명을 다 볼 수 있지. (중간 생략) 2번은 1번만 보이고 1번은 보이는 것이 없다.

9명의 눈을 가리고 모자를 씌울 것이다.
모자는 검정, 빨강, 파랑, 하양 네 가지 종류이며
전체 9개 중 각 모자가 몇 개인지는 알려주지 않는다.
즉, 무수히 많은 검정, 빨강, 파랑, 하양 모자 중 9개를 내키는대로 골라 씌운다.

그리고 나서 모두의 눈가리개를 벗기면
맨 뒤 9번부터 8번, 7번,...,1번 순서대로 자기가 쓰고 있는 모자 색을 맞추어야 한다.
9번은 틀려도 좋다. 글치만 8번 부터 1번 까지 8명은 정확히 자신의 모자 색을 맞춰야 한다.

이제 너희는 작전 회의를 해도 좋다. 준비가 되면 줄을 서라."

문제 : 어떤 전략을 짜서 행하면 위 규칙을 만족시킬 수 있을까요?

덧글 : 9명 모두 논리적으로 사고하고 듣고말하기를 합니다. 장님은 없습니다.

         9명 모두 자기 차례에서 "검정", "빨강", "파랑", "하양" 중 한 단어만 말할 수 있습니다.

 

(N명의 죄수가 K가지 색깔의 모자를 쓰는 경우 마지막 죄수를 제외한 N-1명의 죄수가 정확히 자기 모자 색을 맞출 방법이 있습니다. 이 문제는 N=9, K=4인 것이지요. 그 전략으로 연결되는 통찰을 찾아보세요. )