한 번에 안 되면
몇 번이면 될까

최소 획수 = 홀수점 ÷ 2

선이 모두 이어진 도형에서 홀수점이 2k개(k는 1 이상)라면, 펜을 떼지 않고 그리는 덩어리(획)가 최소 k개 필요하고 k획이면 충분합니다.

왜 그런가

한 획은 시작과 끝, 두 군데에서만 홀수점을 "처리"할 수 있습니다. 그래서 홀수점 2k개를 처리하려면 최소 k획이 필요합니다. 반대로, 홀수점 두 개씩 짝지어 그 사이에 가상의 선을 하나씩 더하면 모든 점이 짝수가 되어 한붓그리기가 되고, 그 가상의 선 자리에서 펜을 뗀다고 보면 k획이 됩니다.

떼지 않고 되밟기

펜을 뗄 수 없고 대신 이미 그은 선을 다시 지나도 된다면, 문제는 "가장 적게 되밟는 길"로 바뀝니다. 이것을 중국 우편배달부 문제라고 합니다. 중국 수학자 관메이구(管梅谷)가 1960년에 연구했습니다.

1. 홀수점을 모두 찾습니다.
2. 홀수점을 두 개씩 짝짓습니다. 짝끼리의 최단 거리 합이 가장 작게 되도록 짝을 고릅니다.
3. 짝 사이의 최단 경로를 "한 번 더 지나갈 선"으로 정합니다.
4. 그 선들을 두 겹으로 보면 모든 점이 짝수가 되어, 출발점으로 돌아오는 한붓그리기가 됩니다.

홀수점이 2개뿐이고 출발점으로 돌아올 필요가 없다면, 되밟을 필요 없이 한 홀수점에서 다른 홀수점으로 한붓그리기를 하면 됩니다.

생활 속 경로

모든 길을 최소 한 번 지나야 하는 일이 같은 구조입니다. 동네 골목을 빠짐없이 도는 전단 배포, 공원 산책로를 전부 걸어 보는 코스, 아파트 단지 도로를 한 바퀴씩 쓰는 순서 등이 그렇습니다. 지도에 교차로마다 점을 찍고 홀수점을 세어 보면, 되돌아오는 길을 얼마나 줄일 수 있는지 감이 옵니다.

앱에서

1

못 푸는 판은 나오지 않는다

원트레일은 판을 기기 안에서 만든 뒤 화면에 내보내기 전에 풀리는지 확인합니다. 그래서 모든 판은 홀수점이 0개 또는 2개인 한붓그리기 판입니다. "이건 안 되는 판 아닐까" 싶을 때는 판을 의심하기보다 시작점과 순서를 다시 보세요.

자주 묻는 질문

함께 보면 좋은 가이드

• 쾨니히스베르크 다리 문제와 오늘날의 다리땅 4곳 · 차수 5·3·3·3 · 지금은 5개 다리로 한붓 가능
• 한붓그리기 가능한지 판별하는 법과 시작점 찾기홀수점 0개면 어디서든 · 2개면 그 점에서 시작 · 4개 이상은 불가
• 한붓그리기 문제를 점 종이로 직접 만드는 법먼저 한 번에 그리고 나중에 숨기기 · 난이도 조절 · 함정 문제
• 원트레일 가이드 전체10개 글 모아 보기