멘사 회원도 풀지 못한다는 문제

이미지를 누르면 영상으로 이동합니다

펜이 이동하는 것 처럼 모든 점을 중복하지 않고 지나는 경로를 해밀턴 경로라고 합니다.

문제를 풀기 위해 점에서 다른 점으로 이동 가능한 상하좌우선을 모두 표시하면

꼭짓점이 18개, 변이 23개인 그래프가 됩니다.

 

해밀턴 경로를 간단하게 표현하면 꼭짓점 개수보다 하나 적은 변이 필요하고 각 점을 잇는 선의 개수는 2개면 충분합니다.

 

해밀턴 경로가 존재한다고 가정했을 때 꼭짓점이 18개이므로 변이 17개 필요한데 서로 이웃하지 않는 점들을 체크한 후(주황색) 필요한 선분 2개를 제외하면( (4-2)*1+(3-2)*5+(2-2)*2=7, 23(기존 변의 개수)-7(필요없는 선의 개수)=16) 이 그래프에서 그을 수 있는 선은 16개로 모순이 생깁니다. 따라서 해밀턴 경로가 존재한다고 할 수 없습니다.