Sunday Times Brain Teaser 777 – Feeler Gauges

by L Poulter

I have half-a-dozen feeler gauges on a ring like keys on a key ring. They are attached in a certain order and by selecting a single gauge or combinations of adjacent gauges it is possible to measure from 1 to 31 thousandths of an inch (thou) inclusive in steps of 1 thou. If I remove two adjacent gauges, replace them with a single gauge and rearrange the five on the ring I can now measure from 1 to 21 thou inclusive in steps of 1 thou with these five gauges by again selecting a single gauge or combinations of adjacent gauges.

What are the thicknesses of the gauges and the order of arrangement on the ring in each case? (start with gauge of unit thickness and then its thinner neighbour for the sets).

2 Comments Leave one →

brian gladman permalink


# g = list of feeler widths
# sm = sum of the widths so far
# target = the total width
# n = the number of feelers on the ring
def add_gauge(g, sm, target, n):
  # if we only have one more feeler left to add
  if len(g) == n - 1:
    # the sum of all gauge widths equals the target width so the
    # width of the last one is (target - sm) - also since the 
    # ring is circular we can insist that the width of the gauge
    # right of the unit gauge is thinner than that to its left
    if target - sm < g[1]:
      return
    # add the last gauge width and extend the list (in h) to allow
    # easy sums of adjacent values
    h = g + [target - sm] + g
    # find the total widths of all sequences of adjacent gauges
    w = set(sum(h[p : p + c]) for p in range(n) for c in range(1, n + 1))
    # we must be able to measure all widths from 1 to target
    if tuple(sorted(w)) == tuple(range(1, target + 1)):
      # return the gauge widths
      yield tuple(h[:n])
  else:
    # add another gauge (a lot faster if we assume that gauge widths 
    # are all different)
    for i in range(1, target - sum(g)):
      yield from add_gauge(g + [i], sm + i, target, n)

print('Solutions for 6 gauges of total width 31')
set_6 = tuple(add_gauge([1], 1, 31, 6))
for s in set_6:
  print(s)
  
print('Solutions for 5 gauges of total width 21')
set_5 = tuple(add_gauge([1], 1, 21, 5))
for s in set_5:
  print(s)

print('Solutions in which 2 gauges are replaced by 1')
for a in set_6:
  for b in set_5:
    # check that these share four gauges
    if len(set(a) & set(b)) == 4:
      # check that the removed gauges are adjacent
      t = tuple(set(a).difference(b))
      if (a.index(t[0]) - a.index(t[1])) % 6 in (1, 5):
        print(a, b)

# g = list of feeler widths

# sm = sum of the widths so far

# target = the total width

# n = the number of feelers on the ring

def add_gauge(g, sm, target, n):

# if we only have one more feeler left to add

if len(g) == n - 1:

# the sum of all gauge widths equals the target width so the

# width of the last one is (target - sm) - also since the

# ring is circular we can insist that the width of the gauge

# right of the unit gauge is thinner than that to its left

if target - sm < g[1]:

return

# add the last gauge width and extend the list (in h) to allow

# easy sums of adjacent values

h = g + [target - sm] + g

# find the total widths of all sequences of adjacent gauges

w = set(sum(h[p : p + c]) for p in range(n) for c in range(1, n + 1))

# we must be able to measure all widths from 1 to target

if tuple(sorted(w)) == tuple(range(1, target + 1)):

# return the gauge widths

yield tuple(h[:n])

else:

# add another gauge (a lot faster if we assume that gauge widths

# are all different)

for i in range(1, target - sum(g)):

yield from add_gauge(g + [i], sm + i, target, n)

print('Solutions for 6 gauges of total width 31')

set_6 = tuple(add_gauge([1], 1, 31, 6))

for s in set_6:

print(s)

print('Solutions for 5 gauges of total width 21')

set_5 = tuple(add_gauge([1], 1, 21, 5))

for s in set_5:

print(s)

print('Solutions in which 2 gauges are replaced by 1')

for a in set_6:

for b in set_5:

# check that these share four gauges

if len(set(a) & set(b)) == 4:

# check that the removed gauges are adjacent

t = tuple(set(a).difference(b))

if (a.index(t[0]) - a.index(t[1])) % 6 in (1, 5):

print(a, b)

which gives:


Solutions for 6 gauges of total width 31
(1, 2, 5, 4, 6, 13)
(1, 2, 7, 4, 12, 5)
(1, 3, 2, 7, 8, 10)
(1, 3, 6, 2, 5, 14)
(1, 7, 3, 2, 4, 14)
Solutions for 5 gauges of total width 21
(1, 3, 10, 2, 5)
Solutions in which 2 gauges are replaced by 1
(1, 3, 2, 7, 8, 10) (1, 3, 10, 2, 5)

Solutions for 6 gauges of total width 31

(1, 2, 5, 4, 6, 13)

(1, 2, 7, 4, 12, 5)

(1, 3, 2, 7, 8, 10)

(1, 3, 6, 2, 5, 14)

(1, 7, 3, 2, 4, 14)

Solutions for 5 gauges of total width 21

(1, 3, 10, 2, 5)

Solutions in which 2 gauges are replaced by 1

(1, 3, 2, 7, 8, 10) (1, 3, 10, 2, 5)

There are a lot of ways of speeding this up with a little effort. Since there is only one solution for the five gauges puzzle, we could solve this one and then modify it by taking out one gauge and adding in two. This would be a lot faster as the bulk of the time is in finding the six gauge solutions. Secondly, we could assume that all the gauges are of different widths (which reduces the time for a solution by a factor of four). This works because the solutions do not involve duplicate width gauges but it is not obvious (to me) that this has to be the case. But since it takes less than half a second to run anyway, we really don’t need to make this assumption.

Arthur Vause permalink

There is some interesting maths behind this puzzle, Perfect Difference Sets, which can be constructed using Galois Fields (finite fields).

I have put together a blog entry that describes the maths, and includes a Python program to construct Perfect Difference Sets of various lengths using Galois Fields. The program also solves the teaser.

It’s rather a sledgehammer to crack a nut to solve the teaser in this way, but the code also solves a related problem invloving Evariste Galois and 18 soldiers (you will have to read the blog entry to find out more).

Reply

Sunday Times Brain Teaser 777 – Feeler Gauges

by L Poulter

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta