Recent Updates Page 34 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 9:44 am on 12 April 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 687: Fair deal 

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

    From a normal pack of playing cards, Bill, George, Harry and Joe were each dealt an Ace, a King, a Queen, a Jack and a ten.

    Harry’s five cards were in three different suits and consisted of three red and two black cards.

    Joe’s five cards were also in three different suits, his Ace being in the same suit as his Queen, and his King in the same suit as his Jack.

    George held more than one black card.

    Bill’s five cards were all in the same suit.

    Harry held the King of spades, and Joe the ten of diamonds.

    What were the cards in George’s hand?

    This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 2 (1981). The puzzle text above is taken from the book.

    [teaser687]

     
    • Jim Randell's avatar

      Jim Randell 9:45 am on 12 April 2022 Permalink | Reply

      I used the [[ SubstitutedExpression ]] solver from the enigma.py library to fill out the suits of the cards.

      Here is the run file:

      #! python3 -m enigma -rr
      
      # assign values 0-3 (S=0; C=1; H=2; D=3) to:
      #
      #     A K Q J X
      #  B: a b c d e
      #  G: f g h i j
      #  H: k m n p q
      #  J: r s t u v
      
      SubstitutedExpression
      
      --base=4
      --distinct="afkr,bgms,chnt,dipu,ejqv"
      
      # red cards and black cards
      --code="red = lambda x: x > 1"
      --code="black = lambda x: x < 2"
      
      # H's cards were in 3 different suits
      "len({{k}, {m}, {n}, {p}, {q}}) == 3"
      # 3 red [and 2 black]
      "icount([{k}, {m}, {n}, {p}, {q}], red) == 3"
      
      # J's cards were in 3 different suits
      "len({{r}, {s}, {t}, {u}, {v}}) == 3"
      # suit of A is the same as Q
      "{r} = {t}"
      # suit of K is the same as J
      "{s} = {u}"
      
      # G has more than 1 black card
      "icount([{f}, {g}, {h}, {i}, {j}], black) > 1"
      
      # B's cards are in the same suit
      "{a} = {b}" "{b} = {c}" "{c} = {d}" "{d} = {e}"
      
      # H held KS (i.e. m = S = 0)
      --assign="m,0"
      
      # J held XD (i.e. v = D = 3)
      --assign="v,3"
      

      And then I wrote a short Python program to output the hands dealt.

      The whole thing runs in 64ms.

      Run: [ @replit ]

      from enigma import (SubstitutedExpression, join, printf)
      
      # load the run-file
      p = SubstitutedExpression.from_file("teaser687.run")
      
      # solve the puzzle
      for s in p.solve(verbose=0):
        # output hands
        printf("   A K Q J X")
        hand = lambda xs: join(("SCHD"[s[x]] for x in xs), sep=" ")
        printf("B: {h}", h=hand("abcde"))
        printf("G: {h}", h=hand("fghij"))
        printf("H: {h}", h=hand("kmnpq"))
        printf("J: {h}", h=hand("rstuv"))
        printf()
      

      Solution: George held: A♣, K♦, Q♣, J♠, 10♠.

      The complete set of hands is fully determined:

      B: A♥, K♥, Q♥, J♥, 10♥.
      G: A♣, K♦, Q♣, J♠, 10♠.
      H: A♦, K♠, Q♦, J♦, 10♣.
      J: A♠, K♣, Q♠, J♣, 10♦.

      Like

  • Unknown's avatar

    Jim Randell 3:02 pm on 8 April 2022 Permalink | Reply
    Tags:   

    Teaser 3107: Room 101 

    From The Sunday Times, 10th April 2022 [link] [link]

    In the Ministry of Love, O’Brien told Winston Smith to calculate five-digit perfect squares, none sharing a prime factor with 1984.

    “And Winston, no two of them may differ by a multiple of 101 or you know what will happen. Now find as many as you can.”

    When Winston said he had found more than fifty, O’Brien replied:

    “Well done, Winston. Although there were a quadrillion solutions, I know some of your squares.”

    “Does the party control my mind?”

    “We do Winston. Did you choose 10201, for example?”

    “Of course not! It’s the worst square in the world!”

    “How many fingers am I holding up Winston?”

    “Three? Four? I don’t know!”

    “That’s how many of your squares we know.”

    What four squares did O’Brien know?

    [teaser3107]

     
    • Jim Randell's avatar

      Jim Randell 3:19 pm on 8 April 2022 Permalink | Reply

      This Python program collects groups of 5-digit squares (excluding 10201) by their residue modulo 101. Any two squares with the same residue will differ by a multiple of 101.

      So Smith can choose at most one square from each group.

      It turns out there are 51 groups, so if Smith has correctly found more than 50 squares he must have chosen 1 from each group. And the only choices we (and O’Brien) can know for sure are from groups that have exactly 1 member.

      The program runs in 55ms.

      Run: [ @replit ]

      from enigma import (powers, is_coprime, group, mod, join, printf)
      
      # group 5-digit squares, except 10201, that are coprime to 1984 by their residue mod 101
      d = group(
        powers(100, 316, 2),
        st=(lambda x: x != 10201 and is_coprime(x, 1984)),
        by=mod(101),
      )
      printf("[{n} groups]", n=len(d.keys()))
      
      # look for keys with only one candidate
      for k in sorted(d.keys()):
        vs = d[k]
        if len(vs) == 1:
          printf("{k} -> {vs}", vs=join(vs, sep=", "))
      

      Solution: The four squares O’Brien knew are: 15625, 34969, 62001, 91809.

      Like

    • GeoffR's avatar

      GeoffR 8:13 am on 14 April 2022 Permalink | Reply

      
      from enigma import is_coprime
      from collections import defaultdict
      SQList = defaultdict(list)
      
      # 5-digit squares must be co-prime with 1984
      # omit 101 as 101 ^ 2 = 10201, which is not needed
      squares = [x * x for x in range(102, 317) if is_coprime(x * x, 1984)]
      
      # index squares on remainder after dividing square by 101.
      for n in squares:
          SQList[n % 101].append(n)
      
      print("O'Brien knew the following squares:" )
      for k, v in SQList.items():
          if len(v) == 1:
              print( v[0], end = ' ')
      
      

      Like

    • Hugh+Casement's avatar

      Hugh+Casement 10:58 am on 17 April 2022 Permalink | Reply

      I think it can be done without a program.
      1984 = 2^6 × 31, so all even integers are excluded, as are the squares of multiples of 31, which are 155, 217, and 279 in the range under consideration (101 to 315). We are also told that 101² is absent.

      If i² – j² is a multiple of 101, then so is either (i – j) or (i + j).
      That means that nearly every odd integer in the range is paired with at least one other. The exceptions are 125 = 404 – 279, 187 = 404 – 217, 249 = 404 – 155, and 303 = 404 – 101 = 101 + 202.

      And there certainly weren’t a quadrillion: in English we would say “Though there be a quadrillion …”.

      Like

  • Unknown's avatar

    Jim Randell 9:30 am on 7 April 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 910: The Teaser Club 

    From The Sunday Times, 30th December 1979 [link]

    “The Teaser Club was formed in the summer of 1969”, the secretary of the Chub told me. “We held our Inaugural meeting then. A president and a secretary were appointed, and a constitution was drawn up. One rule of the Club is that each member must send a Christmas card to every other member. Each card, as you may guess, carries a Teaser as well as Christmas greetings”.

    The membership increased every year”, he continued, “indeed, in 1970, we sent 330 more cards than we did in 1969”.

    “How many were sent in 1978?”, I asked.

    “We sent 330 more than in 1977”, the secretary replied with a smile.

    “And how many did you send in 1977?”, I persisted.

    “By a strange coincidence”, he replied, “it was 330 more than in 1976”.

    “Thank you for your information”, I said. “I see now why you call it the Teaser Club”.

    How many Christmas cards were sent in 1975?

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

    [teaser910]

     
    • Jim Randell's avatar

      Jim Randell 9:31 am on 7 April 2022 Permalink | Reply

      If there are n members of the club, then the number of cards send is s(n) = n(n − 1).

      This Python program looks for pairs of possible s(n) values that differ by 330. And then looks for two pairs which chain together (for the 1976, 1977, 1978 membership.

      We then look for possible lower values (the membership must grow by at least 1 member a year) for the 1969, 1970 membership.

      Together these give us upper and lower bounds on the 1975 membership, from which we can determine the number of cards sent.

      It runs in 55ms.

      Run: [ @replit ]

      from enigma import (irange, inf, subsets, printf)
      
      # record s[n] = number of cards sent by n members
      s = [0]
      for n in irange(1, inf):
        t = n * (n - 1)
        if t - s[-1] > 330: break
        s.append(t)
      
      # find terms that differ by 330, record by index
      d = dict()
      for ((i, x), (j, y)) in subsets(enumerate(s), size=2):
        if y - x == 330:
          d[i] = j
          printf("[s[{i}] = {x} -> s[{j}] = {y}]")
      
      # look for indices i, j, k such that d[i] = j and d[j] = k
      for (i, j) in d.items():
        k = d.get(j)
        if k is None: continue
        printf("1976 = {i}; 1977 = {j}; 1978 = {k}")
      
        # and look for 1969, 1970 valules
        for (a, b) in d.items():
          if b + 6 > i: continue
          printf("-> 1969 = {a}; 1970 = {b}")
      
          # calculate 1975 values
          for g in irange(b + 5, i - 1):
            printf("--> 1975 = {g}; cards = {x}", x=s[g])
      

      Solution: 552 Christmas cards were sent in 1975.

      Like

  • Unknown's avatar

    Jim Randell 8:55 am on 5 April 2022 Permalink | Reply
    Tags:   

    Teaser 2866: On the rack 

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

    I have wine in a rectangular rack consisting of five rows and eight columns. The bottles are made up of five different vintages with each vintage (four reds and four whites) forming a rectangle in the rack. Within each vintage-rectangle the places occupied by the whites form a connected set, and the same is true of the reds. No two vintage-rectangles have the same red/white pattern, no matter what angle they are viewed at from the front.

    In the rack the first row is a mixture of reds and whites, with a red on the extreme right. Another row contains just reds, and the first column contains more reds than than any other column.

    What (in order) are the colours of the wines in the second row?

    [teaser2866]

     
    • Jim Randell's avatar

      Jim Randell 8:56 am on 5 April 2022 Permalink | Reply

      There are 5 possible rectangular patterns of 8 bottles:

      And 5×8 = 40 so each pattern must appear exactly once. All we need to do is work out how to fit them into an 8×5 grid meeting the specified conditions.

      It is fairly straightforward to sketch out a solution manually on the back of an envelope in a few minutes. But making a programmed solution is a bit more involved, and my first program only just managed a run time less than a second.

      However, we can restructure the program using a few techniques to make it more efficient:

      Firstly we take the pieces and precompute the data for the 4 possible rotations. The rotations are then stored with the values furthest from the origin listed first, so when we try to fit them into the grid, pieces that fall outside the bounds of the grid will fail sooner.

      The grid is stored as a linear array to make copying it easy, and the values are stored in columns in the grid, so we fill out the columns in order as we go along.

      As the pieces are placed we check that (row 0, col 7) must be red, and as the columns are filled out we ensure that column 0 (which is filled out first) has more reds than any of the other columns.

      So when the grid is complete we only need to check that row 0 also has whites and one of the other rows is entirely red.

      Together, these measures bring the run time down to just 64ms. (Internal runtime is 12ms).

      Run: [ @replit ]

      from enigma import (irange, unpack, chunk, join, printf)
      
      # red and white
      (R, W) = (0, 1)
      
      # pieces: [ (r, c, v) ... ]
      pieces = [
        # R R R R W W W W
        [ (0, 0, R), (0, 1, R), (0, 2, R), (0, 3, R), (0, 4, W), (0, 5, W), (0, 6, W), (0, 7, W) ],
        # R R R R
        # W W W W
        [ (0, 0, R), (0, 1, R), (0, 2, R), (0, 3, R), (1, 0, W), (1, 1, W), (1, 2, W), (1, 3, W) ],
        # R R R W
        # R W W W
        [ (0, 0, R), (0, 1, R), (0, 2, R), (0, 3, W), (1, 0, R), (1, 1, W), (1, 2, W), (1, 3, W) ],
        # R W W W
        # R R R W
        [ (0, 0, R), (0, 1, W), (0, 2, W), (0, 3, W), (1, 0, R), (1, 1, R), (1, 2, R), (1, 3, W) ],
        # R R W W
        # R R W W
        [ (0, 0, R), (0, 1, R), (0, 2, W), (0, 3, W), (1, 0, R), (1, 1, R), (1, 2, W), (1, 3, W) ],
      ]
      
      # rotate a piece 90 degrees
      def rotate(p):
        p_ = list((c, -r, v) for (r, c, v) in p)
        r0 = min(r for (r, _, _) in p_)
        c0 = min(c for (_, c, _) in p_)
        return list((r - r0, c - c0, v) for (r, c, v) in p_)
      
      # transform the pieces array into [ <rot 0>, <rot 90>, <rot 180>, <rot 270> ]
      for i in irange(len(pieces)):
        p = pieces[i]
        ps = list()
        for n in irange(0, 3):
          ps.append(sorted(p, key=unpack(lambda r, c, v: r + c), reverse=1))
          if n == 3: break
          p = rotate(p)
        pieces[i] = ps
          
      # place p at position k in g
      def place(g, p, k):
        g = list(g)
        (c0, r0) = divmod(k, 5)
        for (r, c, v) in p:
          r += r0
          if r > 4: return
          c += c0
          if c > 7: return
          # only place R at (r=0, c=7)
          if r == 0 and c == 7 and v != R: return
          i = 5 * c + r
          if g[i] is not None: return
          g[i] = v
        return g
      
      # fit the pieces into the grid
      # return the rows
      def fit(ps, g):
        # are we done?
        if not ps:
          # create the cols and rows
          cs = list(chunk(g, 5))
          rs = list(zip(*cs))
          # row 0 has whites in (as well as red at col 7)
          if W not in rs[0]: return
          # but one of the other rows is all red
          if all(W in r for r in rs): return
          # return the rows
          yield rs
        else:
          # find an empty square
          k = g.index(None)
          # try to place a piece there (in some orientation)
          for (i, rs) in enumerate(ps):
            for p in rs:
              g_ = place(g, p, k)
              if g_ is None: continue
              # make the columns
              cs = list(chunk(g_, 5))
              if None not in cs[0]:
                # count the reds in column 0
                n = cs[0].count(R)
                # all the other columns must have fewer reds
                if not all(j == 0 or col.count(R) < n for (j, col) in enumerate(cs)): continue
              # place the remaining pieces
              yield from fit(ps[:i] + ps[i + 1:], g_)
                
      # initial grid
      g0 = [None] * 40
      
      # fit the pieces into the grid
      for rs in fit(pieces, g0):
        # output rows
        for r in rs:
          printf("[ {r} ]", r=join(('RW'[v] for v in r), sep=' '))
        printf()
      

      Solution: The wines in the second row down are: (red, white, white, white, white, white, white, red).

      There is only one possible layout, as shown:

      Like

  • Unknown's avatar

    Jim Randell 4:15 pm on 1 April 2022 Permalink | Reply
    Tags:   

    Teaser 3106: Underground umbra conundrum 

    From The Sunday Times, 3rd April 2022 [link] [link]

    An underground car park has rectangular walls, each covered with 300 abutting square tiles arranged in three repeats of red, orange, yellow, green and blue columns twenty tiles high. A sharp tapering shadow from a duct played across one wall from top to bottom (with straight lines similar to that shown).

    Each shadow edge crossed every colour and, curiously, hit just two points where four tile corners met. The upper and lower pairs of these were on levels the same distance up and down from the mid-level line. I also noticed that no column was completely free of shadow, but just one column was completely in shadow.

    Give the shadow’s area relative to the wall area as a fraction in simplest form.

    [teaser3106]

     
    • Jim Randell's avatar

      Jim Randell 11:01 pm on 1 April 2022 Permalink | Reply

      For the “shadow edge” (or terminator) to “cross” a coloured column I required that a non-zero length of it intersected with the column. I assumed that the points at which the terminator hits the intersections of the four tile corners are all the same vertical distance from the horizontal centre line of the wall. And that the shadow tapers towards the top and slants towards the right (as in the diagram).

      After drawing a diagram on graph paper to solve the puzzle, I wrote the following Python program to check the solution was unique. And I found there were in fact two ways to reach the answer.

      The Python program considers the possible heights at which the terminator line hits the intersections of four tile corners, and then possible horizontal positions. The areas of the resulting lit regions are grouped by the width in tiles of the bounding box of the area.

      We then look for two lit areas that have exactly 1 column between them (that is in shadow), and the total area of shadow is calculated.

      It runs in 56ms. (Internal runtime is 6.1ms).

      Run: [ @replit ]

      from enigma import (defaultdict, irange, subsets, is_coprime, Polynomial, intc, product, printf)
      
      # consider possible levels for the corner intersection (from the floor/ceiling)
      for y in irange(1, 9):
      
        # record possible lit areas by bounding width
        d = defaultdict(set)
        
        # possible x co-ordinates for upper/lower intersections
        for (x, x_) in subsets(irange(1, 8), size=2):
          if not is_coprime(20 - 2 * y, x_ - x): continue
          
          # interpolate the terminator line
          f = Polynomial.interpolate([(y, x), (20 - y, x_)])
          # calculate intercepts of y=0, y=20 (floor/ceiling)
          (x0, x20) = map(f, [0, 20])
          # must start in first column, and include at least 5 columns
          if x0 < 0 or (not x0 < 1) or (not x20 > 4): continue
          
          # width of bounding region
          w = intc(x20)
          if w < 5 or w > 9: continue
          # lit area
          L = 10 * (x0 + x20)
          d[w].add(L)
          
          printf("[y={y}: x=({x}, {x_}) -> ({x0}, {x20}) w={w} L={L}]")
      
        # look for 2 bounding widths that sum to 14
        for w1 in sorted(d.keys()):
          w2 = 14 - w1
          if not w1 < w2: break
      
          # calculate area in shadow
          for (L1, L2) in product(d[w1], d[w2]):
            T = 300
            S = T - L1 - L2
            q = S / T
            printf("q = {S}/{T} = {q} [w1={w1} L1={L1}; w2={w2} L2={L2}]")
      

      Solution: The shadow covers 8/15 of the wall.


      We note that in the determination of any lit region we have:

      x0 + x20 = w

      And the area of the lit region is therefore:

      L = 20 (x0 + x20) / 2
      L = 10w

      And for a solution we require widths that sum to 14 (to leave exactly one column completely in shadow).

      Hence the area in shadow is:

      S = 300 − L1 − L2
      S = 300 − 10w1 − 10w2
      S = 300 − 10(w1 + w2)
      S = 300 − 140
      S = 160

      So we can see, if there are any solutions, the answer will be:

      q = 160 / 300
      q = 8 / 15

      And the program above shows there are two scenarios which lead to a solution (shown below):

      In the second scenario the leftmost red column is only just in shadow (at its bottom right hand corner), and similarly the second green column is only just lit (at its top left hand corner), so the first scenario is probably a better solution (although the second scenario looks more similar to the diagram in the puzzle statement).


      Another way of looking at the puzzle is that there is exactly one column entirely in shadow = 1/15 of the wall.

      And the remaining area of the wall (totalling 14/15) consists of 2 rectangles, each of which is split exactly half in shadow.

      The total area in shadow is therefore: 1/15 + 7/15 = 8/15 of the wall.

      All that remains is to show that there is a construction that meets the remaining conditions (and, as noted above, there are 2).

      Like

  • Unknown's avatar

    Jim Randell 8:40 am on 31 March 2022 Permalink | Reply
    Tags:   

    Teaser 2867: Clumsy Meg 

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

    I arranged cards labelled ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE and TEN equally-spaced around the perimeter of a circular table. The arrangement was such that any two adjacent cards had exactly one letter in common.

    That evening Meg entered the room and accidentally knocked two adjacent cards onto the floor. In her haste to put things right, she inadvertently put the two cards back the wrong way round. Surprisingly, the one-letter property still applied.

    What were the two numbers directly opposite the two that she knocked on the floor?

    [teaser2867]

     
    • Jim Randell's avatar

      Jim Randell 8:41 am on 31 March 2022 Permalink | Reply

      I took “exactly one letter in common” to mean that there was exactly one letter of the alphabet that appeared in both words, but the letter may be repeated in one (or both) of the words.

      The following Python program runs in 51ms.

      Run: [ @replit ]

      from enigma import (subsets, intersect, ordered, update, tuples, join, printf)
      
      # available words
      words = ('ONE', 'TWO', 'THREE', 'FOUR', 'FIVE', 'SIX', 'SEVEN', 'EIGHT', 'NINE', 'TEN')
      
      # find words that share exactly one letter
      S1 = set(ordered(*ws) for ws in subsets(words, size=2) if len(intersect(ws)) == 1)
      
      # check two words share exactly one letter
      check = lambda *ws: ordered(*ws) in S1
      
      # generate a ring of words such that adjacent items share exactly one letter
      def generate(s, ws):
        sz = s[-1]
        # are we done?
        if not ws:
          # check closure and eliminate duplicates
          if check(sz, s[0]) and s[1] < sz:
            yield s
        else:
          # extend the ring
          for (i, w) in enumerate(ws):
            if check(sz, w):
              yield from generate(s + [w], ws[:i] + ws[i + 1:])
      
      # solve the puzzle starting with the first word
      for s in generate([words[0]], words[1:]):
        # find two adjacent words that can be swapped
        for (i, w) in enumerate(s):
          if i == len(s) - 1: break
          s2 = update(s, (i + 1, i), s[i:i + 2])
          if all(check(a, b) for (a, b) in tuples(s2, 2, circular=1)):
            # the numbers opposite the swapped pair
            r = (s2[(i + 5) % 10], s2[(i + 6) % 10])
            fmt = lambda x: join(x, sep=" ", enc="()")
            printf("{r}; {s} -> {s2}", r=fmt(r), s=fmt(s), s2=fmt(s2))
      

      Solution: The two numbers are: SEVEN and EIGHT.

      One scenario is that the cards were initially laid out:

      ONE (O) FOUR (F) FIVE (E) TEN (T) TWO (T) EIGHT (E) SEVEN (S) SIX (I) NINE (E) THREE (E) [ONE]

      And the ONE and FOUR cards were swapped over to give

      FOUR (O) ONE (E) FIVE (E) TEN (T) TWO (T) EIGHT (E) SEVEN (S) SIX (I) NINE (E) THREE (R) [FOUR]

      Or we started with the second set and swapped ONE and FOUR to get the first set.

      Like

  • Unknown's avatar

    Jim Randell 8:47 am on 29 March 2022 Permalink | Reply
    Tags:   

    Teaser 2852: When in Rome 

    From The Sunday Times, 21st May 2017 [link] [link]

    An ancient five-by-five table of letters been found in Rome. All the ten different five-letter rows across and five-letter columns down are Roman numerals, with no letter exceeding a C. The across numbers are, in order, even, even, a cube, a prime, and a power of 2. The down numbers include a cube, the rest being even or prime.

    Which two Roman numerals cross at the middle square?

    [teaser2852]

     
    • Jim Randell's avatar

      Jim Randell 8:47 am on 29 March 2022 Permalink | Reply

      This Python program constructs candidate values for the rows and the columns, and then fills out the rows, ensuring there are always available candidates for the columns.

      Once the grid is filled out the columns are checked to ensure they meet the puzzle requirements.

      It runs in 61ms.

      Run: [ @replit ]

      from enigma import (irange, inf, cb, Primes, int2roman, union, unpack, update, delete, join, match, roman2int, printf)
      
      # max number
      N = 399
      
      # 5-digit roman numerals, map: int -> roman
      rom5 = dict()
      for n in irange(1, N):
        r = int2roman(n)
        if len(r) != 5: continue
        assert not ('M' in r or 'D' in r)
        rom5[n] = r
      
      # generate roman numerals from function f
      def romans(f, a=1):
        for i in irange(a, inf):
          n = f(i)
          if n > N: break
          r = rom5.get(n)
          if r: yield r
      
      # categorise the roman numerals into sets
      evens = set(v for (k, v) in rom5.items() if k % 2 == 0)
      cubes = set(romans(cb))
      ps = Primes(N + 1)
      primes = set(v for (k, v) in rom5.items() if k in ps)
      pow2s = set(romans(lambda n: 2**n))
      
      # row/column candidates
      rcs = [evens, evens, cubes, primes, pow2s]
      ccs = [union([cubes, evens, primes])] * 5
      
      # return column candidates for rows rs
      def col_cand(rs, ccs):
        ccs_ = list()
        # consider each column
        for (j, t) in enumerate(zip(*rs)):
          # make the template
          t = join(t)
          cs = list(x for x in ccs[j] if match(x, t))
          if not cs: return
          ccs_.append(cs)
        return ccs_
      
      # fill out the grid (rows), respecting row/col candidates
      # rs = partially completed grid (rows)
      # rcs = row candidates; map <index> -> <candidates>
      # ccs = col candidates
      def solve(rs, rcs, ccs):
        # are we done?
        if not rcs:
          yield rs
        else:
          # choose a row
          (k, vs) = min(rcs.items(), key=unpack(lambda k, vs: len(vs)))
          # choose a value
          for v in vs:
            rs_ = update(rs, [k], [v])
            # check columns in the new grid match
            cs_ = col_cand(rs_, ccs)
            if cs_:
              # solve for the remaining rows
              yield from solve(rs_, delete(rcs, [k]), cs_)
      
      # initial grid
      g = ['?????'] * 5
      for rs in solve(g, dict(enumerate(rcs)), ccs):
        cs = list(map(join, zip(*rs)))
        # rows and columns are all different
        if len(union([rs, cs])) != 10: continue
        # check the columns: exactly 1 is a cube, the others are even or prime
        cbs = set()
        eps = set()
        for (i, x) in enumerate(cs):
          if x in cubes: cbs.add(i)
          if x in primes or x in evens: eps.add(i)
        if not (len(cbs) == 1 and len(eps) == 4 and (not cbs.issubset(eps))): continue
        # output solution
        for (t, vs) in zip(['rows', 'cols'], (rs, cs)):
          fmt = lambda vs: join(vs, sep=" | ", enc=("[ ", " ]"))
          printf("{t}: {vs} = {ns}", vs=fmt(vs), ns=tuple(roman2int(v) for v in vs))
        printf()
      

      Solution: The middle row is CCXVI (216). The middle column is LXXIX (79).

      The completed grid looks like this:

      Like

    • Jim Olson's avatar

      Jim Olson 6:30 pm on 29 March 2022 Permalink | Reply

      Typo on the last column. Should be “23” which is still a prime number.

      Like

  • Unknown's avatar

    Jim Randell 4:35 pm on 25 March 2022 Permalink | Reply
    Tags: ,   

    Teaser 3105: Roman primes 

    From The Sunday Times, 27th March 2022 [link] [link]

    Romulus played a game using several identical six-sided dice. Each die face shows a different single-character Roman numeral. He rolled two dice and was able to form a prime number in Roman numerals by arranging the two characters. Romulus rolled more dice and, after each roll, formed a prime number with one more character, rearranging the sequence as needed, until he could no longer form a prime number less than 100. He was using standard notation where a character before another that is 5 or 10 times larger is subtracted from the larger one, e.g., IX = 9.

    After playing many games he realised that there were exactly three primes less than 100 that could not occur in any of the sequences.

    In decimal notation and in ascending order, what were those prime numbers?

    I found two different scenarios that fit the puzzle text, but lead to two different answers. So I have marked the puzzle as flawed.

    [teaser3105]

     
    • Jim Randell's avatar

      Jim Randell 5:28 pm on 25 March 2022 Permalink | Reply

      To represent numbers from 1 to 99 using Roman numerals requires five characters I, V, X, L, C. So we know those must be on the dice. The other symbol is probably D (= 500), which lets us express numbers up to 899 (with sufficient dice; it takes 12 to make 888 = DCCCLXXXVIII).

      I’m assuming that Romulus rolls 2 dice, arranges them to make the first prime in the sequence. Then rolls another single die, and arranges the 3 dice (without changing the numerals shown by the first two) to make the second prime, and so on. Rolling a single new die at each step until he is unable to rearrange the dice to make a prime, or he runs out of dice.

      Then we can find a scenario where there are three primes that cannot occur in any sequence.

      This Python program runs in 51ms.

      Run: [ @replit ]

      from enigma import (primes, int2roman, group, join, multiset, printf)
      
      # primes less than 100
      prms = list(primes.between(2, 99))
      
      # record primes by their roman numeral content
      d = group(prms, by=(lambda n: join(sorted(int2roman(n)))))
      
      # find length n extensions of ks in d
      def extend(d, ks, n):
        ss = list(multiset.from_seq(k) for k in ks)
        for k in d.keys():
          if len(k) == n:
            s = multiset.from_seq(k)
            if any(s.issuperset(s_) for s_ in ss):
              yield k
        
      # generate possible throws with increasing lengths
      def generate(d, n=2):
        # start with length n sequences
        ks = list(k for k in d.keys() if len(k) == n)
        while ks:
          yield (n, ks)
          # find keys that are one longer
          n += 1
          ks = list(extend(d, ks, n))
      
      # start with the complete set of primes
      ps = set(prms)
      for (n, ks) in generate(d, 2):
        # and remove those reachable after n dice
        for k in ks:
          ps.difference_update(d[k])
        # we have a solution if there are 3 primes remaining
        if len(ps) == 3:
          printf("{n} dice -> {ps}", ps=sorted(ps))
      

      Solution: The prime numbers are: 5, 37, 83.

      This is the solution in the scenario where Romulus has 6 dice, with the symbols I, V, X, L, C, and one other.

      5 (= V) only requires 1 die, so cannot be constructed using 2-6 dice.

      83 (= LXXXIII) requires 7 dice, so cannot be constructed using 2-6 dice.

      37 (= XXXVII) can be constructed using 6 dice, but there is no predecessor prime using 5 dice.

      Possible predecessor numbers for 37 are: 27, 32, 34, 46. None of which are prime.


      However I was able to find another scenario (see below), where Romulus has more than 6 dice, with the symbols I, V, X, L, and two others, that do not include C.

      In this scenario 5 and 37 cannot be constructed (as above), but 83 can be constructed using 7 dice.

      However the standard representation of 97 in Roman numerals is XCVII, which cannot be constructed if the symbol C is not available. (In fact none of the numbers in [90, 499] can be constructed with these dice).

      So the solution in this scenario is: 5, 37, 97.

      It seems that this second scenario is what the setter had in mind (it is the published answer), although it seems less plausible to me.

      Perhaps the following would have been a better representation of the intended puzzle:

      Romulus found a box containing a large number of identical six-sided dice. Each die face shows a different Latin character, and Romulus found that when he rolled some of the dice he was sometimes able to rearrange them so that the top faces formed a Roman numeral (using standard notation).

      He played a game where he rolled two dice and was able to form a prime number by arranging the two characters. He then rolled another die and was able to arrange the three dice to form another prime number. He carried on rolling extra dice (one die each time), until he could no longer arrange the dice to form a prime number less than 100.

      After playing many games he realised that there were exactly three primes less than 100 that could not occur in any of the sequences.

      In decimal notation and in ascending order, what were those prime numbers?


      The published solution is: “5, 37 and 97”.

      Like

    • Robert Brown's avatar

      Robert Brown 7:39 am on 26 March 2022 Permalink | Reply

      When the text says ‘after many games’ I assumed that some of these would start with II (=2) and some with XI (=11). Clearly cannot find 5 (V) as it is length 1, but I only have one more prime which cannot be made with one of the two starting pairs.

      Like

      • Jim Randell's avatar

        Jim Randell 8:57 am on 26 March 2022 Permalink | Reply

        @Robert: It looks like you are 2/3 of the way to the answer.

        There is a scenario that satisfies the wording of the puzzle text, and there are three primes that are not constructible. And each of the three primes is non-constructible for a different reason.

        Like

    • Jim Randell's avatar

      Jim Randell 12:51 pm on 26 March 2022 Permalink | Reply

      I think there is potentially an alternative scenario that also gives three non-constructible primes:

      If the dice have the symbols I, V, X, L, D, M on them (so not C), then one of the primes is not constructible (using “standard” Roman numerals), no matter how many dice are used.

      We can modify the program for this scenario by only considering primes that don’t include C when constructing the dictionary d:

      # record constructible primes by their roman numeral content
      d = group(prms, by=(lambda n: join(sorted(int2roman(n)))), st=lt(90))
      

      Or here is a version of my code that tries all possible combinations of 6 of the 7 symbols I, V, X, L, C, D, M for the dice [ @replit ], it finds three possibilities corresponding to the two scenarios outlined above.

      from enigma import (primes, int2roman, group, join, multiset, subsets, printf)
      
      # primes less than 100
      prms = list(primes.between(2, 99))
        
      # find length n extensions of ks in d
      def extend(d, ks, n):
        ss = list(multiset.from_seq(k) for k in ks)
        for k in d.keys():
          if len(k) == n:
            s = multiset.from_seq(k)
            if any(s.issuperset(s_) for s_ in ss):
              yield k
      
      def generate(d, n=2):
        # start with length n sequences
        ks = list(k for k in d.keys() if len(k) == n)
        while ks:
          yield (n, ks)
          # find keys that are one longer
          n += 1
          ks = list(extend(d, ks, n))
      
      # solve the puzzle for allowable symbols
      def solve(symbols):
      
        # record primes their roman numeral content
        d = group(prms, by=(lambda n: join(sorted(int2roman(n)))))
      
        # remove keys with invalid symbols
        d = dict((k, v) for (k, v) in d.items() if symbols.issuperset(k))
        
        # start with the complete set of primes
        ps = set(prms)
        for (n, ks) in generate(d, 2):
          # remove those reachable after n dice
          for k in ks:
            ps.difference_update(d[k])
          # we have a solution if there are 3 primes remaining
          if len(ps) == 3:
            printf("{syms}: {n} dice -> {ps}", syms=join(sorted(symbols)), ps=sorted(ps))
      
      # choose 6 symbols for the dice
      for syms in subsets('IVXLCDM', size=6, fn=set):
        solve(syms)
      

      I think I prefer the original scenario given above, where a sufficient number of dice can be used to give the numbers from 1 to 899. A set of dice without C would only be able to go consecutively up to 89 (the next smallest constructible number would be 500). D and M don’t come into play until 400 and 900 respectively.

      Like

      • Jim Randell's avatar

        Jim Randell 9:58 am on 1 April 2022 Permalink | Reply

        Depending on the shape of the glyphs used on the dice, it may be possible to use a V on its side to represent C, which would leave only 2 primes non-constructible in this second scenario (unless the number of dice is limited – and then we get the same solution as my first scenario).

        Like

    • Hugh+Casement's avatar

      Hugh+Casement 1:21 pm on 26 March 2022 Permalink | Reply

      I came to the same conclusion as Robert. I feel the setter of this puzzle has played a trick on us, but Jim rumbled it (before he came up with the alternative scenario ). It would have been neater, to my mind, if the puzzle text had stated that there were just two primes less than 100 that could not occur.

      Like

      • Jim Randell's avatar

        Jim Randell 3:58 pm on 26 March 2022 Permalink | Reply

        There’s definitely some trickery going on, as what you might expect to be the normal interpretation does not give 3 non-constructible primes.

        We would need to have more information about the symbols or number of dice to work out which scenario the setter had in mind.

        Like

  • Unknown's avatar

    Jim Randell 7:40 am on 24 March 2022 Permalink | Reply
    Tags:   

    Teaser 2859: Palindromic 

    From The Sunday Times, 9th July 2017 [link] [link]

    I have assigned to each letter of the alphabet a different number from 0 to 25. Therefore, for example, a three-letter word might stand for a number of three, four, five or six digits. In fact all the letters used in PALINDROMIC have even values. Furthermore, the number represented by this word contains no zeros and is indeed palindromic.

    Find the number represented by PIN.

    [teaser2859]

     
    • Jim Randell's avatar

      Jim Randell 7:41 am on 24 March 2022 Permalink | Reply

      The representation of a word is the concatenation of the numbers representing each letter.

      There are only 10 letters present in PALINDROMIC, and there are only 10 even values that don’t contain the digit 0.

      We can use a short program to consider all possible assignments to of values to letters.

      It is not a spectacularly fast approach, but I think in this case the simplicity of the program outweighs the desire for optimisation.

      The following Python program runs in 1.69s.

      from enigma import (irange, subsets, is_palindrome, join, printf)
      
      # collect values
      vs = set(s for s in map(str, irange(2, 24, step=2)) if '0' not in s)
      
      # assign symbols to values
      for (P, A, L, I, N, D, R, O, M, C) in subsets(vs, size=10, select="P"):
        vs = (P, A, L, I, N, D, R, O, M, I, C)
        if is_palindrome(join(vs)):
          fmt = lambda s: join(s, sep=":") + " = " + join(s)
          printf("PALINDROMIC = {s1} [PIN = {s2}]", s1=fmt(vs), s2=fmt((P, I, N)))
      

      Solution: PIN = 24412.

      There are 2 ways to assign the values to the letters:

      PALINDROMIC = 24:6:18:4:12:22:14:8:16:4:2 = 24618412221481642; PIN = 24:4:12 = 24412
      PALINDROMIC = 24:8:16:4:12:22:14:6:18:4:2 = 24816412221461842; PIN = 24:4:12 = 24412

      In the first case we have A:L = 6:18 and O:M = 8:16.

      In the second case we have A:L = 8:16 and O:M = 6:18.

      But both cases give the same value for PIN.

      Like

      • Jim Randell's avatar

        Jim Randell 7:45 am on 24 March 2022 Permalink | Reply

        If we build up the values for the letters starting at the beginning and end of PALINDROMIC we can discard candidates that will not form a palindrome without having to assign the remaining letters.

        Here I have used the [[ SubstitutedExpression ]] solver from the enigma.py to keep things compact.

        Checking values (P, C), (PA, IC), (PAL, MIC) cuts the run time down to 86ms.

        #! python3 -m enigma -rr
        
        SubstitutedExpression
        
        --base=26
        --digits="2,4,6,8,12,14,16,18,22,24"
        
        # we only need this
        "is_palindrome(concat(P, A, L, I, N, D, R, O, M, I, C))"
        
        # but these conditions speed things up
        --code="check = lambda x, y: zip_eq(x, reverse(y))"
        "check(concat(P), concat(C))"
        "check(concat(P, A), concat(I, C))"
        "check(concat(P, A, L), concat(M, I, C))"
        
        # answer to the puzzle
        --answer="concat(P, I, N)"
        
        # [optional] tidy up output
        --template=""
        

        Like

  • Unknown's avatar

    Jim Randell 11:44 am on 22 March 2022 Permalink | Reply
    Tags:   

    Teaser 2734: Interlocking squares 

    From The Sunday Times, 15th February 2015 [link] [link]

    Place all of the digits 0 to 9 in the grid so that, reading across or down in crossword fashion, one can see a two-figure square, a three-figure square, and two four-figure squares.

    What (in increasing order) are the four squares?

    [teaser2734]

     
    • Jim Randell's avatar

      Jim Randell 11:45 am on 22 March 2022 Permalink | Reply

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

      The following run file executes in 114ms.

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      #  # A # #
      #  B C D E
      #  # F # G
      #  H J # K
      
      SubstitutedExpression
      
      # across
      "is_square(BCDE)"
      "is_square(HJ)"
      
      # down
      "is_square(ACFJ)"
      "is_square(EGK)"
      
      # answer
      --answer="ordered(BCDE, HJ, ACFJ, EGK)"
      

      Solution: The squares are: 49, 576, 1089, 3025.

      (49, 576, 1089, 3025) = (7², 24², 33², 55²).

      Like

    • GeoffR's avatar

      GeoffR 2:33 pm on 22 March 2022 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      %    # A # #
      %    B C D E
      %    # F # G
      %    H J # K
      
      var 1..9:A; var 1..9:B; var 0..9:C; var 0..9:D;
      var 1..9:E; var 0..9:F; var 0..9:G; var 1..9:H;
      var 0..9:J; var 0..9:K;
      
      constraint all_different([A,B,C,D,E,F,G,H,J,K]);
      
      % sets of 2,3 and 4-digit squares
      set of int: sq2 = {n*n | n in 4..9};
      set of int: sq3 = {n*n | n in 10..31};  
      set of int: sq4 = {n*n | n in 32..99};  
      
      constraint (10*H + J) in sq2;
      constraint (100*E +10*G + K) in sq3;
      constraint (1000*A + 100*C + 10*F + J) in sq4 
      /\ (1000*B + 100*C + 10*D + E) in sq4;
      
      solve satisfy;
      
      output [ "[A,B,C,D,E,F,G,H,J,K] = " ++ show([A,B,C,D,E,F,G,H,J,K])];
      % [1, 3, 0, 2, 5, 8, 7, 4, 9, 6]
      % [A, B, C, D, E, F, G, H, J, K]
      % ----------
      % ==========
      % Squares : HJ = 49, EGK = 576, ACFJ = 1089, BCDE = 3025
      
      
      

      Like

    • GeoffR's avatar

      GeoffR 8:10 am on 23 March 2022 Permalink | Reply

      A three stage permutation solution.

      from itertools import permutations
      from enigma import is_square
      
      digits = set('1234567890')
      
      # two digit square HJ
      for p1 in permutations(digits, 2):
        h, j = p1
        if h == '0':continue
        hj = int(h + j)   
        if not is_square(hj):continue
        q1 = digits.difference({h, j})
          
        # three digit square EGK
        for p2 in permutations(q1, 3):
          e, g, k = p2
          if e == '0':continue
          egk = int(e + g + k)
          if not is_square(egk):continue
              
          # two four digit squares BCDE and ACFJ
          q2 = q1.difference({e, g, k})
          for p3 in permutations(q2):
            a, b, c, d, f = p3
            if '0' in (a, b): continue
            bcde = int(b + c + d + e)
            if is_square(bcde):
              acfj = int(a + c + f + j)
              if is_square(acfj):
                print(f"HJ={hj}, EGK={egk}, ACFJ={acfj}, BCDE={bcde}")
                        
      # HJ=49, EGK=576, ACFJ=1089, BCDE=3025
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 8:29 am on 20 March 2022 Permalink | Reply
    Tags: by: S. T. Shovelton   

    Brain Teaser: An Oxford medley 

    From The Sunday Times, 21st December 1958 [link]

    Five men are up at the five colleges at which their fathers were undergraduates, though no one son is at his father’s old college.

    Each of the men spent part of the long vac as a guest at the home of one of the others and as host to another. Their five home towns are the namesakes of the five colleges, though in no case is a man’s home town, or the home town of the man he visited, the namesake of his own college or of his father’s old college.

    Jones plays soccer for the Varsity; so do the Hertford and Pembroke men, and the man who lives at Worcester. The man who lives at Exeter visited the town which is the namesake of the college at which Smith is an undergraduate. The man who visited Exeter plays fives with Jones and lives in the town which is the namesake of the college at which Robinson is an undergraduate. The Exeter man visited Jones in the long vac. The man whose father was at Exeter is at the college of which Robinson’s father was an undergraduate; it is the namesake of Black’s home town.

    What is the name of the man who was the guest in the long vac of the man whose home town is the namesake of the college at which the father of the Worcester man was an undergraduate?

    This one of the occasional Holiday Brain Teasers published in The Sunday Times prior to the start of numbered Teasers in 1961. A prize of £5 was offered.

    [teaser-1958-12-21] [teaser-unnumbered]

     
    • Jim Randell's avatar

      Jim Randell 8:33 am on 20 March 2022 Permalink | Reply

      There is one college/town not mentioned in the puzzle text (I denote it with X), and also the surname of one of the students is not mentions (I denote it with Y).

      If we imagine a table with the columns representing values that are college/town names for each of the students (J, S, R, B, Y), and the rows representing the following values:

      c = college attended by the student
      t = home town of the student
      v = town visited by the student during the long vac
      f = collect attended by the student’s father

      Then each row is a permutation of the available college/town names (E, H, P, W, X) and each column consists of 4-different values.

      So each row is a derangement of the previous rows.

      This Python program runs in 139ms.

      Run: [ @replit ]

      from enigma import (irange, join, printf)
      
      # labels for colleges/towns
      labels = "HPWEX"
      
      # indices for the students
      students = (J, S, R, B, Y) = irange(5)
      
      # produce an arrangement of values from <vs>, not already in maps <ms>
      # return a forward map (array) and a reverse map (dict)
      def derange(vs, ms, xs=[]):
        # are we done?
        if not vs:
          yield (tuple(xs), dict((x, i) for (i, x) in enumerate(xs)))
        else:
          # choose a value for slot k
          k = len(xs)
          for (i, x) in enumerate(vs):
            if all(m[k] != x for m in ms):
              yield from derange(vs[:i] + vs[i + 1:], ms, xs + [x])
      
      # assign colleges to the students
      # c: map student -> college
      for (c, c_) in derange(labels, []):
      
        # "J plays soccer... so do the H and P men"
        # "the E man visited J during the long vac"
        # so, J is not at H, P, E
        if c[J] in 'HPE': continue
      
        # assign towns to the students
        # t: map student -> town
        for (t, t_) in derange(labels, [c]):
      
          # the man who live at W is not J, or the H or P man
          if t[J] == 'W': continue
          if c[t_['W']] in 'HP': continue
      
          # assign visits to students
          # v: map student -> town
          for (v, v_) in derange(labels, [c, t]):
      
            # "the E man visited J"
            if v[c_['E']] != t[J]: continue
            
            # "the man who visits E plays fives with J..."
            # so J did not visit E
            if v[J] == 'E': continue
            # "... and lives in the town which shares a name with the R's college"
            if t[v_['E']] != c[R]: continue
      
            # "the man who lives at E visited the town which shares a name with S's college"
            if v[t_['E']] != c[S]: continue
      
            # assign father's colleges to students
            # f: map student -> college
            for (f, f_) in derange(labels, [c, t, v]):
      
              # "the man whose father was at E is at the college attended by R's father ..."
              if c[f_['E']] != f[R]: continue
              # "... which shares a name with B's town"
              if f[R] != t[B]: continue
      
              # "what is the name of the man who was the guest of the man
              # whose town is the namesake of the college at which the
              # father of the W man was an undergraduate"
              r = v_[f[c_['W']]]
      
              # output solution
              printf("[   J S R B Y]")
              printf("[c: {c}]", c=join(c, sep=" "))
              printf("[t: {t}]", t=join(t, sep=" "))
              printf("[v: {v}]", v=join(v, sep=" "))
              printf("[f: {f}]", f=join(f, sep=" "))
              printf("answer = {r}", r="JSRBY"[r])
              printf()
      

      Solution: The answer is Smith.

      i.e. Smith was the guest of Robinson in Exeter (town) during the long vac. And Exeter is the college that Jones’s father attended, while Jones himself went to Worcester College (as did I).

      Like

    • Hugh+Casement's avatar

      Hugh+Casement 12:28 pm on 20 March 2022 Permalink | Reply

      I’m putting my money on Lincoln for the missing college, though there are a few other possibilities.

      If you’re looking for common surnames (for example to make up puzzles of your own), the top six in England are Smith, Jones, Williams, Taylor, Davies, and Brown. Robinson is no. 12, and I don’t think Black occurs in the first 50 (though Green and White are both among the first 25).

      Like

  • Unknown's avatar

    Jim Randell 4:43 pm on 18 March 2022 Permalink | Reply
    Tags:   

    Teaser 3104: Prime football 

    From The Sunday Times, 20th March 2022 [link] [link]

    There are more than 13 clubs in the Prime Football League, and each club plays each other twice during the football season, gaining three points for winning a match, and one point for a draw.

    At the end of last season, it was observed that the final numbers of points gained by the clubs were all different double-digit prime numbers. During the season our local club, Wessex Wanderers, won just three times as many matches as they lost. If you knew how many clubs were in the league, you could work out the final points total of Wessex Wanderers.

    How many clubs are in the league, and what was the final points total of Wessex Wanderers?

    [teaser3104]

     
    • Jim Randell's avatar

      Jim Randell 5:55 pm on 18 March 2022 Permalink | Reply

      We know there are more than 13 teams in the league, and there are only 21 primes between 10 and 99, so this puts an upper limit on the number of teams in the league.

      If there are n teams in the league, and each team plays every other team twice during a season, then there are a total of 2 × C(n, 2) matches during the season. And each team plays 2(n − 1) matches.

      So we can consider the number of draws d played by WW. The remaining matches must be 3/4 wins and 1/4 losses. So we can calculate p = WW’s points at the end of the season, and this must be a 2-digit prime number.

      We can then look to see if there is a scenario where the teams can all score a different 2-digit prime number of points, and if there is a way for this to occur then we have a viable (n, p) pair. (The program only checks that there is an n-subset of the primes, that includes p, and sums to a potentially viable total number of points awarded during the season. But it turns out this step doesn’t weed out any candidate solutions anyway, so a simpler program would find the same answer).

      This Python program looks for viable (n, p) pairs, and looks for solutions where if we knew n there is a unique value for p. It runs in 94ms.

      Run: [ @replit ]

      from enigma import (primes, irange, C, subsets, div, Record, filter_unique, printf)
      
      # 2-digit primes
      prms = set(primes.between(10, 99))
      
      # find a viable scenario
      def scenario(r):
        (n, w, d, l, p) = (r.n, r.w, r.d, r.l, r.p)
        # m = total number of number of matches
        m = 2 * C(n, 2)
        # consider possible total number of draws in all matches
        for td in irange(d, m - w - l):
          # calculate the total number of points awarded
          tp = 2 * td + 3 * (m - td)
          # can tp be made from an n-subset of primes (that includes p)?
          for ps in subsets(prms, size=n):
            if p in ps and sum(ps) == tp:
              # then this is a viable scenario
              printf("[n={n}; l={l} w={w} d={d}; p={p} -> ps={ps}]")
              yield ps
      
      # generate viable scenarios
      def generate():
        #  consider n = number of teams in the league
        for n in irange(14, len(prms)):
          # WW plays 2(n - 1) matches
          # if there are d draws, then the remaining matches are (3/4) win and (1/4) lost
          t = 2 * (n - 1)
          for l in irange(0, t // 4):
            w = 3 * l
            d = t - l - w
            # and calculate the points (a 2-digit prime)
            p = 3 * w + d
            if p not in prms: continue
      
            # is there a viable scenario?
            r = Record(n=n, w=w, d=d, l=l, p=p)
            for ps in scenario(r):
              yield Record.update(r, ps=ps)
              break
      
      # find solutions if we know n we can work out p
      for r in filter_unique(generate(), (lambda r: r.n), (lambda r: r.p)).unique:
        printf("n={r.n} p={r.p}")
      

      Solution: There are 18 clubs in the league. The final points total for Wessex Wanderers was 59.


      We find there are the following potential (n, p) pairs (grouped by n):

      n=14: p=31 (w=3, d=22); p=41 (w=9, d=14)
      n=15: p=43 (w=9, d=16); p=53 (w=15, d=8)
      n=17: p=37 (w=3, d=28); p=47 (w=9, d=20); p=67 (w=21, d=4)
      n=18: p=59 (w=15, d=14)
      n=19: p=41 (w=3, d=32); p=61 (w=15, d=16); p=71 (w=21, d=8)
      n=20: p=43 (w=3, d=34); p=53 (w=9, d=26); p=73 (w=21, d=10); p=83 (w=27, d=2)

      If each of these situations is viable then the answer is n=18, p=59, as this is the only one where knowing n gives a unique p value.

      And we can show that the n =18, p=59 situation is viable as follows:

      With 18 teams there are 2×C(18, 2) = 306 matches.

      One situation that gives each team a different 2-digit prime number of points is:

      1st: A; 97 pts = 32 wins (BCCDDEFFGGHHIIJJKKLLMMNNOOPPQQWW) + 1 draw (E)
      2nd: B; 79 pts = 25 wins (ADDEEGHHIIJKKLLMMNNOOPPQQ) + 4 draws (CCGJ)
      3rd: C; 73 pts = 21 wins (EEHHIKKLLMMNNOOPPQQWW) + 10 draws (BBDDFFGGIJ)
      4th: D; 71 pts = 22 wins(FFGGHHIJJKKLLMMNNOPPQQ) + 5 draws (CCEEO)
      5th: E; 67 pts = 19 wins (FHIJJKKLLMMNNOOPPQQ) + 10 draws (ADDFGGHIWW)
      6th: W; 59 pts = 15 wins (BBDDGGHHLLMMPQQ) + 14 draws (EEFFIJJKKNNOOP)
      7th: F; 53 pts = 13 wins (BBHHIINNOOPQQ) + 14 draws (CCEGGJJLLMMPWW)
      8th: G; 47pts = 10 wins (LLMMNOOPPQ) + 17 draws (BCCEEFFHHIIJJKKNQ)
      9th: H; 43 pts = 11 wins (KKLMNOOPPQQ) + 10 draws (EGGIIJJLMN)
      10th: I; 41 pts = 9 wins (DNOOPPQQW) + 14 draws (CEGGHHJJKLMMNW)
      11th: J; 37 pts = 6 wins (CMMPPQ) + 19 draws (BCFFGGHHIIKKNNOOQWW)
      12th: K; 31 pts = 5 wins (FFINN) + 16 draws (GGIJJLLMOOPPQQWW)
      13th: L; 29 pts = 5 wins (IJJQQ) + 14 draws (FFHIKKMMNNOOPP)
      14th: M; 23 pts = 3 wins (KOO) + 14 draws (FFHIIKLLNNPPQQ)
      15th: N; 19 pts = 1 win (Q) + 16 draws (GHIJJLLMMOOPPQWW)
      16th: O; 17 pts = 1 win (P) + 14 draws (DJJKKLLNNPQQWW)
      17th: P; 13 pts = 13 draws (FKKLLMMNNOQQW)
      18th: Q; 11 pts = 11 draws (GJKKMMNOOPP)

      This verifies that n =18, p=59 is indeed a solution to the puzzle.

      Although to show that it is the only solution would require showing that there are at least 2 viable (n, p) values for n = 14, 15, 17, 19, 20.

      I think this would be quite tedious to do by hand. But the program below verifies each of the potential situations given is viable, which means that n = 18 is the only solution.

      Like

      • Jim Randell's avatar

        Jim Randell 11:38 am on 20 March 2022 Permalink | Reply

        Here is a variation on the program above. It looks for a viable collection of matches that produces the required points for WW, and different prime numbers of points for each of the other teams.

        It uses a MiniZinc model (highlighted below) to look for viable scenarios, and it does take a while to check all possible (n, w, l, p) values, but it turns out each of them is viable, so a shorter program which doesn’t check for viability will produce the correct result.

        from enigma import (primes, irange, C, subsets, div, Record, filter_unique, update, sprintf, join, peek, printf)
        from minizinc import MiniZinc
        
        # 2-digit primes 
        prms = set(primes.between(10, 99))
        
        # check for a viable scenario (using MiniZinc)
        
        # the model
        model = """
        include "globals.mzn";
        
        % 2-digit primes
        set of int: primes = {prms};
        
        % number of teams
        int: n = {n};
        
        % decision table: x[i, j] = number of matches won by team i against team j
        array [1..n, 1..n] of var 0..2: x;
        
        constraint forall (i in 1..n) (x[i, i] = 0);
        constraint forall (i, j in 1..n where i < j) (x[i, j] + x[j, i] < 3);
        
        % calculate points for a team
        function var int: wins(var int: i) = sum (j in 1..n) (x[i, j]);
        function var int: loss(var int: i) = sum (j in 1..n) (x[j, i]);
        function var int: points(var int: i) = 2 * (n - 1 + wins(i)) - loss(i);
        
        % points for each team
        array [1..n] of var 10..99: pts;
        
        constraint forall (i in 1..n) (pts[i] = points(i) /\ pts[i] in primes);
        constraint all_different(pts);
        
        % specific constraints for team 1
        constraint pts[1] = {p} /\ wins(1) = {w} /\ loss(1) = {l};
        
        solve satisfy;
        """
        
        # default environment
        env = dict(primes=join(prms, sep=", ", enc="{}"))
        
        # check for a viable scenario
        def scenario(r):
          vs = update(env, Record.map(r).items())
          # create the model
          m = MiniZinc(sprintf(model, **vs), solver="minizinc --solver cbc")
          # is there a solution to the model?
          return peek(m.solve(), default=None)
          
        # generate viable scenarios
        def generate():
          #  consider n = number of teams in the league
          for n in irange(14, len(prms)):
            # WW plays 2(n - 1) matches
            # if there are d draws, then the remaining matches are (3/4) win and (1/4) lost
            t = 2 * (n - 1)
            for l in irange(0, t // 4):
              w = 3 * l
              d = t - l - w
              # and calculate the points (a 2-digit prime)
              p = 3 * w + d
              if p not in prms: continue
        
              # check for a viable scenario
              r = Record(n=n, w=w, d=d, l=l, p=p)
              if scenario(r):
                printf("[n={n}; d={d} w={w} l={l} p={p}]")
                yield r
        
        # find solutions if we know n we can work out p
        for r in filter_unique(generate(), (lambda r: r.n), (lambda r: r.p)).unique:
          printf("n={r.n} p={r.p} [{r}]")
        

        I found the mzn-g12mip solver and cbc solver gave run times of around 25s.

        Like

    • Alex T Sutherland's avatar

      Alex T Sutherland 3:39 pm on 21 March 2022 Permalink | Reply

      Number_of_ Teams = [14:21] ;     Teams_Count  = [0];
      Do for each Number_ of_ Teams
                     Calculate Number_of_ games_ played = g
                     Do for each Number_of_Losses [0 : g ]           This range can be shortened 
                              Wins= 3*Losses
                              Draws  = g - Wins -Losses
                              if Draws < 0
                                   continue  to next Loss
                              Points  = a*Losses + b*g                                       a & b can easily be derived 
                              if  Points are in prime  range (11 :97]   ;     if not continue to next Loss
                                    Record the data
                                    Increment the count for this team number
                      end 
      end
      

      From the record obtain the data for team number who has a count = 1
      My answer has (number of teams + their number of losses ) = prime number.
      Run time :- varies between 2 and 6 ms.

      Like

  • Unknown's avatar

    Jim Randell 10:23 am on 17 March 2022 Permalink | Reply
    Tags:   

    Teaser 2722: A simple sum 

    From The Sunday Times, 23rd November 2014 [link]

    I have written down two three-figure numbers and one four-figure number: between them they use each of the digits 0 to 9 exactly once. In fact the four-figure number is the sum of the other two numbers.

    If I told you how many of the three numbers were even, then it would be possible to work out the four-figure number.

    What is it?

    [teaser2722]

     
    • Jim Randell's avatar

      Jim Randell 10:24 am on 17 March 2022 Permalink | Reply

      This Python program uses the [[ SubstitutedExpression ]] solver, from the enigma.py library, to find possible sums, and then the [[ filter_unique ]] function to find those that give a unique result if we know the number of even numbers involved.

      It runs in 58ms.

      Run: [ @replit ]

      from enigma import (SubstitutedExpression, filter_unique, unpack, multiset, printf)
      
      # find viable alphametic sums
      p = SubstitutedExpression.split_sum(
        "ABC + DEF = GHIJ",
        extra=["A < D"], # remove duplicates
        answer="(ABC, DEF, GHIJ)",
      )
      
      # if we knew how many of the numbers were even, we could work out the result
      rs = filter_unique(
        p.answers(verbose=0),
        (lambda ns: sum(n % 2 == 0 for n in ns)),
        unpack(lambda x, y, z: z),
      )
      
      # output possible sums
      m = multiset()
      for (x, y, z) in rs.unique:
        printf("[{x} + {y} = {z}]")
        m.add(z)
      
      # output solution
      for (v, n) in m.most_common():
        printf("result = {v} [{n} sums]")
      

      Solution: The result of the sum is 1098.

      There are 4 possible sums:

      356 + 742 = 1098
      346 + 752 = 1098
      352 + 746 = 1098
      342 + 756 = 1098

      (And another 4 where the summands are swapped around).

      Like

    • Hugh+Casement's avatar

      Hugh+Casement 8:58 am on 18 March 2022 Permalink | Reply

      Either all three numbers are even, or only one of them is.

      If just one of the three-digit numbers is even, there are 24 possible sets,
      with sum 1035, 1053, 1305, 1503, or 1089.
      If only the four-digit number is even, there are 20 possible sets,
      with sum 1026, 1062, 1206, 1602, or 1098.

      Only if both three-digit numbers are even do we have a unique sum.

      Like

    • GeoffR's avatar

      GeoffR 2:59 pm on 18 March 2022 Permalink | Reply

      A MiniZinc program does indeed confirm that two even numbers are required to sum to a unique four digit number.

      % A Solution in MiniZinc
      include "globals.mzn";
       
      var 1..9:A; var 0..9:B; var 0..9:C;
      var 1..9:D; var 0..9:E; var 0..9:F;
      var 1..9:G; var 0..9:H; var 0..9:I; var 0..9:J;
      
      constraint all_different ([A,B,C,D,E,F,G,H,I,J]);
      
      var 100..999:ABC = 100*A + 10*B + C;
      var 100..999:DEF = 100*D + 10*E + F;
      var 1000..9999:GHIJ = 1000*G + 100*H + 10*I + J;
      constraint ABC > DEF;
      
      % confirm two even 3-digit numbers are needed 
      % to sum to a unique 4-digit number 
      constraint ABC mod 2 == 0 /\ DEF mod 2 == 0;
      constraint ABC + DEF == GHIJ;
      
      solve satisfy;
      output ["Sum is " ++ show(ABC) ++ " + " ++ show(DEF) 
      ++ " = " ++ show(GHIJ) ];
      
      % Sum is 756 + 342 = 1098
      % ----------
      % Sum is 752 + 346 = 1098
      % ----------
      % Sum is 746 + 352 = 1098
      % ----------
      % Sum is 742 + 356 = 1098
      % ----------
      % ==========
      
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 9:44 am on 15 March 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 661: The logical choice 

    From The Sunday Times, 10th March 1974 [link]

    Four members who hold office in the Logic Club approve of each other. They recently decided among themselves that next year each of the four would hold an office now held by one of the other three.

    Other members wanted to know whether this was legal and who was moving to which office. So we asked them to explain themselves under the Club’s Friday rules: these rules say that a member must either make two correct statements or two incorrect statements.

    We unfortunately forgot that we were questioning them on a Tuesday, when members may keep the Friday rules or break them, just as they please.

    The President said: “What we are doing is legal. The man who will be Chairman next year keeps the Friday rules on Tuesdays”.

    The Chairman said: “I am keeping the Friday rules. I shall not become Secretary next year”.

    The Secretary said: “The Treasurer will become President next year. I am not keeping the Friday rules”.

    The Treasurer said: “The man who will be Secretary next year does not keep the Friday rules on Tuesdays. What we are doing is legal”.

    Which of them will be next year’s Chairman? Which will be next year’s Treasurer? Is what they are doing legal?

    This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 2 (1981). The puzzle text above is taken from the book.

    [teaser661]

     
    • Jim Randell's avatar

      Jim Randell 9:45 am on 15 March 2022 Permalink | Reply

      If the questioning takes place on a Tuesday, where “members may keep the Friday rules (give two truth values the same) or break them (give two different truth values), just as they please”, to my mind this means the answers to the questions on a Tuesday can be any truth values, and we are none the wiser.

      I suspect we are meant to suppose that on a Tuesday the members either consistently keep the Friday rules (each pair of statements has the same truth value), or consistently break them (each pair of statements has one truth and one falsehood), and their pre-determined behaviour is known to the other officers. Then we can make progress.

      This Python program looks at all possible scenarios to find those which correspond to the described situation. It runs in 47ms.

      Run: [ @replit ]

      from enigma import (subsets, product, multiset, map2str, printf)
      
      # f = keeping Friday rules; x, y = statements
      check = lambda f, x, y: f == (x == y)
      
      # we can populate the following variables:
      #  j: map(current job -> new job);  p: map(new job -> current job)
      #  f: map(current job -> keeping Friday rules
      #  legal: boolean
      
      # collect results (<next C>, <next T>, <legal>)
      qs = multiset()
      
      # consider possible assignments
      people = (P, C, S, T) = "PCST"
      js = subsets(people, size=4, select="D")
      fs = subsets((0, 1), size=4, select="M")
      for (jv, fv, legal) in product(js, fs, (0, 1)):
        j = dict(zip(people, jv))
        p = dict(zip(jv, people))
        f = dict(zip(people, fv))
      
        # P: "is legal; next C keeps Friday rules
        if not check(f[P], legal, f[p[C]]): continue
        
        # C: "C is keeping Friday rules; C will not become S"
        if not check(f[C], f[C], j[C] != S): continue
      
        # S: "T will become P; S is not keeping Friday rules"
        if not check(f[S], j[T] == P, not f[S]): continue
      
        # T: next S does not keep Friday rules; is legal"
        if not check(f[T], not f[p[S]], legal): continue
        
        printf("[legal={legal} j={j} f={f}]", j=map2str(j, arr="->"), f=map2str(f))
        qs.add((p[C], p[T], legal))
      
      # output results
      for ((q1, q2, q3), n) in qs.most_common():
        printf("(1) {q1} -> C; (2) {q2} -> T; (3) legal = {q3} [{n} solutions]", q3=bool(q3))
      

      Solution:(1) The Secretary plans to become the next Chairman; (2) The President plans to become the next Treasurer; (3) It is not legal.

      The plan for the assignment of jobs is:

      P → T
      C → P
      S → C
      T → S

      They can choose to follow Friday rules or not as they wish, except P must be the opposite of S.

      Like

  • Unknown's avatar

    Jim Randell 4:15 pm on 11 March 2022 Permalink | Reply
    Tags:   

    Teaser 3103: Empowered 

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

    I have a rectangular garden whose sides are whole numbers of feet. Away from the edge, an exposed strip of ground, again a whole number of feet in width, runs straight across (not diagonally) from a shorter side of the garden to the other shorter side. I need to run an electrical cable along the ground, between two opposite corners of the garden. Where the cable crosses the exposed area, it has to be threaded through expensive linear ducting to avoid damage. Because of costs, whilst seeking to minimise the length of cable, my overriding concern is to minimise the length of ducting used.

    The straight-line distance between the two corners to be connected is 123 feet, but in minimising costs, the length of cable needed is a whole number of feet longer than this.

    What is the length of cable needed?

    [teaser3103]

     
    • Jim Randell's avatar

      Jim Randell 4:55 pm on 11 March 2022 Permalink | Reply

      The shortest amount of ducting is to cross the exposed area at right angles. The remaining length of cable required is then the diagonal of the garden with the exposed area removed.

      This Python program runs in 47ms.

      Run: [ @replit ]

      from enigma import (pythagorean_triples, irange, ihypot, printf)
      
      # look for pythagorean triples with hypotenuse 123
      for (x, y, z) in pythagorean_triples(123):
        if z != 123: continue
      
        # consider possible w = width of exposed area
        for w in irange(1, x - 1):
          # calculate d = length of cable required
          d = ihypot(x - w, y)
          if d is None: continue
          d += w
          # output solution
          printf("x={x} y={y} z={z}; w={w} d={d}")
      

      Solution: The total length of cable required is 127 feet.

      The garden is an x by y rectangle, where (x, y, 123) form a Pythagorean triple. So:

      x² + y² = 123²

      There is only one possible triple: (27, 120, 123).

      Also the width of the exposed area is w (where: w < x).

      And the amount of cable required is d we have:

      d = w + √((x − w)² + y²)
      (d − w)² = (x − w)² + y²

      So (x − w, y, d − w) is also a Pythagorean triple.

      The only triple with x < 27 and y = 120 is: (22, 120, 122).

      Hence:

      w = 5
      d = 127

      Like

    • GeoffR's avatar

      GeoffR 10:07 am on 12 March 2022 Permalink | Reply

      I looked at this teaser as two triangles with one above the horizontal strip and one below the horizontal strip. The cable length was then the sum of the two hypotenuses and the vertical crossing depth of the horizontal strip.

      It turns out that the two right angled triangles are the same, with dimensions (11, 60, 61).

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      % Main rectangle x by y with z as diagonal and x horizontal dimensions
      % Upper triangle is above horizontal strip (a, x1, h1) 
      % ... and lower triangle (below  horizontal strip)  is (b, x2, h2)
      
      % Cable length = Hypotenuse h1 + w(vertical) + Hypotenuse h2
      % Top triangle has vertical dimension (a) above horizontal strip 
      var 1..50:a; var 1..100:x1;  var 1..100:h1;
      
      int: z == 123; % main diagonal of rectangle
      var 1..200:x; var 1..100:y; % main rectangle dimensions
      
      % w = vertical depth of strip, c = cable length
      var 1..50:w; var 124..150:c;
      
      % Bottom triangle - vertical dimension (b) below horizontal strip
      var 1..50:b; var 1..100:x2;  var 1..100:h2; 
      
      constraint x*x + y*y == z*z;  % main rectangle
      constraint a*a + x1*x1 == h1*h1; % triangle above strip
      constraint b*b + x2*x2 == h2*h2; % triangle below strip
      
      constraint c == h1 + w + h2;  % cable length (> z)
      
      % Main rectangle dimensions and part side dimensions
      constraint y == a + b + w /\ x == x1 + x2;
      
      % minimise the length of ducting used
      solve minimize(w);
      output ["Length of cable needed = " ++ show(c) ++ " feet"];
      
      
      

      Like

      • Jim Randell's avatar

        Jim Randell 12:17 pm on 12 March 2022 Permalink | Reply

        @Geoff: Of course we don’t know that (a, x1, h1) and (b, x2, h2) are all integers. But we do know a+b and h1+h2 must be integers, so we can just consider (a+b, x, h1+h2) to find the solution.

        Like

    • GeoffR's avatar

      GeoffR 1:28 pm on 12 March 2022 Permalink | Reply

      @Jim:

      True, but it seemed a reasonable assumption at the time.

      The output from the programme verified my assumption, but I understand the technical point you make about these dimensions not being specifically stated as integers.

      We do know that the length of the cable(c) is a whole number of feet longer than the diagonal(z), and that c = h1 + w + h2. This suggested to me that it would be perhaps be unlikely for any of h1, w, or h2 to be floating point numbers. My two triangle approach also needs integers to work as Pythagorean triangles, of course.

      Like

    • GeoffR's avatar

      GeoffR 7:50 am on 14 March 2022 Permalink | Reply

      A simpler solution, based on Brian’s manual solution.

      % A Solution in MiniZinc
      include "globals.mzn";
       
      int: z == 123; % main diagonal of rectangle
      var 1..200:x; var 1..100:y; % main rectangle dimensions
       
      % d = duct length, c = cable length
      var 1..20:d; 
      var 124..150:c;
      
      constraint x * x + y * y = z * z;
      
      % Moving the strip to bottom of the rectangle, to give geometrical equivalency,
      % - the following formula can be derived:
      constraint d == (c * c - z * z) / (2 * (c - y));
      
      solve satisfy;
      output [ "Cable length = " ++ show(c) ++" feet"];
      
      
      

      Like

      • Jim Randell's avatar

        Jim Randell 12:56 pm on 14 March 2022 Permalink | Reply

        @Geoff: Yes, that is what I was getting at. There is no need to split the garden into two rectangles, when we can just consider the diagonal of the garden with the exposed area removed. (And in the general case, I don’t think it would always be possible to split the remaining garden into two rectangles with integer sides, and with an integer length of cable running through them, so it is lucky that it occurs in this instance).

        And we don’t even need to derive a formula for the width of the exposed area.

        Here’s my MiniZinc model that interprets my original program:

        %#! minizinc -a
        
        % garden is x by y (x < y), diagonal z
        int: z = 123;
        var 1..121: x;
        var 2..122: y;
        constraint  x < y;
        % (x, y, z) is a pythagorean triple
        constraint pow(x, 2) + pow(y, 2) = pow(z, 2);
        
        % exposed area width = w (< x)
        var 1..120: w;
        constraint w < x;
        
        % total length of cable = d
        var 124..245: d;
        % (x - w, y, d - w) is a pythagorean triple
        constraint pow(x - w, 2) + pow(y, 2) = pow(d - w, 2);
        
        solve satisfy;
        

        Like

    • Hugh+Casement's avatar

      Hugh+Casement 7:22 am on 21 March 2022 Permalink | Reply

      I find that a strange shape for a garden.
      A more realistic puzzle would have involved one 140 × 51 ft (diagonal 149 ft),
      with a path 3 ft wide, parallel to the long sides, that for practical reasons has to be traversed at right angles to its length.

      Like

  • Unknown's avatar

    Jim Randell 8:47 am on 10 March 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 682: Jigsaw 

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

    “Bend me your ears”, says Bell wittily at the pub. “I have here six cardboard squares all of different sizes and one extra rectangular piece, which is bigger than the smallest square but smaller than any of the other five”.

    “Now I fit them together as a jigsaw puzzle to make a complete rectangle. All the pieces measure an exact number of inches and nobody can make a smaller jigsaw out of any such seven pieces. Bigger and smaller, of course, means by areas”.

    “To help you I will tell you this table is 20 inches square, and the jigsaw, you can see, is smaller than that. For the first solution I shall be happy to award one pint”.

    What are the measurements of:

    (a) the six squares?
    (b) the extra piece?
    (c) the jigsaw?

    The setter is given as “the late W A Thatcher”.

    This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 2 (1981). The puzzle text above is taken from the book.

    [teaser682]

     
    • Jim Randell's avatar

      Jim Randell 8:48 am on 10 March 2022 Permalink | Reply

      This Python program uses the rectangle packing code rectpack.py, last seen in Teaser 2806.

      It considers possible values for the total area of the pieces, then sees if that area can be made from 6 squares and a rectangular piece, and then attempts to pack them into a rectangle that fits within the table.

      It runs in 261ms. (Internal runtime is 207ms).

      Run: [ @replit ]

      from enigma import (irange, inf, divisors_pairs, multiply, printf)
      from rectpack import (pack, output_grid)
      
      # construct a set of <k> square pieces and a rectangular piece of total area <t>
      # s = minimal side of square
      # rs = current rectangles
      def pieces(t, k, s=1, rs=[]):
        # are we done?
        if k == 0:
          if len(rs) > 1:
            # final piece is a rectangle, between the smallest squares
            if multiply(rs[0]) < t < multiply(rs[1]):
              for (x, y) in divisors_pairs(t):
                if x < y < 21:
                  yield rs + [(x, y)]
        else:
          # add in another square
          for x in irange(s, inf):
            x2 = x * x
            if t < k * x2 + 2: break
            yield from pieces(t - x2, k - 1, x + 1, rs + [(x, x)])
      
      # find a minimal solution
      def solve():
        # consider possible total areas
        for t in irange(93, 380):
          for (x, y) in divisors_pairs(t):
            if y > 20: continue
      
            for rs in pieces(t, 6):
              for ps in pack(y, x, rs):
                # output solution
                printf("t={t} x={x} y={y} -> {rs}")
                printf()
                output_grid(y, x, ps)
                printf()
      
                # we only need 1 packing
                return
      
      solve()
      

      Solution: (a) The six squares measure: 1×1, 4×4, 5×5, 6×6, 7×7, 8×8. (b) The extra piece is a 1×4 rectangle. (c) The jigsaw is 13×15.

      Here is the layout found by the program:

      Note that the 5×5, 4×4, 1×4 pieces form sub-rectangles that can be rearranged to give additional layouts.

      There are also solutions for a 15×17 jigsaw and a 17×19 jigsaw.

      Like

  • Unknown's avatar

    Jim Randell 9:24 am on 8 March 2022 Permalink | Reply
    Tags:   

    Teaser 2873: Circular logic 

    From The Sunday Times, 15th October 2017 [link] [link]

    Ten of us (me [Ian], Alice, Arnold, Carla, Celia, Clara, Ina, Rona, Ronald and Roland) were sitting equally-spaced around a circular table. None of us was directly opposite or next to anyone whose name was an anagram of theirs, or between two people whose names were anagrams of each other. The same applied when looking at the initial letters of the names.

    Then Ari and Ira joined us. We found two extra chairs and all budged up to make two spaces. With the twelve of us equally-spaced around the circular table all the above facts remained true. I was now opposite a different person, Roland.

    Who from the twelve was then directly opposite Alice? And who was opposite Celia?

    [teaser2873]

     
    • Jim Randell's avatar

      Jim Randell 9:26 am on 8 March 2022 Permalink | Reply

      We can look for viable 12-seat layouts, and then remove Ari and Ira to give a 10-seat layout, which we can check is viable.

      This Python program runs in 88ms.

      Run: [ @replit ]

      from enigma import (update, ordered, diff, join, printf)
      
      # implement a circular list (see Tantalizer 496)
      class CircularList(list):
      
        def __getitem__(self, i):
          return list.__getitem__(self, i % len(self))
      
        def copy(self):
          # list.copy() returns a list(), so re-wrap it
          return self.__class__(list.copy(self))
      
      # find names in <ns> that can be opposite/adjacent to <ps>
      def valid(ns, ps):
        # find disallowed initials and anagrams
        xis = set(p[0] for p in ps if p is not None)
        xas = set(ordered(*p) for p in ps if p is not None)
        for n in ns:
          if n[0] in xis or ordered(*n) in xas: continue
          yield n
      
      # place names <ns> in table <t>
      def place(t, ns):
        # are we done?
        if not ns:
          if t[1] < t[-1]:
            yield t
        else:
          # find the next unoccupied place
          i = t.index(None)
          # choose someone to occupy it
          for n in valid(ns, {t[i + 6], t[i - 1], t[i + 1], t[i - 2], t[i + 2]}):
            yield from place(update(t, [(i, n)]), ns.difference([n]))
      
      # create a 12-place table
      t = CircularList([None] * 12)
      
      # place IAN at position 0 and ROLAND in position 6
      t[0] = "IAN"
      t[6] = "ROLAND"
      
      # the remaining people
      people = { "ALICE", "ARNOLD", "CARLA", "CELIA", "CLARA", "INA", "RONA", "RONALD", "ARI", "IRA" }
      
      # find possible 12 place tables
      for t12 in place(t, people):
        # now remove ARI and IRA to give a 10 place table
        t = CircularList(diff(t12, {"ARI", "IRA"}))
        # check ROLAND is no longer opposite IAN
        if t[5] == "ROLAND": continue
        # check t is a valid table
        if not all(n in valid([n], {t[i + 5], t[i - 1], t[i + 1], t[i - 2], t[i + 2]}) for (i, n) in enumerate(t)): continue
        
        # output solution
        printf("{t12} <- {t10}", t12=join(t12, sep=" ", enc="[]"), t10=join(t, sep=" ", enc="[]"))
        for x in ["ALICE", "CELIA"]:
          opp = t[t.index(x) + 5]
          printf("-> ({x} <-> {opp})")
        printf()
      

      Solution: Rona ended up opposite Alice. Ira ended up opposite Celia.

      Here is a possible layout of the 12 seats (going round the table, listing opposites):

      IAN = 0; ROLAND = 6
      ARI = 1; CLARA = 7
      RONALD = 2; INA = 8
      CARLA = 3; ARNOLD = 9
      ALICE = 4; RONA = 10
      IRA = 5; CELIA = 11

      CARLA and CLARA can swap positions to give a second layout.

      And the tables can be mirrored (go round the table anti-clockwise, instead of clockwise) to give further viable layouts.

      Like

  • Unknown's avatar

    Jim Randell 4:43 pm on 4 March 2022 Permalink | Reply
    Tags:   

    Teaser 3102: Jokers 

    From The Sunday Times, 6th March 2022 [link] [link]

    A group of us wanted to play a card game. We had a standard 52-card pack but we needed to deal out a whole pack with each person getting the same number of cards, so I added just enough “jokers” to make this possible. Then I randomly shuffled the enlarged pack (in this shuffled pack there was more than a 50:50 chance that there would be at least two jokers together). Then I dealt the cards out, each of us getting the same number (more than three). There was more than a 50:50 chance that my cards would not include a joker.

    How many of us were there?

    [teaser3102]

     
    • Jim Randell's avatar

      Jim Randell 7:04 pm on 4 March 2022 Permalink | Reply

      I think I’ve got the probability calculations right.

      If there are n numbers and we choose k of them, then there are C(n, k) ways of doing this.

      And if we consider k-tuples of non-adjacent numbers, we can use the following map:

      (n[1], n[2], n[3], …, n[k]) ↔︎ (n[1], n[2] − 1, n[3] − 2, …, n[k] − k + 1)

      to put them into 1-1 correspondence with k tuples from (n − k + 1) numbers.

      So there are C(n − k + 1, k) of them. (See: Enigma 1029).

      So, when we think about n non-joker cards and j jokers, the probability of a non-adjacent shuffle is:

      C((n + j) − j + 1, j) / C(n + j, j) = C(n + 1, j) / C(n + j, j)

      And the probability of a hand of k cards not containing a joker is:

      (n / (n + j)) × ((n − 1) / (n + j − 1)) × … × ((n − k + 1) / (n + j − k + 1))

      The following Python program runs in 52ms. (Internal runtime is 229µs).

      Run: [ @replit ]

      from enigma import (Rational, irange, inf, divisors_pairs, multiply, C, printf)
      
      Q = Rational()
      h = Q(1, 2)
      
      def solve(N=52):
        # consider number of jokers added to the pack (at least 2)
        for j in irange(2, inf):
          # total number of cards in the pack
          n = N + j
      
          # probability of adjacent jokers is > 50%
          Pa = 1 - Q(C(N + 1, j), C(n, j))
          if not (Pa > h): continue
      
          # number of players k is a divisor of n; number of cards per player = p
          for (k, p) in divisors_pairs(n, every=1):
            if p < 4: break
            if N % k + j != k: continue
      
            # probability of a hand of p cards _not_ having a joker
            Ph = multiply(Q(N - i, n - i) for i in irange(0, p - 1))
            if not (Ph > h): continue
      
            # output solution
            printf("j={j} n={n}; k={k} p={p}; P(adj)={Pa:.3f} P(hand)={Ph:.3f}", Pa=float(Pa), Ph=float(Ph))
            return
      
      solve()
      

      Solution: There were 15 in the group.

      Which required 8 jokers adding to a standard pack, to make 60 cards in total. So each player receives 4 cards in the deal.

      The probability of no 2 jokers being adjacent when the cards are shuffled is:

      C(53, 8) / C(60, 8) = 886322710 / 2558620845 ≈ 34.64%

      So it is more likely that there will be at least one pair of adjacent jokers in the shuffled pack.

      And the probability of an individual hand of 4 cards not including a joker is:

      (52/60) × (51/59) × (50/58) × (49/57) ≈ 55.52%


      I also wrote code to simulate 1 million random trials with 52 non-joker cards and 8 jokers.

      import random
      from enigma import (Record, irange, join, fdiv, printf)
      
      # run N trials
      def run(N):
      
        # 52 non-jokers + 8 jokers
        cards = ('N' * 52) + ('J' * 8)
      
        # t = number of trials
        # a = number of shuffles with adjacent jokers
        # h = number of hands _not_ having a joker
        r = Record(t=0, a=0, h=0)
      
        # run a trial
        def trial(r):
          cs = list(cards)
          # shuffle the cards
          random.shuffle(cs)
          cs = join(cs)
          # collect stats
          r.t += 1
          if 'JJ' in cs: r.a += 1
          if 'J' not in cs[:4]: r.h += 1
      
        # run the trials
        for _ in irange(N):
          trial(r)
      
        # output results
        printf("{r.t} trials: adj = {r.a} ({a:.1%}), hand = {r.h} ({h:.1%})", a=fdiv(r.a, r.t), h=fdiv(r.h, r.t))
      
      # run 1 million trials
      run(1000000)
      

      The output of a typical run is:

      1000000 trials: adj = 654261 (65.4%), hand = 555384 (55.5%)
      

      Which match the calculated probabilities above.

      Like

      • Jim Randell's avatar

        Jim Randell 9:17 am on 5 March 2022 Permalink | Reply

        Using the same probability formulae, it is perhaps a bit neater to start by considering the number of players.

        Run: [ @replit ]

        from enigma import (Rational, irange, inf, ediv, C, multiply, printf)
        
        Q = Rational()
        h = Q(1, 2)
        
        def solve(N=52):
          # consider number of players k
          for k in irange(3, inf):
            # how many extra jokers do we need? (at least 2)
            j = -N % k
            if j < 2: continue
        
            # n = total number of cards
            # p = number of cards per player
            n = N + j
            p = ediv(n, k)
            if p < 4: continue
        
            # probability of adjacent jokers is > 0.5
            Pa = 1 - Q(C(N + 1, j), C(n, j))
            if not (Pa > h): continue
        
            # probability of a hand of p cards _not_ containing a joker is > 0.5
            Ph = multiply(Q(N - i, n - i) for i in irange(0, p - 1))
            if not (Ph > h): continue
        
            # output (and return solution)
            printf("k={k} j={j} n={n} p={p}; P(adj)={Pa:.3f} P(hand)={Ph:.3f}", Pa=float(Pa), Ph=float(Ph))
            yield (k, j, n, p)
        
        # find the first solution
        for _ in solve():
          break
        

        Like

      • Tony Brooke-Taylor's avatar

        Tony Brooke-Taylor 5:01 pm on 7 March 2022 Permalink | Reply

        I am still working through understanding your probability calculations (my problem) but I can confirm that a long-hand calculation of all possible deals produces the same P(adjacent jokers) as in your solution… in about 10 minutes.

        For small numbers of jokers relative to non-jokers, I think you can get away with approximating each pair as an independent sample of two cards from the expanded pack (with replacement). I don’t think this is quicker computationally, but it is easier to get my head around.

        Alternatively, by observing how P(no jokers in my hand) and P(adjacent jokers dealt) change with respect to the number of jokers, one might be able to infer the solution after calculating all possible joker counts that meet the P(no jokers in my hand) condition.

        Like

  • Unknown's avatar

    Jim Randell 8:57 am on 3 March 2022 Permalink | Reply
    Tags:   

    Teaser 2874: An age-old progression 

    From The Sunday Times, 22nd October 2017 [link] [link]

    It is my birthday today — the same day as two of my younger relatives, Betty and Charles. I commented that the digits involved in our three ages are all different. Betty noted that the square of her age is equal to my age multiplied by Charles’s age. Then Charles added that on one of our birthdays in the next ten years the sum of our ages will be one hundred.

    What are our three ages today?

    [teaser2874]

     
    • Jim Randell's avatar

      Jim Randell 8:58 am on 3 March 2022 Permalink | Reply

      We have:

      A > B, C
      B² = A⋅C (i.e. B is the geometric mean of A and C)
      A, B, C digits are all different
      A + B + C + 3n = 100, for some n = 1 .. 10

      We can get an upper bound on B by setting A = B = C:

      A + B + C ≤ 97
      3B ≤ 97
      B ≤ 32

      This Python program finds possible values for A, B, C. It runs in 47ms.

      Run: [ @replit ]

      from enigma import (irange, divisors_pairs, is_duplicate, div, printf)
      
      # consider values of B
      for B in irange(1, 32):
      
        # B^2 = A.C; C < A
        for (C, A) in divisors_pairs(B, 2):
          if not (C < B < A): continue
      
          # calculate n
          n = div(100 - (A + B + C), 3)
          if n is None or n < 1 or n > 10: continue
      
          # check for repeated digits
          if is_duplicate(A, B, C): continue
      
          # output solution
          printf("A={A} B={B} C={C}; n={n}")
      

      The program finds 2 possible solutions:

      B=8; C=1 A=64; n=9
      B=21; C=7 A=63; n=3

      The second of these seems the most likely as Charles joins in the conversation. (Although it would have been nice if the first case had been ruled out explicitly by the puzzle text).

      Solution: Angela is 63. Betty is 21. Charles is 7.

      We have 21² = 441 = 7 × 63 as required.

      And in 3 years time: (63 + 3) + (21 + 3) + (7 + 3) = 100.

      Like

  • Unknown's avatar

    Jim Randell 9:57 am on 1 March 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 907: Snakes & ladders 

    From The Sunday Times, 9th December 1979 [link]

    During my recent trip into the jungle, I came across a clearing, at the centre of which was a stone with the following design:

    On closer inspection, I saw that the small squares were numbered from 1 to 10 (left to right along the bottom row), then from 11 to 20 (right to left on the next row up), 21 to 30 (left to right on the third row up), and so on. The lines joined the following pairs of squares:

    13 & 32
    25 & 48
    35 & 54
    45 & 66
    63 & 88
    79 & 94

    My guide explained that it was a very old snakes and ladders board. However, due to the ravages of time, it was not possible to tell which of the six lines were snakes and which were ladders. Fortunately the guide knew a legend concerning the board, and he told it to me.

    Many years ago, the king of that region had a beautiful daughter, and offered her in marriage to the first man who could get from square 1 to square 100 in just one turn. After many young men had tried and failed, a handsome prince from a neighbouring country had his turn, and threw 12 consecutive sixes. As he stood on square 1 to start, the first six took him to square 7. The remaining sixes took him to square 100.

    Which of the lines are snakes?

    This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 2 (1981). The puzzle text above is taken from the book.

    It is also included in the book The Sunday Times Book of Brainteasers (1994).

    [teaser914]

     
    • Jim Randell's avatar

      Jim Randell 10:00 am on 1 March 2022 Permalink | Reply

      We start with 6 linked squares, but we don’t know which way they “teleport”.

      This Python program considers each roll of the dice, and progresses the player. If we reach an “unassigned” linked square we try both possible directions of teleportation. It runs in 49ms.

      Run: [ @replit ]

      from enigma import update, delete, printf
      
      # the linked squares
      links = [(13, 32), (25, 48), (35, 54), (45, 66), (63, 88), (79, 94)]
      
      # make a dict of potential "teleports"
      ps = dict()
      for (x, y) in links:
        ps[x] = y
        ps[y] = x
      
      # play the game
      # rs = remaining dice rolls
      # ps = potential teleports (src -> tgt)
      # ts = actual teleports (src -> tgt)
      # n = current position
      def solve(rs, ps, n=1, ts=dict()):
        # are we done?
        if not rs:
          if n == 100:
            yield (ts, ps)
        else:
          # add in the next roll
          n += rs[0]
          if n > 100: n = 100
          n = ts.get(n, n)
          # is it a potential teleport?
          t = ps.get(n)
          if t is not None:
            ps_ = delete(ps, [n, t])
            # choose to teleport
            yield from solve(rs[1:], ps_, t, update(ts, [(n, t)]))
            # choose not to teleport
            yield from solve(rs[1:], ps_, n, update(ts, [(t, n)]))
          else:
            # move on
            yield from solve(rs[1:], ps, n, ts)
      
      # solve for a finish in 12 throws of 6
      for (ts, ps) in solve([6] * 12, ps):
        for (s, t) in sorted(ts.items()):
          printf("{s} -> {t} {x}", x=("snake" if t < s else "ladder"))
        printf("remaining = {ps}")
        printf()
      

      Solution: The lines (32 → 13) and (66 → 45) are snakes.

      And the rest are ladders.

      So play proceeds:

      (6) 1 → 7
      (6) 7 → 13
      (6) 13 → 19
      (6) 19 → 25 (ladder) → 48
      (6) 48 → 54
      (6) 54 → 60
      (6) 60 → 66 (snake) → 45
      (6) 45 → 51
      (6) 51 → 57
      (6) 57 → 63 (ladder) → 88
      (6) 88 → 94
      (6) 94 → 100

      Like

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