Updates from October, 2019 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 4:19 pm on 18 October 2019 Permalink | Reply
    Tags:   

    Teaser 2978: Norfolk Flats 

    From The Sunday Times, 20th October 2019 [link] [link]

    Sam has purchased Norfolk Flats; an area of farmland (less than 100 hectares) bordered by six straight fences. He intends to farm an area which is an equilateral triangle with corners that are the midpoints of three of the existing boundaries. This creates three more distinct areas (one for each of his sons); these areas are identical in shape and size and have two sides that are parallel.

    Sam measured the area (in square metres) which each son will farm and also his own area. One of the numbers is a square and the other a cube. If I told you which was which, you should be able to work out the area of Norfolk Flats.

    What (in square metres) is that area?

    [teaser2978]

     
    • Jim Randell's avatar

      Jim Randell 5:34 pm on 18 October 2019 Permalink | Reply

      I supposed that the plot of land in question was a regular hexagon.

      Then, if the hexagon has side x the area of Sam’s triangular enclosure is:

      sam = (9/16)x²√3

      and the area of the enclosure for each son is:

      son = (5/16)x²√3

      So we can say Sam’s enclosure is 9 area units and each son’s enclosure is 5 area units.

      Here is a visual representation of the situation:

      So, we need to look for squares and cubes where 5 times one of them is 9 times the other.

      This Python program runs in 83ms.

      Run: [ @replit ]

      from enigma import (irange, inf, div, is_square, printf)
      
      # max area (100 hectares = 1_000_000 square metres)
      M = 1000000
      
      # collect the areas for each case (sam, son, total)
      (case1, case2) = (list(), list())
      
      # consider values for the cube
      for x in irange(1, inf):
        cube = x ** 3
        if not (8 * cube < 3 * M): break
      
        # does 5 * square = 9 * cube ?
        square = div(9 * cube, 5)
        if square is not None and is_square(square):
          (sam, son) = (square, cube)
          area = sam + 3 * son
          if area < M:
            printf("[1] son = cube = {cube} -> sam = square = {square}, area = {area}")
            case1.append((sam, son, area))
      
        # does 9 * square = 5 * cube ?
        square = div(5 * cube, 9)
        if square is not None and is_square(square):
          (sam, son) = (cube, square)
          area = sam + 3 * son
          if area < M:
            printf("[2] sam = cube = {cube} -> son = square = {square}, area = {area}")
            case2.append((sam, son, area))
      
      # consider the cases
      for ss in (case1, case2):
        if len(ss) != 1: continue
        (sam, son, area) = ss[0]
        printf("area = {area} [sam = {sam}, son = {son}]")
      

      Solution: The total area of Norfolk Flats is 243,000 square metres (= 24.3 hectares).

      Sam’s enclosure is 91,125 square metres (= 45³).

      Each son’s enclosure is 50,625 square metres (= 225²).

      So each side of the hexagon is about 305.83 metres long.

      This is the only viable solution where the area of Sam’s enclosure is a perfect cube, and the area of each son’s enclosure is a perfect square. So it is the answer to the puzzle.

      If the area of Sam’s enclosure is a perfect square, and the area of each son’s enclosure is a perfect cube, we find there are three potential solutions (where the total area is below 1 million square metres):

      sam = 225 = 15²; son = 125 = 5³; area = 600
      sam = 14400 = 120²; son = 8000 = 20³; area = 38400
      sam = 164025 = 405²; son = 91125 = 45³; area = 437400

      So this case is ruled out as the answer.


      Manually:

      [1] In the case: 5a² = 9b³

      We see that 3 must divide a, and 5 must divide b. So:

      let: a = 3p, b = 5q
      → p² = 25q³

      So 5 must divide p:

      let: p = 5r
      → r² = q³

      So we are looking for numbers that are simultaneously squares and cubes, i.e. powers of 6.

      r² = q³ = k⁶
      r = k³, q = k²
      → a = 15k³, b = 5k²

      And we are interested in cases where:

      a² +3b³ < 1,000,000
      600 k⁶ < 1,000,000
      → k = 1, 2, 3

      So there are three possible solutions in this case (those given above).

      [2] In the case: 5a³ = 9b²

      We can similarly arrive at a solution of:

      a = 45k², b = 225k³

      And we require:

      a³ + 3b² < 1,000,000
      243,000 k⁶ < 1,000,000
      → k = 1

      So in this case there is a single solution, and from this we get the answer to the puzzle.

      Like

    • Robert Brown's avatar

      Robert Brown 10:39 pm on 18 October 2019 Permalink | Reply

      It doesn’t say the fences are the same length. Alternate short & long fences makes a diagram that fits the words in the text – only restriction I can see is that ‘son’ is < 'sam'. If this is true, I don't see a possible solution.

      Like

      • Jim Randell's avatar

        Jim Randell 11:03 pm on 18 October 2019 Permalink | Reply

        @Robert: I think if you don’t require the hexagon to be regular it is possible to find side lengths that will work for many different (square, cube) combinations, so it wouldn’t be possible to work out the total area being told which of the enclosures areas was a square which was a cube.

        But with a regular hexagon there are many fewer possibilities and we can find a unique solution, so it is probably what the setter had in mind (although not what the text of the puzzle explicitly states).

        Like

    • GeoffR's avatar

      GeoffR 3:30 pm on 22 October 2019 Permalink | Reply

      
      # This solution uses Jim's diagram i.e son/sam = 5/9 in area ratio
      # F + 3.(5/9).F < 1000000 -> F < 375000
      # Hence squares < 613, cubes < 73
      
      from collections import defaultdict
      
      # Two dictionaries to collect squares and cubes for each case
      # i.e 5 * square = 9 * cube or 9 * square = 5 * cube
      
      d1 = defaultdict(list)  # 5 * square = 9 * cube
      d2 = defaultdict(list)  # 9 * square = 5 * cube
      
      # F + 3.(5/9).F < 1000000 -> F < 375000
      # hence squares < 613, cubes < 73
      
      sq = [n * n for n in range(10, 613)]
      cb = [n * n * n for n in range(10, 73)]
      
      for x in sq:
        for y in cb:
          if 5 * x == 9 * y:    
            d1[x] += [(x, y)]  
          # Other solution     
          if 9 * x == 5 * y:
            d2[x] += [(x, y)] 
      
      # One of the two dictionaries must have a single solution
      for k,v in d1.items():
        if len(v) == 1 and len(d1) == 1:
          print(f"Norfolk Flats Area = {3 * v[0][0] + v[0][1]} sm")
          print(f"Son's area = {v[0][0]} sm, Sam's area = {v[0][1]} sm")
          
      for k,v in d2.items():
        if len(v) == 1 and len(d2) == 1:
          print(f"Norfolk Flats Area = {3 * v[0][0] + v[0][1]} sm")
          print(f"Son's area = {v[0][0]} sm, Sam's area = {v[0][1]} sm")
      
      

      Like

  • Unknown's avatar

    Jim Randell 3:03 pm on 11 October 2019 Permalink | Reply
    Tags:   

    Teaser 2977: Enjoying retirement 

    From The Sunday Times, 13th October 2019 [link] [link]

    George and Martha have worked on separate departments of a company which has four-digit telephone extensions. George looked at his extension and it was ABCD. Martha’s (larger) also had A, B and C as her first three digits but not necessarily in that order. Her last digit was E. They added up their two four-digit numbers and found that the least significant digit was F. They then looked at the difference and that was a four-digit number of which the least significant digit was G. They then looked at the product and the least significant digit was H. They then looked at the average of the extensions; in it the first two digits were equal, the last two digits were also equal, and the least significant digit was J. I have thus mentioned nine digits, all positive and unequal.

    What was Martha’s extension?

    [teaser2977]

     
    • Jim Randell's avatar

      Jim Randell 3:34 pm on 11 October 2019 Permalink | Reply

      I assumed that the average of the two extension numbers was a whole number, so both extension numbers must have the same parity.

      The following Python program runs in 92ms.

      Run: [ @repl.it ]

      from enigma import (irange, subsets, nconcat, nsplit, div, printf)
      
      # allowable digits
      digits = set(irange(1, 9))
      
      # check digits are allowable and all different
      def check(*ds):
        return len(ds) + len(digits.difference(ds)) == len(digits)
      
      # consider digits D and E, which must have the same parity
      for (D, E) in subsets(digits, size=2, select='P'):
        if not(D % 2 == E % 2): continue
      
        # the sum ends in F, difference ends in G, the product ends in H
        (F, G, H) = (n % 10 for n in (D + E, E - D, D * E))
        if not check(D, E, F, G, H): continue
      
        # choose first three digits A, B, C to give ABCD = George's extension
        for (A, B, C) in subsets(digits.difference((D, E, F, G, H)), size=3, select='P'):
          xG = nconcat(A, B, C, D)
      
          # and permute ABC to give XYZ, where XYZE = Martha's extension
          for (X, Y, Z) in subsets((A, B, C), size=3, select='P'):
            xM = nconcat(X, Y, Z, E)
      
            # George's number is less than Martha's, difference is 4 digits
            if xM - xG < 1000: continue
      
            # average ...
            avg = nsplit(div(xG + xM,  2))
            # has first 2 and last 2 digits equal
            if not(avg[0] == avg[1] and avg[-2] == avg[-1]): continue
            # and the final digit is J
            J = avg[-1]
            if not check(A, B, C, D, E, F, G, H, J): continue
      
            printf("George = {xG}, Martha = {xM} [A={A} B={B} C={C} D={D} E={E} F={F} H={H} J={J}]")
      

      Solution: Martha’s extension number is 8563.

      George’s extension number is 6859.

      So if George’s number is ABCD, then Martha’s is BCAE.

      The sum is 15422, which ends in F=2.

      The difference is 1704, which ends in G=4.

      The product is 58733617, which ends in H=7.

      And the average (mean) is 7711, which starts with two 7’s and ends with two J’s; J=1.

      Each non-zero digit is mentioned once. We have (1, 2, 3, 4, 5, 6, 7, 8, 9) = (J, F, E, G, C, A, H, B, D).

      Like

    • GeoffR's avatar

      GeoffR 9:31 am on 13 October 2019 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..9: A; var 1..9: B; var 1..9: C;  
      var 1..9: D; var 1..9: E; var 1..9: F;    
      var 1..9: G; var 1..9: H; var 1..9: J;
      
      constraint all_different([A, B, C, D, E, F, G, H, J]);
      
      % George's extension number
      var 1000..9999: george = 1000*A + 100*B + 10*C + D; 
      
      % Martha's extension number
      var 1000..9999: martha ;
      
      % Average of George's and Martha's numbera
      var 1000..9999: av ; 
       
      constraint av == (martha + george) div 2;
      constraint martha > george;
      
      % Martha's extension had the first three digits A,B,C in some order
      % Martha's 1st Digit
      constraint 
         martha div 1000 == A 
      \/ martha div 1000 == B 
      \/ martha div 1000 == C;
      
      % Martha's 2nd Digit
      constraint 
         ((martha div 100) mod 10) == A
      \/ ((martha div 100) mod 10) == B
      \/ ((martha div 100) mod 10) == C;
      
      % Martha's 3rd Digit
      constraint 
         ((martha div 10) mod 10) == A
      \/ ((martha div 10) mod 10) == B
      \/ ((martha div 10) mod 10) == C;
      
      % Martha's 4th Digit
      constraint martha mod 10 == E;
      
      % Sum of george and martha has F as least significant digit
      constraint (george + martha) mod 10 == F;
      
      % Difference of george and martha has G as least significant digit
      constraint (martha - george) > 1000  
      /\ (martha - george) mod  10 == G;
      
      % Product of george and martha has H as least significant digit
      constraint (martha * george) mod 10 == H;
      
      % Average has first 2 digits equal
      constraint av div 1000 ==  (av div 100) mod 10;
        
      % Average has last 2 digits equal to J
      constraint (av div 10) mod 10 == J /\ av mod 10 = J;
      
      solve satisfy;
      
      output [ "Martha's extension is " ++ show(martha) 
      ++ "\n" ++ "George's extension is " ++ show(george)
      ++ "\n" ++ "Average of two extensions is " ++ show(av)];
      
      % Martha's extension is 8563
      % George's extension is 6859
      % Average of two extensions is 7711
      % ----------
      % ==========
      
      

      Like

  • Unknown's avatar

    Jim Randell 5:11 pm on 4 October 2019 Permalink | Reply
    Tags:   

    Teaser 2976: Piece of cake 

    From The Sunday Times, 6th October 2019 [link] [link]

    Using her special recipe, so that each cubic inch of baked cake weighed one ounce, Mam made the cake for my eighth birthday party. It had a regular octagonal flat top and base, and equal square vertical faces, several inches high exactly.

    Not all (but a majority) of the dozen invited pals came to the party. We each had an equal portion of cake (the largest whole number of ounces possible from it, a two-figure number). Mam had the leftover cake. Curiously, if one more or one fewer pal had turned up and our portions had been worked out in the same way, Mam’s leftover would have been the same in each case, but less than she actually got.

    How large, in ounces, was my portion?

    [teaser2976]

     
    • Jim Randell's avatar

      Jim Randell 5:38 pm on 4 October 2019 Permalink | Reply

      12 people were invited, and more than half but not all came, so between 7 and 11. If we include the setter as well the cake is divided into between 8 and 12 integer portions.

      We can ignore the fractional part of the volume as it is always included in the leftover portion of cake. So we just need to consider the integer part of the remaining portion.

      This Python program runs in 87ms.

      Run: [ @repl.it ]

      from enigma import (sqrt, irange, inf, divf, printf)
      
      # area of an octagon with unit sides
      a = 2 * (1 + sqrt(2))
      
      # consider the side of the octagon
      for x in irange(1, inf):
        # volume of the cake (discarding the fractional part)
        v = int(a * x**3)
        if v < 80: continue
        if v > 1200: break
      
        # consider the number of portions
        d = dict()
        for k in irange(7, 13):
          # the (2-digit) amount of cake per portion, and remaining amount
          (p, r) = divmod(v, k)
          if 9 < p < 100: d[k] = r
      
        # find the actual number of portions
        for (k, r) in d.items():
          try:
            (rm, rp) = (d[k - 1], d[k + 1])
          except KeyError:
            continue
          if not (rm < r and rm == rp): continue
          # output solution
          printf("portion = {p} [x={x} k={k}; ({km} -> {rm}+, {k} -> {r}+, {kp} -> {rp}+)]", p=divf(v, k), km=k - 1, kp=k + 1)
      

      Solution: The portion size was 54 ounces.

      It seems like quite a large portion, but I suppose any 2-digit number of ounces is quite a weighty piece of cake.

      Of the 12 invited guests, 10 attended, meaning that the cake was divided into 11 integer portions.

      The cake has vertical faces that are squares measuring 5 inches along each side, so would require a round cake tin just over 13 inches in diameter to fit it in. It would weigh just over 603.5 ounces (about 17.1 kg).


      We only need to look at the cases where the cake is between 3 and 6 inches high, and there are four possibilities where the leftover portions would have been equal if one fewer or one more guest had attended:

      height = 3″, portions = 8 @ 16 oz, leftover = 2.37 oz; 7 or 9 portions, leftover = 4.37 oz
      height = 4″, portions = 11 @ 28 oz, leftover = 1.02 oz; 10 or 12 portions, leftover = 9.02 oz
      height = 5″, portions = 9 @ 67 oz, leftover = 0.55 oz; 8 or 10 portions, leftover = 3.55 oz
      height = 5″, portions = 11 @ 54 oz, leftover = 9.55 oz; 10 or 12 portions, leftover = 3.55 oz

      Only the last of these has a hypothetical leftover portion that is smaller than the actual leftover portion, so this gives rise to the solution.

      Like

  • Unknown's avatar

    Jim Randell 6:14 pm on 27 September 2019 Permalink | Reply
    Tags:   

    Teaser 2975: Hollow cube land 

    From The Sunday Times, 29th September 2019 [link] [link]

    I have a large box of toy building bricks. The bricks are all cubes (the same size), and can be pushed together then dismantled.

    I decided to build the largest cube possible by leaving out all the interior bricks. When my hollow cube was finished I had two bricks left over. I put all the bricks back in the box and gave it to my two children. Each in turn was able to use every brick in the box to construct two hollow cubes, again with all interior bricks removed. Their cubes were all different sizes.

    This would not have been possible had the box contained any fewer bricks.

    How many bricks were in the box?

    [teaser2975]

     
    • Jim Randell's avatar

      Jim Randell 6:57 pm on 27 September 2019 Permalink | Reply

      For n ≥ 2 we can calculate the “hollow cube” number as:

      h(n) = n³ − (n − 2)³ = 6(n − 1)² + 2

      We can then check for values where it is possible to make h(n) + 2 from the sum of two smaller h() numbers, in (at least) two different ways.

      This Python 3 program runs in 81ms.

      Run: [ @replit ]

      from enigma import (irange, inf, subsets, printf)
      
      # "hollow cube" numbers (n >= 2)
      h = lambda n: 6 * (n - 1)**2 + 2
      
      # solve the puzzle using formula for h(n)
      def solve():
        d = dict()
        for n in irange(3, inf):
          # calculate h(n)
          x = h(n)
          printf("[h({n}) = {x}]")
          # can x + 2 be made from the sum of 2 smaller h numbers?
          ss = list(s for s in subsets(d.keys(), size=2) if sum(d[k] for k in s) == x + 2)
          # in 2 different ways?
          if len(ss) > 1:
            printf("t={t} [n={n} x={x}, ss={ss}]", t=x + 2)
            return
          # add the number to the list
          d[n] = x
      
      solve()
      

      Solution: There were 3754 bricks in the box.

      The setter was able to build a hollow cube measuring 26 units along each side, using up 3752 of the bricks (leaving 2 unused).

      One child produced cubes measuring 8 and 25 units along each side, using up 296 + 3458 = 3754 bricks.

      The other child produced cubes measuring 16 and 21 units along each side, using up 1352 + 2402 = 3754 bricks.


      Analytically:

      We are looking for numbers p, q such that:

      6(n − 1)² + 4 = 6(p − 1)² + 2 + 6(q − 1)² + 2
      (n − 1)² = (p − 1)² + (q − 1)²

      So we can look for Pythagorean triples that share a hypotenuse. The smallest is:

      25² = 7² + 24² = 15² + 20²

      from which we see the setter’s cube measured 26 units, and the children’s were (8, 25) units and (16, 21) units.

      For more than 2 children the smallest solution is with 25354 bricks. The setter built a cube measuring 66 units, and there can be up to 4 children with cubes measuring (17, 64), (26, 61), (34, 57), (40, 53) units. Corresponding to:

      65² = 16² + 63² = 25² + 60² = 33² + 56² = 39² + 52²

      Like

  • Unknown's avatar

    Jim Randell 12:05 am on 21 September 2019 Permalink | Reply
    Tags:   

    Teaser 2974: Flockbuster 

    From The Sunday Times, 22nd September 2019 [link] [link]

    Wu, Xi, Yo and Ze had different two-figure numbers of sheep and kept them in a walled field divided by fences into a fold each. Maths whizz, Wu, with the largest flock, noticed that together her flock and Ze’s equalled Xi’s and Yo’s combined; and that, as a fraction, the ratio of Yo’s flock to Xi’s had consecutive upper and lower numbers (e.g. 3/4), whereas her flock to Xi’s ratio had those numbers swapped over (e.g. 4/3).

    Overnight, storm-damaged fences led to the same number of sheep in each fold. Wu’s old maths teacher, told just this number and the above relationships, couldn’t be certain how many sheep Wu owned (which would have been true, also, if he’d been told either fraction instead).

    How many sheep did Wu own?

    [teaser2974]

     
    • Jim Randell's avatar

      Jim Randell 12:07 am on 21 September 2019 Permalink | Reply

      This Python program considers possible values for X and Y, from which the values of W and Z (and k) can be derived. It runs in 88ms.

      Run: [ @replit ]

      from enigma import (irange, subsets, div, filter_unique, unpack, intersect, printf)
      
      # collect possible solutions
      rs = list()
      
      # choose X and Y (Y < X)
      for (Y, X) in subsets(irange(10, 99), size=2):
      
        # Y / X can be expressed as k / (k + 1)
        k = div(Y, X - Y) 
        if k is None: continue
      
        # X / W can be expressed as (k + 1) / k
        W = div((k + 1) * X, k)
        if W is None or not (X < W < 100): continue
      
        # W + Z = X + Y
        Z = X + Y - W
        if (not 9 < Z < W) or Z == Y or Z == X: continue
      
        # total number of sheep must be divisible by 4
        t = W + X + Y + Z
        if t % 4 != 0: continue
      
        rs.append((W, X, Y, Z, k, t))
        printf("[Y={Y} X={X}, k={k}, W={W} Z={Z}, t={t}]")
      
      # the total is ambiguous
      (_, rs1) = filter_unique(rs, unpack(lambda W, X, Y, Z, k, t: t))
      
      # the fraction is also ambiguous
      (_, rs2) = filter_unique(rs, unpack(lambda W, X, Y, Z, k, t: k))
      
      # but together these tell us W
      rs = intersect((rs1, rs2))
      ws = set(W for (W, X, Y, Z, k, t) in rs)
      printf("W = {ws} [{rs}]")
      

      Solution: Wu owns 99 sheep.

      There are 12 possible values for W, X, Y, Z that fit the description. Here they are are by the total number of sheep, and the value of k, the numerator of the fraction:

      [ 1] t=72 k=4, W=25 Z=11, X=20 Y=16
      [ 2] t=84 k=3, W=32 Z=10, X=24 Y=18
      [ 3] t=144 k=4, W=50 Z=22, X=40 Y=32
      [ 4] t=156 k=6, W=49 Z=29, X=42 Y=36
      [ 5] t=168 k=3, W=64 Z=20, X=48 Y=36
      [ 6] t=200 k=2, W=90 Z=10, X=60 Y=40
      [ 7] t=216 k=4, W=75 Z=33, X=60 Y=48
      [ 8] t=220 k=5, W=72 Z=38, X=60 Y=50
      [ 9] t=220 k=2, W=99 Z=11, X=66 Y=44
      [10] t=252 k=3, W=96 Z=30, X=72 Y=54
      [11] t=272 k=8, W=81 Z=55, X=72 Y=64
      [12] t=312 k=6, W=98 Z=58, X=84 Y=72

      We see that the total number of sheep is only ambiguous when t = 220 (cases 8, 9). So the teacher can narrow down the situation to one of those two cases (all other values of t uniquely identify a single case).

      And the value of k is ambiguous when:

      k = 2 (cases 6, 9)
      k = 3 (cases 2, 5, 10)
      k = 4 (case 1, 3, 7)
      k = 6 (cases 4, 12)

      And case 9 is the only one common to both scenarios so this is the required solution: W=99 Z=11, X=66 Y=44.

      So W + Z = X + Y = 110 and Y/X = X/W = 2/3.

      Like

      • Jim Randell's avatar

        Jim Randell 3:06 pm on 22 September 2019 Permalink | Reply

        Here’s a slightly shorter program that considers values for X, and derives possible values for W, Y, Z, k, t from that.

        Since we know:

        k / (k + 1) = Y / X = X / W

        We also know that:

        X² = Y.W

        So Y and W are divisor pairs of X², and Y < X < W.

        We can then also calculate Z and k and check they satisfy the remaining conditions.

        Run: [ @replit ]

        from enigma import (irange, divisors_pairs, div, filter_unique, unpack, intersect, printf)
        
        # collect possible solutions
        rs = list()
        
        # consider 2-digit values for X
        for X in irange(10, 99):
        
          # compute W, Y, Z, k, t
          for (Y, W) in divisors_pairs(X, 2):
            if not (9 < Y < X < W < 100): continue
            Z = X + Y - W
            if not (9 < Z): continue
            k = div(Y, X - Y)
            if k is None: continue
            t = X + Y + W + Z
            if t % 4 != 0: continue
        
            rs.append((W, X, Y, Z, k, t))
            printf("[X={X}, Y={Y} W={W} Z={Z}, k={k} t={t}]")
        
        # the total is ambiguous
        (_, rs1) = filter_unique(rs, unpack(lambda W, X, Y, Z, k, t: t))
        
        # the fraction is also ambiguous
        (_, rs2) = filter_unique(rs, unpack(lambda W, X, Y, Z, k, t: k))
        
        # but together these tell us W
        rs = intersect((rs1, rs2))
        ws = set(W for (W, X, Y, Z, k, t) in rs)
        printf("W = {ws} [{rs}]")
        

        Like

  • Unknown's avatar

    Jim Randell 3:58 pm on 13 September 2019 Permalink | Reply
    Tags:   

    Teaser 2973: Something in common 

    From The Sunday Times, 15th September 2019 [link] [link]

    I have written down four different numbers. The third number is the highest common factor of the first two (i.e. it is the largest number that divides exactly into both of them). The fourth number is the lowest common multiple of the first two (i.e. it is the smallest number that both of them divide exactly into).

    I can consistently replace digits by letters in my numbers so that the highest common factor is HCF and the lowest common multiple is LCM.

    What are the first two numbers?

    [teaser2973]

     
    • Jim Randell's avatar

      Jim Randell 4:06 pm on 13 September 2019 Permalink | Reply

      The two mystery numbers have a common divisor that is 3 digits, and also the have a common multiple that is 3 digits, so they are both 3 digit numbers themselves.

      Denoting the numbers UVW and XYZ we can use the [[ SubstitutedExpression() ]] solver from the enigma.py library to give a direct interpretation of the the puzzle.

      This run file executes in 989ms.

      Run: [ @repl.it ]

      #! python -m enigma -rr
      
      SubstitutedExpression
      
      --distinct="CFHLM"
      --answer="(UVW, XYZ)"
      
      "gcd(UVW, XYZ) = HCF"
      "lcm(UVW, XYZ) = LCM"
      
      "all_different(UVW, XYZ, HCF, LCM)"
      
      "UVW < XYZ"
      

      Solution: The first two numbers are 278 and 417.

      hcf(278, 417) = 139
      lcm(278, 417) = 834

      Like

      • Jim Randell's avatar

        Jim Randell 5:14 pm on 13 September 2019 Permalink | Reply

        Here’s an alternative approach that uses a bit of analysis:

        Each of the mystery numbers must be some small (proper) multiple of HCF, say, A × HCF and B × HCF. And A and B must be co-prime.

        We can then use the fact that:

        hcf(p, q) × lcm(p, q) = p × q

        to give a faster alphametic approach.

        The following run file executes in 173ms.

        Run: [ @repl.it ]

        #! python -m enigma -rr
        
        SubstitutedExpression
        
        --distinct="CFHLM"
        --answer="(A * HCF, B * HCF)"
        
        "1 < A < B"
        "gcd(A, B) = 1"
        
        "A * B * HCF = LCM"
        

        Actually it is clear that A × B < 10, so the only options are A = 2, B = 3, giving rise to the following one-line solution:

        % python -m enigma SubstitutedExpression "6 * HCF = LCM" --answer="(2 * HCF, 3 * HCF)"
        (6 * HCF = LCM) ((2 * HCF, 3 * HCF))
        (6 * 139 = 834) ((2 * 139, 3 * 139)) / C=3 F=9 H=1 L=8 M=4
        (2 * HCF, 3 * HCF) = (278, 417) [1 solution]
        

        Like

    • GeoffR's avatar

      GeoffR 10:09 am on 17 September 2019 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..9:H; var 0..9:C; var 0..9:F;
      var 1..9:L; var 0..9:M;
      
      var 100..999:N1; var 100..999:N2;
      var 100..999:HCF = 100*H + 10*C + F;
      var 100..999:LCM = 100*L + 10*C + M;
      
      constraint all_different( [N1, N2, HCF, LCM] );
      constraint all_different( [H, C, F, L, M] );
      
      constraint LCM * HCF == N1 * N2;
      
      constraint N1 mod HCF == 0 /\ N2 mod HCF == 0;
      
      solve maximize(HCF);
      
      output [ " First number = " ++ show(N1) ++ "\n"
      ++ " Second number = " ++ show(N2) ++ "\n"
      ++ " Highest common factor = " ++ show(HCF) ++ "\n"
      ++ " Lowest common multiple = " ++ show(LCM) ]; 
      
      

      Like

  • Unknown's avatar

    Jim Randell 5:56 pm on 6 September 2019 Permalink | Reply
    Tags:   

    Teaser 2972: A relaxing day 

    From The Sunday Times, 8th September 2019 [link] [link]

    George and Martha have a digital clock, which displays time with six digits on the 24-hour system (i.e. HH:MM:SS).

    One afternoon, George looked at the clock and saw a six-digit display involving six different positive digits. He dozed off immediately, and when he awoke in the evening he saw another display of six digits, again all positive and different. He dozed off immediately and later on (before midnight) he awoke, having slept for exactly 23 minutes longer than the previous time. At that time, he saw a third display, yet again six different positive digits. He thus had seen eighteen digits and the nine positive digits had each appeared exactly twice.

    At what time did George wake up after his first sleep?

    [teaser2972]

     
    • Jim Randell's avatar

      Jim Randell 6:30 pm on 6 September 2019 Permalink | Reply

      This Python program looks for possible 6-digit times composed of different digits, it separates them into afternoon (before 6pm) and evening (after 6pm) and the looks for two times in the evening that have a difference that is 23 minutes longer than the difference between the first time and one of the afternoon times. We then check the three times between them use each of the digits exactly twice. It runs in 460ms.

      Run: [ @repl.it ]

      from enigma import (irange, nsplit, cproduct, subsets, multiset, sprintf, printf)
      
      # format a number of seconds as HH:MM:SS
      def hms(t):
        (h, m, s) = nsplit(t, 3, base=60)
        return sprintf("{h:02d}:{m:02d}:{s:02d}")
      
      # consider 2-digit numbers with different digits that make valid times
      (hs, mss) = (list(), list())
      for n in irange(12, 59):
        (a, b) = nsplit(n, 2)
        if a == b or b == 0: continue
        if n < 24: hs.append((a, b))
        mss.append((a, b))
      
      # collect times composed of 6 different digits
      (aft, eve) = (dict(), dict())
      for ((h1, h0), (m1, m0), (s1, s0)) in cproduct([hs, mss, mss]):
        ds = (h1, h0, m1, m0, s1, s0)
        if len(set(ds)) != 6: continue
        # time as a number of seconds
        t = ((h1 * 10 + h0) * 60 + (m1 * 10 + m0)) * 60 + (s1 * 10 + s0)
        (aft if t < 64800 else eve)[t] = ds
      
      # find times t2, t3, both in the evening
      for (t2, t3) in subsets(sorted(eve.keys()), size=2):
        d = t3 - t2 - 1380
        if not (d > 0): continue
        # and t1 in the afternoon
        t1 = t2 - d
        if t1 not in aft: continue
      
        # check each digit is used exactly twice
        m = multiset(aft[t1], eve[t2], eve[t3])
        if not all(v == 2 for v in m.values()): continue
      
        # output solution
        printf("{t1} -> {t2} -> {t3}", t1=hms(t1), t2=hms(t2), t3=hms(t3))
      

      Solution: After the first nap George awoke when the clock read 19:56:48.

      There are two possible start times for the first nap (although they are within a minute of each other), but in both cases the wake time from the first nap is the same, and so there is a unique answer to the puzzle.

      The two possible sequences are:

      16:27:39 → (3h29m09s) → 19:56:48 → (3h52m09s) → 23:48:57
      16:28:37 → (3h28m11s) → 19:56:48 → (3h51m11s) → 23:47:59

      And these are the only two sequences even if we don’t restrict the first time to be “afternoon” and the final two times to be “evening”.

      Like

    • GeoffR's avatar

      GeoffR 3:33 pm on 10 September 2019 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % hours, min and sec for afternoon time
      var 12..17: ah;
      var 12..59: am;
      var 12..59: as;
      
      % No zeroes in six positive digits
      constraint am != 20 /\ am != 30 /\ am != 40 /\ am != 50;
      constraint as != 20 /\ as != 30 /\ as != 40 /\ as != 50;
      
      constraint  all_different([ah div 10, ah mod 10,
      am div 10, am mod 10, as div 10, as mod 10]);
      
      % afternoon time in sec (range from midday to midnight)
      var 43000..90000: a_sec = ah*3600 + am*60 + as;
      
      % hours, min and sec for 1st evening time 
      var 18..23: eh1;
      var 12..59: em1;
      var 12..59: es1;
      
      constraint eh1 != 20;
      
      % No zeroes in six positive digits of time
      constraint em1 != 20 /\ em1 != 30 /\ em1 != 40 /\ em1 != 50;
      constraint es1 != 20 /\ es1 != 30 /\ es1 != 40 /\ es1 != 50;
      
      constraint all_different ([eh1 div 10, eh1 mod 10,
      em1 div 10, em1 mod 10, es1 div 10, es1 mod 10]);
      
      % 1st evening time in sec
      var 43000..90000: e1_sec = eh1*3600 + em1*60 + es1;
      
      % 2nd evening time 
      % hours, min and sec for 2nd evening time
      var 18..23: eh2;
      var 12..59: em2;
      var 12..59: es2;
      
      constraint all_different ([eh2 div 10, eh2 mod 10,
      em2 div 10, em2 mod 10, es2 div 10, es2 mod 10]);
      
      constraint eh2 != 20;
      
      % No zeroes in six positive digits
      constraint em2 != 20 /\ em2 != 30 /\ em2 != 40 /\ em2 != 50;
      constraint es2 != 20 /\ es2 != 30 /\ es2 != 40 /\ es2 != 50;
      
      % 2nd evening time in sec
      var 43000..90000: e2_sec = eh2*3600 + em2*60 + es2;
      
      % all digits 1..9 in the three 6-digit times occur exactly twice
      constraint forall(i in 1..9) 
      (count ([ 
      ah div 10, ah mod 10,am div 10, am mod 10, as div 10, as mod 10,
      eh1 div 10, eh1 mod 10,em1 div 10, em1 mod 10, es1 div 10, es1 mod 10,
      eh2 div 10, eh2 mod 10, em2 div 10, em2 mod 10, es2 div 10, es2 mod 10
              ], i, 2) );
      
      % 2nd time span is 23 minutes longer than the 1st time span
      constraint (e1_sec - a_sec) ==  (e2_sec - e1_sec) - 23 * 60;
      
      solve satisfy;
      
      output  [ "Time are in format [hh mm ss] " ++ "\n" ++
      show ([ah, am, as])  ++ " " ++ show(a_sec) ++ " total sec"
      ++"\n" ++ show([eh1, em1, es1]) ++ " " ++ show(e1_sec) ++ " total sec"
      ++"\n" ++ show([eh2, em2, es2]) ++ " " ++ show(e2_sec) ++ " total sec"
      ++"\n" ++ "George woke up after his first sleep at " 
      ++ show(eh1) ++ ":" ++ show(em1) ++ ":" ++ show(es1)  ];
      
      % Time are in format [hh mm ss] 
      % [16, 27, 39] 59259 total sec
      % [19, 56, 48] 71808 total sec
      % [23, 48, 57] 85737 total sec
      % George woke up after his first sleep at 19:56:48
      % ----------
      % Time are in format [hh mm ss] 
      % [16, 28, 37] 59317 total sec
      % [19, 56, 48] 71808 total sec
      % [23, 47, 59] 85679 total sec
      % George woke up after his first sleep at 19:56:48
      % ----------
      % ==========
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 7:29 am on 30 August 2019 Permalink | Reply
    Tags:   

    Teaser 2971: Six sisters on the ski lift 

    From The Sunday Times, 1st September 2019 [link] [link]

    The sum of the ages of six sisters known to me is 92. Though there is no single whole number greater than 1 that simultaneously divides the ages of any three of them, I did notice this morning, while they lined up for the ski lift, that the ages of any two of them standing one behind the other, had a common divisor greater than 1.

    In increasing order, how old are the six sisters?

    [teaser2971]

     
    • Jim Randell's avatar

      Jim Randell 8:06 am on 30 August 2019 Permalink | Reply

      This program builds up a list of the ages in the order they appear in the queue, such that each consecutive pair share a common factor (greater than 1), but no 3 of them have a common factor (greater than 1).

      It runs in 287ms.

      Run: [ @replit ]

      from enigma import (irange, mgcd, cached, subsets, printf)
      
      # use a caching version of gcd
      gcd = cached(mgcd)
      
      # look for k numbers that sum to t
      # each has a common factor with the previous number
      # but no 3-set has a common factor > 1
      def solve(t, k, m=1, ns=[]):
        if k == 0:
          yield ns
        else:
          # choose a value from the remaining total
          for n in (irange(m, t - (k - 1) * m) if k > 1 else [t]):
            # any new number must have a gcd > 1 with the previous number
            if len(ns) > 0 and gcd(n, ns[-1]) == 1: continue
            # but must have a gcd of 1 combined with all other pairs
            if any(gcd(n, a, b) > 1 for (a, b) in subsets(ns, size=2)): continue
            # solve for the remaining numbers
            yield from solve(t - n, k - 1, m, ns + [n])
      
      # solve the puzzle
      for ns in solve(92, 6, 2):
        printf("{s} -> {ns}", s=sorted(ns))
      

      Solution: The ages of the sisters are 7, 10, 13, 15, 21, 26.

      They are queuing in the order (7, 21, 15, 10, 26, 13), or the reverse of this.

      Which we can factorise as: (7, 7×3, 3×5, 5×2, 2×13, 13). So the common factors are 7, 3, 5, 2, 13.

      And, in fact, picking a sequence of different prime numbers and then multiplying them together in pairs will give us a sequence where consecutive pairs share a factor, but no three numbers share a common factor.

      However this procedure will not necessary find all possible solutions. For example, if the required total had been 96, there is a possible queue of (7, 7×3, 3×5, 5×2×2, 2×11, 11) that cannot be constructed in this way (note the 5×2×2 term), but it is found by the program given above.

      Like

      • Jim Randell's avatar

        Jim Randell 2:17 pm on 31 August 2019 Permalink | Reply

        Here is an alternative approach that uses a bit of analysis.

        Each consecutive pair of numbers in the queue must have some prime as a common factor. So we can start with a prime and then look at pairs that are multiples of that prime. We can then choose a different prime (if a prime is repeated we will have 3 numbers that are divisible by it) that divides the second number, and choose the third number that is a multiple of the new prime, and so we continue until we have all six numbers in the queue.

        This recursive Python 3 program is a little longer that my previous approach, but it runs quicker, and can be used to explore solutions for different totals and number of elements in the queue. (It also removes the solutions that that are reverse of another solution).

        For the parameters of the puzzle it runs in 80ms. (Internal runtime is 23ms).

        Run: [ @replit ]

        from enigma import (primes, irange, mgcd as gcd, subsets, arg, printf)
        
        # T = total sum of numbers, K = number of numbers to consider
        T = arg(92, 0, int)
        K = arg(6, 1, int)
        printf("[T={T} K={K}]")
        
        # possible common prime factors
        primes = set(primes.between(1, T // 3))
        
        # return viable multiples of p
        multiples = lambda p, t, k: irange(p, t - (k - 1) * 2, step=p)
        
        # find k more numbers, that sum to t
        # the next number should be a multiple of prime p
        # ns = numbers found so far
        # ps = primes used so far
        def solve(k, t, p, ns=[], ps=set()):
          # are we done?
          if k == 1:
            if t % p == 0:
              yield ns + [t]
          else:
            # the next age n is some multiple of p and also some other prime q
            for q in primes.difference(ps):
              for n in multiples(p * q, t, k):
                yield from solve(k - 1, t - n, q, ns + [n], ps.union([q]))
        
        # choose the first prime
        for p in primes:
          # the first age is some multiple of p
          for n in multiples(p, T, K):
            # solve for the remaining 5 numbers
            for ns in solve(K - 1, T - n, p, [n], set([p])):
              if ns[0] > ns[-1]: continue # [optional] only consider queues one way round
              # check no 3-set has a gcd > 1
              if any(gcd(*s) > 1 for s in subsets(ns, size=3)): continue
              # output solution
              printf("{s} -> {ns}", s=sorted(ns))
        

        Like

    • Robert Brown's avatar

      Robert Brown 5:18 pm on 30 August 2019 Permalink | Reply

      That’s odd. My QuickBasic program (using a different algorithm!) runs in < 10ms.

      Like

  • Unknown's avatar

    Jim Randell 1:56 am on 24 August 2019 Permalink | Reply
    Tags:   

    Teaser 2970: Puzzling powers 

    From The Sunday Times, 25th August 2019 [link] [link]

    I came across a most remarkable number recently and wrote it down. All its digits were different and it was divisible by 11. In itself, that wasn’t particularly interesting, but I wrote down the number of digits in the number and then wrote down the sum of the digits in the number.

    I therefore had three numbers written down. What surprised me was that of the three numbers, one was a square and two were cubes.

    What is the remarkable number?

    [teaser2970]

     
    • Jim Randell's avatar

      Jim Randell 7:42 am on 24 August 2019 Permalink | Reply

      I started without making the assumption that the numbers are separately a square, a cube and a cube (in some order), i.e. one of them could be both a square and a cube.

      The smallest numbers that are both squares and cubes are 0, 1, 64, 729, … (i.e. the powers of 6).

      So we can write down 0 (a multiple of 11 using all different digits), which has 1 digit and a digit sum of 0. And we can say one of them is a square and two of them are cubes (as they are all both squares and cubes). If however, we require exactly 1 of them to be a square and exactly 2 of them to be cubes we can eliminate this solution.

      The number of digits is going to be between 1 and 10, and the digits sum is going to be between 0 and 45, so neither of those can be both a square and a cube, which means that the multiple of 11 must be either a square or a cube (possibly both), so can be written as either (11.m)² or (11.m)³.

      This Python program considers numbers of this form, and finds only one solution. It runs in 157ms.

      Run: [ @repl.it ]

      from enigma import (irange, iroot, nsplit, icount_exactly as count, is_square, is_cube, printf)
      
      # consider multiples of 11 both squared and cubed
      for p in (2, 3):
        for m in irange(11, iroot(9876543210, p), step=11):
          n = m**p
          # digits
          ds = nsplit(n)
          # number of digits
          k = len(ds)
          # all digits different
          if len(set(ds)) != k: continue
          # digit sum
          s = sum(ds)
      
          # one is a square, two are cubes
          ns = (n, k, s)
          if count(ns, is_square, 1) and count(ns, is_cube, 2):
            printf("n={n} k={k} s={s}")
      

      Solution: The number is 26198073.

      Changing [[ count() ]] to use [[ icount_at_least() ]] does not yield any further solutions.

      The number is (27×11)³.

      The digit length is 8 (= 2³).

      The digit sum is 36 (= 6²).

      If we look at the 6th power of multiples of 11 we find that the powers of 11, 22, 33, 44 all have repeated digits, and the power of 55 is longer than 10 digits. So none of the numbers are going to be both a square and a cube. We can use this analysis to reduce the run time of the program, for example we only have to check numbers with 1, 4, 8, 9 digits. So we can reduce the maximum possible number (at line 5) to 987654321.

      For k = 1 the only possible value is n = 0, and we have already eliminated this as a solution.

      For k = 4 (a square), the only multiple of 11 cubed with 4 digits is n = 11³ = 1331, which has repeated digits.

      For k = 8 (a cube) and k = 9 (a square) the only possible digit sum is s = 36 (a square), so we see the solution must be a multiple of 11 cubed, with 8 different digits and a digit sum of 36. So we only have to check values n = (11.m)³ for m = 20 … 42 to find a value with 8 different digits. There are 2 possible values, and only one of these has a digit sum of 36.

      Like

  • Unknown's avatar

    Jim Randell 8:43 pm on 15 August 2019 Permalink | Reply
    Tags:   

    Teaser 2969: Slide rules 

    From The Sunday Times, 18th August 2019 [link] [link]

    Using her ordinary 15cm ruler and Zak’s left-handed version (numbers 1 to 15 reading right to left) Kaz could display various fractions. For instance, putting 5 on one ruler above 1 on the other ruler, the following set of fractions would be displayed: 5/1, 4/2, 3/3, 2/4 and 1/5. Zak listed the fifteen sets starting from “1 above 1” up to “15 above 1”.

    Kaz chose some fractions with values less than one from Zak’s sets (using just the digits 1 to 9, each once only in her selection). Of these, two were in simplest form, one of which had consecutive numerator and denominator. Zak correctly totalled Kaz’s selection, giving the answer as a fraction in simplest form. Curiously, the answer’s numerator and denominator were both palindromic.

    Give Zak’s answer.

    [teaser2969]

     
    • Jim Randell's avatar

      Jim Randell 10:45 pm on 15 August 2019 Permalink | Reply

      This Python program collects possible fractions, and then uses a recursive function to select viable sets that Kaz could have chosen. These sets are then examined to find candidates where the sum is expressed as a fraction consisting of two palindromes.

      Run: [ @repl.it ]

      from fractions import Fraction as F
      from enigma import (irange, nsplit, gcd, join, printf)
      
      # collect fractions less than 1
      fs = list()
      
      # consider overlaps from 1 to 15
      for n in irange(1, 15):
        for (a, b) in zip(irange(n, 1, step=-1), irange(1, n, step=1)):
          if a < b:
            fs.append((a, b))
      
      # generate sets of fractions, using the digits in ds, and:
      # one of the fractions consists of consecutive numbers
      # two of the fractions are in lowest terms
      def choose(fs, ds=set(), ss=[]):
        # are we done?
        if not ds:
          # find fractions in their lowest terms
          rs = list((a, b) for (a, b) in ss if gcd(a, b) == 1)
          # there should be exactly 2 of them
          if len(rs) != 2: return
          # and exactly one of them must consist of consecutive numbers
          if sum(b == a + 1 for (a, b) in rs) != 1: return
          yield ss
        else:
          for (i, (a, b)) in enumerate(fs):
            d = nsplit(a) + nsplit(b)
            if len(set(d)) < len(d) or not ds.issuperset(d): continue
            yield from choose(fs[i + 1:], ds.difference(d), ss + [(a, b)])
      
      # check for palindromes
      def is_palindromic(n):
        ds = nsplit(n)
        return ds == ds[::-1]
      
      # choose the set of fractions
      for ss in choose(fs, set(irange(1, 9))):
        # calculate the sum of the fractions
        t = sum(F(a, b) for (a, b) in ss)
        if is_palindromic(t.numerator) and is_palindromic(t.denominator):
          printf("{ss} = {t}", ss=join((join((a, "/", b)) for (a, b) in ss), sep=" + "))
      

      Solution: Zak’s answer is 545/252.

      The fractions Kaz has chosen are:

      3/12 + 4/8 + 5/9 + 6/7 = 545/252

      There are 10 sets of fractions that Kaz could have chosen, but only one of these sets has a total consisting of palindromic numerator and denominator when expressed in lowest terms.

      3/5 + 7/8 + 6/9 + 4/12 = 99/40
      3/5 + 7/8 + 6/9 + 2/14 = 1919/840
      4/5 + 6/8 + 3/12 + 7/9 = 116/45
      3/6 + 5/9 + 7/8 + 4/12 = 163/72
      3/6 + 5/9 + 7/8 + 2/14 = 1045/504
      4/6 + 5/9 + 7/8 + 3/12 = 169/72
      5/6 + 4/8 + 3/12 + 7/9 = 85/36
      4/8 + 6/7 + 5/9 + 3/12 = 545/252 [*** SOLUTION ***]
      3/9 + 6/7 + 5/8 + 4/12 = 361/168
      3/9 + 6/7 + 5/8 + 2/14 = 47/24

      Like

  • Unknown's avatar

    Jim Randell 8:13 pm on 9 August 2019 Permalink | Reply
    Tags:   

    Teaser 2968: Gardening division 

    From The Sunday Times, 11th August 2019 [link] [link]

    George and Martha’s garden is a perfect square of length (whole number of metres) a two-digit number AB. The area is a three-digit number CDE. In the middle, they have planted a square flowerbed of a length which is a single-digit number F and area a two-digit number GH.

    They have called in a gardener, who works for a single-digit I hours. He works for a whole number of minutes on the flowerbed and the remainder on the surrounding lawn. Each square metre of the flowerbed requires N (a single digit) times the time spent on each square metre of the surrounding lawn. I have mentioned nine letters, A-I inclusive, and each stands for a different positive digit.

    How many minutes does the gardener work on the lawn?

    [teaser2968]

     
    • Jim Randell's avatar

      Jim Randell 8:29 pm on 9 August 2019 Permalink | Reply

      We can express the puzzle as a set of alphametic constraints and then use the general alphametic solver [[ SubstitutedExpression() ]] from the enigma.py library to find the solution.

      The following run file executes in 140ms.

      #! python -m enigma -rr
      
      SubstitutedExpression
      
      --distinct="ABCDEFGHI"
      --digits="1-9"
      
      "AB**2 = CDE"
      "F**2 = GH"
      
      "div(CDE - GH + N * GH, I * 60)"
      
      --answer="div((CDE - GH) * I * 60, CDE - GH + N * GH)"
      

      Solution: The gardener worked on the lawn for 99 minutes.

      The garden is a square of side 24m, giving a total area of 576m².

      The flowerbed has sides of 9m, so has an area of 81m², leaving an area of 495m² of lawn.

      The gardener works on the flowerbed for 81 minutes, at a rate of 1 minute per square metre of flowerbed. He then works on the lawn 5 times faster, at a rate of 1 minute per 5 square metres of lawn, so the 495m² of lawn takes 99 minutes. The total time is therefore 180 minutes, or 3 hours.

      Like

  • Unknown's avatar

    Jim Randell 5:47 pm on 2 August 2019 Permalink | Reply
    Tags:   

    Teaser 2967: Odds and evens 

    From The Sunday Times, 4th August 2019 [link] [link]

    I have done a “long multiplication”, which is reproduced above. [If the multiplication was ABC × DE, then the third line shows the result of ABC × E and the fourth line shows the result of ABC × D]. However instead of writing the actual digits involved, I have written “O” where there is an odd digit and “E” where there is an even digit.

    What is the result of the multiplication?

    [teaser2967]

     
    • Jim Randell's avatar

      Jim Randell 5:59 pm on 2 August 2019 Permalink | Reply

      (See also: Enigma 1242, Enigma 1721, Enigma 109, Enigma 1503).

      We can use the [[ SubstitutedExpression() ]] solver from the enigma.py library to solve this.

      The following run file executes in 140ms.

      Run: [ @repl.it ]

      #! python -m enigma -rr
      
      #     A B C
      #  *    D E
      #   -------
      #   J K L M (= ABC * E)
      #   N P Q   (= ABC * D)
      #   -------
      #   F G H I
      #   =======
      
      SubstitutedExpression
      
      --distinct=""
      --invalid="1|3|5|7|9,BCDEHIJLMNQ" # even digits
      --invalid="2|4|6|8,AFGKP" # odd digits
      --invalid="0,ADFGJKNP" # odd digits + leading even digits
      
      "ABC * DE = FGHI"
      
      "ABC * E = JKLM"
      "ABC * D = NPQ"
      

      Solution: The result of the multiplication sum is 9744.

      The full sum is:

      348 × 28 = 2784 + 696×10 = 9744

      Like

    • GeoffR's avatar

      GeoffR 8:45 am on 5 August 2019 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 0..9:A; var 0..9:B; var 1..9:C; 
      var 0..9:D; var 0..9:E; 
      var 0..9:F; var 0..9:G; var 0..9:H; var 0..9:I; 
      var 0..9:J; var 0..9:K; var 0..9:L; var 0..9:M; 
      var 0..9:N; var 0..9:P; var 0..9:Q;
      
      constraint A > 0 /\ D > 0 /\ J > 0 /\ N > 0 
      /\ K > 0/\ F > 0 /\ G > 0 /\ P > 0;
      
      % Allocate parity to the digits
      constraint A mod 2 == 1 /\ B mod 2 == 0 /\ C mod 2 == 0;
      constraint D mod 2 == 0 /\ E mod 2 == 0;
      constraint F mod 2 == 1 /\ G mod 2 == 1 /\ H mod 2 == 0
       /\ I mod 2 == 0;
      
      constraint J mod 2 == 0 /\ K mod 2 == 1 /\ L mod 2 == 0
       /\ M mod 2 == 0;
      constraint N mod 2 == 0 /\ P mod 2 == 1 /\ Q mod 2 == 0;
      
      % Components of multiplication sum
      var 100..999: ABC = 100*A + 10*B + C;
      var 10..99: DE = 10*D + E;
      var 1000..9999: JKLM = 1000*J + 100*K +10*L + M;
      var 1000..9999: NPQ = 1000*N + 100*P + 10*Q;
      var 1000..9999: FGHI = 1000*F + 100*G + 10*H + I;
      
      constraint ABC * DE == FGHI;
      constraint ABC * D * 10 == NPQ;
      constraint ABC * E == JKLM;
      
      solve satisfy;
      
      output ["Multiplication sum is " ++ show(ABC) ++ " * " 
      ++ show(DE) ++ " = " ++ show(JKLM) ++ " + " ++ show(NPQ)
       ++ " = " ++ show(FGHI) ];
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 6:52 pm on 26 July 2019 Permalink | Reply
    Tags:   

    Teaser 2966: On track 

    From The Sunday Times, 28th July 2019 [link] [link]

    Sarah and Jenny are runners who train together on a circular track, and Sarah can run up to 20 per cent faster than Jenny. They both run at a constant speed, with Sarah running an exact percentage faster than Jenny. To reduce competition they start at the same point, but run round the track in different directions, with Sarah running clockwise.

    On one day they passed each other for the seventh time at a point which is an exact number of degrees clockwise from the start. Sarah immediately changed her pace, again an exact percentage faster then Jenny. After a few [additional] passes both runners reached the exit, at a point on the track an exact number of degrees clockwise from the start, at the same time.

    How fast, relative to Jenny, did Sarah run the final section?

    [teaser2966]

     
    • Jim Randell's avatar

      Jim Randell 8:20 pm on 26 July 2019 Permalink | Reply

      If S is going p percent faster than J, she is going at rate of (1 + p/100) times as fast as J.

      If they meet after J has travelled through d degrees of the circle, then S has travelled through d(1 + p/100) degrees of the circle, and together these must make up the full circle. So:

      d + d(1 + p/100) = 360
      d = 36000 / (200 + p)

      And if they meet at an exact number of degrees after k passings:

      kd = 36000k / (200 + p)

      must be an integer.

      This Python program finds possible percentage increases for S where she meets J at an exact number of degrees for up to 7 passings. It runs in 81ms.

      Run: [ @repl.it ]

      from enigma import (irange, cproduct, printf)
      
      # suppose they meet after k passings and S runs p percent faster than J
      for (k, p) in cproduct([irange(1, 7), irange(1, 20)]):
        # do they meet at an exact number of degrees?
        if (36000 * k) % (200 + p) == 0:
          printf("k={k} p=+{p}% [{s}]", s=('initial' if k == 7 else 'final'))
      

      Solution: Sarah ran the final section 16% faster than Jenny.

      For the first section Sarah was running 10% faster than Jenny.

      And the final section lasted for some multiple of 3 crossings. Probably 3 or 6, as there are only “a few” additional passes, but we don’t need to know that to get the answer to the puzzle.

      Further solutions appear if we allow higher values of k. For example, at k = 11 we get a solution where S is 20% faster than J, but from the wording of the puzzle it seems likely that the number of passings in the final section is fewer than 7, so we get a unique answer.

      Like

    • John Crabtree's avatar

      John Crabtree 2:19 am on 27 July 2019 Permalink | Reply

      You could calculate the minimum k for any p. In Excel format:
      k = +(200 + p) / GCD(36000, 200 + p)
      Then if k < 8, print k and p

      I am not a Python programmer, but understand that Python does have a gcd function.

      Like

      • Jim Randell's avatar

        Jim Randell 8:07 am on 27 July 2019 Permalink | Reply

        @John: Python does indeed have [[ gcd() ]].

        We can generate the list of first k for each p, and then output them in k order:

        from enigma import (irange, gcd, div, printf)
        
        # find first k for each p
        kps = ((div(200 + p, gcd(36000, 200 + p)), p) for p in irange(1, 20))
        
        # output (k, p) pairs, ordered by k
        for (k, p) in sorted(kps):
          printf("k={k} p=+{p}%")
        

        Like

      • Jim Randell's avatar

        Jim Randell 2:19 pm on 1 August 2019 Permalink | Reply

        Here’s a program that uses a similar approach to generate the solutions in a given range (in this case p = 1..20, k = 1..7, like my first program):

        from enigma import (irange, fraction, printf)
        
        # consider values for p
        for p in irange(1, 20):
          (a, b) = fraction(36000, 200 + p)
          # consider values for k
          for k in irange(b, 7, step=b):
            printf("k={k} p=+{p}% [{s}]", s=('initial' if k == 7 else 'final'))
        

        Like

    • Robert Brown's avatar

      Robert Brown 11:35 am on 1 August 2019 Permalink | Reply

      For each p value, you found equivalent k value. I reversed this, leading to an easy manual solution.
      At k passings, J has travelled 180k+x and S has travelled 180k–x giving J/S = (180k+x)/(180k–x).
      (x = integer, k is prime to avoid duplication). This gives the following rapid 3 line solution:

      k = 7 J/S = 1260+x / 1260-x By inspection, x = 60 giving J/S = 1.10
      k = 2 J/S = 360+x / 360-x By inspection, x = 60 giving J/S = 1.40 (too large)
      k = 3 J/S = 540+x / 540-x By inspection, x = 40 giving J/S = 1.16 (the answer)

      Like

  • Unknown's avatar

    Jim Randell 6:21 pm on 19 July 2019 Permalink | Reply
    Tags:   

    Teaser 2965: Knock, knock! 

    From The Sunday Times, 21st July 2019 [link] [link]

    Last year a two-figure number of teams entered our football competition. With that number, it was impossible to have a straightforward knockout competition (where half the teams are knocked out in each round), so we divided the teams into equal-sized groups, each pair of teams within a group played each other once, and the overall winner from each group went forward to the second stage consisting of a knockout competition. Unfortunately our local team was knocked out in the quarter-finals of that stage.

    This year a higher number of teams entered (but not twice as many). Again a straightforward knockout competition was impossible so we copied last year’s model but with smaller groups and more of them. By coincidence the total number of games played this year equalled the number played last year.

    How many teams entered last year and how many this year?

    [teaser2965]

     
    • Jim Randell's avatar

      Jim Randell 7:01 pm on 19 July 2019 Permalink | Reply

      In order to have a knockout tournament (without using byes) the number of teams needs to be a power of 2 (half the teams are knocked out at each stage).

      So the numbers of teams we are dealing with cannot be powers of two. But we can divide the numbers into groups where the winners of the groups can have a knockout tournament, so the number of groups must be a power of 2. Hence the total number of teams has to have a divisor that is a power of 2.

      Within a group of size m, the number of matches where each team plays each other team is T(m − 1).

      This Python program looks for 2-digit values for the number of teams last year, works out the total number of matches played in the tournament, and then finds a scenario for this year which has the same total number of matches. It runs in 91ms.

      Run: [ @replit ]

      from enigma import (irange, div, tri, bit_permutations as powers2, printf)
      
      # check a positive integer is a power of 2
      is_power2 = lambda n: not (n & (n - 1))
      
      # number of teams last year (a 2-digit number)
      for n in irange(24, 99, step=8):
        # skip numbers that are powers of 2
        if is_power2(n): continue
      
        # divide n into k groups of m (k is a power of 2)
        # a team was knocked out in the quarter finals, so k > 7
        for k in powers2(8):
          m = div(n, k)
          if m is None: break
          # calculate the total number of games played
          t = k * tri(m - 1) + (k - 1)
      
          # now look for possible values with the same total, but with smaller groups
          for m2 in irange(3, m - 1):
            # and m2 must not be a power of 2
            if is_power2(m2): continue
            # calculate the number of groups
            k2 = div(t + 1, tri(m2 - 1) + 1)
            if k2 is None: continue
            # there must be more groups
            if not (k2 > k): continue
            # k2 must be a power of 2
            if not is_power2(k2): continue
            # the total number of teams this year
            n2 = k2 * m2
            # and n2 greater than n, but not twice n
            if not (n2 > n and n2 != n * 2): continue
      
            printf("t={t}: last year = {n} teams ({k} groups of {m}), this year = {n2} teams ({k2} groups of {m2})")
      

      Solution: 56 teams entered last year. 80 teams entered this year.

      Last year the 56 teams were formed into 8 groups of 7. Each group would play 21 matches, and then the 8 winners of the groups would play 4 quarter-finals, 2 semi-finals and 1 final to give 175 matches in total.

      This year the 80 teams were formed into 16 groups of 5. Each group would play 10 matches, and then the 16 winners of the groups would play 8 eighth-finals, 4 quarter-finals, 2 semi-finals and 1 final to also give 175 matches in total.


      As a team was knocked out in the quarter-finals last year, the number of groups must have been at least 8, and we can consider multiples of 8 (that are not exact powers of 2). So there are only 8 candidate numbers for the number of teams last year: 24, 40, 48, 56, 72, 80, 88, 96.

      There are two “near miss” scenarios:

      48 teams last year (8 groups of 6), and 96 teams this year (32 groups of 3). Both have 127 matches.
      96 teams last year (16 groups of 6), and 192 teams this year (64 groups of 3). Both have 255 matches.

      But both are eliminated by the requirement that the number of teams this year is not twice the number of teams last year.

      When I initially read the puzzle I took “not twice as many” to mean “fewer than twice as many”, but in my program I relaxed this condition to “not exactly twice as many”, and the single solution remains.

      There is also the question of whether, in the knockout tournament, there is a match to decide 3rd and 4th places. It doesn’t matter if there is or not, as long as both tournaments use the same format. If there is a match for the semi-final losers then the total numbers of matches will be increased by 1.

      Like

    • Jim Randell's avatar

      Jim Randell 12:52 pm on 22 July 2019 Permalink | Reply

      Here is a MiniZinc model for the puzzle. It executes in 66ms.

      %#! minizinc -a
      
      % powers of 2
      set of int: pow2 = { pow(2, i) | i in 1..9 };
      
      
      % last year: n teams, k groups of m
      var 10..99: n; % n is a 2 digit number
      var 3..33: k;
      var 5..99: m;
      
      % n can be divided into k groups of m;
      % n is not a power of 2
      % k is a power of 2
      % m is not a power of 2
      constraint k * m = n;
      constraint not(n in pow2);
      constraint k in pow2;
      constraint not(m in pow2);
      
      % k is at least 8
      constraint not(k < 8);
      
      
      % this year: n1 teams, k1 groups of m1
      var 11..1000: n1;
      var 4..334: k1;
      var 3..98: m1;
      
      constraint n1 = k1 * m1;
      constraint not(n1 in pow2);
      constraint k1 in pow2;
      constraint not(m1 in pow2);
      
      % more teams, but not twice as many
      constraint n1 > n;
      constraint n1 != 2 * n;
      
      % smaller groups, but more of them
      constraint m1 < m;
      constraint k1 > k;
      
      % total number of matches is the same
      constraint k * (m * (m - 1) + 2) = k1 * (m1 * (m1 - 1) + 2);
      
      solve satisfy;
      

      I wasn’t sure how use the neat trick to test for powers of 2 in MiniZinc, so I assumed an upper bound of 1,000 teams, and just made a set of powers of 2 less than this.

      Like

    • Lise Andreasen's avatar

      Lise Andreasen 2:50 pm on 6 June 2024 Permalink | Reply

      I think it’s possible to figure this out on paper, but there are a lot of restrictions to deal with.
      9 < x < 100
      x < y < 2x
      x = m * 2^k
      y = n * 2^l
      (that’s an L)
      l > k
      2 < n < m
      2^k or 2^l groups
      m or n members of each group
      Neither m nor n can be a power of 2
      There are this number of matches the first year:
      2^k * m(m-1)/2 + 2^k – 1
      And the second year:
      2^l * n(n-1)/2 + 2^l – 1
      These 2 numbers are the same
      A little calculation gives:
      m(m-1) + 2 = 2^(l-k) * [n(n-1) + 2]
      (I hope I got that one right!)
      Now it's possible to systematically go through all the possibilities.
      Like, k = 3, l = 4, n = 3, is m integer? And so on.
      Neat puzzle!

      Like

    • Frits's avatar

      Frits 7:38 pm on 6 June 2024 Permalink | Reply

      Comparing triangular numbers.

      tri = lambda n: (n * (n + 1)) // 2
      
      # powers of 2 (upper bound is not important as breaks are used)
      ps2 = [1 << i for i in range(1, 10)]
      
      # maximum number of teams last year is 96 (a multiple of 8)
      # t = number of teams per group
      # ngroups * t < 192 with ngroups >= 8 (quarter finals) so nteams < 24
      
      # nmatches = ngroups * (tri(t - 1) + 1) - 1  
      d = {tri(t - 1) + 1: t for t in range(2, 24) if t & (t - 1)} 
      mx = max(d)
      
      # last: matches = g * d[k2] - 1
      # this: matches = q * g * d[k1] - 1  where q = k2 / k1 and q is a power of 2
      for k1 in d.keys():
        for q in ps2:
          # k2 must be a multiple of k1
          if (k2 := q * k1) > mx: break
          if k2 not in d: continue
        
          # try different number of groups
          for g in ps2:
            if g < 8: continue
            if (nlast := g * d[k2]) > 99: break
            if (nthis := q * g * d[k1]) >= 2 * nlast: break
           
            print("answer:", nlast, "and", nthis)     
      

      Like

  • Unknown's avatar

    Jim Randell 6:18 pm on 12 July 2019 Permalink | Reply
    Tags:   

    Teaser 2964: “Bingo a go-go” lingo a no-go 

    From The Sunday Times, 14th July 2019 [link] [link]

    My rest home’s Bingo set uses numbers 1 to 99. To win, nine numbers on your game card must be called. Our caller, not knowing “bingo-lingo”, says “Number 1, total factors 1”, “Number 11, total factors 2” and “Number 30, total factors 8”, etc.

    Yesterday, in one game, my hearing aid howled whenever a call started. I missed each number, but heard each “total factors” value. Fortunately, after just nine calls I shouted “HOUSE!” certain that I’d won.

    I told my daughter how many different “factor” values I’d heard, but didn’t say what any of the values were. Knowing that I had won after nine calls, she could then be sure about some (fewer than nine) of my winning numbers.

    Find, in ascending order, the numbers that she could be sure about.

    [teaser2964]

     
    • Jim Randell's avatar

      Jim Randell 6:43 pm on 12 July 2019 Permalink | Reply

      (See also: Enigma 1004 for another puzzle that involves counting divisors).

      This Python program groups the numbers from 1 to 99 into collections that have the same number of divisors, and then looks for groups of those collections that give a set of exactly 9 numbers, and these groups are recorded by the size of the group.

      We can then find groups of the same size that have a non-empty set of fewer than 9 numbers in common, and this gives our solution.

      It runs in 78ms.

      Run: [ @repl.it ]

      from enigma import (defaultdict, irange, tau, subsets, flatten, intersect, printf)
      
      # consider the numbers, and group them by number of divisors
      g = defaultdict(list)
      for n in irange(1, 99):
        t = tau(n)
        g[t].append(n)
      
      # [optional] we can discard groups with > 9 elements
      g = dict((k, v) for (k, v) in g.items() if not (len(v) > 9))
      
      # collect possible keys that give a set of 9 numbers
      # grouped by the total number of keys
      rs = defaultdict(list)
      for ks in subsets(g.keys()):
        ns = flatten(g[k] for k in ks)
        if not (len(ns) == 9): continue
        
        n = len(ks)
        printf("[{n}: {ks} -> {ns}]")
        rs[n].append(ns)
      
      # find groups with more than 0, but less than 9 elements in common
      for (n, ns) in rs.items():
        s = intersect(ns)
        if not (0 < len(s) < 9): continue
      
        # output solution
        printf("{s} [n={n}]", s=sorted(s))
      

      Solution: The 7 numbers she could be sure about are: 1, 4, 9, 25, 36, 49, 64.

      The daughter was told that 5 different “factor” values were heard, so she knows the divisors are either:

      (1, 3, 5, 7, 9), which identify the numbers (1, 4, 9, 16, 25, 36, 49, 64, 81); or:
      (1, 3, 7, 9, 10), which identify the numbers (1, 4, 9, 25, 36, 48, 49, 64, 80)

      So the solution is given by the subset of the numbers that have 1, 3, 7, or 9 divisors.

      1 is the only number with 1 divisor.
      4, 9, 25, 49 (the squares of primes) have 3 divisors.
      64 (a prime to the power of 6) has 7 divisors
      36 (the square of the product of two different primes) has 9 divisors.

      Like

  • Unknown's avatar

    Jim Randell 5:26 pm on 5 July 2019 Permalink | Reply
    Tags:   

    Teaser 2963: A result 

    From The Sunday Times, 7th July 2019 [link] [link]

    For any number, I square the digits and then add the resulting numbers. If necessary, I keep repeating the process until I end up with a single digit, called the result. For example: 142 gives 1 + 16 + 4 = 21 which then gives 4 + 1 = 5, the result.

    I have written down a two-digit number. If I tell you one of the digits [the key digit], you should be able to work out the result.

    I then use a 3rd digit to get a three-digit number. The result of that number happens to be the key digit.

    In increasing order, what are the three digits?

    [teaser2963]

     
    • Jim Randell's avatar

      Jim Randell 5:59 pm on 5 July 2019 Permalink | Reply

      The following Python program runs in 90ms.

      Run: [ @repl.it ]

      from enigma import (nsplit, subsets, irange, unpack, filter_unique, printf)
      
      # process a sequence of digits
      def process(ds):
        while True:
          n = sum(d * d for d in ds)
          if n < 10: return n
          ds = nsplit(n)
      
      # collect the results for 2 digit numbers
      ss = list((ds, process(ds)) for ds in subsets(irange(0, 9), size=2, select='R') if ds != (0, 0))
      
      # if I tell you "one of the digits is <k>" you should be able to work out the result
      for k in irange(0, 9):
        (rs, _) = filter_unique(ss, unpack(lambda ds, r: k in ds), unpack(lambda ds, r: r))
      
        # consider possible 2-digit sequences
        for (ds, _) in rs:
          # and add an extra digit
          for x in irange(0, 9):
            # the result should be the digit <k>
            if process(ds + (x,)) == k:
              printf("k={k}: {ds} + {x}")
      

      Solution: The three digits are: 5, 6, 9.

      The order of the digits in a number does not matter. 24 will have the same result as 42 (both are 2² + 4² = 20 → 2² + 0² = 4).

      The key digit is 5. Any 2-digit sequence that contains a 5 has a result of 4.

      The initial number is one of: 56, 59, 65, 95. An extra digit is added so the three digit sequence consists of the digits 5, 6, 9 (in some order). And this sequence has a result of 5.


      Most of the 2-digit numbers give a result of 4, and if the process is allowed to continue summing the squares of the digits we see the following cycle emerge:

      4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4

      Numbers that eventually result in this cycle are known as “unhappy numbers” (see [ link ]).

      The other 2-digit numbers give results of 1, 2, 5, 8, 9, we can also continue the process with these values:

      1 → 1
      2 → 4
      5 → 25 → 29 → 85 → 89 → … → 4
      8 → 64 → 52 → 29 → … → 4
      9 → 81 → 65 → 61 → 37 → … → 4

      We see that any numbers with a result of 2, 5, 8, 9 are also “unhappy”, and only those numbers that have a result of 1 are “happy”. (See OEIS A124095 [ link ]).

      Like

      • Jim Randell's avatar

        Jim Randell 3:54 pm on 7 July 2019 Permalink | Reply

        Here’s a simpler program to solve the puzzle.

        Run: [ @repl.it ]

        from enigma import (nsplit, seq_all_same, irange, subsets, printf)
        
        # process a sequence of digits
        def process(*ds):
          while True:
            n = sum(d * d for d in ds)
            if n < 10: return n
            ds = nsplit(n)
        
        # look for possible key digits
        for k in irange(0, 9):
          # must give the same result when combined with all other digits
          if seq_all_same(process(k, d) for d in irange(0, 9) if k + d > 0):
        
            # look for two additional digits to give a result of k
            for (a, b) in subsets(irange(0, 9), size=2, select='R'):
              if process(k, a, b) == k and k + a + b > 0:
                printf("k={k}: {s}", s=sorted([k, a, b]))
        

        Like

  • Unknown's avatar

    Jim Randell 5:48 pm on 28 June 2019 Permalink | Reply
    Tags:   

    Teaser 2962: Book receipts 

    From The Sunday Times, 30th June 2019 [link] [link]

    My wife recently purchased two books from her local bookshop. She showed me the receipt, which showed the cost of each book and the three-figure total cost. I noticed that all of the digits from 1 to 9 had been printed. Coincidentally, exactly the same happened to me when buying two different books, but my more expensive book cost more than hers. In fact, it would not have been possible for that book to have cost more.

    How much did I pay for the more expensive book?

    [teaser2962]

     
    • Jim Randell's avatar

      Jim Randell 5:57 pm on 28 June 2019 Permalink | Reply

      Assuming each digit from 1 to 9 is used exactly once, we can consider the following alphametic sum:

      ABC + DEF = GHI

      Which gives the prices of the books, and the total in whatever currency units we are using.

      This Python program uses a couple of useful routines from the enigma.py library to solve the puzzle.

      It runs in 163ms.

      Run: [ @replit ]

      from enigma import (SubstitutedExpression, Accumulator, irange, printf)
      
      # the alphametic sum
      p = SubstitutedExpression(
        [ "ABC + DEF = GHI", "A > D" ],  # "ABC > DEF"
        digits=irange(1, 9),
        answer="ABC",
        verbose=0
      )
      
      # find the maximum answer
      r = Accumulator(fn=max, collect=1)
      r.accumulate_data_from(p.solve(), value=1, data=0)
      
      # output the solution
      for s in r.data:
        t = p.substitute(s, "ABC + DEF = GHI")
        printf("max summand = {r.value} [{t}] [{n} sums]", n=r.count)
      

      Solution: The more expensive book cost 784 currency units.

      There are 168 possible sums, and the largest possible summand is 784, making the sum:

      784 + 152 = 936

      If the digit 0 is allowed (but we are still looking for 9 different digits) then there are 544 possible sums, and the largest possible summand is 847, in the sum:

      847 + 106 = 953

      Like

    • GeoffR's avatar

      GeoffR 12:11 pm on 3 March 2020 Permalink | Reply

      from itertools import permutations
      
      from collections import defaultdict
      DI = defaultdict(list) 
      
      for p in permutations('123456789'):
          A, B, C, D, E, F, G, H, I = p
          ABC = int(A + B + C)
          DEF =int(D + E + F)
          GHI = int(G + H + I)
          # ABC is most expensive book below
          if ABC > DEF and ABC + DEF == GHI:
              DI[ABC] += [(ABC, DEF, GHI)]
              
      L = []  # List of most expensive books in equation
      
      for K in DI.keys():
          L.append(K)
      
      print(f"Most expensive book costs {max(L)} currency units")
      # Most expensive book costs 784 currency units
      
      
      

      I also found that the summands 546 and 654 both had six solutions to the alphametic equation.

      Like

  • Unknown's avatar

    Jim Randell 11:54 am on 21 June 2019 Permalink | Reply
    Tags:   

    Teaser 2961: Alan and Cat 

    From The Sunday Times, 23rd June 2019 [link] [link]

    Alan and Cat live in a city which has a regular square grid of narrow roads. Avenues run west/east, with 1st Avenue being the furthest south, while Streets run south/north with 1st Street being the furthest west.

    Cat lives at the intersection of 1st Street and 1st Avenue, while Alan lives at an intersection due northeast from Cat. On 1 January 2018, Cat walked to Alan’s house using one of the shortest possible routes (returning home the same way), and has done the same every day since. At first, she walked a different route every day and deliberately never reached an intersection where the Street number is less then the Avenue number. However, one day earlier this year she found that she could not do the same, and repeated a route.

    What was the date then?

    [teaser2961]

     
    • Jim Randell's avatar

      Jim Randell 12:20 pm on 21 June 2019 Permalink | Reply

      We have encountered problems similar to this before, see: Enigma 1108.

      The puzzle can be solved using Catalan’s Triangle [ link ], hence the names Cat and Alan.

      This Python program counts the paths constructively. It runs in 95ms.

      Run: [ @repl.it ]

      import datetime
      from enigma import (irange, inf, cached, printf)
      
      # count paths from (0, 0) to (x, y) where x =< y
      @cached
      def paths(x, y):
        if x == 0: return 1
        n = paths(x - 1, y)
        if x < y: n += paths(x, y - 1)
        return n
      
      for n in irange(1, inf):
        p = paths(n, n)
        printf("[{n} -> {p} paths]")
        if p < 365: continue
        if p > 538: break
        d = datetime.date(2018, 1, 1) + datetime.timedelta(p)
        printf("first repeat on date = {d}")
      

      Solution: The date of the first repeat was 6th March 2019.


      Instead of counting the paths we can use the formula for Catalan numbers:

      import datetime
      from enigma import (C, irange, inf, printf)
      
      # generalised Catalan numbers
      def catalan(n, k, m=1):
        if k > n + m - 1:
          return 0
        elif 0 <= k < m:
          return C(n + k, n)
        else:
          return C(n + k, k) - C(n + k, k - m)
      
      for n in irange(1, inf):
        p = catalan(n, n)
        printf("[{n} -> {p} paths]")
        if p < 365: continue
        if p > 538: break
        d = datetime.date(2018, 1, 1) + datetime.timedelta(p)
        printf("first repeat on date = {d}")
      

      Like

  • Unknown's avatar

    Jim Randell 11:16 pm on 14 June 2019 Permalink | Reply
    Tags:   

    Teaser 2960: Bags of sweets! 

    From The Sunday Times, 16th June 2019 [link] [link]

    I recently bought a number of equally priced bags of sweets for a bargain price, spending more than 50p in total. If they had been priced at 9p less per bag, I could have had 2 bags more for the same sum of money. In addition, if each had cost 12p less than I paid, then I could also have had an exact number of bags for the same sum of money.

    How much did I spend in total on the sweets?

    [teaser2960]

     
    • Jim Randell's avatar

      Jim Randell 11:47 pm on 14 June 2019 Permalink | Reply

      If we buy n bags of sweets at x pence per bag, then the total outlay n.x can be expressed as:

      n.x = (n + 2)(x − 9)
      n.x = k(x − 12)
      n.x > 50

      (for some whole number k, where n > 1).

      From which we see:

      x = (18 + 9n) / 2

      This Python program finds the first value of n that satisfies the conditions and gives an integer value for k.

      Run: [ @repl.it ]

      from enigma import (Rational, irange, inf, div, printf)
      
      Q = Rational()
      
      # consider n the number of bags of sweets bought
      for n in irange(1, inf):
        x = Q(18 + 9 * n, 2)
        t = n * x
        if not (t > 50): continue
      
        # find the number of bags if the prices were 12p less
        k = div(t, x - 12)
        if k is None: continue
      
        printf("{t}p = {n} bags @ {x}p [= {n2} bags @ {x9}p = {k} bags @ {x12}p]", n2=n+2, x9=x-9, x12=x-12)
        break
      

      Solution: The total spend was 216p.


      With a bit more analysis we can show this is the only solution.

      We can write an expression for k as:

      k = 9n(n + 2) / (9n − 6) = n + 8/3 + 16 / (9n − 6)

      And this only gives a whole number when 16 / (9n − 6) has a fractional part of 1/3.

      This is only possible for n = 1, 2, 6.

      n = 1 gives x = 13.5p, n.x = 13.5p, which is not more than 50p (and we want n > 1 anyway).

      n = 2 gives x = 18p, n.x = 36p, which is not more than 50p.

      n = 6 gives x = 36p, n.x = 216p, so this is the solution.

      Here is a program that uses this analysis to consider all possible solutions, by looking at the divisors of 48:

      from enigma import (Rational, divisors, div, printf)
      
      Q = Rational()
      
      # consider divisors of 48
      for d in divisors(48):
        # we only want divisors of the form (3z + 1)
        if not (d % 3 == 1): continue
        # compute n
        n = div(48 // d + 6, 9)
        if n is None: continue
        # compute x and t
        x = Q(18 + 9 * n, 2)
        t = n * x
        if not (t > 50): continue
        # compute k
        k = div(9 * n * (n + 2), 9 * n - 6)
        # output solution
        printf("[d={d}] n={n} x={x} t={t} k={k}")
      

      Removing the check at line 15 will give all three solutions for the equations.

      Like

    • GeoffR's avatar

      GeoffR 6:49 pm on 16 June 2019 Permalink | Reply

      We can put Jim’s initial three equations into a MinZinc constraint for an easy solution

      % A Solution in MiniZinc
      include "globals.mzn";
       
      var 1..50: n;   % no of bags bought originally
      var 1..50: k;   % no bags bought at 12p less
      var 1..100: x;  % original cost per bag (pence)
      
      constraint n * x > 50 /\ n * x == (n + 2) * (x - 9) 
      /\ n * x = k * (x - 12);
      
      solve satisfy;
      output ["Total spent on sweets = " ++ show(n * x) ++ " pence" ];
      

      Like

      • Jim Randell's avatar

        Jim Randell 8:46 am on 17 June 2019 Permalink | Reply

        @GeoffR: This approach works OK for cases where the price per bag is a whole number (which is the case in the actual solution).

        I didn’t assume that and found there were 3 candidate solutions that satisfied the 2 equations, one of which has the bags priced with a fractional amount. Two of the candidates are eliminated by the inequality (including the one where the bags are priced a fractional amount), leaving a single solution.

        Like

    • GeoffR's avatar

      GeoffR 3:12 pm on 17 June 2019 Permalink | Reply

      @Jim: I can see you are making a mathematical point about prices for fractional amounts, but is this applicable for this teaser ?

      We don’t have fractional pennies these days in our monetary system, so maybe we should assume that prices per bag are in whole numbers of pennies ?

      Like

      • Jim Randell's avatar

        Jim Randell 4:56 pm on 18 June 2019 Permalink | Reply

        @GeoffR: It was just a comment to try and extract a bit more interest from a relatively straightforward puzzle.

        I try not to make additional assumptions about the puzzle if I can help it. From the formula for x we see that the price per pack is a whole number of half-pennies, so it seemed reasonable to allow this. And we do get an extra potential solution if we do. Although this solution is then removed by the “more than 50p” requirement, so it doesn’t really matter if we consider it or not.

        Like

  • Unknown's avatar

    Jim Randell 7:08 pm on 7 June 2019 Permalink | Reply
    Tags:   

    Teaser 2959: The Magnificent Seven 

    From The Sunday Times, 9th June 2019 [link] [link]

    After a day’s filming, a group of those involved in the film’s production went for a gallop.

    They split into threes, with a samurai leading each grouping.

    The seven samurai were:

    BRONSON, BRYNNER, BUCHHOLZ, COBURN, DEXTER, MCQUEEN and VAUGHN.

    The others involved in the gallop were:

    ALANIZ, ALONZO, AVERY, BISSELL, BRAVO, DE HOYOS, HERN, LUCERO, NAVARRO, RUSKIN, RUSSELL, SUAREZ, VACIO and WALLACH.

    For each grouping, any two names from the three had exactly 2 letters in common (e.g., BRYNNER and BRAVO have B and R in common).

    If I told you who accompanied BRONSON, you should be able to tell me who accompanied (a) MCQUEEN and (b) DEXTER.

    [teaser2959]

     
    • Jim Randell's avatar

      Jim Randell 11:16 pm on 7 June 2019 Permalink | Reply

      This Python program runs in 116ms.

      Run: [ @repl.it ]

      from enigma import (grouping, subsets, diff, unpack, filter_unique, printf)
      
      # the "others"
      others = (
        'ALANIZ', 'ALONZO', 'AVERY', 'BISSELL', 'BRAVO', 'DE HOYOS', 'HERN',
        'LUCERO', 'NAVARRO', 'RUSKIN', 'RUSSELL', 'SUAREZ', 'VACIO', 'WALLACH'
      )
      
      # selection function
      fn = grouping.share_letters(2)
      
      # find a gang for leader x, with remaining members chosen from ys
      def gang(x, ys):
        for (y, z) in subsets((y for y in ys if fn(x, y)), size=2):
          if fn(y, z):
            yield (y, z)
      
      # find multiple gangs, with leaders from x, followers from ys
      def gangs(xs, ys, gs=[]):
        # are we done?
        if not xs:
          yield gs
        else:
          # find a gang for the first leader
          for g in gang(xs[0], ys):
            # and solve for the rest
            yield from gangs(xs[1:], diff(ys, g), gs + [g])
      
      # record possible values for (g1, g2, g3)
      vs = list()
      
      # find possible 2-gangs led by BRONSON, DEXTER, MCQUEEN
      for gs in gangs(["BRONSON", "DEXTER", "MCQUEEN"], others):
        # check the remaining 2-gangs can be made with the remaining followers
        for _ in gangs(["BRYNNER", "BUCHHOLZ", "COBURN", "VAUGHN"], diff(others, *gs)):
          vs.append(gs)
          # we only need one example
          break
      
      # "if I told you who accompanied BRONSON ..."
      f = unpack(lambda B, D, M: B)
      # "... you could tell me who accompanied MCQUEEN and DEXTER"
      g = unpack(lambda B, D, M: (M, D))
      (ss, _) = filter_unique(vs, f, g)
      
      # output solutions
      for (B, D, M) in ss:
        printf("BRONSON + {B} -> DEXTER + {D}, MCQUEEN + {M}")
      

      Solution: (a) MCQUEEN was accompanied by HERN and RUSSELL. (b) DEXTER was accompanied by AVERY and DE HOYOS.

      There are only three possible ways that complete groupings can be made:

      BRONSON = BISSELL, DE HOYOS
      DEXTER = AVERY, LUCERO
      MCQUEEN = HERN, RUSSELL
      BRYNNER = NAVARRO, RUSKIN
      BUCHHOLZ = BRAVO, SUAREZ
      COBURN = ALONZO, VACIO
      VAUGHN = ALANIZ, WALLACH

      BRONSON = BISSELL, DE HOYOS
      DEXTER = AVERY, RUSSELL
      MCQUEEN = HERN, RUSKIN
      BRYNNER = LUCERO, NAVARRO
      BUCHHOLZ = BRAVO, SUAREZ
      COBURN = ALONZO, VACIO
      VAUGHN = ALANIZ, WALLACH

      BRONSON = BISSELL, LUCERO
      DEXTER = AVERY, DE HOYOS
      MCQUEEN = HERN, RUSSELL
      BRYNNER = NAVARRO, RUSKIN
      BUCHHOLZ = BRAVO SUAREZ
      COBURN = ALONZO, VACIO
      VAUGHN = ALANIZ, WALLACH

      Telling us the parters of BRONSON uniquely identifies the solution, so it must the last of these groupings.

      Like

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
Design a site like this with WordPress.com
Get started