문제의 배경
쾨니히스베르크는 프레겔 강이 도시를 가르며 흐르고, 강 가운데 크네이프호프 섬이 있었습니다. 강 양쪽 땅과 섬, 그리고 강이 갈라진 사이의 땅까지 모두 네 구역이 7개 다리로 이어져 있었습니다. 오일러는 이 문제를 1735년 상트페테르부르크 학술원에 발표했고, 논문은 1741년에 출판되었습니다.
도시는 지금 러시아 칼리닌그라드입니다.
왜 불가능했나
오일러는 땅을 점으로, 다리를 선으로 바꿨습니다. 그러면 각 땅에 닿은 다리 수가 그 점의 차수가 됩니다.
| 땅 | 닿은 다리 수 | 홀짝 |
|---|---|---|
| 크네이프호프 섬 | 5 | 홀수 |
| 나머지 세 구역 | 각 3 | 홀수 |
홀수점이 4개입니다. 한붓그리기는 홀수점이 0개 또는 2개일 때만 가능하므로(홀수점 규칙), 어디서 출발해도 7개 다리를 한 번씩만 건너는 산책은 없습니다.
지금의 다리
제2차 세계대전 폭격으로 다리 2개가 파괴되었고, 이후 2개는 도로 건설로 철거되었습니다. 지금 원래 자리에 있는 다리는 5개입니다(그중 오일러 시대의 다리는 2개). 이렇게 바뀐 구성에서는 두 구역의 차수가 2, 나머지 두 구역이 3이 되어 홀수점이 2개입니다. 즉 차수 3인 구역 하나에서 출발하면 지금 있는 다리를 한 번씩 건너 다른 차수 3 구역에서 끝나는 산책이 가능합니다. 출발점으로 돌아오는 것은 여전히 안 됩니다.
출처: Wikipedia, Seven Bridges of Königsberg (다리 구성과 연도). 현지 다리 이용 여부는 방문 전에 따로 확인하세요.
그림으로 바꾸는 법
- 땅 덩어리마다 점 하나를 찍습니다. 땅의 크기와 모양은 상관없습니다.
- 다리마다 해당하는 두 점 사이에 선을 긋습니다. 같은 두 땅 사이 다리가 2개면 선도 2개입니다.
- 점마다 선 수를 세어 홀수점 개수를 봅니다.
우리 동네 하천과 다리, 공원 산책로로도 똑같이 해 볼 수 있습니다. 아이와 함께라면 한붓그리기 수학 놀이도 참고하세요.
앱에서
도감의 쾨니히스베르크의 다리
원트레일 도감에는 손으로 설계하고 풀리는지 검증한 고전 도형이 모여 있고, 그중 하나가 쾨니히스베르크의 다리입니다. 도감 도형은 모두 홀수점이 0개 또는 2개인 풀리는 판이라, 원래의 7개 다리 그대로가 아니라 선 5개, 홀수점 2개짜리 그림입니다. 차수 구성(3·3·2·2)은 오늘날의 5개 다리 구성과 같습니다.
자주 묻는 질문
다리 하나만 더 놓으면 원래 문제도 풀리나요?
네. 홀수점 4개 중 두 땅 사이에 다리 하나를 추가하면 그 둘이 짝수가 되어 홀수점이 2개로 줄고, 한 번씩 건너는 산책이 가능해집니다. 출발점으로 돌아오려면 다리 2개를 더 놓아 홀수점을 0개로 만들어야 합니다.
오일러가 처음 한붓그리기를 생각한 사람인가요?
한붓그리기 놀이 자체는 더 오래되었지만, 가능 조건을 수학적으로 따진 출발점으로 오일러의 이 논문이 꼽힙니다.
원트레일: 한붓그리기 퍼즐
회원가입 없이, 완전 오프라인. 모든 판이 풀리는지 확인된 뒤 나오는 안드로이드 무료 퍼즐 게임입니다.