퍼레이드 – 1
퍼레이드는 경로상의 모든 거리를 정확히 한 번씩 방문하기를 원합니다. 이 두 예시에서 첫 번째는 성공적인 퍼레이드 경로이고, 두 번째는 그렇지 않습니다(한 거리가 빠져 있습니다).
도전 과제
각 거리 배치에 대해, 모든 거리를 정확히 한 번씩 방문하는 퍼레이드 경로를 찾거나, 그것이 불가능하다고 판단하세요. 퍼레이드가 가능한 거리 배치 중에서, 퍼레이드의 시작점과 끝점이 같은 배치는 어떤 것일까요? 결과에서 어떤 패턴을 찾을 수 있나요?
노트
도전 과제
핵심은 거리 지도에 표시하기 위해 퍼레이드의 시작과 끝 지점을 기록해 두는 것입니다. 퍼레이드는 시작과 끝이 어디든 될 수 있지만, 어떤 퍼레이드는 특정 장소에서 시작하거나 끝나야 합니다.
여러 사례를 살펴본 결과 다음과 같은 결론에 도달했습니다. 어린아이들에게 이러한 것들을 증명하는 것은 중요하지 않습니다.
결과 1: 한 모퉁이로 들어오는 도로의 수가 홀수이면, 행렬은 반드시 그곳에서 시작하거나 끝나야 합니다.
이유는 간단합니다. 행렬이 모퉁이를 돌 때마다 그 모퉁이로 향하는 거리의 수가 짝수가 됩니다. 따라서 거리의 수가 홀수인 모퉁이는 행렬의 시작점 또는 종착점이 되어야 합니다.
결과 2: 만약 홀수 개의 도로가 들어오는 모퉁이가 두 개 이상 있다면, 이 지도에서는 퍼레이드가 진행될 수 없습니다.
결과 3: 만약 거리의 개수가 홀수인 모퉁이가 정확히 두 개 있다면, 모든 행렬은 반드시 그 중 한 곳에서 시작해서 다른 한 곳에서 끝나야 합니다. 특히, 시작점과 끝점이 같은 행렬은 불가능합니다.
결과 4: 만약 거리의 개수가 홀수인 모퉁이가 없다면, 행렬은 어디에서든 시작할 수 있으며, 시작점과 끝점은 반드시 같아야 합니다.