옛날 어느 먼 나라에 술을 매우 즐겨 마시는 왕이 살고 있었다.
독이든 단지의 술을 아주 조금만 맛보아도 술을 맛 본 사람이 자고 일어난 다음날 죽는다.
왕은 독이든 술 단지를 반드시 내일까지 찾아내라고 실력있는 책략가인 당신에게 명하였다.
당신은 투옥된 죄수들을 다음날 살아 남으면 석방을 시켜주는 조건으로 실험에 동원 할 수 있다.
될 수 있으면 최소한의 죄수들을 동원하고자 한다.
풀이1 -이진법식 풀이-
128개의 술 단지가 있다. 이 128개의 술 단지들에 0~127의 번호를 붙이자.
즉 0~127번중 한 번호를 찾아 내라는 문제이다.
이 문제에서 죄수의 선택지는 마시다 안마시다. 이 두 가지 뿐이다.
또한 결과도 죽는다 안죽는다 이 두가지 뿐이다.
즉 1과 0 두 가지 숫자만으로 표현이 가능하며 자연스레 이진법 문제가 된다.
0~127은 0000000 ~ 1111111로 표기 할 수 있다.
세어보니 7자리 숫자가 나온다. 즉 7명이면 마시다 안마시다로 0~127번의 술 단지 번호를 표현 할 수 있다는 뜻이다.
고로 최소 동원해야 하는 죄수의 숫자는 7명이다.
0번 술단지는 0000000 즉 아무 죄수에게도 먹이지 않고
1번 술단지는 0000001 즉 7번째 죄수에게만 먹이고
75번 술단지는 1001011 즉 첫번째,네번째,여섯번째,일곱번째 죄수에게만 먹이고
127번 술단지는 1111111 즉 모든 죄수에게 먹이는 것이다.
그리고 다음날
2번 죄수만 죽었을 경우 0100000 즉 32번 술 단지에 독이 들어 있다는 뜻이고
모든 죄수가 죽었을 경우 1111111 127번 술 단지에 독이 들어 있다는 뜻이다.
아무도 안 죽었을 경우 0000000 0번 술 단지에 독이 들어 있는 것이다.
풀이2 -난 이진법같은거 모르겠다식 풀이-
한 개의 술단지를 아무도 안먹었을때 아무도 죽지 않으면 그 술 단지는 독이 있는 술 단지이니 일단 거저 1개를 얻는다.
파란색이 술 단지이고 원이 사람이라고 치자.
1명의 사람은 1+1개의 술 단지를 판독 할 수 있다.
2명이 되면 3+1개의 술 단지를 판독 할 수 있다.
3명이 되면 7+1개의 술 단지를 판독 할 수 있다.
여기서 규칙을 알 수 있다.
2명에서 3명이 될 때를 보면 원 두개를 새로운 원 하나가 양분 시키면서
1,2,3이 4,5,6으로 두배가 된다. 그리고 새로운 원 자신의 고유의 숫자(7) 한 개가 추가되고
마지막으로 거저 얻는 술 단지 한 개가 추가된다. 즉 *2+1에 (+1)이 된다.
즉 현 단계에서 판독 할 수 있는 술 단지의 개수는 전 단계의 개수 곱하기 2 더하기 1이다.
써보자
1: 1 (+1=2)
2: 1*2+1 = 3 (+1 = 4)
3: 3*2+1 = 7 (+1 = 8)
4: 7*2+1 = 15 (+1 = 16)
5: 15*2+1 = 31 (+1 = 32)
6: 31*2+2 = 63 (+1 = 64)
7: 63*2+2 = 127 (+1 = 128)
사실 3까지만 써보더라도 2의 제곱 개수를 구하는 문제라는 것을 알 수 있다.
결국 7명이면 128개의 술 단지를 판독 할 수 있다는 답이 된다.
