자에 눈금 다섯 개만 표시할 수 있다면, 길이 1부터 10까지 빠짐없이 잴 수 있을까요? 여기서 눈금은 서로 다른 정수 위치에 찍어요. 한 길이를 잰다는 것은 표시된 두 눈금 사이의 거리를 한 번에 읽는다는 뜻이에요. 길이 1을 여러 번 이어 붙이거나, 이미 잰 두 길이를 더하고 빼는 방식은 허용하지 않아요.
다섯 눈금은 양끝 표지를 포함한 전체 개수예요. 길이의 단위는 일정하고 측정 오차는 없는 자체 수학 모형이에요. 매번 어느 두 눈금을 쓸지는 자유이며, 서로 다른 눈금 쌍에서 같은 길이가 나와도 괜찮아요. 목표는 1부터 어떤 양의 정수 N까지의 모든 길이를 직접 잴 수 있게 만드는 거예요. 가능한 가장 큰 N을 찾아볼까요?
우선 두 눈금을 고르는 방법을 세어요. 왼쪽에서 오른쪽으로 재든 반대로 재든 같은 두 눈금의 거리이므로 순서 있는 선택으로 두 번 세지 않아요. 제공 교재의 조합은 이런 순서 없는 선택에 대응해요.
따라서 길이 후보는 많아야 10가지이고, N은 10보다 클 수 없어요. 하지만 쌍이 열 개 있다는 말은 열 개의 원하는 길이를 모두 만들 수 있다는 뜻일까요? 눈금을 0,1,2,3,4에 찍으면 열 쌍이 있어도 거리는 1,2,3,4뿐이에요. 서로 다른 쌍이 같은 거리를 만들기 때문이에요.
그렇다면 간격을 불규칙하게 바꿔 1부터 10까지를 모두 만들면 되지 않을까요? 만약 성공했다면 열 쌍의 거리는 정확히 1,2,…,10이어야 해요. 각 길이에는 적어도 한 쌍이 필요하고 쌍도 열 개뿐이므로, 같은 거리를 두 번 만들거나 10보다 큰 거리를 만들 여유가 없어요. 이때 모든 쌍의 거리 합은 55입니다.
그런데 다섯 정수 눈금에서는 그 합이 항상 짝수예요. 눈금 위치를 작은 것부터 x₀,x₁,x₂,x₃,x₄라고 쓸게요. 모든 쌍의 거리는 오른쪽 위치에서 왼쪽 위치를 뺀 값이에요. 같은 눈금이 이 전체 합에 몇 번 더해지고 몇 번 빠지는지 세어요.
가장 왼쪽 x₀는 다른 네 눈금과 짝을 이루며 네 번 빠져요. x₁은 왼쪽 눈금과의 거리에서 한 번 더해지고, 오른쪽 세 눈금과의 거리에서 세 번 빠져요. 가운데 x₂는 두 번 더해지고 두 번 빠져 사라져요. x₃은 세 번 더해지고 한 번 빠지며, 가장 오른쪽 x₄는 네 번 더해져요.
각 위치가 정수이고 계수가 모두 짝수이므로 이 합은 짝수예요. 필요한 합 55는 홀수여서 같아질 수 없어요. 특정 배치 몇 개가 실패한 이유가 아니라, 어떤 다섯 정수 눈금을 고르더라도 1부터 10까지를 모두 담을 수 없다는 증명이에요. 눈금을 옮기거나 간격을 늘려도 이 홀짝 조건을 피하지 못해요.
이제 1부터 9까지는 가능한지 볼까요? 눈금을 0,1,4,7,9에 표시하면 돼요. 모든 열 쌍을 빠짐없이 확인하면 다음 표를 얻어요.
| 왼쪽 눈금 | 오른쪽에서 고르는 눈금 | 나오는 거리 |
|---|---|---|
| 0 | 1, 4, 7, 9 | 1, 4, 7, 9 |
| 1 | 4, 7, 9 | 3, 6, 8 |
| 4 | 7, 9 | 3, 5 |
| 7 | 9 | 2 |
거리들을 크기순으로 적으면 1,2,3,3,4,5,6,7,8,9입니다. 길이 3은 두 번 나오지만 문제에서 반복을 허용했으므로 괜찮아요. 서로 다른 길이는 정확히 1부터 9까지이며 어느 길이도 빠지지 않아요. 10 이상은 불가능하고 9는 실제 달성했으므로 최대 N은 9입니다. 이 답이 최대 배치를 전부 분류했다는 뜻은 아니에요.
착안한 골롬 자의 규칙은 모든 눈금 쌍의 거리가 서로 달라야 해요. 지금 구성은 거리 3이 반복되어 그 규칙을 만족하지 않아요. 이번에는 반복을 허용하는 대신 정수 길이의 연속 구간을 모두 담도록 조건을 바꿨어요. 원문에서 정의를 읽은 뒤에 두 문제의 목표를 같은 것으로 취급하지 않는 것이 필요해요.
먼저 ‘쌍의 개수’를 적고, 이어 ‘원하는 모든 길이가 실제로 나오는 배치’를 찾아 봐요. 10이라는 상한만 쓰면 가능성이 남고, 9를 만드는 예만 쓰면 더 좋은 배치의 가능성이 남아요. 전체 합의 홀짝으로 10을 막고 표로 9를 달성해야 최대라는 결론까지 얻어요.
착안: UNSW의 CSPLib, Golomb rulers, Beck·Bogart·Pham, Enumeration of Golomb Rulers and Acyclic Orientations of Mixed Graphs, 1–2쪽. 정수 눈금과 쌍별 차의 정의에서 착안해 조건·문항·다섯 눈금 구성·불가능성과 달성 증명을 자체 작성했어요. 원문 그림이나 측정 실험을 옮긴 글이 아니에요.