Enigmatic Code

Programming Enigma Puzzles

Enigma 391b: Christmas recounted

From New Scientist #1540, 25th December 1986 [link]

Delivering Christmas presents is not an easy task and Exe-on-Wye has grown to be so populous that it is hardly surprising that this year Santa Claus decided to delegate the delivery to his minions. Thanks to some failure in communication, however, instead of each house receiving one sack of presents, each of his helpers left a sack at each and every house. The number of sacks that should have been delivered happens to be the number obtained by striking out the first digit of the number of sacks delivered.

When Santa Claus discovered this, he was not pleased. “Things couldn’t be worse!” he groaned. “The number of sacks you should have delivered is the largest number not ending in zero to which the addition of a single digit at the beginning produces a multiple of that number”. And he disciplined the unhappy helpers.

But for each unhappy helper there were many happy households in Exe-on-Wye on Christmas morning.

Can you say how many unhappy helpers and how many happy households?

This puzzle completes the archive of Enigma puzzles from 1986, and brings the total number of Enigma puzzles on the site to 1,058. There is a complete archive from the start of Enigma in February 1979 to the end of 1986, as well as a complete archive from February 2001 to the end of Enigma in December 2013, which is 59% of all Enigma puzzles, and leaves 733 Enigma puzzles left to publish.

I have also started to post the Tantalizer and Puzzle problems that were precursors to the Enigma puzzles in New Scientist, and so far I have posted 16 of each. In total there are 90 Puzzles (which I can get from Google Books) and 500 Tantalizer puzzles (of which the final 320 are available in Google Books).

Happy puzzling (and coding)!

[enigma391b] [enigma391]

Advertisements

2 responses to “Enigma 391b: Christmas recounted

  1. Jim Randell 14 April 2017 at 8:28 am

    If x is a k-digit number that can be multiplied by m by adding a digit d to the front we have:

    d.10^k + x = m.x
    d.10^k = x(m – 1)

    So, to find x, we can consider the factors of d.10^k.

    From the 10^k part the will be k 2’s and also k 5’s. But x cannot have both 2 and 5 as factors (as it doesn’t end in a zero).

    This program consider the possible values for the prepended digit d, and finds possible corresponding values of x and m. It runs in 38ms.

    from enigma import irange, divisors, Accumulator, printf
    
    # find numbers x = a.(f^j) and m where x -> mx can be achieved by prepending digit d
    # a = starting number
    # f = increasing powers of f are multiplied in
    # d = digit to prepend
    # r = accumulator for results - accumulate (x, (d, m))
    def solve(a, f, d, r):
      # start with a*(f^0) = a
      x = a
      while True:
        # count the digits in x
        k = len(str(x))
        # compute m
        (m, z) = divmod(d * (10 ** k), x)
        if z != 0: break
        m += 1
        printf("[d={d} x={x} k={k} m={m}: x = {x} -> {m}x = {mx}]", mx=m * x)
        r.accumulate_data(x, (d, m))
        # multiply in the next factor f
        x *= f
    
    # look for the largest x
    r = Accumulator(fn=max)
    
    # consider the prepended digit
    for d in irange(1, 9):
      for a in divisors(d):
        # consider a * 2^j and a * 5^j
        if a % 5 != 0: solve(a, 2, d, r)
        if a % 2 != 0: solve(a, 5, d, r)
    
    (x, (d, m)) = (r.value, r.data)
    printf("max: x = {x} -> {m}x = {mx} by prepending {d}", mx=m * x)
    

    Solution: Santa has 65 helpers. There are 140,625 households in Exe-on-Wye.

    x = 140625 ⇒ 65x = 9140625, which is formed by prepending the digit 9 to x.

    Although the puzzle says “for each unhappy helper there were many happy households”, 140625 does not divide exactly by 65.

  2. geoffrounce 17 April 2017 at 8:10 am

    I found a non-rigorous solution in MiniZinc by fixing the number of houses as a 6-digit number.
    I see New Scientist of 22 Jan 1987 gives the answer as 65 unhappy helpers and 140625 happy households, so all the helpers were unhappy and all the houses were happy.

    include "globals.mzn";
    
    var 1..9: digit; 
    var 1..99: helpers;
    var 100000..999999: houses;
    var 100000..99999999: sacks;
    
    constraint sacks = helpers * houses /\ sacks mod 10 > 0
    /\ sacks = digit * 1000000 + houses;
    
    solve maximize (houses);
    
    output[ "Houses, helpers, sacks = " ++ show(houses) ++ ", " ++ show(helpers) 
    ++ ", " ++ show(sacks) ];
    
    % Houses, helpers, sacks = 140625, 65, 9140625
    % Approx 4 sec.
    

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: