강 건너기 (네 커플) (by Sam Loyd)

Sam Loyd라고, 퍼즐계에서 유명한 아저씨가 만들었다는 문제입니다.

제목 : 네 커플 (원제 : The Four Elopements)

네 쌍의 남녀가 같은 날 야반도주를 하였는데, 강이 가로막고 있습니다.
보트는 하나, 보트에 동시에 탈 수 있는 사람 수는 최대 2명,
여덟 명이 모두 노를 저을 수 있습니다. 남자를 ABCD, 여자를 abcd로 표시합시다.

이쪽 강가를 X, 저 쪽 강가를 Z라 둡니다. 그 사이 섬 Y가 있습니다.
섬 Y에는 몇 사람이라도 머물 수 있습니다.

조건은 크게 두 가지입니다.
첫째, 서로 다른 쌍의 남녀가 한 배를 타지는 못합니다. (예: Ad)
열정이 넘치는 젊은이들이라, 언제 눈이 맞아 배를 탄 채로 도망갈지 모르기 때문~

둘째, 어떤 공간(X, Y, Z)이라도, 남자 파트너 없이 여자 홀로 다른 남자와 함께 있는 것은 허용되지 않습니다.
(예 : Aab. 이 경우 멀리 떨어진 남자 B의 질투심이 불상사를 야기할 수 있음~)
즉, 여자는, 여자 끼리 있거나, 남자 파트너가 함께 하여야 합니다. (예 : abc 또는 AaBb)

문제 : 어떻게 하면 모두가 무사히 강을 건널 수 있을까요? 그리고 그 최소 횟수는 얼마일까요?

 

참고 : Aa가 Z로 가서 a가 X로 돌아오는 것이 허용되느냐? 안됩니다. a가 배에 타고 있을지라도 X에 닿는 순간 a는 공간 X에 다른 남정네와 함께 있는 것으로 간주됩니다. 그래야 보다 어려운 문제가 되겠지요.