Updates from Jim Randell Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 9:13 am on 25 October 2022 Permalink | Reply
    Tags:   

    Teaser 2698: Pond plants 

    From The Sunday Times, 8th June 2014 [link] [link]

    John bought some packs of pond plants consisting of oxygenating plants in packs of eight, floating plants in packs of four and lilies in packs of two, with each pack having the same price. He ended up with the same number of plants of each type. Then he sold some of these packs for twenty-five per cent more than they cost him. He was left with just fifty plants (with fewer lilies than any other) and he had recouped his outlay exactly.

    How many of these fifty plants were lilies?

    [teaser2698]

     
    • Jim Randell's avatar

      Jim Randell 9:14 am on 25 October 2022 Permalink | Reply

      If John ends up with L packs of lilies, F packs of floating plants and X packs of oxygenating plants, then we have:

      2L + 4F + 8X = 50

      And if he started out by buying a total of N packs, and selling some (at 25% markup) to cover the cost of the initial purchase, then we have:

      (5/4)(N − (X + F + L)) = N
      N = 5(X + F + L)

      And if he initially purchased n plants of each type we have:

      N = n/8 + n/4 + n/2 = (7/8)n

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

      Run: [ @replit ]

      from enigma import (express, div, printf)
      
      # consider the make up of the 50 remaining plants
      # L = lily packs, F = floating packs; X = oxygenating packs
      # 2L + 4F + 8X = 50
      for (L, F, X) in express(50, (2, 4, 8)):
        # there are fewer lilies than any other type of plant
        if not (2 * L < min(4 * F, 8 * X)): continue
        # calculate the initial number of packs bought
        N = 5 * (L + F + X)
        # calculate the initial number of plants of each type bought
        n = div(8 * N, 7)
        if n is None: continue
        # output solution (final number of lily plants)
        printf("{x} lily plants [L={L} F={F} X={X} -> N={N} n={n}]", x=2 * L)
      

      Solution: 14 of the remaining 50 plants were lilies.

      Initially John bought 80 of each type of plant (240 plants in total) = 10 packs of oxygenators + 20 packs of floating plants + 40 packs of lilies.

      Of these 70 packs he sold 8 packs of oxygenators + 15 packs of floating plants + 33 packs of lilies. Leaving him with 14 packs.

      The sale of these 56 packs at a 25% markup exactly met the initial cost of the 70 packs.

      Leaving John with 2 packs of oxygenators (= 16 plants) + 5 packs of floating plants (= 20 plants) + 7 packs of lilies (= 14 plants). A total of 50 plants.

      Like

  • Unknown's avatar

    Jim Randell 9:55 am on 23 October 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 177: The pay roll rules 

    From The Sunday Times, 30th August 1964 [link]

    I am the Managing Director of a factory and I have under me five employees. Their names are: Alf, Bert, Charlie, Duggie and Ernie. And their jobs are, not necessarily respectively: Doorkeeper, Doorknob Polisher, Bottle Washer, Welfare Officer and Worker.

    There has been some dissatisfaction recently about wages which, in the past, I am bound to admit, have sometimes been rather haphazard. It is clearly very difficult to arrange things in such a way that merit is appropriately rewarded, but it seemed to me important that everybody’s position should at least be clear. After much thought, therefore, I put up the following notice:

    Wages:

    1. Alf is to get more than Duggie.

    2. Ernie is to get 12 per cent more than the Bottle Washer will when he receives the 10 percent rise that he will be getting next month.

    3. The Doorknob Polisher is to get 30 per cent more than he used to.

    4. Charlie is to get £12 a year less than 20 per cent more than the Welfare Officer.

    5. No one is to get less than £200 or more than £600 a year.

    6. The Doorkeeper is to get 5 per cent more than he would if he got 10 per cent less than Bert.

    Everyone always has received in my factory, receives now, and as long as I am in charge will always receive an exact number of £s per year.

    What are the various jobs of my employees, and what yearly wage is each of them to get?

    This puzzle is included in the book Sunday Times Brain Teasers (1974). The puzzle text above is taken from the book.

    [teaser177]

     
    • Jim Randell's avatar

      Jim Randell 9:56 am on 23 October 2022 Permalink | Reply

      (See also: Teaser 811).

      I think the wording in this puzzle was slightly confusing.

      I am assuming that an unqualified wage referred to on the notice are the new wage that each employee is to receive immediately.

      However there is also a future wage referred to (the Bottle Washer will receive a 10% rise next month), and a previous wage (the Doorknob polisher receives 30% more than he used to).

      This time I used constraint satisfaction solver, so here is a MiniZinc model to solve the puzzle. It uses my minizinc.py library to provide a shortcut for allowing multiple variables with the same domain to be declared in one statement.

      %#! python3 -m minizinc use_embed=1
      
      include "globals.mzn";
      
      % wages by name: A, B, C, D, E
      {var("200..600", "ABCDE")};
      
      % wages by job: DK, DP, BW, WO, WK
      {var("200..600", ["DK", "DP", "BW", "WO", "WK"])};
      
      % the sets of values are the same
      constraint sort([A, B, C, D, E]) = sort([DK, DP, BW, WO, WK]);
      
      % 1. A gets more than D
      constraint A > D;
      
      % 2. In the future BW is to get a 10% increase ...
      constraint (BW * 110) mod 100 = 0;
      % ... and E (now) gets 12% more than this future amount
      constraint (BW * 112 * 110) mod (100 * 100) = 0;
      constraint E = (BW * 112 * 110) div (100 * 100);
      
      % 3. DP gets a 30% increase
      constraint (DP * 100) mod 130 = 0;
      
      % 4. C is to get 12 less than 20% more than WO
      constraint (WO * 120) mod 100 = 0;
      constraint C = (WO * 120) div 100 - 12;
      
      % 6. DK is to get 5% more than 10% less than B
      constraint (B * 90 * 105) mod (100 * 100) = 0;
      constraint DK = (B * 90 * 105) div (100 * 100);
      
      solve satisfy;
      

      And you can then run it like this:

      % python3 minizinc.py use_embed=1 teaser177.mzn
      A=378 B=400 C=468 D=250 E=308 DK=378 DP=468 BW=250 WO=400 WK=308
      

      Solution: The jobs and wages are as follows:

      Alf: Doorkeeper; £378
      Bert: Welfare Officer; £400
      Charlie: Doorknob Polisher; £468 (was £360)
      Duggie: Bottle Washer; £250 (future £275)
      Ernie: Worker; £308

      The originally published puzzle was pre-decimalisation, and gave the salaries in shillings per week, rather than pounds per year, but used the same values.

      Like

    • Hugh Casement's avatar

      Hugh Casement 11:08 am on 23 October 2022 Permalink | Reply

      I have yet to come across a good puzzle set by Eric Emmet.

      I think we have to assume that what the doorknob polisher “used to get” is what he currently gets, and that all the new wages come into effect next month.

      Like

      • Jim Randell's avatar

        Jim Randell 12:52 pm on 23 October 2022 Permalink | Reply

        @Hugh: I thought originally that everyone had a “before” and “after” value. But unless you have a “future” value for D (that comes after “after”), then you don’t get the published solution.

        Like

  • Unknown's avatar

    Jim Randell 4:27 pm on 21 October 2022 Permalink | Reply
    Tags:   

    Teaser 3135: Rhythmic gymnastics 

    From The Sunday Times, 23rd October 2022 [link] [link]

    Skaredahora used three rhythmic patterns of quaver beats in a short, purely percussive, composition. His “Dotykam” rhythm has accents on beats 1, 4, 6, 7, 8, 10 & 11; “Kluc” has accents on beats 1, 8 and one particular beat in between; and “Omacka” has accents on beats 1, 2, 5, 6 & 10. Several percussion instruments are involved, each playing one of the three rhythms, but starting at different times. Overall the patterns overlap, with every beat in the composition being filled by an accent from exactly one of the instruments, and all the patterns finishing by the end of the composition.

    What is the other beat of Kluc, and what is the order of appearance of the rhythmic patterns (e.g. DOOKD)?

    [teaser3135]

     
    • Jim Randell's avatar

      Jim Randell 4:51 pm on 21 October 2022 Permalink | Reply

      This Python program considers possible additional accent positions for pattern K, and then fills out patterns with an accent on every beat, but no overlaps, until there is a continuous sequence of accents.

      It runs in 54ms. (Internal runtime is 372µs).

      Run: [ @replit ]

      from enigma import (irange, inf, update, peek, printf)
      
      # the rhythm patterns
      D = [1, 4, 6, 7, 8, 10, 11]
      K = [1, None, 8]  # a beat in the range [2, 7] is missing
      O = [1, 2, 5, 6, 10]
      
      # disjoint union of two sets (or None)
      def disjoint_union(ss, xs):
        ss = set(ss)
        for x in xs:
          if x in ss: return
          ss.add(x)
        return ss
      
      # fill out patterns from <ps> with an accent on every beat
      # starting from <s>
      def solve(ps, s=1, vs=[], bs=set()):
        # we are done if there are no missing beats
        if bs and len(bs) == max(bs):
          yield vs
        else:
          # find the first missing beat
          b = peek(k for k in irange(s, inf) if k not in bs)
          # and choose a pattern to start here
          for (k, pattern) in ps.items():
            bs_ = disjoint_union(bs, (x + b - 1 for x in pattern))
            if bs_ is not None:
              yield from solve(ps, s + 1, vs + [(k, b)], bs_)
      
      # consider the missing beat in pattern K
      for k in irange(2, 7):
        for vs in solve(dict(D=D, K=update(K, [1], [k]), O=O)):
          printf("k={k} vs={vs}")
      

      Solution: Kluc has an additional accent on beat 5. The order of the patterns as: OOKKDDK.

      The composition lasts for 33 beats (or a multiple of 33 beats). The patterns being:

      O @ 1: (1, 2, 5, 6, 10)
      O @ 3: (3, 4, 7, 8, 12)
      K @ 9: (9, 13, 16)
      K @ 11: (11, 15, 18)
      D @ 14: (14, 17, 19, 20, 21, 23, 24)
      D @ 22: (22, 25, 27, 28, 29, 31, 32)
      K @ 26: (26, 30, 33)

      Which covers all beats from 1 – 33.

      In order for the composition to end after 33 beats with each beat being accented by exactly one of the instruments, we need pattern K to end after the last accented beat. Pattern D can have 0 or 1 non-accented beats after the last accented beat. And pattern O could have up to 21 non-accented beats after the last accented beat.

      Like

    • NigelR's avatar

      NigelR 10:47 am on 25 October 2022 Permalink | Reply

      Less elegant than Jim’s solution, but gets the job done!

      rhy = [[1, 4, 6, 7, 8, 10, 11],[1, 2, 8],[1, 2, 5, 6,10]] 
      patts=('DO','KL','OM')
      ntotxt = lambda k : [[patts[j[0]],j[1]] for j in k]  #makes print out more intelligible using labels
      score = lambda k : sorted([y+x[1]-1 for x in k for y in rhy[x[0]]]) # creates list of beat numbers filled
      gap = lambda k : sorted([x for x in range(1,len(k)+1) if x not in k]) # identifies gaps in beat sequence
      for n in range(2,8): # iterate for missing value in KL
          rhy[1][1] = n
          seq=[[0,1]] #Initialise seq.  Entries in seq are in format:[pattern no.,starting beat]
          while seq:
              beats=score(seq)
              if dup:=len(beats)-len(set(beats)): #if overlap of beats found, go back in sequence
                  while seq and seq[-1][0]==2:
                      seq.pop()                
                  if not seq:break
                  seq[-1][0]+=1   #try next pattern in exisiting sequence
              else: #no overlaps in current sequence
                  if g:=gap(beats):  # start next pattern at first gap in sequence
                      seq.append([0,g[0]])                
                  else: # if no gap and no overlaps, solution has been found
                      print('solution found: ',ntotxt(seq), '   n=',n)
                      exit()                         
          print('options exhausted for n='         ,n)
      

      Like

  • Unknown's avatar

    Jim Randell 10:18 am on 20 October 2022 Permalink | Reply
    Tags:   

    Teaser 2746: Five finger exercise 

    From The Sunday Times, 10th May 2015 [link] [link]

    George and Martha have a five-figure code for their burglar alarm. George commented that the three-figure number formed by the first three digits of the code equalled the sum of the cubes of those first three digits.

    Martha added that the three-figure number formed by the last three digits of the code equalled the sum of the factorials of those three digits. (She had to remind George what a factorial was — he remembered once she had pointed out that the factorial of 4 was 4×3×2×1 = 24).

    What is their code?

    This puzzle was not included in the book The Sunday Times Brain Teasers Book 1 (2019).

    This completes the archive of Teaser puzzles originally published in 2015. There is a complete archive of puzzles from 2015 – present available on S2T2, as wall as many older puzzles going back to 1949.

    [teaser2746]

     
    • Jim Randell's avatar

      Jim Randell 10:19 am on 20 October 2022 Permalink | Reply

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

      The following run file executes in 63ms. (The internal runtime of the generated program is 424µs).

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      --distinct=""
      --answer="ABCDE"
      
      "cb(A) + cb(B) + cb(C) = ABC"
      "factorial(C) + factorial(D) + factorial(E) = CDE"
      

      Solution: The code is: 37145.

      And we have:

      3³ + 7³ + 1³ = 371
      1! + 4! + 5! = 145

      Although not a condition of the puzzle, it turns out that the digits in the code are all different.

      Like

    • GeoffR's avatar

      GeoffR 10:47 am on 20 October 2022 Permalink | Reply

      from itertools import permutations
      from enigma import factorial as fact
      
      for p1 in permutations(range(1, 10), 5):
          A,B,C,D,E = p1
          if A**3 + B**3 + C**3 == 100*A + 10*B + C:
              if fact(C) + fact(D) + fact(E) == 100*C + 10*D + E:
                  code = 10000*A + 1000*B + 100*C + 10*D + E
                  print(f"Code is {code}.")
                             
      # Code is 37145.
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 8:40 am on 18 October 2022 Permalink | Reply
    Tags:   

    Teaser 2538: Octahedra 

    From The Sunday Times, 15th May 2011 [link] [link]

    Fabulé’s latest jewellery creation consists of a set of identically sized regular octahedra made of solid silver. On each octahedron, Fabulé has gold-plated four of its eight equilateral triangle faces. No two octahedra are the same, but if Fabulé had to make another, then it would be necessary to repeat one of the existing designs.

    How many octahedra are there in the set?

    [teaser2538]

     
    • Jim Randell's avatar

      Jim Randell 8:40 am on 18 October 2022 Permalink | Reply

      The octahedron is the dual of the cube, so colouring the faces of an octahedron is equivalent to colouring the vertices of a cube.

      I already have some code that deals with the rotations of the faces of the cube (see: Teaser 2835), so I used that to generate the rotations of an octahedron.

      We then consider all possible octahedra with 4 faces coloured gold and 4 coloured silver, and then remove those that are equivalent by rotation.

      The following Python program runs in 53ms. (Internal run time is 2.0ms).

      Run: [ @replit ]

      from enigma import (irange, subsets, arg, printf)
      from cube import Cube
      
      # make a cube with faces labelled in powers of 2
      fs = list((1 << i) for i in irange(0, 5))
      cube = Cube(faces=fs)
      
      # extract the vertices from a cube
      def vertices(cube):
        (U, D, F, B, L, R) = cube.faces
        return (
          U + F + L, U + F + R, U + B + R, U + B + L,
          D + F + L, D + F + R, D + B + R, D + B + L,
        )
      
      # map vertex values to indices
      m = dict((v, k) for (k, v) in enumerate(vertices(cube)))
      
      # construct the rotations of the faces of an octahedron
      rot8s = list()
      for x in cube.rotations():
        rot8s.append(list(m[v] for v in vertices(x)))
      
      # now on with the puzzle ...
      
      # canonical form of a colouring of the faces of the octahedron
      def canonical(fs):
        return min(tuple(fs[r[i]] for (i, _) in enumerate(fs)) for r in rot8s)
      
      # colour k of the faces
      k = arg(4, 0, int)
      # initial colouring
      fs = list(int(i < k) for i in irange(0, 7))
      # collect all possible permutations of the faces
      rs = set(canonical(s) for s in subsets(fs, size=len, select="mP"))
      
      printf("{k} faces -> {n} different octahedra", n=len(rs))
      

      Solution: There are 7 different octahedra.

      Like

    • Hugh Casement's avatar

      Hugh Casement 12:50 pm on 18 October 2022 Permalink | Reply

      I was thinking of the octahedron as two pyramids stuck together base to base, but treating its dual may be easier to visualize.

      The seven variants are then, for example:
      1. All four upper vertices.
      2 to 5. Three upper vertices and each in turn of the lower ones.
      6. Two adjacent upper vertices and their diametric opposites.
      7. Two opposite upper vertices and their diametric opposites.
      Any further patterns turn out to be repeats, rotated or reflected in one way or another (a cube has many axes of symmetry).

      If we allow ourselves any number of gold faces, from 0 to 8, then I think there are 23 variants in all.

      Like

      • Jim Randell's avatar

        Jim Randell 11:17 am on 19 October 2022 Permalink | Reply

        Yes. I’ve updated my program to allow you to specify the number of faces to be coloured:

        0 (or 8) → 1 octahedron
        1 (or 7) → 1 octahedron
        2 (or 6) → 3 octahedra
        3 (or 5) → 3 octahedra
        4 → 7 octahedra

        Which gives the 23 essentially different colourings.

        Like

    • Jim Olson's avatar

      Jim Olson 6:05 pm on 18 October 2022 Permalink | Reply

      I looked at this teaser the same as Hugh and came up with 23.

      Like

  • Unknown's avatar

    Jim Randell 4:00 pm on 15 October 2022 Permalink | Reply
    Tags: ,   

    Teaser 3134: Stringing along [revised] 

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

    An artist hammered thin nails from a pack of 40 into a board to form the perimeter of a rectangle with a 1 cm gap between adjacent nails. He created a work of art by stringing a long piece of wire from one nail to another, such that no section of wire was parallel to an edge of the rectangle. The wire started and ended at two different nails, no nail was used more than once and the length of the wire was a whole number of cm. No longer wire was possible that satisfied the above conditions.

    What were the dimensions of the rectangle and the length of the wire chain (in cm)?

    This is a revised version of the puzzle posted as Teaser 3134. The underlined text has been changed from the previously published version on The Sunday Times website.

    This is the version of the puzzle that appeared in the printed newspaper.

    [teaser3134]

     
    • Jim Randell's avatar

      Jim Randell 4:01 pm on 15 October 2022 Permalink | Reply

      Having solved the (more general) previously published version of this puzzle [link], it is a simple case of adapting my program to account for the additional condition.

      For this version I am assuming we want to find the maximum achievable total length of wire between the nails that can be made using a rectangle constructed from up to 40 nails, with the wire strung between nails where no nail is used more than once and consecutive nails are on different edges of the rectangle (i.e. each linear section of wire must cross part of the interior of the rectangle, and be a whole number of centimetres long), and no linear section of wire is parallel to the edges of the rectangle.

      You can think of the wire being available in various stiff lengths with looped ends, but these individual links can only ever fit between nails that are a whole number of centimetres apart. We wish to make a chain of these wire links, where each link goes from the end of the previous link to a currently unoccupied nail. What is the longest possible chain that can be made, on a rectangle whose perimeter is constructed from no more than 40 nails spaced 1 cm apart, where each link must cross the interior of the rectangle not parallel to the edges of the rectangle, and the start and end of the complete chain are on different nails.

      This Python program runs in 104ms.

      Run: [ @replit ]

      from enigma import (irange, ihypot, chain, Accumulator, printf)
      
      # generate possible <x> by <y> rectangles, using (up to) <n> nails
      def generate(n):
        for y in irange(2, n // 4):
          for x in irange(2, (n - 2 * y) // 2):
            yield (x, y)
      
      # find paths by adding nails to <vs>
      def solve(x, y, nails, vs, d=0):
        # return the current path
        yield (d, vs)
        # choose the next nail
        (x1, y1) = vs[-1]
        for v in nails:
          (x2, y2) = v
          (dx, dy) = (x2 - x1, y2 - y1)
          if dx == 0 or dy == 0: continue
          dd = ihypot(dx, dy)
          if dd is not None:
            yield from solve(x, y, nails.difference([v]), vs + [v], d + dd)
      
      # collect maximal distance paths
      r = Accumulator(fn=max, collect=1)
      
      # consider possible rectangles
      for (x, y) in generate(40):
        # collect possible edge nails
        nails = set()
        for i in irange(0, x - 1):
          nails.update([(i, 0), (x - i, y)])
        for i in irange(0, y - 1):
          nails.update([(0, y - i), (x, i)])
        # start in the bottom/left quadrant
        botm = ((i, 0) for i in irange(0, x // 2))
        left = ((0, i) for i in irange(1, y // 2))
        for v in chain(botm, left):
          for (d, vs) in solve(x, y, nails.difference([v]), [v]):
            r.accumulate_data(d, (x, y, vs))
      
      # output solution(s)
      printf("max wire length = {r.value} cm")
      for (x, y, vs) in r.data:
        printf("-> {x} cm by {y} cm grid {vs}")
      

      Solution: The rectangle was 12 cm × 8 cm. The total length of wire used was 102 cm.


      Here is a diagram of the maximal length layout:

      Like

      • Jim Randell's avatar

        Jim Randell 11:28 am on 28 October 2022 Permalink | Reply

        In my program above, in order to get a total distance that is a whole number we require the individual segments between consecutive pins in the stringing to be a whole number.

        This is a reasonable assumption. As we can show that if we have a collection of positive integers, and at least one of them has a square root that is irrational, then the sum of the square roots of the entire collection is irrational. (See below [*]).

        However, this does not mean we cannot construct stringings that are very close to an integer value using segments that are not themselves integers. And this lets us find solutions that are much longer than the published solution.

        For example here is a stringing on the 12cm × 8 cm grid that has a total length of 440.999925 cm (i.e. 750 nanometres short of 441 cm). It would be practically impossible to tell this apart from a 441 cm length of wire.

        Note that in this construction every pin is visited.

        If we want more accuracy we can get within 6nm of 438 cm.


        [*] The core of the proof is:

        Suppose x, y are integers, such that at least one of √x and √y are irrational.

        Then (x − y) is also an integer, and:

        (x − y) = (√x + √y)(√x − √y)

        If (√x + √y) is rational (= p), then:

        (√x − √y) = (x − y)/(√x + √y) is also rational (= q)

        But then:

        √x = (p + q)/2 is rational; and
        √y = (p − q)/2 is rational

        Which is a contradiction, hence the sum (√x + √y) is irrational.

        Like

    • Hugh Casement's avatar

      Hugh Casement 10:16 am on 16 October 2022 Permalink | Reply

      The change in wording makes quite a difference to the total length, at least with the solution I worked out.

      The puzzle does not seem to be well thought out. That the nails are thin clearly means that we are to ignore their diameter (and the thickness of the wire). But with centimetres as the unit they are not nails at all but pins, and it’s fine fuse wire. Inches would have been somewhat less unrealistic.

      I also feel that if the “artist” had allowed himself more nails, the resulting pattern could have been more interesting. For example, 12 occurs in the Pythagorean triangles (9, 12, 15) and (12, 16, 20) as well as (5, 12, 13), which would presumably give more scope. But the length + width of the rectangle must not exceed 20, so we are much restricted.

      Like

      • Jim Randell's avatar

        Jim Randell 12:03 pm on 17 October 2022 Permalink | Reply

        @Hugh: Yes for the original wording I found a maximal solution with 24 links. For this revised version there are only 10 links. The rectangle was the same in both cases.

        Like

  • Unknown's avatar

    Jim Randell 4:35 pm on 14 October 2022 Permalink | Reply
    Tags:   

    Teaser 3134: Stringing along 

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

    An artist hammered thin nails from a pack of 40 into a board to form the perimeter of a rectangle with a 1 cm gap between adjacent nails. He created a work of art by stringing a long piece of wire from one nail to another, such that consecutive nails were on different edges of the rectangle. The wire started and ended at two different nails, no nail was used more than once and the length of the wire was a whole number of cm. No longer wire was possible that satisfied the above conditions.

    What were the dimensions of the rectangle and the length of the wire chain (in cm)?

    The wording of this puzzle was later revised. The underlined section was changed to a more restrictive condition.

    See: Teaser 3134: Stringing along [revised] for the revised puzzle.

    [teaser3134]

     
    • Jim Randell's avatar

      Jim Randell 5:07 pm on 14 October 2022 Permalink | Reply

      (Note: It seems that my initial interpretation of the puzzle may not be the intended one. See below for a more likely interpretation).

      It seems we would need to know the dimensions of the rectangle before we determined the maximum length of wire. I considered all rectangles that can be constructed using 40 nails, and found the maximum possible length of wire that touches each edge of the rectangle no more than once.

      This Python program tries all possible rectangles, and all possible stringings.

      It runs in 275ms.

      Run: [ @replit ]

      from enigma import (irange, inf, subsets, tuples, hypot, intr, Accumulator, printf)
      
      # generate possible <x> by <y> rectangles, using <n> nails
      def generate(n):
        for y in irange(3, inf):
          x = (n - 2 * y) // 2
          if x < 3: break
          yield (x, y)
      
      # calculate length of wire required between points <vs>
      def dist(vs):
        d = 0
        for ((x1, y1), (x2, y2)) in tuples(vs, 2):
          d += hypot(x2 - x1, y2 - y1)
        if abs(d - intr(d)) < 1e-6:
          return d
      
      # collect maximal stringings
      r = Accumulator(fn=max, collect=1)
      
      # consider possible rectangles
      for (x, y) in generate(40):
        # choose top, bottom nails
        for (x1, x2) in subsets(irange(1, x - 1), size=2, select="R"):
          (T, B) = ((x1, y), (x2, 0))
          # choose left, right nails
          for (y1, y2) in subsets(irange(1, y - 1), size=2, select="P"):
            (L, R) = ((0, y1), (x, y2))
            # calculate possible lengths
            for vs in [(T, R, B, L), (T, R, L, B), (T, B, R, L)]:
              d = dist(vs)
              if d is None: continue
              printf("[({x}, {y}) {d:g} = {vs}]")
              r.accumulate_data(d, (x, y, vs))
      
      printf("max wire length = {r.value:g} cm")
      for (x, y, vs) in r.data:
        printf("-> {x} cm by {y} cm grid {vs}")
      

      Solution: The rectangle was 6 cm × 14 cm, and the wire was 37 cm long.


      This program finds what I assume is the required answer (where each section of the wire is an integer length). But by changing the tolerance at line 15 we can find a longer wire that is sufficiently close to an exact whole number of centimetres that it would be physically impossible to determine that it wasn’t.

      So we can create a stringing on a 6 cm × 14 cm rectangle that uses 40.0007 cm of wire.

      And also a stringing on a 4 cm × 16 cm rectangle that uses 44.99 cm of wire.

      Like

      • Jim Randell's avatar

        Jim Randell 11:19 pm on 14 October 2022 Permalink | Reply

        Using a different (and more likely) interpretation of the problem (see below), where each edge of the rectangle may be visited many times (and allowing the corner nails to be used), but each linear section of wire is a whole number of centimetres, we can get a much longer wire.

        To be clear: I am assuming we want to find the maximum achievable total length of wire between the nails that can be made using a rectangle constructed from up to 40 nails, with the wire strung between nails where no nail is used more than once and consecutive nails are on different edges of the rectangle (i.e. each linear section of wire must cross part of the interior of the rectangle, and be a whole number of centimetres long).

        Here is a quick program to explore that (although there may be some duplication in the patterns found).

        It runs in 942ms.

        Run: [ @replit ]

        from enigma import (irange, ihypot, chain, Accumulator, printf)
        
        # generate possible <x> by <y> rectangles, using (up to) <n> nails
        def generate(n):
          for y in irange(2, n // 4):
            for x in irange(2, (n - 2 * y) // 2):
              yield (x, y)
        
        # find paths by adding nails to <vs>
        def solve(x, y, nails, vs, d=0):
          # return the current path
          yield (d, vs)
          # choose the next nail
          (x1, y1) = vs[-1]
          for v in nails:
            (x2, y2) = v
            (dx, dy) = (x2 - x1, y2 - y1)
            if dx == 0 and (x1 == 0 or x1 == x): continue
            if dy == 0 and (y1 == 0 or y1 == y): continue
            dd = ihypot(dx, dy)
            if dd is not None:
              yield from solve(x, y, nails.difference([v]), vs + [v], d + dd)
        
        # collect maximal distance paths
        r = Accumulator(fn=max, collect=1)
        
        # consider possible rectangles
        for (x, y) in generate(40):
          # collect possible edge nails
          nails = set()
          for i in irange(0, x - 1):
            nails.update([(i, 0), (x - i, y)])
          for i in irange(0, y - 1):
            nails.update([(0, y - i), (x, i)])
          # start in the bottom/left quadrant
          botm = ((i, 0) for i in irange(0, x // 2))
          left = ((0, i) for i in irange(1, y // 2))
          for v in chain(botm, left):
            for (d, vs) in solve(x, y, nails.difference([v]), [v]):
              r.accumulate_data(d, (x, y, vs))
        
        # output solution(s)
        printf("max wire length = {r.value} cm")
        for (x, y, vs) in r.data:
          printf("-> {x} cm by {y} cm grid {vs}")
        

        Solution: The rectangle was 12 cm × 8 cm. The total length of wire used was 258 cm.


        Here is a diagram of one maximal length arrangement (there are several):

        Like

    • Brian Gladman's avatar

      Brian Gladman 9:56 pm on 14 October 2022 Permalink | Reply

      The answer for this one depends on the assumptions being made. I found a different answer by assuming that the wire length was exact and that not all nails are used. I then looked for a number of Pythagorean triangle hypotenuses with a maximum sum (not necessarily alternating x, y edges).

      Like

      • Jim Randell's avatar

        Jim Randell 10:51 pm on 14 October 2022 Permalink | Reply

        @Brian: I was assuming that each edge of the rectangle was only used once (and the corners not at all). But the puzzle text only says consecutive nails are on different edges, so if we can visit edges more than once then we can use much more wire. (And get a more artful display into the bargain).

        In this case I assumed distance between each consecutive pair of nails was an exact whole number of cm, so that the total length of the wire is as well.

        (Although it still seems like we would need to know the size of the rectangle the artist had constructed before we could find the maximum length of wire he could use).

        Like

  • Unknown's avatar

    Jim Randell 8:04 am on 13 October 2022 Permalink | Reply
    Tags:   

    Teaser 2737: Pinpoint accuracy 

    From The Sunday Times, 8th March 2015 [link] [link]

    George and Martha’s bank PIN is an odd four-figure number. George did some calculations and wrote down three numbers: the first was the sum of the four digits in the PIN; the second was the average of the four digits; and the third was the product of the four digits.

    Then Martha multiplied these three numbers together and was surprised that the answer equalled the original PIN.

    What is their PIN?

    This puzzle was not included in the book The Sunday Times Brain Teasers Book 1 (2019).

    [teaser2737]

     
    • Jim Randell's avatar

      Jim Randell 8:05 am on 13 October 2022 Permalink | Reply

      None of the individual digits can be 0, as then the product of the digits would also be 0.

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

      The following run file executes in 65ms. (Internal runtime of the generated code is 1.1ms)

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      --distinct=""
      --digits="1-9"
      --answer="ABCD"
      
      # The following multiplied together give the value of the PIN
      # (i) the sum of the digits;
      # (ii) the mean of the digits (= (i) / 4);
      # (iii) the product of the digits
      "sq(A + B + C + D) * (A * B * C * D) == 4 * ABCD"
      
      # the PIN is odd
      "D % 2 = 1"
      

      Solution: The PIN is: 1715.

      Like

    • GeoffR's avatar

      GeoffR 12:16 pm on 13 October 2022 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..9:A; var 1..9:B; var 1..9:C; var 1..9:D;
      constraint D mod 2 == 1; % PIN number is odd
      
      var 1000..9999:PIN = 1000*A + 100*B + 10*C + D;
      
      % Num 1the sum of the four digits in the PIN
      var 4..36:Num1 = A + B + C + D;
      
      var 4..36: Num2; %  average = Num2 / 4
      constraint Num2 == A + B + C + D;
      
      % Num3 was the product of the four digits
      var 1..6561: Num3 == A * B * C * D ; % UB = 9^4
      
      % Martha multiplied these three numbers together
      constraint 4 * PIN == Num1 * Num2 * Num3;
      
      solve satisfy;
      
      output[ "PIN = " ++ show(PIN) ];
      
      % PIN = 1715
      % ----------
      % ==========
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 8:46 am on 11 October 2022 Permalink | Reply
    Tags:   

    Teaser 2676: New diary 

    From The Sunday Times, 5th January 2014 [link] [link]

    My diary has this design on the cover:

    In this 2-by-3 grid there are 12 junctions (including the corners), some pairs of which are joined by a straight line in the grid. In fact there are 30 such pairs.

    The diary publisher has been using such grids of various sizes for years and the 1998 diary was special because its grid had precisely 1998 pairs of junctions joined by lines. Within the next 10 years they will once again be able to produce a special diary where the number of joined pairs equals the year.

    (a) What was the grid size on the 1998 diary?
    (b) What is the year of this next special diary?

    [teaser2676]

     
    • Jim Randell's avatar

      Jim Randell 8:47 am on 11 October 2022 Permalink | Reply

      In an x by y grid each horizontal line (of length x) has:

      1 pair that are distance x apart
      2 pairs that are distance (x − 1) apart
      3 pairs that are distance (x − 2) apart

      x pairs that are distance 1 apart

      Giving a total of tri(x) pairs on that line, and there are (y + 1) horizontal lines.

      So the total number of horizontal pairs is:

      h(x, y) = (y + 1) tri(x)

      Similarly the total number of vertical pairs is:

      v(x, y) = (x + 1) tri(y)

      And so the total number of pairs is:

      pairs(x, y) = h(x, y) + v(x, y)
      pairs(x, y) = (y + 1)x(x + 1)/2 + (x + 1)y(y + 1)/2
      pairs(x, y) = (x + 1)(y + 1)(x + y)/2

      This Python program runs in 54ms. (Internal runtime is 488µs).

      Run: [ @replit ]

      from enigma import (irange, inf, div, decompose, printf)
      
      # count pairs on an x by y grid
      pairs = lambda x, y: div((x + 1) * (y + 1) * (x + y), 2)
      
      # check the 3x2 grid gives 30 pairs
      assert pairs(3, 2) == 30
      
      # generate (x, y, pairs(x, y)) values
      def generate():
        # consider increasing x + y values
        for t in irange(2, inf):
          for (x, y) in decompose(t, 2, increasing=1, sep=0, min_v=1):
            yield (x, y, pairs(x, y))
      
      # find the answers
      a = b = 0
      for (x, y, n) in generate():
        # (a) look for grids with 1998 pairs
        if n == 1998:
          printf("(a) {x} x {y} -> {n}")
          a = 1
        # (b) looks for grid in the range [2015, 2024]
        if 2014 < n < 2025:
          printf("(b) {x} x {y} -> {n}")
          b = 1
        # are we done?
        if a and b: break
      

      Solution: (a) The 1998 diary had a 2 × 35 grid; (b) The next special diary is for 2016.

      We have:

      1998 = pairs(2, 35)
      2016 = pairs(5, 23) = pairs(11, 13)


      Alternatively we can start with the required number of pairs n and produce possible (x, y) grids, by considering the divisors of n.

      Which gives us a shorter program.

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

      Run: [ @replit ]

      from enigma import (divisors_pairs, irange, printf)
      
      def solve(n):
        for (a, b) in divisors_pairs(2 * n):
          for (x, y) in divisors_pairs(b - a - 1):
            if x + y == a:
              yield (x, y)
      
      # years to investigate
      qs = {
        'a': [1998],
        'b': irange(2015, 2024),
      }
      
      # solve the puzzle
      for k in sorted(qs.keys()):
        for n in qs[k]:
          for (x, y) in solve(n):
            printf("({k}) {x} x {y} -> {n}")
      

      Like

    • Hugh Casement's avatar

      Hugh Casement 3:18 pm on 11 October 2022 Permalink | Reply

      Of course 2016 is in the past for us, and the next will be 2025:
      1 × 44 or 4 × 26 or 8 × 17.

      However, I maintain that those are the sizes of the arrays of square cells;
      the grids (of lines) are 2 × 45, 5 × 27, and 9 × 18.

      Like

  • Unknown's avatar

    Jim Randell 8:18 am on 9 October 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 190: Towns and families 

    From The Sunday Times, 13th December 1964 [link]

    Cardiff and London share a line of latitude; Cardiff and Edinburgh share a line of longitude.

    The Archers, the Brewers, the Carters and the Drews are four married couples born and married in London, Cardiff, Edinburgh and Belfast. One of each sex was born in each city; one marriage took place in each city. No one was married in the city of his or her birth. Mrs Archer was the only woman married east of where she was born; Mr Archer was the only man married south of where he was born; Mr Brewer was the only man to marry a woman born north of him. Mr Carter and Mrs Drew were twins.

    Where were the Carters married?

    This puzzle is included in the book Sunday Times Brain Teasers (1974).

    [teaser190]

     
    • Jim Randell's avatar

      Jim Randell 8:18 am on 9 October 2022 Permalink | Reply

      This Python program tries all possible arrangements.

      It runs in 55ms. (Internal runtime is 790µs).

      Run: [ @replit ]

      from enigma import (subsets, printf)
      
      # Belfast, Cardiff, Edinburgh, London
      cities = "BCEL"
      
      # assign North and East values (approximate latitude and longitude)
      N = dict(C=51.5, L=51.5, B=54.6, E=56.0)
      E = dict(B=-5.9, C=-3.2, E=-3.2, L=-0.1)
      
      # choose cities of birth for the men
      for (mA, mB, mC, mD) in subsets(cities, size=len, select="P"):
      
        # choose cities of birth for the women
        for (fA, fB, fC, fD) in subsets(cities, size=len, select="P"):
      
          # "Mr C and Mrs D were twins" (presumably born in the same place)
          if not (mC == fD): continue
      
          # "Mr B was the only man to marry a woman born N of him"
          if not (N[fB] > N[mB]): continue
          if any(N[f] > N[m] for (m, f) in zip((mA, mC, mD), (fA, fC, fD))): continue
      
          # choose cities for marriages
          for (wA, wB, wC, wD) in subsets(cities, size=len, select="P"):
            # no-one was married in the city of their birth
            if any(w == m or w == f for (m, f, w) in zip((mA, mB, mC, mD), (fA, fB, fC, fD), (wA, wB, wC, wD))): continue
      
            # "Mrs A is the only woman married east of her birth"
            if not (E[wA] > E[fA]): continue
            if any(E[w] > E[f] for (f, w) in zip((fB, fC, fD), (wB, wC, wD))): continue
      
            # "Mr A is the only man married south of his birth"
            if not (N[mA] > N[wA]): continue
            if any(N[m] > N[w] for (m, w) in zip((mB, mC, mD), (wB, wC, wD))): continue
      
            printf("          A B C D")
            printf("husband = {mA} {mB} {mC} {mD}")
            printf("wife    = {fA} {fB} {fC} {fD}")
            printf("wedding = {wA} {wB} {wC} {wD}")
            printf()
      

      Solution: The Carters were married in Belfast.

      The full solution is:

      Archer: husband = Edinburgh; wife = Belfast; married = London
      Brewer: husband = London; wife = Edinburgh; married = Cardiff
      Carter: husband = Cardiff; wife = London; married = Belfast
      Drew: husband = Belfast; wife = Cardiff; married = Edinburgh

      Like

  • Unknown's avatar

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

    Teaser 3133: Primary road network 

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

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

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

    In increasing order, what were the three numbers?

    [teaser3133]

     
    • Jim Randell's avatar

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

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

      We can use Euler’s formula:

      V – E + F = 2

      where:

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

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

      Run: [ @replit ]

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

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


      We can construct a viable map as follows:

      Consider the following diagram:

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

      And together the central and surrounding areas contribute:

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

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

      0 vertices
      p edges
      p areas

      And a stalk of length s adds:

      s vertices
      s edges
      0 areas

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

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

      Which provides a viable map.

      Like

      • Jim Randell's avatar

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

        Using the formula:

        E = p + q − 1

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

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

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

        Run: [ @replit ]

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

        Like

    • Frits's avatar

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

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

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

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

      Like

    • Hugh Casement's avatar

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

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

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

      Like

    • GeoffR's avatar

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

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

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

      Like

  • Unknown's avatar

    Jim Randell 7:56 am on 6 October 2022 Permalink | Reply
    Tags:   

    Teaser 2750: Granny’s birthdays 

    From The Sunday Times, 7th June 2015 [link] [link]

    At Granny’s birthday this year she was telling us some surprising things about some past birthdays. She told us that each year she writes down the date of her birthday (in the eight-digit form dd/mm/yyyy) and her age in years.

    On two occasions in her lifetime it has turned out that this has involved writing each of the digits 0 to 9 exactly once. The first of these occasions was in 1974.

    What is Granny’s date of birth (in the eight-digit form)?

    Note that in order to solve this puzzle it is important to be aware of the date it was originally set.

    All 200 puzzles included in the book The Sunday Times Brain Teasers Book 1 (2019) are now available on S2T2.

    [teaser2750]

     
    • Jim Randell's avatar

      Jim Randell 8:00 am on 6 October 2022 Permalink | Reply

      The puzzle was originally set on 7th June 2015, and mentions Granny’s birthday “this year” as having already happened. So her birthday must be earlier in the year than 7th June.

      This Python program considers dates in 1974 up to 6th June, if the date includes 8 different digits, then the remaining 2 digits indicate Granny’s age (in some order), and we can then look for other years.

      The program runs in 59ms. (Internal runtime is 4.3ms)

      Run: [ @replit ]

      from datetime import (date, timedelta)
      from enigma import (irange, repeat, nsplit, union, subsets, nconcat, printf)
      
      digits = set(irange(0, 9))
      
      # consider dates earlier than this
      end = date(1974, 6, 7)
      
      # consider dates in 1974
      inc = lambda x, i=timedelta(days=1): x + i
      for d in repeat(inc, date(1974, 1, 1)):
        if not (d < end): break
        # remaining digits
        ds4 = union([nsplit(d.month, 2), nsplit(d.day, 2)])
        ds = digits.difference(nsplit(d.year, 4), ds4)
        if len(ds) != 2: continue
        # construct possible ages
        for ss in subsets(ds, size=2, select='P'):
          age = nconcat(ss)
          year = 1974 - age
          # collect "special" years
          years = list()
          for bd in irange(10, 99):
            y = year + bd
            if y > 2015: break
            if not digits.difference(nsplit(y, 4), ds4, nsplit(bd, 2)):
              years.append(y)
          if len(years) == 2 and years[0] == 1974:
            # output solution
            printf("{d} -> {years}", d=date(year, d.month, d.day).strftime("%d/%m/%Y"))
      

      Solution: Granny’s date of birth is: 26/05/1936.

      So Granny is 38 in 1974 → (26/05/1974, 38).

      And she is 47 in 1983 → (26/05/1983, 47).

      In 2015 (when the puzzle was set) she was 79.

      If we consider all dates in 1974 then there is a further solution of: 25/06/1936.

      So, the puzzle only has a unique solution if posed between 27th May and 24th June. A fact that was not mentioned when the puzzle was included in the book The Sunday Times Brain Teasers 1 (2019).

      Like

  • Unknown's avatar

    Jim Randell 8:11 am on 4 October 2022 Permalink | Reply
    Tags:   

    Teaser 2751: Red-handed 

    From The Sunday Times, 14th June 2015 [link] [link]

    I removed an even number of red cards from a standard pack and I then divided the remaining cards into two piles. I drew a card at random from the first pile and it was black (there was a whole-numbered percentage chance of this happening). I then placed that black card in the second pile, shuffled them, and chose a card at random from that pile. It was red (and the percentage chance of this happening was exactly the same as that earlier percentage).

    How many red cards had I removed from the pack?

    [teaser2751]

     
    • Jim Randell's avatar

      Jim Randell 8:11 am on 4 October 2022 Permalink | Reply

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

      Run: [ @replit ]

      from enigma import (irange, cproduct, div, printf)
      
      # start with 26 red, 26 black
      R = B = 26
      
      # remove an even (non-zero) number of red cards from the pack
      for k in irange(2, R, step=2):
      
        # pile 1 has r1 reds and b1 blacks (at least 1 black)
        for (r1, b1) in cproduct([irange(0, R - k), irange(1, B)]):
      
          # chance of drawing a black is a whole number percentage
          pb = div(100 * b1, r1 + b1)
          if pb is None: continue
      
          # a black card is moved to pile 2 which now has r2 reds and b2 blacks
          (r2, b2) = (R - k - r1, B - b1 + 1)
          # chance of a red card is also pb percent
          pr = div(100 * r2, r2 + b2)
          if pr is None or pr != pb: continue
      
          # output solution
          printf("k={k}: p1={r1}r + {b1}b -> pb={pb}%; p2={r2}r + {b2}b -> pr={pr}%")
      

      Solution: 8 red cards were removed from the pack.

      From the 18 red and 26 black cards the two piles can be made in two ways:

      pile 1: 6 red + 24 black; P(black) = 24/30 = 80%
      (1 black card is moved to pile 2)
      pile 2: 12 red + 3 black; P(red) = 12/15 = 80%

      pile 1: 12 red + 3 black; P(black) = 3/15 = 20%
      (1 black card is moved to pile 2)
      pile 2: 6 red + 24 black; P(red) = 6/30 = 20%

      Like

  • Unknown's avatar

    Jim Randell 8:36 am on 2 October 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 188: Family birthdays 

    From The Sunday Times, 29th November 1964 [link]

    I wrote to an American friend on the 3rd February 1964, and told him of the coincidence of our family birthdays. My wife and I, our three sons, and our four grandsons all have our birthdays on the same day of the week every year, though all our birthdays are different. When I wrote, I used the usual English form of the date — 3/2/64 — and I gave all our birthdays in that form also.

    My third son received a cable from my friend on his birthday in 1964, but later I was surprised to get a cable from him myself on my eldest son’s birthday. Next my eldest grandson received a cable on his right birthday, and I realised that we were all going to receive cables, but that my friend was, quite reasonably, reading the dates in the American form, i.e. he assumed that the letter had been sent on 2nd March 1964.

    However, I did not write to put him right, and my wife was the next person to get a cable; this was not on her birthday.

    What was the day and date of her birthday in 1964?

    This puzzle is included in the book Sunday Times Brain Teasers (1974).

    [teaser188]

     
    • Jim Randell's avatar

      Jim Randell 8:37 am on 2 October 2022 Permalink | Reply

      The birthdays are on the same day of the week each year, so they cannot straddle 29th February.

      But in any case the letter was sent on 3/2, which was misinterpreted as 2nd March, so the birthdays must be after that date.

      This Python program runs in 57ms. (Internal run time is 434µs).

      Run: [ @replit ]

      from datetime import (date, timedelta)
      from enigma import (defaultdict, repeat, catch, subsets, printf)
      
      # reverse the day/month of a date
      rev = lambda d: catch(date, d.year, d.day, d.month)
      
      # is a date reversible?
      is_rev = lambda d: rev(d) == d
      
      # group days by day of the week
      g = defaultdict(list)
      # look for dates in 1964 that can be misinterpreted as US style dates
      inc = lambda x, i=timedelta(days=1): x + i
      for d in repeat(inc, date(1964, 1, 1)):
        if d.year > 1964: break
        # try US format
        d_ = rev(d)
        if not d_: continue
        # must be the same day of the week as the original date
        w = d.isoweekday()
        if d_.isoweekday() == w:
          g[w].append(d)
      
      # consider the day of the week
      for k in g.keys():
        # we need 9 dates the come after 2nd March
        for ds in subsets((d for d in g[k] if d > date(1964, 3, 2)), size=9):
          # the first birthday is the correct date (third son)
          if not is_rev(ds[0]): continue
          # the second birthday is not the correct date (eldest son, sent to setter)
          if is_rev(ds[1]): continue
          # the third birthday is the correct date (eldest grandson)
          if not is_rev(ds[2]): continue
          # the fourth birthday is not the correct date (sent to wife)
          if is_rev(ds[3]): continue
          # so the wife's birthday is ...
          d = rev(ds[3])
          # output solution
          printf("{d}", d=d.strftime("%A, %d %B %Y"))
      

      Solution: Her birthday is on: Saturday, 7th November 1964.

      There is only one set of dates that works:

      4/4 = 4th April, third son
      9/5 = 9th May, eldest son; misinterpreted as 5th September (the setter’s birthday)
      6/6 = 6th June, eldest grandson
      11/7 = 11th July; misinterpreted at 7th November (the setter’s wife’s birthday)
      8/8 = 8th August
      5/9 = 5th September, setter; misinterpreted at 9th May
      10/10 = 10th October
      7/11 = 7th November, setter’s wife; misinterpreted as 11th July
      12/12 = 12th December

      Like

  • Unknown's avatar

    Jim Randell 4:35 pm on 30 September 2022 Permalink | Reply
    Tags:   

    Teaser 3132: Bilateral symmetry 

    From The Sunday Times, 2nd October 2022 [link] [link]

    My son, at a loose end after A-levels, asked me for a mental challenge. As we’d been discussing palindromes, I suggested he try to find an arrangement of the digits 1 to 9 with the multiplication symbol “×” to give a palindrome as the answer, and he came up with:

    29678 × 1453 = 43122134.

    I said: “Now try to find the smallest such palindromic product starting in 4, where the last digit of the smallest number is still 3”. He found that smallest product, and, interestingly, if he added the two smaller numbers instead of multiplying them, then added 100, he also got a palindrome.

    What is the smallest product?

    [teaser3132]

     
    • Jim Randell's avatar

      Jim Randell 4:55 pm on 30 September 2022 Permalink | Reply

      Using the [[ SubstitutedExpression() ]] solver from the enigma.py library.

      This Python program runs in 98ms.

      Run: [ @replit ]

      from enigma import (
        Accumulator, SubstitutedExpression, irange,
        is_npalindrome as is_npal, sprintf as f, printf
      )
      
      # find the smallest product
      r = Accumulator(fn=min, collect=1)
      
      # symbols to use
      syms = "ABCDEFGHI"
      
      n = len(syms)
      for i in irange(1, n // 2):
      
        # construct the alphametic puzzle; X < Y
        (X, Y) = (syms[:i], syms[i:])
        (x, y) = (X[-1], Y[-1])
        # X * Y is palindromic and starts (and ends) in the digit 4
        exprs = [ f("is_npal({X} * {Y})"), f("({x} * {y}) % 10 = 4") ]
        if len(X) == len(Y): exprs.append(f("{X[0]} < {Y[0]}"))
        p = SubstitutedExpression(
          exprs,
          digits=irange(1, 9),  # digits are 1-9
          s2d={ x: 3 },  # final digit of X is 3
          answer=f("({X}, {Y})"),
          env=dict(is_npal=is_npal),
        )
        # solve it
        for (s, (x, y)) in p.solve(verbose=0):
          z = x * y
          printf("[{x} * {y} = {z}]")
          r.accumulate_data(z, (x, y))
      
      # output solution
      printf("min product = {r.value}")
      for (x, y) in r.data:
        v = x + y + 100
        printf("  = {x} * {y}; {x} + {y} + 100 = {v} [{s}palindrome]", s=('' if is_npal(v) else 'not '))
      

      Solution: The smallest product is 40699604.

      Ignoring the final palindromic addition check, there are 3 candidate palindromic products that meet the criteria (in decreasing order)

      424393424 = 7163 × 59248
      43122134 = 1453 × 29678
      40699604 = 23 × 1769548

      The final one gives the answer to the puzzle, and is also the only one where the sum of the multiplicands and 100 is also palindromic.

      There are also two further palindromic products where the larger of the multiplicands ends in the digit 3:

      449757944 = 56219743 × 8
      49900994 = 167453 × 298

      Like

      • Frits's avatar

        Frits 10:22 am on 1 October 2022 Permalink | Reply

        @Jim,

        I expected “for i in irange(5, n – 1):” ( where the last digit of the smallest number is still 3)

        Like

    • GeoffR's avatar

      GeoffR 10:10 am on 3 October 2022 Permalink | Reply

      The only way I could find a MiniZinc solution was to assume that one of the multipliers was two digits long, so this is not a rigorous solution. Although I coded requirements for the second palindrome, as stated in the teaser, I found it was not strictly necessary to find the smallest palindromic product.

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      % re-using Frits' toNum function
      function var int: toNum(array[int] of var int: a) =
           let { int: len = length(a) }in
               sum(i in 1..len) (
               ceil(pow(int2float(10), int2float(len-i))) * a[i]
                );
                
      % Digits for the two numbers being multiplied together
      % which are AB and CDEFGHI
      var 1..9:A; var 1..9:B; var 1..9:C; var 1..9:D; var 1..9:E; 
      var 1..9:F; var 1..9:G; var 1..9:H; var 1..9:I;
      
      constraint all_different ([A,B,C,D,E,F,G,H,I]);
      
      var 10..99:AB;
      var 1000000.. 9999999:CDEFGHI;
      
      % last digits of the two numbers 
      constraint B == 3 /\ I == 8;
      
      % abcdefgh - main product
      var 1..9:a; var 0..9:b; var 0..9:c; var 0..9:d;
      var 0..9:e; var 0..9:f; var 0..9:g; var 1..9:h;
      
      % mnopqrst - 2nd palindrome
      var 1..9:m; var 0..9:n; var 0..9:o; var 0..9:p;
      var 0..9:q; var 0..9:r; var 0..9:s; var 1..9:t;
      
      % Two palindromes
      var 40000000..45000000:abcdefgh;
      var 1000000..2000000:mnopqrs;
      
      % Two numbers being multiplied together
      constraint AB == toNum([A,B]);
      constraint CDEFGHI == toNum([C,D,E,F,G,H,I]);
      
      % Main and 2nd palindromes
      constraint abcdefgh == toNum([a,b,c,d,e,f,g,h]);
      constraint mnopqrs == toNum([m,n,o,p,q,r,s]); 
      
      % check main product is palindromic
      constraint (a == 4 /\ h == 4) /\ b == g /\ c == f /\ d == e;
      
      % main palindromic product
      constraint CDEFGHI * AB == abcdefgh;
      
      % form 2nd palindrome 
      constraint mnopqrs == CDEFGHI + AB + 100;
      constraint m = s /\ n == r /\ o == q;
      
      % find smallest palindromic product
      solve minimize(abcdefgh);
      
      output["Smallest palindrome = " ++ show(abcdefgh) ++ "\n" ++
      "Sum is: " ++show(CDEFGHI) ++ " * " ++ show(AB) ++ " = " ++ 
       show(abcdefgh) ++ "\n2nd palindrome = "  ++ show(mnopqrs)];
      
      

      Like

    • NigelR's avatar

      NigelR 11:28 am on 3 October 2022 Permalink | Reply

      Shorter but not quicker! The palin lambda proves I was listening last week, though!!

      from itertools import combinations as comb, permutations as perm
      #test whether number 'num' is palindromic
      palin = lambda num:sum(str(num)[n]!=str(num)[-n-1] for n in range(len(str(num))//2)) == 0
      digs=['1','2','4','5','6','7','8','9']
      res=999999999
      #work through possible values for 'left' of two smaller numbers
      for i in range(1,8):
          for x in comb(digs,i):
              for y in perm(x):
                  l = int("".join(y))
                  #work through possible values for 'right' of two smaller numbers (ending in 3)
                  for v in perm([w for w in digs if w not in y]):
                      r=int("".join(v))*10+3
                      if r>l:continue   #number ending in 3 is smallest number
                      prod=l*r
                      #test for output conditions
                      if str(prod)[0]!='4':continue
                      if not palin(prod):continue
                      if not palin(l+r+100):continue
                      if prod<res:res=prod
      print('Smallest valid product is:', res)
      

      Like

      • NigelR's avatar

        NigelR 11:36 am on 3 October 2022 Permalink | Reply

        Given that the number ending in ‘3’ is the smaller of the two numbers, I could have made line 7
        ‘for i in range(5,8)’, which shaves a bit of time off.

        Like

      • Frits's avatar

        Frits 3:19 pm on 3 October 2022 Permalink | Reply

        Easier: palin = lambda num: (s := str(num)) == s[::-1]

        The “for x .. for y ..” can be replaced by “for y in perm(digs, i):”

        Like

        • NigelR's avatar

          NigelR 12:31 pm on 4 October 2022 Permalink | Reply

          Thanks Frits . Much neater – and I now know how to assign a variable within an expression. Onwards and upwards!

          Like

      • Frits's avatar

        Frits 10:57 pm on 3 October 2022 Permalink | Reply

        I spent some time in making a generic version of GeoffR’s Minizinc program.

        As the numFirst and numAsOf functions do not work with “var int” parameters I had to call them several times.

        Using the fact that the first digit of the largest number must be a 1 (as p1 + p2 plus 100 is palindromic and has to end in 1) didn’t help to bring the run time under one second.

         
        % A Solution in MiniZinc
        include "globals.mzn";
        
        % return <n>-th digit of number <a> with length<len>
        function var int: nthDigit(var int: a, var int: len, var int: n) =
          ((a mod pows[len + 2 - n]) div pows[len + 1 - n]);                        
                       
        % return number of the first <len> digits        
        function var int: numFirst(array[int] of var int: a, var int: len) =
          sum(i in 1..len) (pows[len + 1 - i] * a[i]);            
        
        % return number as of the <b>-th digit                        
        function var int: numAsOf(array[int] of var int: a, var int: b) =
          let { int: len = length(a) }in
               sum(i in b..len) (pows[len + 1 - i] * a[i]);  
        
        % count how many digits have a correct mirror digit              
        function var int: palin(var int: a, var int: len, var int: b) =
          sum(i in 1..b) (
              nthDigit(a, len, i) == nthDigit(a, len, len + 1 - i)
          );        
        
        % digits used in the two numbers
        var 1..9: a; var 1..9: b; var 1..9: c; var 1..9: d;
        var 1..9: e; var 1..9: f; var 1..9: g; var 1..9: h; var 1..9: i;
        
        % make a tables of powers of 10
        set of int: pows = {pow(10, j) | j in 0..8};
        
        constraint i == 8;  % largest number has to end in 8
        
        constraint all_different ([a, b, c, d, e, f, g, h, i]);
        
        var 1..9999: p1;           % smallest number
        var 1..99999999: p2;       % largest number
        var 1..999999999: prod;    % product
        var 8..9: L;               % length palindrome
        var 1..4: L1;              % length smallest number
        
        % set smallest number to p1
        constraint p1 == numFirst([a, b, c, d, e, f, g, h, i], L1);
        % set largest number to p2          
        constraint p2 == numAsOf([a, b, c, d, e, f, g, h, i], L1 + 1);
        
        constraint p1 mod 10 == 3;    % last digit of smallest number is 3
        
        % first digit of product must be a 4  (needed for performance)
        constraint nthDigit(prod, L, 1) == 4;
                   
        constraint prod == p1 * p2;
        
        % set length variable L
        constraint (prod  > 99999999 /\ L == 9) \/
                   (prod <= 99999999 /\ L == 8);
        
        % product should be a palindrome
        constraint palin(prod, L, 4) == 4;
        
        % find smallest palindromic product
        solve minimize(prod);
         
        output["Smallest palindrome = " ++ show(prod)];
        

        Like

    • GeoffR's avatar

      GeoffR 9:24 am on 4 October 2022 Permalink | Reply

      @Frits:
      An excellent full programming solution in MiniZinc, with some new functions.

      Like

    • GeoffR's avatar

      GeoffR 8:50 am on 20 October 2022 Permalink | Reply

      # last digits of a = 3 and for b = 8 with a < b
      for a in range(13, 100, 10):  # UB assumed value
          # check 8-digit products up to teaser stated product
          for b in range(100008, 43122134 // a, 10):
              prod1 = a * b
              if prod1 < 40000004:continue
              
              # we need all digits in range 1..9 in prod1
              all_dig = str(a) + str(b)
              if '0' in all_dig:continue
              if len(set(all_dig)) != 9:continue
              
              # check product is a palindrome
              if str(prod1) == str(prod1)[::-1]:
                  # 2nd palindrome condition
                  pal2 = a + b + 100
                  if str(pal2) == str(pal2)[::-1]:
                      print(f"Sum is {a} * {b} = {prod1}")
      
      # Sum is 23 * 1769548 = 40699604
      
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 8:48 am on 29 September 2022 Permalink | Reply
    Tags:   

    Teaser 2747: Marble jar 

    From The Sunday Times, 17th May 2015 [link] [link]

    At our local fete one of the games consisted of guessing the number of marbles in a jar: some of the marbles were red and the rest were blue. People had to guess how many there were of each colour.

    The organiser gave me a couple of clues. Firstly, he told me that there were nearly four hundred marbles altogether. Secondly, he told me that if, when blindfolded, I removed four marbles from the jar, then the chance that they would all be red was exactly one in a four-figure number.

    How many red marbles were there, and how many blue?

    [teaser2747]

     
    • Jim Randell's avatar

      Jim Randell 8:49 am on 29 September 2022 Permalink | Reply

      If there are T marbles in total (T = “nearly 400”) and R of them are red, then the probability of removing 4 red marbles is:

      P = (R / T) × ((R − 1) / (T − 1)) × ((R − 2) / (T − 2)) × ((R − 3) / (T − 3))
      P = (R × (R − 1) × (R − 2) × (R − 3)) / (T × (T − 1) × (T − 2) × (T − 3))

      And this probability is “one in a four-figure number”, so the largest it can be is 1/1000 and the smallest is 1/9999.

      The following Python program considers total numbers of marbles from 399 down to 350, and then looks for numbers of red marbles that give an appropriate value for P.

      It runs in 57ms. (Internal run time is 1.2ms).

      Run: [ @replit ]

      from enigma import (irange, printf)
      
      # consider total number of marbles (nearly 400)
      for T in irange(399, 350, step=-1):
        # denominator of P
        d = T * (T - 1) * (T - 2) * (T - 3)
        # R = number of red marbles
        for R in irange(4, T):
          # numerator of P
          n = R * (R - 1) * (R - 2) * (R - 3)
          # calculate p = 1/P
          (p, x) = divmod(d, n)
          if p > 9999: continue
          if p < 1000: break
          if x == 0:
            # output solution
            printf("red = {R}, blue = {B}; total = {T} -> P = 1/{p}",B=T - R)
      

      Solution: There were 45 red marbles and 342 blue marbles.

      So, 387 marbles in total. And the probability of choosing 4 red is 1/6176.

      Like

  • Unknown's avatar

    Jim Randell 8:45 am on 27 September 2022 Permalink | Reply
    Tags:   

    Teaser 2749: Round the river 

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

    My school holds “Round the river” runs — a whole number of metres to a bridge on the river and then the same number of metres back. Some years ago I took part with my friends Roy, Al, David and Cy. We each did the outward half at our own steady speeds (each being a whole number of centimetres per minute). For the return half I continued at my steady speed, Roy increased his speed by 10%, Al increased his speed by 20%, David increased his by 30%, and Cy increased his by 40%. We all finished together in a whole number of minutes, a little less than half an hour.

    What (in metres) is the total length of the race?

    [teaser2749]

     
    • Jim Randell's avatar

      Jim Randell 8:46 am on 27 September 2022 Permalink | Reply

      The speeds are whole numbers of centimetres per minute, so we will work in units of centimetres and minutes.

      If the distance to bridge is x centimetres, then x must be divisible by 100.

      And the time is t minutes (less than 30).

      If the 5 speeds are: a, b, c, d, e, then we have:

      t = x/a + x/a = 2x / a
      t = x/b + x/1.1b = 21x / 11b
      t = x/c + x/1.2c = 11x / 6c
      t = x/d + x/1.3d = 23x / 13d
      t = x/e + x/1.4e = 12x / 7e

      From which we see that x must also be divisible by 11, 6, 13, 7.

      Placing some sensible limits on distance and speeds, we can suppose x is less than 10km (= 10,000m = 1,000,000cm), and that speeds are less than 15mph (≈ 40,000cm/min).

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

      Run: [ @replit ]

      from enigma import (irange, mlcm, div, printf)
      
      # x must be a multiple of m
      m = mlcm(100, 11, 6, 13, 7)
      
      # consider possible total times: "a little less than half an hour"
      for t in irange(29, 21, step=-1):
      
        # consider possible values of x (up to 10km)
        for x in irange(m, 1000000, step=m):
      
          # calculate the speeds
          vs = [
            div(20 * x, 10 * t),
            div(21 * x, 11 * t),
            div(22 * x, 12 * t),
            div(23 * x, 13 * t),
            div(24 * x, 14 * t),
          ]
          # check speeds
          if None in vs or vs[-1] * 1.4 > 40000: continue
      
          # output solution
          printf("d={d} metres [t={t} x={x} {vs}]", d=div(2 * x, 100))
      

      Solution: The total length of the race is 6006m.

      And the race took exactly 25 minutes.

      The outward speeds are:

      1: 24024 cm/min (≈ 8.96 mph); 12.5 min out + 12.5 min back (@ 8.96 mph)
      2: 22932 cm/min (≈ 8.55 mph); 13.1 min out + 11.9 min back (@ 9.40 mph)
      3: 22022 cm/min (≈ 8.21 mph); 13.6 min out + 11.4 min back (@ 9.85 mph)
      4: 21252 cm/min (≈ 7.92 mph); 14.1 min out + 10.9 min back (@ 10.30 mph)
      5: 20592 cm/min (≈ 7.68 mph); 14.6 min out + 10.4 min back (@ 10.75 mph)

      Note that the speeds on the return leg are not all whole numbers of cm/min.

      Like

  • Unknown's avatar

    Jim Randell 10:53 am on 25 September 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 418: Bell’s weights 

    From The Sunday Times, 11th May 1969 [link]

    “Now”, says Bell at the pub, “look intelligent and imaginative even if you don’t look beautiful by any means”. We swallow the insult and look solemn. Bell likes his jokes and we like his puzzles.

    “Imagine you have some scales, but only three weights. However, you have a heap of Grade A sand, and a couple of bags; so you make two extra weights, one as heavy as all the first three put together, and the other twice as heavy as all the first three. Whereupon all the remaining sand is removed to a great distance”.

    “With these five weights you must be able to weigh 1 ounce, 2 ounces, 3, 4, and so on, as far as possible. No gaps in that lot. It’s how far you can to the first gap I’m after. Usual prize — one pint for the best score before closing time”.

    What should Bell’s five weights be to give the highest possible score?

    This puzzle is included in the book Sunday Times Brain Teasers (1974).

    [teaser418]

     
    • Jim Randell's avatar

      Jim Randell 10:54 am on 25 September 2022 Permalink | Reply

      This Python program considers increasing values for the total of the first 3 weights, from 3 to 40.

      It runs in 351ms.

      Run: [ @replit ]

      from enigma import (irange, inf, decompose, subsets, peek, Accumulator, printf)
      
      def unreachable(ws):
        # collect possible weights
        vs = set()
        # choose multipliers for each weight
        for ms in subsets((1, 0, -1), size=len(ws), select="M"):
          v = sum(m * w for (m, w) in zip(ms, ws))
          if v > 0: vs.add(v)
        # find the first unreachable value
        return peek(v for v in irange(1, inf) if v not in vs)
      
      # record maximum unreachable weight
      r = Accumulator(fn=max, collect=1)
      
      # consider t = a + b + c
      for t in irange(3, 40):
        for (a, b, c) in decompose(t, 3, increasing=1, sep=0, min_v=1):
          # calculate the first unreachable value
          ws = (a, b, c, t, 2 * t)
          v = unreachable(ws)
          r.accumulate_data(v, ws)
          if v == r.value: printf("[t={t}: {ws} -> unreachble = {v}]")
      
      printf("values = 1 .. {x}", x=r.value - 1)
      for ws in r.data:
        printf("-> {ws}")
      

      Solution: The 5 weights are: 4, 6, 9, 19, 38.

      And this set of weights can be used to weigh all values from 1 to 64.


      Using a set of balancing scales each weight can go in the left pan, right pan, or neither.

      For for n weights there are 3^n possibilities.

      But these include, not using any weights (all in neither pan), and each combination has a mirror image.

      So the total maximum possible number of different weights would be:

      W(n) = (3^n − 1) / 2

      For 5 weights we have: W(5) = 121, and using a set consisting of increasing powers of 3 we can achieve this maximum and weigh all values between 1 and 121:

      1, 3, 9, 27, 81

      But for a set of the form:

      (a, b, c, a + b + c, 2(a + b + c))

      there are 70 different arrangements. So the maximum number of different values we could achieve would be no more than this. And we can use the program to perform an exhaustive check up to this total, but there are no better solutions.

      Like

  • Unknown's avatar

    Jim Randell 4:33 pm on 23 September 2022 Permalink | Reply
    Tags:   

    Teaser 3131: Heads up savings 

    From The Sunday Times, 25th September 2022 [link] [link]

    Little Spencer saves 5p coins in a jar, and when they reach £10, deposits them in his savings account. He likes playing with the coins. In one game, after first turning them all heads up, he places them in a row on the table. Starting from the left, he then turns over every 2nd coin until he has reached the end of the row. He then again starts from the left, and this time turns over every 3rd coin. He repeats this for every 4th, 5th coin etc, until finally he turned over just one coin, the last in the row.

    At the end of the game I could see that if Spencer had exactly 75 per cent more coins he would have an increase of 40 per cent in the number showing heads. However, if he had exactly 50 per cent fewer coins, he would have a decrease of 40 per cent in the number showing heads.

    What is the value of his 5p savings?

    There are now 750 Teaser puzzles available on the S2T2 site.

    [teaser3131]

     
    • Jim Randell's avatar

      Jim Randell 5:09 pm on 23 September 2022 Permalink | Reply

      (See also: Puzzle #08).

      Here is a constructive solution.

      It runs in 52ms. (Internal runtime is 409µs).

      Run: [ @replit ]

      from enigma import (irange, csum, div, printf)
      
      # play the game with <n> coins
      def coins(n):
        # each coin starts out showing heads = 1
        vs = [1] * n
        # allow the coins to be indexed from 1
        vs.insert(0, None)
        # every <k> coins
        for k in irange(2, n):
          # flip coin k, 2k, 3k, ....
          for i in irange(k, n, step=k):
            vs[i] ^= 1
        vs.pop(0)
        return vs
      
      # it is enough to calculate one sequence, and then use prefixes
      heads = list(csum(coins(350), empty=1))
      
      # consider initial number of coins
      for n in irange(1, 200):
        # we need 1.75 times the number of coins, and 0.5 times the number
        n1 = div(175 * n, 100)
        n2 = div(50 * n, 100)
        if n1 is None or n2 is None: continue
      
        # h1 is 1.4 times h; h2 is 0.6 times h
        (h, h1, h2) = (heads[x] for x in (n, n1, n2))
        if not (100 * h1 == 140 * h and 100 * h2 == 60 * h): continue
      
        # output solution
        printf("{n} coins = {h} heads; {n1} coins = {h1} heads; {n2} coins = {h2} heads")
      

      Solution: The total value of the coins is £1.40.

      Spencer has 28 coins.

      After performing the procedure there are 5 coins remaining heads up (= coins 1, 4, 9, 16, 25).

      If he had 1.75× the number of coins (= 49 coins), then 7 would remain heads up (= coins 1, 4, 9, 16, 25, 36, 49).

      And if he had 0.5× the number of coins (= 14 coins), then 3 would remain heads up (= coins 1, 4, 9).

      Like

      • Jim Randell's avatar

        Jim Randell 5:46 pm on 23 September 2022 Permalink | Reply

        Using the fact that the coins that remain heads up are exactly those in the perfect square numbered positions (numbering from 1), we can get a shorter (and faster) program.

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

        Run: [ @replit ]

        from enigma import (irange, isqrt, div, printf)
        
        # play the game with <n> coins, return the number of heads
        heads = isqrt
        
        # consider initial number of coins
        for n in irange(1, 200):
          # we need 1.75 times the number of coins, and 0.5 times the number
          n1 = div(175 * n, 100)
          n2 = div(50 * n, 100)
          if n1 is None or n2 is None: continue
        
          # h1 is 1.4 times h, h2 is 0.6 times h
          (h, h1, h2) = (heads(x) for x in (n, n1, n2))
          if not (100 * h1 == 140 * h and 100 * h2 == 60 * h): continue
        
          # output solution
          printf("{n} coins = {h} heads; {n1} coins = {h1} heads; {n2} coins = {h2} heads")
        

        Like

    • NigelR's avatar

      NigelR 10:50 am on 26 September 2022 Permalink | Reply

      Irrespective of the number of times coin n in the row is flipped, its final H/T depends on whether n has an odd or even number of factors. (I hadn’t spotted the elegance of the perfect squares!).
      PS: I think the answer sought was actually the value of the coins, not the number.

      
      # Test whether n has an even number of factors
      countfac = lambda n: True if [1 if n % i == 0 else 0 for i in range(1, (n//2)+1)].count(1) %2==0 else False
      heads={x:1 for x in range(1,200)} #initialise heads as dictionary 
      for x in range(2,200):
          heads[x]=heads[x-1]
          if countfac(x): heads[x]+=1  #heads[n] now has cumulative number of heads for row of n coins
      #test for output conditions. Number of coins must be divisible by 4 if 75% greater is integer 
      for x in range(4,200,4):
          if x*1.75>200:continue
          y=int(x*1.75)
          z=int(x/2)
          if heads[y]!=heads[x]*1.4:continue
          if heads[z]!=heads[x]*0.6:continue
          value = divmod(5*x,100)
          print(x ,'coins in row, ',heads[x],'of which are heads. Value of savings is £',value[0],'and',value[1],'p')
      

      Like

      • Jim Randell's avatar

        Jim Randell 2:24 pm on 26 September 2022 Permalink | Reply

        @NigelR: I left determining the total value of a certain number of 5p coins as a simple exercise for the reader ;-).

        You could shorten this line of code somewhat:

        countfac = lambda n: True if [1 if n % i == 0 else 0 for i in range(1, (n // 2) + 1)].count(1) % 2 == 0 else False
        

        (True if ... else False) is just the same as evaluating ... (in a boolean context):

        countfac = lambda n: [1 if n % i == 0 else 0 for i in range(1, (n // 2) + 1)].count(1) % 2 == 0
        

        and then in the list comprehension, (1 if ... else 0) is also the same as ... (in a boolean context; in Python False and True are just 0 and 1 in disguise):

        countfac = lambda n: [n % i == 0 for i in range(1, (n // 2) + 1)].count(1) % 2 == 0
        

        and we don’t need to construct the list, just to count the number of 1’s in it:

        countfac = lambda n: sum(n % i == 0 for i in range(1, (n // 2) + 1)) % 2 == 0
        

        Also note that Python’s builtin range function does not include the endpoint. So if you want to go to 350 in line 4 you need to specify a stop value of 351. Similarly in line 8, to check up to 200 coins you need to specify a stop value of 201.

        (I tend to use the inclusive irange() function from the enigma.py library, which includes both endpoints, to avoid this kind of “fencepost” error).

        Like

        • NigelR's avatar

          NigelR 8:40 pm on 26 September 2022 Permalink | Reply

          JIm: Thank you so much for taking the time to unpick my messy code and for your very helpful advice – your countfac is much simpler and I’m now wiser! I couldn’t work out what on earth I’d done in the lambda an hour after writing it!
          Agree on the stop value of 351, but I did think about the 200/201 and concluded that Spencer would have banked the lot if it had reached 200, and hence he would only have been playing with up to 199 coins. Perhaps I’m overthinking it!

          Like

        • Jim Randell's avatar

          Jim Randell 10:08 am on 27 September 2022 Permalink | Reply

          Yes the (200, 350) case is a bit of a grey area. I decided he might like one last play with his coins before he banked them, so I might as well check it, as I prefer solutions that exhaustively explore the solution space.

          As it turns out it doesn’t provide an answer, so it doesn’t really matter if you check it or not.

          Like

    • NigelR's avatar

      NigelR 10:58 am on 26 September 2022 Permalink | Reply

      … and,of course, the 75% greater number is only hypothetical and hence can be greater than 200. My line 4 should go to 350, and line 10 is unnecessary.

      Like

  • Unknown's avatar

    Jim Randell 9:38 am on 22 September 2022 Permalink | Reply
    Tags:   

    Teaser 2742: Hymns bored 

    From The Sunday Times, 12th April 2015 [link] [link]

    Peter became bored during the Sunday service, so his mind turned to the three three-figure hymn numbers displayed on the board, all chosen from the five hundred hymns in the hymnal. He noticed that the sum of the digits for each hymn was the same, that one hymn number was the average of the other two, and that no digit appeared more than once on the board.

    What (in increasing order) were the three hymn numbers?

    [teaser2742]

     
    • Jim Randell's avatar

      Jim Randell 9:39 am on 22 September 2022 Permalink | Reply

      We can treat this as an alphametic puzzle, and use the [[ SubstitutedExpression ]] solver from the enigma.py library to solve the puzzle.

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

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      # if the hymn numbers are: ABC, DEF, GHI
      --answer="(ABC, DEF, GHI)"
      
      # the hymns are in order
      "A < D < G"
      
      # hymns are numbered from 1 to 500
      "G < 5"
      
      # each hymn has the same digit sum
      "all_same(A + B + C, D + E + F, G + H + I)"
      
      # one hymn number is the average of the other two: DEF = (ABC + GHI) / 2
      "div(ABC + GHI, 2) = DEF"
      
      # allow leading zeros
      --invalid=""
      

      Solution: The hymn numbers are: 157, 283, 409.

      Like

    • GeoffR's avatar

      GeoffR 12:00 pm on 22 September 2022 Permalink | Reply

      
      from itertools import permutations
      
      for p1 in permutations('1234567890', 9):
          A, B, C, D, E, F, G, H, I = p1
          if '0' in (A, D, G):continue
          
          # check digit sums are same for three numbers
          total = int(A) + int(B) + int(C)
          if int(D) + int(E) + int(F) != total:continue
          if int(G) + int(H) + int(I) != total:continue
          
          # find three hymn numbers in increasing order
          ABC, DEF = int(A + B + C), int(D + E + F)
          GHI = int(G + H + I)
          if not ABC < DEF < GHI:continue
          # check all hymn numbers are less than 500
          if not all( x < 500 for x in (ABC, DEF, GHI)):continue
          
          # One hymn number was the average of the other two
          if 2 * DEF == ABC + GHI:
              print(f"Three hymn numbers are {ABC}, {DEF} and {GHI}.")
      
      # Three hymn numbers are 157, 283 and 409.  
      
      

      Like

    • GeoffR's avatar

      GeoffR 1:23 pm on 22 September 2022 Permalink | Reply

      % 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;
      
      constraint all_different([A,B,C,D,E,F,G,H,I]);
      
      var 100..500:ABC = 100*A + 10*B + C;
      var 100..500:DEF = 100*D + 10*E + F;
      var 100..500:GHI = 100*G + 10*H + I;
      
      constraint A + B + C == D + E + F /\ A + B + C == G + H + I;
      constraint ABC < DEF /\ DEF < GHI;
      constraint 2 * DEF == ABC + GHI;
      
      solve satisfy;
      output ["Three hymn numbers were " ++ show(ABC) ++ ", " ++ show(DEF) 
      ++ " and " ++ show(GHI) ];
      
      % Three hymn numbers were 157, 283 and 409
      % ----------
      % ==========
      
      
      

      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