목사와 식인종 문제

일반화

김진홍

3:3 용 규칙

Step 1: 식인종을 모두 옮겨라.

보낼때: 식인종 2, 돌아올때: 식인종 1

만약, 목사와 식인종이 모두 옮겨졌으면 종료.

만약, 식인종이 모두 옮겨지면 Step 2로.

Step 2: 목사를 모두 옮겨라.

보낼때: 목사 2, 돌아올때: 목사 1 식인종 1, 혹은 식인종 1

만약, 목사가 모두 옮겨졌으면 Step 1로.

배의 수용인원 수가 2일때, 일반화된 규칙:

1. 건너갈때: (1) 같은종 둘 선택

(2) 다른종 하나씩 선택

2. 돌아올때: (1) 하나만 선택 (같은것이 둘이 돌아가면 안됨)

(2) 다른종 하나씩 선택 (비율을 맞추기 위해)

** 반드시 목사가 먼저 시도한다.

** 매번 건너가도 양 강변의 목사가 무사한지를 판단함.

결과:

배의 수용인원 한계가 2일때, 목사와 식인종의 수가 3,3일때를 제외하고

나머지는 모두 목사수+1:식인종수 의 비율이어야 한다.