Tagged: by: John Owen Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 7:03 am on 21 September 2025 Permalink | Reply
    Tags: by: John Owen   

    Teaser 3287: Ferry route 

    From The Sunday Times, 21st September 2025 [link] [link]

    A large circular sea, whose diameter is less than 300km, is served by a ferry that makes a clockwise route around half of the sea, serving the ports of Ayton, Beaton, Seaton and Deaton in that order, then back to Ayton. Deaton is diametrically opposite Ayton. Each of the four legs of its route is a straight line, two of them being the same length. The lengths of all of the legs are whole numbers of km, and they all happen to be square numbers.

    In increasing order, what are the three different leg lengths?

    [teaser3287]

     
    • Jim Randell's avatar

      Jim Randell 7:18 am on 21 September 2025 Permalink | Reply

      See: Teaser 2549.

      If the diameter of the circle is x, and the lengths of the non-diameter legs are a, b, c, then we have:

      x³ − (a² + b² + c²)x − 2abc = 0

      The following Python program runs in 62ms. (Internal runtime is 643µs).

      from enigma import (powers, inf, first, lt, subsets, pi, cb, sumsq, printf)
      
      # squares less than 300
      sqs = list(first(powers(1, inf, 2), lt(300)))
      
      # choose 3 different lengths (x is the diameter)
      for (a, b, x) in subsets(sqs, size=3):
        # duplicate one of the short lengths
        for c in (a, b):
          # check for a viable quadrilateral
          if not (x < a + b + c < pi * x): continue
          if not (cb(x) - sumsq([a, b, c]) * x - 2 * a * b * c == 0): continue
          # output solution
          printf("{a}, {b}, {x} [and {c}]")
      

      Solution: The leg lengths are 36, 49, 81 km.

      The duplicate leg length is 36 km.

      The next smallest solution is at 4× these lengths, which brings the diameter to 324 km.

      Like

      • Jim Randell's avatar

        Jim Randell 8:49 am on 22 September 2025 Permalink | Reply

        We can suppose that the non-diameter sides are (a, b, a) (i.e. c = a, and it may be the case that a > b), and then the equation can be simplified to:

        2a² = x(x − b)

        So by choosing b and x we can then straightforwardly calculate the corresponding value for a, and check it is viable (i.e. a square):

        from enigma import (powers, inf, first, lt, subsets, is_square, div, ordered, printf)
        
        # squares less than 300
        sqs = list(first(powers(1, inf, 2), lt(300)))
        
        # choose 2 different lengths (x is the diameter)
        for (b, x) in subsets(sqs, size=2):
          # a is the duplicated side
          a = is_square(div(x * (x - b), 2))
          if a is None or a not in sqs: continue
          # output solution
          (p, q) = ordered(a, b)
          printf("{p}, {q}, {x} [and {a}]")
        

        Liked by 1 person

        • Frits's avatar

          Frits 2:29 pm on 22 September 2025 Permalink | Reply

          I had come up with similar equation. You can also deduce the parity of “a”.

          Like

    • Ruud's avatar

      Ruud 10:35 am on 21 September 2025 Permalink | Reply

      import math
      import itertools
      
      for ab, bs, sd, da in itertools.product((i * i for i in range(1, 18)), repeat=4):
          try:
              angle_ab = math.asin(ab / da) * 2
              angle_bs = math.asin(bs / da) * 2
              angle_sd = math.asin(sd / da) * 2
      
              if angle_ab + angle_bs + angle_sd == math.pi:
                  print(sorted({ab, bs, sd, da}))
          except ValueError:
              ...
      

      Like

      • Jim Randell's avatar

        Jim Randell 11:38 am on 21 September 2025 Permalink | Reply

        @Ruud: How does this code ensure that two of the leg lengths are the same?

        And it is probably better to use [[ math.isclose() ]] rather than testing floats for equality using ==.

        Like

        • Ruud's avatar

          Ruud 12:55 pm on 21 September 2025 Permalink | Reply

          I just checked manually by checking that there are 3 different length. Could have added a simple test, of course.

          Yes, math.isclose would have been better, but as the equality check gave already an answer, I thought I could just refrain from isclose.

          Like

        • Ruud's avatar

          Ruud 4:14 pm on 21 September 2025 Permalink | Reply

          @Jim
          I just checked manually that there are exactly three different lengths, but a test would be better.

          Yes, math.isclose would have beeen safer.

          Here’s my updated version:

          import math
          import itertools
          
          for ab, bs, sd, da in itertools.product((i * i for i in range(1, 18)), repeat=4):
              try:
                  angle_ab = math.asin(ab / da) * 2
                  angle_bs = math.asin(bs / da) * 2
                  angle_sd = math.asin(sd / da) * 2
          
                  if math.isclose(angle_ab + angle_bs + angle_sd, math.pi) and len(sol := {ab, bs, sd, da}) == 3:
                      print(sorted(sol))
              except ValueError:
                  ...
          
          peek("done")
          

          Like

    • Alex.T.Sutherland's avatar

      Alex.T.Sutherland 10:42 am on 28 September 2025 Permalink | Reply

      TEASER 3287.....FERRY ROUTE.
      Given:-		Cyclic Quadrilateral [A B C D] with lengths [a b c d], d = diameter; 
      		               All sides are of perfect square length.
      Method:-	Using Ptolemy's Theorem relating the diagonals to the sides
      		               of the quadrilateral and that right angles are created at B & C
      		              by the diagonals the following equation is derived:-
      
      		              (d^2 - a^2) * (d^2 - c^2) = (b*d + a*c)^2
      
      		              If 'c' is made equal to 'a' the following can be  derived:-
      
      Answer:-	2*a^2  = d*(d-b);
      
      		              Choose 3 squares from the given set to satisfy this equation.
      Side Line:-	The path could be 'abad' or'aabd' but the answer is the same for the lengths.
      		              (neglecting symmetry eg 'baa' is the same as 'aab')'
      		             For my answer the sum of the lengths 'aba' or 'aab' is a perfect square.
      

      Like

  • Unknown's avatar

    Jim Randell 6:24 am on 13 July 2025 Permalink | Reply
    Tags: by: John Owen,   

    Teaser 3277: Croquet equipment 

    From The Sunday Times, 13th July 2025 [link] [link]

    Our non-standard croquet lawn has six hoops, at positions A to F, and a central peg at P. The equipment storage box is in the southwest corner at S, and the lawn is symmetrical in both the east-west and north-south directions. The diagram is not to scale, but D is south of the projected line from S to E.

    Also AB is half the width of the lawn. When setting out the equipment, I walk along the route SEFDPCBAS. All of the distances on my route between positions are whole numbers of feet (less than 60), and both D and E are whole numbers of feet north of the south boundary.

    What is the total distance of my route?

    [teaser3277]

     
    • Jim Randell's avatar

      Jim Randell 8:46 am on 13 July 2025 Permalink | Reply

      I get two solutions, so here is a straightforward solution to make sure I haven’t missed any thing.

      But if we disallow distances of 60ft or more between any two positions on the walk (not just adjacent positions), then we can eliminate the larger of these solutions.

      This Python program runs in 65ms. (Internal runtime is 5ms).

      from enigma import (irange, ihypot, printf)
      
      M = 59  # max length of a path segment
      
      # let AB = EF = 2x
      for x in irange(1, M // 2):
        # e = distance E north from southern edge
        for e in irange(1, M):
          SE = ihypot(x, e)
          if SE is None or SE > M: continue
      
          # d = distance D is north of EF
          for d in irange(1, e - 1):
            FD = ihypot(x, d)
            if FD is None or FD > M: continue
      
            # p = distance P north of D
            for p in irange(1, M):
              SA = ihypot(x, e + d + p + p + d)
              if SA is None or SA > M: continue
      
              # total distance walked
              T = SE + SA + 2*FD + 4*x + 2*p
              printf("T={T} [SE={SE} FD={FD} SA={SA}; x={x} e={e} d={d} p={p}]")
      

      Solution: There are two viable solutions to the puzzle: 142 ft, and 220 ft.

      Apparently the size of a croquet lawn is not fixed, but it should be a rectangle with sides in the ratio of 1.25.

      The first of the solutions involves a playing area of 48 ft × 44 ft (ratio = 1.09).

      And all positions on the route are within 60 ft of S (as indicated by the dotted line).

      The second of the solutions involves a playing area of 96 ft × 42 ft (ratio = 2.29).

      And B and F are further than 60 ft from S.


      The published solution is: “142 feet”.

      But a correction was issued with Teaser 3280:

      There were in fact two possible answers: 142 and 220 feet.
      Either was accepted as correct.

      .

      Like

      • Frits's avatar

        Frits 11:38 am on 13 July 2025 Permalink | Reply

        @Jim, shouldn’t we have: e + d + p = 2.x ?

        Like

      • Jim Randell's avatar

        Jim Randell 4:19 pm on 13 July 2025 Permalink | Reply

        Alternatively, using the [[ pythagorean_triples() ]] function from the enigma.py library.

        The following Python program has an internal runtime of 122µs.

        from enigma import (defaultdict, pythagorean_triples, subsets, div, printf)
        
        M = 59  # maximum length of a path segment
        
        # collect (<other>, <hypot>) sides for pythagorean triples
        t = defaultdict(list)
        for (x, y, z) in pythagorean_triples(M):
          t[x].append((y, z))
          t[y].append((x, z))
        
        # consider possible x values
        for x in sorted(t.keys()):
          if 2 * x > M: break
          # FD, SE, SA all have base x, and increasing vertical sides
          ts = sorted(t[x])
          for ((d, FD), (e, SE), (a, SA)) in subsets(ts, size=3):
            p = div(a - e - 2*d, 2)
            if p is None or p < 1: continue
        
            # total distance walked
            T = SE + SA + 2*FD + 4*x + 2*p
            printf("T={T} [SE={SE} FD={FD} SA={SA}; x={x} e={e} d={d} p={p}]")
        

        Like

    • Hugo's avatar

      Hugo 10:34 am on 21 July 2025 Permalink | Reply

      If hoop P has coordinates (0, 0) then it seems
      A is at (12, -13), B is at (12, 13)
      C is at (0, 8), D is at (0, -8)
      E is at (-12, -13), F is at (-12, 13)
      S is at (-24, -22).

      It would have been kind of them to tell us that all the distances, including x and y separations, are integers.

      Like

  • Unknown's avatar

    Jim Randell 2:42 am on 30 March 2025 Permalink | Reply
    Tags: by: John Owen   

    Teaser 3262: Log cabins 

    From The Sunday Times, 30th March 2025 [link] [link]

    Ann, Bert, Chloe and Dave own log cabins on the shore of a circular lake. Ann often rows across the lake (in a straight line) to visit Bert, and vice-versa. Chloe and Dave also visit each other in the same way.

    The two routes cross in the lake at point X. Interestingly, the four distances from the log cabins to X are all whole numbers of metres (greater than 20m), but the list of distances contains no digit more than once. Chloe’s distance from her log cabin to X is twice Ann’s, while Bert’s distance is three times Ann’s.

    In ascending order, what are the four distances from the log cabins to X?

    [teaser3262]

     
    • Jim Randell's avatar

      Jim Randell 3:10 am on 30 March 2025 Permalink | Reply

      The cabins form a cyclic quadrilateral [ @wikipedia ].

      And if we denote the distances AX = a, BX = b, CX = c, DX = d. Then we have:

      a . b = c . d

      This is the intersecting chords theorem [ @wikipedia ].

      So:

      b = 3a
      c = 2a

      d = 3a/2

      Hence a must be even.

      The following Python program runs in 67ms. (Internal runtime is 106µs).

      from enigma import (irange, inf, ediv, ordered, join, printf)
      
      # consider distance AX = a (must be even)
      for a in irange(22, inf, step=2):
        # BX = b = 3a, CX = c = 2a, DX = d = 3a/2
        (b, c, d) = (3 * a, 2 * a, ediv(3 * a, 2))
        ds = ordered(a, b, c, d)
        s = join(ds)
        # between them they use no digit more than once
        if len(s) > 10: break
        if len(s) != len(set(s)): continue
        # output solution
        printf("{ds} [a={a} b={b} c={c} d={d}]")
      

      Solution: The distances are: 36, 54, 72, 108 metres.

      a = 36
      b = 108
      c = 72
      d = 54
      and:
      a . b = c . d = 3888


      Manually we can follow a similar approach, considering even values for a starting at 22, until a solution is found:

      a = 22; repeated digits
      a = 24; b = 72; repeated digits
      a = 26; b = 78; c = 52; repeated digits
      a = 28; b = 84; repeated digits
      a = 30; b = 90; repeated digits
      a = 32; b = 96; c = 64; repeated digits
      a = 34; b = 102; c = 68; d = 51; repeated digits
      a = 36; b = 108; c = 72; d = 54; solution found

      For an exhaustive solution it is sufficient to check a ≤ 66 beyond which the distances use more than 10 digits, so there will always be duplication of digits. But there are no further solutions.

      Like

  • Unknown's avatar

    Jim Randell 9:57 am on 3 December 2024 Permalink | Reply
    Tags: by: John Owen   

    Teaser 2600: Mileometer 

    From The Sunday Times, 22nd July 2012 [link] [link]

    My car’s digital mileometer has five digits, displaying whole miles. It also has a trip meter with five digits, displaying tenths of a mile (which resets to zero when reaching 10,000 miles). Soon after the car was new I reset the trip meter to zero (but never did that again). Not long after, I noticed that the two five-digit displays were the same ignoring the decimal point). The next time the displays were the same I wrote down the mileage and did so on each subsequent occasion until the mileage reached 100,000. The sum of all the mileages I wrote down was 500,000.

    What were the five digits when the displays were first the same?

    [teaser2600]

     
    • Jim Randell's avatar

      Jim Randell 9:57 am on 3 December 2024 Permalink | Reply

      Suppose the readings are the same at a distance ABCDE+F miles (the +F indicates + F tenths of a mile), then the readings are:

      milometer = ABCDE
      trip meter = ABCD+E

      The trip meter is actually reading XABCD+E miles, since it was reset, for some non-visible digit X.

      Which means the trip meter was reset at an actual distance of:

      ABCDE+F − XABCD+E

      And we want this to be soon after the car was new, maybe in the first 10K miles.

      This Python program looks at distances of possible duplicated readings, and collects them by the trip reset distance. It then looks for a distance where the sum of the milometer readings (except for the first one) is 500000.

      It runs in 530ms (using PyPy).

      from enigma import (defaultdict, irange, subsets, nconcat, trim, printf)
      
      # collect readings by reset distance
      rs = defaultdict(list)
      
      # consider possible 6-digit distances (in 0.1 mile units)
      for (A, B, C, D, E, F) in subsets(irange(0, 9), size=6, select='M'):
        dist = nconcat(A, B, C, D, E, F)
        for X in irange(max(0, A - 1), A):
          # consider trip distances that match the milometer (in 0.1 mile units)
          trip = nconcat(X, A, B, C, D, E)
          # calculate trip reset point
          k = dist - trip
          if not (0 < k < 100000): continue
          rs[k].append(dist)
      
      # output the milometer/trip readings
      def output(d, k):
        (m, f) = divmod(d, 10)
        (t, g) = divmod(d - k, 10)
        t %= 10000
        printf("@ {m:05d}.{f} miles -> {m:05d} + {t:04d}.{g}")
      
      # consider possible reset distances
      for (k, vs) in rs.items():
        vs = sorted(vs)
        # sum the milometer readings (except the first one)
        t = sum(v // 10 for v in trim(vs, head=1))
        if t == 500000:
          # output solution
          output(k, k)
          for v in vs: output(v, k)
          printf("t = {t}")
          printf()
      

      Solution: When the displays were first the same they were showing 01235 (or 0123.5 for the trip meter).

      The trip meter was reset as a distance of 1111.6 miles, and so the readings were:

      @ 01111.6 miles → 01111 + 0000.0 [trip reset]
      @ 01235.1 miles → 01235 + 0123.5 [1st equal display]
      @ 12346.2 miles → 12346 + 1234.6 [2nd equal display – noted down]
      @ 23457.3 miles → 23457 + 2345.7 [3rd equal display – noted down]
      @ 34568.4 miles → 34568 + 3456.8 [4th equal display – noted down]
      @ 45679.5 miles → 45679 + 4567.9 [5th equal display – noted down]
      @ 56790.6 miles → 56790 + 5679.0 [6th equal display – noted down]
      @ 67901.7 miles → 67901 + 6790.1 [7th equal display – noted down]
      @ 79012.8 miles → 79012 + 7901.2 [8th equal display – noted down]
      @ 90123.9 miles → 90123 + 9012.3 [9th equal display – noted down]
      @ 90124.0 miles → 90124 + 9012.4 [10th equal display – noted down]

      And the sum of the values noted down is:

      12346 + 23457 + 34568 + 45679 + 56790 + 67901 + 79012 + 90123 + 90124
      = 500000

      Like

  • Unknown's avatar

    Jim Randell 7:58 am on 5 November 2024 Permalink | Reply
    Tags: by: John Owen   

    Teaser 2608: Football logic 

    From The Sunday Times, 16th September 2012 [link] [link]

    In the logicians’ football tournament, each of three teams (captained by Alf, Bert and Charlie) plays each other once, with three points for a win and one for a draw. In working out their order at the end of the tournament, “goals scored” are used to determine the order of teams with the same points total. Each captain only knows the scores in his own team’s games. At the end I asked the captains in turn whether they knew which position they had finished in. The replies were:

    Alf: “no”;
    Bert: “no”;
    Charlie: “no”;
    Alf: “yes”.

    In which position did Charlie’s team finish? And what was the result in the game between the other two teams?

    [teaser2608]

     
    • Jim Randell's avatar

      Jim Randell 8:01 am on 5 November 2024 Permalink | Reply

      If a captain knows that they are tied on points with another team, then they cannot know which way the tie breaking will go, as they do not know how many goals the other team scored in their remaining match, so any situation where teams are tied on points will necessarily require the captain to respond that they do not know their final position.

      This Python program uses the [[ Football() ]] helper class, and the [[ filter_unique() ]] function from the enigma.py library to solve the puzzle.

      It runs in 69ms. (Internal runtime is 838µs).

      from enigma import (Football, filter_unique, printf)
      
      # scoring system
      football = Football(games='wdl', points=dict(w=3, d=1))
      
      # calculate positions from points, ties are indicated with '='
      def pos(pts):
        rs = [None] * len(pts)
        p = 1
        for x in sorted(set(pts), reverse=1):
          k = pts.count(x)
          v = str(p)
          if k > 1: v += '='
          for (i, y) in enumerate(pts):
            if y == x:
              rs[i] = v
          p += k
        return tuple(rs)
      
      is_tie = lambda x: x.endswith('=')
      
      # generate possible situations
      def generate():
        # consider possible game outcomes
        for (AB, AC, BC) in football.games(repeat=3):
          # table for each team
          A = football.table([AB, AC], [0, 0])
          B = football.table([AB, BC], [1, 0])
          C = football.table([AC, BC], [1, 1])
          # return (<match-outcomes>, <positions>)
          yield ((AB, AC, BC), pos([A.points, B.points, C.points]))
      
      # indices for the teams, and the matches
      (A, B, C) = (AB, AC, BC) = (0, 1, 2)
      matches = { A: (AB, AC), B: (AB, BC), C: (AC, BC) }
      
      # can team <j> deduce their finishing position knowing the outcomes of their own matches?
      # <f> = 0 if the answer is "no"; = 1 if it is "yes"
      def answer(ss, j, f):
        # which matches is team <j> involved in?
        ms = matches[j]
        fnf = lambda t: tuple(t[0][i] for i in ms)
        fng = lambda t: t[1][j]
        # find results with unique/non-unique positions
        r = filter_unique(ss, fnf, fng)
        if f == 0:
          # return results that are non-unique, or end with a tie on points
          return r.non_unique + [t for t in r.unique if is_tie(fng(t))]
        else:
          # return results that are unique, but don't end with a tie on points
          return [t for t in r.unique if not is_tie(fng(t))]
      
      # start with all possible outcomes and positions
      ss = list(generate())
      
      # A cannot deduce his finishing position
      ss = answer(ss, A, 0)
      
      # B cannot deduce his finishing position
      ss = answer(ss, B, 0)
      
      # C cannot deduce his finishing position
      ss = answer(ss, C, 0)
      
      # A can now deduce his finishing position
      ss = answer(ss, A, 1)
      
      # output solutions
      for ((AB, AC, BC), (posA, posB, posC)) in ss:
        printf("posC = {posC}; AB = {AB} [AB={AB} AC={AC} BC={BC}; posA={posA} posB={posB} posC={posC}]")
      

      Solution: Charile finished in second place. The game between Alf and Bert was a draw.

      The match outcomes are either:

      (A v B = draw; C beat A; B beat C)
      B = 1w 1d = 4 pts (1st)
      C = 1w = 3 pts (2nd)
      A = 1d = 1 pt (3rd)

      or:

      (A v B = draw; A beat C; C beat B)
      A = 1w 1d = 4 pts (1st)
      C = 1w = 3pts (2nd)
      B = 1d = 1pt (3rd)

      Like

  • Unknown's avatar

    Jim Randell 8:39 am on 15 October 2024 Permalink | Reply
    Tags: by: John Owen   

    Teaser 2439: [Higher or lower] 

    From The Sunday Times, 21st June 2009 [link]

    Six cards are numbered 1 to 6. One card is placed on the forehead of each of three expert logicians. Each can see the other numbers, but not his own. I asked each in turn if his number was higher, lower or the same as the average of all three. They replied as follows:

    Alf: I don’t know.
    Bert: I don’t know.
    Charlie: I don’t know.

    If I now told you the product of the three numbers, you could work out which number each holds.

    What numbers did Alf, Bert and Charlie hold (in that order)?

    This puzzle was originally published with no title.

    I received a message via the “Contact” form asking for a solution to this puzzle.

    [teaser2439]

     
    • Jim Randell's avatar

      Jim Randell 8:39 am on 15 October 2024 Permalink | Reply

      We can start with all possible scenarios – there are P(6, 3) = 120.

      Then, knowing A says “don’t know” we can remove any candidates where A would know. For example: if A were to see 1 and 2, he would know that whatever his card is (3, 4, 5, or 6) it would be more than the average of the three cards. Similarly, if he were to see 5 and 6, then he would know that whatever his card was (1, 2, 3, or 4) it would be less than the average of the 3 cards.

      This whittles the number of candidates down to 104.

      We can then apply the same reasoning to these remaining candidates, knowing that B says “don’t know”, which gets us down to 70 candidates.

      Finally applying the same process to these candidates, knowing that C says “don’t know”, gets us down to 22 candidate scenarios.

      And only one of the remaining candidates is unique by the product of the numbers. (In fact all the other candidates appear in multiple permutations, so must have repeated products).

      This Python program performs these steps. It runs in 71ms. (Internal runtime is 1.8ms).

      from enigma import (
        irange, compare, seq_all_same, subsets, group, multiply, join, printf
      )
      
      values = set(irange(1, 6))
      
      # return situations from <ss> where <i> answers "don't know" on seeing <j> and <k>
      def check(ss, i, j, k):
        # consider possible situations
        for s in ss:
          # find possible candidates from i's POV (same j and k)
          ts = (t for t in ss if t[j] == s[j] and t[k] == s[k])
          # do the candidates give multiple different answers?
          if not seq_all_same(compare(2 * t[i], t[j] + t[k]) for t in ts):
            # if so keep this situation
            yield s
      
      # initial list of candidate (A, B, C) assignments
      ss = set(subsets(values, size=3, select='P'))
      printf("[start: {n} candidates]", n=len(ss))
      
      # label A, B, C
      (A, B, C) = (0, 1, 2)
      
      # remove candidates that don't give a "don't know" from A
      ss = set(check(ss, A, B, C))
      printf("[after A: {n} candidates]", n=len(ss))
      
      # now remove candidates that don't give a "don't know" from B
      ss = set(check(ss, B, A, C))
      printf("[after B: {n} candidates]", n=len(ss))
      
      # now remove candidates than don't give a "don't know" from C
      ss = set(check(ss, C, A, B))
      printf("[after C: {n} candidates]", n=len(ss))
      
      # group the remaining candidates by product
      g = group(ss, by=multiply)
      
      # look for candidates with a unique product
      for (p, cs) in g.items():
        if len(cs) != 1: continue
        printf("product = {p} -> {cs}", cs=join(cs, sep=" "))
      

      Solution: Alf had 5, Bert had 3, Charlie had 4.

      Like

    • Frits's avatar

      Frits 5:31 am on 25 October 2024 Permalink | Reply

      If Bert heard Alf’s answer and Charlie heard Alf’s and Bert’s answer then the reported solution is incorrect (Charlie would say “lower”).

      Like

      • Jim Randell's avatar

        Jim Randell 9:29 am on 25 October 2024 Permalink | Reply

        @Frits: I think C would not know whether to say “lower” or “same”, so has to say “don’t know”. (And in the actual situation C’s number is the same as the arithmetic mean, so he cannot know that it is lower).

        Like

    • Frits's avatar

      Frits 11:29 am on 25 October 2024 Permalink | Reply

      @Jim, Sorry, I got confused with (5, 4, 3).

      Like

  • Unknown's avatar

    Jim Randell 6:16 am on 4 August 2024 Permalink | Reply
    Tags: by: John Owen   

    Teaser 3228: Prime tiles 

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

    Ann, Beth and Chloe play a game with tiles. The prime numbers from 3 to 41 inclusive are written on 12 tiles, and each player receives 4 tiles. An odd starting number is chosen at random, then each player in turn tries, if possible, to increase the total to a prime number, by adding two of their tiles. For example, if the starting number is 5, Ann could play 11 and 31 to make the total 47, then Beth might be able to play 5 and 7 to make 59 and so on.

    In a game where the starting number was 3, Ann was first, but couldn’t play. Beth and Chloe both took their turns, but again Ann was unable to play.

    In ascending order, which four tiles did Beth and Chloe play?

    [teaser3228]

     
    • Jim Randell's avatar

      Jim Randell 6:32 am on 4 August 2024 Permalink | Reply

      This Python program runs in 68ms. (Internal runtime is 2.8ms).

      Run: [ @replit ]

      from enigma import (primes, subsets, diff, ordered, printf)
      
      # available tiles
      tiles = list(primes.between(3, 41))
      
      # starting total
      t0 = 3
      
      # choose 4 tiles for A
      for As in subsets(tiles, size=4):
        # A is unable to play
        if any(t0 + x + y in primes for (x, y) in subsets(As, size=2)): continue
      
        # B plays two tiles
        for (b1, b2) in subsets(diff(tiles, As), size=2):
          t1 = t0 + b1 + b2
          if t1 not in primes: continue
      
          # C plays 2 tiles
          for (c1, c2) in subsets(diff(tiles, As, (b1, b2)), size=2):
            t2 = t1 + c1 + c2
            if t2 not in primes: continue
      
            # A is unable to play
            if any(t2 + x + y in primes for (x, y) in subsets(As, size=2)): continue
      
            # output solution
            played = ordered(b1, b2, c1, c2)
            printf("played = {played} [A={As}; {t0} -> ({b1}, {b2}) -> {t1} -> ({c1}, {c2}) -> {t2}]")
      

      Solution: The tiles Beth and Chloe played were 7, 23, 31, 37.

      A’s tiles were: 5, 13, 19, 41.

      There are 3 possible games:

      3 → (7, 31) → 41 → (23, 37) → 101
      3 → (7, 37) → 47 → (23, 31) → 101
      3 → (31, 37) → 71 → (7, 23) → 101

      but in all cases the tiles played by B and C are: 7, 23, 31, 37.

      Like

      • Ruud's avatar

        Ruud 10:52 am on 5 August 2024 Permalink | Reply

        Similar to @Frits:

        import itertools
        
        
        def is_prime(n):
            if n < 2:
                return False
            if n == 2:
                return True
            if not n & 1:
                return False
            for x in range(3, int(n**0.5) + 1, 2):
                if n % x == 0:
                    return False
            return True
        
        
        primes = set(n for n in range(3, 42) if is_prime(n))
        
        for a in itertools.combinations(primes, 4):
            bc = primes - set(a)
            total = 3
            if not any(is_prime(total + sum(a2)) for a2 in itertools.combinations(a, 2)):
                for b2 in itertools.combinations(bc, 2):
                    if is_prime(total + sum(b2)):
                        for c2 in itertools.combinations(bc - set(b2), 2):
                            if is_prime(total + sum(b2) + sum(c2)):
                                if not any(is_prime(total + sum(b2) + sum(c2) + sum(a2)) for a2 in itertools.combinations(a, 2)):
                                    print(sorted(b2 + c2))
        

        Like

    • Frits's avatar

      Frits 10:05 am on 4 August 2024 Permalink | Reply

      from itertools import combinations
      
      # determine valid primes up to approx 6 * 41
      P = {3, 5, 7}
      P |= {x for x in range(11, 100, 2) if all(x % p for p in P)}
      P |= {x for x in range(101, 240, 2) if all(x % p for p in P)}
      
      sols, t = set(), 3  
      tiles = {p for p in P if 3 <= p <= 41}
      
      # pick four tiles for Ann
      for a4 in combinations(tiles, 4):
        # check if any two of Ann's tiles make a prime (with 3)
        for a2 in combinations(a4, 2):
          if (sum(a2) + t) in P: break
        else: # no break, Ann couldn't play  
          # pick 2 playable tiles for Beth
          for b2 in combinations(tiles.difference(a4), 2):
            if (t_b := (sum(b2) + t)) not in P: continue
            # pick 2 playable tiles for Chloe
            for c2 in combinations(tiles.difference(a4 + b2), 2):
              if (t_c := (sum(c2) + t_b)) not in P: continue
              # check if any two of Ann's tiles can make a prime
              for a2 in combinations(a4, 2):
                if (sum(a2) + t_c) in P: break
              else: # no break, Ann couldn't play  
                sols.add(tuple(sorted(b2 + c2)))
                
      # print the solution(s)          
      for s in sols:
        print(f"answer: {s}")     
      

      Like

    • Frits's avatar

      Frits 12:10 pm on 4 August 2024 Permalink | Reply

      Less efficient.

      from itertools import combinations
      
      # determine valid primes up to approx 6 * 41
      P = {3, 5, 7}
      P |= {x for x in range(11, 100, 2) if all(x % p for p in P)}
      P |= {x for x in range(101, 240, 2) if all(x % p for p in P)}
      
      sols, t = set(), 3  
      tiles = [p for p in P if 3 <= p <= 41]
      
      # combinations of 4 tiles that sum to a certain total
      d = {t: [c4 for c4 in combinations(tiles, 4) 
               if sum(c4) == t] for t in range(26, 139, 2)}
               
      # pick four tiles for Ann
      for a4 in combinations(tiles, 4):
        # starting totals where Ann cannot play
        npt = {t for t in range(3, 142, 2) 
               if all((sum(a2) + t) not in P for a2 in combinations(a4, 2))}
        if 3 not in npt: continue
        
        # check non-playing totals (besides total <t>)
        for np in npt:
          if np == t: continue
          # get 4 tiles for Beth and Chloe ...
          for t4 in d[np - t]:
            # ... that differ from Ann's tiles
            if len(set(a4 + t4)) != 8: continue
            
            # can we make a prime with 2 numbers of <t4>
            for b2 in combinations(t4, 2):
              if (t_b := sum(b2) + t) not in P: continue
              # can we make a prime with 2 numbers of <t4>
              c2 = set(t4).difference(b2)
              if (t_c := sum(c2) + t_b) not in P: continue
              sols.add(tuple(sorted(b2 + tuple(c2))))
      
      # print the solution(s)          
      for s in sols:
        print(f"answer: {s}")           
      

      Like

  • Unknown's avatar

    Jim Randell 11:52 am on 12 March 2024 Permalink | Reply
    Tags: by: John Owen   

    Teaser 2646: Monday birthdays 

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

    In one auspicious month last year our family had two great celebrations: Harry, the oldest member of the family, had his 100th birthday and, in the same month, his great-grandson Peter was born.

    It turns out that they were both born on the same day of the week. Of course, Harry has celebrated several of his 100 birthdays on a Monday, as will Peter. However, even if Peter lives that long, the number of his first 100 birthdays that fall on a Monday will be two fewer than Harry’s.

    On which day of the week were they born?

    [teaser2646]

     
    • Jim Randell's avatar

      Jim Randell 11:52 am on 12 March 2024 Permalink | Reply

      This puzzle was set in 2013, so Harry had his 100th birthday in 2012, and so was born in 1912.

      Peter was born in the same month in 2012 as Harry’s 100th birthday, so Peter’s 100th birthday will be in 2112.

      And we are interested in counting birthdays that fall on a Monday.

      This Python program collects candidate birthdays >(month, day) for each of them and groups them by the number of Monday birthdays in the first 100. We then look for situations where Harry has 2 more Monday birthdays that Peter, and then try to find common (weekday, month) combinations.

      It runs in 63ms. (Internal runtime is 3.1ms).

      Run: [ @replit ]

      from datetime import (date, timedelta)
      from enigma import (defaultdict, group, intersect, printf)
      
      # collect birthdays between y1 and y2 that fall on a Monday
      def collect(y1, y2):
        # find the first Monday (weekday = 0) in the range
        inc = timedelta(days=1)
        d = date(y1, 1, 1)
        while d.weekday() != 0: d += inc
        # and then skip forward by weeks
        inc = timedelta(days=7)
        # count the number of Monday birthdays by date
        r = defaultdict(int)
        while True:
          r[(d.month, d.day)] += 1
          d += inc
          if d.year > y2: break
        # group dates by Monday count
        return group(r.keys(), by=r.get)
      
      # count birthdays on a Monday for Harry from 1913 - 2012
      gH = collect(1913, 2012)
      # count birthdays on a Monday to Peter from 2013 - 2112
      gP = collect(2013, 2112)
      
      # collect results
      rs = set()
      
      # consider possible counts for H
      for (kH, vH) in gH.items():
        # P has a count that is 2 less
        kP = kH - 2
        vP = gP.get(kP)
        if vP is None: continue
      
        # collect possible (weekday, month) combinations for Harry and Peter
        fn = lambda d: (d.weekday(), d.month)
        dH = group((date(1912, m, d) for (m, d) in vH), by=fn)
        dP = group((date(2012, m, d) for (m, d) in vP), by=fn)
      
        # look for (weekday, month) combinations common to both
        for (w, m) in intersect([dH.keys(), dP.keys()]):
          rs.add(w)
      
      # find possible days of the week
      days = ['Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat', 'Sun']
      for w in rs:
        printf("weekday = {w}", w=days[w])
      

      Solution: Harry and Peter were both born on a Tuesday.

      And they could be both born on Tuesdays in any month from March to December.

      For example:

      Harry was born on Tuesday, 5th March 1912, and has had 15 birthdays on a Monday up to 2012 (in years: 1917, 1923, 1928, 1934, 1945, 1951, 1956, 1962, 1973, 1979, 1984, 1990, 2001, 2007, 2012).

      Peter was born on Tuesday, 6th March 2012, and will have 13 birthdays on a Monday up to 2112 (in years: 2017, 2023, 2028, 2034, 2045, 2051, 2056, 2062, 2073, 2079, 2084, 2090, 2102).

      The sequences differ because 2000 was a leap year, but 2100 will not be.

      Like

  • Unknown's avatar

    Jim Randell 8:21 am on 13 February 2024 Permalink | Reply
    Tags: by: John Owen   

    Teaser 2661: Three clocks 

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

    I have three digital clocks, each showing the time as a four-digit display “hhmm” on the 24-hour scale. One keeps perfect time, one runs fast at a constant rate (less than a minute per day) and the third runs slow at exactly the same rate. Every six months I simultaneously reset the faulty clocks to the correct time. Recently I noticed that each clock displayed the same collection of digits but in different orders. In fact, on the fast clock no digit was in the correct place.

    What time did the correct clock show at that moment?

    [teaser2661]

     
    • Jim Randell's avatar

      Jim Randell 8:22 am on 13 February 2024 Permalink | Reply

      If the clocks are reset every 6 months then that is at most 184 days apart. So the inaccurate clocks are less than 184 minutes adrift from the accurate clock.

      This Python program collects together times that use the same digits but rearranged, and then looks for a collection of at least 3 different times, chooses a correct time, and looks for a fast time that is a derangement of the correct time. From this we calculate the difference window for the inaccurate clocks, and we can look for a corresponding slow time that appears in the same collection.

      It runs in 67ms. (Internal runtime is 9.8ms).

      Run: [ @replit ]

      from enigma import (defaultdict, irange, cproduct, ordered, dot, printf)
      
      # collect possible times by digit content
      d = defaultdict(list)
      for (hh, mm) in cproduct([irange(0, 23), irange(0, 59)]):
        ds = divmod(hh, 10) + divmod(mm, 10)
        d[ordered(*ds)].append(ds)
      
      # digit position values (in minutes, left to right)
      pos = (600, 60, 10, 1)
      
      # look for sets of digits corresponding to at least 3 times
      for (k, vs) in d.items():
        if len(vs) < 3: continue
      
        # choose the correct time
        for corr in vs:
          mc = dot(corr, pos)
          # choose a fast time
          for fast in vs:
            # which must be a derangement of corr
            if fast == corr or any(x == y for (x, y) in zip(fast, corr)): continue
            # calculate the window of difference (in minutes)
            md = (dot(fast, pos) - mc) % 1440
            if md > 183: continue
      
            # look for possible slow times (difference may be +/- 1)
            for w in [-1, 0, +1]:
              ms = (mc - md + w) % 1440
              (hh, mm) = divmod(ms, 60)
              slow = divmod(hh, 10) + divmod(mm, 10)
              if slow not in vs: continue
      
              # output solution
              printf("correct = {corr}; fast = {fast}; slow={slow}")
      

      Solution: The correct clock was showing: 2301.

      And the inaccurate clocks are adrift from the accurate clock by 150 – 151 minutes.

      For example, using fractional minutes we can suppose the accurate clock is showing:

      23:01.75 → 2301

      If the time difference with the inaccurate clocks is 150.5 minutes (= 2h30.5m) then the fast clock is showing:

      01:32.25 → 0132

      and the slow clock is showing:

      20:31.25 → 2031

      Each display uses the digits: 0, 1, 2, 3.

      Like

    • Frits's avatar

      Frits 4:39 am on 23 February 2024 Permalink | Reply

      I have a different version that matches Jim’s speed (but with more code).

          
      from enigma import SubstitutedExpression
      
      # invalid digit / symbol assignments
      d2i = dict()
      for d in range(0, 10):
        vs = set()
        if d > 1: vs.update('X')
        if d > 2: vs.update('AFSW')
        if d > 5: vs.update('CHU')
      
        d2i[d] = vs 
      
      # return time difference in minutes between h1:m1 and an earlier h2:m2  
      def diff_minutes(h1, m1, h2, m2):
        d = 60 * (h1 - h2) + m1 - m2 
        return d if d > 0 else 1440 + d
      
      # remove elements from list <s2> from list <s1>
      # eg diff_lists([1,3,1,2], [2,0,1]) results in [3,1]
      def diff_lists(s1, s2):
        for x in s2:
          if x in s1:
            s1.remove(x)
        return s1
      
      # correct : AB:CD
      # fast    : FG:HI
      # slow    : ST:UV
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
          "AB < 24", 
          # ----- logic for fast clock FG:HI ------
          # speeding things up: check for <I>
          "(D + Z) % 10 in {A, B, C, D}",
      
          # add XYZ minutes for fast clock
          "0 < XYZ < 184",
          "(60 * AB + CD + XYZ) % 1440 = OPQR",
          "OPQR // 60 = FG",
          "OPQR % 60 = HI",
      
          # the same collection of digits 
          "sorted([A, B, C, D]) == sorted([F, G, H, I])",
        
          # ----- logic for slow clock ST:UV ------
          # 2 * correct = fast + slow + 1 - W with 0 <= W <= 2
          "(2 * (60 * AB + CD) - (60 * FG + HI) - 1 + W) % 1440 = KLMN",
          "KLMN // 60 = ST",
          "KLMN % 60 = UV",
          
          # the same collection of digits 
          "sorted([A, B, C, D]) == sorted([S, T, U, V])",
        ],
        answer="ABCD",
        d2i=d2i,
        # on the fast clock no digit was in the correct place
        distinct=("AF", "BG", "CH", "DI"),
        env=dict(diff_minutes=diff_minutes, diff_lists=diff_lists),
        reorder=0,
        verbose=0,    # use 256 to see the generated code
      )
      
      # print answers
      for ans in sorted(p.answers()):
        print(f"answer: {ans}")
      

      Like

  • Unknown's avatar

    Jim Randell 8:30 am on 19 December 2023 Permalink | Reply
    Tags: by: John Owen   

    Brainteaser 1087: Pennies from heaven 

    From The Sunday Times, 5th June 1983 [link]

    In our club we have three one-armed bandits. The Saturn Skyjacker accepts 10p, 2p and 1p coins, the Mars Marauder accepts 10p and 1p coins, and the Aries Axeman accepts 5p and 2p coins.

    I am the club treasurer, so each week I have the onerous task of emptying the machines and counting the coins. Last week, my efforts were rewarded with the discovery of an interesting series of coincidences. On counting the coins for the Saturn Skyjacker, I found that there were the same number of coins of two of the denominations, and that the number of coins of the third denomination differed from this number by only one. In addition, the total value of all the coins was an exact number of pounds less than one hundred.

    The coins from the Mars Marauder were similarly distributed: the numbers of 10p and 1p coins differed by only one, and the total value was again an exact number of pounds. In fact, this total value was the same as for the Saturn Skyjacker.

    Incredibly, the same was true for coins from the Aries Axeman: the numbers of 5p and 2p coins differed by one, and the total value was the same as for the Mars Marauder and the Saturn Skyjacker.

    What was the total number of coins I emptied that day?

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

    [teaser1087]

     
    • Jim Randell's avatar

      Jim Randell 8:31 am on 19 December 2023 Permalink | Reply

      This Python program runs in 60ms. (Internal runtime is 306µs).

      Run: [ @replit ]

      from enigma import (irange, div, cproduct, printf)
      
      # decompose t into k * x and (k +/- 1) * y
      def decompose(t, x, y):
        k = div(t - y, x + y)
        if k: yield (k, k + 1)
        k = div(t + y, x + y)
        if k: yield (k, k - 1)
      
      # total number of pounds is less than 100
      for t in irange(100, 9900, step=100):
        # can we make this total for (10, 1) and (5, 2)
        for (m, a) in cproduct([decompose(t, 10, 1), decompose(t, 5, 2)]):
          # try to make t from (10, 2, 1) by combining 2 of the values
          for (x, y) in [(12, 1), (11, 2), (3, 10)]:
            for s in decompose(t, x, y):
              # calculate total number of coins
              n = sum(m) + sum(a) + sum(s) + s[0]
              # output solution
              printf("{n} coins [t={t}: m={m} a={a} -> x={x} y={y} s={s}]")
      

      Solution: The total number of coins is: 3001.

      In the Saturn Skyjacker there were 331× 10p + 330× 2p + 330× 1p = 4300p.

      In the Mars Marauder there were 391× 10p + 390× 1p = 4300p.

      In the Aries Axman there were 614× 5p + 615× 2p = 4300p.

      So in total there were 3001 coins totalling £129.

      Like

    • Frits's avatar

      Frits 2:48 pm on 19 December 2023 Permalink | Reply

       
      # coins (pennies) for Saturn Skyjacker, the Mars Marauder and the Aries Axeman
      cs = [{1, 2, 10}, {1, 10}, {2, 5}]
      
      # total number of pounds is less than 100
      for t in range(100, 10000, 100):
        # remainder by sum of coin denominations should be equal to one of the 
        # coin denominations or equal to the sum of all coin denominations but one
        if all((t % sum(c)) in c | {sum(c) - x for x in c} for c in cs):
          print("answer:", sum(len(c) * (t // sum(c)) + 
                (1 if (t % sum(c)) in c else len(c) - 1) for c in cs))  
      

      Like

    • GeoffR's avatar

      GeoffR 8:36 pm on 27 December 2023 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      % Saturn Skyjacker coins are 1p, 2p and 10p
      var 1..9999:SS;   % maximum Saturn Skyjacker total(p)
      
      % Assumed UB for SS, MM and AA coin numbers
      var 1..1000:s10; var 1..1000:s2; var 1..1000:s1; 
      
      % Two coins hae the same number, differing fron the other denomination by 1
      constraint (s10 == s2 /\ abs(s10 - s1) == 1)
      \/ (s10 == s1 /\ abs(s10 - s2) == 1)
      \/ (s1 == s2 /\ abs(s1 - s10) == 1);
      
      constraint s1*1 + s2*2 + s10*10 == SS;
      constraint SS div 100 < 100 /\ SS mod 100 == 0;
      
      % Mars Marauder coins 1p and 10p
      var 1..9999:MM; % maximum Mars Marauder total(p)
      var 1..1000:m1; var 1..1000:m10;
      
      % Mars Marauder coin numbers differ by 1
      constraint abs(m1 - m10) == 1;
      constraint MM = m1 * 1  + m10 * 10;
      constraint MM div 100 < 100 /\ MM mod 100 == 0;
      
      % Aries Axem coins are 2p and 5p
      var 1..9999:AA; % maximum Aries Axem  total(p)
      var 1..1000:a2; var 1..1000:a5;
      
      % Aries Axem coin numbers differ by 1
      constraint abs(a2 - a5) == 1;
      constraint AA = a2 * 2  + a5 * 5;
      constraint AA div 100 < 100 /\ AA mod 100 == 0;
      
      % Total amount from three machines is the same
      constraint MM == SS /\ MM == AA;
      
      % Total number of coins
      var 1..7000:tot_coins == s1 + s2 + s10 + m1 + m10 + a2 + a5;
      
      solve satisfy;
      
      output[" Total number of coins = " ++ show(tot_coins) ++ "\n" ++
      " Saturn coins are s1, s2, s10 = " ++ show([s1, s2, s10] ) ++ "\n" ++
      " Mars coins m1 and m10 = " ++ show([m1, m10]) ++ "\n" ++
      " Aries coins are a2 and a5 = " ++ show([a2, a5]) ++ "\n" ++
      " Total value in each machine = £" ++ show(SS div 100) ];
      
      %  Total number of coins = 3001
      %  Saturn coins are s1, s2, s10 = [330, 330, 331]
      %  Mars coins m1 and m10 = [390, 391]
      %  Aries coins are a2 and a5 = [615, 614]
      %  Total value in each machine = £43
      % ----------
      % ==========
      % Finished in 506msec.
      
      

      Like

  • Unknown's avatar

    Jim Randell 4:27 pm on 22 September 2023 Permalink | Reply
    Tags: by: John Owen   

    Teaser 3183: Partial eclipse 

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

    Alf, Bert and Charlie were comparing their experiences of the eclipse from different locations. The moon appeared to be exactly the same size as the sun as it passed in front of part of the sun’s disc. The magnitude of an eclipse measures the maximum part of the diameter of the sun’s disc that is obscured. Taking the apparent diameter of the sun as 100, they noted the following:

    Alf: “My magnitude was a whole number”.
    Bert: “If I took the part of the sun’s circumference that was obscured, multiplied it by the radius and then subtracted the area of the sun’s disc that was obscured, I also got a whole number”.
    Charlie: “Both of those statements are true for all of us, but we all saw different magnitudes greater than 10”.

    In increasing order, what were those three magnitudes?

    As well as this puzzle being Teaser 3183 there are now 3183 puzzles posted in total between the Enigmatic Code and S2T2 sites.

    [teaser3183]

     
    • Jim Randell's avatar

      Jim Randell 4:55 pm on 22 September 2023 Permalink | Reply

      If we suppose the apparent radius of the two discs is R, and we consider the part of the circumference of the sun that is obscured, then it forms the arc of a circular sector that subtends an angle of at the centre of the sun’s disc. The length of the obscured circumference is then: 2Rθ.

      The area of the part of the sun’s disc that is obscured A can be calculated as the sum of two equal obscured segments, each being the area of the circular sector less the area of the triangle formed by replacing the arc of the sector with a chord.

      A = 4 [(𝛑R²)(θ/2𝛑) − (R cos(θ))(R sin(θ))/2)
      A = 2R²θ − 2R²sin(θ)cos(θ)
      A = R²(2θ − sin(2θ))

      (See also: [@wikipedia])

      And so B’s measure is:

      B = 2R²θ − A

      B = 2R²sin(θ)cos(θ)
      B = R²sin(2θ)

      And A’s measure (the magnitude) m is given by:

      m = 2R(1 − cos(θ))

      So given an integer magnitude, we can calculate a rational value for cos(θ), and using the identity cos²(θ) + sin²(θ) = 1 we can calculate a value for sin(θ), which must also be rational if B is to have an integer value.

      This Python program runs in 61ms. (Internal runtime is 413µs).

      from enigma import (Rational, irange, is_square_q, sq, as_int, printf)
      
      Q = Rational()
      
      # apparent radius
      R = 50
      
      # consider possible magnitudes from 11 to 99
      for m in irange(11, 99):
        # calculate cos(theta), sin(theta)
        cost = 1 - Q(m, 2 * R)
        sint = is_square_q(1 - sq(cost), F=Q)
        if sint is None: continue
        # calculate B's measure
        B = 2 * sq(R) * sint * cost
        # is it an integer?
        B = as_int(B, default=None)
        if B is None: continue
        # output solution
        printf("m={m} -> B={B}")
      

      Solution: The magnitudes are: 20, 40, 72.

      And we have:

      m = 20 → B = 2400
      m = 40 → B = 2400
      m = 72 → B = 1344

      There are only 3 values because the “partner” value for m = 72 (which also gives B = 1344) is m = 4.

      Like

      • Frits's avatar

        Frits 8:47 pm on 22 September 2023 Permalink | Reply

        I had to look up some formula and came to the same formula for B.

           
        # apparent radius
        R = 50
        
        # consider possible magnitudes from 11 to 99
        for m in range(11, 100):
          # calculate cos(theta)
          c = 1.0 - m / (2 * R)
          # calculate sin(theta), c^2 + s^2 = 1
          s = (1 - c**2)**.5
          # B = r^2.sin(2 * theta), sin(2x) = 2.sin(x).cos(x) 
          B = 2 * R * R * s * c
          
          # is it close to an integer?
          if abs(B - round(B)) > 1e-6: continue
         
          # output solution
          print(f"m={m} -> B={B:.2f}")
        

        Like

      • Jim Randell's avatar

        Jim Randell 2:38 pm on 23 September 2023 Permalink | Reply

        With a bit more work we can simplify the calculation of B to:

        B = (1/2)(2R − m)√(m(4R − m))

        Which gives a simpler program, that only uses integers:

        Run: [ @replit ]

        from enigma import (irange, is_square, div, printf)
        
        # apparent radius
        R = 50
        
        # consider possible magnitudes from 11 to 99
        for m in irange(11, 99):
          r = is_square(m * (4 * R - m))
          if r is None: continue
          B = div((2 * R - m) * r, 2)
          if B is None: continue
          # output solution
          printf("m={m} -> B={B}")
        

        Like

  • Unknown's avatar

    Jim Randell 4:38 pm on 28 July 2023 Permalink | Reply
    Tags: by: John Owen   

    Teaser 3175: Blindfold roulette 

    From The Sunday Times, 30th July 2023 [link] [link]

    Our roulette wheel has fewer than 100 equal-sized sectors. Before each game a fixed number (fewer than half) of the sectors are randomly designated winning ones and the others as losing. A player can see which are the winning sectors, then is blindfolded. A ball is then placed at random in a winning sector and the player chooses to spin (S) the wheel or move (M) the ball clockwise by one sector. The game continues from there (the player has the same  choices) and ends when the ball lands in a losing sector.

    Alf’s longest winning run was MMSM while Bert’s was SSS and Charlie’s was MMMS. Being expert logicians, they had always chosen the option that gave the better chance of the ball landing in a winning sector. Remarkably, the probabilities of achieving each run of success were the same.

    How many sectors are there and how many are winning sectors?

    [teaser3175]

     
    • Jim Randell's avatar

      Jim Randell 6:55 pm on 28 July 2023 Permalink | Reply

      This is my first stab at a program that explores the solution space looking for viable solutions. It is not very fast (it runs in 1.31s), and it stops after the first viable solution is found. (A second viable solution is eliminated by rejecting situations where both plays have the same probability).

      It works by considering possible the total number of sectors n, and the number of winning sectors w, and then dividing the winning sectors into contiguous clumps, and calculating the corresponding probabilities.

      Run: [ @replit ]

      from enigma import (Rational, irange, decompose, intersect, divf, seq2str, printf)
      
      Q = Rational()
      
      # with <n> sectors, <w> winning in clumps <ws>, find probability of seq <seq>
      def prob(n, w, ws, seq):
        P = 1
        # calculate probability of a good spin
        S = Q(w, n)
        # calculate probability of a good move
        zs = ws  # winning zones
        for v in seq:
          z = sum(zs)
          zs = list(x - 1 for x in zs if x > 1)
          M = Q(sum(zs), z)
          # check the sequence
          if v == 'M' and M > S:
            P *= M
          elif v == 'S' and S > M:
            P *= S
            zs = ws
          else:
            return
        return P
      
      # with <n> sectors, <w> winning, collect common probabilities for sequences <ss>
      def solve(n, w, ss):
        # collect probabilities
        d = dict((k, set()) for k in ss)
        # break the sectors into k contiguous blocks
        for k in irange(1, w):
          for ws in decompose(w, k, increasing=1, sep=0, min_v=1):
            # calculate the probabilities for A, B, C
            for (k, v) in d.items():
              P = prob(n, w, ws, k)
              if P is not None: v.add(P)
        # return common probabilities
        return intersect(d.values())
      
      # solve the puzzle
      def main():
        # consider number of sectors <n>
        for n in irange(9, 99):
          # consider number of winning sectors <w>
          for w in irange(4, divf(n - 1, 2)):
            # find common probabilities
            ps = solve(n, w, ['MMSM', 'SSS', 'MMMS'])
            if ps:
              printf("n={n} w={w} -> P={ps}", ps=seq2str(ps))
              return  # stop at the first solution
      
      main()
      

      Solution: There are 54 sectors in total, and 18 winning sectors.

      In this case the probability of a good spin is:

      P(S) = 18/54 = 1/3

      So the probability of B’s run of SSS is:

      P(SSS) = (1/3)³ = 1/27

      And a configuration where each winning sector is isolated from the other winning sectors makes the probability of a good M move zero, so this is possible (although this is not the only viable configuration to permit this – there are 19 in total).

      For A there are 2 possible configurations, one of them is:

      (1, 1, 1, 1, 2, 3, 3, 3, 3)

      Of the 18 winning sectors there are 9 that have a winning sector as a clockwise neighbour:

      P(M) = 9/18 = 1/2 [which is > 1/3]

      And of those 9 sectors only 4 of them have 2 neighbouring winning sectors going clockwise:

      P(MM|M) = 4/9 = 1/2 [which is > 1/3]

      And there are no winning sectors with 3 neighbouring clockwise winning sectors:

      P(MMM|MM) = 0 [which is < 1/3]

      So at this point A would choose S, which resets the situation back to the start, so the next choice (if he gets one) would be M.

      Hence the overall probability of MMSM is:

      P(MMSM) = (9/18)×(4/9)×(1/3)×(9/18) = 1/27

      which is the same as B’s run.

      For C, with a configuration (chosen from 9 possibilities) of:

      (2, 2, 2, 2, 2, 4, 4)

      We get:

      P(M) = 11/18
      P(MM|M) = 4/11
      P(MMM|MM) = 2/4 = 1/2

      P(MMMS) = (11/18)×(4/11)×(2/4)×(1/3) = 1/27


      However if we permit situations where the probabilities of M and S are equal then there is a further solution with 64 total sectors and 16 winning sectors.

      The probability of a good S is:

      P(S) = 16/64 = 1/4

      And choosing a configuration (of 12 the possible configurations) where each winning sector is isolated we get:

      P(SSS) = (1/4)³ = 1/64

      For A the only possible distribution is:

      (1, 1, 2, 2, 2, 2, 3, 3)

      which gives:

      P(M) = 8/16 = 1/2
      P(MM|M) = 2/8 = 1/4 [same as P(S)]

      P(MMSM) = (8/16)×(2/8)×(1/4)×(8/16) = 1/64

      And for C there are 14 possible distributions, we choose:

      (2, 2, 2, 3, 3, 4)

      which gives:

      P(M) = 10/16 = 5/8
      P(MM|M) = 4/10 = 2/5
      P(MMM|MM) = 1/4 [same as P(S)]

      P(MMMS) = (10/16)×(4/10)×(1/4)×(1/4) = 1/64

      So in order for the puzzle to have a unique answer, we have to eliminate scenarios where when choosing between M and S that calculated probabilities are the same

      Like

      • Jim Randell's avatar

        Jim Randell 10:55 am on 30 July 2023 Permalink | Reply

        By analysing the probabilities associated with the given sequences (which I will post later) we can eliminate a lot of the testing done by my program above.

        Here it is adapted to include the conditions:

        decomposition for A must include a clump of size 3 or more
        decomposition for C must include a clump of size 4 or more
        n² divides w³

        (This last condition is the same as suggested by Frits in his comment below).

        It calculates the probability for B, and then finds example decompositions for A and C that give the same probability.

        This Python program fully explores the solution space and runs in 92ms. (Internal runtime is 27ms).

        Run: [ @replit ]

        from enigma import (Rational, irange, divf, div, decompose, first, printf)
        
        Q = Rational()
        
        # with <n> sectors, <w> winning in clumps <ws>, find probability of seq <seq>
        def prob(n, w, ws, seq):
          P = 1
          # calculate probability of a good spin
          S = Q(w, n)
          # calculate probability of a good move
          (zs, d) = (ws, w)  # winning zones
          for v in seq:
            # calculate new zones
            zs = list(x - 1 for x in zs if x > 1)
            n = sum(zs)
            M = Q(n, d)
            # check the sequence
            if v == 'M' and M > S:
              P *= M
              d = n
            elif v == 'S' and S > M:
              P *= S
              (zs, d) = (ws, w)
            else:
              return
          return P
        
        # with <n> sectors, <w> winning, sequence <seq>
        # find winning clumps <ws> that give probability <p>
        # subject to max(<ws>) >= <m>
        def solve(n, w, seq, m, p):
          for k in irange(1, w):
            for ws in decompose(w, k, increasing=1, sep=0, min_v=1):
              if ws[-1] < m: continue
              if prob(n, w, ws, seq) == p:
                yield ws
        
        # consider possible n, w values such that n^2 divides w^3
        for n in irange(9, 99):
          for w in irange(4, divf(n - 1, 2)):
            k3 = div(w**3, n**2)
            if k3 is None: continue
        
            # calculate probability for B (SSS)
            # a split into <w> clumps of size 1 will do
            B = prob(n, w, [1] * w, "SSS")
        
            # find examples for C (MMMS) and A (MMSM):
            # for A we need at least one clump of size 3 or more
            As = first(solve(n, w, "MMSM", 3, B), 1)
            if not As: continue
        
            # for C we need at least one clump of size 4 or more
            Cs = first(solve(n, w, "MMMS", 4, B), 1)
            if not Cs: continue
        
            # output solution
            printf("n={n} w={w} -> P={B}, A={As} C={Cs}")
        

        Here is the analysis:

        C was able to make 3 consecutive Ms, so there must have been a block of at least 4 contiguous winning sectors in that game. Hence the wheel must have at least 9 sectors in total.

        Similarly in the game where A made 2 consecutive Ms, there must have been a block of at least 3 contiguous winning sectors.

        If the wheel has n sectors in all, and w winning sectors, then the probability of winning on a spin is:

        P(S) = w/n

        (which is less than 50% by definition).

        So for B we have:

        P(SSS) = w³/n³

        regardless of the configuration of the winning sectors.

        Except we also require there to be some configuration where:

        P(S) > P(M)

        But if every winning sector is in a clump of 1 (which is possible as there are fewer than half winning sectors) we have:

        P(M) = 0

        so the inequality above can be satisfied.

        Now if we consider a situation where k1 of the winning sectors are “good” (i.e. they are directly anti-clockwise from another winning sector), then we have:

        P(M) = k1/w

        For the next move suppose only k2 of the k1 sectors are “good”, we have:

        P(MM) = (k1/w)(k2/k1) = k2/w

        and so on:

        P(MMM) = (k1/w)(k2/k1)(k3/k2) = k3/w

        where: (w, k1, k2, k3) form a decreasing sequence.

        And so for C we have:

        P(MMMS) = (k3/w)(w/n) = k3/n

        And this must be the same as P(SSS) above:

        k3/n = w³/n³
        k3 = w³/n²

        So: n² must divide into w³ (as k3 is an integer).

        This narrows us down to just 4 possible (n, w) pairs:

        (27, 9)
        (54, 18)
        (64, 16)
        (81, 27)

        Which have give the following probabilities for B

        (27, 9) → 1/27
        (54, 18) → 1/27
        (64, 16) → 1/64
        (81, 27) → 1/27

        And for C gives k3 values of:

        (27, 9) → 1
        (54, 18) → 2
        (64, 16) → 1
        (81, 27) → 3

        For A we get:

        P(MMSM) = k1.k2 / n.w

        Giving the following k1.k2 values:

        (27, 9) → 9 (not possible)
        (54, 18) → 36 = 12×3 = 9×4
        (64, 16) → 16 = 8×2
        (81, 27) → 81 (not possible)

        So there are only 2 pairs to consider, and we need to find appropriate decompositions of the winning sectors for A and C that give the appropriate probability (same as B), and where the choice to play M or S is always that with the larger probability.

        Like

    • Frits's avatar

      Frits 2:01 pm on 29 July 2023 Permalink | Reply

      Extra analysis:

      for MMMS we have sum(x – 3 for x in ws if x > 3) * n^2 = w^3
      for MMSM we have sum(x – 1 for x in ws if x > 1) * sum(x – 2 for x in ws if x > 2) *n^2 = w^4

      This adaptation of Jim’s program checks the full solution space in 30ms.

       
      from enigma import (Rational, irange, decompose, intersect, divf, seq2str, printf)
       
      Q = Rational()
       
      # with <n> sectors, <w> winning in clumps <ws>, find probability of seq <seq>
      def prob(n, w, ws, seq):
        P = 1
        # calculate probability of a good spin
        S = Q(w, n)
        # calculate probability of a good move
        zs = ws  # winning zones
        for v in seq:
          z = sum(zs)
          zs = list(x - 1 for x in zs if x > 1)
          M = Q(sum(zs), z)
          
          # check the sequence
          if v == 'M' and M > S:
            P *= M
          elif v == 'S' and S > M:
            P *= S
            zs = ws
          else:
            return
          
        return P if P == S**3 else None
       
      # with <n> sectors, <w> winning, collect common probabilities for sequences <ss>
      def solve(n, w, ss):
        # collect probabilities
        d = dict((k, set()) for k in ss)
      
        w3byn2, w4byn2 = w**3 // n**2, w**4 // n**2
        
        # break the sectors into k contiguous blocks
        for k in irange(1, w):
          for ws in decompose(w, k, increasing=1, sep=0, min_v=1):
            # we have a solution if P = (w/n)^3 has been found for both MMSM and MMMS
            if d[ss[0]] and d[ss[2]]:
              return d[ss[0]]
            
            fn = lambda s, y: sum(x - y for x in s if x > y) 
            # check if P can be calculated as (w/n)^3
            if (fn(ws, 3) != w3byn2 or d[ss[2]]) and \
               (fn(ws, 1) * fn(ws, 2) != w4byn2 or d[ss[0]]): continue
            
            # calculate only the probabilities for MMSM and MMMS  
            # (as P for SSS equals (w/n)^3 if ws = [1, 1, ..., 1, 1])
            for s in [ss[0], ss[2]]:
              P = prob(n, w, ws, s)
              if P: d[s] = {P}
        # return common probabilities
        return intersect(d.values())
       
      # solve the puzzle
      def main():
        # consider number of sectors <n>
        for n in irange(9, 99):
          # consider number of winning sectors <w>
          for w in irange(4, divf(n - 1, 2)):
            # skip early if probability for MMSM and MMMS can't be (w/n)^3
            if w**4 % n**2 or w**3 % n**2: continue
            # find common probabilities
            ps = solve(n, w, ['MMSM', 'SSS', 'MMMS'])
            if ps:
              printf("n={n} w={w} -> P={ps}", ps=seq2str(ps))
              # continue to check the full solution space
       
      main()  
      

      Like

    • Frits's avatar

      Frits 9:04 pm on 30 July 2023 Permalink | Reply

      Trying to perform decomposition with SubstitutedExpression().
      In order to not use too many variables the maximum number of decomposition variables is calculated.
      The programs runs in 185ms.

       
      from enigma import SubstitutedExpression, divf, div
      
      # function used in probability formula for M
      fn = lambda s, y: sum(x - y for x in s if x > y) 
      
      symbols = "ABCDEFGHIJKLMNOPQRabcdefghijklmopqrtuvxyx"
      syms2 = ["ST", "UV", "WX", "YZ"]
      
      # consider possible n, w values such that n^2 divides w^3
      for n in range(9, 100):
        for w in range(4, divf(n - 1, 2) + 1):
          if w**3 % n**2: continue
          
          # try to decompose <w> into  A, B, .. , xx 
          # maximum number of elements to decompose <w>
          mx = (w + 1) - (w**2 // n + 2)
          # maximum number of 2-digit variables needed
          n2 = w // 10
          
          # invalid digit / symbol assignments
          d2i = {d: set() for d in range(10)}
          for i in range(n2 - 1):
            for d in range((w // (n2 - i)) // 10 + 1, 10):
              d2i[d].add(syms2[i][0])
          
          # build expressions
          exprs = []
          for i in range(mx - 1):
            j = mx - n2 - i
            cur = symbols[i] if j > 0 else syms2[-j]
            nxt = symbols[i + 1] if j > 1 else syms2[0] if j == 1 else syms2[(1 - j)]
            
            if i < mx - 2:
              exprs.append(f"{{{cur}}} <= {{{nxt}}}")
            else:
              exp = f"{{{cur}}} <= {{{nxt}}}"  # save for later
              
            # restrict values of single digit variables
            if len(cur) == 1:
              for d in range(w // (mx - i) + 1, 10):
                d2i[d].add(cur)
            else:
              # restrict values by adding an expression
              exprs.append(f"{{{cur}}} <= {w // (mx - i)} ")
      
          vars = [f"{{{s}}}" for s in symbols[:mx - n2]] 
          vars += [f"{{{s}}}" for s in syms2[:n2]]
          svars = ','.join(vars)
          
          # direct assignment of last variable
          exprs.append(f"{w} - sum([{','.join(vars[:-1])}]) = {vars[-1]}",)
          exprs.append(exp)
          
          exp = ""
          # for MMMS we have sum(x – 3 for x in ws if x > 3) * n^2 = w^3
          exp += f"(c1 := (fn(svars:= [{svars}], 3) * {n**2} == {w**3}) and "
          exp += f"{n} * fn([{svars}], 1) > {w**2} and "
          exp += f"{n} * fn([{svars}], 2) > {w} * fn([{svars}], 1) and "
          exp += f"{n} * fn([{svars}], 3) > {w} * fn([{svars}], 2) and "
          exp += f"{n} * fn([{svars}], 4) < {w} * fn([{svars}], 3)) or "
          
          # for MMSM we have sum(x – 1 for x in ws if x > 1) * 
          #                  sum(x - 2 for x in ws if x > 2) * n^2 = w^4
          exp += f"(c2 := (fn([{svars}], 1) * fn([{svars}], 2) * {n**2} == {w**4}) "
          exp += f"and {n} * fn([{svars}], 1) > {w**2} and "
          exp += f"{n} * fn([{svars}], 2) > {w} * fn([{svars}], 1) and "
          exp += f"{n} * fn([{svars}], 3) < {w} * fn([{svars}], 2))"
          exprs.append(exp)
          
          # the alphametic puzzle
          p = SubstitutedExpression(
            exprs,
            answer="c1, c2, vars",
            d2i=d2i,
            distinct="",
            env=dict(fn=fn),
            reorder=0,
            verbose=0,    # use 256 to see the generated code
          )
      
          # print answers
          cnts = [0, 0]
          for ans in p.answers():
            #print(f"{ans}")
            if ans[0]: cnts[0] = 1
            if ans[1]: cnts[1] = 1
          
            if cnts == [1, 1]:
              print(f"answer: n={n}, w={w}")
              break  
      

      Like

    • Tony Brooke-Taylor's avatar

      Tony Brooke-Taylor 7:11 pm on 3 August 2023 Permalink | Reply

      You can do a lot with Frits’ MMMS result and the limits for n and w, to constrain the search space. I used a slightly different paradigm from Jim’s, considering numbers of winning segments with clockwise winning neighbours, so my nomenclature is a bit different. Also I am coding in Rust now so won’t reproduce my solution here. However, I have written up a solution which can be applied manually in the comments of my code at:

      https://github.com/TuonyBT/teaser3175/blob/master/src/main.rs

      Like

    • Frits's avatar

      Frits 9:52 pm on 8 August 2023 Permalink | Reply

      There is a different answer (n=64, w=16) when a winning run is supposed to be followed by a loss.

      from enigma import (Rational, irange, decompose, intersect, divf, seq2str, printf)
      
      fn = lambda s, y: sum(x - y for x in s if x > y) 
       
      Q = Rational()
       
      # with <n> sectors, <w> winning in clumps <ws>, find probability of seq <seq>
      def prob(n, w, ws, seq, target):
        P = 1
        # calculate probability of a good spin
        S = Q(w, n)
        # calculate probability of a good move
        zs = ws  # winning zones
        for v in seq:
          z = sum(zs)
          zs = list(x - 1 for x in zs if x > 1)
          M = Q(sum(zs), z)
          
          # check the sequence
          if v == 'M' and M > S:
            P *= M
          elif v == 'S' and S > M:
            P *= S
            zs = ws
          else:
            return
        
        P *= (1 - fn(ws, 1) / w) if seq[-1] == 'S' else (1 - fn(ws, 2) / fn(ws, 1)) 
        return P if P == S**3 * (n - w) / n else None
        
      
      # with <n> sectors, <w> winning, collect common probabilities for sequences <ss>
      def solve(n, w, ss):
        # collect probabilities
        d = dict((k, set()) for k in ss)
      
        # probability for winning run SSS
        F =  (n - w) * w**4 / n**3
        
        # maximum number of elements to decompose <w>
        mx = (w + 1) - (w**2 // n + 2)
        # break the sectors into k contiguous blocks
        for k in irange(1, mx):
          for ws in decompose(w, k, increasing=1, sep=0, min_v=1):
            # we have a solution if P = (w/n)^3 has been found for both MMSM and MMMS
            if d[ss[0]] and d[ss[2]]:
              return d[ss[0]]
            
            # check if P can be calculated as F
            if (fn(ws, 3) * w - fn(ws, 1) * fn(ws, 3) != F or d[ss[2]]) and \
               (fn(ws, 1) * fn(ws, 2) - fn(ws, 2)**2 != F or d[ss[0]]): continue
       
            # calculate only the probabilities for MMSM and MMMS  
            # (as P for SSS equals F if ws = [1, 1, ..., 1, 1])
            for s, t in [(ss[0], (w/n)**3 ), (ss[2], (w/n)**3)]:
              P = prob(n, w, ws, s, t)
              if P: d[s] = {P}
        # return common probabilities
        return intersect(d.values())
      
      # fn(a, b) = sum(x – b for x in a if x > b)
      # for SSS we have probablility (w/n)**3 * (n - w) / n
      # for MMMS we have fn(ws, 3) * w - fn(ws, 1) * fn(ws, 3) = (n - w) * w**4 / n**3
      # for MMSM we have fn(ws, 1) * fn(ws, 2) - fn(ws, 2)**2  = (n - w) * w**4 / n**3
      
      # solve the puzzle
      def main():
        # consider number of sectors <n>
        for n in irange(9, 99):
          # consider number of winning sectors <w>
          for w in irange(4, divf(n - 1, 2)):
            # skip if probability for MMSM and MMMS can't be (w/n)^3 * (n - w) / n
            if (w**4 * n - w**5) % n**2: 
              continue
            
            # find common probabilities
            ps = solve(n, w, ['MMSM', 'SSS', 'MMMS'])
            if ps:
              printf("\nn={n} w={w} -> P={ps}\n", ps=seq2str(ps))
              # continue to check the full solution space
       
      main()   
      

      Like

      • Jim Randell's avatar

        Jim Randell 10:08 pm on 9 August 2023 Permalink | Reply

        I interpreted the probabilities as being those of achieving the sequences given, and not being concerned about what happened on the next play.

        But I augmented my program to include the probability of a loss on the next play of each run and I got 4 answers to the puzzle:

        n=27, w=9, P=2/81
        n=54, w=18, P=2/81
        n=64, w=16, P=3/256
        n=81, w=27, P=2/81

        For example, with the first of these we have 27 sectors and 9 of them are winning, so:

        The probability of a good spin is 9/27 = 1/3 (and the probability of a bad spin is 2/3).

        So for B the probability of (S=win, S=win, S=win, S=lose) is:

        P(SSS(S)) = (1/3)×(1/3)×(1/3)×(1 − 1/3) = 2/81

        For A the configuration could be (1, 2, 3, 3), giving the probability of (M=win, M=win, S=win, M=win, M=lose) as:

        P(MMSM(M)) = (5/9)×(2/5)×(1/3)×(5/9)×(1 − 2/5) = 2/81

        For C the configuration could be (1, 4, 4), giving the probability of (M=win, M=win, M=win, S=win, M=lose) as:

        P(MMMS(M)) = (6/9)×(4/6)×(2/4)×(1/3)×(1 − 6/9) = 2/81

        Like

        • Frits's avatar

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

          @Jim, you are right. Using rational numbers class Q in line 28/29 also yields 4 answers.

             
          P *= (1 - Q(fn(ws, 1), w)) if seq[-1] == 'S' else (1 - Q(fn(ws, 2), fn(ws, 1))) 
          return P if n * P == S**3 * (n - w) else None
          

          Like

  • Unknown's avatar

    Jim Randell 4:55 pm on 8 January 2023 Permalink | Reply
    Tags: by: John Owen,   

    Teaser 3146: Curling league [revised] 

    From The Sunday Times, 8th January 2023 [link] [link]

    The number of teams in our curling league is more than 4, but less than 26. In a tournament each team plays each of the other teams once, and the teams are ranked according to the number of wins they achieve (draws are impossible). If any teams are tied on wins, ranking is only possible if those teams have different numbers of wins in their mutual games. For example, in a three-way tie if A beats B, B beats C and A beats C, the ranking is ABC, but if C beats A (or A has not yet played C), then ranking is impossible, as A and B have one win each.

    At one point (when each team had played G games), ranking the teams as above was possible. However, if each team had played G−1 games, a ranking would not have been possible, irrespective of results. With one more team in the league, the minimum number of games needed to allow a ranking would be G+2.

    How many teams are in the league and what was the value of G?

    This is a revised version of the puzzle posted as Teaser 3146. The underlined text has been changed from the published version, to be in line with the intention of the setter.

    [teaser3146]

     
    • Jim Randell's avatar

      Jim Randell 9:41 am on 9 January 2023 Permalink | Reply

      I solved the previous version of this puzzle with a fairly straightforward search [link]. And it came up with a solution quickly, without having to explore the entire solution space. Which was handy because that would have taken a long time.

      So I looked at making my program more efficient. By looking at the number of wins achieved by each team we find there are only certain patterns of wins that are viable. Limiting the search to these patterns of wins, and doing more checks to reject candidate solutions early I was able to come up with a (more complicated) program that explores the entire solution space in a reasonable time, and constructively finds a single solution to the puzzle.

      (This program can also be used to find both solutions to the puzzle as originally worded).

      The following Python program runs in 7.6s.

      Run: [ @replit ]

      from enigma import (
        irange, group, item, div, subsets, multiset, rev,
        diff, filter2, seq_all_different, cache, printf
      )
      
      # labels for <n> teams; 1..n
      teams = lambda n: irange(1, n)
      
      # a match is represented by (<winning-team>, <losing-team>)
      
      # check a set of matches for <n> teams is orderable for teams <ts>
      def orderable(ms, ts):
        # extract the winners
        (ws, _) = zip(*ms)
        # and count the number of wins for each team
        w = dict((t, ws.count(t)) for t in ts)
        # group teams with the same number of wins together
        g = group(w.items(), by=item(1), f=item(0), fn=sorted)
        # look for tied groups
        for (_, xs) in g.items():
          if len(xs) < 2: continue
          # collect the mutual games amongst the group
          ws_ = list(x for (x, y) in ms if x in xs and y in xs)
          # and check they are all different
          if not seq_all_different(ws_.count(t) for t in xs): return False
        # looks good
        return True
      
      # allocate played matches for <n> teams, <k> matches per team, <p> matches in total,
      # from unallocated matches <ps>
      def allocate(n, k, p, ps, ws, t=1, ss=[]):
        # are we done?
        if t > n:
          yield ss
        else:
          # allocated games involving team <t>
          xs = list(x for x in ss if t in x)
          r = k - len(xs)
          if r < 0: return
          nw = ws[0]
          # number of allocated wins
          xw = sum(x == t for (x, y) in xs)
          if xw > nw: return
          # consider unallocated games involving team <t>
          (ts, ps_) = filter2((lambda x: t in x), ps)
          # select the remaining matches for team <t>
          for rs in subsets(ts, size=r):
            for js in subsets(irange(r), size=nw - xw, fn=set):
              # construct the new set of matches
              ss_ = ss + list(((t, x + y - t) if j in js else (x + y - t, t)) for (j, (x, y)) in enumerate(rs))
              # check wins/losses are still viable for the remaining teams
              xws = multiset.from_seq(x[0] for x in ss_)
              xls = multiset.from_seq(x[1] for x in ss_)
              if any(xws.count(j) > w or xls.count(j) > k - w for (j, w) in zip(irange(t, n), ws)): continue
              # and check it is orderable for teams up to t
              if orderable(ss_, teams(t)):
                yield from allocate(n, k, p - r, ps_, ws[1:], t + 1, ss_)
      
      # decompose total played matches <p> into wins for <n> teams, each played <k> matches
      def decompose(p, n, k, w=0, ws=[]):
        if len(ws) == n:
          if p == 0:
            yield rev(ws)
        elif not (w > k):
          # choose number of teams with <w> wins
          for m in irange(min(w, k - w) + 1, 0, step=-1):
            if len(ws) + m > n or m * w > p: continue
            yield from decompose(p - m * w, n, k, w + 1, ws + [w] * m)
      
      # find orderable sets of wins for <n> teams, each having played <k> matches
      def wins(n, k):
        # calculate the number of played matches
        p = div(n * k, 2)
        if p is None: return
        # construct the possible matches
        ps = list(subsets(teams(n), size=2))
        # construct possible wins
        for ws in decompose(p, n, k):
          # we can allocate matches between teams with the same number of wins
          g = group(enumerate(ws, start=1), by=item(1), f=item(0), fn=sorted)
          ss = list()
          for (_, vs) in g.items():
            if len(vs) > 1:
              ss.extend(subsets(vs, size=2))
          if len(ss) > p: continue
          # allocate the remaining matches
          yield from allocate(n, k, p - len(ss), diff(ps, ss), ws, 1, ss)
      
      # check if <n> teams, each played <k> games is orderable
      @cache
      def check(n, k):
        if not (n > k > 0): return None
        for r in wins(n, k):
          printf("[n={n} k={k} -> {r}]", r=sorted(r))
          return True
        printf("[n={n} k={k} -> None]")
        return False
      
      # solve the puzzle
      def solve(start, stop):
        # n = number of teams in the league
        for n in irange(start + 1, stop + 1):
          # k = number of matches played by each team
          # look for minimum k that is orderable
          for k in irange(1, n - 1):
            # can we find an orderable set of wins?
            r = check(n, k)
            # find the smallest k that gives an orderable set
            if r:
              printf("-> n={n}: min_k = {k}")
              (T, G) = (n - 1, k - 2)
              # look to see if (T, G) is possible and (T, G - 1) is not possible
              if check(T, G) is True and check(T, G - 1) is False:
                # output solution
                printf("=> T = {T}; G = {G}")
                printf("##### SOLUTION FOUND -> league has {T} teams; games played = {G} #####")
                yield (T, G)
              break
          printf()
      
      # output solution summary
      for (T, G) in list(solve(5, 25)):
        printf("=> SOLUTION: league has {T} teams; games played = {G}")
      

      Solution: There are 16 teams in the league. G = 6.

      For example, with teams A – P, each can play 6 games, and be orderable as follows:

      1st = A [6 wins; beat: B D E G H I]
      2nd = B [5 wins; beat: C D G H K]
      3rd = C [5 wins; beat: G K L M N]
      4th = D [4 wins; beat: E F K L]
      5th = E [4 wins; beat: F K L N]
      6th = F [4 wins; beat: M N O P]
      7th = G [3 wins; beat: H I J]
      8th = H [3 wins; beat: I J N]
      9th = I [3 wins; beat: J O P]
      10th = J [3 wins; beat: N O P]
      11th = K [2 wins; beat: L M]
      12th = L [2 wins; beat: M P]
      13th = M [2 wins; beat: O P]
      14th = N [1 win; beat: O]
      15th = O [1 win; beat: P]
      16th = P [0 wins]

      And it is not possible for 16 teams to have each played 5 games and be orderable.

      >>> from enigma import first
      >>> first(wins(16, 5))
      []
      

      But it is possible for 17 teams, A – Q, to have each played 8 games and be orderable:

      1st = A [8 wins; beat: B D E G H I J K]
      2nd = B [7 wins; beat: C D G H I J K]
      3rd = C [7 wins; beat: G I J K L M N]
      4th = D [6 wins; beat: E F I J K L]
      5th = E [6 wins; beat: F J L M N O]
      6th = F [6 wins; beat: L M N O P Q]
      7th = G [5 wins; beat: H L M O P]
      8th = H [5 wins; beat: L M O P Q]
      9th = I [4 wins; beat: N O P Q]
      10th = J [3 wins; beat: K O Q]
      11th = K [3 wins; beat: O P Q]
      12th = L [2 wins; beat: M N]
      13th = M [2 wins; beat: N Q]
      14th = N [2 wins; beat: P Q]
      15th = O [1 win; beat: P]
      16th = P [1 win; beat: Q]
      17th = Q [0 wins]

      but not for any number of games less than 8.


      Here are some notes on the refinements I used to eliminate cases from testing compared with my original program, that allows it to run in a reasonable time over the entire solution space…

      Firstly we don’t care what order the teams are in, so we can assume team 1 is 1st in the order, team 2 is 2nd, and so on.

      For a league with n teams, each having played k matches there are p = (n × k /2) matches played in total (each match involves 2 teams), so we can allocate these p wins among the n teams in a non-decreasing sequence of [0..k] wins. With team 1 having the largest number of wins, down to team n having the least wins.

      Then looking at groups of teams with the same number of wins, these groups must be ordered according to the matches played amongst the teams involved. If team X has 0 wins there cannot be another team Y with 0 wins, as we can only order them with an X vs. Y match, which neither team can be allowed to win. So there can be at most 1 team with 0 wins, at most 2 teams with 1 wins, etc.

      And by considering losses we get the same pattern coming down. There can be at most 1 team with k wins, at most 2 teams with (k – 1) wins, and so on.

      So, I generated viable patterns of wins and then allocated matches according to these patterns by working through the list of wins and allocating appropriate matches for each team.

      When allocating the remaining matches for each team I check after each allocation that we haven’t allocated too many wins (or losses) to one of the later occurring teams, and also after we have allocated the matches for a team the matches for that team and all earlier teams are fixed, so the set of matches restricted to just these teams must already be orderable (as they are not going to change later).

      Also, it soon became obvious that using [[ enigma.decompose() ]] to generate all possible decompositions and discarding those that were unsuitable was not very efficient as n increased, so I wrote a specific [[ decompose() ]] routine to do this for me.

      Then I realised that if we have groups of teams with the same number of wins, and we know the order that we want them to appear in, then we can allocate the wins involved between those teams immediately, before we start the general allocation of the remaining matches.

      Together all these improvements let the program run in 10s or less (running under PyPy 7.3.11). This was hugely faster than my initial program for the original puzzle, and let the program examine the entire solution space, and construct orderings where they were possible.

      Like

      • Frits's avatar

        Frits 4:41 pm on 9 January 2023 Permalink | Reply

        Using a different solve() is a bit faster. Basically we start with making a list of orderable set of wins (first item only) by calling decompose().

        Only changes made to the code is to return a tuple in decompose() and to suppress printing in the check routine.

        The “not found” branche is not further developed as it seems that all decompose() output is orderable.

           
        def solve(start, stop):
          F = dict()
          # n = number of teams in the league
          for n in range(start, stop):
            # k = number of matches played by each team
            for k in range(1, n):  
              if n % 2 and k % 2: continue
              # get first orderable set of wins
              lst = list(first(decompose(n * k // 2, n, k)))
              if lst: 
                print((n, k), "-->", lst[0])
                if not check(n, k, p=0):
                  print("not found")
                else:
                  F[n] = k
                break
        
          # check dictionary of first orderable set of wins
          for n, k in F.items():
            if n - 1 in F:
              if F[n - 1] == k - 2:
                printf("=> SOLUTION: league has {n - 1} teams; games played = {k - 2}")
              elif k > 3 and F[n - 1] < k - 2:
                if check(n - 1, k - 2, p=0) and not check(n - 1, k - 3, p=0):
                  printf("=> SOLUTION: league has {n - 1} teams; games played = {k - 2}")
        

        Like

        • Jim Randell's avatar

          Jim Randell 9:46 pm on 9 January 2023 Permalink | Reply

          @Frits: I think most of the speed increase you are seeing comes from not checking the full range for n. If the number of teams can be up to 25 then we need to check up to n = 26. Otherwise it seems to be doing pretty much the same thing as my program, but finding solutions at the end rather than as it goes along.

          The values generated by [[ decompose() ]] all give an orderable set of matches when the program is run normally, but this is not the case in general. While playing around I found [[ check(10, 8) ]] (for example) needed to look at multiple decompositions before an orderable set was found.

          Like

          • Frits's avatar

            Frits 11:21 pm on 9 January 2023 Permalink | Reply

            @Jim, you are right, with range(start, stop + 2) the performance gain is minimal.

            A bit surprising, your program calls check() 135 times and mine only 23 times (but these are all time consuming).

            Like

          • Jim Randell's avatar

            Jim Randell 11:28 pm on 9 January 2023 Permalink | Reply

            The [[ check() ]] function is cached (via the [[ @cache ]] decorator), so we get access to previously computed values without recalculating them.

            Like

            • Frits's avatar

              Frits 11:34 pm on 9 January 2023 Permalink | Reply

              Removing @cache most of the time slightly improves the run time!

              Like

    • Jim Randell's avatar

      Jim Randell 9:36 am on 27 January 2023 Permalink | Reply

      Here is a non-constructive solution, that uses the pattern of wins given in my notes above.

      Thinking about leagues of n teams where each team has played k matches, then if we start with a value for k we see the smallest possible value that n can be is (k + 1).

      And when we think about allocating the p = (n.k / 2) matches among the n teams, then there can only be 1 team with 0 wins or k wins, 2 teams with 1 win or (k − 1) wins, etc.

      So, if k is even (say 2x) we get a pattern of the form:

      1, 2, …, (x + 1), …, 2, 1
      max(n) = 2T(x) + (x + 1) = (x + 1)²

      And if k is odd (say 2x + 1) we get a pattern of the form:

      1, 2, …, (x + 1), (x + 1), …, 2, 1
      max(n) = 2T(x + 1) = (x + 1)(x + 2)

      So by considering increasing values of k we can find a range of potentially viable n values and build up a set of viable (n, k) values. Note that no (n, k) value where both n and k are odd is viable, as a corresponding p value cannot be calculated, but we assume that all remaining (n, k) value will allow a viable ordering to be constructed. (In my program above this assumption is not made, and we don’t accept an (n, k) until an orderable scenario has been constructed. Removing this requirement significantly reduces the amount of work required to find a solution, and is the approach used in the setters’ own solution).

      Once an appropriate set of (n, k) values has been constructed we can look for scenarios that provide a solution to the puzzle.

      We are looking for a number of teams T and number of games G such that:

      (T, G) is viable
      (T, G − 1) is not viable
      (T + 1, G + 2) is viable
      (G + 2) is the smallest viable number of games for a league with (T + 1) teams

      The Python program performs this search. It runs in 57ms. (Internal runtime is 534µs).

      Run: [ @replit ]

      from enigma import (irange, divc, tri, div, peek, printf)
      
      # for a given k value generate possible range of n values
      def nrange(k):
        lo = k + 1
        # count maximum possible wins = number of matches
        h = divc(k, 2)
        t = k * tri(h)
        if k % 2 == 0: t += h * (h + 1)
        hi = div(2 * t, k)
        return (lo, hi)
      
      def solve(start, stop):
        ss = list()
        # possible number of teams
        t = 1
        # record possible (n, k) values
        R = set()
        # consider increasing k values
        for k in irange(1, stop + 1):
          (lo, hi) = nrange(k)
          # fill out possible (n, k) values in R
          for n in irange(lo, hi):
            if k % 2 == 0 or n % 2 == 0:
              R.add((n, k))
          # check possible teams
          while t + 1 < lo:
            t += 1
            # find min_k for t
            min_k = peek(k for k in irange(1, t - 1) if (t, k) in R)
            printf("t={t} -> min_k={min_k}")
            # look for solutions
            (T, G) = (t - 1, min_k - 2)
            if T < start or T > stop: continue
            if (T, G) in R and (T, G - 1) not in R:
              printf("=> T = {T}; G = {G}")
              printf("##### SOLUTION FOUND -> league has {T} teams; games played = {G}")
              ss.append((T, G))
        # output solution summary
        if ss:
          printf()
          for (T, G) in ss:
            printf("=> SOLUTION: league has {T} teams; games played = {G}")
      
      # solve the puzzle
      solve(5, 25)
      

      Like

  • Unknown's avatar

    Jim Randell 4:29 pm on 6 January 2023 Permalink | Reply
    Tags: by: John Owen,   

    Teaser 3146: Curling league 

    From The Sunday Times, 8th January 2023 [link] [link]

    In our curling league (between 4 and 26 teams), each team plays each other once. Teams are ranked according to the number of wins (draws are impossible). If any teams are tied on wins, ranking is only possible if those teams have different numbers of wins in their mutual games. For example, in a three-way tie if A beats B, B beats C and A beats C, the ranking is ABC, but if C beats A (or A has not yet played C), then ranking is impossible, as A and B have one win each.

    At one point (each team had played G games), ranking the teams as above was possible. However, if each team had played G-1 games, a ranking would have been impossible, irrespective of results. With one more team in the league, the minimum number of games needed to allow a ranking is G+2.

    How many teams are in the league and what was the value of G?

    Note: The setter of the puzzle is expecting a solution where the league has at least 5 and no more than 25 teams. (Which I would have phrased as “between 5 and 25 teams”).

    See Teaser 3146: Curling league [revised] for a revised version of this puzzle.

    [teaser3146]

     
    • Jim Randell's avatar

      Jim Randell 5:42 pm on 6 January 2023 Permalink | Reply

      I wrote a quick program to start attacking this puzzle starting with the smallest number of teams and working upwards, although I didn’t expect my program to run in a reasonable time as the number of teams grew.

      However I found that a situation that satisfies the conditions described in the puzzle presented itself very quickly, which makes me wonder if I have missed something.

      The following Python program runs in 57ms (it stops when the first solution is found). (Internal run time is 4.3ms).

      Run: [ @replit ]

      from enigma import (
        irange, group, item, div, subsets, multiset,
        cproduct, seq_all_different, cache, printf
      )
      
      # labels for <n> teams; 1..n
      teams = lambda n: irange(1, n)
      
      # a match is represented by (<winning-team>, <losing-team>)
      
      # check a set of matches for <n> teams is orderable
      def orderable(n, ms):
        # extract the winners
        (ws, _) = zip(*ms)
        # and count the number of wins for each team
        w = dict((t, ws.count(t)) for t in teams(n))
        # group teams with the same number of wins together
        g = group(w.items(), by=item(1), f=item(0), fn=sorted)
        # look for tied groups
        for (_, ts) in g.items():
          if len(ts) < 2: continue
          # collect the mutual games amongst the group
          ws_ = list(x for (x, y) in ms if x in ts and y in ts)
          # and check they are all different
          if not seq_all_different(ws_.count(t) for t in ts): return False
        # looks good
        return True
      
      # choose <p>-subsets of potential matches <ps>, with <k> matches played per team
      def choose(n, ps, p, k):
        for ss in subsets(ps, size=p):
          m = multiset.from_seq(*ss)
          if all(m.count(t) == k for t in teams(n)):
            yield ss
      
      # find orderable sets of wins for <n> teams, each having played <k> matches
      def wins(n, k):
        # calculate the number of played matches
        p = div(n * k, 2)
        if p is None: return
        # construct the possible matches
        ps = list(subsets(teams(n), size=2))
        # choose a p-subset with k matches played per team
        for ss in choose(n, ps, p, k):
          # now choose the winning team in each match
          for ms in cproduct([(x, y), (y, x)] for (x, y) in ss):
            # is this set of matches orderable?
            if orderable(n, ms):
              yield ms
      
      # check if <n> teams, each played <k> games is orderable
      @cache
      def check(n, k):
        if not (n > k > 0): return None
        for r in wins(n, k):
          printf("[n={n} k={k} -> {r}]")
          return True
        printf("[n={n} k={k} -> None]")
        return False
      
      # solve the puzzle
      def solve():
        # n = number of teams in the league
        for n in irange(5, 27):
          # k = number of matches played by each team
          # look for minimum k that is orderable
          for k in irange(1, n - 1):
            # can we find an orderable set of wins?
            r = check(n, k)
            # find the smallest k that gives an orderable set
            if r:
              printf("-> n={n}: min_k = {k}")
              (T, G) = (n - 1, k - 2)
              # look to see if (T, G) is possible and (T, G - 1) is not possible
              if check(T, G) is True and check(T, G - 1) is False:
                # output solution
                printf("=> T = {T}; G = {G}")
                printf("##### SOLUTION FOUND -> league has {T} teams; games played = {G} #####")
                # we are done
                return
              break
          printf()
      
      solve()
      

      There are two solution to this puzzle:

      Solution: There are either 4 teams in the league, and G = 2. Or there are 16 teams in the league and G = 6.

      My program quickly finds the first of these solutions, but would take a long time to find the second one (and to exhaustively check the entire solution space).

      But the program I wrote for the revised puzzle [link] does find both solutions in a reasonable time.


      Here is a description of the solution with 4 teams:

      It is possible for each of the 4 teams (A, B, C, D) to have played 2 games. For example:

      A beat B
      A beat C
      B beat D
      D beat C

      And we see the teams are ranked:

      1st: A (2 wins)
      2nd: B (1 win, but B beat D)
      3rd: D (1 win, but D lost to B)
      4th: C (0 wins)

      It is not possible to rank the teams if they have only played one game. As there will only have been 2 games played, involving all 4 teams. 2 of the teams will have 1 win (and cannot be ranked, as they have not played each other), and the other will have 0 wins (likewise).

      If there were 5 teams in the league (A, B, C, D, E) then it is not possible for each of the teams to have played an odd number of games (as each game requires 2 teams), but it is possible for each team to play 4 games, for example:

      A beat B
      A beat C
      A beat D
      A beat E
      B beat C
      B beat D
      B beat E
      C beat D
      C beat E
      D beat E

      The teams are ranked:

      1st: A (4 wins)
      2nd: B (3 wins)
      3rd: C (2 wins)
      4th: D (1 win)
      5th: E (0 wins)

      All that remains is to show that it is not possible to find a set of matches with 2 wins per team, and the program can do this for us:

      >>> from enigma import first
      >>> first(wins(5, 2))
      []
      

      Like

      • Frits's avatar

        Frits 12:35 pm on 7 January 2023 Permalink | Reply

        @Jim, nice solution. It is not easy to solve this week.

        How can you be sure this is the only solution? So you might give an incorrect answer (for “our curling league”).

        One thing I can deduce is that if k = n-1 then we can always find an orderable set of wins.

        Like

        • Jim Randell's avatar

          Jim Randell 12:44 pm on 7 January 2023 Permalink | Reply

          My program gets bogged down as n increases, so it just stops at the first viable solution, and I haven’t been able to check all values up to n = 26.

          There may be an analytical way to show that there is only a single solution. Although if there are multiple solutions we won’t be able to tell which of them the setter had in mind.

          Like

        • Jim Randell's avatar

          Jim Randell 11:32 am on 9 January 2023 Permalink | Reply

          I’ve put a more efficient (but more complex) version of my program up on the page for the revised version of this puzzle [link].

          And we see that the original formulation of the puzzle has 2 solutions.

          Like

      • Jim Randell's avatar

        Jim Randell 10:26 am on 8 January 2023 Permalink | Reply

        Apparently the setter of this puzzle is expecting a solution for this puzzle with the number of teams in the league in the interval [5..25]. If this is the case, I think the wording should have been chosen more carefully.

        Like

    • Brian Gladman's avatar

      Brian Gladman 2:48 pm on 7 January 2023 Permalink | Reply

      Congratulations on getting a solution for this one Jim. At the moment I don’t have one 😦

      Like

    • Brian Gladman's avatar

      Brian Gladman 10:50 am on 8 January 2023 Permalink | Reply

      John Owen has just clarified on the Sunday Times discussion group site that “between 4 and 26” means “5 or more and at most 25”.

      Like

      • Jim Randell's avatar

        Jim Randell 2:49 pm on 8 January 2023 Permalink | Reply

        @Brian: This change certainly makes things trickier, as my program gets bogged down before it can check leagues with 10 or more teams.

        Although I would have expected this condition to be expressed as “between 5 and 25 teams”.

        Like

      • Frits's avatar

        Frits 4:14 pm on 8 January 2023 Permalink | Reply

        Nice to encounter a teaser which doesn’t seem to get solved (within a reasonable time) by brute force. My adapted version (with recursion) of Jim’s program is getting too slow at n=10.

        It isn’t easy to find a way to simplify the problem so it can be solved.

        Like

  • Unknown's avatar

    Jim Randell 4:00 pm on 7 October 2022 Permalink | Reply
    Tags: by: John Owen   

    Teaser 3133: Primary road network 

    From The Sunday Times, 9th October 2022 [link] [link]

    I was recently studying a large map that showed all the towns and major roads in a country. Every town had at least one road leading to it and every road led from one town to another. The roads only met at towns and all joined together to make a network with lots of blank areas in between, which I happily coloured in, needing just four different colours.

    I counted up the number of areas (excluding the area around the outside of the network) and the number of towns, and discovered that both numbers were prime. Also, when I took these two numbers with the number of roads, the three numbers together used every digit from 0 to 9 precisely once.

    In increasing order, what were the three numbers?

    [teaser3133]

     
    • Jim Randell's avatar

      Jim Randell 4:31 pm on 7 October 2022 Permalink | Reply

      This is an exercise in the properties of planar graphs [@wikipedia].

      We can use Euler’s formula:

      V – E + F = 2

      where:

      V = the number of vertices in graph (= the number of towns on the map)
      E = the number of edges in the graph (= the number of roads on the map)
      F = the number of enclosed regions in the graph (including the region around the graph)
      F = (the number of enclosed/coloured regions on the map) + 1

      This Python program runs in 93ms. (Internal run time is 38.6ms).

      Run: [ @replit ]

      from enigma import (primes, distinct_chars, ordered, printf)
      
      # consider V = the number of towns, it is prime
      for V in primes.between(3, 1000):
        if distinct_chars(V) is None: continue
      
        # consider A = the number of enclosed areas, it is also prime
        for A in primes.between(5, 2 * V - 5):
          if distinct_chars(V, A) is None: continue
      
          # calculate E = the number of roads
          E = V + A - 1
          if E > 3 * V - 6: continue
          if distinct_chars(V, A, E) != 10: continue
      
          # output solution
          ns = ordered(V, A, E)
          printf("{ns} [V={V} A={A} E={E}]")
      

      Solution: The three numbers are: 607, 829, 1435.


      We can construct a viable map as follows:

      Consider the following diagram:

      If the central area is an odd n-gon, coloured with the first colour, then it is surrounded by n regions, and as n is odd we require an additional 3 colours to colour these. So at least 4 colours are required, and the 4-colour theorem tells that we don’t need more than 4 colours.

      And together the central and surrounding areas contribute:

      2n vertices
      3n edges
      (n + 1) areas

      And adding p petals (we may add multiple layers of elongated petals if necessary), adds:

      0 vertices
      p edges
      p areas

      And a stalk of length s adds:

      s vertices
      s edges
      0 areas

      So using: n = 413, p = 193, s = 3, gives a graph with:

      826 + 0 + 3 = 829 vertices
      1239 + 193 + 3 = 1435 edges
      414 + 193 + 0 = 607 areas

      Which provides a viable map.

      Like

      • Jim Randell's avatar

        Jim Randell 8:33 am on 8 October 2022 Permalink | Reply

        Using the formula:

        E = p + q − 1

        where p and q are primes, and (E, p, q) is pandigital, we see that E must be 4-digits, so p and q can only be (2, 4) or (3, 3) digits.

        And without further planarity checks there is only one candidate solution, which we can find using the [[ SubstitutedExpression() ]] solver from the enigma.py library.

        The following Python program runs in 83ms. (Internal runtime is 28.4ms)

        Run: [ @replit ]

        from enigma import (SubstitutedExpression, sprintf as f, printf)
        
        # symbols for the digits
        (terms, result) = ("ABCDEF", "GHIJ")
        # consider (2,4) and (3, 3) digit terms
        for i in (2, 3):
          (x, y) = (terms[:i], terms[i:])
          exprs = [ f("is_prime({x})"), f("is_prime({y})"), f("{x} + {y} - 1 = {result}") ]
          if len(x) == len(y): exprs.append(f("{x} < {y}", x=x[0], y=y[0]))
          p = SubstitutedExpression(exprs, answer=f("({x}, {y}, {result})"))
          for ans in p.answers(verbose=0):
            printf("{ans}")
        

        Like

    • Frits's avatar

      Frits 12:31 am on 8 October 2022 Permalink | Reply

      This program considers up to 9999 number of towns.
      I stopped programming when the run time got under 10ms.

      NB The final P4 list is always logically empty, I didn’t remove the code to process 4-digit number of towns .

        
      from itertools import combinations
      
      # formula E = V + A - 1
      
      # V = the number of towns
      # A = the number of enclosed areas
      # E = the number of roads
      sols = set()
      
      P = [3, 5, 7]
      P += [x for x in range(11, 33, 2) if all(x % p for p in P)]
      P += [x for x in range(33, 1000, 2) if all(x % p for p in P)]
      
      # if V has 3 digits then E must be 1xxx
      # E must have at least 4 digits so V + 2V - 5 - 1 > 999 --> 3V > 1005
      # 3-digit primes
      P3 = [p for p in P if p > 335 and 
                           len(s := str(p)) == len(set(s)) and
                          '1' not in s]
      
      # first process 3-digit number of towns
      for V, A in combinations(P3, 2):
        if V + A < 1024: continue
        E = V + A - 1
        if len(set(str(1000000 * E + 1000 * A + V))) != 10: continue
        sols.add(tuple(sorted([V, A, E])))
        
      P = [3, 5, 7]
      P += [x for x in range(11, 100, 2) if all(x % p for p in P)]
      
      # if V has 4 digits then the 2nd digit of V, E must be resp 9, 0
      # if A ends in 1 then V and E will end in the same digit
      
      # 2-digit primes
      P2 = [p for p in P if p > 9 and 
                            all(y not in (s := str(p)) for y in "019") and
                            len(s) == len(set(s))]
                            
      # 4-digit primes
      P4 = [x for x in range(1001, 10000, 2) if all(x % p for p in P)]
      
      # if V has 4 digits the 2nd digit must be a nine (and may not use a zero)
      # otherwise E will use some of the same digits
      # if V ends in 1 then A and E will end in the same digit
      P4 = [p for p in P4 if (s := str(p))[1] == '9' and 
                             '0' not in s and
                             len(s) == len(set(s)) and
                             s[-1] != '1']
                             
      # numbers in P2 and P4 always end in 3 or 7  (1, 5, and 9 are not allowed)
      # so E must end in 9
      P2 = [p for p in P2 if '9' not in (s := str(p)) and p not in {37, 73}]
      P4 = [p for p in P4 if '9' not in (s := str(p)) and
                              all(y not in s[:-1] for y in "37")]
        
      # process 4-digit number of towns  
      for V in P4:
        # if V has 4 digits (x9yz) then A must be at least 101 - yz
        for A in [p for p in P2 if p >= 101 - V % 100]:
          E = V + A - 1
          if len(set(str(1000000 * E + 1000 * A + V))) != 10: continue
          sols.add(tuple(sorted([V, A, E])))
          
      # print solutions
      for s in sols:    
        print(s)
      

      Like

    • Hugh Casement's avatar

      Hugh Casement 6:32 am on 9 October 2022 Permalink | Reply

      I too had the idea of using Euler’s formula. At first I thought that a town with only a single road leading to it would spoil things, but then realized that they cancel out.

      Most unlikely that there would be a four-digit number of towns and only a two-digit number of regions between the roads, or vice versa. In any case, three plus three quickly yields a solution.
      I’ll spare you my program code, but Basic’s ability to handle strings was useful in determining whether all ten digits are present.

      Like

    • GeoffR's avatar

      GeoffR 11:44 am on 9 October 2022 Permalink | Reply

      I based my program on (3/3) and (2/4) digit splits for towns/areas, with 4 digits for roads.

      from enigma import nsplit, is_prime
       
      # form lists of 2, 3 and 4 digit primes
      # with non-repeating digits to check digit splits
      pr2 = [n for n in range(11, 99) if is_prime(n) \
             and len(set(str(n))) == 2]
      pr3 = [n for n in range(100, 999) if is_prime(n) \
             and len(set(str(n))) == 3]
      pr4 = [n for n in range(1000, 9999) if is_prime(n) \
             and len(set(str(n))) == 4 ]
       
      # check if (town/area) digits split is (3, 3)
      for town in pr3:
        A, B, C = nsplit(town)
        for area in pr3:
          if area == town:continue
          D, E, F = nsplit(area)
          if len(set((A, B, C, D, E, F))) != 6:continue
          roads = town + area - 1
          if roads in pr4: continue
          if roads < 1000 or roads > 9999:continue
          R1, R2, R3, R4 = nsplit(roads)
          if len(set((A,B,C,D,E,F,R1,R2,R3,R4))) == 10:
            if town < area:
              print(f"1.The three numbers were {town}, {area} and {roads}.")
       
      # check if (town/area) digits split is (2,4)
      for town2 in pr2:
        a, b = nsplit(town2)
        for area2 in pr4:
          c, d, e, f = nsplit(area2)
          if len(set((a, b, c, d, e, f))) == 6:
            roads2 = town2 + area2 - 1
            if roads2 < 1000 or roads2 > 9999: continue
            R5, R6, R7, R8 = nsplit(roads2)
            if len(set((a,b,c,d,e,f,R5,R6,R7,R8))) == 10:
              print(f"2.The three numbers were {town2}, {area2} and {roads2}.")
      

      Like

  • Unknown's avatar

    Jim Randell 9:14 am on 5 June 2022 Permalink | Reply
    Tags: by: John Owen   

    Teaser 2868: Prime logic 

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

    Three expert logicians played a game with a set of twenty-one cards each containing a different two-figure prime number. Each drew a card and held it up so that they could not see their own card but could see the others. Alf, Bert and Charlie in turn were then asked two questions, namely “Is your number the smallest of the three?” and “Is your number the largest of the three?”. In the first round all three answered “Don’t know” to both questions. The same happened in rounds two and three. In round four Alf answered “Don’t know” to the first question.

    What did Alf answer to the second question and what numbers did Bert and Charlie have?


    News

    When I started the S2T2 site (in February 2019), I already had notes for a number of Teaser puzzles that I had solved at the time of publication. And since then I have been steadily posting my notes for these puzzles to the site. This puzzle completes the accumulation of these notes, so there is now a complete archive of puzzles I solved at the time of publication from July 2015 to present.

    I shall continue to post puzzles from 2011 – 2015 corresponding to the collections of Teasers published as books in 2019 and 2020 (see: [Books]), but these puzzles will be new to me.

    Also, the posting of this puzzle also means that all puzzles from Teaser 2831 onwards are available on S2T2. Earlier Teaser puzzles are available via The Sunday Times Digital Archive (which is my source for older puzzles on the site).

    [teaser2868]

     
    • Jim Randell's avatar

      Jim Randell 9:15 am on 5 June 2022 Permalink | Reply

      Although it is not explicitly made clear I have assumed that at the beginning for the game each player draws a card, and then the three cards remain the same while the rounds of questions proceed.

      The puzzle would work just as well with cards numbered 1 – 21 (although the numbers on the final cards would be different).

      This program starts out with all possible ways for the 3 cards to be chosen. There are P(20, 3) = 7980 possibilities.

      We then consider the first three rounds where A, B, C answer “Don’t know” to both questions, eliminating possibilities where they would be able to give a different answer. And in the fourth round A answers “Don’t know” to the first question. The remaining possibilities then give the answer to the puzzle.

      It runs in 123ms. (Internal runtime is 62.9ms).

      Run: [ @replit ]

      from enigma import (primes, seq_all_same_r, group, ordered, delete, subsets, printf)
      
      # indices for A, B, C
      (A, B, C) = (0, 1, 2)
      
      # consider the 21 cards
      cards = list(primes.between(10, 99))  # 2-digit primes
      #cards = list(irange(1, 21))  # 1 - 21 work just as well
      assert len(cards) == 21
      
      smallest = lambda x, y: x < y
      largest = lambda x, y: x > y
      
      # answer question <fn> with knowledge <ks> and other cards <others>
      # return "Yes", "No", "???" (= "Don't know")
      def check(ks, others, fn):
        r = seq_all_same_r(all(fn(x, y) for y in others) for x in ks)
        # there should be at least one choice
        assert not r.empty
        if r.same:
          # if all choices had the same value the answer is "Yes" or "No"
          return ('Yes' if r.value else 'No')
        else:
          # mismatch, answer is "Don't know"
          return '???'
      
      # return new set of possibilities where the answer to questions <qs> is as specified
      def question(label, ps, i, *qs):
        # map: <others> -> <possibilities>
        d = group(ps, by=(lambda p: ordered(*delete(p, [i]))), fn=set)
        # consider possibilities based on the other cards I can see
        ps1 = set()
        for (others, ps) in d.items():
          # person <i> must be holding one of these cards
          ks = set(p[i] for p in ps)
          # must give correct answer to all questions
          if any(check(ks, others, fn) != r for (fn, r) in qs): continue
          # collect the viable possibilities
          ps1.update(ps)
        if label: printf("[{label}] {n} possibilities", n=len(ps1))
        return ps1
      
      # initial possible assignments of cards
      ps = set(subsets(cards, size=3, select="P"))
      printf("[---] {n} possibilities", n=len(ps))
      
      # the first three rounds, answers are all "Don't know"
      for rnd in "123":
        ps = question(rnd + ".A", ps, A, (smallest, '???'), (largest, '???'))
        ps = question(rnd + ".B", ps, B, (smallest, '???'), (largest, '???'))
        ps = question(rnd + ".C", ps, C, (smallest, '???'), (largest, '???'))
      
      # [4.A.1] answer is "Don't know"
      ps = question("4.A.1", ps, A, (smallest, '???'))
      
      # output remaining possibilities
      for r in ("Yes", "No", "???"):
        for (a, b, c) in question(None, ps, A, (largest, r)):
          printf("-> A={a} B={b} C={c}, answer to 4.A.2 is \"{r}\"")
      

      Solution: Alf’s answer to the second question in round four is “No”. Bert and Charlie had cards with numbers 47 and 59 (respectively).


      After the first 3 rounds and A’s answer to the first question of the fourth round there are only 2 possibilities remaining:

      A=43 B=47 C=59
      A=53 B=47 C=59

      Like

    • Frits's avatar

      Frits 11:11 am on 6 June 2022 Permalink | Reply

      Easier to read and with better performance:

      [https://brg.me.uk/?page_id=4512]

      Like

      • Jim Randell's avatar

        Jim Randell 11:32 pm on 6 June 2022 Permalink | Reply

        @Frits: I took a generic approach to the puzzle. The program runs pretty much instantaneously, so I didn’t feel the need for additional analysis to simplify the programming or make it run faster.

        Like

    • Frits's avatar

      Frits 11:29 am on 7 June 2022 Permalink | Reply

      Based on Brian’s program and avoiding the use of defaultdict.

         
      from itertools import product
      
      # all two digit primes
      P = [x for x in range(11, 100, 2) if all(x % p for p in (3, 5, 7))]
       
      # In answering the question 'is your number the smallest of the three?',
      # if they see numbers held by the other two that are less than or equal
      # to their current inferred minimum, they would be able to answer 'no';
      # so when they answer "don't know" we can remove such numbers as possible
      # for the other two; being unable to answer the question 'is your number
      # the largest of the three?' similarly allows us to remove numbers for
      # the others that are greater than or equal to their inferred maximum. 
      # The same numbers will also be removed from the questioner his/her self
      # during the next question.
      
      # After 3 rounds of questions 9*2 numbers have been removed for A and B
      # and 9*2 - 1 numbers for C (as C asked the last question)
      
      A = P[9:-9]
      B = P[9:-9]
      C = P[8:-8]
      
      # In round four Alf answered "Don't know" to the first question.
      # Alf's inferred minimum was A[0] so Bert and Charlie drew cards > A[0]
      B = [p for p in B if p > A[0]]
      C = [p for p in C if p > A[0]]
      
      # map possible values for B and C to lists of possible A values
      d = {tuple(sorted(prd)): [a for a in A if a not in prd]
           for prd in product(B, C) if prd[0] != prd[1] 
               and any(p < A[-1] for p in prd)}
      
      # Alf can give an answer if he has only one possible number 
      d = {k: vs for k, vs in d.items() if len(vs) > 1}
      
      # report possibilities that are left
      for bc, a in d.items():
        # Alf is asked "Is your number the largest of the three?"
        ans = "Yes" if a[0] > bc[-1] else "No" if a[-1] < bc[-1] else "Don't know"
        
        # all values in B are also in C, check if high number only occurs in C
        (bc, relation) = (set(bc), "in") if bc[-1] in B else (bc, "=")     
            
        print(f"answer = {ans}, (B, C) {relation} {bc} and A in {set(a)}")
      

      Like

  • Unknown's avatar

    Jim Randell 8:57 am on 21 September 2021 Permalink | Reply
    Tags: by: John Owen, ,   

    Teaser 2823: Queuing 

    From The Sunday Times, 30th October 2016 [link] [link]

    Tickets for the event went on sale at 09:30. The queue started at 09:00 when 2 people arrived, then 4 more at 09:01, 6 more at 09:02 and so on until 60 more arrived at 09:29. Just 16 people arrived at 09:30, 16 more at 09:31, 16 more at 09:32 and so on. Tickets were sold steadily at a rate of 25 per minute (one per person).

    Joe and I were the first to arrive at our respective minutes, but we had identical waiting times before being sold our tickets, and no-one waited for less time to get a ticket. Joe was lucky to get the last ticket to be sold.

    At what time did Joe join the queue?

    This version of the text is provided by the setter, and differs from the version published in The Sunday Times.

    [teaser2823]

     
    • Jim Randell's avatar

      Jim Randell 8:58 am on 21 September 2021 Permalink | Reply

      The problem with this puzzle (particularly in the form it was published in the newspaper) was working out the intended mechanics of the situation.

      We suppose that all people joining the queue, do so simultaneously at the start of each specified minute. And that when the tickets are sold, they sold sequentially (a single ticket booth), with each sale taking exactly 1/25 minute (= 0.04m = 2.4s). This is apparently what the setter intended.

      The following Python program simulates the sale of tickets as described, and looks for minimal wait times that occur for the first member of a joining clump, until the value is repeated (then the earlier one is the setter, and the later one Joe, and Joe gets the last ticket, so sales end).

      It produces a log of events as it goes, and runs in 72ms.

      Run: [ @replit ]

      from enigma import irange, inf, sprintf, printf
      
      # format a time, (m=0, f=0) = 09:00.00
      def fmt(m, f=0):
        (h, m) = divmod(m, 60)
        return sprintf("{h:02d}:{m:02d}.{f:02d}", h=h + 9, f=4 * f)
      
      # the queue, record groups as (number of people, start minute)
      q = [(0, -1)]
      
      # extend the queue, add n people with value m
      def extend(q, n, m):
        if n > 0:
          q.append((n, m))
      
      # pop the queue, identifying the first in a group, return (x, flag)
      def pop(q):
        ((n, m), flag) = (q[0], 0)
        if n == 0:
          # move on to the next group
          q.pop(0)
          ((n, m), flag) = (q[0], 1)
        q[0] = (n - 1, m)
        return (m, flag)
      
      # size of the queue
      def size(q):
        return sum(n for (n, m) in q)
      
      # t = tickets sold
      # W = shortest waiting time
      # data = information for minimal wait times
      (t, W, data) = (0, inf, None)
      
      # run a timer
      for i in irange(0, inf):
        # m = minutes, f = fractions (1/25) of a minute
        (m, f) = divmod(i, 25)
      
        # on the minute
        if f == 0:
          # up to 09:29, 2m + 2 people join the queue
          # afterwards, 16 people join the queue
          n = (2 * m + 2 if m < 30 else 16)
          extend(q, n, m)
          printf("time {i}: added {n} people to queue, queue length = {q}", i=fmt(m, f), q=size(q))
      
        # from 9:30, one ticket is sold per frame
        if m > 29:
          t += 1
          # calculate waiting time (in frames)
          (x, flag) = pop(q)
          w = 25 * (m - x) + f
          printf("time {i}: joined at {x}, waited {w} frames, ticket {t}", i=fmt(m, f), x=fmt(x))
          # is this a new minimum?
          if not (w > W):
            printf("-> min wait = {w} frames for ticket {t}")
            if w < W:
              W = w
              data = list()
            # is this the first in their group?
            if flag:
              # record data
              data.append((x, m, f, t))
              # are we done?
              if len(data) == 2:
                printf("-> sold out after ticket {t}, queue length = {q}\n", q=size(q))
                # output solution
                for (n, (x, m, f, t)) in enumerate(data, start=1):
                  printf("{n} joined at {x}, served at {m}, ticket {t}", x=fmt(x), m=fmt(m, f))
                break
      

      Solution: Joe joined the queue at 10:06.

      The minimal wait time is 24.24 minutes (= 606/25 minutes).

      When the 1507 tickets sell out there are 399 people remaining in the queue.

      The setter joined the queue at 09:12, and got the 157th ticket at 09:36.24.

      Joe joined the queue at 10:06, and got the 1507th (and final) ticket at 10:30.24.

      So, if the tickets are numbered consecutively from 1, the digit sum of the two tickets is the same (and if they are numbered with leading zeros where necessary, the ticket numbers are anagrams of each other).

      Like

      • Jim Randell's avatar

        Jim Randell 9:03 am on 21 September 2021 Permalink | Reply

        The puzzle text as originally published in the newspaper read as follows:

        Tickets for the event went on sale at 09:30. The queue started at 09:00 when 2 people arrived, then 4 more at 09:01, 6 more at 09:02 and so on until 60 more arrived at 09:29. Just 16 people arrived at 09:30, 16 more at 09:31, 16 more at 09:32 and so on. Tickets were sold at 25 per minute (with one to each person in the queue) until they were sold out.

        Joe and I both had identical waiting times before being sold our tickets, despite me having arrived earlier, and no-one who got a ticket waited for less time than us.

        At what time did Joe join the queue?

        My interpretation of this was that people joined the queue simultaneously at the start of a minute. And when the tickets were sold, the 25 people at the head of the queue were processed simultaneously, at the start of each minute. (You can suppose there are 25 ticket booths, and each transaction takes exactly one minute). The wait times will always be whole numbers of minutes.

        The main problem I came across with this method was that we don’t know how many tickets there are (it is implied that they sell out at some point), but if we suppose Joe is in the last batch of 25 tickets sold we can solve the problem.

        Here is my code adapted to process the tickets 25 at a time.

        from enigma import (irange, inf, sprintf, printf)
        
        # format a time, m=0 = 09:00
        def fmt(m):
          (h, m) = divmod(m, 60)
          return sprintf("{h:02d}:{m:02d}", h=h + 9)
        
        # the queue, record groups as (number of people, start minute)
        q = [(0, -1)]
        
        # extend the queue, add n people with value m
        def extend(q, n, m):
          if n > 0:
            q.append((n, m))
        
        # pop the queue, identifying the first in a group, return (x, flag)
        def pop(q):
          ((n, m), flag) = (q[0], 0)
          if n == 0:
            # move on to the next group
            q.pop(0)
            ((n, m), flag) = (q[0], 1)
          q[0] = (n - 1, m)
          return (m, flag)
        
        # size of the queue
        def size(q):
          return sum(n for (n, m) in q)
        
        # t = tickets sold
        # W = shortest waiting time
        # data = information for minimal wait times
        (t, W, data) = (0, inf, None)
        
        # run a timer (in minutes)
        for m in irange(0, inf):
        
          # up to 9:29, 2m + 2 people join the queue
          # afterwards, 16 people join the queue
          n = (2 * m + 2 if m < 30 else 16)
          extend(q, n, m)
          printf("time {m}: added {n} people to queue, queue length = {q}", m=fmt(m), q=size(q))
        
          # from 9:30, 25 tickets are processed per minute
          if m > 29:
            for _ in irange(1, min(25, size(q))):
              t += 1
              # calculate waiting time (in frames)
              (x, flag) = pop(q)
              w = m - x 
              printf("time {m}: joined at {x}, waited {w} minutes, ticket {t}", m=fmt(m), x=fmt(x))
              # is this a new minimum?
              if not (w > W):
                printf("-> min wait = {w} minutes for ticket {t}{s}", s=(' [first]' if flag else ''))
                if w < W:
                  W = w
                  data = list()
                # is this the first in their group?
                if flag:
                  # record data
                  data.append((x, m, t))
        
            # are we done?
            if len(data) > 1:
              printf("\nsold out after {t} tickets, min wait = {w} minutes, queue length = {q}", q=size(q))
              # output solution
              for (n, (x, m, t)) in enumerate(data, start=1):
                printf("{n} joined at {x}, served at {m}, ticket {t}", x=fmt(x), m=fmt(m))
              printf()
              break
        

        We get the solution:

        minimal wait time = 24 minutes
        setter joined queue @ 9:08, served @ 9:32, ticket 73
        joe joined queue @ 9:09, served @ 9:33, ticket 91
        100 tickets sold, 894 people remaining in queue

        Like

  • Unknown's avatar

    Jim Randell 8:46 am on 29 December 2020 Permalink | Reply
    Tags: by: John Owen   

    Teaser 2508: [Near miss] 

    From The Sunday Times, 17th October 2010 [link] [link]

    An Austin was pootling along a country lane at 30mph; behind were a Bentley doing 40mph and a Cortina doing 50mph. The Bentley and the Cortina braked simultaneously, decelerating at constant rates, while the Austin carried on at the same speed. The Bentley just avoided hitting the rear of the Austin, [while, at the same time,] the Cortina just avoided a collision with the Bentley. The Bentley and the Cortina continued to decelerate at the same rates, and stopped with a 45 yard gap between them.

    What was the gap between the Bentley and the Cortina at the moment they started to brake?

    The wording in this puzzle has been modified from the published version for clarification.

    This puzzle was originally published with no title.

    [teaser2508]

     
    • Jim Randell's avatar

      Jim Randell 8:46 am on 29 December 2020 Permalink | Reply

      I am assuming that at the time of the “almost collision” the separation between A, B and B, C can be considered to be zero. (And so we can consider the cars to be points, that coincide at the moment of “almost collision”).

      This puzzle can be solved graphically, without the need to resort to equations of motion (although you can solve it that way too).

      If we plot the velocities of the Austin (red), the Bentley (green), and the Cortina (blue) against time we get a graph like this:

      Where red carries on at a steady 30mph, green starts at 40mph and decelerates steadily to 0mph (BB’), and blue starts at 50mph and decelerates steadily to 0mph (CC’).

      At X, all their speeds are 30mph, and this is the point at which the separations between the cars are zero (the almost collision).

      The area under the line XB’ gives the distance travelled by green after the almost collision, and the area under the line XC’ gives the distance travelled by blue after the almost collision.

      And the difference between these distances corresponds to their final separation:

      area(XUB’) − area(XUC’) = 45 yards
      (45 − 45/2) units = 45 yards
      1 unit = 2 yards

      Similarly we can calculate the difference between the areas under the lines CX and BX to get the separation of green and blue at the time they started braking:

      area(CAX) − area(BAX) = (10 − 5) units
      = 10 yards

      Solution: The Bentley and the Cortina were 10 yards apart at the time they started braking.

      Like

  • Unknown's avatar

    Jim Randell 4:51 pm on 4 December 2020 Permalink | Reply
    Tags: by: John Owen   

    Teaser 3037: Prime advent calendar 

    From The Sunday Times, 6th December 2020 [link] [link]

    Last year I was given a mathematical Advent calendar with 24 doors arranged in four rows and six columns, and I opened one door each day, starting on December 1. Behind each door is an illustrated prime number, and the numbers increase each day. The numbers have been arranged so that once all the doors have been opened, the sum of the numbers in each row is the same, and likewise for the six columns. Given the above, the sum of all the prime numbers is as small as it can be.

    On the 24th, I opened the last door to find the number 107.

    In order, what numbers did I find on the 20th, 21st, 22nd and 23rd?

    [teaser3037]

     
    • Jim Randell's avatar

      Jim Randell 6:52 pm on 4 December 2020 Permalink | Reply

      I think this is the first Teaser in quite a while that has taken me more than a few minutes to solve. Fortunately all the numbers we are dealing with are different, so that simplifies things a bit.

      My original program [link] was shorter, but less efficient (it runs in 3.4s). The following Python 3 program is longer, but runs in only 81ms.

      Run: [ @repl.it ]

      from enigma import Primes, subsets, diff, intersect, div, join, peek, sprintf, printf
      
      # choose length k sets from ns, where each set sums to t
      def rows(ns, k, t, ss=[]):
        # are we done?
        if not ns:
          yield ss
        else:
          # take the first element
          n = ns[0]
          # and k-1 other elements to go with it
          for s in subsets(ns[1:], size=k - 1):
            if sum(s) == t - n:
              s = (n,) + s
              yield from rows(diff(ns, s), k, t, ss + [s])
      
      # make a column that sums to t, by choosing an element from each row
      def make_col(rs, t, s=[]):
        if len(rs) == 1:
          if t in rs[0]:
            yield tuple(s + [t])
        else:
          for x in (rs[0][:1] if len(s) == 0 else rs[0]):
            t_ = t - x
            if t_ > 0:
              yield from make_col(rs[1:], t_, s + [x])
      
      # make columns from the rows, where each column sums to t
      def cols(rs, t, ss=[]):
        # are we done?
        if not rs[0]:
          yield ss
        else:
          # make one column
          for s in make_col(rs, t):
            # and then make the rest
            yield from cols(list(diff(r, [x]) for (r, x) in zip(rs, s)), t, ss + [s])
      
      # solve the puzzle
      def solve():
        # possible primes
        primes = Primes(107)
      
        # find viable sets of primes
        for ps in sorted(subsets(primes, size=23), key=sum):
          ps += (107,)
          # total sum = T, row sum = R, col sum = C
          T = sum(ps)
          R = div(T, 4)
          C = div(T, 6)
          if R is None or C is None: continue
          printf("[T={T} R={R} C={C}]")
      
          # choose rows of 6, each sums to R
          for rs in rows(ps, 6, R):
            # select columns, each sums to C
            for cs in cols(rs, C):
              yield (ps, rs, cs)
      
      # find the first solution
      for (ps, rs, cs) in solve():
        # output solution
        printf("ps = {ps} -> {T}", T=sum(ps))
        printf("rs = {rs} -> {R}", R=sum(rs[0]))
        printf("cs = {cs} -> {C}", C=sum(cs[0]))
      
        # output solution grid
        for r in rs:
          printf("{r}", r=join(sprintf("[{x:3d}]", x=peek(intersect((r, c)))) for c in cs))
      
        # we only need the first solution
        break
      

      Solution: The numbers on the 20th, 21st, 22nd, 23rd were: 73, 79, 83, 101.

      One possible layout is shown below, but there are many others:

      Each row sums to 270. Each column sums to 180. Altogether the numbers sum to 1080.

      I let my program look for solutions with a higher sum, and it is possible to construct a calendar for every set of primes whose sum is a multiple of 24.

      Like

    • Frits's avatar

      Frits 12:02 pm on 5 December 2020 Permalink | Reply

      @Jim, you can also remove 2 from primes (as column sum needs to be even (row sum, 1.5 * column sum, must be a whole number) and there is only 1 even prime in primes).

      With this, your first reported T,R,C combination can be discarded as R may not be odd (sum of 6 odd numbers is even).

      I also have the same first solution but it takes a long time (mainly in checking column sums).
      I first tried a program with SubstitutedExpression but I had problems with that.

      Like

      • Jim Randell's avatar

        Jim Randell 5:18 pm on 5 December 2020 Permalink | Reply

        @Frits: Thanks. I realised that 2 wasn’t going to be involved in final grid. But if you exclude it at the start, and only allow even row and column sums, then the runtime of my program goes down to 58ms. (And the internal runtime is down to 14ms).

        Like

        • Frits's avatar

          Frits 8:17 pm on 5 December 2020 Permalink | Reply

          @Jim,

          A further improvement could be to skip checking subsets (line 45) when testing sum 1080 as the number of primes to be used is fixed.

          Sum of primes from 3 to 107 is 1369 (for 27 primes)
          1369 – 1080 = 289 which can only be formed by 3 primes with (89, 97 and 103 ).
          The 24 remaining primes can be used to do the rows and cols logic.

          Like

          • Jim Randell's avatar

            Jim Randell 10:15 pm on 5 December 2020 Permalink | Reply

            @Frits: I’m not sure I understand. In my program the sets of primes are tackled in sum order (to ensure we find the set with the lowest sum), so only one set of primes with sum 1080 will be checked (as there is only one set that sums to 1080).

            Like

            • Frits's avatar

              Frits 11:46 pm on 5 December 2020 Permalink | Reply

              You can analyze that 1080 is the first sum to check (sum has to be a multiple of 24).

              So you don’t need to execute line 45 if you first have a separate check for 1080 (with the 24 primes) and you do find an answer for it.

              The disadvantage is that it will make the code less concise.

              Like

            • Frits's avatar

              Frits 11:51 pm on 5 December 2020 Permalink | Reply

              Meaning:

              handle 1080 sum, exit program if solution found
              
              for ps in sorted(subsets(primes, size=23), key=sum)
                if sum == 1080: continue
                .....
              

              Like

    • Frits's avatar

      Frits 10:17 am on 6 December 2020 Permalink | Reply

      A little bit different and less efficient.

      from itertools import combinations as comb
      from itertools import product as prod
      from enigma import group
      
      flat = lambda group: {x for g in group for x in g}
      
      # Prime numbers up to 107 
      Pr =  [2, 3, 5, 7]
      Pr += [x for x in range(11, 100, 2) if all(x % p for p in Pr)]
      Pr += [x for x in range(101, 108, 2) if all(x % p for p in Pr)]
      
      min1 = sum(Pr[1:24]) + 107
      max1 = sum(Pr[-24:])
      print("    sum    row     column")  
      print("min", min1, " ", round(min1 / 4, 2), " ", round(min1 / 6, 2))
      print("max", max1, " ", round(max1 / 4, 2), " ", round(max1 / 6, 2))
      
      Pr = Pr[1:-1]              # exclude 2 and 107
      
      sumPr = sum(Pr + [107])
      lenPr = len(Pr + [107])
      
      # length Pr + [107]: 27, sum(Pr + [107]) = 1369
      #
      #     sum    row     column
      # min 1068   267.0   178.0
      # max 1354   338.5   225.66666666666666
        
      # pick one value from each entry of a <k>-dimensional list <ns>
      def pickOneFromEach(k, ns, s=[]):
        if k == 0:
           yield s 
        else:
          for n in ns[k-1]:
            yield from pickOneFromEach(k - 1, ns, s + [n])  
            
      # decompose <t> into <k> increasing numbers from <ns>
      # so that sum(<k> numbers) equals <t>
      def decompose(t, k, ns, s=[], used=[], m=1):
        if k == 1:
          if t in ns and not(t in s or t in used) :
            if not(t < m): 
              yield s + [t]
        else:
          for (i, n) in enumerate(ns):
            if not(n < t): break
            if n in s or n in used: continue
            if (n < m): continue
            yield from decompose(t - n, k - 1, ns[i:], s + [n], used, n)
            
      # check if sums are the same for all columns
      def checkColSums(rs, t):
        correctSumList = [p for p in prod(*rs) if sum(p) == t]
        uniqueFirstCols = len(set(x[0] for x in correctSumList))
         
        if uniqueFirstCols < 6:        # elements are not unique
          return
        elif uniqueFirstCols == 6:
          groupByFirstCol = [x for x in group(correctSumList, 
                             by=(lambda d: d[0])).values()]
          for p in list(pickOneFromEach(6, groupByFirstCol)):
            if len(set(flat(p))) == 24:
              yield p
        else:  
          for c in comb(correctSumList, 6):
            if len(set(flat(c))) == 24:
              yield c        
      
      # check sums by starting with smallest 
      for T in {x for x in range(min1, max1 + 1) if x % 24 == 0}:
        dif = sumPr - T
        rsum = T // 4
        csum = T // 6
        print("\nTotal sum",T, "row sum",rsum, "col sum",csum, "difference", dif)
        
        # check which primes are to be dropped
        c = 0
        for di in decompose(dif, lenPr - 24, Pr): 
          if c == 0:
            Pr2 = [x for x in Pr if x not in di] + [107]
          c += 1  
          
        if c > 1:           # more possibilities to drop primes
          Pr2 = list(Pr)
        
        print(f"\nPrimes to check={Pr2}")
        
        # first make 4 lists of 6 numbers which add up to rsum
        for s1 in decompose(rsum - 107, 5, Pr2, [107]):
          s1 = s1[1:] + [s1[0]]                   # put 107 at the end
          for s1 in decompose(rsum, 6, Pr2, s1, m=s1[0]):
            for s1 in decompose(rsum, 6, Pr2, s1, m=s1[6]):
              for s1 in decompose(rsum, 6, Pr2, s1, m=s1[12]):
                rs = [s1[0:6], s1[6:12], s1[12:18], s1[18:24]]
                # check if all columns add up to csum
                for cs in checkColSums(rs, csum):
                  print("\nSolution: \n")
                  for r in zip(*cs[::-1]):        # rotate matrix
                    for x in r:
                      print(f"{x:>3}", end = " ")
                    print()  
                  
                  print("\nNumbers on the 20th, 21st, 22nd and 23rd:")  
                  print(", ".join(str(x) for x in sorted(flat(cs))[-5:-1]))
                  exit(0)  
      

      Like

      • Jim Randell's avatar

        Jim Randell 2:30 pm on 6 December 2020 Permalink | Reply

        @Frits: I don’t think you want to use a set() at line 70. The set() will remove duplicates, but you are not guaranteed to get the numbers out in increasing order. In this case we know that there are no duplicates, and we definitely want to consider the numbers in increasing order (so we can be sure we have found the smallest).

        Changing the brackets to () or [] will do, but I think there are clearer ways to write the loop.

        Like

        • Frits's avatar

          Frits 7:18 pm on 6 December 2020 Permalink | Reply

          @Jim. Thanks.

          I normally run python programs with PyPy and PyPy preserves the order of dictionaries and sets.

          Running with Python solved the sum 1152 and not for 1080.

          Like

          • Jim Randell's avatar

            Jim Randell 11:10 am on 7 December 2020 Permalink | Reply

            @Frits: OK. I knew about the PyPy’s behaviour for dict(), but not for set().

            FWIW: I try to post code that runs on as wide a variety of Pythons as possible. I currently check against CPython 2.7.18 and 3.9.0 (although sometimes I use features that only became available in Python 3).

            Like

    • GeoffR's avatar

      GeoffR 10:43 am on 7 December 2020 Permalink | Reply

      I found a solution in MiniZinc, but the run time was very slow (just over 5 min)

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      % grid of Advent calendar doors
      % a b c d e f
      % g h i j k l
      % m n o p q r
      % s t u v w x
      
      % set of primes, excluding 2 as non viable for this puzzle
      set of int: primes = {3, 5, 7, 11, 13, 17, 19, 23,
      29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
      83, 89, 97, 101, 103, 107};
      
      set of int: Digit = 3..107;
      
      % 24 prime numbers
      var Digit: a; var Digit: b; var Digit: c; var Digit: d;
      var Digit: e; var Digit: f; var Digit: g; var Digit: h; 
      var Digit: i; var Digit: j; var Digit: k; var Digit: l; 
      var Digit: m; var Digit: n; var Digit: o; var Digit: p; 
      var Digit: q; var Digit: r; var Digit: s; var Digit: t;
      var Digit: u; var Digit: v; var Digit: w; var Digit: x; 
      
      var 0..1400: psum = sum([a, b, c, d, e, f, g, h, i, j,
       k, l, m, n, o, p, q, r, s, t, u, v, w, x]);
       
      constraint all_different ([a, b, c, d, e, f, g, h, i, j,
       k, l, m, n, o, p, q, r, s, t, u, v, w, x]);
      
      % allocate 24 primes
      constraint a in primes /\ b in primes /\ c in primes
      /\ d in primes /\ e in primes /\ f in primes;
      
      constraint g in primes /\ h in primes /\ i in primes
      /\ j in primes /\ k in primes /\ l in primes;
      
      constraint m in primes /\ n in primes /\ o in primes
      /\ p in primes /\ q in primes /\ r in primes;
      
      constraint s in primes /\ t in primes /\ u in primes
      /\ v in primes /\ w in primes;
      
      % put highest prime in Xmas Eve Box to fix grid
      constraint x == 107;
      
      % row totals add to the same value
      constraint (a + b + c + d + e + f) == (g + h + i + j + k + l)
      /\ (a + b + c + d + e + f) == (m + n + o + p + q + r)
      /\ (a + b + c + d + e + f) == (s + t + u + v + w + x);
      
      % column totals add to the same value
      constraint (a + g + m + s) == (b + h + n + t)
      /\ (a + g + m + s) == (c + i + o + u)
      /\ (a + g + m + s) == (d + j + p + v)
      /\ (a + g + m + s) == (e + k + q + w)
      /\ (a + g + m + s) == (f + l + r + x);
      
      % sum of grid primes is divisible by 12 - LCM of 4 and 6
      % as 4 x row sum = psum and 6 x column sum = psum
      constraint psum mod 12 == 0;
       
      % minimise total sum of prime numbers used
      solve minimize psum;
      
      % find unused primes in original max list of primes
      var set of int: digits_not_used = primes diff 
      {a, b, c, d, e, f, g, h, i, j,
       k, l, m, n, o, p, q, r, s, t, u, v, w, x};
      
      % output grid and grid row and column totals
      output ["  Grid is: " 
      ++ "\n " ++ show([a, b, c, d, e, f]) 
      ++ "\n " ++ show([g, h, i, j, k, l])
      ++ "\n " ++ show([m, n, o, p, q, r])
      ++ "\n " ++ show([s, t, u, v, w, x]) 
      
      ++ "\n Prime Sum overall = " ++ 
      show(sum([a, b, c, d, e, f, g, h, i, j,
      k, l, m, n, o, p, q, r, s, t, u, v, w, x]))
      
      ++ "\n Row sum = " ++ show(sum([a + b + c + d + e + f])) 
      ++ "\n Column sum = " ++ show(sum([a + g + m + s]))
      ++ "\n Unused primes : " ++ show(digits_not_used) ];
      
      

      Like

      • Frits's avatar

        Frits 1:33 pm on 8 December 2020 Permalink | Reply

        Finding a solution takes less than a second.

        I used the fact that psum has to be a multiple of 24 and has a minimum/maximum of 1080/1344.

        Biggest time gain seems to have come from replacing the psum definition from the sum of 24 variables to 6 times the sum of 4 variables.

        % A Solution in MiniZinc
        include "globals.mzn";
         
        % grid of Advent calendar doors
        % a b c d e f
        % g h i j k l
        % m n o p q r
        % s t u v w x
         
        % set of primes, excluding 2 as non viable for this puzzle
        set of int: primes = {3, 5, 7, 11, 13, 17, 19, 23,
        29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
        83, 89, 97, 101, 103, 107};
        
        % psum is a multiple of 24 as column total is a multiple of 4
        % (otherwise row total would be odd which is not possible)
        set of int: psums = {1080, 1104, 1128, 1152, 1176, 1200,
        1224, 1248, 1272, 1296, 1320, 1344};
         
        set of int: Digit = 3..107;
         
        % 24 prime numbers
        var Digit: a; var Digit: b; var Digit: c; var Digit: d;
        var Digit: e; var Digit: f; var Digit: g; var Digit: h; 
        var Digit: i; var Digit: j; var Digit: k; var Digit: l; 
        var Digit: m; var Digit: n; var Digit: o; var Digit: p; 
        var Digit: q; var Digit: r; var Digit: s; var Digit: t;
        var Digit: u; var Digit: v; var Digit: w; var Digit: x; 
         
        %var 1080..1344: psum = sum([a, b, c, d, e, f, g, h, i, j,
        % k, l, m, n, o, p, q, r, s, t, u, v, w, x]);
        var 1080..1344: psum = 6 * (a + g + m + s);
        constraint psum = 4 * (a + b + c + d + e + f);
        constraint psum in psums;
         
        constraint all_different ([a, b, c, d, e, f, g, h, i, j,
         k, l, m, n, o, p, q, r, s, t, u, v, w, x]);
         
        % allocate 24 primes
        constraint a in primes /\ b in primes /\ c in primes
        /\ d in primes /\ e in primes /\ f in primes;
         
        constraint g in primes /\ h in primes /\ i in primes
        /\ j in primes /\ k in primes /\ l in primes;
         
        constraint m in primes /\ n in primes /\ o in primes
        /\ p in primes /\ q in primes /\ r in primes;
         
        constraint s in primes /\ t in primes /\ u in primes
        /\ v in primes /\ w in primes;
         
        % put highest prime in Xmas Eve Box to fix grid
        constraint x == 107;
         
        % row totals add to the same value
        constraint (a + b + c + d + e + f) == (g + h + i + j + k + l)
        /\ (a + b + c + d + e + f) == (m + n + o + p + q + r)
        /\ (a + b + c + d + e + f) == (s + t + u + v + w + x);
        
        % column totals add to the same value
        constraint (a + g + m + s) == (b + h + n + t)
        /\ (a + g + m + s) == (c + i + o + u)
        /\ (a + g + m + s) == (d + j + p + v)
        /\ (a + g + m + s) == (e + k + q + w)
        /\ (a + g + m + s) == (f + l + r + x);
         
        % minimise total sum of prime numbers used
        solve minimize psum;
         
        % find unused primes in original max list of primes
        var set of int: digits_not_used = primes diff 
        {a, b, c, d, e, f, g, h, i, j,
         k, l, m, n, o, p, q, r, s, t, u, v, w, x};
         
        % output grid and grid row and column totals
        output ["  Grid1 is: " 
        ++ "\n " ++ show([a, b, c, d, e, f]) 
        ++ "\n " ++ show([g, h, i, j, k, l])
        ++ "\n " ++ show([m, n, o, p, q, r])
        ++ "\n " ++ show([s, t, u, v, w, x]) 
         
        ++ "\n Prime Sum overall = " ++ 
        show(sum([a, b, c, d, e, f, g, h, i, j,
        k, l, m, n, o, p, q, r, s, t, u, v, w, x]))
         
        ++ "\n Row sum = " ++ show(sum([a + b + c + d + e + f])) 
        ++ "\n Column sum = " ++ show(sum([a + g + m + s]))
        ++ "\n Unused primes : " ++ show(digits_not_used) ];
        

        Like

        • GeoffR's avatar

          GeoffR 9:48 pm on 8 December 2020 Permalink | Reply

          Thanks to Frits for his optimisation of my code to make it run a lot faster.

          I have added an explanation of the range calculation for psum ie 1080..1344.

          I also found I could tidy code further by just using psum mod24 == 0. It was not necessary to use a list of prime sums in this revised code. It ran in about 0.6 sec.

          % A Solution in MiniZinc  - version 3
          include "globals.mzn";
            
          % grid of Advent calendar doors
          % a b c d e f
          % g h i j k l
          % m n o p q r
          % s t u v w x
            
          % set of primes, excluding 2 as non viable for this puzzle
          set of int: primes = {3, 5, 7, 11, 13, 17, 19, 23,
          29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
          83, 89, 97, 101, 103, 107};
           
          set of int: Digit = 3..107;
          
          % The minimum prime sum = sum of first 23 + 107 = 1068
          % The maximum prime sum = sum of last 24 = 1354
          % The prime sum (psum) = 4 * row_sum = 6 * column_sum
          % But, since the row and column sums are both even, psum 
          % is a multiple of both 8 and 12 and hence also of their 
          % lowest common multiple 24, giving 1080 <= psum <= 1344
          var 1080..1344: psum;      
          
          % 24 prime numbers
          var Digit: a; var Digit: b; var Digit: c; var Digit: d;
          var Digit: e; var Digit: f; var Digit: g; var Digit: h; 
          var Digit: i; var Digit: j; var Digit: k; var Digit: l; 
          var Digit: m; var Digit: n; var Digit: o; var Digit: p; 
          var Digit: q; var Digit: r; var Digit: s; var Digit: t;
          var Digit: u; var Digit: v; var Digit: w; var Digit: x; 
          
          constraint psum = 4 * (a + b + c + d + e + f)
                  /\ psum = 6 * (a + g + m + s) 
                  /\ psum mod 24 == 0;
            
          constraint all_different ([a, b, c, d, e, f, g, h, i, j,
           k, l, m, n, o, p, q, r, s, t, u, v, w, x]);
            
          % allocate 24 primes
          constraint a in primes /\ b in primes /\ c in primes
          /\ d in primes /\ e in primes /\ f in primes;
            
          constraint g in primes /\ h in primes /\ i in primes
          /\ j in primes /\ k in primes /\ l in primes;
            
          constraint m in primes /\ n in primes /\ o in primes
          /\ p in primes /\ q in primes /\ r in primes;
            
          constraint s in primes /\ t in primes /\ u in primes
          /\ v in primes /\ w in primes;
            
          % put highest prime in Xmas Eve Box to fix grid
          constraint x == 107;
            
          % row totals add to the same value
          constraint (a + b + c + d + e + f) == (g + h + i + j + k + l)
          /\ (a + b + c + d + e + f) == (m + n + o + p + q + r)
          /\ (a + b + c + d + e + f) == (s + t + u + v + w + x);
           
          % column totals add to the same value
          constraint (a + g + m + s) == (b + h + n + t)
          /\ (a + g + m + s) == (c + i + o + u)
          /\ (a + g + m + s) == (d + j + p + v)
          /\ (a + g + m + s) == (e + k + q + w)
          /\ (a + g + m + s) == (f + l + r + x);
            
          % minimise total sum of prime numbers used
          solve minimize psum;
            
          % find unused primes in original max list of primes
          var set of int: digits_not_used = primes diff 
          {a, b, c, d, e, f, g, h, i, j,
           k, l, m, n, o, p, q, r, s, t, u, v, w, x};
            
          % output grid and grid row and column totals
          output ["  Grid is: "
          ++ "\n " ++ show([a, b, c, d, e, f]) 
          ++ "\n " ++ show([g, h, i, j, k, l])
          ++ "\n " ++ show([m, n, o, p, q, r])
          ++ "\n " ++ show([s, t, u, v, w, x]) 
            
          ++ "\n Prime Sum overall = " ++
          show(sum([a, b, c, d, e, f, g, h, i, j,
          k, l, m, n, o, p, q, r, s, t, u, v, w, x]))
            
          ++ "\n Row sum = " ++ show(sum([a + b + c + d + e + f])) 
          ++ "\n Column sum = " ++ show(sum([a + g + m + s]))
          ++ "\n Unused primes : " ++ show(digits_not_used) ];
          
          
          
          
          
          

          Like

      • Frits's avatar

        Frits 1:48 pm on 8 December 2020 Permalink | Reply

        Another program using many nested loops.

        from itertools import product as prod
        
        # Prime numbers up to 107 
        Pr =  [2, 3, 5, 7]
        Pr += [x for x in range(11, 100, 2) if all(x % p for p in Pr)]
        Pr += [x for x in range(101, 108, 2) if all(x % p for p in Pr)]
        
        # sum has to be a multiple of 24 
        # (if column sum is not a multiple of 4 then the row sum will be odd)
        min1 = sum(Pr[1:24]) + 107
        min1 = [x for x in range(min1, min1 + 24) if x % 24 == 0][0]
        max1 = sum(Pr[-24:])
        max1 = [x for x in range(max1 - 23, max1 + 1) if x % 24 == 0][0]
        
        Pr = Pr[1:-1]              # exclude 2 and 107
        
        sumPr = sum(Pr + [107])
        lenPr = len(Pr + [107])
        
        # make sure loop variable value is not equal to previous ones
        def domain(v):
          # find already used loop values  ...
          vals = set()
          # ... by accessing previously set loop variable names
          for s in lvd[v]:
            vals.add(globals()[s])
        
          return [x for x in Pr2 if x not in vals]
          
        # decompose <t> into <k> increasing numbers from <ns>
        # so that sum(<k> numbers) equals <t>
        def decompose(t, k, ns, s=[], used=[], m=1):
          if k == 1:
            if t in ns and not(t in s or t in used) :
              if not(t < m): 
                yield s + [t]
          else:
            for (i, n) in enumerate(ns):
              if not(n < t): break
              if n in s or n in used: continue
              if (n < m): continue
              yield from decompose(t - n, k - 1, ns[i:], s + [n], used, n)
        
        # pick <k> elements from list <li> so that all combined fields are different
        def uniqueCombis(k, li, s=[]):
          if k == 0:
            yield s
          else:
            for i in range(len(li)):
              if len(s + li[i]) == len(set(s + li[i])):
                yield from uniqueCombis(k - 1, li[i:], s + li[i])
              
        # check if sums are the same for all columns
        def checkColSums(rs, t):
          correctSumList = [list(p) for p in prod(*rs) if sum(p) == t]
          for u in uniqueCombis(6, correctSumList): 
            yield [u[0:4], u[4:8], u[8:12], u[12:16], u[16:20], u[20:]] 
            break       
                
                
        # set up dictionary of for-loop variables
        lv = ["A","B","C","D","E","F","G","H","I","J","K","L",
              "M","N","O","P","Q","R","S","T","U","V","W","X"]
        lvd = {v: lv[:i] for i, v in enumerate(lv)}        
        
        # check sums by starting with smallest 
        for T in [x for x in range(min1, max1 + 1) if x % 24 == 0]:
          dif = sumPr - T
          rsum = T // 4
          csum = T // 6
          print("\nTotal sum",T, "row sum",rsum, "col sum",csum, "difference", dif)
          
          # check which primes are to be dropped
          c = 0
          for di in decompose(dif, lenPr - 24, Pr): 
            if c == 0:
              Pr2 = [x for x in Pr if x not in di] 
            c += 1  
            
          if c > 1:           # more possibilities to drop primes
            Pr2 = list(Pr)
          
          print(f"\nPrimes to check = {Pr2}")
          
          for A in Pr2:
           for B in domain('B'):
            if B < A: continue
            for C in domain('C'):
             if C < B: continue
             for D in domain('D'):
              if D < C: continue
              for E in domain('E'):
               if E < D: continue
               for F in [107]:
                RSUM = sum([A,B,C,D,E,F])
                if RSUM < min1 // 4 or RSUM > max1 // 4 or RSUM % 6 != 0: continue
                for G in domain('G'):
                 for H in domain('H'):
                  if H < G: continue
                  for I in domain('I'):
                   if I < H: continue
                   for J in domain('J'):
                    if J < H: continue
                    for K in domain('K'):
                     if K < J: continue
                     L = RSUM - sum([G,H,I,J,K])
                     if L < K or L not in Pr2: continue
                     if L in {A,B,C,D,E,F,G,H,I,J,K}: continue
                     for M in domain('M'):
                      for N in domain('N'):
                       if N < M: continue
                       for O in domain('O'):
                        if O < N: continue
                        for P in domain('P'):
                         if P < O: continue
                         for Q in domain('Q'):
                          if Q < P: continue
                          R = RSUM - sum([M,N,O,P,Q])
                          if R < Q or R not in Pr2: continue
                          if R in {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q}: continue
                          for S in domain('S'):
                           for T in domain('T'):
                            if T < S: continue
                            for U in domain('U'):
                             if U < T: continue
                             for V in domain('V'):
                              if V < U: continue
                              for W in domain('W'):
                               if W < V: continue
                               X = RSUM - sum([S,T,U,V,W])
                               if X < W or X not in Pr2: continue
                               if X in {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W}:
                                 continue
                               rs = [[A,B,C,D,E,F],[G,H,I,J,K,L],
                                     [M,N,O,P,Q,R],[S,T,U,V,W,X]]
                               CSUM = (RSUM * 2) // 3
                               
                               # select columns, each sums to CSUM
                               for cs in checkColSums(rs, CSUM):
                                print("\nSolution: \n")
                                for r in zip(*cs[::-1]):        # rotate matrix
                                 for x in r:
                                  print(f"{x:>3}", end = " ")
                                 print() 
                                exit(0)
        

        Like

    • GeoffR's avatar

      GeoffR 7:41 pm on 8 December 2020 Permalink | Reply

      I get an error on the Idle and Wing IDE’s when I try to run this code:

      i.e Syntax Error: too many statically nested blocks

      Is there an easy fix?

      Like

      • Jim Randell's avatar

        Jim Randell 7:59 pm on 8 December 2020 Permalink | Reply

        @Geoff: There is a limit of 20 nested loops in the standard Python interpreter. But the PyPy interpreter doesn’t have this limit, so you can use it to execute code with lots of nested loops.

        Like

  • Unknown's avatar

    Jim Randell 8:38 am on 24 November 2020 Permalink | Reply
    Tags: by: John Owen   

    Teaser 2765: Prime points 

    From The Sunday Times, 20th September 2015 [link] [link]

    In my fantasy football league each team plays each other once, with three points for a win and one point for a draw. Last season Aberdeen won the league, Brechin finished second, Cowdenbeath third, and so on, in alphabetical order. Remarkably each team finished with a different prime number of points. Dunfermline lost to Forfar.

    In order, what were Elgin’s results against Aberdeen, Brechin, Cowdenbeath, and so on (in the form WWLDL…)?

    [teaser2765]

     
    • Jim Randell's avatar

      Jim Randell 8:38 am on 24 November 2020 Permalink | Reply

      This Python program considers possible numbers of teams (up to a maximum of 26, as each team is named for a letter of the alphabet), and looks for possible sequences of primes that could correspond to the points. Once a candidate sequence is found we try to fill out a table of match outcomes (win, lose, draw) that gives the desired number of points for each team.

      It runs in 49ms.

      Run: [ @repl.it ]

      from enigma import irange, T, Primes, subsets, express, update, join, printf
      
      points = { 'w': 3, 'd': 1 } # points for win, draw
      swap = { 'w': 'l', 'l': 'w', 'd': 'd' } # how a match went for the other team
      
      # complete the table by filling out row i onwards
      def complete(k, table, ps, i=0):
        # are we done?
        if not(i < k):
          yield table
        else:
          # collect: (total, empty squares)
          (t, js) = (ps[i], list())
          for (j, x) in enumerate(table[i]):
            if x == ' ':
              js.append(j)
            else:
              t -= points.get(x, 0)
          # find ways to express t using 3 (= w) and 1 (= d)
          for (d, w) in express(t, (1, 3)):
            # and the remaining games are lost
            l = len(js) - d - w
            if l < 0: continue
            # look for ways to fill out the row
            for row in subsets('w' * w + 'd' * d + 'l' * l, size=len, select="mP"):
              # make an updated table
              t = update(table, [(i, update(table[i], js, row))])
              for (j, x) in zip(js, row):
                t[j] = update(t[j], [(i, swap[x])])
              # and solve for the remaining points
              yield from complete(k, t, ps, i + 1)
      
      # list of primes
      primes = Primes(75)
      
      # consider the number of teams in the league
      for k in irange(6, 26):
      
        # total number of matches
        n = T(k - 1)
      
        # maximum possible number of points
        m = 3 * (k - 1)
      
        # choose a set of k distinct primes for the points
        for ps in subsets(primes.irange(2, m), size=k):
          # calculate the total number of points scored
          t = sum(ps)
          # number of drawn and won/lost matches
          d = 3 * n - t
          w = n - d
          if d < 0 or w < 0 or d > n or w > n: continue 
      
          # make the initial table
          table = list()
          for i in irange(k):
            row = [' '] * k
            row[i] = '-'
            table.append(row)
          # given data (D (= 3) lost to F (= 5))
          for (r, c, v) in [(3, 5, 'l')]:
            table[r][c] = v
            table[c][r] = swap[v]
      
          # complete the table for the list of points
          for t in complete(k, table, ps[::-1]):
            # output the table
            printf("[{k} teams, {n} matches ({d} drawn, {w} won/lost)]")
            ts = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"[:k]
            printf("   {ts}", ts=join(ts, sep=' '))
            for (n, r) in zip(ts, t):
              p = sum(points.get(x, 0) for x in r)
              printf("{n}: {r}  ->  {p:2d} pts", r=join(r, sep=' '))
            printf()
      

      Solution: Elgin’s results were: L L L L W D W.

      The complete table looks like this:

      [8 teams, 28 matches (7 drawn, 21 won/lost)]
         A B C D E F G H
      A: - d w w w w w w  ->  19 pts
      B: d - w d w w w w  ->  17 pts
      C: l l - d w w w w  ->  13 pts
      D: l d d - w l w w  ->  11 pts
      E: l l l l - w d w  ->   7 pts
      F: l l l w l - d d  ->   5 pts
      G: l l l l d d - d  ->   3 pts
      H: l l l l l d d -  ->   2 pts
      

      Like

    • Frits's avatar

      Frits 11:48 am on 25 November 2020 Permalink | Reply

      from itertools import product
      
      P = [2, 3, 5, 7]
      P += [x for x in range(11, 100, 2) if all(x % p for p in P)]
      P += [x for x in range(101, 104, 2) if all(x % p for p in P)]
      
      SCORES = [0, 1, 3]
      LDW = "LD-W"
      LETTERS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
      
      # determine the outcome of 0.5 * n * (n - 1) games
      def solve(n, i, pzl):
        if i < 0:
          yield pzl
       
        # determine number of unknown values
        cnt = sum(pzl[i][j] == -1 for j in range(n))
        
        for p in product(SCORES, repeat=cnt):
          save = list(pzl[i])
      
          x = 0
          for j in range(n):
            if pzl[i][j] == -1:
              pzl[i][j] = p[x]
              pzl[j][i] = (1 if p[x] == 1 else abs(p[x] - 3))
              x += 1
      
          if sum(pzl[i]) == P[n - i - 1]:    # correct total
            yield from solve(n, i - 1, pzl)  # solve next team
          pzl[i] = save                      # backtrack
      
      # generate cumulative sum list of primes
      cumsum = [sum(P[:i+1]) for i in range(len(P))]
      nlist = []
      
      # primes for teams must be minimal (2,3,5 ..) as otherwise the highest prime
      # exceeds the maximum score (n * 3)
      #
      # Dunfermline lost to Forfar so Forfar must have at least 3 points
      # and this can't happen in a league with 6 teams (6th team has 2 points)
      # so n > 6
      
      print("teams  games  draws  points max    high     reject reason")  
      for n in range(7, 27):
        games = int(0.5 * n * (n - 1)) 
        reason = ""
        if (n-1) * 3 - 1 == P[n-1]:
          reason = "high = max - 1"
        if (n-1) * 3 < P[n-1]:
          reason = "high > max"  
        print(f"{n:<6} {games:<6} {games * 3 - cumsum[n-1]:<6} {cumsum[n-1]:<6} "
              f"{(n-1) * 3:<6} {P[n-1]:<6}   {reason}")
        if reason == "":
          nlist.append(n)
       
      # solve and print table 
      for n in nlist:
        # create matrix
        pzl = [[-1 for i in range(n)] for j in range(n)]
        pzl[3][5] = 0      # Dunfermline lost to Forfar
        pzl[5][3] = 3      # Forfor won from Dunfermline
        
        for i in range(n): 
          pzl[i][i] = 0    # don't calculate x against x
       
        # solve which games have been played
        sol = solve(n, n-1, pzl)
        
        # print table
        print(f"\nnumber of teams: {n} \n")
        for s in sol: 
          print("   " + "  ".join(list(LETTERS[:n])))   # column header
          for i in range(len(s)):
            r = " " + "  ".join(str(x) if k != i else "-" 
                                for k, x in enumerate(s[i]))
            print(LETTERS[:n][i], r)   # row qualifier
          
          print("\nElgin's results:", 
                " ".join([LDW[x] for k, x in enumerate(s[4]) if k != 4]))  
         
      # teams  games  draws  points max    high     reject reason
      # 7      21     5      58     18     17       high = max - 1
      # 8      28     7      77     21     19
      # 9      36     8      100    24     23       high = max - 1
      # 10     45     6      129    27     29       high > max
      # 11     55     5      160    30     31       high > max
      # 12     66     1      197    33     37       high > max
      # 13     78     -4     238    36     41       high > max
      # 14     91     -8     281    39     43       high > max
      # 15     105    -13    328    42     47       high > max
      # 16     120    -21    381    45     53       high > max
      # 17     136    -32    440    48     59       high > max
      # 18     153    -42    501    51     61       high > max
      # 19     171    -55    568    54     67       high > max
      # 20     190    -69    639    57     71       high > max
      # 21     210    -82    712    60     73       high > max
      # 22     231    -98    791    63     79       high > max
      # 23     253    -115   874    66     83       high > max
      # 24     276    -135   963    69     89       high > max
      # 25     300    -160   1060   72     97       high > max
      # 26     325    -186   1161   75     101      high > max
      #
      # number of teams: 8
      #
      #    A  B  C  D  E  F  G  H
      # A  -  1  3  3  3  3  3  3
      # B  1  -  3  1  3  3  3  3
      # C  0  0  -  1  3  3  3  3
      # D  0  1  1  -  3  0  3  3
      # E  0  0  0  0  -  3  1  3
      # F  0  0  0  3  0  -  1  1
      # G  0  0  0  0  1  1  -  1
      # H  0  0  0  0  0  1  1  -
      # 
      # Elgin's results: L L L L W D W
      

      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