Skip to main content
The National Cipher Challenge

Solution to Sunday puzzle 8: A (?) gap in the solution


Recall the problem: BOSS engineers are setting up a radio calibration range consisting of a straight track, which is 17 metres long. Six small transmitters will be installed along it at pre-prepared docking stations which are installed 1m about along the entire length. Because of interference patterns no two transmitters can be placed the same distance apart as any other two. If two pairs had the same separation, their calibration echoes could arrive with the same delay and become ambiguous.

The problem described by the BOSS engineers is a classic real-world application of a Golomb Ruler—a set of marks at integer positions where no two pairs of marks are the same distance apart. This ensures that every possible echo delay is completely unique, eliminating ambiguity.

Solution

If we place the sixth transmitter at 10 meters, our full set of positions is:

{0,1,4,10,12,17}

Let’s look at all (62)=15(26​)=15 pairwise distances between these six positions:

  • From 0: to 1 is 1, to 4 is 4, to 10 is 10, to 12 is 12, to 17 is 17.
  • From 1: to 4 is 3, to 10 is 9, to 12 is 11, to 17 is 16.
  • From 4: to 10 is 6, to 12 is 8, to 17 is 13.
  • From 10: to 12 is 2, to 17 is 7.
  • From 12: to 17 is 5.

Collecting and sorting all 15 distances gives:

{1,2,3,4,5,6,7,8,9,10,11,12,13,16,17}{1,2,3,4,5,6,7,8,9,10,11,12,13,16,17}

Every single distance is completely distinct, meaning no two pairs share the same echo delay.

As for uniqueness, mathematical enumerations of 6-mark Golomb rulers bounded by a length of 17 prove that there are only four valid configurations up to reversal, and 10 is the only missing integer from your specific starting subset {0,1,4,12,17}{0,1,4,12,17} that completes a valid ruler. Any other position results in a duplicate distance.

While you probably managed to find this solution by brute-force trial and error, this only works for small puzzles, and mathematicians and engineers use more structured, elegant approaches as the problems get more complicated. You might already have worked out a more systematic method for yourself. For example Difference Triangle Analysis uses the idea of mapping out the “forbidden distances” (distances already claimed by the existing pairs) and comparing with the remaining gaps to reduce the number of attempts.

For larger scales, mathematicians use advanced number theory (such as Singer difference sets or the Erdős–Turán construction) to generate optimal Golomb rulers directly using modular arithmetic and finite fields, bypassing trial-and-error entirely.

Finite fields also underlie some of the most important cryptographic systems in use today, including elliptic curve cryptography and the Rijndael algorithm underpinning the widely used Advanced Encryption Standard.

Report a problem