Recent Updates Page 20 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 10:12 am on 12 September 2023 Permalink | Reply
    Tags:   

    Teaser 2651: Parsnip Farm 

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

    On Parsnip Farm there was a triangular field with one of its boundaries running north to south. From that boundary’s southernmost point Farmer Giles built a fence in an easterly direction, thus partitioning the field into two smaller triangular fields, with the area of the northern field being forty per cent of the area of the southern field. Each side of each field was a whole number of furlongs in length, one of the sides of the southern field being twenty-five furlongs in length.

    What are the lengths of the other two sides of the southern field?

    [teaser2651]

     
    • Jim Randell's avatar

      Jim Randell 10:12 am on 12 September 2023 Permalink | Reply

      If the area of the original field is A, then it is split such that the northern field has an area N = (2/7)A and the southern field S = (5/7)A.

      The boundaries of N are all integers and so form a Pythagorean triple (x, y, z).

      And we can expand the northern field by a factor of f until its hypotenuse exactly covers the boundary of the original field, and we get this:

      The we can then write the area of the original field in two ways:

      A = (7/2)N = 7xy / 4
      A = fxy / 2

      f = 7/2

      And we can calculate the unknown sides of S:

      z′ = (f − 1)z = 5z/2
      y′ = hypot(7x/2, 5y/2) = hypot(7x, 5y) / 2

      This Python program runs in 58ms. (Internal runtime is 334µs).

      Run: [ @replit ]

      from enigma import (pythagorean_triples, div, ihypot, ordered, printf)
      
      for (a, b, z) in pythagorean_triples(100):
        z_ = div(5 * z, 2)
        if z_ is None: continue
        N = ordered(a, b, z)
        for (x, y) in [(a, b), (b, a)]:
          y_ = div(ihypot(7 * x, 5 * y), 2)
          if y_ is None: continue
          S = ordered(x, z_, y_)
          if 25 in S:
            # output solution
            printf("N = {N}; S = {S}")
      

      Solution: The other two sides of the southern field are 6 and 29 furlongs.

      N is a (6, 8, 10) triangle, (area = 24 square furlongs ≈ 0.97 sq km).

      S is a (6, 25, 29) triangle, (area = 60 square furlongs ≈ 2.43 sq km).

      So the original field was a (8, 29, 35) triangle, (area = 84 square furlongs ≈ 3.40 sq km).

      Like

    • Frits's avatar

      Frits 5:44 pm on 12 September 2023 Permalink | Reply

      Avoiding imports.

       
      is_square = lambda n: int(rt := n**.5) == rt
      
      # generate Pythagoren triples for a fixed hypothenuse
      def triples(h):
        sqs = {i * i for i in range(1, h)}
        return [(int(s1**.5), int(s2**.5)) for s1 in sqs 
                 if (s2 := h**2 - s1) >= s1 and s2 in sqs]
        
      side = 25
      
      # can x be 25?  
      # then f.x = 87.5, y' can never be a whole number  (f = 3.5)
      # if other side (2.5y) is k.0 or k.5, so x != 25
      
      # can y' be 25?
      for c, d in triples(side): 
         # are these lenghts multiples of 2.5 and 3.5?
        x, y = -1, -1
        if (c % 2.5 == 0 and d % 3.5 == 0):
          y, x = c // 2.5, d // 3.5    
        if ((c % 3.5 == 0 and d % 2.5 == 0)):
          x, y = c // 3.5, d // 2.5    
        if x == -1: continue
        
        # y' can be 25
        if is_square(z2 := x**2 + y**2):
          z = int(z2**.5)
          if z % 2 == 0:
            print(f"answer {int(x)} and {int(2.5 * z)} furlongs")
        
      # can z' be 25?
      if side % 5: exit(0)
      z = int(side * 2 / 5)
      
      ts = triples(z)
      # determine z'
      for x, y in ts + [x[::-1] for x in ts]:
        if is_square(y1 := 3.5**2 * x**2 + 2.5**2 * y**2):
          print(f"answer {int(x)} and {int(y1**.5)} furlongs")  
      

      Like

  • Unknown's avatar

    Jim Randell 8:05 am on 10 September 2023 Permalink | Reply
    Tags:   

    Brain-Teaser 928: Confused contracts 

    From The Sunday Times, 4th May 1980 [link]

    The results of the hands in a bridge tournament were written like this: “Joe Smith, two ♥”. Before I could calculate the scores, my dog tore up the results of the last four players. Fortunately the writing remained legible. By manoeuvring the fragments, and knowing there had been one contract in each suit, and one at each of the one, two, three and four levels, I was able to construct various feasible combinations.

    I first tried putting ♦ opposite Ted, Pete and Reg in turn. Ted could have ♦ only when Mr Green had the two contract; Pete only when ♠ were four; and Reg only when Mr Black had the one. Similarly, if Reg or Mr Black had ♣, then Mr Green had four; If Mr White had ♥ or ♣ then Mr Black had the other; if Reg had ♥ then Pete had ♦; if Mr Brown had ♥ then Mr Black had four; if Mr Black had ♥ then Mr Green had two; and if Mr Black didn’t have ♥ then ♠ were in less than four.

    Mr Black could have one only when Pete had three ♠; Mr Green could have two only when ♥ were four; Mr Black had four only when Reg had ♦; Mr Green had four only when ♦ were in three; and ♣ could be in three or four only when Reg had ♥.

    Finally I noted that Ted and Vic had the same coloured suits whenever I tried putting ♠ with the three, but different coloured suits if Mr White did not have ♥.

    Luckily, I then remembered that ♦ had actually been bid at the four level.

    What was the suit of the three contract, and what was the full name of the player who bid it?

    This puzzle is included in the book The Sunday Times Book of Brainteasers (1994). The puzzle text above is taken from the book.

    [teaser928]

     
    • Jim Randell's avatar

      Jim Randell 8:06 am on 10 September 2023 Permalink | Reply

      I know nothing of Bridge, so at first the puzzle text made no sense to me, but there is a handy hint in the 1974 book:

      Ignoring the Bridge jargon, you have to match each of the numbers 1 to 4 with one of the suits, a forename, and a surname.

      I used the [[ SubstitutedExpression ]] solver to allocate the values among the three groups, so all we need to do is translate the text into a collection of constraints which we can represent by Python expressions.

      I translated: “If A had X or Y, then B had the other” into: “(A = X) ⇒ (B = Y)” and “(A = Y) ⇒ (B = X)”.

      Note that we might expect to deduce “Reg != Black” from the statement “if Reg or Mr Black had …”, but if we try this then there are no solutions.

      The following run file executes in 66ms. (Internal runtime of the generated code is 185µs).

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      # allocate values 1-4 to the following:
      #
      #  suits    : C D S H [Clubs, Diamonds, Spades, Hearts]
      #  forenames: T R P V [Ted, Reg, Pete, Vic]
      #  surnames : B K G W [Brown, blacK, Green, White]
      
      SubstitutedExpression
      
      --digits="1-4"
      --distinct="CDSH,TRPV,BKGW"
      
      # specify the conditions
      "implies(T == D, G == 2)"
      "implies(P == D, S == 4)"
      "implies(R == D, K == 1)"
      "implies(R == C or K == C, G == 4)"
      "implies(W == H, K == C)" "implies(W == C, K == H)"
      "implies(R == H, P == D)"
      "implies(B == H, K == 4)"
      "implies(K == H, G == 2)"
      "implies(K != H, S != 4)"
      "implies(K == 1, P == 3 == S)"
      "implies(G == 2, H == 4)"
      "implies(K == 4, R == D)"
      "implies(G == 4, D == 3)"
      "implies(C == 3 or C == 4, R == H)"
      "implies(S == 3, {T, V} in [{C, S}, {D, H}])"
      "implies(W != H, {T, V} not in [{C, S}, {D, H}])"
      
      # diamonds was the 4th contract
      --assign="D,4"
      
      # mention all the variables
      "true(C, D, S, H, T, R, P, V, B, K, G, W)"
      
      --template="(C D S H) (T R P V) (B K G W)"
      --solution=""
      

      Solution: The 3 contract was in hearts. It was bid by Pete Green.

      The contracts are fully defined:

      1♣ = Ted Brown
      2♠ = Reg Black
      3♥ = Pete Green
      4♦ = Vic White

      And we see that Reg = Black.

      Like

    • Frits's avatar

      Frits 4:06 pm on 11 September 2023 Permalink | Reply

      More than 200 lines of code.

      from itertools import combinations 
      
      # allocate values 1-4 to the following:
      #
      #  suits    : C D S H [Clubs, Diamonds, Spades, Hearts]
      #  forenames: T R P V [Tom, Reg, Pete, Vic]
      #  surnames : B K G W [Brown, blacK, Green, White]
      
      # 0/1/2 for no/some/all details
      detail = 1
      
      rev = lambda x: "neq" if x == "eq" else "eq"
      
      # a specific print format
      p_frz = lambda x, y: f"{x:>3}-{''.join(sorted(y))}"
      
      # add implication if <x> then <y> 
      def implies(x, y):
        if "=" in x:
          op1 = "eq" if "==" in x else "neq"
          op2 = "eq" if "==" in y else "neq"
          # use frozenset to make it hashable
          var1, var2 = frozenset([x[0], x[-1]]), frozenset([y[0], y[-1]])
          imp[(op1, var1)] = imp.get((op1, var1), []) + [(op2, var2)]
          # if a implies b then not b implies not a
          imp[(rev(op2), var2)] = imp.get((rev(op2), var2), []) + [(rev(op1), var1)]
        else:
          if x in imp:
            if y not in imp[x]:
              # check if y results in a falsehood
              if y == (rev(x[0]), x[1]):
                print(f"ERROR {x}-{y} is false")
               
              if y[1] in fb[x[1]] and x[0] == y[0] == "eq":  
                if detail: 
                  print(f"{p_frz(x[0], x[1])} is false as it leads to "
                        f"eq-{''.join(y[1])} which is not allowed")
                add_truth("neq", x[1])
              imp[x] += [y]
          else:
             imp[x] = [y]
      
      # print implications
      def print_imp(d):
        print()  
        for (a, b), vs in sorted(d.items()):
          print(f"{p_frz(a, b)}  : ", end=' ')
          for (c, d) in vs:
            print(f"{p_frz(c, d)}", end=', ')
          print()
        print()  
            
      # add entries to truth list <t>
      def add_truth(c, s):
        s_ = frozenset(s)
        if (c, s_) in t: return
        l_ = list(s)
        if detail: print("add to t:", p_frz(c, s_))
        t.add((c, s_))
        if c != "eq": return
        
        # add forbidden entries
        for f in fb[s_]:
          if detail > 1: print("add inherited rules to t:", p_frz("neq", f))
          t.add(("neq", f)) 
      
        toadd = []
        # propagate 'eq-ab': if 'neq-ac' exists then also 'neq-bc' must be true
        for d, f in t:
          if d != "neq": continue
          for i, x in enumerate(l_):
            if x not in f: continue
            o, = f.difference([x])
            if o not in bd[l_[1 - i]]:
              toadd.append(frozenset([l_[1 - i], o]))
      
        for x in toadd:
          add_truth("neq", x)
                  
      imp, fb, bd = dict(), dict(), dict()
      
      # specify the conditions
      implies("T == D", "G == 2")
      implies("P == D", "S == 4")
      implies("R == D", "K == 1")
      implies("W == H", "K == C") 
      implies("W == C", "K == H")
      implies("R == H", "P == D")
      implies("B == H", "K == 4")
      implies("K == H", "G == 2")
      implies("K != H", "S != 4")
      implies("K == 1", "P == 3")
      implies("K == 1", "P == S")
      implies("K == 1", "S == 3")
      implies("G == 2", "H == 4")
      implies("K == 4", "R == D")
      implies("G == 4", "D == 3")
      
      #implies("R == C or K == C", "G == 4")
      implies("R == C", "G == 4")
      implies("K == C", "G == 4")
      #implies("C == 3 or C == 4", "R == H")
      implies("C == 3", "R == H")
      implies("C == 4", "R == H")
      
      #implies("S == 3", "{T, V} in [{C, S}, {D, H}]")
      #implies("W != H", "{T, V} not in [{C, S}, {D, H}]")
      implies("S == 3", "W == H")
      
      types = [x.split() for x in ["C D S H", "T P R V", "B K G W", "1 2 3 4"]]
      # buddies
      bd = {x: [y for y in types[i] if y != x] 
                for i, tp in enumerate(types) for x in tp}
      # forbidden values
      for a, b in combinations(bd.keys(), 2):
        if b in bd[a]: continue
        fb[frozenset([a, b])] = [frozenset([a, x]) for x in bd[b]] + \
                                [frozenset([b, x]) for x in bd[a]] 
      
      if detail > 1:
        print("forbidden\n---------")
        for k, vs in sorted(fb.items()):
          print(''.join(k), end="  :  ")
          for v in vs:
            print(''.join(v), end=", ")
          print()
        print()  
      
      t = set()
      # diamonds was the 4th contract
      add_truth('eq', frozenset(['D', '4']))
      
      loop, ln = 1, len(t)
      while True:
      
        if detail:
          print(f"\nloop {loop}\n------")
          if loop < 3: print_imp(imp)
      
        if detail > 1:
          print(f"\ntruths\n------")
          for x in sorted(t, key = lambda x: (x[0], sorted(x[1]) ) ):
            print(p_frz(x[0], ''.join(sorted(x[1]))))
        
        # expand implications by chaining
        for k, vs in imp.items():
          for v in vs:
            # check if v is allowed ...
            if (rev(v[0]), v[1]) in t:
              # ... if not disallow k
              add_truth(rev(k[0]), k[1])
            
            if v in imp:
              # add implications of v to k
              for i in imp[v]:
                implies(k, i)
      
        # check for 3 non-equalities in a group
        toadd = []
        for c, f in t:
          if c != "neq": continue
          lst = list(f)
          # for both elements within f
          for i in range(2):
            y = [("neq", frozenset([x, lst[1-i]])) in t for x in bd[lst[i]]]
            if sum(y) != 2: continue
            # we have 3 neq's so the remaining entry in group must be eq
            toadd.append(frozenset([lst[1-i], bd[lst[i]][y.index(0)]]))
        
        for x in toadd:
          add_truth("eq", x)
        
        # only if normal logic has been exhausted
        if len(t) == ln:
          lookup = lambda d, x: [f for c, f in d if c == "eq" and x in f and 
                                 len(f | set("1234")) == 5]
              
          # implies("S == 3", "{T, V} in [{C, S}, {D, H}]")
          # implies("W != H", "{T, V} not in [{C, S}, {D, H}]")
          s3 = ("eq", frozenset(["S", "3"])) in t
          ns3 = ("neq", frozenset(["S", "3"])) in t
          if not s3 and not ns3: break
          
          # D is 4 so try to find H
          tH = lookup(t, "H")      
          if not tH: break
      
          tT, tV = lookup(t, "T"), lookup(t, "V")    
          if not tV and not tT: break
      
          H, = tH[0].difference(["H"]) 
          DH = {'4', H}
          
          vr, ot = "V" if tV else "T", "T" if tV else "V"
         
          v, = (tV[0] if tV else tT[0]).difference([vr]) 
      
          n = DH.difference([v]).pop() if v in DH else (set("1234") - DH - {v}).pop()
          add_truth("neq" if ns3 else "eq", frozenset([ot, n]))
        
        r3 = [''.join(f.difference(["3"])) for c, f in t if c == "eq" and '3' in f]
        # is there enough data in row 3 for the answer?
        if len(r3) == 3: 
          print(f"\nanswer: {r3[0]}, {r3[1]} and {r3[2]}") 
          exit(0)
        
        ln = len(t)  
        loop += 1     
      

      Like

  • Unknown's avatar

    Jim Randell 4:51 pm on 8 September 2023 Permalink | Reply
    Tags:   

    Teaser 3181: “No slack, Alice!” says Grace 

    From The Sunday Times, 10th September 2023 [link] [link]

    Grace mimicked Mr Dodgson: “Take two different positive odd numbers with no shared prime factor. Multiply the larger by their sum, giving the perimeter of a distinct right-angled triangle with whole-number sides. Only such values and their multiples work”.

    Alice created a loop from part of a 1m thread. She was able to pull it tightly on a pinboard into a right-angled triangle with whole-number cm sides in two ways (with different-shaped triangles).

    Alice then pulled the same loop tight over the thin polar spike of the classroom globe, down two meridians and along the equator. Thinking “Logic’s dead!”, she saw 90° equatorial angles and a non-zero polar angle, which obviously didn’t add to 180°.

    Grace calculated the polar angle to the nearest degree. Curiously, transposing its two digits gave the globe’s whole-number centimetre radius.

    Find this radius.

    [teaser3181]

     
    • Jim Randell's avatar

      Jim Randell 5:09 pm on 8 September 2023 Permalink | Reply

      If the string has length p and angle (in radians) made by the loop at the pole is 𝛂 on a globe of radius r, then we have:

      p = r(𝛑 + 𝛂)

      This Python program finds perimeters (that are whole numbers of centimetres, less than 100), such that (at least) two dissimilar Pythagorean triangles can be constructed, and then looks for a corresponding radius for a globe that fits the remaining conditions.

      It runs in 58ms. (Internal runtime is 296µs).

      from math import (pi, degrees)
      from enigma import (pythagorean_triples, group, item, fdiv, irange, intr, nrev, printf)
      
      # generate possible pythagorean triangles, return (<perimeter>, <triangles>)
      def generate(M):
        for ss in pythagorean_triples(M // 2):
          p = sum(ss)
          if p < M:
            yield (p, ss)
      
      # group pythagorean triangles by their perimeter
      g = group(generate(100), by=item(0), f=item(1))
      
      # consider possible perimeters
      for (p, ts) in g.items():
        if len(ts) < 2: continue
        printf("[p={p} -> {ts}]")
      
        # consider possible globe radii
        for r in irange(10, 99):
          # calculate the polar angle (to the nearest degree)
          a = intr(degrees(fdiv(p, r) - pi))
          if a > 99: continue
          if a < 10: break
          if a == nrev(r):
            printf("-> r={r} a={a}")
      

      Solution: The globe has a radius of 19 cm.

      The loop used 90 cm of thread.

      Which allows (planar) right-angled triangles with sides of (15, 36, 39) cm and (9, 40, 41) cm to be formed.

      It can also be used on a 19cm radius globe to form a triangle on the globe with approx. 30.31 cm running along the equator and 29.85 cm running up meridians to the north pole, meeting at an angle of approx. 91.4°. So the three sides are each close to 30 cm, and the angles are all about 90°.

      Like

  • Unknown's avatar

    Jim Randell 9:28 am on 7 September 2023 Permalink | Reply
    Tags: ,   

    Teaser 2645: One square 

    From The Sunday Times, 2nd June 2013 [link] [link]

    I have consistently replaced digits by letters, using different letters for different digits, and in this way I have found that:

    (FIVEFOUR)² = ONE

    Now, if I were to tell you whether or not THREE is divisible by 3, and whether or not FOUR is divisible by 4, then you could work out FIVE.

    What number is FIVE?

    Note: As originally published this puzzle has no solution (and was reproduced in this flawed form in the book The Sunday Times Brain Teasers Book 2 (2020)).

    However the additional information that “FIVE is greater than FOUR” allows the published answer to be found.

    [teaser2645]

     
    • Jim Randell's avatar

      Jim Randell 9:29 am on 7 September 2023 Permalink | Reply

      With the extra condition that “FIVE is greater than FOUR” we find the published answer.

      So maybe the setter intended to say: “… I have found that FIVEFOUR is a positive number, whose square is ONE” (or: “the square root of ONE is equal to FIVEFOUR“).

      This Python program runs in 147ms.

      Run: [ @replit ]

      from enigma import (SubstitutedExpression, group, unpack, item, peek, seq2str, printf)
      
      # the alphametic problem (with an additional condition)
      p = SubstitutedExpression(
        ["sq(FIVE - FOUR) = ONE", "FIVE > FOUR"],
        answer="(THREE, FOUR, FIVE)",
      )
      
      # collect the answers, and record values of FIVE (= item(2))
      # by (THREE divisible by 3, FOUR divisible by 4).
      fn = unpack(lambda n3, n4, n5: (int(n3 % 3 == 0), int(n4 % 4 == 0)))
      d = group(p.answers(verbose=0), by=fn, f=item(2), fn=set)
      
      # output the collections, and find the solution
      for (k, vs) in d.items():
        if len(vs) == 1:
          printf("(d3, d4) = {k} -> FIVE = {v} [*** SOLUTION ***]", v=peek(vs))
        else:
          printf("(d3, d4) = {k} -> FIVE = {vs}", vs=seq2str(vs, sort=1, enc="{}"))
      

      Solution: FIVE = 5901.

      If we are told THREE is not divisible by 3, and FOUR is divisible by 4, then the only possible assignments are:

      FIVE = 5901, FOUR = 5872, ONE = 841, THREE = 36211
      FIVE = 5901, FOUR = 5872, ONE = 841, THREE = 63211

      Any of the other of the divisibility possibilities lead to multiple candidate values for FIVE, so this gives the answer.


      However if we do not require FIVE > FOUR, then we find many further possible solutions to the alphametic problem:

      FIVE = 1496, FOUR = 1520, ONE = 576, THREE = 38066
      FIVE = 1496, FOUR = 1520, ONE = 576, THREE = 83066

      FIVE = 3791, FOUR = 3820, ONE = 841, THREE = 56011
      FIVE = 3791, FOUR = 3820, ONE = 841, THREE = 65011

      FIVE = 5791, FOUR = 5820, ONE = 841, THREE = 36011
      FIVE = 5791, FOUR = 5820, ONE = 841, THREE = 63011

      FIVE = 6791, FOUR = 6820, ONE = 841, THREE = 35011
      FIVE = 6791, FOUR = 6820, ONE = 841, THREE = 53011

      FIVE = 8496, FOUR = 8520, ONE = 576, THREE = 13066
      FIVE = 8496, FOUR = 8520, ONE = 576, THREE = 31066

      And so we cannot work out the value of FIVE.

      We can see these candidates by removing the [[ "FIVE > FOUR" ]] on line 5 of the program.

      Like

      • Frits's avatar

        Frits 12:32 pm on 8 September 2023 Permalink | Reply

        The reported run time 147ms was probably with PyPy (I get 423ms with CPython).

        With this program CPython performs better than PyPY.

        from enigma import (SubstitutedExpression, group, unpack, item, peek, seq2str, printf)
        
        # invalid digit / symbol assignments
        d2i = dict()
        for d in range(0, 10):
          vs = set()
          if d == 0: vs.update('OFT')
          # if E is odd then R is even and if E is even then R is even as well
          if d % 2: vs.update('R')
          # a number that ends in 2, 3, 7 or 8 is not a perfect square
          if d in {2, 3, 7, 8}: vs.update('E')
          d2i[d] = vs
         
        # the alphametic problem (with an additional condition)
        p = SubstitutedExpression(
          [ # FIVE > FOUR
            "I > O", 
            "sq(IVE - OUR) = ONE",],
          answer="(FOUR, FIVE, THREE)",
          #answer="(FOUR, FIVE, \
          #         R + 2*E + sum(i for i in range(10) if i not in {F,I,V,E,O,U,R,N}))",
          d2i=d2i,
          verbose=0
        )
         
        # collect the answers, and record values of FIVE (= item(1))
        # by (THREE divisible by 3, FOUR divisible by 4).
        fn = unpack(lambda n4, n5, n3: (int(n3 % 3 == 0), int(n4 % 4 == 0)))
        d = group(p.answers(), by=fn, f=item(1), fn=set)
         
        # output the collections, and find the solution
        for (k, vs) in d.items():
          if len(vs) == 1:
            printf("(d3, d4) = {k} -> FIVE = {v} [*** SOLUTION ***]", v=peek(vs))
          else:
            printf("(d3, d4) = {k} -> FIVE = {vs}", vs=seq2str(vs, sort=1, enc="{}"))   
        

        Like

        • Jim Randell's avatar

          Jim Randell 12:13 pm on 9 September 2023 Permalink | Reply

          @Frits: Yes, 147ms was with PyPy 7.3.12. With CPython 3.12 I get an overall runtime of 255ms.

          Although, if you are solving the rescued problem you can use the expression [[ "is_square(ONE) + FOUR = FIVE" ]] which is a bit faster, and it is even faster to use [[ "is_square(ONE) + OUR = IVE" ]] (93ms with CPython 3.12).

          Like

  • Unknown's avatar

    Jim Randell 9:09 am on 5 September 2023 Permalink | Reply
    Tags:   

    Teaser 2637: Powerful team 

    From The Sunday Times, 7th April 2013 [link] [link]

    George and Martha support the local football team. The squad is numbered from 1 to 22, with 11 playing at any one time and the remaining 11 sitting on the bench. At the start of this week’s match Martha commented that among their 11 players on the pitch there were no three consecutive numbers, and that the same was true of the 11 sitting on the bench. She also commented that the sum of the 11 players’ numbers on the pitch was a perfect square. At half-time one substitution was made and in the second half George noted that all that Martha had said was still true, but now the perfect square was higher.

    What (in increasing order) were the numbers of the 11 players in the first half?

    [teaser2637]

     
    • Jim Randell's avatar

      Jim Randell 9:10 am on 5 September 2023 Permalink | Reply

      This Python program runs in 349ms. (Internal runtime is 279ms).

      Run: [ @replit ]

      from enigma import (irange, subsets, tuples, is_square, diff, cproduct, update, printf)
      
      # available players
      players = list(irange(1, 22))
      
      # check for <k> consecutive numbers in sorted list <ns>
      is_consecutive = lambda ns, k: any(t[0] + k == t[-1] + 1 for t in tuples(ns, k))
      
      # choose 11 of the players to form the team
      for ps in subsets(players, size=11):
        # the sum is a perfect square
        s = sum(ps)
        if not is_square(s): continue
        # no 3 consecutive numbers are used
        if is_consecutive(ps, 3): continue
      
        # and the unused players
        xs = diff(players, ps)
        # no 3 consecutive numbers
        if is_consecutive(xs, 3): continue
      
        # substitute a player from ps with one from xs
        for ((i, p), (j, x)) in cproduct([enumerate(ps), enumerate(xs)]):
          s_ = s - p + x
          if not (s_ > s and is_square(s_)): continue
          # perform the substitution
          ps_ = sorted(update(ps, [(i, x)]))
          if is_consecutive(ps_, 3): continue
          xs_ = sorted(update(xs, [(j, p)]))
          if is_consecutive(xs_, 3): continue
      
          # output solution
          printf("{ps} = {s} -> {ps_} = {s_}")
      

      Solution: The players in the first half were: 1, 2, 4, 5, 7, 8, 10, 12, 14, 17, 20.

      The sum of the numbers in the first half is 100 (= 10²).

      In the second half player 1 was substituted by player 22, causing the sum to increase to 121 (= 11²).


      We can easily see that the smallest possible square is 100, and the largest possible square is 144.

      The difference in the squares is also the difference in the numbers of the substituting and substituted players.

      So the only possible difference is 21, going from 100 → 121.

      And the substitution must be that player 1 was substituted by player 22.

      Like

  • Unknown's avatar

    Jim Randell 8:54 am on 3 September 2023 Permalink | Reply
    Tags: by: Ian Adamson   

    Brain-Teaser 937: Number please? 

    From The Sunday Times, 6th July 1980 [link]

    It was so stifling that afternoon that I had been dozing on my bed with the curtains closed, the air conditioning full on, and a bottle of Vichy water on my bedside table.

    The harsh ring of the telephone brought me to my full consciousness. “This is X9 calling”, said the voice, “it’s been a hot afternoon”. This was the message I had been waiting for, so I replied, “Yes, but it’s cooler in Stockholm.”

    “Now listen carefully”, continued X9, “I want you to telephone me at eleven o’clock tonight. The first digit of my number is twice the first digit of your age; the second digit of my number is three times the second (and last) of your age. Have you got that?”

    “Yes”, I acknowledged, “but why this secrecy?”

    “There may be people listening in. My third digit is the difference of my first two digits — and the fourth is the sum of my first two digits. The final digit of my number is the sum of my third and fourth digits.”

    At first, I worked out an incorrect telephone number, as I had forgotten that I had just recently celebrated my birthday — the difference between the two telephone numbers being a multiple of my age.

    What number should I telephone?

    This puzzle is included in the book The Sunday Times Book of Brainteasers (1994).

    [teaser937]

     
    • Jim Randell's avatar

      Jim Randell 8:54 am on 3 September 2023 Permalink | Reply

      This Python program runs in 53ms. (Internal runtime is 95µs).

      Run: [ @replit ]

      from enigma import (cproduct, nconcat, tuples, printf)
      
      # generate possible (<age>, <number>) pairs
      def generate():
        # for a 2-digit age we have:
        # 1st digit = 1, 2, 3, 4
        # 2nd digit = 0, 1, 2, 3
        for (x, y) in cproduct([(1, 2, 3, 4), (0, 1, 2, 3)]):
          # calculate the 5-digit number <abcde>
          a = 2 * x
          b = 3 * y
          c = abs(a - b)
          d = a + b
          e = c + d
          if d > 9 or e > 9: continue
          # return viable pair
          yield (nconcat(x, y), nconcat(a, b, c, d, e))
      
      # collect the pairs in a dict
      d = dict(generate())
      
      # look for consecutive ages
      for (k1, k2) in tuples(sorted(d.keys()), 2):
        if k1 + 1 != k2: continue
        (v1, v2) = (d[k1], d[k2])
        # difference in numbers is a multiple of the current age
        if (v1 - v2) % k2 > 0: continue
        # output solution
        printf("{k2} -> {v2} [{k1} -> {v1}]")
      

      Solution: The telephone number is 43178.

      This is derived from an age of 21.

      21 → (4 = 2×2)(3 = 3×1)(1 = 4 − 3)(7 = 4 + 3)(8 = 1 + 7) = 43178

      So the incorrectly calculated number is 40448, derived from age 20:

      20 → (4 = 2×2)(0 = 3×0)(4 = 4 − 0)(4 = 4 + 0)(8 = 4 + 4) = 40448.

      And 43178 − 40448 = 2730 = 130×21.


      In fact the only other ages that give viable phone numbers are:

      10 → 20224
      11 → 23156

      But in this case 23156 − 20224 = 2932 is not divisible by 11.

      Like

    • Frits's avatar

      Frits 3:51 pm on 5 September 2023 Permalink | Reply

       
      # formula for X9's telephone number
      x9 = lambda a, b: (20224 - (f := 2*a < 3*b) * 404) * a + (2730 + f * 606) * b
      
      # Assume that for the incorrect telephone number the same rules must appply.
      # This means that the 2nd digit of current age can't be 0, 
      # also 2nd digit of current age can't be 3 (then 4th digit > 9)
      
      for n in [11, 12, 21, 31]:
        d1, d2 = n // 10, n % 10 
        
        correct = x9(d1, d2)
        incorrect = x9(d1, d2 - 1)
        # sum of 2nd and 3rd digit must be less than 10
        if any(int(x[2]) + int(x[3]) > 9 for x in (str(correct), str(incorrect))):
          continue
        
        # difference in numbers is a multiple of the current age
        if (correct - incorrect) % n: continue
        print("answer:", correct)  
      

      Like

  • Unknown's avatar

    Jim Randell 4:41 pm on 1 September 2023 Permalink | Reply
    Tags:   

    Teaser 3180: Taking the chair 

    From The Sunday Times, 3rd September 2023 [link] [link]

    There were eight people on the committee: four men — Jingo, King, Ling and Ming, and four women — Sheena, Tina, Una and Vina. They had to choose a chairperson from among themselves and so each of them voted for their choice, each person choosing someone of the opposite sex. Jingo’s choice’s choice was King. Also, Ling’s choice’s choice’s choice was Sheena. Furthermore, Tina’s choice’s choice’s choice’s choice was Una.

    Just two people got fewer votes than their choice did. After further discussion the woman with the most votes was  made chairperson.

    (a) Who was that?
    (b) Who voted for her?

    [teaser3180]

     
    • Jim Randell's avatar

      Jim Randell 4:58 pm on 1 September 2023 Permalink | Reply

      See also: Tantalizer 8.

      This Python program runs in 126ms. (Internal runtime is 72ms).

      Run: [ @replit ]

      from enigma import (irange, subsets, cproduct, multiset, map2str, seq2str, printf)
      
      # multiple lookups on dict <d>
      def nget(d, k, n):
        for _ in irange(1, n):
          k = d[k]
        return k
      
      # male and female labels
      (male, female) = ("JKLM", "STUV")
      
      # each chooses a member of the opposite gender
      choose = lambda vs, k: subsets(vs, size=k, select='M')
      for (ms, fs) in cproduct([choose(female, len(male)), choose(male, len(female))]):
        # map label to choice
        m = dict(zip(male + female, ms + fs))
      
        # check the conditions:
        if not nget(m, 'J', 2) == 'K': continue
        if not nget(m, 'L', 3) == 'S': continue
        if not nget(m, 'T', 4) == 'U': continue
      
        # count the votes
        vote = multiset.from_seq(m.values())
      
        # exactly 2 people got fewer votes than their choice
        if not sum(vote.count(k) < vote.count(v) for (k, v) in m.items()) == 2: continue
      
        # output voting map
        printf("{m}", m=map2str(m, arr="->"))
        # find max votes for a female
        t = max(vote.count(k) for k in female)
        # output winner
        for w in female:
          if vote.count(w) == t:
            vs = list(k for (k, v) in m.items() if v == w)
            printf("-> winner = {w} [choice of {vs}]", vs=seq2str(vs, enc=""))
        printf()
      

      Solution: (a) Una was made chairperson. (b) Jingo and King voted for her.

      The votes are:

      J → U
      K → U
      L,M → S,V

      S → L
      T → K
      U → K
      V → M

      L and M voted for S and V in some order.

      K and U got 2 votes each. And L, M, S, V got 1 vote each.

      Like

    • Frits's avatar

      Frits 8:14 pm on 1 September 2023 Permalink | Reply

      Without a function for multiple lookup.

      from itertools import product
       
      # male and female labels
      (male, female) = ("JKLM", "STUV")
      
      # all possible votes for men
      ms = [m for m in product(female, repeat=4) if 'S' in m and 'U' in m]
      # all possible votes for women
      fs = [f for f in product(male, repeat=4) if 'K' in f]
      
      # remove entries where 3 or more people nobody votes for
      votes = [(m, f) for m, f in product(ms, fs) if len(set(m + f)) > 5]
      
      # Jingo's choice's choice was King, J -> f? -> K
      votes = [(m, f) for m, f in votes if f[female.index(m[0])] == 'K']
      
      # Ling's choice's choice's choice was Sheena L -> f? -> m? -> S
      votes = [(m, f) for m, f in votes 
               if m[male.index(f[female.index(m[2])])] == 'S']
      
      # Tina's choice's choice's choice's choice was Una, T -> m? -> f? -> m? -> U
      votes = [(m, f) for m, f in votes 
               if m[male.index(f[female.index(m[male.index(f[1])])])] == 'U']
      
      # exactly 2 people got fewer votes than their choice
      for m, f in votes:
        d = dict()
        # build frequency dictionary
        for i in range(4):
          d[male[i]] = f.count(male[i])
          d[female[i]] = m.count(female[i])
      
        # count the number of people who got fewer votes than their choice
        c = sum((d[male[i]] < d[m[i]]) + (d[female[i]] < d[f[i]]) for i in range(4))  
        
        if c == 2: 
          mx = max([(d[w], w) for w in female])
          print(f"That was {mx[1]}, voted for by "
                f"{' and '.join(male[i] for i, x in enumerate(m) if x == mx[1])}"
                f", {m}, {f}")   
      

      Like

    • Frits's avatar

      Frits 11:15 pm on 1 September 2023 Permalink | Reply

      from enigma import SubstitutedExpression
      
      # male and female labels
      (male, female) = ("JKLM", "STUV")
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
         # Jingo's choice's choice was King, J -> f? -> K
         "(f := [S, T, U, V])[J] == 1",
         
         # Ling's choice's choice's choice was Sheena, L -> f? -> m? -> S
         "(m := [J, K, L, M])[f[L]] == 0",
        
         # Tina's choice's choice's choice's choice was Una, T -> m? -> f? -> m? -> U
         "m[f[m[T]]] == 2",
         
         # exactly 2 people got fewer votes than their choice
         "sum((f.count(i) < m.count(m[i])) if i < 4 else \
              (m.count(i - 4) < f.count(f[i - 4])) for i in range(8)) == 2",
        ],
        answer="m, f",
        distinct="",
        digits=range(4),
        reorder=0,
        verbose=0,    # use 256 to see the generated code
      )
      
      # print answers
      for ans in p.answers():
        # build frequency dictionary
        d = {i: ans[0].count(i) for i in range(4)}
        mx = max([(d[i], i) for i in range(4)])  
       
        print(f"That was {female[mx[1]]}, voted for by "
              f"{' and '.join(male[i] for i, x in enumerate(ans[0]) if x == mx[1])}"
              f", {[female[x] for x in ans[0]]} {[male[x] for x in ans[1]]}")   
      

      Like

  • Unknown's avatar

    Jim Randell 9:21 am on 31 August 2023 Permalink | Reply
    Tags:   

    Teaser 1952: Naturally enough 

    From The Sunday Times, 13th February 2000 [link]

    Imagine putting a digit into each of the 20 boxes of this grid so that, reading across, there are four five-figure numbers (labelled 14) and, reading down, five four-figure numbers (labelled 59). Do this in such a way that (naturally) the resulting numbers 19 have the following properties:

    1, 4 and 9 are squares;
    1 and 8 are cubes;
    2, 3, 5 and 7 are primes;
    6 is the product of two primes;
    the average of 19 is more than 4.

    You should then be able to answer the question:

    What is the five-figure number forming 4 across?

    Although this brings the total number of Teaser puzzles set by Victor Bryant to 94 there are a further 5 set by Dr V W Bryant and 1 set by V. Bryant, so it seems likely there are now 100 Teaser puzzles set by Victor Bryant on the S2T2 site (of the 931 Teaser puzzles posted). Which is just over 10.7% (about 1 in 9) of the puzzles on the site.

    If we include the 413 Enigma puzzles set by Victor Bryant under the pseudonym of Susan Denham (geddit?) that are posted on the Enigmatic Code site we get a total of 513 / 3160 puzzles, just over 16.2% (or about 1 in 6) of the puzzles set over both sites that originate from Victor Bryant.

    [teaser1952]

     
    • Jim Randell's avatar

      Jim Randell 9:21 am on 31 August 2023 Permalink | Reply

      Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      It is not particularly fast, but squeaks in just under 1s with a runtime of 999ms. (Internal runtime of the generated program is 860ms).

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      #     [5][6][7][8][9]
      #  [1] A  B  C  D  E
      #  [2] F  G  H  I  J
      #  [3] K  L  M  N  P
      #  [4] Q  R  S  T  U
      
      SubstitutedExpression
      
      --distinct=""
      
      # [1] [4] [9] are squares
      "is_square(ABCDE)"
      "is_square(QRSTU)"
      "is_square(EJPU)"
      
      # [1] [8] are cubes
      "is_cube(ABCDE)"
      "is_cube(DINT)"
      
      # [2] [3] [5] [7] are primes
      "is_prime(FGHIJ)"
      "is_prime(KLMNP)"
      "is_prime(AFKQ)"
      "is_prime(CHMS)"
      
      # [6] is the product of two primes
      "len(factor(BGLR)) = 2"
      
      # the average (mean) of [1]-[9] is > [4]
      "avg([ABCDE, FGHIJ, KLMNP, QRSTU, AFKQ, BGLR, CHMS, DINT, EJPU]) > QRSTU"
      
      # answer is [4]
      --answer="QRSTU"
      
      --template="ABCDE FGHIJ KLMNP QRSTU / AFKQ BGLR CHMS DINT EJPU"
      --solution=""
      --denest=-1
      #--verbose="A" # just show the answer
      

      Solution: [4] = 15376.

      There are 807 ways to fill out the grid. But [4] is the same in all of them.

      In fact the following values are determined:

      Like

  • Unknown's avatar

    Jim Randell 8:53 am on 29 August 2023 Permalink | Reply
    Tags:   

    Teaser 2638: Digilist 

    From The Sunday Times, 14th April 2013 [link] [link]

    I have written down a list of positive whole numbers in ascending order. Overall they use each of the digits 0 to 9 exactly once. There is more than one even number in the list, and the majority of the numbers are primes. The final number in the list is a perfect square and it is the sum of all the other numbers in the list.

    What is my list of numbers?

    [teaser2638]

     
    • Jim Randell's avatar

      Jim Randell 8:56 am on 29 August 2023 Permalink | Reply

      There is more than 1 even number on the list (i.e. at least 2), and the majority of numbers on the list are primes.

      There is only one even prime, so there must be at least 2 primes on the list, so the list must have at least 3 numbers.

      If the final square had 5 digits there would only be 5 digits remaining to form at least 2 numbers that sum to a 5 digit number, and this is not possible.

      So we only need to consider results that are 2, 3, or 4 digits.

      My first program was straightforward, but a bit slow (execution time was 1.9s).

      This Python program constructs an alphametic problem by allocating 2, 3 or 4 digits to the result of the sum, and then chops the remaining digits into numbers that make up the terms. It constructs a corresponding alphametic puzzle, and then uses the [[ SubstitutedExpression() ]] solver from the enigma.py library to solve that.

      It runs in 128ms.

      Run: [ @replit ]

      from enigma import (
        SubstitutedExpression, irange, express, str_upper, tuples,
        sprintf as f, join, printf
      )
      
      # construct appropriate alphametic words
      def words(qs, ds, k, syms=str_upper):
        for (q, d) in zip(qs, ds):
          # return <q> <d>-length words
          for _ in irange(1, q):
            yield syms[:d]
            syms = syms[d:]
        # and a <k>-length result
        yield syms[:k]
      
      # the result is a <k> digit square
      for k in [2, 3, 4]:
        # form numbers from the remaining digits
        ds = list(irange(1, k))
        for qs in express(10 - k, ds):
          if qs[-2:] == [0, 0]: continue
          # make appropriate length alphametic words for the numbers
          ss = list(words(qs, ds, k))
      
          # the alphametic puzzle sum
          sq = ss.pop(-1)
          expr = f("{ss} = {sq}", ss=join(ss, sep=" + "))
          # additional constraints
          exprs = [
            f("is_square({sq})"),  # result is a square
          ]
          # remove duplicates (same length symbols are ordered)
          for (x, y) in tuples(ss, 2):
            if len(x) == len(y):
              exprs.append(f("{x} < {y}", x=x[0], y=y[0]))
          # now add in expressions over the entire list
          ss.append(sq)
          ns = join(ss, sep=", ", enc="[]")
          exprs.extend([
            # more than 1 of the numbers is even
            f("sum(n % 2 == 0 for n in {ns}) > 1 "),
            # the majority of the numbers are prime
            f("sum(is_prime(n) for n in {ns}) > {t}", t=len(ss) // 2),
          ])
      
          # make a solver for the puzzle
          p = SubstitutedExpression.split_sum(
            expr, extra=exprs,
            d2i={ 0: list(s[0] for s in ss) }, # all numbers are positive
            template=expr,
          ).solver()
      
          # solve the puzzle
          for s in p.solve(verbose=0):
            # output the sum
            printf("{s}", s=p.substitute(s, expr))
      

      Solution: The numbers are: 2, 3, 80, 491, 576.

      And:

      2 + 3 + 80 + 491 = 576

      There is more than one even number (2, 80, 576), and 3 of the 5 numbers are prime (2, 3, 491).

      The wording of the puzzle excludes 0 from being on the list, but if it were allowed we would have an alternative solution of:

      0 + 2 + 83 + 491 = 576

      Which has the same square total.

      There are also two further solutions that have the same square total (although a different one to above) but have fewer than 2 even numbers on the list:

      3 + 5 + 41 + 680 = 729
      3 + 5 + 80 + 641 = 729

      Like

  • Unknown's avatar

    Jim Randell 6:57 am on 27 August 2023 Permalink | Reply
    Tags:   

    Brain-Teaser 930: All scores different 

    From The Sunday Times, 18th May 1980 [link]

    The great thing about the new football method is that goals count whoever wins the match. With luck, this will create more excitement, and reward skills better than at present, for even a side losing heavily will have some incentive to attack.

    In this new method 10 points are given for a win, five points to each side for a draw, and one point for each goal scored.

    In a recent competition between four teams — A, B, C and D — who played each other once, the points were as follows:

    A = 25
    B = 34
    C = 6
    D = 20

    Each side scored at least one goal in each match, and — rather interestingly — the score was different in every match.

    Find the score in each match.

    This puzzle is included in the book The Sunday Times Book of Brainteasers (1994). The puzzle text above is taken from the book.

    The setter is given as “the late Eric Emmet”, and it is noted in the 1994 book that Eric Emmet had died by the time this puzzle was published.

    Eric Emmet also contributed the Puzzle series of puzzles to New Scientist, as well as several Enigma puzzles (including puzzles published as late as 1991).

    [teaser930]

     
    • Jim Randell's avatar

      Jim Randell 6:57 am on 27 August 2023 Permalink | Reply

      See also: Enigma 599.

      The total number of points awarded are: 25 + 34 + 6 + 20 = 85.

      There are 6 matches in the tournament, and 10 points are awarded depending on the match outcomes, accounting for 60 points in total.

      So there are 25 goals scored. Each side scored at least one goal in each match, so there are only 13 goals unaccounted for.

      In order to get different scores in each match we need to allow at least 4, but no more than 6 goals to be scored (per team) in any match.

      And we find a solution with up to 4 goals scored (per team) in a match.

      The following run file executes in 79ms. (Internal runtime of the generated program is 19ms).

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      # matches are:
      #
      #  A vs B = E - F
      #  A vs C = G - H
      #  A vs D = I - J
      #  B vs C = K - L
      #  B vs D = M - N
      #  C vs D = P - Q
      
      SubstitutedExpression
      
      --distinct=""
      --digits="1-4"
      
      # points for X in match X vs Y, where the score is x - y
      --code="pts = lambda x, y: compare(x, y, (0, 5, 10)) + x"
      
      # points for A, B, C, D
      "pts(E, F) + pts(G, H) + pts(I, J) == 25"
      "pts(F, E) + pts(K, L) + pts(M, N) == 34"
      "pts(H, G) + pts(L, K) + pts(P, Q) ==  6"
      "pts(J, I) + pts(N, M) + pts(Q, P) == 20"
      
      # all matches have different scores
      "seq_all_different(ordered(x, y) for (x, y) in [(E, F), (G, H), (I, J), (K, L), (M, N), (P, Q)])"
      
      # output match scores
      --header=""
      --template="AvB = {E}-{F}; AvC = {G}-{H}; AvD = {I}-{J}; BvC = {K}-{L}; BvD = {M}-{N}; CvD = {P}-{Q}"
      --solution=""
      

      Solution: The scores are: A vs B = 2-2; A vs C = 2-1; A vs D = 1-1; B vs C = 4-3; B vs D = 3-1; C vs D = 2-3.

      Like

      • Frits's avatar

        Frits 1:01 pm on 28 August 2023 Permalink | Reply

        @Jim, please elaborate on “And we find a solution with up to 4 goals scored in a match”.

        Did you add it because –digits=”1-6″ was rather slow?

        Like

        • Jim Randell's avatar

          Jim Randell 7:51 am on 29 August 2023 Permalink | Reply

          Limiting the digits to a maximum of 4 is enough to find a solution, and it runs quickly.

          For an exhaustive search we can increase the maximum digit to 6. The runtime is increased, but it is still less than 1s.

          But we can limit the total number of goals in any match (it cannot be more than 7), to reduce the runtime again. It complicates the recipe a little, but gives a complete solution that still runs quickly.

          Like

    • Frits's avatar

      Frits 11:45 am on 30 August 2023 Permalink | Reply

      Based on Jim’s setup.

       
      # points for X in match X vs Y, where the score is x - y
      pts = lambda x, y: x + 1 if x < y else x + 6 if x == y else x + 11
      
      # decompose <t> into <k> numbers from <ns> so that sum(<k> numbers) equals <t>
      def solve(t, ns, k=12, s=[]):
        if k == 1:
          if t in ns:
            yield s + [t]
        else: # perform early checks
        
          # H, L, P are already known
          if k == 9 and sum(s) != 3: return  # C must have had three losses
          
          # H, L, P, F, K, M are already known
          if k == 6:                 
            if sum(s) != 9: return   # B didn't loose and had one draw
            if s[4] <= s[1]: return  # C lost from B
          
          # H, L, P, F, K, M, E, N are already known  
          if k == 4:                  
            # B: 2 wins and a draw so (F > E and M == N) or (F == E and M > N)
            if not((s[3] > s[6] and s[5] == s[7]) or 
                   (s[3] == s[6] and s[5] > s[7])): return
            # G > 0 and Q > 0  (and G + Q > 2)
            if sum(s) > 10: return
         
          # G > H and Q > P (and G + Q > 2)
          if k == 3 and s[-1] <= s[0]:  return 
          if k == 2 and (s[-1] <= s[2] or s[-2] + s[-1] <= 2):  return 
             
          for n in ns:
            if n > t: break
            yield from solve(t - n, ns, k - 1, s + [n])
            
      # there are 25 goals scored and only 13 goals unaccounted for   
      # B must have had two wins and one draw as otherwise one win and two draws
      # leads to two "1 - 2" losses for C (who had definitely had three losses)
      
      # matches are:
      #
      #  A vs B = 1 + E  -  1 + F
      #  A vs C = 1 + G  -  1 + H
      #  A vs D = 1 + I  -  1 + J
      #  B vs C = 1 + K  -  1 + L
      #  B vs D = 1 + M  -  1 + N
      #  C vs D = 1 + P  -  1 + Q
      
      # first unaccounted goals for C followed by unaccounted goals for B
      for H, L, P, F, K, M, E, N, G, Q, I, J in solve(13, range(6)):
        games = [(E, F), (G, H), (I, J), (K, L), (M, N), (P, Q)]
        # all matches have different scores
        if len(set(seq := [tuple(sorted(x)) for x in games])) != len(seq): continue
        
        # check number of points
        if pts(E, F) + pts(G, H) + pts(I, J) != 25: continue
        if pts(J, I) + pts(N, M) + pts(Q, P) != 20: continue
        if pts(J, I) + pts(N, M) + pts(Q, P) != 20: continue
        if pts(H, G) + pts(L, K) + pts(P, Q) !=  6: continue
        
        desc = "AvB AvC AvD BvC BvD CvD".split()
        # add 1 to scores
        scores = [desc[i] + " = " + str(games[i][0] + 1) + "-" + 
                  str(games[i][1] + 1) for i in range(6)]
        print(', '.join(scores))  
      

      Like

  • Unknown's avatar

    Jim Randell 4:37 pm on 25 August 2023 Permalink | Reply
    Tags:   

    Teaser 3179: Sums and products 

    From The Sunday Times, 27th August 2023 [link] [link]

    Mrs Green uses a dice game to improve the maths skills of her pupils. The children sit four to a table and each child throws five dice. Points are awarded according to the sum and product for each child; bonus points are awarded if the five scores contain three or more of the same number.

    At Liam’s table all four children had the same sum but all achieved that sum in different ways. Surprisingly, all of the twenty dice scored more than one and no bonus points were awarded. The distribution of scores was:

    sixes … 5;
    fives … 4;
    fours … 2;
    threes … 4;
    twos … 5.

    Liam had the highest product.

    What, in ascending order, were Liam’s five scores?

    [teaser3179]

     
    • Jim Randell's avatar

      Jim Randell 4:54 pm on 25 August 2023 Permalink | Reply

      A bit more straightforward than the last couple of puzzles.

      This Python program runs in 52ms. (Internal runtime is 457µs).

      Run: [ @replit ]

      from enigma import (subsets, multiset, multiply, ediv, printf)
      
      # required distribution of values
      dist = multiset.from_dict({ 6: 5, 5: 4, 4: 2, 3: 4, 2: 5 })
      
      # find the common sum <k> for the 4 children
      k = ediv(dist.sum(), 4)
      
      # generate possible scores
      def scores(dist, k):
        # no value occurs more than 2 times
        m = multiset.from_pairs((k, min(2, v)) for (k, v) in dist.items())
        # look for scores from 5 dice, with the required sum
        for ss in subsets(sorted(m), size=5, select='uC'):
          if sum(ss) == k:
            yield ss
      
      # consider 4-sets of scores
      for ss in subsets(scores(dist, k), size=4):
        # look for required distribution
        if multiset.from_seq(*ss) == dist:
          printf("sum = {k} -> scores = {ss}")
          # find the set with the max product
          ans = max(ss, key=multiply)
          # output solution
          printf("ans = {ans}")
      

      Solution: Liam’s scores were: 3, 3, 4, 5, 5.

      Each child on Liam’s table threw 5 dice with a sum of 20:

      3, 3, 4, 5, 5 → product = 900 (Liam)
      2, 3, 3, 6, 6 → product = 648
      2, 2, 5, 5, 6 → product = 600
      2, 2, 4, 6, 6 → product = 576

      Liked by 1 person

    • Frits's avatar

      Frits 9:25 pm on 25 August 2023 Permalink | Reply

      from enigma import SubstitutedExpression
      
      # (A, B, C, D, E), (F, G, H, I, J), (K, L, M, N, O), (P, Q, R ,S, T) 
      # are four rows of frequencies (0-2)
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [ # check first 3 scores of 5 throws
          "5 - A - B - C - D = E",
          "2 * A + 3 * B + 4 * C + 5 * D + 6 * E == 20",
          
          "F >= A",
          "5 - F - G - H - I = J",
          "2 * F + 3 * G + 4 * H + 5 * I + 6 * J == 20",
          
          "K >= F",
          "5 - K - L - M - N = O",
          "2 * K + 3 * L + 4 * M + 5 * N + 6 * O == 20",
          
          # fill up to target frequency
          "5 - A - F - K = P", 
          "P >= K",
          
          "4 - B - G - L = Q",
          "2 - C - H - M = R",
          "4 - D - I - N = S",
          "5 - E - J - O = T",
          
          "2 * P + 3 * Q + 4 * R + 5 * S + 6 * T == 20",
          
          # different throws, avoid duplicates
          "sorted(set(@rows)) == @rows",
        ],
        answer="[(multiply(i**y for i, y in enumerate(x, 2) if y), x) \
                           for x in @rows]",
        base=3,
        d2i="",
        macro=dict([("rows", "[(A, B, C, D, E), (F, G, H, I, J), \
                               (K, L, M, N, O), (P, Q, R ,S, T)]")]),
        distinct="",
        digits=range(0, 3),
        reorder=0,
        verbose=0,    # use 256 to see the generated code
      )
      
      # print answers
      for ans in p.answers():
        nums = [[i] * y for i, y in enumerate(ans[0][1], 2) if y]
        print(f"answer: {sorted(y for x in nums for y in x)}")   
      

      Like

  • Unknown's avatar

    Jim Randell 2:09 pm on 24 August 2023 Permalink | Reply
    Tags:   

    Brain-Teaser 922: Additional letters 

    From The Sunday Times, 23rd March 1980 [link]

    It is true, of course, that there are a lot of letters in this puzzle, but in spite of that I thought that for once Uncle Bungle was going to write it out correctly.

    In fact there was no mistake until the third and last line across but, in that line one of the letters, I’m afraid, was incorrect.

    This is another addition sum with letters substituted for digits. Each letter consistently stands for the same digit whenever it appears, and different letters stand for different digits — or at least the should do — and they do, but for the mistake in the last line across:

    What is the correct numerical 10-figure answer to the addition sum?

    This puzzle is included in the book The Sunday Times Book of Brainteasers (1994). The puzzle text above is taken from the book.

    [teaser922]

     
    • Jim Randell's avatar

      Jim Randell 2:09 pm on 24 August 2023 Permalink | Reply

      We can use [[ bungled_sum() ]] solver (as seen in Puzzle 56 etc.) for this puzzle.

      The following Python command line executes in 146ms.

      Run: [ @replit ]

      >>> from bungled_sum import bungled_sum
      >>> bungled_sum(['YTBBEDMKD', 'YHDBTYYDD', 'EDYTERTPTY'], [2])
      
                                      T
      YTBBEDMKD + YHDBTYYDD = EDYTERTPHY / @[2,8] T -> H
      695513243 + 673596633 = 1369109876 / B=5 D=3 E=1 H=7 K=4 M=2 P=8 R=0 T=9 Y=6
      

      Solution: The answer to the addition sum is 1369109876.

      The complete sum is:

      695513243 + 673596633 = 1369109876

      which would have been correctly posed as:

      YTBBEDMKD + YHDBTYYDD = EDYTERTPHY

      i.e. the penultimate (tens) digit of the result should have been H (not T).

      Like

  • Unknown's avatar

    Jim Randell 8:46 am on 22 August 2023 Permalink | Reply
    Tags:   

    Teaser 2635: Three sisters 

    From The Sunday Times, 24th March 2013 [link] [link]

    In Shakespeare’s less well-known prequel, King Lear shared all of his estate amongst his three daughters, each daughter getting a fraction of the estate. The three fractions, each in their simplest form, had numerators less than 100 and had the same denominators. Cordelia got the least, with Regan getting more, and Goneril the most (but her share was less than three times Cordelia’s). Each of the three fractions gave a decimal which recurred after three places (as in 0.abcabc…) and each digit from 1 to 9 occurred in one of the three decimals.

    What were the three fractions?

    [teaser2635]

     
    • Jim Randell's avatar

      Jim Randell 8:46 am on 22 August 2023 Permalink | Reply

      The recurring decimal 0.(abc)… is a representation of the fraction abc/999.

      But the three fractions we are dealing with can all be reduced to fractions with a 2-digit numerator, and a common denominator.

      So the common denominator must be a divisor of 999.

      This Python program runs in 54ms. (Internal runtime is 2ms)

      Run: [ @replit ]

      from enigma import (divisors, decompose, gcd, recurring, join, printf)
      
      # return viable repetends
      def repetend(n, d):
        r = recurring(n, d)
        return (None if r.nr else r.rr)
      
      # consider possible denominator values 3 < d < 100
      for d in divisors(999):
        if d < 4: continue
        if d > 297: break
      
        # calculate ascending splits of the denominator
        for (C, R, G) in decompose(d, 3, increasing=1, sep=1, min_v=1, max_v=99):
          # G's share is less than 3 times C's
          if not (G < 3 * C): continue
          # check fractions are in lowest terms
          if any(gcd(n, d) != 1 for n in (C, R, G)): continue
      
          # find the repetends
          reps = list(repetend(n, d) for n in (C, R, G))
          if None in reps: continue
          # check the digits used
          ds = join(reps)
          if '0' in ds or len(set(ds)) < 9: continue
      
          # output solution
          (rC, rR, rG) = reps
          printf("C = {C}/{d} = 0.({rC})...; R = {R}/{d} = 0.({rR})...; G = {G}/{d} = 0.({rG})...")
      

      Solution: The fractions are: Cordelia = 6/37, Reagan = 14/37, Goneril = 17/37.

      As decimals:

      C = 0.(162)…
      R = 0.(378)…
      G = 0.(459)…

      Like

  • Unknown's avatar

    Jim Randell 5:10 pm on 20 August 2023 Permalink | Reply
    Tags: by: Robert Eastaway   

    Brain-Teaser 917: Run ’em up 

    From The Sunday Times, 17th February 1980 [link]

    Last summer, for a pleasant holiday pastime with mathematical connections, I took up the job of operating our local cricket scoreboard at matches.

    This scoreboard is the envy of all the other teams in the league. It shows:

    – the two batsmen identified by their numbers in the batting order, with their individual totals;
    – the score (i.e. the number of runs and the wickets fallen);
    – the number of overs bowled;
    – the number of extras;
    – the score of the last man out.

    During one match, while the two batsmen were in full flight, our team declared their innings closed at the end of an over, with wickets to spare. Exhausted after a busy day, I examined the board and was amazed to see that all of the numbers recorded on it used only two different digits between them.

    I noted that the total was the only three-figure number; that there were four two-figure numbers; and that two single-figure numbers appeared twice. I also observed that the score of the last man out was a factor of the total, and the division of the latter by the former still resulted in a single figure number on the board.

    I was pleased to see that all the batsmen on the board reached double figures.

    What was the final score, i.e. how many runs for how many wickets?

    How many extras were there?

    [In cricket, the batsmen are numbered from 1 upwards as they come in to bat. The world record is 77 runs in one over. The match itself was perfectly normal — no-one retired hurt etc. Ed.]

    This puzzle is included in the book The Sunday Times Book of Brainteasers (1994). The puzzle text above is taken from the book.

    [teaser917]

     
    • Jim Randell's avatar

      Jim Randell 5:11 pm on 20 August 2023 Permalink | Reply

      We start with batsmen 1 and 2 playing, and at this point there would be 0 wickets taken (and no last man out).

      When one of them is out, batsman 3 comes in to play, and there is 1 wicket taken. And when another batsman is dismissed, there are 2 wickets taken, and batsman 4 comes in to play. And so on.

      So, if w is the number of wickets taken, then the most recent of the current batsmen must be number (w + 2).

      This Python program considers possible numbers for the current batsman, and uses these along with the number of wickets taken to find the 2 available digits. It then looks for possible 3-digit numbers using those digits that can be divided by one of digits to give a 2-digit number composed of the available digits (and this is the score of the last man out).

      This is enough to get us the score in the match, and deduce the number of extras.

      This Python program runs in 51ms. (Internal runtime is 457µs).

      Run: [ @replit ]

      from enigma import (irange, subsets, nsplit, union, nconcat, div, printf)
      
      # construct <k> digit numbers from digits <ds>
      construct = lambda ds, k: subsets(ds, size=k, select="M", fn=nconcat)
      
      # consider the numbers of the batsmen on the board
      for (a, b) in subsets(irange(1, 11), size=2):
      
        # and number of wickets fallen
        w = b - 2
        if w < 1: continue
      
        # calculate digits used
        ds = union(nsplit(x) for x in (a, b, w))
        if len(ds) > 2: continue
        # suppose both available digits are determined
        assert len(ds) == 2
      
        # choose a 3-digit total score
        for t in construct(ds, 3):
          # divisible by one of the digits
          for d in ds:
            # to give the score of the last man out
            z = div(t, d)
            # which is a 2 digit number, composed of the required digits
            if z is None or z < 10 or z > 99: continue
            if not ds.issuperset(nsplit(z)): continue
      
            # output solution
            printf("score = {t} for {w} [a={a} b={b} -> w={w} ds={ds} t={t} z={z}]")
      

      Solution: (i) The score in the match was: 688 for 6.

      We have:

      batsman = 6, runs = {66, 68, 86, 88}
      batsman = 8, runs = {66, 68, 86, 88}
      score = 688 for 6
      overs = __
      extras = __
      last man out = 86

      There is a single digit value of 8 to be filled out in one of the gaps (and the other is a 2-digit number (which must be 66, 68, 86, 88)).

      The most likely scenario is that the 688 runs have been scored off more than 8 overs (= 64 balls), so the number of extras is 8.

      (Also, we wouldn’t be able to determine what the number of extras was if it was the missing 2-digit number).

      Solution: (ii) There were 8 extras.


      In the book The Sunday Times Book of Brainteasers (1994), the additional information that: “The world record is 77 runs in one over” is given.

      Presuming the record was not broken during this match, that would give a maximum of 616 runs in 8 overs, so there must be more than 8 overs. (But as noted above, if the number of extras were a 2 digit number, we could not determine it).

      Like

  • Unknown's avatar

    Jim Randell 4:29 pm on 18 August 2023 Permalink | Reply
    Tags: ,   

    Teaser 3178: Drying boards 

    From The Sunday Times, 20th August 2023 [link] [link]

    Chef Ignacio liked to prop his two identical thin rectangular chopping boards against the shelf at the end of his counter to dry. He placed the top of the first one flush with the shelf corner and rested the second on the first, as shown in the diagram. To aid drying, he positioned the second to maximise the air volume in the bounded region below it. The length of each board is an even number of cm (less than 26cm). The distance between the bases of the two boards was a whole number of mm.

    What is this distance?

    It seems that the setter intends that the height of the shelf above the counter is an exact (but not specified) number of mm. Without this requirement we can find multiple potential solutions.

    [teaser3178]

     
    • Jim Randell's avatar

      Jim Randell 5:30 pm on 18 August 2023 Permalink | Reply

      I am assuming the distance between the bases of the boards is the separation between the edges that touch the counter top.

      At the moment I don’t understand how we can work out a unique answer without knowing more information, say, the height of the shelf above the surface of the counter, or the angle of one of the boards.

      Solution: [See my comment below]

      Like

      • Jim Randell's avatar

        Jim Randell 8:26 am on 19 August 2023 Permalink | Reply

        I have now found a single solution using the additional assumption that the height of the shelf above the counter is an exact whole number of millimetres. It seems it is likely this is what the setter intended.

        If the first board makes an angle θ with the surface (0° < θ < 90°), then the maximum cross-sectional area under the second board is achieved when it makes an angle θ/2 with the surface (and the bounded area is an isosceles triangle).

        With the length of the board and the height of the shelf we can calculate the angle θ, and hence θ/2. Then cos(θ/2) is the ratio of half the board length to the required separation.

        I used the half-angle formula:

        \cos \left( \frac{\theta}{2} \right)\; =\; \sqrt{\frac{1\; +\; \cos \left( \theta \right)}{2}}

        This Python program runs in 56ms. (Internal runtime is 1.7ms).

        Run: [ @replit ]

        from enigma import (Rational, irange, is_square_q, div, as_int, printf)
        
        Q = Rational()
        
        # solve for a board of length x (mm)
        for x in irange(20, 240, step=20):
        
          # and a shelf of height h (mm)
          for h in irange(1, x - 1):
        
            # separation between the boards on the counter = y (mm)
            d = is_square_q(x * x - h * h)
            if d is None: continue
            q = is_square_q(Q(d + x, 2 * x))
            if q is None: continue
            y = Q(x, 2 * q)
            # check for integer value
            y = as_int(y, include="+", default=None)
            if y is None: continue
        
            # output solution
            printf("x={x} h={h} -> y={y}")
        

        Solution: The boards are 125 mm apart.

        The boards are 200 mm in length (x = 200), and the shelf is height 192 mm above the counter top (h = 192).

        So the first board makes a (56, 192, 200) = 8× (7, 24, 25) right-angled triangle.

        And we have:

        cos(θ) = 7/25

        θ ≈ 73.74°

        And we calculate cos(θ/2) as:

        cos(θ/2) = √((1 + cos(θ))/2)
        = √((1 + 7/25)/2)
        = √(16/25)
        = 4/5

        θ/2 ≈ 36.87°

        And the required separation is:

        y = (x/2) / cos(θ/2)
        y = 100 / (4/5)
        y = 125


        If the height of the shelf h is unconstrained, then we can find an appropriate value to give any (reasonable) answer we choose.

        For a board of length x and a required separation distance y, we calculate the angle of θ (between 0° and 90°) as:

        cos(θ/2) = x/2y

        Then the required height h for this scenario is given by:

        h = x sin(θ)

        For example:

        x = 240, y = 140

        cos(θ/2) = 6/7
        θ ≈ 62.01°
        h ≈ 211.92 mm

        Like

        • Frits's avatar

          Frits 12:29 pm on 19 August 2023 Permalink | Reply

          I had to make two assumptions, not one, to get to the same answer.

          Luckily my initial derived rule for maximal air volume remains true.

           
          from enigma import Rational
          
          Q = Rational()
          
          M = 26 # length of each board in cm is smaller than M
          
          # air volume in the bounded region is maximal if line perpendicular to
          # the 2nd board splits the 2nd board in half (isoceles triangle)
          
          # board length in mm
          for b in range(20, 10 * M, 20):
            # assume shelf height is a whole number of mm
            for h in range(1, b):
              # assume the distance from corner to 1st board touching 
              # the counter <a> is a whole number of mm
              a = (b**2 - h**2)**(1/2)
              if not (a == (a := int(a))): continue
              # using cosine half-angle formula the following must be true
              d2 = Q(b**2 + a * b, 2 + 4 * Q(a, b) + Q(2 * a**2, b**2))
              if d2.denominator != 1: continue
              
              # distance <d> must be a whole number of mm
              if (d := d2.numerator**(1/2)) != int(d): continue
              print("answer:", int(d), "mm")
          

          Like

          • Frits's avatar

            Frits 10:12 pm on 19 August 2023 Permalink | Reply

            line 17 is not really necessary.

            Like

        • Jim Randell's avatar

          Jim Randell 1:04 pm on 19 August 2023 Permalink | Reply

          For a shorter/faster program we can use [[ pythagorean_triples() ]] from the enigma.py library (and a bit of analysis).

          This Python program has an internal runtime of 316µs.

          Run: [ @replit ]

          from enigma import (pythagorean_triples, div, is_square, printf)
          
          # generate pythagorean triples for the first board (in mm)
          for (a, b, x) in pythagorean_triples(240):
            if x % 20 != 0: continue
            for (d, h) in [(a, b), (b, a)]:
              # calculate the separation of the boards (in mm)
              y = is_square(div(x**3, 2 * (d + x)))
              if y is None: continue
              # output solution (in mm)
              printf("x={x} h={h} -> y={y}")
          

          Analysis:

          Using the identity:

          2 cos²(θ/2) = 1 + cos(θ)

          we have:

          cos(θ/2) = x / 2y
          cos(θ) = d / x

          hence:

          x²/2y² = 1 + d/x

          y² = x³ / 2(d + x)

          And x and y are integers, hence d is also an integer, so (d, h, x) is a Pythagorean triple.

          Liked by 1 person

  • Unknown's avatar

    Jim Randell 8:33 am on 17 August 2023 Permalink | Reply
    Tags: ,   

    Teaser 2634: Good company 

    From The Sunday Times, 17th March 2013 [link] [link]

    Each year at this time Pat’s company gives its staff a bonus to help them “drown their shamrocks” on the Irish national holiday. A total of £500 is shared out amongst all six employees (five men and the manager Kate) whose numbers of years of service consist of six consecutive numbers. Each man gets the same whole number of pounds for each year of his service and Kate gets a higher whole number of pounds for each year of her service. This means that, although Pat does not get the lowest bonus, he does get £20 less than Kate — even though he has served the company for a year longer than her.

    How much does Pat get?

    [teaser2634]

     
    • Jim Randell's avatar

      Jim Randell 8:33 am on 17 August 2023 Permalink | Reply

      This Python program runs in 51ms. (Internal runtime is 421µs).

      Run: [ @replit ]

      from enigma import (irange, tuples, update, printf)
      
      # consider possible consecutive years of service (up to 50)
      for ys in tuples(irange(1, 50), 6):
        # total years service
        t = sum(ys)
        # choose a basic bonus amount
        for b in irange(1, 23):
          # remaining bonus
          r = 500 - t * b
          if not r > 0: break
          # make the list of basic bonuses
          bs = list(y * b for y in ys)
          # kate (not first or last) gets the remaining bonus
          for i in (1, 2, 3, 4):
            y = ys[i]
            if r % y != 0: continue
            # kate's bonus is 20 more than pat's
            (k, p) = (bs[i] + r, bs[i + 1])
            if k == p + 20:
              # output solution
              printf("pat = {p}, kate = {k} [years = {ys}, bonus = {bs}]", bs=update(bs, [(i, k)]))
      

      Solution: Pat’s bonus was £ 108.

      The six employees have worked at the company for 4, 5, 6, 7, 8, 9 years. With Kate having worked 8 years and Pat 9 years.

      Each of the non-managers receives a £12/year bonus:

      4 → £48
      5 → £60
      6 → £72
      7 → £84
      9 → £108 (Pat)

      Kate receives a £16/year bonus:

      8 → £128

      Like

    • Frits's avatar

      Frits 1:08 pm on 17 August 2023 Permalink | Reply

      # basic bonus amount: B,          we have B < 500 / (6 + 15)
      for B in range(1, 24):
        # years of service Y, ..., Y+5, we have (6 * Y + 15) * B < 500
        for Y in range(1, int((500 / B - 15) / 6) + 1):
          # index Kate in Y, ..., Y+5: I   (if I = 0 then Pat gets the lowest bonus)
          for I in range(1, 5):
            # Pat does get 20 pounds less than Kate,  K.(Y + I) - B.(Y + I + 1) = 20
            K, r = divmod(20 + B * (Y + I + 1), Y + I)
            if r: continue
            # a total of 500 pounds is shared out amongst all six employees
            if sum(B * (Y + i) if i != I else K * (Y + I) for i in range(6)) != 500:
              continue
            print(f"answer: {(Y + I + 1) * B} pounds")   
      

      or

      # basic bonus amount: B,          we have B < 500 / (6 + 15)
      for B in range(1, 24):
        # years of service Y, ..., Y+5, we have (6 * Y + 15) * B < 500
        for Y in range(1, int((500 / B - 15) / 6) + 1):
          # index Kate in Y, ..., Y+5: I   (if I = 0 then Pat gets the lowest bonus)
          sofar = sum(B * (Y + i) for i in range(6))
         
          # (Y + I).(K - B) = 500 - sofar,  I = index Kate in list years of service 
          for K, I in [(B + d[0], i) for i in range(1, 5) 
                       if not (d := divmod(500 - sofar, Y + i))[1]]:
            # Pat does get 20 pounds less than Kate
            if K * (Y + I) - B * (Y + I + 1) != 20: continue
            print(f"answer: {(Y + I + 1) * B} pounds")
      

      Like

  • Unknown's avatar

    Jim Randell 9:22 am on 15 August 2023 Permalink | Reply
    Tags:   

    Brainteaser 1644: Piecework 

    From The Sunday Times, 13th March 1994 [link]

    On a piece of card draw a grid of 1 inch squares as shown. Then cut along some of the lines to cut out various pieces. Each piece must consist of five squares, no two pieces can be the same shape, even if turned over or turned round, and all possible shapes of five squares must be included. Then with some of the pieces it is possible to make various shapes in jigsaw fashion.

    I asked my son to make a rectangle in which the longer side was a whole number multiple of the shorter side. His first attempt:

    But then he broke that up and constructed another of different size and with an even number of unused pieces.

    What were the dimensions of this new rectangle?

    [teaser1644]

     
    • Jim Randell's avatar

      Jim Randell 9:23 am on 15 August 2023 Permalink | Reply

      (See also: Enigma 611).

      There are 12 different pentominoes (if we allow rotation and reflection), and I have written polyominoes.py for dealing with them (and other polyominoes).

      This Python program starts with the 12 possible pentomino shapes, and then removes an even number of them and tries to fit them into possible rectangles.

      It runs in 2.2s.

      Run: [ @replit ]

      from enigma import (irange, subsets, divisors_pairs, seq2str, printf)
      import polyominoes
      
      # possible pentomino shapes
      tiles = polyominoes.shapes("I5 U5 T5 V5 X5 W5 L5 Y5 P5 N5 F5 Z5".split(), as_map=1)
      n = len(tiles.keys())
      
      # record grid dimensions
      rs = set()
      # an even number of tiles are unused
      for k in irange(2, n - 1, step=2):
        # choose (n - k) tiles
        for ks in subsets(tiles.keys(), size=n - k):
          ts = list(tiles[x] for x in ks)
          # consider possible rectangles for these pieces
          for (x, y) in divisors_pairs(5 * len(ts)):
            if y % x != 0: continue  # width is a multiple of height
            if (x, y) == (2, 10): continue  # exclude 2 x 10
            # can we fit the tiles into the grid?
            for g in polyominoes.fit(ts, y, x):
              rs.add((x, y))
              # output 1 example
              printf("{x} x {y} grid -> {ks} [{k} unused]", ks=seq2str(ks, sep=" "))
              polyominoes.output_grid(g)
              break
      
      # output solution
      printf("grid = {rs}", rs=seq2str(rs, sep=" ", enc=""))
      

      Solution: The rectangle was 5 in × 10 in.

      There are many possible pairs of shapes which can remain unused, and many possible ways to fit the remaining shapes into the grid. (The program prints one example packing for each set of shapes and grid size).

      Here is one:

      I have a wooden set of pentominoes, here is the same packing (slightly exploded, so you can see the individual pentominoes), along with the unused pieces:

      Like

  • Unknown's avatar

    Jim Randell 3:13 pm on 11 August 2023 Permalink | Reply
    Tags:   

    Teaser 3177: Prime birthday card 

    From The Sunday Times, 13th August 2023 [link] [link]

    On her 11th birthday, Ann’s older brother Ben gave her a card on which he had drawn a 5×5 square grid with a different prime number in each of the cells. Every 5-cell row, column and diagonal had the same sum and, noting that 1 is not a prime, he used primes that made this sum as small as possible.

    The centre cell contained Ann’s age. All but one of the primes containing a digit 7 were on the two diagonals, the largest of these being in the bottom right corner. Two cells in the far right column contained a digit 5 as did two cells of the 4th row down. Four of the cells in the middle row contained a digit 3, and the largest prime on the grid was in the same column as two single digit primes.

    What are the five prime numbers on the top row of the card?

    [teaser3177]

     
    • Jim Randell's avatar

      Jim Randell 5:42 pm on 11 August 2023 Permalink | Reply

      We can exclude 2 from the list of primes, as we need the sum of all 12 magic lines to have the same parity (as they are all equal to the magic constant).

      The magic constant of the square is the sum of the numbers used, divided by 5, so we can look for candidate sets of primes that give the smallest magic constant.

      There are two potential sets of 25 primes that would give a magic constant of 233:

      (1) primes from 3 to 103, excluding 97
      (2) primes from 3 to 107, excluding 101, 103

      And it is possible to construct a Magic Square using either of these sets, so one of these sets must be the set that Ben used.

      (I used a separate program to find the minimal sets, see: [@replit]).

      In the completed grid the centre cell is occupied by 11, so there are 8 remaining cells on the diagonals.

      The first of these sets has 8 numbers that include the digit 7. So is possible for 7 of the remaining diagonal cells to use 7 of these numbers, and the remaining number is in one of the non-diagonal cells.

      The second of these sets has 10 numbers that include the digit 7. So, even if all 8 remaining diagonal cells are filled with one of these numbers there would be 2 numbers left over, so this set is not viable.

      So the set of primes used by Ben must be set (1).

      We can now look for ways to fill out the grid as specified by the remaining requirements.

      I used a MiniZinc program to generate candidate magic squares that fulfil some (most) of the requirements, and then perform additional checks in Python to find arrangements that satisfy all the requirements. I used the minizinc.py library for this.

      This program performs an exhaustive search in 702ms.

      from enigma import (primes, ediv, nsplit, diff, chunk, unzip, implies, icount, lt, join, int2base, printf)
      from minizinc import (MiniZinc, var)
       
      # numbers to use (= set (1))
      numbers = diff(primes.between(3, 103), {97})
      # the magic constant
      k = ediv(sum(numbers), 5)
       
      # find numbers that include the digit 3, 5, 7
      (n3s, n5s, n7s) = (set(), set(), set())
      for n in numbers:
        ds = nsplit(n)
        if 3 in ds: n3s.add(n)
        if 5 in ds: n5s.add(n)
        if 7 in ds: n7s.add(n)
       
      # format a sequence for MiniZinc
      fseq = lambda xs, sep=", ", enc="{}": join(xs, sep=sep, enc=enc)
       
      # construct the model:
      #
      #  A B C D E
      #  F G H I J
      #  K L M N P
      #  Q R S T U
      #  V W X Y Z
      #
      vs = "ABCDEFGHIJKLMNPQRSTUVWXYZ"
      model = f"""
       
      include "globals.mzn";
       
      % possible numbers
      set of int: Number = {fseq(numbers)};
       
      % decision variables for the cells of the square
      {var("Number", vs)};
       
      % general constraints:
       
      % each cell is different
      constraint all_different({fseq(vs, enc="[]")});
       
      % magic lines have the same sum (= k)
      constraint all_equal([{k},
        A+B+C+D+E, F+G+H+I+J, K+L+M+N+P, Q+R+S+T+U, V+W+X+Y+Z,  % rows
        A+F+K+Q+V, B+G+L+R+W, C+H+M+S+X, D+I+N+T+Y, E+J+P+U+Z,  % cols
        A+G+M+T+Z, E+I+M+R+V  % diags
      ]);
       
      % some specific constraints:
       
      % centre cell is 11
      constraint M = 11;
       
      % and the other 4 cells in the middle row (K, L, N, P) contain a digit 3
      constraint {{K, L, N, P}} subset {fseq(n3s)};
       
      % 2 cells in the far right column contain a digit 5
      constraint card({{E, J, P, U, Z}} intersect {fseq(n5s)}) = 2;
      % as did 2 cells in the 4th row down
      constraint card({{Q, R, S, T, U}} intersect {fseq(n5s)}) = 2;
       
      % all but one of the primes containing a '7' are on the diagonals
      constraint card({fseq(n7s)} diff {{A, E, G, I, R, T, V, Z}}) = 1;
      % and the largest of these is Z
      constraint max({fseq(n7s)} intersect {{A, E, G, I, R, T, V, Z}}) = Z;
       
      solve satisfy;
      """
       
      # load the model
      p = MiniZinc(model, solver="minizinc --solver gecode --all", verbose=0)
       
      # and solve it
      for s in p.solve():
        ns = tuple(s[k] for k in vs)
        rows = list(chunk(ns, 5))
        cols = list(unzip(rows))
        (A, B, C, D, E, F, G, H, I, J, K, L, M, N, P, Q, R, S, T, U, V, W, X, Y, Z) = ns
       
        # centre cell is 11
        if not (M == 11): continue
       
        # and the other 4 cells in the middle row contain a digit 3
        if not n3s.issuperset([K, L, N, P]): continue
       
        # 2 cells in the far right column have a digit 5
        if not (len(n5s.intersection([E, J, P, U, Z])) == 2): continue
        # also 2 of the cells in the 4th row down
        if not (len(n5s.intersection([Q, R, S, T, U])) == 2): continue
       
        # all but one of the numbers containing the digit 7 are on the diagonals
        x7s = diff(n7s, {A, E, G, I, R, T, V, Z})
        if not (len(x7s) == 1): continue
        # and the largest of these numbers is Z
        if not (max(diff(n7s, x7s)) == Z): continue
       
        # the largest prime on the grid is in the same column as 2 single digit primes
        maxn = max(ns)
        if not all(implies(maxn in col, icount(col, lt(10)) == 2) for col in cols): continue
       
        # output the grid
        fmt = lambda n: int2base(n, width=3, pad=' ')
        for r in rows:
          printf("{r}", r=join(r, sep=" ", enc="[]", fn=fmt))
        printf()
      

      Solution: The numbers on the top row of the card are: 17, 7, 101, 41, 67.

      The complete grid is:

      Like

      • Frits's avatar

        Frits 9:11 am on 12 August 2023 Permalink | Reply

        Thanks. I wondered how you would do the y contains ‘x’ thing in MiniZinc without string support.

        Like

        • Jim Randell's avatar

          Jim Randell 10:55 am on 12 August 2023 Permalink | Reply

          Originally I had fewer constraints in the MiniZinc model (which is why they are all tested in Python), but it ran faster if the constraints were implemented in the model (apart from the “largest prime” constraint, which was messier to do in MiniZinc, and also slowed down the overall execution).

          As it is the model now only generates a single candidate, so the cost of verifying all the requirements in Python is negligible. (Although the repeated tests could be removed to give a shorter program).

          But I used a restricted version of the model to find the minimal sets of primes that form a Magic Square.

          Like

    • Frits's avatar

      Frits 10:09 am on 13 August 2023 Permalink | Reply

      from itertools import combinations, permutations
      
      # decompose <t> into <k> numbers from <ns>
      def decompose(t, k, ns, s=tuple()):
        if k == 1:
          if t in ns:
            yield s + (t, )
        else:
          for n in ns:
            if t - n < minPr: continue
            yield from decompose(t - n, k - 1, ns.difference([n]), s + (n ,))
      
      # decompose <t> into <k> increasing odd prime numbers from <ns>
      def decompose_inc(t, k, ns, s=[]):
        if k == 1:
          if t in ns:
            yield set(s + [t])
        else:
          for i, n in enumerate(ns):
            if t < k * n + k * (k - 1): break
            yield from decompose_inc(t - n, k - 1, ns[i + 1:], s + [n])
      
      # exclude entries that occur in <s>
      ps = lambda s: {p for p in Pr if p not in s}
      
      # A B C D E
      # F G H I J
      # K L M N O
      # P Q R S T
      # U V W X Y
      
      def solve():
        sol = 0
        # all but one of the primes containing a digit 7 were on two diagonals
        # choose <no7s - 1> 7's for the diagonals
        for c7 in combinations(sevens, no7s - 1):
          rest = 2 * s - 2 * M - sum(c7)             # rest sum for other diagonals
          Y = c7[-1]     # largest of diagonal 7's being in the bottom right corner
      
          match(no7s):
            case 9: oth = ((), )       # tuple of an empty tuple
            case 8: oth = ((rest, ), ) if rest in Pr and '7' not in str(rest) \
                                       else tuple()
            case other:
              oth = tuple(decompose(rest, 9 - no7s,
                          {p for p in Pr if '7' not in str(p)}))
              if not oth: continue
      
          # for all combinations of diagonal cells without '7' (or center)
          for o in oth:
            # permute unknown diagonal values
            for A, G, S, E, I, Q, U in permutations(c7[:-1] + o):
              # only check one diagonal sum
              if A + G + M + S + Y != s: continue
              s1 = {A, G, M, S, Y, E, I, Q, U}
              # four of the cells in the middle row contained a digit 3
              for K, L, N, O in decompose(s - M, 4, {p for p in Pr.difference(s1)
                                                     if '3' in str(p)}):
                # determining J, T followed by determining P, R is a lot faster
                # than determining P, R, T and calculating J  (credit: B. Gladman)
      
                # 5th column
                for J, T in decompose(s - E - O - Y, 2, ps(s2 := s1 | {K, L, N, O})):
                  # two cells in the far right column contained a digit 5
                  if sum('5' in str(x) for x in [E, J, O, T, Y]) != 2: continue
                  # 4th row
                  for P, R in decompose(s - Q - S - T, 2, ps(s3 := s2 | {J, T})):
                    # two cells in the 4th row down contained a digit 5
                    if sum('5' in str(x) for x in [P, Q, R, S, T]) != 2: continue
      
                    F = s - (A + K + P + U)                # 1st column
                    if F in s3 | {P, R} or F not in Pr: continue
                    H = s - (F + G + I + J)                # 2nd row
                    if H in (s4 := s3 | {P, R, F}) or H not in Pr: continue
      
                    # 2nd column
                    for B, V in decompose(s - G - L - Q, 2, ps(s5 := s4 | {H})):
                      # 3rd column
                      for C, W in decompose(s - H - M - R, 2, ps(s6 := s5 | {B, V})):
                        D = s - (A + B + C + E)            # 1st row
                        X = s - (U + V + W + Y)            # 5th row
                        if any(x not in Pr for x in [D, X]): continue
                        if len(s6 | {C, W, D, X}) != 25: continue
      
                        mat = [(A, B, C, D, E),  (F, G, H, I, J),  (K, L, M, N, O), \
                               (P, Q, R, S, T),  (U, V, W, X, Y)]
                        # transpose matrix
                        tmat = list(zip(*mat))
      
                        # largest prime on the grid was in the same column as two
                        # single digit primes
                        if sum(max(Pr) in x for x in tmat \
                                   if sum(y < 10 for y in x) >= 2) != 1: continue
      
                        # double check sums for rows and columns
                        if any(sum(x) != s for m in [mat, tmat] for x in m): continue
      
                        print()
                        for m in mat:
                          print(''.join([f"{str(x):>4}" for x in m]))
      
                        print("\nanswer:", mat[0])
                        # break if we have finished processing this magical sum <s>
                        sol = 1
        return sol
      
      # list of prime numbers up to 997
      primes = [3, 5, 7]
      primes += [x for x in range(11, 100, 2) if all(x % p for p in primes)]
      primes += [x for x in range(101, 1000, 2) if all(x % p for p in primes)]
      total = sum(primes[:25])
      
      # find first entry higher than total for which total = s * 5 for an odd s
      while total % 5 or total % 2 == 0:
        total += 1
      
      M = 11  # the centre cell contained Ann's age
      primes = [p for p in primes if p != M]
      
      sol = 0
      # potentially process all odd magical sums <s> up to a high number
      for s in range(total // 5, 10000, 2):
        # choose 24 prime numbers that (together with <M>) sum up to 5 * s
        for Pr in decompose_inc(5 * s - M, 24, primes):
          sevens = [p for p in Pr if '7' in str(p)]
          # 9 diagonal cells from which M is 11
          if (no7s := len(sevens)) > 9: continue
          minPr = min(Pr)
          # solve the puzzle
          sol += solve()
      
        if sol: break   
      

      Like

    • Frits's avatar

      Frits 10:10 am on 13 August 2023 Permalink | Reply

      from enigma import SubstitutedExpression
      
      # decompose <t> into <k> increasing numbers from <ns>
      def decompose_inc(t, k, ns, s=[]):
        if k == 1:
          if t in ns:
            yield set(s + [t])
        else:
          for i, n in enumerate(ns):
            if t < k * n + 2: break
            yield from decompose_inc(t - n, k - 1, ns[i + 1:], s + [n])      
      
      '''
        A B C D E
        F G H I J
        K L M N O
        P Q R S T
        U V W X Y
      '''
      
      # list of prime numbers
      primes = [3, 5, 7]
      primes += [x for x in range(11, 100, 2) if all(x % p for p in primes)]
      primes += [x for x in range(101, 1000, 2) if all(x % p for p in primes)]
      
      total = sum(primes[:25])
      # find first entry higher than total for which total = s * 5 for an odd s
      while total % 5 or total % 2 == 0:
        total += 1
      
      sol = 0
      # potentially process all odd magical sums <s> up to a high number
      for s in range(total // 5, 10000, 2):
        for Pr in decompose_inc(5 * s, 25, primes):
          sevens = [p for p in Pr if '7' in str(p)]
          # 9 diagonal cells from which M is 11 
          if (no7s := len(sevens)) > 9: continue
          
          exprs = []
         
          # diagonal  
          exprs += ["A + G + M + S + Y == " + str(s)] 
          exprs += ["sum('7' in str(x) for x in [A, G, M, S]) >= 2"]
          exprs += ["max(x for x in [A, G, M, S, Y] if '7' in str(x)) == Y"]
          
          exprs += ["E + I + M + Q + U == " + str(s)]
          # check for <no7s - 1> 7's on the diagonals
          exprs += ["sum('7' in str(x) for x in [A, G, M, S, Y, E, I, Q, U]) == " +\
                    str(no7s - 1)]
          exprs += ["max(x for x in [A, G, M, S, Y, E, I, Q, U] \
                        if '7' in str(x)) == Y"]
      
          # 3rd row
          exprs += ["K + L + M + N + O == " + str(s)] 
          # four of the cells in the middle row contained a digit 3
          exprs += ["sum('3' in str(x) for x in [K, L, M, N, O]) == 4"]
          
          # 5th column
          exprs += ["E + J + O + T + Y == " + str(s)]
          # two cells in the far right column contained a digit 5
          exprs += ["sum('5' in str(x) for x in [E, J, O, T, Y]) == 2"]
      
          # 4th row
          exprs += ["P + Q + S + T + R == " + str(s)] 
          # two cells in the 4th row down contained a digit 5
          exprs += ["sum('5' in str(x) for x in [P, Q, R, S, T]) == 2"]
      
          # remaining horizontal
          exprs += ["A + B + C + D + E == " + str(s)] 
          exprs += ["F + G + H + I + J == " + str(s)] 
          exprs += ["U + V + W + X + Y == " + str(s)] 
      
          # remaining vertical
          exprs += ["A + F + K + U + P == " + str(s)] 
          exprs += ["B + G + L + Q + V == " + str(s)] 
          exprs += ["C + H + M + R + W == " + str(s)] 
          exprs += ["D + I + N + S + X == " + str(s)] 
      
          # largest prime on the grid was in the same column 
          # as two single digit primes
          exprs += ["sum(" + str(max(Pr)) + " in x for x in [(A, F, K, P, U), \
                    (B, G, L, Q, V), (C, H, M, R, W), (D, I, N, S, X), \
                    (E, J, O, T, Y)] if sum(y < 10 for y in x) >= 2) == 1"]
        
          # the alphametic puzzle
          p = SubstitutedExpression(
            exprs,
            answer="((A, B, C, D, E), (F, G, H, I, J), (K, L, M, N, O), \
                     (P, Q, R, S, T), (U, V, W, X, Y))",
            s2d=dict(M=11),
            base=max(Pr) + 1,
            digits=Pr,
            #denest=8,      # use denest if not run with PyPy
            verbose=0,      # use 256 to see the generated code
          )
      
          # print answers
          for ans in p.answers():
            sol = 1
            print()
            for a in ans:
              print(''.join([f"{str(x):>4}" for x in a]))
            print(f"\nanswer: {ans[0]}")
          
        if sol: break   
      

      Like

      • NigelR's avatar

        NigelR 11:28 am on 13 August 2023 Permalink | Reply

        Hi Frits
        I could be missing something, and it may not be relevant to this problem, but the ‘break’ condition (line 10) in your function decompose_inc seems to risk missing some valid decompositions. For example, if you call decompose_inc(10,3,[1,2,3,4,5]), it doesn’t yield {1,4,5}. If you change the condition to ‘if t < k * n + 1: break' it seems to work correctly. Is there a reason for using +2 rather than +1?

        Like

        • Frits's avatar

          Frits 2:10 pm on 13 August 2023 Permalink | Reply

          Hi Nigel, I chose the “+ 2” as there always is a difference of at least 2 between odd prime numbers.

          Like

          • NigelR's avatar

            NigelR 5:46 pm on 13 August 2023 Permalink | Reply

            Thanks Frits. I can now see that it is tailored to the context rather than intended as a generic decompose generator, which is how I was trying to use it!

            Like

    • Frits's avatar

      Frits 2:09 pm on 13 August 2023 Permalink | Reply

      A MiniZinc solution with a matrix based on Jim’s program and Brian Gladman’s initial setup.
      It runs in 411ms.

       
      from enigma import (nsplit, join)
      from minizinc import MiniZinc
      
      # decompose <t> into <k> increasing numbers from <ns>
      def decompose_inc(t, k, ns, s=[]):
        if k == 1:
          if t in ns:
            yield set(s + [t])
        else:
          for i, n in enumerate(ns):
            if t < k * n + 2: break
            yield from decompose_inc(t - n, k - 1, ns[i + 1:], s + [n])      
      
      # format a sequence for MiniZinc
      fseq = lambda xs, sep=", ", enc="{}": join(xs, sep=sep, enc=enc)
      
      # list of prime numbers up to 997
      primes = [3, 5, 7]
      primes += [x for x in range(11, 100, 2) if all(x % p for p in primes)]
      primes += [x for x in range(101, 1000, 2) if all(x % p for p in primes)]
      
      total = sum(primes[:25])
      # find first entry higher than total for which total = s * 5 for an odd s
      while total % 5 or total % 2 == 0:
        total += 1
      
      sol = 0
      # potentially process all odd magical sums <s> up to a high number
      for s in range(total // 5, 10000, 2):
        # choose 25 prime numbers that sum up to 5 * s
        for Pr in decompose_inc(5 * s, 25, primes):
          sevens = [p for p in Pr if '7' in str(p)]
          # 9 diagonal cells from which center is 11 
          if (no7s := len(sevens)) > 9: continue
          
          # find numbers that include the digit 3, 5, 7
          (n3s, n5s, n7s) = (set(), set(), set())
          for n in Pr:
            ds = nsplit(n)
            if 3 in ds: n3s.add(n)
            if 5 in ds: n5s.add(n)
            if 7 in ds: n7s.add(n)
          
          magic = s
          model = f"""
       
          include "globals.mzn";
      
          % possible numbers
          set of int: Number = {fseq(Pr)};
      
          set of int: SIZE = 1..5; 
          
          array[SIZE, SIZE] of var Number: sq;
          
          %var set of int: r3 = array2set(row(sq, 3));
          %var set of int: r4 = array2set(row(sq, 4));
          %var set of int: c5 = array2set(col(sq, 5));
         
          % the centre cell contained Ann's age
          constraint sq[3, 3] = 11;
          
          constraint alldifferent(i in SIZE, j in SIZE) (sq[i, j]);
          
          % same row sums
          constraint forall(i in SIZE) (sum(j in SIZE) (sq[i, j]) = {magic});
          % same column sums
          constraint forall(j in SIZE) (sum(i in SIZE) (sq[i, j]) = {magic});
          % same diagonal sums
          constraint sum(i in SIZE) (sq[i, i]) = {magic};
          constraint sum(i in SIZE) (sq[i, 6 - i]) = {magic};
          
          % all primes but one with '7' are located on the diagonals
          % and the largest of these is sq[5, 5]
          constraint sum(i, j in SIZE where i == j \/ i + j == 6) (sq[i, j] in {fseq(n7s)} /\ sq[i, j] <= sq[5, 5]) == {no7s - 1};
          
          % and the other 4 cells in the middle row contain a digit 3
          % constraint card(r3 intersect {fseq(n3s)}) = 4;
          constraint sum(j in SIZE) (sq[3, j] in {fseq(n3s)}) = 4;
          
          % 2 cells in the far right column contain a digit 5
          %constraint card(c5 intersect {fseq(n5s)}) = 2;
          constraint sum(i in SIZE) (sq[i, 5] in {fseq(n5s)}) = 2;
          
          % as did 2 cells in the 4th row down
          %constraint card(r4 intersect {fseq(n5s)}) = 2;
          constraint sum(j in SIZE) (sq[4, j] in {fseq(n5s)}) = 2;
          
          solve satisfy;
          """      
          
          # load the model
          p = MiniZinc(model, solver="minizinc --solver gecode --all", verbose=0)
           
          # and solve it
          for s in p.solve():
            sq = s['sq']
            for y in sq:
              print(y)
            print("\nanswer:", sq[0])  
            sol = 1
            
        if sol: break  
      

      Like

      • Frits's avatar

        Frits 5:03 pm on 13 August 2023 Permalink | Reply

        The largest prime requirement is not needed to find a unique solution.
        Here is the MiniZinc constraint (it is faster to check in afterwards in Python).

           
        % largest prime on the grid was in the same column as two single digit primes
        constraint sum(j in SIZE) ({max(Pr)} in col(sq, j) /\ 
                   card(array2set(col(sq, j)) intersect {{3, 5, 7}}) >= 2) == 1;
        

        Like

    • Hugo's avatar

      Hugo 11:19 am on 20 August 2023 Permalink | Reply

      OEIS no. A164843 confirms that 233 is the smallest sum for an order-5 prime magic square.

      Is it possible to arrange the same twenty-five primes (alternatively with 97 and 107 instead of 101 and 103) to form a ‘panmagic’ square, i.e where the broken diagonals also sum to 233?

      Like

      • Jim Randell's avatar

        Jim Randell 5:50 pm on 20 August 2023 Permalink | Reply

        I added these constraints into my MiniZinc program, and it has been running some for some time to see if it is possible to find a construction (which makes me suspect it is not). But I will keep you posted if it finds anything.

        Like

        • Hugo's avatar

          Hugo 6:38 pm on 20 August 2023 Permalink | Reply

          Thanks, Jim.
          I too suspect it won’t work with sum 233. On the tangled web I found one with sum 395. There may be one with a smaller sum than that, but my program would take about 1000 years to find it.

          Like

  • Unknown's avatar

    Jim Randell 9:19 am on 10 August 2023 Permalink | Reply
    Tags:   

    Teaser 2484: [Snooker bag] 

    From The Sunday Times, 2nd May 2010 [link] [link]

    Josh put all the snooker balls except the cue [ball] into a bag. He and I then played an imaginary frame. At each person’s turn, he drew a ball. If it was red, he scored a point, discarded the red and drew again. If that was a “colour” (i.e. not red), he scored the appropriate number of points, and returned it to the bag, then tried again for a red. If a player drew the wrong ball, it was returned to the bag and his break was over.

    On one break, the first four balls drawn earned me points; at that stage, the chance of this happening was one in N, N being the number of points I’d got from the break so far.

    Which two colours had I drawn?

    This puzzle was originally published with no title.

    [teaser2484]

     
    • Jim Randell's avatar

      Jim Randell 9:19 am on 10 August 2023 Permalink | Reply

      There are 15 reds and 6 coloured balls in a standard snooker set.

      If at the start of the go there are R reds, then the probability of the first ball being red (for 1 point) is:

      P1 = R / (R + 6)

      and the chance of the second ball being a colour (for x points) is:

      P2 = 6 / (R + 5)

      the chance of the third ball being red (for 1 point) is:

      P3 = (R − 1) / (R + 5)

      and the chance of the fourth ball being a colour (for y points) is:

      P4 = 6 / (R + 4)

      The probability of getting this far is the product of these probabilities.

      And we want this product to give a value of 1/N for some positive integer N that is the total score from 2 colours.

      This Python program runs in 56ms. (Internal runtime is 91µs).

      from enigma import (irange, div, Decompose, printf)
      
      # decompose a total into a set of colours (2..7 points)
      decompose = Decompose(increasing=1, sep=0, min_v=2, max_v=7)
      
      # consider number of reds at the start of the break
      for R in irange(2, 15):
        # calculate the inverse of the overall probability
        # = (product of denominators) / (product of numerators)
        # which we want to be an integer N
        N = div((R + 6) * (R + 5) * (R + 5) * (R + 4), R * 6 * (R - 1) * 6)
        if not N: continue
        # find points for the 2 colours
        for cs in decompose(N - 2, 2):
          printf("R={R} N={N} -> cs={cs}")
      

      Solution: The colours were pink (6 points) and black (7 points).

      So there were 4 reds at the start of the break, the probabilities being:

      R = 4
      P1 = 4/10 = 2/5
      P2 = 6/9 = 2/3
      P3 = 3/9 = 1/3
      P4 = 6/8 = 3/4
      product = 1/15
      N = 15 = 6 + 7

      Like

  • Unknown's avatar

    Jim Randell 8:05 am on 8 August 2023 Permalink | Reply
    Tags:   

    Teaser 2639: Prime number 

    From The Sunday Times, 21st April 2013 [link] [link]

    I have given each letter of the alphabet a different whole-number value between 1 and 99 so that each letter represents one or two digits. In this way, for example, a three- letter word can represent a number of three, four, five or six digits. With my values it turns out that:

    PRIME = NUMBER.

    Furthermore, rather fortuitously, each letter used in that display has a value equal to an odd prime number.

    What is the number PRIME?

    [teaser2639]

     
    • Jim Randell's avatar

      Jim Randell 8:06 am on 8 August 2023 Permalink | Reply

      We have encountered a puzzle similar to this before (see: Teaser 2628), and I wrote some generic code to solve that puzzle, which can also be used to solve this puzzle.

      The following Python 3 program runs in 64ms. (Internal runtime is 8.8ms).

      Run: [ @replit ]

      from enigma import (primes, subsets, filter2, group, item, update, remove, translate, join, printf)
      
      # solve() routine copied from teaser2628r.py:
      
      # replace letters in <X>, <Y> with values from <ns>, so the strings formed are equal
      # <ns> groups values by their final digit
      # return the map: letter -> value
      def _solve(X, Y, ns, d):
        # are we done?
        if X == Y:
          yield d
        elif X and Y:
          # remove any common suffix
          while X and Y and X[-1] == Y[-1]: (X, Y) = (X[:-1], Y[:-1])
          if not (X and Y): return
          # split the final characters into numeric / non-numeric
          (nums, nons) = filter2((lambda x: x.isdigit()), [X[-1], Y[-1]])
          # different final numerics = failure
          if len(nums) > 1: return
          # choose values with the same final digit
          # if there is a numeric value use that, otherwise use the groups
          for k in (nums or ns.keys()):
            ss = ns.get(k, [])
            for vs in subsets(ss, size=len(nons), select='P'):
              # update the strings
              d_ = update(d, nons, vs)
              (X_, Y_) = (translate(x, d_, embed=0) for x in (X, Y))
              ns_ = update(ns, [(k, remove(ss, *vs))])
              # and solve for the translated strings
              yield from _solve(X_, Y_, ns_, d_)
      
      # replace letters in <X>, <Y>
      def solve(X, Y, ns):
        # group values by their final digit
        ns = group(map(str, ns), by=item(-1), fn=set)
        # and call the solver
        return _solve(X, Y, ns, dict())
      
      # now solve the puzzle:
      
      # possible numeric values
      ns = list(primes.irange(3, 99))
      
      # word values we are interested in
      (w1, w2) = ("PRIME", "NUMBER")
      
      # turn a word into a string
      fmt = lambda w, sep=':': join((d.get(x, x) for x in w), sep=sep)
      
      # solve the puzzle
      for d in solve(w1, w2, ns):
        # output solution
        printf("{w1}={f1} {w2}={f2}", f1=fmt(w1), f2=fmt(w2))
      

      Solution: PRIME = 531713717.

      We have:

      PRIME = 53:17:13:71:7
      NUMBER = 5:31:71:3:7:17

      Like

      • Frits's avatar

        Frits 7:54 pm on 8 August 2023 Permalink | Reply

        One performance improvement could be to add:

        vars2 = len(nons) == 2

        and

        if vars2 and len(vs[0] + vs[1]) != 3: continue

        I have more performance optimisations but this seems to be the one with the most impact.

        Like

        • Jim Randell's avatar

          Jim Randell 8:42 am on 9 August 2023 Permalink | Reply

          @Frits: To keep things generic we could just skip selections of 2 values where they have the same length. That is a simple change.

          More complicated would be to store candidate values by the final digit and the number of values required and populate it only with different length pairs, and that would avoid the recalculation at each step.

          Like

    • Frits's avatar

      Frits 12:59 pm on 8 August 2023 Permalink | Reply

      Without much analysis (except that both PRIME and NUMBER must have the same trailing digit F).

       
      from enigma import SubstitutedExpression, join
      
      # build string of valid numbers
      P = [3, 5, 7]
      P += [x for x in range(11, 100, 2) if all(x % p for p in P)]
      P = "{" + join(P, ",") + "}" 
      
      # check for same leading digits
      leading = lambda s1, s2: all(x == y for x, y in zip(join(s1), join(s2)))
      # check for same trailing digits
      trailing = lambda s1, s2: all(x == y for x, y in zip(join(s1)[::-1], join(s2)[::-1]))
       
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
          #      PRIME             NUMBER  
          # PQ RF IJ MA EF == NO UV MA BC EF RF"
          
          # first check from the back
          "EF in @primes",
          "RF in @primes and len(s2 := {EF, RF}) == 2",
          "trailing([EF], [RF])",
          
          "MA in @primes and len(s3 := s2 | set([MA])) == 3",
          "trailing([MA, EF], [EF, RF])",
          
          # now check from the front
          "PQ in @primes and len(s4 := s3 | set([PQ])) == 4",
          "NO in @primes and len(s5 := s4 | set([NO])) == 5",
          "leading([PQ, RF], [NO])",
      
          "UV in @primes and len(s6 := s5 | set([UV])) == 6",
          "leading([PQ, RF], [NO, UV, MA])",
          
          "IJ in @primes and len(s7 := s6 | set([IJ])) == 7",
          "leading([PQ, RF, IJ], [NO, UV, MA])",
          
          "BC in @primes and BC not in s7",
          
          # check all digits
          "join(@prime) == join(@number)",
        ],
        answer="join(@prime)",
        d2i=dict([(k, "QFJAOVC") for k in [0, 2, 4, 6, 8]]),
        macro=dict([("primes", P)] + [("prime", "[PQ, RF, IJ, MA, EF]")] + \
                   [("number", "[NO, UV, MA, BC, EF, RF]")]
        ),
        distinct="",
        env=dict(leading=leading, trailing=trailing),
        reorder=0,
        verbose=0,    # use 256 to see the generated code
      )
      
      # print answers
      for ans in p.answers():
        print(f"answer: {ans}")
      

      Like

    • Jim Randell's avatar

      Jim Randell 4:46 pm on 8 August 2023 Permalink | Reply

      Here is a run file for this puzzle.

      It would be fairly straightforward to write a program that used this format for a generic solution.

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      --base=100
      
      # digits = primes.between(3, 99)
      --digits="3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97"
      
      # check the concatenations match (working from the end)
      --code="check = lambda xs, ys, **kw: zip_eq(join(xs), join(ys), reverse=1, **kw)"
      
      # check the full strings
      "check([P, R, I, M, E], [N, U, M, B, E, R], strict=1)"
      
      # for performance check the partial strings
      "check([E], [R])"
      "check([M, E], [E, R])"
      "check([I, M, E], [B, E, R])"
      "check([R, I, M, E], [M, B, E, R])"
      "check([P, R, I, M, E], [U, M, B, E, R])"
      
      --template=""
      --answer="((P, R, I, M, E), (N, U, M, B, E, R))"
      
      # zip_eq(..., strict=1) only works in Python 3.10+
      --code="require('sys.version', '3.10')"
      

      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