Enigmatic Code

Programming Enigma Puzzles

Enigma 228: Quality control

From New Scientist #1374, 8th September 1983 [link]

At the car factory where I work the latest model is pouring off the assembly line. Their chassis numbers started at 1 and they have been numbered consecutively since.

In the quality control department we have to check some of the cars. The first one we checked was one of the early ones off the line. Then we checked all cars whose chassis numbers were multiples of the first number which we had checked.

Unfortunately this system let too many mistakes go undetected and so the manager asked us to check an extra car last week. He also introduced new rules by which we would subsequently have to check all cars whose chassis numbers were the sum of two numbers (possibly the same) which we had already checked.

Car number 77777 has just gone through unchecked and we are now checking number 77778. Our union is demanding extra staff in this department because we now realise that under the new rules we are going to have to check every car from now on.

How many of the first 77777 cars were checked?

Note: I am still waiting for a phone line to be connected at my new house, so I only have sporadic access to the internet at the moment. The latest estimate is that I’ll have a connection by the end of October 2014.

[enigma228]

Advertisements

2 responses to “Enigma 228: Quality control

  1. Jim Randell 9 October 2014 at 12:03 pm

    We can get an analytical solution to this puzzle using Frobenius Numbers [ http://en.wikipedia.org/wiki/Frobenius_number ].

    For integers a, b with gcd(a, b) = 1, the Frobenius Number:

    F(a, b) = a.b − (a + b)

    is the largest integer not expressible as i.a + j.b (for i, j non-negative integers).

    We require F(a, b) = n, where n = 77777.

    So:

    b = (n + a) / (a + 1)

    Also the number of non-expressible integers is:

    N(a, b) = (a − 1) (b − 1) / 2

    Substituting for b, we get:

    N = (n + 1) / 2

    which is independent of a and b.

    The non-expressible integers correspond to the cars that were not checked. So the number of cars checked is:

    n – (n + 1) / 2 = (n − 1) / 2

    and as n = 77777, the number of cars checked is 38888.

    This Python program uses the formulae given above to determine the possible numbers of the two exemplar cars, a and b. It runs in 30ms.

    from enigma import irange, gcd, printf
    
    N = 77777
    
    for a in irange(2, N - 1):
      if not(a * (a - 2) < N): break
      if N % a == 0: continue
      (b, r) = divmod(N + a, a - 1)
      if r > 0 or b > N or gcd(a, b) > 1: continue
      t = N - (a - 1) * (b - 1) // 2
      printf("a={a} b={b} t={t}")
    

    Solution: 38,888 of the first 77,777 cars were checked.

    It finds 9 possible pairs of numbers:

    a=3 b=38890 t=38888
    a=4 b=25927 t=38888
    a=10 b=8643 t=38888
    a=19 b=4322 t=38888
    a=30 b=2683 t=38888
    a=59 b=1342 t=38888
    a=88 b=895 t=38888
    a=150 b=523 t=38888
    a=262 b=299 t=38888

    As expected, each pair gives rise to the same solution – that 38,888 of the first 77,777 cars were checked.

    Given that a is “one of the early cars off the line”, and b came off the line “last week” and they are now checking car 77777 it seems that the most likely candidates are (a, b) = (3, 38890) or (4, 25927).

    Either way they are producing thousands of cars a day, so the car can only have been in production for a couple of weeks.

    • Jim Randell 13 October 2014 at 2:25 pm

      Here’s a program that finds the same pairs as given above, but constructively, so it’s a lot slower. It runs in 28m16s.

      from enigma import irange, gcd, printf
      
      N = 77777
      
      # express n as i.a + j.b
      def express(n, a, b):
        for jb in irange(0, n, step=b):
          (i, r) = divmod(n - jb, a)
          if r == 0: return (i, jb // b)
        return None
      
      # check that N is not expressible in terms of a and b
      # but that all larger numbers are
      # return a count of numbers between 1 and N expressible in terms of a and b
      def check(a, b, N):
        t = 0
        # N must not be expressible
        if express(N, a, b) is not None: return None
        # check all higher numbers are expressible
        for n in irange(N + 1, N + a):
          if express(n, a, b) is None: return None
        # count how many lower numbers are expressible
        return sum(1 for n in irange(1, N - 1) if express(n, a, b) is not None)
      
      for a in irange(2, N - 1):
        if N % a == 0: continue
        for b in irange(a + 1, N - 1):
          if gcd(a, b) > 1: continue
          t = check(a, b, N)
          if t is None: continue
          printf("a={a} b={b} t={t}")
      

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: