Design a site like this with WordPress.com
Get started

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

  • 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 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.

      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)
      
      @cache
      # check if <n> teams, each played <k> games is orderable
      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 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 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 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 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 11:34 pm on 9 January 2023 Permalink | Reply

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

              Like

    • 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

  • 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 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
      
      @cache
      # check if <n> teams, each played <k> games is orderable
      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 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 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 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 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 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 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 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 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

  • 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 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, nsplit, seq_all_different as all_different, ordered, printf)
      
      # consider V = the number of towns, it is prime
      for V in primes.irange(3, 1000):
        dsV = nsplit(V)
        if not all_different(dsV): continue
      
        # consider A = the number of enclosed areas, it is also prime
        for A in primes.irange(5, 2 * V - 5):
          dsA = nsplit(A)
          if not all_different(dsV + dsA): continue
      
          # calculate E = the number of roads
          E = V + A - 1
          if E > 3 * V - 6: continue
          dsE = nsplit(E)
          ds = dsV + dsA + dsE
          if not (len(ds) == 10 and all_different(ds)): 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 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 (s, ans) in p.solve(verbose=0):
            printf("{ans}")
        

        Like

    • 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 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 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

  • 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]

    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 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 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 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 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

  • 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 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 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

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

    Teaser 2508 

    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.

    [teaser2508]

     
    • 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

  • 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]

    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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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

  • 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 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 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

  • Jim Randell 4:44 pm on 16 October 2020 Permalink | Reply
    Tags: by: John Owen   

    Teaser 3030: Pot success 

    From The Sunday Times, 18th October 2020 [link]

    In snooker, pot success (PS) is the percentage of how many pot attempts have been successful in that match (e.g. 19 pots from 40 attempts gives a PS of 47.5%). In a recent match, my PS was a whole number at one point. I then potted several balls in a row to finish a frame, after which my improved PS was still a whole number. At the beginning of the next frame, I potted the same number of balls in a row, and my PS was still a whole number. I missed the next pot, my last shot in the match, and, remarkably, my PS was still a whole number.

    If I told you how many balls I potted during the match, you would be able to work out those various whole-number PS values.

    How many balls did I pot?

    [teaser3030]

     
    • Jim Randell 5:03 pm on 16 October 2020 Permalink | Reply

      This Python program runs in 46ms.

      Run: [ @repl.it ]

      from enigma import irange, div, peek, printf
      
      # calculate PS
      PS = lambda p, t: div(100 * p, t)
      
      # generate scenarios with p balls potted (at the end)
      def generate(p):
        # consider total number of attempts (at the end)
        for t in irange(p + 1, 100):
          # final PS (ps4)
          ps4 = PS(p, t)
          if ps4 is None: continue
          # last shot was a miss, and the PS before it (ps3)
          ps3 = PS(p, t - 1)
          if ps3 is None: continue
          # before that 2 lots of k balls were potted
          for k in irange(2, (p - 1) // 2):
            ps2 = PS(p - k, t - 1 - k)
            if ps2 is None: continue
            ps1 = PS(p - 2 * k, t - 1 - 2 * k)
            if ps1 is None or not(ps1 < ps2): continue
            # return (t, k, PS) values
            yield (t, k, (ps1, ps2, ps3, ps4))
      
      # consider number of balls potted (at the end)
      for p in irange(5, 99):
        # accumulate ps values
        s = set(ps for (t, k, ps) in generate(p))
        # is there only one?
        if len(s) == 1:
          # output solution
          printf("balls potted = {p} -> PS = {ps}", ps=peek(s))
      

      Solution: You potted 13 balls.

      This corresponds to the following scenario:

      13 balls potted (2 runs of 5), PS = (3/15 = 20%; 8/20 = 40%; 13/25 = 52%; 13/26 = 50%)

      The other possible scenarios are:

      12 balls potted (2 runs of 5), PS = (2/5 = 40%; 7/10 = 70%; 12/15 = 80%; 12/16 = 75%)
      12 balls potted (2 runs of 4), PS = (4/16 = 25%; 8/20 = 40%; 12/24 = 50%; 12/25 = 48%)

      57 balls potted (2 runs of 15), PS = (27/45 = 60%; 42/60 = 70%; 57/75 = 76%; 57/76 = 75%)
      57 balls potted (2 runs of 25), PS = (7/28 = 25%; 32/50 = 64%; 57/75 = 76%; 57/76 = 75%)

      It seems plausible that these could correspond to a snooker match (it is possible to pot 10 reds + 10 colours + 6 colours = 26 balls in one frame, and we know at least 2 frames are involved). Although if just one of them did not, then the other scenario would provide a further solution.

      The program ensures that the PS values we are considering are non-zero, but allowing the initial PS to be zero gives a further solution:

      18 balls potted (2 runs of 9), PS = (0/6 = 0%; 9/15 = 60%; 18/24 = 75%; 18/25 = 72%)

      Like

    • Frits 11:06 am on 17 October 2020 Permalink | Reply

      @Jim, I think you should also consider p=4 as ps1 might be zero and zero also is a whole number .

      Also if t would be (p + 1) then ps1, ps2 and ps3 would be 100 and ps2 would not be higher than ps1.
      If you start t from (p+ 2) you don’t have to code the ps1 < ps2 check as it will always be the case.

      Of course there always is a balance between efficiency and seeing right away that the code solves the requirements.

      Like

      • Jim Randell 11:50 am on 17 October 2020 Permalink | Reply

        @Frits: Unfortunately the term “whole number” isn’t precise. It can be used to mean the integers, the non-negative integers, or just the positive integers.

        For this puzzle I took it to be the positive integers (which gets around a possible problem when considering PS values of 0), so I didn’t have to consider PS values of zero. Which is probably what the setter intended, as I’m sure the puzzle is meant to have a unique solution.

        I also wanted to make the [[ ps1 < ps2 ]] condition explicit in the code (as without it there would be further solutions – which can be seen by removing the test).

        Like

    • Frits 1:28 pm on 17 October 2020 Permalink | Reply

      Assuming whole numbers are in the range (1, …, 100) and with the “improved PS” check (which is not needed if we use “AB < CD").

      If we include zero as a whole number there are 2 solutions.

      from enigma import  SubstitutedExpression, multiset
      
      r = multiset()
      
      p = SubstitutedExpression([
          # we start with AB balls potted from CD attempts
          "AB <= CD",
          "CD > 0",
          # "I then potted several balls (XY > 1) in a row"
          # Assume CD + 2 * XY + 1 is roughly less than 100
          "XY > 1",
          "XY < (99 - CD) // 2",
           # the 4 pot successes being whole numbers (meaning 1..100 ???)
          "div(100 * AB, CD) > 0",
          "div(100 * (AB + XY), CD + XY) > 0",
          "div(100 * (AB + 2 * XY), CD + 2 * XY) > 0",
          "div(100 * (AB + 2 * XY), CD + 2 * XY + 1) > 0",
          # improved PS
          "div(100 * (AB + XY), CD + XY) > div(100 * AB, CD)",
          ],
          verbose=0,
          d2i={},
          answer="AB + 2 * XY, AB, CD, XY, " 
                 "(100 * AB / CD, 100 * (AB + XY) / (CD + XY),"
                 " 100 * (AB + 2 * XY) / (CD + 2 * XY),"
                 " 100 * (AB + 2 * XY) / (CD + 2 * XY + 1))",
          distinct="",
      )
      
      # Solve and print answers
      
      print("potted   start  several     pot success" )
      for (_, ans) in p.solve():
        print(f" {ans[0]:>2}     {str(ans[1:3]):<9}  {str(ans[3]):<3}  {ans[4]}")
        r.add(ans[0])
      
      for (k, v) in r.items():
        if v == 1:
          print(f"\n{k} balls potted")
      

      Like

  • Jim Randell 8:11 am on 2 June 2020 Permalink | Reply
    Tags: by: John Owen   

    Teaser 2566: A fulfilling strategy 

    From The Sunday Times, 27th November 2011 [link]

    I drove down a road with a number of petrol stations whose locations I saw on my map. I decided to check the price at the first station then fill up when I found one offering a lower price (or, failing that, the last one).

    When I got home I noticed that I could arrange the prices (in pence per litre) into an ascending sequence of consecutive whole numbers of pence, plus 0.9p (i.e. 130.9p, 131.9p, 132.2p, etc). I also worked out the average price that I would expect to pay using this strategy, if I were to encounter this set of prices in an unknown order, and I was surprised to find that this value turned out to be a whole number of pence per litre.

    How many petrol stations were there?

    When the puzzle was originally published in The Sunday Times it had been edited into a form that meant there were no solutions. Here I have rephrased the middle paragraph so that it works as the setter originally intended.

    [teaser2566]

     
    • Jim Randell 8:12 am on 2 June 2020 Permalink | Reply

      (See also: Teaser 2988).

      Here is a program that calculates the result directly. It runs in 50ms.

      Run: [ @repl.it ]

      from enigma import subsets, irange, inf, factorial, div, printf
      
      # strategy, take the first amount lower than the first n items
      def strategy(s, n):
        t = min(s[:n])
        for x in s[n:]:
          if x < t: break
        return x
      
      # play the game with k items
      def play(k):
        # collect total amount
        t = 0
        # consider possible orderings of the items
        ps = list(1299 + 10 * p for p in irange(1, k))
        for s in subsets(ps, size=k, select="P"):
          t += strategy(s, 1)
        return t
      
      # consider numbers of items
      for k in irange(2, inf):
        t = play(k)
        # calculate the average expected price (in 10th pence)
        d = factorial(k)
        p = div(t, d)
        if p is not None and p % 10 == 0:
          printf("k={k} -> p={p}")
          break
      

      Solution: There were 5 petrol stations.

      And the expected average fuel price was 132.0 pence.

      It doesn’t actually matter what the prices actually are, all the petrol stations could adjust their prices by the same whole number of pence, and the expected average price would be adjusted by the same amount.


      Analytically:

      As determined in Teaser 2988 we can use the formula:

      S(n, k) = ((2n + 1)k − n(n + 1)) (k + 1) / 2(n + 1)k

      To determine the mean expected value of choosing from k boxes with values from 1..k, using the strategy of picking the next box that is better than any of the first n boxes (or the last box if there are no boxes better than the first).

      In this case n = 1:

      S(1, k) = (3k − 2) (k + 1) / 4k

      If we award ourselves a prize of value k for selecting the cheapest fuel, and a prize of value 1 for selecting the most expensive fuel, then we have the same situation as in Teaser 2988, and if p is expected average prize value, then the corresponding expected average fuel price is (130.9 + k − p).

      And k is an integer, so in order to make the expected average fuel price a whole number of pence we are looking for expected average prize value that is an integer plus 0.9.

      i.e. when the value of 10 S(1, k) is an integer with a residue of 9 modulo 10.

      10 S(1, k) = (15k + 5) / 2 − (5 / k)

      When k is odd, the first part gives us a whole number, so we would also need the (5 / k) part to give a whole number. i.e. k = 1, 5.

      When k is even, the first part gives us an odd number of halves, so we also need (5 / k) to give an odd number of halves. i.e. k = 2, 10.

      And we are only interested in values of k > 1, so there are just 3 values to check:

      k = 5: 10 S(1, k) = 39
      k = 2: 10 S(1, k) = 15
      k = 10: 10 S(1, k) = 77

      The only value for k that gives a residue of 9 modulo 10 is k = 5.

      And in this case our expected average prize is p = 3.9 so our expected average fuel price is 132.0 pence.

      Like

  • Jim Randell 9:44 pm on 29 May 2020 Permalink | Reply
    Tags: by: John Owen   

    Teaser 3010: Putting game 

    From The Sunday Times, 31st May 2020 [link]

    A putting game has a board with eight rectangular holes, like the example (not to scale), but with the holes in a different order.

    If you hit your ball (diameter 4cm) through a hole without touching the sides, you score the number of points above that hole. The sum of score and width (in cm) for each hole is 15; there are 2cm gaps between holes.

    I know that if I aim at a point on the board, then the ball’s centre will arrive at the board within 12cm of my point of aim, and is equally likely to arrive at any point in that range. Therefore, I aim at the one point that maximises my long-term average score. This point is the centre of a hole and my average score is a whole number.

    (a) Which hole do I aim at?

    (b) Which two holes are either side of it?

    [teaser3010]

     
    • Jim Randell 9:23 am on 30 May 2020 Permalink | Reply

      The 4cm diameter ball is not allowed to touch the sides of the hole, so we can consider the outside 2cm of each hole to be “out of bounds”. Which is the same as if the ball was a point, the gaps between holes are extended 2cm in each direction (so they become 6cm wide), and each hole is reduced by a corresponding 2cm on either edge.

      To be sure I satisfy all the conditions this Python program constructs all possible orderings for the holes, and then for each ordering looks at possible target positions. It looks for orderings that have a unique maximum targeting point that is at the centre of a hole, and that yields an integer average score per shot. Once an ordering passes these tests we record the hole that the target is in, along with the two holes on either side. This gives a unique target + left/right value (although there are many orderings that contain the three holes appropriately positioned).

      It runs in 1.58s, but I think this could be improved with some additional analysis.

      from enigma import irange, subsets, multiset, ordered, printf
      
      # available holes (points)
      holes = [ 1, 2, 3, 4, 5, 6, 7, 8 ]
      
      # layout for a sequence of holes
      # return a list of: (region size (in mm), points scored) pairs
      def layout(ps):
        for (i, p) in enumerate(ps):
          if i > 0: yield (60, 0) # gap between holes
          yield (110 - 10 * p, p) # hole size
      
      # generate intervals ((a, b), p) from a layout
      # where a, b are absolute distances, p is number of points scored
      def intervals(ss):
        a = b = 0
        for (d, p) in ss:
          if b == 0:
            (a, b) = (0, d)
          else:
            (a, b) = (b, b + d)
          yield ((a, b), p)
      
      # analyse the layout (working in 5mm steps)
      # return list of (d, (v, r)) values, where:
      # d = absolute target distance
      # v + r/240 = max average score
      def analyse(ss):
        # determine total length
        t = sum(d for (d, _) in ss)
        rs = list()
        # consider target positions (in 5mm steps)
        for x in irange(120, t - 120, step=5):
          # consider each zone
          r = 0
          for ((a, b), p) in intervals(ss):
            # overlap?
            if b < x - 120: continue
            if a > x + 120: break
            d = min(x + 120, b) - max(x - 120, a)
            r += p * d
          rs.append((x, r))
        # find maximum average value
        m = max(r for (_, r) in rs)
        return list((x, divmod(r, 240)) for (x, r) in rs if r == m)
      
      # collect results
      m = multiset()
      
      # choose an order for the holes
      for ps in subsets(holes, size=len, select="P"):
        # but ignore the order in the diagram
        if ps == (6, 3, 8, 7, 2, 5, 1, 4): continue
        # construct the sequence of (regions, points)
        ss = list(layout(ps))
        # analyse it
        rs = analyse(ss)
        # there should only be one max position
        if len(rs) != 1: continue
        (x, (v, r)) = rs[0]
        # and the average score should be an integer
        if r != 0: continue
        # find the interval x is in
        for ((a, b), p) in intervals(ss):
          # and check it is centred
          if p > 0 and a < x < b and b - x == x - a:
            # find the holes on either side
            i = ps.index(p)
            z = ps[i - 1:i + 2]
            printf("[{ps} -> target = {x} mm, avg pts = {v}; segment = {z}]")
            m.add((p, ordered(ps[i - 1], ps[i + 1])))
      
      # output solution
      for ((x, (l, r)), n) in m.most_common():
        printf("centre = {x}, left/right = {l}/{r} [{n} solutions]")
      

      Solution: (a) You should aim at the centre of the 5 point hole. (b) The 6 point and 8 point holes are either side of the 5 point hole.

      Here is a diagram of the arrangement:

      The “out of bounds” areas are indicated in red, and we score zero points if the centre of the ball lands in these.

      In the 24cm section centred on the 5 point hole we see that there is a 3cm zone where we can score 6 points, a 6cm zone where we can score 5 points, and a 3cm zone where we can score 8 points.

      The average expected score is thus: (6×3 + 5×6 + 8×3) / 24 = 72 / 24 = 3.

      Like

      • Jim Randell 6:28 pm on 30 May 2020 Permalink | Reply

        Here is the program adapted to just consider the centre + left/right values. It finds there is only one segment that must appear in any solution (or its reverse), and this gives the required answer. It runs in 54ms.

        Run: [ @repl.it ]

        from enigma import irange, subsets, peek, printf
        
        # available holes (points)
        holes = [ 1, 2, 3, 4, 5, 6, 7, 8 ]
        
        # layout for a sequence of holes (in mm)
        # return a list of: (region size, points scored) pairs
        def layout(ps):
          for (i, p) in enumerate(ps):
            if i > 0: yield (60, 0) # gap between holes
            yield (110 - 10 * p, p) # hole
        
        # generate intervals ((a, b), p) from a layout
        # where a, b are absolute distances, p is the number of points scored
        def intervals(ss):
          a = b = 0
          for (d, p) in ss:
            if b == 0:
              (a, b) = (0, d)
            else:
              (a, b) = (b, b + d)
            yield ((a, b), p)
        
        # analyse the layout (working in 5mm steps)
        # return list of (d, (v, r)) values, where:
        # d = absolute target distance
        # v + r/240 = max average score
        def analyse(ss):
          # determine total length
          t = sum(d for (d, _) in ss)
          rs = list()
          # consider target positions (in 5mm steps)
          for x in irange(120, t - 120, step=5):
            # consider each zone
            r = 0
            for ((a, b), p) in intervals(ss):
              # overlap?
              if b < x - 120: continue
              if a > x + 120: break
              d = min(x + 120, b) - max(x - 120, a)
              r += p * d
            rs.append((x, r))
          # find maximum average value
          m = max(r for (_, r) in rs)
          return list((x, divmod(r, 240)) for (x, r) in rs if r == m)
        
        # find triples with integer scores max average scores at the centre of the centre hole
        
        # choose the centre hole and left/right holes
        for (X, L, R) in subsets(holes, size=3, select="P"):
          if not(L < R): continue
          # create the layout
          ss = list(layout((L, X, R)))
          # analyse it
          rs = analyse(ss)
          # there should be only one max position
          if len(rs) != 1: continue
          (x, (v, r)) = rs[0]
          # and the max average score should be an integer
          if r != 0: continue
          # and it should be centred on X
          ((a, b), _) = peek(intervals(ss), 2)
          if a < x < b and b - x == x - a:
            printf("segment = ({L}, {X}, {R}) -> target = {x} mm, avg pts = {v}")
        

        I suppose really I should demonstrate that we can construct an ordering containing the required segment that satisfies all the requirements, but as my first program finds lots I don’t think it is necessary.

        Like

    • Robert Brown 10:02 am on 30 May 2020 Permalink | Reply

      If the middle & adjacent slots are too small, the ±12 cm range goes into the next slot, which is undefined. This reduces the solution space and quickly leads to what appears to be a unique result. But if you reduce the smaller adjacent slot by 1 and increase the other one, it still works. This would be valid if the smaller slot was the first one on the board, so a possible duplicate result?

      Like

      • Jim Randell 1:11 pm on 30 May 2020 Permalink | Reply

        @Robert: I don’t think it is possible for the target area to extend beyond the centre hole and the holes on either side. The smallest holes are 7cm and 8cm and the distance from the centre of one to the edge of the other is always greater than 12cm, so I think we only need to consider centre + left/right configurations. (Which I’m looking at to give a more efficient program).

        Like

    • Robert Brown 10:52 am on 30 May 2020 Permalink | Reply

      Further to above. The ‘not to scale’ drawing masks the fact that low value slots are quite wide. I assume there are 8 values as per the drawing, with corresponding slot widths.
      So there is a solution where the mid value is low, and the adjacent values can take one of two different pairs (they have the same sum), and where the total length measured from the centre of the mid slot is > 12 in each case. Definitely two sets of results, doesn’t matter where they are on the board. Maybe I’m missing something?

      Like

    • Robert Brown 12:17 pm on 30 May 2020 Permalink | Reply

      This is not a good place to have a conversation. You have my email address, but I don’t have yours!
      Both of the above sets of results work, but each post has typos which I cannot correct. An in depth exploration reveals 5 different solutions, all with 3 different L M R values between 1 & 8, and with average values of 3, 4 or 5. In each case the minimum distance from the centre of the middle value (where he aims for) is at least 15.5 cm before going into the next (unknown) slot, plenty of room for the 2cm radius ball to have it’s centre up to 12 cm from that centre. So no need for any of the slots to be the first one on the board.

      Like

      • Jim Randell 6:55 pm on 1 June 2020 Permalink | Reply

        @Robert: It’s a limitation of WordPress.com I’m afraid, but if there are any corrections you would like to make, just post a followup comment, and I will use it to correct errors in the original.

        Like

  • Jim Randell 4:27 pm on 17 April 2020 Permalink | Reply
    Tags: by: John Owen   

    Teaser 3004: Going up 

    From The Sunday Times, 19th April 2020 [link]

    In our football league, the teams all play each other once, with three points for a win and one for a draw. At the end of the season, the two teams with most points are promoted, goal difference being used to separate teams with the same number of points.

    Last season’s climax was exciting. With just two games left for each team, there were several teams tied at the top of the league with the same number of points. One of them, but only one, could be certain of promotion if they won their two games. If there had been any more teams on the same number of points, then none could have guaranteed promotion with two wins.

    How many teams were tied at the top of the league, and how many of the remaining matches involved any of those teams?

    [teaser3004]

     
    • Jim Randell 9:33 am on 18 April 2020 Permalink | Reply

      I supposed there were several teams, A, B, C, …, tied at the top. And we are looking for situations where team A is looking at a guaranteed promotion, if they win both their games.

      Obviously any of the other teams tied at the top of the table would also be in with a chance of promotion if they win both their games (as they will have the same maximum number of points as A).

      But if one of the teams were to win a match by an enormous number of goals, it would give them an unassailable goal difference. So A can only be guaranteed a win if there are fewer than three teams tied at the top after the games are played (so the goal difference rule doesn’t come into it).

      So we need to look at numbers of teams, such that there is an arrangement of remaining matches, where A (and only A) is guaranteed a promotion if they win both their matches, but if there were one more team then there would be no such arrangement of matches.

      This Python program is a bit slow (it takes 8.9s), but it does find what seems to be a reasonable answer. I may see if I can come up with a more efficient program later.

      from enigma import (cproduct, multiset, irange, join, printf)
      
      # generate matches for teams <ts> tied at the top
      # ts = teams tied at the top
      # ss = number of matches to be played by teams in <ts>
      # team Z is used to denote any other team not in <ts>
      def matches(ts, ss, ms=[]):
        # are we done?
        if not ss:
          yield ms
        else:
          # choose a team
          ks = sorted(ss.keys())
          t = ks.pop(0)
          # choose an opponent
          ks.append('Z')
          for x in ks:
            m = (t, x)
            if x == 'Z' or not (ms and m < ms[-1]):
              yield from matches(ts, ss.difference(m), ms + [m])
      
      # find teams that can be guaranteed promotion
      # ts = teams tied at the top
      # ms = remaining matches
      def solve(ts, ms):
        # find wins where 2 wins guarantees A a place in the top 2
        (inc, exc) = (set(), set())
        # choose winning teams for each match
        for wins in cproduct(ms):
          # collect teams with 2 wins
          m = multiset.from_seq(wins)
          ws = list(t for (t, n) in m.items() if n == 2 and t != 'Z')
          if len(ws) < 3:
            # a guaranteed win
            inc.update(ws)
          else:
            # not a guaranteed win
            exc.update(ws)
            if exc.issuperset(ts): return set()
        # return those teams that are guaranteed a win in all situations
        return inc.difference(exc)
      
      # format a sequence of matches
      fmt = lambda ms: join((x + "v" + y for (x, y) in ms), sep=", ", enc="()")
      
      # consider teams labelled A, B, C, ... (Z is used to denote "other" teams)
      # record teams where there is a set of matches that guarantees only team A a promotion
      r = dict()
      for n in irange(2, 25):
        teams = "ABCDEFGHIJKLMNOPQRSTUVWXY"[:n]
        ss = multiset.from_seq(teams * 2)
        for ms in matches(teams, ss):
          # does this set of matches guarantee a promotion for only A?
          ws = solve(teams, ms)
          if len(ws) == 1 and 'A' in ws:
            printf("n={n}: {ms} -> {ws}", ms=fmt(ms), ws=join(sorted(ws)))
            r[n] = ms
            break # we only need one set of matches
        if n not in r:
          printf("n={n}: <none>")
          # are we done?
          k = n - 1
          if k in r:
            ms = r[k]
            printf("{k} -> {ms}; {m} matches", m=len(ms), ms=fmt(ms))
            break
      

      Solution: There are 6 teams tied at the top. 7 of the remaining matches involve at least one of those teams.


      For six teams at the top:

      If A plays B and C and wins both matches, then neither B nor C can achieve the maximum number of points, so they are out of contention.

      And there are three more teams at the top, D, E, F, and they all play each other, then only one of them can achieve 2 wins, to tie with A at the top of the table.

      So A is guaranteed to finish in the top 2 if they win both their games, and get promotion.

      Introducing a seventh team, G, would mean that a third team could get two wins, so A‘s promotion would not be guaranteed.

      Like

  • Jim Randell 4:25 pm on 27 December 2019 Permalink | Reply
    Tags: by: John Owen   

    Teaser 2988: Open the box 

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

    Game show contestants are shown a row of boxes, each containing a different sum of money, increasing in regular amounts (eg, £1100, £1200, £1300, …), but they don’t know the smallest amount or the order. They open one box then take the money, or decline that and open another box (giving them the same choices, apart from opening the last box when they have to take the money).

    Alf always opens boxes until he finds, if possible, a sum of money larger than the first amount. Bert’s strategy is similar, except he opens boxes until he finds, if possible, a sum of money larger than both of the first two amounts. Remarkably, they can both expect to win exactly the same amount on average.

    How many boxes are there in the game?

    [teaser2988]

     
    • Jim Randell 4:37 pm on 27 December 2019 Permalink | Reply

      With k boxes, we always win a base amount, along with some multiple of the increment. So we can just consider the boxes to take on the values from 1 to k.

      This Python program considers increasing numbers of boxes, looking at the total winnings for A and B for all possible arrangements of boxes. Until it finds two totals with the same value. It runs in 75ms.

      Run: [ @repl.it ]

      from enigma import subsets, irange, inf, printf
      
      # strategy, take the first amount larger than the first n boxes
      def strategy(s, n):
        t = max(s[:n])
        for x in s[n:]:
          if x > t: break
        return x
      
      # strategies for A and B
      A = lambda s: strategy(s, 1)
      B = lambda s: strategy(s, 2)
      
      # play the game with k boxes
      def play(k):
        # collect total winnings for A and B
        tA = tB = 0
        # consider possible orderings of the boxes
        for s in subsets(irange(1, k), size=k, select="P"):
          tA += A(s)
          tB += B(s)
        return (tA, tB)
      
      for k in irange(3, inf):
        (tA, tB) = play(k)
        if tA != tB: continue
        printf("{k} boxes")
        break
      

      Solution: There are 6 boxes.

      For 3 to 5 boxes A’s strategy is better than B’s. When there are more than 6 boxes B’s strategy is better.

      Using prizes with values from 1..k I found that the average winnings for A and B are:

      k=3: A = 2.333; B = 2.000
      k=4: A = 3.125; B = 2.917
      k=5: A = 3.900; B = 3.800
      k=6: A = 4.667; B = 4.667
      k=7: A = 5.429; B = 5.524
      k=8: A = 6.188; B = 6.375
      k=9: A = 6.944; B = 7.222
      k=10: A = 7.700; B = 8.067
      k=11: A = 8.455; B = 8.909
      k=12: A = 9.208; B = 9.750

      In general we have:

      A(k) = (3k − 2) (k + 1) / 4k
      B(k) = (5k − 6) (k + 1) / 6k

      So, as k increases the ratio of A’s average approaches 3/4 (= 75.0%) of the maximum available prize. And the ratio of B’s average approaches 5/6 (= 83.3%) of the maximum prize.

      From the equations we see that the average winnings are the same when:

      (3k − 2)(k + 1) / 4k = (5k − 6)(k + 1) / 6k
      3(3k − 2) = 2(5k − 6)
      9k − 6 = 10k − 12
      k = 6 (for k > 2)


      In general a strategy of looking at n values and then taking the next highest value gives average winnings from k boxes according to the following formula:

      S(n, k) = ((2n + 1)k² − (n² − n − 1)k − (n² + n)) / (2n + 2)k
      S(n, k) = ((2n + 1)k − n(n + 1)) (k + 1) / 2(n + 1)k

      So: A(k) = S(1, k) and B(k) = S(2, k).

      Like

  • Jim Randell 4:32 pm on 1 November 2019 Permalink | Reply
    Tags: by: John Owen,   

    Teaser 2980: Egyptian weights and measures 

    From The Sunday Times, 3rd November 2019 [link]

    We were wondering why ancient Egyptians chose to represent arbitrary fractions as sums of distinct unit fractions of the form 1/n (thus 5/7 = 1/2 + 1/5 + 1/70). One of us recalled long ago watching our greengrocer use four brass weights of 1/2, 1/4, 1/8, 1/16 lb to weigh any number of ounces up to 15 by stacking some of them on one side of her balancing scales. We wanted to make a metric equivalent, a set of distinct weights of unit fractions of a kilo, each weighing a whole number of grams, to weigh in 10g steps up to 990g.

    Naturally, we wanted to use as little brass as possible, but we found that there were several possible such sets. Of these, we chose the set containing the fewest weights.

    List, in increasing order, the weights in our set.

    [teaser2980]

     
    • Jim Randell 5:03 pm on 1 November 2019 Permalink | Reply

      Possible weights are the divisors of 1000.

      This Python program looks for subsets that permit all the required weights to be made, and then selects those sets with the minimal possible weight. It runs in 501ms.

      Run: [ @repl.it ]

      from enigma import divisors, inf, subsets, printf
      
      # find weights that are unit fractions of 1000
      weights = divisors(1000)
      weights.remove(1000)
      
      # find minimal weight sets of weights that can be used to weigh all
      # multiples of 10 from 10 to 990
      (w, rs) = (inf, list())
      
      # choose a set of weights
      for ws in subsets(weights, min_size=7):
        k = sum(ws)
        if k < 990 or k > w: continue
      
        # collect amounts
        amounts = set()
        # choose a subset of the weights to use
        for s in subsets(ws, min_size=1):
          # calculate the total weight
          t = sum(s)
          # is it a multiple of 10 between 10 and 990?
          if 9 < t < 991 and t % 10 == 0:
            amounts.add(t)
      
        # can we make 99 different amounts?
        if len(amounts) == 99:
          if k < w: (w, rs) = (k, list())
          rs.append(ws)
          printf("[{k} = {ws} ({n})]", n=len(ws))
      
      # and find the minimum number weights in the set
      n = min(len(ws) for ws in rs)
      
      # output solutions
      for ws in rs:
        if len(ws) == n:
          printf("min = {w}; set of {n} weights = {ws}")
      

      Solution: There are 10 weights in the set: 2g, 5g, 8g, 10g, 25g, 40g, 50g, 100g, 250g, 500g.

      The total weight of the set is 990g (which is obviously the minimum possible total to be able to weigh up to 990g).

      There are 4 viable sets of weights that have a total weight of 990g:

      set of 10 weights = (2, 5, 8, 10, 25, 40, 50, 100, 250, 500)
      set of 11 weights = (1, 2, 4, 8, 10, 25, 40, 50, 100, 250, 500)
      set of 12 weights = (1, 2, 4, 5, 8, 10, 20, 40, 50, 100, 250, 500)
      set of 13 weights = (1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 125, 200, 500)

      When I initially read the puzzle I solved it allowing weights to be placed on both sides of the scales, and I found two sets of 7 weights which can be used to achieve the required values, where both sets weigh 990g in total:

      set of 7 weights = (5, 20, 40, 50, 125, 250, 500)
      set of 7 weights = (5, 20, 40, 100, 125, 200, 500)

      Like

  • Jim Randell 10:38 am on 27 August 2019 Permalink | Reply
    Tags: by: John Owen   

    Brainteaser 1661: Goals galore 

    From The Sunday Times, 10th July 1994 [link]

    Three football teams played each other once in a tournament. Athletic beat City, City beat Borough, and Borough beat Athletic.

    They could not decide which team should receive the trophy since:

    Athletic had scored the most goals;

    Borough had the best goal average (goals for ÷ goals against)

    City had the best goal difference (goals for − goals against)

    Fewer than 40 goals were scored in the tournament.

    What were the scores in the three games?

    This puzzle was included in the book Brainteasers (2002, edited by Victor Bryant). The puzzle text above is taken from the book.

    [teaser1661]

     
    • Jim Randell 10:39 am on 27 August 2019 Permalink | Reply

      There are six bounded variables (the number of goals scored by each team in each of the three matches), and the conditions put further constraints on the variables.

      I used the MiniZinc system to solve the set of constraints, and the minizinc.py library to construct the constraints using Python.

      This Python 3 program runs in 228ms.

      from minizinc import MiniZinc, var
      from enigma import join
      
      # teams
      (A, B, C) = teams = list('ABC')
      
      # decision variables: XY = goals for X against Y in X vs Y match
      vs = "AB BA AC CA BC CB"
      
      # goals for / against team x
      gf = lambda x: "(" + join((x + t for t in teams if t != x), sep=' + ') + ")"
      ga = lambda x: "(" + join((t + x for t in teams if t != x), sep=' + ') + ")"
      
      model = f"""
      
        % declare the variables
        {var('0..39', vs.split())};
      
        % the match outcomes
        constraint BA > AB; % B beat A
        constraint AC > CA; % A beat C
        constraint CB > BC; % C beat B
      
        % A scored the most goals
        constraint {gf(A)} > {gf(B)};
        constraint {gf(A)} > {gf(C)};
      
        % B had the best goal average
        constraint {gf(B)} * {ga(A)} > {gf(A)} * {ga(B)};
        constraint {gf(B)} * {ga(C)} > {gf(C)} * {ga(B)};
      
        % C had the best goal difference
        constraint {gf(C)} - {ga(C)} > {gf(A)} - {ga(A)};
        constraint {gf(C)} - {ga(C)} > {gf(B)} - {ga(B)};
      
        % fewer than 40 goals were scored in the tournament
        constraint AB + BA + AC + CA + BC + CB < 40;
      
        solve satisfy;
      """
      
      # create the model
      m = MiniZinc(model)
      
      # solve the constraints
      for (AB, BA, AC, CA, BC, CB) in m.solve(result=vs):
        print(f"A vs B = {AB}-{BA}; A vs C = {AC}-{CA}; B vs C = {BC}-{CB}")
      

      Solution: The scores in the matches are: A vs B = 3-7; A vs C = 13-12; B vs C = 0-3.

      In total there were 38 goals scored in the tournament.

      The different measures are:

      goals scored: A = 16, C = 15, B = 7
      goal average: B = 1.17, C = 1.15, A = 0.84
      goal difference: C = +2, B = +1, A = −3

      Like

    • GeoffR 3:37 pm on 28 August 2019 Permalink | Reply

      Minizinc found two solutions for me, the first solution looks incorrect as the averages for B and C were the same(7/6 and 14/12, which does not agree with my constraint for goal averages.

      The second solution is a correct solution and agrees with the published solution.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % Teams A, B and C goal scores
      % eg AB = goals for Team A playing Team B
      % and BA = goals against Team A playing Team B
      var 0..39:AB; var 0..39:BA;  
      var 0..39:AC; var 0..39:CA; 
      var 0..39:BC; var 0..39:CB; 
      
      % goals for and against Teams A, B and C
      var 0..39:gfA; var 0..39:gfB; var 0..39:gfC; 
      var 0..39:gaA; var 0..39:gaB; var 0..39:gaC; 
      
      % goal difference variables
      var -10..39: gdifA; 
      var -10..39: gdifB; 
      var -10..39: gdifC; 
      
      % goal average variables
      var 0.01..10.1: gavA; 
      var 0.01..10.1: gavB; 
      var 0.01..10.1: gavC;
      
      % total of all goals < 40
      constraint AB + BA + AC + CA + BC + CB < 40;
      
      % Team B beat Team A, Team A beat TeamC and Team C beat Team B
      constraint BA > AB; 
      constraint AC > CA; 
      constraint CB > BC; 
      
      % Goals for Teams A, B and C
      constraint gfA = AB + AC;
      constraint gfB = BA + BC;
      constraint gfC = CA + CB;
      
      % goals against Teams A, B and C
      constraint gaA = BA + CA;
      constraint gaB = AB + CB;
      constraint gaC = AC + BC;
      
      % A had the most goals of Teams A, B and C
      constraint (AC + AB) > (BA + BC) /\ (AC + AB) > (CA + CB);
      
      % C had the highest goal difference
      constraint gdifA = AB + AC - BA - CA;
      constraint gdifB = BA + BC - AB - CB;
      constraint gdifC = CA + CB - AC - BC;
      
      constraint gdifC > gdifA /\ gdifC > gdifB;
      
      % B had the best goal average
      constraint gavA = (AB + AC) / (BA + CA);
      constraint gavB = (BA + BC) / (AB + CB);
      constraint gavC = (CA + CB) / (AC + BC);
      
      constraint gavB > gavC /\ gavB > gavA;
      
      solve satisfy;
      
      % show team scores in the three games
      output [   "A v B = " ++ show(AB) ++ "-" ++ show(BA)
      ++ "\n" ++ "A v C = " ++ show(AC) ++ "-" ++ show(CA)
      ++ "\n" ++ "B v C = " ++ show(BC) ++ "-" ++ show(CB) ];
      
      % A v B = 3-7
      % A v C = 12-11
      % B v C = 0-3
      % ----------
      % A v B = 3-7
      % A v C = 13-12
      % B v C = 0-3
      % ----------
      % ==========
      % Finished in 433msec
      
      % Detailed outputs
      % AB = 3; BA = 7; AC = 12; CA = 11; BC = 0; CB = 3;
      % gfA = 15; gfB = 7; gfC = 14;0
      % gaA = 18; gaB = 6; gaC = 12;
      % gdifA = -3; gdifB = 1; gdifC = 2;
      % gavA = 0.833333333333333; gavB = 1.16666666666667; gavC = 1.16666666666667;
      % ----------
      % AB = 3; BA = 7; AC = 13; CA = 12; BC = 0; CB = 3;
      % gfA = 16; gfB = 7; gfC = 15;
      % gaA = 19; gaB = 6; gaC = 13;
      % gdifA = -3; gdifB = 1; gdifC = 2;
      % gavA = 0.842105263157895; gavB = 1.16666666666667; gavC = 1.15384615384615;
      %----------
      %==========
      
      
      

      Like

      • Jim Randell 9:18 am on 29 August 2019 Permalink | Reply

        @GeoffR: I suspect the second solution comes about because the calculations for “goal average” will be done using floating point numbers. floats are only approximations to real numbers, so if we compare two floats that should be equal, but have been arrived at by different calculations, it is likely that one will compare as larger than the other.

        I would change the model to keep things in the integer domain, by replacing constraints of the form:

        constraint a / b > c / d;
        

        with the equivalent:

        constraint a * d > c * b;
        

        Like

    • GeoffR 3:12 pm on 29 August 2019 Permalink | Reply

      @Jim: Yes, I think you are right as I got a similar second incorrect solution in Python, with a similar approach. For me, it was an unforeseen consequence of using floats instead of integers.
      Thanks for the explanation.

      Like

      • Jim Randell 3:17 pm on 29 August 2019 Permalink | Reply

        Although in Python you can avoid floats by using the [[ fractions ]] module to give an exact representation of rational numbers for the goal averages.

        Like

  • Jim Randell 11:28 am on 12 August 2019 Permalink | Reply
    Tags: by: John Owen   

    Teaser 2885: Croquet mallet 

    From The Sunday Times, 7th January 2018 [link]

    My croquet mallet is less than a metre high and consists of a cylindrical shaft attached to a heavier cuboid head, both of uniform density. Knowing the total weight of the mallet, I wanted to work out the weight of the shaft. I found the point of balance along the shaft and measured the distances from there to each end of the shaft, the smaller of which was less than the height of the head. Each of these three distances was a whole prime number of cm, and taking the three distances together with the height of the mallet, no digit was repeated. I worked out that the weight of the head was a single digit multiple of the weight of the shaft.

    What was the height of my mallet?

    [teaser2885]

     
    • Jim Randell 11:29 am on 12 August 2019 Permalink | Reply

      When the mallet is balanced we have:

      where a, b, c are all primes and b < c < a.

      The total length of the mallet t = a + b + c < 100.

      And between them, the numbers a, b, c, t have no repeated digits.

      The shaft has a weight w acting at a distance of (a + b)/2 − b = (a − b)/2 from the balance point.

      The head has a weight kw acting at a distance of b + c/2.

      So for these to balance we have:

      w(a − b)/2 = kw(b + c/2)
      (a − b) = k(2b + c)
      k = (a − b) / (2b + c)

      where k is a single digit integer.

      This Python program finds the solution in 78ms.

      Run: [ @repl.it ]

      from enigma import subsets, Primes, is_duplicate, div, printf
      
      for (b, c, a) in subsets(Primes(100), size=3, select='C'):
        t = a + b + c
        if not(t < 100): continue
        if is_duplicate(a, b, c, t): continue
      
        k = div(a - b, 2 * b + c)
        if k is None or k < 2 or k > 9: continue
      
        printf("t={t} [a={a} b={b} c={c}, k={k}]")
      

      Solution: The mallet is 90cm high.

      The values are: t=90, a=83 b=2 c=5, k=9.

      Like

  • Jim Randell 11:54 am on 21 June 2019 Permalink | Reply
    Tags: by: John Owen   

    Teaser 2961: Alan and Cat 

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

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

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

    What was the date then?

    [teaser2961]

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

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

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

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

      Run: [ @repl.it ]

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

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


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

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

      Like

  • Jim Randell 12:37 pm on 17 June 2019 Permalink | Reply
    Tags: by: John Owen   

    Teaser 2903: What’s my card? 

    From The Sunday Times, 13th May 2018 [link]

    Four expert logicians play a game with a pack of six cards, numbered from 1 to 6. The cards are shuffled and each draws a card, holding it in front of him so that he cannot see his own number but can see the numbers held by the others. The winner is the player who can first deduce what number he is holding.

    Each player in turn is asked to announce the sum of two numbers that he can see on the other cards. One game started with Alf announcing 6. After a long pause, no-one claimed victory, so Bert then announced 5. There was a significant pause, but before Charlie spoke, someone claimed victory.

    Which cards did Alf and Bert hold, and which cards remained on the table?

    [teaser2903]

     
    • Jim Randell 12:38 pm on 17 June 2019 Permalink | Reply

      I took the “long pause” to mean that no-one can immediately declare victory, and each player can take the fact that no-one can immediately declare victory into account. And even with this additional information no-one can declare victory, and this too can be taken into account, and so on until the process provides no further information to any of the players.

      I took the “significant pause” to mean that no-one can immediately declare victory, and each player can take this fact into account.

      This Python program starts by consider all possible P(6, 4) = 360 ways the cards can be dealt, and then reduces the possibilities as each piece of new information is taken into account.

      It runs in 84ms.

      Run: [ @repl.it ]

      from itertools import permutations
      from enigma import unpack, filter_unique, irange, printf
      
      # cards for A, B, C, D
      cA = unpack(lambda A, B, C, D: A)
      cB = unpack(lambda A, B, C, D: B)
      cC = unpack(lambda A, B, C, D: C)
      cD = unpack(lambda A, B, C, D: D)
      
      # what A, B, C, D can see
      sA = unpack(lambda A, B, C, D: (B, C, D))
      sB = unpack(lambda A, B, C, D: (A, C, D))
      sC = unpack(lambda A, B, C, D: (A, B, D))
      sD = unpack(lambda A, B, C, D: (A, B, C))
      
      # cards
      cards = set(irange(1, 6))
      
      # start with all possible arrangements of cards for (A, B, C, D)
      r = set(permutations(cards, 4))
      printf("[{n} possibilities]", n=len(r))
      
      # A declares 6, which the value of B+C, B+D or C+D
      r = set((A, B, C, D) for (A, B, C, D) in r if 6 in (B + C, B + D, C + D))
      printf("[{n} possibilities]", n=len(r))
      
      # no-one claims immediate victory
      def unclaimed(r):
        (_, rA) = filter_unique(r, sA, cA)
        (_, rB) = filter_unique(r, sB, cB)
        (_, rC) = filter_unique(r, sC, cC)
        (_, rD) = filter_unique(r, sD, cD)
        return set(rA).intersection(rB, rC, rD)
      
      # apply filter until the results remain unchanged (according to ==)
      def repeat(fn, x):
        while True:
          x0 = x
          x = fn(x0)
          if x == x0: return x0
      
      # there is a long pause
      # so repeat unclaimed() until there is nothing further eliminated
      r = repeat(unclaimed, r)
      printf("[{n} possibilities]", n=len(r))
      
      # B declares 5, which is the value of A+C, A+D, C+D
      r = set((A, B, C, D) for (A, B, C, D) in r if 5 in (A + C, A + D, C + D))
      printf("[{n} possibilities]", n=len(r))
      
      # at this point no-one claims immediate victory
      r = unclaimed(r)
      printf("[{n} possibilities]", n=len(r))
      
      # so what possibilities are left?
      printf("remaining = {r}")
      
      
      # output possible declarations
      (dA, _) = filter_unique(r, sA, cA)
      (dB, _) = filter_unique(r, sB, cB)
      (dC, _) = filter_unique(r, sC, cC)
      (dD, _) = filter_unique(r, sD, cD)
      
      for s in r:
        (A, B, C, D) = s
        printf("\nA={A} B={B} C={C} D={D}, table={t}:", t=cards.difference(s))
        if s in dA: printf("  A declares {A}")
        if s in dB: printf("  B declares {B}")
        if s in dC: printf("  C declares {C}")
        if s in dD: printf("  D declares {D}")
      

      Solution: Alf has 3. Bert has 5. The cards remaining on the table are 2 and 6.

      Starting from 360 possibilities the possible hands are reduced as follows:

      Initially, 360 possibilities.
      “A declares 6”, 144 possibilities.
      “there is a long pause”, 48 possibilities.
      “B declares 5”, 20 possibilities.
      “no-one claims immediate victory”, 2 possibilities.

      The two remaining possibilities are (A=3, B=5, C=1, D=4) and (A=3, B=5, C=4, D=1). We don’t know from the information given which order C and D are holding 1 and 4, but each player can see at least one of the cards, so they would know the exact hand dealt, and presumably all four of them would declare victory simultaneously.


      Here is my manual solution:

      A says “6”, so can see 1+5 or 2+4 (3 and 6 cannot participate in any pair that sum to 6)

      If A is holding one of these cards (1, 2, 4, 5) they must be seeing the sum that doesn’t involve their own card. B, C, D can see which card A is holding, so would know which of the sums A is seeing, and so the people who can only see one half of that sum would immediately be able to declare their number (as the other half of that sum). This doesn’t happen.

      Hence A must be holding 3 or 6. And the other card (6 or 3) must still be on the table, as if one of B, C, D were holding it the other two could deduce their cards immediately.

      So B, C, D are holding three cards from 1, 2, 4, 5.

      B says “5”, so can see 1+4 or 2+3.

      If A is holding 6, then 3 is still on the table, so B can see 1+4 from C and D. C and/or D can immediately declare their cards as soon as B says “5”. This doesn’t happen.

      So A can deduce he is holding 3 (and can declare victory, after the pause where neither C nor D declare victory).

      B must be able to see 1+4 (from C and D) or 2+3 (from A’s 3 and one of C and D holds the 2).

      If B is holding 1 or 4, then he must be able to see 2+3, so whichever of C and D cannot see the 2 must be holding it and can declare immediately. This doesn’t happen.

      Similarly if B is holding 2, then he must be able to see 1+4 from C and D, so C and D can declare their cards immediately. This doesn’t happen.

      So B can deduce he is holding 5 (and can declare, after the pause where neither C nor D declare victory).

      This leaves C and D holding two cards from 1, 2, 4, and the other is still on the table (along with 6).

      If C and D are holding 1 and 2, then when B says “5” A would immediately know his card was 3 (which goes with the 2 to make 5). This doesn’t happen.

      If C and D are holding 2 and 4, then when B says “5” A would immediately know his card was 3 (which goes with the 2 to make 5). This doesn’t happen.

      So C and D are holding 1 and 4, and can declare (after the pause where A does not declare victory). 2 and 6 remain on the table.

      Like

    • John Crabtree 3:00 pm on 21 June 2019 Permalink | Reply

      Let a declared value be D.
      If the non-declarers have cards >= D or = D/2, two players can immediately determine their cards.
      If two pairs of cards add to D, two players can immediately determine their cards.

      After A’s call, only A can have and as 1 + 5 = 2 + 4 = 6 must have, 3 or 6
      After B’s call, A must have 3 and, as 1 + 4 = 2 + 3 = 5, B must have 5.
      After B’s call, A knows immediately that he has 3 unless he can see C + D = 5 = 1 + 4.
      The cards on the table are 2 and 6.

      Like

  • Jim Randell 11:22 am on 8 May 2019 Permalink | Reply
    Tags: by: John Owen   

    Teaser 2914: Bank statement 

    From The Sunday Times, 29th July 2018 [link]

    My last bank statement was most interesting. The first line showed the opening balance in pounds and pence, then each of the following four lines showed a debit together with the resulting balance. I did not go overdrawn.

    Remarkably, each of the five balances used the same five different digits once only, and the largest of the digits was less than three times the smallest. Each of the four debits also used five different digits once only, but the digits in the debits were all different from those in the balances.

    What was the final balance?

    [teaser2914]

     
    • Jim Randell 11:23 am on 8 May 2019 Permalink | Reply

      This Python 3 program runs in 415ms.

      Run: [ @repl.it ]

      from itertools import combinations, permutations
      from collections import defaultdict
      from enigma import irange, nconcat, nsplit, join, sprintf as f
      
      digits = irange(0, 9)
      
      # from transactions <ts> and balance <b> find <k> transactions
      def solve(ts, b, k, s=[]):
        if k == 0:
          yield s
        elif b in ts:
          for (d, a) in ts[b]:
            yield from solve(ts, a, k - 1, s + [(b, d, a)])
      
      # choose 5 different digits for the balance
      for ds in combinations(digits, 5):
      
        # the largest is less than 3x the smallest
        if not(ds[-1] < 3 * ds[0]): continue
      
        # make all possible numbers from the digits
        ns = sorted(nconcat(s) for s in permutations(ds) if s[0] != 0)
      
        # find transactions that make viable debits
        ts = defaultdict(list)
        for (a, b) in combinations(ns, 2):
          d = b - a
          xs = set(nsplit(d))
          if len(xs) == 5 and xs.isdisjoint(ds):
            ts[b].append((d, a))
      
        # find a sequence of 4 transactions
        for b in ts.keys():
          for s in solve(ts, b, 4):
            print(f("final = {f} [{s}]", s=join((f("{b} - {d} = {a}") for (b, d, a) in s), sep=", "), f=s[-1][2]))
      

      Solution: The final balance was £ 347.58.

      There are two possibilities for the initial amount and the first debit amount, which give the same value for the balance:

      (1) 853.47 – 109.62 = 743.85; or:
      (1) 873.45 – 129.60 = 743.85

      After that the next three debits are:

      (2) 743.85 – 169.02 = 574.83
      (3) 574.83 – 120.96 = 453.87
      (4) 453.87 – 106.29 = 347.58

      The condition that “the largest of the digits was less than three times the smallest” reduces the search space, but there are no further solutions without this condition.

      Like

    • GeoffR 10:28 am on 9 May 2019 Permalink | Reply

      A brute force approach in MiniZinc uses 45 integer variables and sets to solve this teaser.

      % A Solution in MiniZinc 
      include "globals.mzn"; 
      
      % Balance/Debit Sums - uses 5-digit integers for £ and pence parts
      % ABCDE - abcde == FGHIJ;
      % FGHIJ - fghij == KLMNO;
      % KLMNO - klmno == PQRST;
      % PQRST - pqrst == UVWXY;
      
      % Balances integers
      var 0..9: A; var 0..9: B; var 0..9: C; var 0..9: D; var 0..9: E;
      var 0..9: F; var 0..9: G; var 0..9: H; var 0..9: I; var 0..9: J;
      var 0..9: K; var 0..9: L; var 0..9: M; var 0..9: N; var 0..9: O;
      var 0..9: P; var 0..9: Q; var 0..9: R; var 0..9: S; var 0..9: T;
      var 0..9: U; var 0..9: V; var 0..9: W; var 0..9: X; var 0..9: Y;
      
      constraint A != 0 /\ F != 0 /\ K != 0 /\ P != 0 /\ U != 0;
      
      % max balance digit < 3 * min digit for the five balances  
      constraint max([A,B,C,D,E]) < 3 * min([A,B,C,D,E]);
      constraint max([F,G,H,I,J]) < 3 * min([F,G,H,I,J]);
      constraint max([K,L,M,N,O]) < 3 * min([K,L,M,N,O]);
      constraint max([P,Q,R,S,T]) < 3 * min([P,Q,R,S,T]);
      constraint max([U,V,W,X,Y]) < 3 * min([U,V,W,X,Y]);
      
      % Balances - sets of integers
      var set of int: s1 = { A,B,C,D,E };
      var set of int: s2 = { F,G,H,I,J };
      var set of int: s3 = { K,L,M,N,O };
      var set of int: s4 = { P,Q,R,S,T };
      var set of int: s5 = { U,V,W,X,Y };
      
      % Sets s1 to s5 have the same integers
      constraint card (s1 intersect s2 ) == 5;
      constraint card (s1 intersect s3 ) == 5;
      constraint card (s1 intersect s4 ) == 5;
      constraint card (s1 intersect s5 ) == 5;
      
      % Debits integers
      var 0..9: a; var 0..9: b; var 0..9: c; var 0..9: d; var 0..9: e;
      var 0..9: f; var 0..9: g; var 0..9: h; var 0..9: i; var 0..9: j;
      var 0..9: k; var 0..9: l; var 0..9: m; var 0..9: n; var 0..9: o;
      var 0..9: p; var 0..9: q; var 0..9: r; var 0..9: s; var 0..9: t;
      
      constraint a != 0 /\ f != 0 /\ k != 0 /\ p != 0;
      
      % Debits - sets of integers
      var set of int: s6 = { a,b,c,d,e };
      var set of int: s7 = { f,g,h,i,j };
      var set of int: s8 = { k,l,m,n,o };
      var set of int: s9 = { p,q,r,s,t };
      
      % Debit sets s6 to s9 have the same integers
      constraint card (s6 intersect s7 ) == 5;
      constraint card (s6 intersect s8 ) == 5;
      constraint card (s6 intersect s9 ) == 5;
      
      % Sets s1 and s6 have no digits in common
      constraint card(s1 intersect s6) == 0;
      
      % Form all 5-digit integers
      var 10000..99999: ABCDE = 10000*A + 1000*B + 100*C + 10*D + E;
      var 10000..99999: FGHIJ = 10000*F + 1000*G + 100*H + 10*I + J;
      var 10000..99999: KLMNO = 10000*K + 1000*L + 100*M + 10*N + O;
      var 10000..99999: PQRST = 10000*P + 1000*Q + 100*R + 10*S + T;
      var 10000..99999: UVWXY = 10000*U + 1000*V + 100*W + 10*X + Y;
      
      var 10000..99999: abcde = 10000*a + 1000*b + 100*c + 10*d + e;
      var 10000..99999: fghij = 10000*f + 1000*g + 100*h + 10*i + j;
      var 10000..99999: klmno = 10000*k + 1000*l + 100*m + 10*n + o;
      var 10000..99999: pqrst = 10000*p + 1000*q + 100*r + 10*s + t;
      
      % Balance/Debit sums in sequence
      constraint ABCDE - abcde == FGHIJ;
      constraint FGHIJ - fghij == KLMNO;
      constraint KLMNO - klmno == PQRST;
      constraint PQRST - pqrst == UVWXY;
      
      solve satisfy;
      
      output ["Final Balance = " ++ "£"++ show(U),show(V),show(W) ++ "." 
      ++ show(X),show(Y) ] 
      ++ ["\n" ++ show(ABCDE) ++ " - " ++ show(abcde)  ++ " = " ++ show(FGHIJ) ]
      ++ ["\n" ++ show(FGHIJ) ++ " - " ++ show(fghij)  ++ " = " ++ show(KLMNO) ]
      ++ ["\n" ++ show(KLMNO) ++ " - " ++ show(klmno)  ++ " = " ++ show(PQRST) ]
      ++ ["\n" ++ show(PQRST) ++ " - " ++ show(pqrst)  ++ " = " ++ show(UVWXY) ];
      
      % Final Balance = £347.58
      % 85347 - 10962 = 74385 - five digit integer format for £/pence sums
      % 74385 - 16902 = 57483
      % 57483 - 12096 = 45387
      % 45387 - 10629 = 34758
      % % time elapsed: 0.27 s
      % ----------
      % Final Balance = £347.58
      % 87345 - 12960 = 74385
      % 74385 - 16902 = 57483
      % 57483 - 12096 = 45387
      % 45387 - 10629 = 34758
      % % time elapsed: 0.27 s
      % ----------
      % ==========
      % Finished in 666msec
      
      

      Like

  • Jim Randell 8:57 am on 1 April 2019 Permalink | Reply
    Tags: by: John Owen   

    Teaser 2928: Golf balls 

    From The Sunday Times, 4th November 2018 [link]

    Three friends play 18 holes of golf together every week. They have a large supply of golf balls numbered from 1 to 5. At the beginning of a year, they each start playing with a new ball, but all three ball numbers are different. Alf uses the same ball number for exactly 21 holes before changing to the next higher number (or to number 1 if he was using a number 5). He continues to use each number for exactly 21 holes. The same applies to Bert, except that he changes his ball number in the same way after every 22 holes, and to Charlie who changes his ball number after every 23 holes.

    Last year, there was just one occasion when they all used the same ball number on a hole.

    What was the number of the hole on that occasion?

    [teaser2928]

     
    • Jim Randell 8:59 am on 1 April 2019 Permalink | Reply

      This Python program finds the solution constructively in 79ms.

      Run: [ @repl.it ]

      from itertools import permutations
      from enigma import irange, first, printf
      
      # increment ball count, and ball if necessary
      def inc(i, x, X):
        i += 1
        if i == X:
          x = (1 if x == 5 else x + 1)
          i = 0
        return (i, x)
      
      # find (week, hole) pairs
      def solve(A, B, C, a, b, c, n):
        i = j = k = 0
        # consider number of weeks
        for w in irange(1, n):
          # and each hole
          for h in irange(1, 18):
            if a == b == c:
              yield (w, h, b)
            # increment ball counters
            (i, a) = inc(i, a, A)
            (j, b) = inc(j, b, B)
            (k, c) = inc(k, c, C)
      
      # choose starting balls for A, B, C
      # suppose A's ball is 1, we only have to choose B and C
      a = 1
      for (b, c) in permutations((2, 3, 4, 5), 2):
        # in 2017 there were 52 whole weeks, + 1 extra Sunday
        rs = first(solve(21, 22, 23, a, b, c, 53), 2)
        if len(rs) == 1:
          (w, h, x) = rs[0]
          printf("a={a} b={b} c={c}: week={w}, hole={h}, ball={x}")
      

      Solution: Hole number 10.

      It would happen on week number 53.

      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
%d bloggers like this: