잰 눈금 쌍이 지워진 거리 카드 열다섯 장이 있어요. 거리 중복이 없으면 눈금도 하나로 정해질까요? 가능한 여섯 눈금 배치를 모두 찾아볼까요?
왼쪽 끝은0, 오른쪽 끝은17인 직선에 서로 다른 여섯 실수 위치를 놓아요. 단위는 같고 오차는 없어요. 두 점 사이의 거리는 위치 차의 절댓값이에요. 모든 쌍을 한 번씩 재었고, 거리는 다음 목록과 정확히 같아야 해요.
a_i는 왼쪽부터 매긴 눈금 위치예요. 같은 거리를 두 쌍이 쓰거나 목록에 없는 거리를 만들면 실패예요. 좌우를 뒤집은 배치도 따로 세어요. 끝0부터 각 눈금까지의 거리도 카드에 있어, 실수로 시작해도 성공한 위치는 정수예요.
최대 거리17은 양끝을 정해요. 다음 거리16은 위치1 또는16을 강제해요. 반사로1이 있는 쪽부터 검사해 봐요. 새 위치를 넣을 때 기존 모든 눈금까지의 거리 카드를 한 장씩 지워요. 이미 지운 카드를 다시 쓰면 안 돼요.
남은 최대 거리d는 아직 안 놓인 눈금의 위치d 또는17−d에서 나와요. 안 놓인 가장 왼쪽·오른쪽 눈금까지의 끝점 거리가 모든 남은 거리를 덮기 때문이에요. 따라서 두 후보를 모두 검사하면 다른 실수 위치가 빠지지 않아요.
1 다음에는4 또는13입니다. 4를 택하면12와10으로만 완성되고,13을 택하면11과8로만 완성돼요. 5·7·6 등을 택한 다른 가지는 필요한 카드가 없어서 막혀요. 답은
여기서17−A는 A의 각 위치x를17−x로 바꾼 집합이고 B도 같아요. 네 배치는 모두 열다섯 거리를 정확히 재현해요. 실패 가지에는 부족한 카드도 적어 볼게요. 알려진 예의 두 반례와 모든 답의 증명을 구별해요.
착안: FIU Mark A. Weiss, The Turnpike Reconstruction Problem, 완전 도입과 Pseudocode 절. 원문 코드를 옮기거나 프로그램 성능을 검사하지 않았어요.