Design a site like this with WordPress.com
Get started

Tagged: by: Howard Williams Toggle Comment Threads | Keyboard Shortcuts

  • Jim Randell 4:12 pm on 25 November 2022 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3140: Enjoy every minute 

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

    On rugby international morning, I found myself, along with eight friends, in a pub 5.8 miles from the match ground. We were enjoying ourselves, and so wished to delay our departure for the ground until the last possible minute. The publican, wishing to keep our custom for as long as possible, offered to help us get there by carrying us, one at a time, as pillion passengers on his motorbike.

    We could walk at 2.5mph and the bike would travel at 30mph. We all left the pub together, and arrived at the ground in time for kick-off.

    Ignoring the time taken getting on and off the bike, what was our minimum travelling time in minutes?

    [teaser3140]

     
    • Jim Randell 4:58 pm on 25 November 2022 Permalink | Reply

      (Curiously this week’s New Scientist back page puzzle is a simpler variation on the problem [link]).

      If the friends just walked from pub to the stadium it would take 2.32 hours.

      If the barman ferried each of them individually between the pub and the stadium it would take 3.29 hours.

      But we can do better.

      If the barman takes the first friend on his motorbike, and the rest of the friends start walking towards the stadium. Then the barman drops the first friend off to walk the remainder of the distance to the stadium and returns to the group (now a short distance from the pub) and ferries the next friend to join the first friend, and so on until he collects the final friend and drops him off at the stadium at the same time that all the other friends arrive, then we can achieve a minimum overall time.

      The only thing to work out is how far before the stadium to drop the first friend, then it is just a matter of ferrying friends from the trailing to the leading group.

      If each of the k friends walks a distance x at velocity w, and travels by motorbike a distance (d − x) at a velocity v, then each journey takes:

      t = x/w + (d − x)/v

      And the total time taken for the barman to ferry them all is:

      t = [(2k − 1)d − 2kx]/v

      Everyone arrives at the stadium at the same time, so:

      x/w + (d − x)/v = [(2k − 1)d − 2kx]/v
      vx + (d − x)w = [(2k − 1)d − 2kx]w
      vx + dw − xw = (2k − 1)dw − 2kxw
      x(v + w(2k − 1)) = dw(2k − 2)
      x = 2dw(k − 1) / (v + w(2k − 1))

      or:

      n = 2k − 1
      x = dw(n − 1) / (v + wn)
      t = d(w + vn) / v(v + wn)

      The answer can then be calculated directly.

      Run: [ @replit ]

      from enigma import (fdiv, printf)
      
      k = 9    # number of people in the group
      d = 5.8  # distance between pub and stadium
      w = 2.5  # walking speed
      v = 30   # motorbike speed
      
      # calculate amount of walking per person
      n = 2 * k - 1
      x = fdiv(d * w * (n - 1), v + w * n)
      
      # calculate time taken
      t = fdiv(x, w) + fdiv(d - x, v)
      
      # output solution
      printf("t={t:g} hours (= {m:g} min) [x={x:g} miles]", m=t * 60)
      

      Solution: The minimum travelling time is 82 minutes.

      We calculate:

      x = 16/5 = 32/10
      t = 32/25 + 13/150 = 41/30 = 82/60

      So the first friend is dropped off 3.2 miles from the stadium (and walks the remainder of the way).

      Each friend walks for 76.8 minutes and is on the motorbike for 5.2 minutes. Giving each a total journey time of 82 minutes.

      Like

      • Jim Randell 10:56 pm on 30 November 2022 Permalink | Reply

        (See also: Enigma 977).

        Here is a numerical approach, based on the barman dropping the first friend off after a distance x (from the pub) while the remaining friends set off on foot.

        The barman then returns to the trailing group and ferries a single friend from the trailing to the leading group until everyone has been transferred to the leading group. And we record the maximal journey time for the friends to give us a total time to get all the friends to the stadium.

        We then use the [[ find_min() ]] function from the enigma.py library to determine at what distance x the shortest total journey time occurs.

        Unsurprisingly this gives us the same answer as the analytical approach above (but with considerably more effort). But it does show that the logic used in the analysis does indeed produce the minimum time.

        Run: [ @replit ]

        from enigma import (irange, fdiv, find_min, printf)
        
        k = 9    # number of people in the group
        d = 5.8  # distance between pub and stadium
        w = 2.5  # walking speed
        v = 30   # motorbike speed
        
        # if: A starts at a, velocity v; B starts at b, velocity w
        # return: (<position>, <time>) of meeting
        def meet(a, v, b, w, t0=0):
          t = fdiv(b - a, v - w)
          return (b + t * w, t0 + t)
        
        # run a scenario where the first person is dropped off at distance x
        # return the time taken for everyone to arrive
        def run(x):
          ts = list()
          # ferry friend 1 to x and let them walk the remaining distance (d - x)
          d1 = x
          t1 = fdiv(x, v)
          # and so the total time for the first friend is ...
          ts.append(t1 + fdiv(d - d1, w))
        
          # the position of the trailing group at time t is:
          tr = lambda t: min(t * w, d)
          # the position of the leading group at time t >= t1 is:
          ld = lambda t, t1=t1: min(x + (t - t1) * w, d)
        
          # ferry the remaining friends ...
          for _ in irange(2, k):
            # we return from d1 to the trailing group
            (d2, t2) = meet(d1, -v, tr(t1), w, t1)
            # and then back to the leading group
            (d3, t3) = meet(d2, +v, ld(t2), w, t2)
            if d3 < d:
              # they walk the remaining distance
              ts.append(t3 + fdiv(d - d3, w))
            else:
              # they are dropped off at the stadium
              (d3, t3) = (d, t2 + fdiv(d - d2, v))
              ts.append(t3)
            (d1, t1) = (d3, t3)
          # return the maximum time
          return max(ts)
        
        # find the minimal time
        r = find_min(run, 0, d)
        (t, x) = (r.fv, r.v)
        printf("min time = {t:g} hours (= {m:g} min) [drop 1 at {x:g} miles]", m=t * 60)
        

        Here is a graph of the total journey time against the distance x that the first friend is taken from the pub. We see that the minimum time is achieved when x = 2.6 miles.

        Like

      • NigelR 4:29 pm on 1 December 2022 Permalink | Reply

        Hi Jim. I very much enjoyed this puzzle (more for the logic than the Python content!) but I’m intrigued to know how you got to the term 2kx in your second equation. I got to it indirectly by looking at the vector sum of all the motorbike journeys out: [(k)(d-x)] +back: [(k)(d-x)-d] given that he finishes up a distance d from where he started. That then reduces to:
        [(2k-1)d -2kx] but is there a more intuitive way of getting to the second term?

        Like

        • Jim Randell 10:50 pm on 1 December 2022 Permalink | Reply

          @Nigel: The way I thought of it the barman makes a journey towards the stadium for each of the k friends. And in between friends he has to make (k − 1) return journeys towards the pub.

          If he made complete journeys between the pub and the stadium this would be (2k − 1) journeys of distance d for a total of (2k − 1)d.

          But if he made complete journeys he would be travelling over the ground that each friend walks, in both directions, so this amount is overcounting the barmans distance by 2x for each of the k friends.

          So the actual overall distance travelled by the barman is:

          (2k − 1)d − 2kx

          And this actual distance is travelled at velocity v, so we can determine the total time taken for the barman.

          Like

          • NigelR 9:31 am on 3 December 2022 Permalink | Reply

            Thanks Jim. It was the ‘in both directions’ that I was struggling to get my head around. This week’s puzzle is trivial by comparison!

            Like

    • Hugh Casement 9:45 am on 4 December 2022 Permalink | Reply

      There were some early Brain-Teasers of a similar kind by Brigadier A.G.H. Brousson (who died in 1976), involving the Smart brothers who took part in races with one bicycle between them.
      Numbers 640, 663, 686, 722, 741, and 792 would presumably yield to a variant of Jim’s analysis as given here. 792 (at least) is flawed because it doesn’t specify that they all arrived together — nor, for that matter, whether riding pillion on the rear carrier is permitted (I know from experience that it seriously upsets the balance and steering!).

      Like

      • Jim Randell 10:53 am on 8 December 2022 Permalink | Reply

        @Hugh: Thanks. I’ll have a look at those. None of them are in the published books I’m working from, so it would have been a while before I got round to looking at them.

        Like

  • Jim Randell 4:33 pm on 23 September 2022 Permalink | Reply
    Tags: by: Howard Williams   

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

  • Jim Randell 4:03 pm on 15 July 2022 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3121: Top marks 

    From The Sunday Times, 17th July 2022 [link] [link]

    A teacher is preparing her end of term class test. After the test she will arrive at each pupil’s score by giving a fixed number of marks for each correct answer, no marks for a question that is not attempted, and deducting a mark for each incorrect answer. The computer program she uses to prepare parents’ reports can only accept tests with the number of possible test scores (including negative scores) equal to 100.

    She has worked out all possible combinations of the number of questions asked and marks awarded for a correct answer that satisfy this requirement, and has chosen the one that allows the highest possible score for a pupil.

    What is that highest possible score?

    [teaser3121]

     
    • Jim Randell 4:25 pm on 15 July 2022 Permalink | Reply

      If there are n questions asked, and there are a marks for a correct answer, then the possible scores are:

      score = ax − z; where x + z ≤ n

      And we need there to be exactly 100 possible scores.

      There are tri(n + 1) different (correct, unanswered, incorrect) ways the n questions can be answered.

      So we need n ≥ 13 in order for there to be 100 or more different combinations (some may have the same score).

      Here’s a quick program to solve the puzzle.

      It runs in 66ms.

      Run: [ @replit ]

      from enigma import (irange, inf, Accumulator, printf)
      
      # find the highest possible score (all answers correct)
      r = Accumulator(fn=max, collect=1)
      
      # consider possible marks for a correct answer
      for a in irange(1, 10):
        # consider possible numbers of questions
        for n in irange(13, inf):
          # calculate possible scores
          ss = set(a * x - z for x in irange(0, n) for z in irange(0, n - x))
          k = len(ss)
          if k > 100: break
          if k == 100:
            m = max(ss) # = a * n
            r.accumulate_data(m, (a, n))
            printf("[a={a} n={n} m={m}]")
      
      # output solutions
      printf("max score = {m}")
      for (a, n) in r.data:
        printf("-> {n} questions; {a} marks for a correct answer")
      

      Solution: The maximum possible score is 105.

      There are 15 questions, and 7 marks for each correct answer. The maximum is therefore 15×7 = 105.

      It is also possible to have 100 potential scores with 21 questions, and 4 marks for each correct answer. In this case the maximum is 21×4 = 84.

      Like

    • Frits 7:28 pm on 15 July 2022 Permalink | Reply

         
      m = 0 
      # consider possible marks for a correct answer
      for a in range(1, 11):
        # range [-n, -n+1, ..., -1, 0, 1, ..., a*n]
        # max scores            = (a + 1) * n + 1    
        # nr impossible to make = a * (a - 1) / 2
      
        # n.a + n + 1 - 1/2 a.a + 1/2 a = 100
        # (2a + 2)n = a.a - a + 198
        n, r = divmod(a * a - a + 198, 2 * a + 2)
        if r: continue
        
        m = max(m, a * n)
      
      print("answer:", m)  
      

      Like

      • Jim Randell 8:59 am on 16 July 2022 Permalink | Reply

        I wondered how you arrived at your formula for the unreachable marks.

        I came up with this:

        If we get all the questions right the (maximum possible) score is: a.n

        If we get all but one of the questions right (and don’t attempt the remaining question) the next lowest score is: a(n − 1).

        So there are (a − 1) unreachable scores between these.

        If, however, we get the remaining question wrong, we get a score of: a(n − 1) − 1.

        The there are only (a − 2) unreachable scores in the next gap.

        If we get all but two of the questions right the possible scores are: a(n − 2), a(n − 2) − 1, a(n − 2) − 2.

        And there are (a − 3) unreachable scores in the following gap.

        So, in each gap the number of unreachable scores decreases by 1.

        Hence the total number of unreachable scores is: tri(a − 1), providing na. (All possible negative scores are reachable).

        And using this we can determine the number of possible scores without having to construct them.

        And we can proceed manually (there are only 10 values to check), or programatically:

        Run: [ @replit ]

        from enigma import (irange, inf, tri, Accumulator, printf)
        
        # find the highest possible score (all answers correct)
        r = Accumulator(fn=max, collect=1)
        
        # consider possible marks for a correct answer
        for a in irange(1, inf):
          # "unreachable" scores
          u = tri(a - 1)
          # find number of questions (100 = m + n + 1 - u)
          (n, q) = divmod(99 + u, a + 1)
          if n < 13: break
          if q != 0: continue
          assert n >= a
          # max possible score
          m = a * n
          r.accumulate_data(m, (a, n))
          printf("[a={a} n={n} m={m}]")
        
        # output solutions
        printf("max score = {m}")
        for (a, n) in r.data:
          printf("-> {n} questions; {a} marks for a correct answer")
        

        Manually, we can consider increasing a values, calculate u values (by just adding the preceding a value), and compute n = (99 + u) / (a + 1). We need n to be an integer ≥ 13. The calculations proceed as follows:

        a = 1; u = 0; n = 99/2 = 49r1
        a = 2; u = 1; n = 100/3 = 33r1
        a = 3; u = 3; n = 102/4 = 25r2
        a = 4; u = 6; n = 105/5 = 21 [candidate solution]
        a = 5; u = 10; n = 109/6 = 18r1
        a = 6; u = 16; n = 115/7 = 16r2
        a = 7; u = 21; n = 120/8 = 15 [candidate solution]
        a = 8; u = 28; n = 127/9 = 14r1
        a = 9; u = 36; n = 135/10 = 13r5
        a = 10; u = 45; n = 144/11 = 13r1
        a = 11; u = 55; n = 154/12 = 12r10 [n < 13]

        There are two candidate solutions a=4, n=21 ⇒ max=84 and a=7, n=15 ⇒ max=105, so we want the second one.

        Liked by 1 person

        • Frits 12:48 pm on 16 July 2022 Permalink | Reply

          I printed and analyzed the sorted ss lists of your program and noticed that
          the first unreachable number always is F = (n – (a – 2)) * a – (a – 1).
          This happens if the number of correct answers is equal to n – (a – 2).

          the next two unreachable numbers always are:
          (F + a, F + a + 1)
          the next three unreachable numbers always are:
          (F + 2*a, F + 2*a + 1, F + 2*a + 2)
          etc…

          Like

      • Frits 12:27 am on 17 July 2022 Permalink | Reply

        If a >= n then the number of possible test scores is independent of a.
        The number of unreachable scores is then tri(a – 1) – tri(a – n – 1).

        The number of possible test scores is equal to (n + 1) * (n + 2) / 2.
        The number of possible test scores equal to 100 leads to the formula
        (n + 1) * (n + 2) = 200

        A positive solution for n is (3 * sqrt(89) – 3) / 2 = 12.65 so
        not an integer solution.

        Like

    • Frits 6:09 pm on 21 July 2022 Permalink | Reply

      Formula (2a + 2).n = a.a – a + 198 is valid if marks for a correct answer (a) is not higher than the number of questions (n). If a is higher or equal to n then n must be a non-integer solution (approx 12.65).

      Another option would have been to use divisor_pairs().

         
      #! python3 -m enigma -r
      
      # rearrangement idea from John Crabtree:
      
      # formula (2a + 2).n = a.a - a + 198
      # can be rearranged to 2.n + 3 = 200 / (a + 1) + (a + 1) 
      # so both terms of RHS are divisors of 200
       
      SubstitutedExpression
      
      # find divisors of 200
      "div(200, AB) = DEF"
      "1 < AB <= DEF"
      
      # make sure exactly one of them is odd
      "(AB + DEF) % 2"
      
      # marks for a correct answer: AB - 1
      # number of question: (AB + DEF - 3) / 2
      --answer="(AB - 1) * (AB + DEF - 3) // 2"
      --distinct=""
      --accumulate=max
      --invalid="2-9,A"
      --verbose=16
      

      Like

      • Jim Randell 3:04 pm on 22 July 2022 Permalink | Reply

        I also did a solution based on John Crabtree’s analysis:

        from enigma import (Accumulator, divisors_pairs, div, printf)
        
        # based on John Crabtree's derivation: 2n + 3 = 200/(a + 1) + (a + 1)
        
        # find the highest possible score (all answers correct)
        r = Accumulator(fn=max, collect=1)
        
        # look for divisors of 200
        for (p, q) in divisors_pairs(200, every=1):
          a = p - 1
          if a < 1: continue
          # calculate n
          n = div(p + q - 3, 2)
          if n is None or n < a: continue
          m = a * n
          r.accumulate_data(m, (a, n))
          printf("[a={a}: n={n} m={m}]")
        
        # output solutions
        printf("max score = {m}")
        for (a, n) in r.data:
          printf("-> {n} questions; {a} marks for a correct answer")
        

        It is neat because we sum the divisor pairs.

        But it is more straightforward (and slightly faster) just to consider increasing a values (as in my second program).

        Like

  • Jim Randell 3:58 pm on 6 May 2022 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3111: Don’t miss a second 

    From The Sunday Times, 8th May 2022 [link] [link]

    I have an analogue wall clock with a second hand and also a separate 24-hour hh:mm:ss digital clock. The wall clock loses a whole number of seconds over a two-digit period of seconds. The digital clock gains at a rate 2.5% greater than the wall clock loses. After resetting both clocks to the correct time, I noticed that later in the week, at a time one hour earlier than the time of setting, both clocks were displaying the same wrong time.

    I can reset one of the clocks at an exact hour so that it will show the correct time when the televised rugby kicks off at 19:15:00 on the 31st.

    What is the latest time (hour and date) when I can do this?

    The puzzle text has been reworded to (hopefully) remove an ambiguity.

    [teaser3111]

     
    • Jim Randell 5:39 pm on 6 May 2022 Permalink | Reply

      I assumed that the wall clock is a standard 12 hour clock.

      This Python program looks for possible fractions for the wall clock to run slow, and corresponding values for the digital clock to run fast, until we find a pair of values that allows the clocks to apparently show the same time, on a day one hour ahead of the time they were set.

      We can then look backwards for times when a clock could be set on the hour and report the correct time at 19:15:00 on the 31st. The first value we find is the latest possible time.

      The program runs in 112ms.

      Run: [ @replit ]

      from enigma import (Rational, irange, uniq, sprintf, printf)
      
      Q = Rational()
      
      # digital clock gains (41/40)k seconds for every k seconds lost by the
      # wall clock
      m = Q(41, 40)
      
      # gain for wall clock and digital clock after <t> seconds
      W = lambda f, t: int(t * (1 - f))
      D = lambda f, t: int(t * (1 + f * m))
      
      # convert (days, hours, minutes, seconds) to seconds
      hms2t = lambda d=0, h=0, m=0, s=0: s + (60 * (m + 60 * (h + 24 * d)))
      
      H12 = hms2t(h=12) # 12 hours
      H24 = hms2t(h=24) # 24 hours
      
      # format seconds as: [<days>+]<hh>:<mm>:<ss>
      def t2hms(t):
        (m, s) = divmod(t, 60)
        (h, m) = divmod(m, 60)
        (d, h) = divmod(h, 24)
        x = ('' if d == 0 else sprintf("{d}+"))
        return sprintf("[{x}{h:02d}:{m:02d}:{s:02d}]")
      
      # n = the 2-digit period of seconds
      # k = number of seconds the 12 hour clock loses every n seconds
      for f in uniq(Q(k, n) for n in irange(10, 99) for k in irange(1, n - 1)):
      
        # consider times that are 1 hour earlier than the setting time
        for h in irange(23, 168, step=24):
          t = hms2t(h=h)
          w = W(f, t)
          d = D(f, t)
          # are they separated by a multiple of 12 hours?
          (p, r) = divmod(d - w, H12)
          if r != 0: continue
          printf("f={f}; h={h} w={w} d={d} p={p}", w=t2hms(w), d=t2hms(d))
      
          tgt = hms2t(d=31, h=19, m=15)
          # consider clocks set (x hours + 15 minutes) ago
          for x in irange(0, 1000):
            t = hms2t(h=x, m=15)
            # wall clock (has it lost 12 hours?)
            w = t - W(f, t)
            if w % H12 == 0:
              printf("-> wall clock: set @ {s}", s=t2hms(tgt - t))
              break
            # digital clock (has it gained 24 hours?)
            d = D(f, t) - t
            if d % H24 == 0:
              printf("-> digital clock: set @ {s}", s=t2hms(tgt - t))
              break
          printf()
      

      Solution: The latest time is 11:00:00 (i.e. 11:00 am) on the 26th.


      The wall clock loses 32 seconds every 57 seconds (i.e. it goes forward at a rate of 25 seconds every 57 seconds).

      And the digital clock gains (41/40)×32 seconds every 57 seconds = 164/5 seconds every 57 seconds = 164 seconds every 285 seconds. So it goes forwards at a rate of 449 seconds every 285 seconds.

      These are very inaccurate clocks.

      If we suppose the clocks are put right at midnight (= 00:00:00), then in 95 hours time, it will be 23:00:00, almost 4 days later.

      And the wall clock will have advanced by:

      95 × 3600 × (25/57) = 150000 seconds
      = 1 day, 17 hours, 40 minutes

      So it will be showing a time of 5:40 (pm).

      The digital clock will have advanced by:

      95 × 3600 × (449/285) = 538800 seconds
      = 6 days, 5 hours, 40 minutes

      So it will be showing a time of 05:40:00.

      i.e. both clocks will be showing a time of exactly “twenty to six”.


      Now let us suppose the wall clock is set to the right time at 11:00:00 on the 26th.

      At 19:15:00 on the 31st the elapsed time is 5 days, 8 hours, 15 minutes = 461700 seconds.

      And the wall clock will be showing an elapsed time of:

      461700 × (25/57) = 202500 seconds
      = 2 days, 8 hours, 15 minutes

      i.e. the time showing will be: 7:15 (pm), as required.

      Like

  • Jim Randell 4:15 pm on 11 March 2022 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3103: Empowered 

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

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

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

    What is the length of cable needed?

    [teaser3103]

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

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

      This Python program runs in 47ms.

      Run: [ @replit ]

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

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

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

      x² + y² = 123²

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

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

      And the amount of cable required is d we have:

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

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

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

      Hence:

      w = 5
      d = 127

      Like

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

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

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

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

      Like

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

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

        Like

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

      @Jim:

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

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

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

      Like

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

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

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

      Like

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

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

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

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

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

        Like

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

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

      Like

  • Jim Randell 4:34 pm on 17 December 2021 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3091: Birthday money 

    From The Sunday Times, 19th December 2021 [link] [link]

    My two daughters were born on the same day but seven years apart. Every birthday, with only one year’s exception, I have given them both five pounds for each year of their age. They are now grown-up, but I have continued to do this on their birthdays, except for the one year when I couldn’t afford to give either of them anything. Averaged out over all of their birthdays, including the one for which they received nothing, my elder daughter has now received 21 per cent more per birthday than her younger sister.

    How much in total have I given to my daughters as birthday presents?

    [teaser3091]

     
    • Jim Randell 5:08 pm on 17 December 2021 Permalink | Reply

      This Python program finds the solution constructively. It runs in 52ms.

      Run: [ @replit ]

      from enigma import Rational, irange, unzip, printf
      
      Q = Rational()
      
      # look for solutions
      def solve():
        # initial ages
        ages = [7, 0]
      
        # collect gifts (newest first)
        gifts = list(list(5 * x for x in irange(age, 1, step=-1)) for age in ages)
        totals = list(sum(x) for x in gifts)
      
        while True:
          # add in data for the next year
          for (i, _) in enumerate(ages):
            ages[i] += 1
            v = 5 * ages[i]
            gifts[i].insert(0, v)
            totals[i] += v
      
          # consider missing years
          for ms in unzip(gifts):
            # calculate averages without missing year
            avgs = list(Q(t - m, a) for (t, m, a) in zip(totals, ms, ages))
      
            # look for avgs[0] = 121% of avgs[1]
            if 100 * avgs[0] == 121 * avgs[1]:
              yield (ages, totals, ms)
      
      # find the first solution
      for (ages, totals, ms) in solve():
        t = sum(totals) - sum(ms)
        printf("total = {t}; ages = {ages}; missing={ms}")
        break
      

      Solution: The total of the gifts is £6660.

      The daughters are currently aged 40 and 33, and the missing amounts are £140 and £105, when the daughters were 28 and 21.

      In total the elder daughter has received £3960 (an average of £99 per year), and the younger has received £2700 (an average of £81 + 9/11 per year).

      And we have:

      121% of (81 + 9/11)
      = (121/100) × (900/11)
      = 99


      Analytically we see that the £5 multiplier cancels out and we are looking for values of:

      (T(n + 7) − (k + 7)) / (n + 7) = (121/100) (T(n) − k) / n

      where: n is the age of the younger daughter, and k ∈ [1, n] is her age in the missing year.

      This simplifies to:

      k = (3n² − 76n − 479)n / (6n + 242)

      And we can then just look for the first n that gives a viable value for k:

      from enigma import irange, inf, div, T, printf
      
      # consider age of youngest daughter
      for n in irange(1, inf):
        # calculate missing year
        k = div(((3 * n - 76) * n - 479) * n, 6 * n + 242)
        if not(k is None or k < 0 or k > n):
          # output solution
          t1 = T(n) - k
          t2 = T(n + 7) - (k + 7)
          t = 5 * (t1 + t2)
          printf("[n={n} k={k}] total = {t}; ages = ({n+7}, {n})")
          break
      

      Further analysis shows that in order for k to be positive we require: n > (38 + √2881) / 3 ≈ 30.56.

      And for k ≤ n we require: n ≤ 103/3 ≈ 34.33.

      So we only need to check k ∈ [31, 34], which we can do manually.

      n = 31 ⇒ k = 3.48…
      n = 32 ⇒ k = 11.87…
      n = 33 ⇒ k = 21
      n = 34 ⇒ k = 30.87…

      Like

    • GeoffR 9:12 am on 18 December 2021 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % Assume max daughters ages are 63 and 70 years and father is in his nineties.
      % Max UB amount - 1st daughter = 63 * 64 div 2 * 5 = 10080, say 10100
      % Max UB amount - 2nd daughter = 70 * 71 div 2 * 5 = 12425, say 12500
      
      var 1..63:D1; % max 1st daughter's age
      var 1..70:D2; % max 2nd daughter's age
      var 1..63: MA; % missed age year
      
      % Total gift amounts for two daughters
      var 5..10100: D1_tot;
      var 5..12500: D2_tot;
      var 10..22600: Total;
      
      % Elder daughter is 7 years older than her sister
      constraint D2 == D1 + 7;
      
      % Total gift amounts, allowing for the missing age year
      constraint D1_tot == 5 * D1 * (D1 + 1) div 2 - 5 * MA;
      constraint D2_tot == 5 * D2 * (D2 + 1) div 2 - 5 * (MA + 7);
      constraint Total == D1_tot + D2_tot;
      
      % Elder daughter received 21 per cent more per birthday than her sister
      % (D2_tot/D2) / (D1_tot/D1) = 121/100
      constraint 100 * D2_tot * D1 == 121 * D1_tot * D2;
      
      solve satisfy;
      
      output ["Total (£) = " ++ show(Total) ++ "\n" ++ "Daughter's ages are " ++ 
      show(D1) ++ " and " ++ show(D2) ++ " years"]; 
      
      
      
      

      Like

    • NigelR 3:23 pm on 19 December 2021 Permalink | Reply

      apologies Jim – I haven’t worked out how to post code properly. Is there a guide somewhere, please?

      acum,bcum=140,0  #140 is accumulated gifts for daughter 1 for birthdays 1-7
      for y in range(8,90): #start from 1st birthday for daughter 2
          acum+=5*y
          bcum+=5*(y-7)
          for i in range (8,y):  #iterate over previous years to remove 1 year at a time
              if abs(((acum-5*i)/y)-1.21*((bcum-(5*(i-7)))/(y-7)))<0.0001:
                  print("total gifted is:",(acum-5*i)+(bcum-5*(i-7)))
      

      Like

      • Jim Randell 3:44 pm on 19 December 2021 Permalink | Reply

        Hi,

        You can include code like this:

        [code language="python"]
        your code here
        [/code]
        

        For longer programs (80 lines for more) you can also include the collapse="true" parameter, to hide it until clicked on.

        Be careful though,it is not possible to edit a comment in WordPress once it is posted.

        Like

    • Tony Brooke-Taylor 7:31 am on 20 December 2021 Permalink | Reply

      With a bit of rearrangement of a formula for the ratio of averages you can pretty much solve this manually. Once you have the limits you can almost intuit the correct value for the younger daughter’s age but the program below loops until it finds a solution.

      # Find real roots of a quadratic equation with conventional coefficients a, b, c
      def quad_roots(a, b, c):
          r = (b ** 2 - 4 * a * c)
          if r >= 0:
              low = (-b - r**(1/2))/2/a
              up = (-b + r**(1/2))/2/a
              return low, up
      
      
      # Define missing_year as the age of the younger daughter when the gift was missed
      # Make this the subject of the equation formed from taking the ratio of averages given
      
      # The lower bound for the younger age can be inferred from the condition that missing_year exceeds 0
      low_lim = max([int(r) for r in quad_roots(3, -76, -479) if r > 0]) + 1
      # The upper bound for the younger age can be inferred from the condition that it exceeds missing_year
      up_lim = max([int(r) for r in quad_roots(3, -(76 + 6), -(479 + 242)) if r > 0]) + 1
      
      # Find the value for the age now of the younger daughter, such that missing_year is an integer
      for young_age, missing_year in ((n, (3 * n ** 2 - 76 * n - 479) / (6 * n + 242) * n) for n in range(low_lim, up_lim)):
          if missing_year % 1 == 0:
              total = 0
              for d in [0, 7]:
                  total += ((young_age + d) * ((young_age + d)+1)/2 - (missing_year + d))
              print("Total given to both daughters is", total * 5)
              break
      
      

      Like

  • Jim Randell 4:05 pm on 12 November 2021 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3086: Four-sided dice game 

    From The Sunday Times, 14th November 2021 [link] [link]

    I have two identical four-sided dice (regular tetrahedra). Each die has the numbers 1 to 4 on the faces. Nia and Rhys play a game in which each of them takes turns throwing the two dice, scoring the sum of the two hidden numbers. After each has thrown both dice three times, if only one of them scores an agreed total or over, then he or she is the winner. Otherwise the game is drawn.

    After Rhys had taken two throws, before Nia took her second throw she noticed that they both had a chance of winning, but if things had gone differently, they could have reached a situation where Rhys had scored a lower total on his two throws, and Nia had scored twice her current total with a single throw, then in that situation Nia’s chance of winning would be 35 times what it was in reality.

    What are Nia’s and Rhys’ actual scores (so far) and what is the agreed winning total?

    I have modified the wording of this puzzle slightly to make it clearer (hopefully).

    [teaser3086]

     
    • Jim Randell 6:05 pm on 12 November 2021 Permalink | Reply

      After a couple of false starts with no solution found, I decided that we are looking for a hypothetical probability of N winning that is 35× what the actual probability is.

      This Python program runs in 58ms.

      Run: [ @replit ]

      from enigma import (Rational, multiset, subsets, multiply, printf)
      
      Q = Rational()
      
      # possible scores and their frequency for a single throw of the pair
      scores = multiset.from_seq(a + b for (a, b) in subsets((1, 2, 3, 4), size=2, select="M"))
      T = scores.size()
      
      # possible totals from 1, 2 throws
      total1 = set(scores.keys())
      total2 = set(sum(s) for s in subsets(total1, size=2, select="R"))
      total3 = set(sum(s) for s in subsets(total1, size=3, select="R"))
      
      # calculate probabilities of reaching target <tgt> from totals <ts> with <k> additional throws
      def probabilities(tgt, ts, k):
        d = T ** k
        ps = dict()
        for t in ts:
          n = sum(multiply(scores[x] for x in xs) for xs in subsets(total1, size=k, select="M") if t + sum(xs) >= tgt)
          ps[t] = Q(n, d)
        return ps
      
      # consider possible targets
      for tgt in total3:
      
        # probabilities of reaching target after one and two throws
        p1 = probabilities(tgt, total1, 2)
        p2 = probabilities(tgt, total2, 1)
      
        # look for possible N totals, where 2N is also possible
        for (N, pN) in p1.items():
          if not (0 < pN < 1): continue
          pN_ = p1.get(2 * N)
          if pN_ is None: continue
      
          # consider possible R, pR values
          for (R, pR) in p2.items():
            if not (0 < pR < 1): continue
      
            # calculate N's actual probability of winning
            w = pN * (1 - pR)
            w_ = 35 * w
            if w_ > 1: continue
      
            # look for lower hypothetical R_ value, that gives N a probability of w_
            for (R_, pR_) in p2.items():
              if not (R_ < R and pN_ * (1 - pR_) == w_): continue
      
              # output solution
              printf("tgt={tgt}; N={N} pN={pN} pN_={pN_}; R={R} pR={pR}; R_={R_} pR_={pR_}")
      

      Solution: Nia has scored 2 on her single throw. Rhys has scored 13 from his two throws. The target total is 17.

      N has a 5/256 (≈ 2.0%) probability of reaching the target, and R’s probability would be 13/16 (≈ 81%).

      So N’s overall probability of winning is: (5/256)(3/16) = 15/4096 (≈ 0.37%).

      However if N had scored twice as much on her throw (i.e. 4) she would have a 35/256 (≈ 14%) probability of reaching the target, and if R had scored only 9 on his two throws, his probability would be 1/16 (≈ 6.3%).

      And the overall probability of N winning in this situation would be: (35/256)(15/16) = 525/4096 (≈ 13%).

      And we see: 35 × 15/4096 = 525/4096, as required.

      Like

      • Jim Randell 11:13 am on 14 November 2021 Permalink | Reply

        Here is a faster version of my program. It avoids recalculation of probabilities, and keeps values in the integers.

        Run: [ @replit ]

        from enigma import (multiset, multiply, subsets, cached, printf)
        
        # possible scores, and their frequency for 1 throw of 2 dice
        scores = multiset.from_seq(a + b for (a, b) in subsets((1, 2, 3, 4), size=2, select="M"))
        T = scores.size()
        T2 = T * T
        T3 = T * T2
        
        # possible totals from 1, 2, 3 throws
        total = { 1: sorted(scores.keys()) }
        total.update((i, sorted(set(sum(s) for s in subsets(total[1], size=i, select="R")))) for i in (2, 3))
        
        # probability of scoring n or more in k throws
        @cached
        def prob(n, k):
          if n < 0: return 0
          return sum(multiply(scores[x] for x in xs) for xs in subsets(total[1], size=k, select="M") if sum(xs) >= n)
        
        # consider possible targets
        for tgt in total[3]:
        
          # consider actual total for N after 1 throw
          for N in total[1]:
            N_ = 2 * N
            if not (N_ in total[1]): continue
            # calculate N's actual probability of reaching the target in 2 throws
            pN = prob(tgt - N, 2) # / T2
            if not(0 < pN < T2): continue
        
            # calculate N's hypothetical probability of reaching the target in 2 throws
            pN_ = prob(tgt - N_, 2) # / T2
        
            # consider possible R, pR values    
            for R in total[2]:
              pR = prob(tgt - R, 1) # / T
              if not(0 < pR < T): continue
        
              # calculate N's actual probability of winning
              w = pN * (T - pR) # / T3
              w_ = 35 * w
              if w_ > T3: continue
        
              # look for lower hypothetical R_ value, that gives N a probability of w_
              for R_ in total[2]: 
                if not (R_ < R): break
                pR_ = prob(tgt - R_, 1)
                if not (pN_ * (T - pR_) == w_): continue
        
                # output solution
                printf("tgt={tgt}; N={N} pN={pN}/{T2} N_={N_} pN_={pN_}/{T2}; R={R} pR={pR}/{T}; R_={R_} pR_={pR_}/{T}")
        

        Like

        • Frits 11:03 pm on 14 November 2021 Permalink | Reply

          @Jim, your Friday night version is still the fastest when run with PyPy (timeit, 20 times 8 executions). My program also benefits from the @cached function (do you know if there is a @cached variant for lambda functions?)

          Like

          • Jim Randell 9:27 am on 15 November 2021 Permalink | Reply

            I am currently targeting CPython 3.9 as my primary platform (although I am expecting to switch to CPython 3.10 before long), but I also like my code to run on older versions of Python (including Python 2.7 where possible).

            I measured the internal run time of my original program as 7.1ms and my faster version as 1.1ms. So I was happy enough with the performance improvement. And both times are dwarfed by the overhead of running Python.

            The [[ cached ]] function can be called directly as well as used as a decorator. For example, in Teaser 3081:

            recurring = cached(lambda n: enigma.recurring(1, n, recur=1))
            

            Note that if you are targeting a Python 3 environment you can use [[ functools.lru_cache ]] which comes with the Python standard library.

            I’ve added the [[ cache() ]] function to enigma.py which will use [[ functools.cache ]] if available (it was added in Python 3.9), otherwise it uses [[ enigma.cached ]].

            Like

    • Frits 12:32 pm on 13 November 2021 Permalink | Reply

      Not storing the product structures.
      I have let the winning total start from 7, I didn’t see an easy deduction to use a better starting value.

        
      rom itertools import product
      from fractions import Fraction as RF
      
      N = 4         # number of sides
      GC = 35       # greater chance of winning
      
      # number of times out of N**rep attempts you will reach the limit
      ntimes = lambda rep, limit: sum(sum(p2) >= limit
                                  for p2 in product(range(1, N + 1), repeat=rep)) 
      
      # loop over winning totals
      for wt in range(7, 6 * N + 1):
        for nia in range(2, N + 1): 
          # number of times out of N**4 tries Nia will reach the winning total
          nt_nia = ntimes(4, wt - nia)        
          # they both have a chance of winning
          if nt_nia == 0: continue
         
          nt_nia_double = ntimes(4, wt - 2 * nia) 
         
          # GC * w1 = w2
          # nt_nia * GC / nt_nia_double = (N**2 - nt_rhys_less) / (N**2 - nt_rhys))
          if not (1 < nt_nia * GC / nt_nia_double <= N**2): continue
             
          # w1 * GC <= 1 so nt_nia * (N**2 - nt_rhys) * GC / N**6 <= 1
          # (N**2 - nt_rhys) <= N**6 / (GC * nt_nia)
          min_nt_rhys = N**2 - N**6 / (GC * nt_nia)
         
          for rhys in range(5, 4 * N + 1):
            # number of times out of N**2 attempts Rhys will reach the winning total
            nt_rhys = ntimes(2, wt - rhys)   
            # they both have a chance of winning
            if nt_rhys == 0 or nt_rhys < min_nt_rhys: continue        
       
            # calculate Nia's winning chance
            w1 = RF(nt_nia * (N**2 - nt_rhys), N**6)
            if w1 == 0: break
           
            for rhys_less in range(4, rhys):
              nt_rhys_less = ntimes(2, wt - rhys_less)    
             
              # calculate Nia's winning chance under better conditions
              w2 = RF(nt_nia_double * (N**2 - nt_rhys_less), N**6)
             
              if w2 == GC * w1:
                print(f"Nia's score: {nia}, Rhys's score: {rhys}"
                      f" and the agreed winning total: {wt}")
              elif w2 < GC * w1:
                break
      

      Like

    • Hugh Casement 12:58 pm on 14 November 2021 Permalink | Reply

      “35 times greater” would mean 36 times as much. Just the sort of silly expression that journalists use. Altogether badly worded.

      Like

      • Jim Randell 1:28 pm on 14 November 2021 Permalink | Reply

        Yes. I suppose “35 times” will do. (We can see it must have a greater value, as N has a non-zero actual probability of winning).

        I did a quick check and there is no solution to the puzzle where N’s hypothetical probability is 36× the actual probability.

        Originally I was thrown by what were were comparing N’s hypothetical probability to. (I thought maybe it was R’s hypothetical probability, bit it turns out it is N’s actual probability).

        Like

  • Jim Randell 4:39 pm on 8 October 2021 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3081: Connect four 

    From The Sunday Times, 10th October 2021 [link]

    I have four different two-digit numbers, each having at least one digit which is a three. When I multiply any three of these numbers together I get a product that, with the inclusion of a leading zero, is one or more repetitions of the repetend of the reciprocal of the fourth two-digit number. A repetend is the repeating or recurring decimal of a number. For example 1 divided by 27 is 0.037037…, giving a repetend of 037; in that case, the product would be 37 or 37037 or 37037037 etc.

    What, in ascending order, are the four two-digit numbers?

    [teaser3081]

     
    • Jim Randell 4:59 pm on 8 October 2021 Permalink | Reply

      This Python program uses the [[ recurring() ]] function from the enigma.py library to calculate the repetends. It runs in 51ms.

      Run: [ @replit ]

      from enigma import (enigma, irange, nsplit, subsets, multiply, format_recurring, printf)
      
      # find the repetend of 1/n (recurring part of the recurring decimal representation)
      recurring = enigma.cache(lambda n: enigma.recurring(1, n, recur=1))
      
      # consider 2-digit numbers containing the digit 3
      ns = list(n for n in irange(10, 99) if 3 in nsplit(n))
      
      # check this set of numbers
      def check(ss, verbose=0):
        m = multiply(ss)
        for n in ss:
          # calculate the product
          p = str(m // n)
          # find the repetend (rr)
          (i, nr, rr) = recurring(n)
          # if the repetend has leading zeros extend the product
          for d in rr:
            if d != '0': break
            p = '0' + p
          # remove copies of the repetend from the product
          k = len(rr)
          while p.startswith(rr):
            p = p[k:]
          # anything left?
          if p: return False
          if verbose: printf("-> 1/{n} = {f}; product = {p}", f=format_recurring((i, nr, rr)), p=m // n)
        # if we get this far we've done it
        return True
      
      # select 4 of the numbers
      for ss in subsets(ns, size=4):
        if check(ss):
          printf("{ss}:")
          check(ss, verbose=1)
          printf()
      

      Solution: The four numbers are: 13, 33, 37, 63.


      Without the requirement that each of the 2-digit number must contain at least one 3, we can find further sets:

      (11, 27, 37, 91)
      (11, 37, 39, 63)
      (13, 21, 37, 99)
      (13, 27, 37, 77)
      (13, 33, 37, 63) [solution to the puzzle]
      (21, 33, 37, 39)

      All these sets have a product of 999999.

      And this is a consequence of the fact that for any fraction f ≤ 1, if a k-length repdigit of 9, multiplied by f gives an integer result, then that result is a k-length repetend of f (suitably padded with leading zeros, and there will be no non-repeating part of the decimal expansion).

      So any set of numbers that multiplies to a 9-repdigit will form such a set.

      For example, multiplying the numbers in the solution to give pairs:

      999999 = (13×33)×(37×63) = 429 × 2331: 1/429 = 0.(002331)…, 1/2331 = 0.(000429)…
      999999 = (13×37)×(33×63) = 481 × 2079: 1/481 = 0.(002079)…, 1/2079 = 0.(000481)…
      999999 = (13×63)×(33×37) = 819 × 1221: 1/819 = 0.(001221)…, 1/1221 = 0.(000819)…

      Or:

      9999999 = 9 × 239 × 4649:
      1/9 = 0.(1)…; 239 x 469 = 1111111
      1/239 = 0.(0041841)…; 9 × 4649 = 41841
      1/4649 = 0.(0002151)…; 9 × 239 = 2151

      Programatically we can easily find 4-sets from the candidates that multiply together to give a 9-repdigit:

      from enigma import (irange, nsplit, subsets, multiply, seq_all_same, printf)
      
      # candidate numbers (can't be divisible by 2 or 5)
      ns = list(n for n in irange(10, 99) if 3 in nsplit(n) and n % 2 and n % 5)
      
      # look for 4-subsets that multiply to a 9-repdigit
      for ss in subsets(ns, size=4):
        p = multiply(ss)
        if seq_all_same(nsplit(p), value=9):
          printf("{ss}; product={p}")
      

      Which we could then pass to the [[ check() ]] function above to verify the solution and output information for each number.

      But there are sets that don’t have a 9-repdigit product, and do have decimal expansions with non-repeating parts, e.g.:

      9990 = 54 × 185
      1/54 = 0.0(185)…
      1/185 = 0.0(054)

      (Although I haven’t found any that aren’t a 9-repdigit multiplied by a power of 10).

      But I did find that the four 2-digit numbers {28, 74, 78, 99} have the following property:

      1/28 = 0.3(571428)…; 74 × 78 × 99 = 571428

      Unfortunately it doesn’t work for the reciprocals of the other terms, but I did notice:

      1/78 = 0.0(128205)… = 0.0128(205128)…; 28 × 74 × 99 = 205128

      Like

      • Jim Randell 11:15 pm on 8 October 2021 Permalink | Reply

        And here is a faster (but slightly longer) version, using the same [[ check() ]] function, that avoids looking at all possible 4-subsets of the candidate numbers, by discarding those with a repetend that is larger than the largest possible product.

        It runs in 48ms (and the internal runtime is 884µs).

        Run: [ @replit ]

        from enigma import enigma, irange, nsplit, multiply, subsets, format_recurring, printf
        
        # find the repetend of 1/n (recurring part of the recurring decimal representation)
        recurring = enigma.cached(lambda n: enigma.recurring(1, n, recur=1))
        
        # consider 2-digit numbers containing the digit 3
        ns = list(n for n in irange(10, 99) if 3 in nsplit(n))
        
        # map numbers to repetends
        # [[ and rr[0] == '0' ]] to require repetend has a leading zero
        # [[ and not(nr) ]] to require no non-repeating part
        rep = dict((n, rr) for (n, (i, nr, rr)) in ((n, recurring(n)) for n in ns) if rr)
        
        # remove any numbers with repetends that are too big
        while True:
          M = multiply(ns[-3:])
          ks = list()
          for (k, v) in rep.items():
            if int(v) > M: ks.append(k)
          if not ks: break
          for k in ks: del rep[k]
          ns = sorted(rep.keys())
        
        # check a set of numbers
        def check(ss, verbose=0):
          m = multiply(ss)
          if verbose: printf("{ss}: product = {m}")
          for n in ss:
            # calculate the product
            p = str(m // n)
            # find the repetend (rr)
            rr = rep[n]
            # if the repetend has leading zeros extend the product
            for d in rr:
              if d != '0': break
              p = '0' + p
            # remove copies of the repetend from the product
            k = len(rr)
            while p.startswith(rr):
              p = p[k:]
            # anything left?
            if p: return False
            if verbose: printf("-> 1/{n} = {f}; product = {p}", f=format_recurring(*recurring(n)), p=m // n)
          # if we get this far we've done it
          return True
        
        # select 4 of the numbers
        for ss in subsets(ns, size=4):
          if check(ss):
            check(ss, verbose=1)
            printf()
        

        Like

    • GeoffR 10:35 pm on 8 October 2021 Permalink | Reply

      Instead of looking for repeating digit patterns, I thought I would try equating sets of digits in the multiplication of the three two-digit numbers with the digits in the reciprocal of the fourth two-digit number, Not a conventional approach, but it seems to work.

      A set length of nine for reciprocals/multiplications proved adequate to capture the repeating digits patterns for this set comparison method. I omitted the leading zero and decimal point for reciprocal digits set to compare them with multiplication digits. I found the full length decimal reciprocal could give a last digit which was not part of the general repeating pattern.

      from enigma import irange, nsplit
      from itertools import combinations
      
      N4 = []  # list for the groups of four two-digit numbers
      
      # consider 2-digit numbers containing the digit 3
      ns = list(n for n in irange(10, 99) if 3 in nsplit(n))
      
      for p in combinations(ns, 4):
        ab, cd, ef, gh = p
        # check 1st tuple of three numbers and the reciprocal
        s1 = set(str(ab * cd * ef)[:9]).difference(set(['0']))
        r1 = set(str(1 / gh)[:9]).difference(set(['.', '0']))
        if s1 == r1:
          # check 2nd tuple of three numbers and the reciprocal
          s2 = set(str(ab * cd * gh)[:9]).difference(set(['0']))
          r2 = set(str(1 / ef)[:9]).difference(set(['.', '0']))
          if s2 == r2:
            # check 3rd tuple of three numbers and the reciprocal
            s3 = set(str(ab * ef * gh)[:9]).difference(set(['0']))
            r3 = set(str(1 / cd)[:9]).difference(set(['.', '0']))
            if s3 == r3:
              # check 4th tuple of three numbers and the reciprocal
              s4 = set(str(cd * ef * gh)[:9]).difference(set(['0']))
              r4 = set(str(1 / ab)[:9]).difference(set(['.', '0']))
              if s4 == r4:
                L = sorted([ab, cd, ef, gh])
                if L not in N4:
                  N4.append(L)
      
      if len(N4) == 1:
        print(f"Four two digit numbers are {N4[0]}")
      
      
      

      Like

    • Frits 5:09 pm on 9 October 2021 Permalink | Reply

      from enigma import divisors
      
      # consider 2-digit numbers containing the digit 3
      nbrs = list(n for n in range(10, 100) if '3' in str(n))
        
      # retrieve repeating decimals of 1 / n
      def repdec(n):
        c = 100
        dgts = ""
        done = dict()
        i = 0
        while True:
          if c in done:
            rep = dgts[done[c]:]
            if rep[-1] == '0':
              rep = '0' + rep[:-1]
            return rep
          done[c] = i
          q, r = divmod(c, n)
          dgts += str(q)
          c = 10 * r
          i += 1   
         
      # decompose number <t> into <k> numbers from <ns>
      # so that product of <k> numbers equals <t>
      def decompose(t, k, ns, s=[]):
        if k == 1:
          if t in ns and t >= s[-1]:
            yield s + [t]
        else:
          for n in ns:
            if n not in s and (not s or n >= s[-1]):
              yield from decompose(t // n, k - 1, ns.difference([n]), s + [n])
      
      d = dict()
      for n in nbrs:
        rep = repdec(n)
        lngth = len(rep)
        if lngth > 7 or rep == 0: continue 
        r = rep
       
        # extend up to 6 digits
        for _ in range(6 // lngth):
          prod = int(r)
         
          for _ in range(1):     # dummy loop used for breaking
            # 13 * 23 * 30 <= product <= 73 * 83 * 93 
            if not(8970 <= prod <= 563487): break 
           
            # collect all divisors of product
            divs = [x for x in divisors(prod) if x in nbrs]
           
            # skip if less than 3 valid divisors
            if len(divs) < 3: break
           
            # check if product of 3 numbers equals <prod>
            for decomp in decompose(prod, 3, set(divs)):
              n4 = tuple(sorted([n] + decomp))
              d[n4] = d.get(n4, 0) + 1
        
          r += rep  # extend up to 6 digits
      
      # sets of four 2-digit numbers must have been encountered four times
      for k, v in d.items():
        if v == 4:
          print(f"answer: {k}")
       

      Like

      • Frits 11:15 am on 11 October 2021 Permalink | Reply

        or with a recursive function:

          
        # https://codegolf.stackexchange.com/questions/78850/find-the-repetend-of-the-decimal-representation    
        def replist(n, t=1, ns=[], *d):
          return ns[(*d, t).index(t):] or replist(n, (t % n) * 10, ns + [t // n], *d, t)   
         
        # retrieve repeating decimals of 1 / n 
        def repdec(n):
          return "".join(str(x) for x in replist(n)) 
        

        Like

        • Jim Randell 12:34 pm on 11 October 2021 Permalink | Reply

          It’s certainly short, although not necessarily very readable. But it does produce the right answer for positive reciprocals with a non-terminating decimal expansion.

          The puzzle text isn’t completely clear what the intended repetend is for fractions with a normally terminating decimal expansion. You could argue that in this case there is no repetend, and these numbers can be discarded.

          But I prefer the definition that the repetend is the shortest and earliest repeating section of the non-terminating decimal representation of the fraction.

          As every non-zero fraction has a unique non-terminating decimal expansion, this is well-defined.

          And it just so happens it is what the [[ recurring() ]] function returns when [[ recur=1 ]] is set. (The [[ recurring() ]] function was originally written for Enigma 1247, but has proved useful in several other Enigma puzzles).

          So, for example, we have (with repetends in parentheses):

          1/3 = 0.(3)…
          1/1 = 0.(9)…
          1/27 = 0.(037)…
          1/28 = 0.3(571428)…
          1/32 = 0.03124(9)…

          But, it does seem to be possible to solve this puzzle with a less well defined version of “repetend”.

          Like

    • Alex. T,Sutherland 1:59 pm on 10 October 2021 Permalink | Reply

      Each of the answer numbers must have a repeatable characteristic.
      (a) Number of possible x3,3x numbers =17. (b) Only 6 from these 17 are repeatable.
      (c) Evaluate any 4 from these 6 (15 possibles) to satisfy the constraints.Ony one solution.
      The sum of the solution is between 140-150. Run time 25ms.

      Like

      • Jim Randell 6:41 pm on 10 October 2021 Permalink | Reply

        @Alex: I found that 8 of the numbers had viable repetends. (i.e. ones where a single repeat was not larger than the largest possible product of three numbers). Or 7 if we exclude numbers with a terminating decimal representation.

        Like

        • Tony Brooke-Taylor 9:50 am on 12 October 2021 Permalink | Reply

          Jim I think if you add the requirement for a leading zero you can reduce this number to five possibilities. I’d be curious to compare my 5 with Alex’s 6 and your 7, once the solution embargo is lifted.

          Like

          • Jim Randell 9:57 am on 12 October 2021 Permalink | Reply

            @Tony: Yes. If you require a leading zero in the repetend, then this reduces the number of candidates to 5. (I took the “inclusion of a leading zero” to be “(where necessary)”, rather than a strict requirement).

            Reducing the set of candidates to 5, means there are only 5 sets of 4 numbers to check.

            In fact multiplying the (numerically) first 3 numbers together, gives the repetend of one of the other 2, so the answer drops out immediately. All that’s left is to check the remaining combinations work as expected. A very simple manual solution.

            Like

    • Jim Olson 4:12 pm on 11 October 2021 Permalink | Reply

      Jim is your EnigmaticCode site down temporarily?

      Like

      • Jim Randell 4:15 pm on 11 October 2021 Permalink | Reply

        Unfortunately, yes.

        It seems WordPress.com suspended the site without warning earlier today. I have contacted them to get it reinstated.

        Hopefully normal service will be resumed before too long.

        Like

    • Jim Randell 6:06 pm on 12 October 2021 Permalink | Reply

      So here’s an interesting fact, repetend fans:

      The repetend of the reciprocal of the square of the k-length 9-repdigit, consists of the concatenation of all the k-length numbers starting from zero, in order, up to the k-length 9-repdigit itself, except that the penultimate k-length number is missing.

      (And there are corresponding results for other bases).

      Let’s see:

      >>> format_recurring(recurring(1, sq(9)))
      '0.(012345679)...'
      
      >>> format_recurring(recurring(1, sq(99)))
      '0.(0001020304050607080910111213141516171819
          2021222324252627282930313233343536373839
          4041424344454647484950515253545556575859
          6061626364656667686970717273747576777879
          80818283848586878889909192939495969799)...'
      
      >>> format_recurring(recurring(1, sq(999)))
      '0.(000001002003004005006007008009010011012013014015016017018019
          020021022023024025026027028029030031032033034035036037038039
          ...
          980981982983984985986987988989990991992993994995996997999)...'
      

      And if you want to know where that penultimate term has gone, here is Numberphile to explain it all [@youtube].

      Like

  • Jim Randell 5:45 pm on 20 August 2021 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3074: Timely overthrows 

    From The Sunday Times, 22nd August 2021 [link]

    Without changing their size, Judith sews together one-foot squares of different colours that her mother has knitted, to make rectangular throws. These are usually all of the same dimensions using fewer than a hundred squares. She has observed that it takes her mother 20 per cent longer to knit each square than it takes her to sew two single squares together.

    As a one-off she has completed a square throw whose sides have the same number of squares as the longer side of her usual rectangular throws. The average time it took per square foot, both knitting and sewing, to complete the square throw was 2 per cent longer than that of the rectangular throws.

    What are the dimensions (in feet) of the rectangular throws?

    [teaser3074]

     
    • Jim Randell 6:19 pm on 20 August 2021 Permalink | Reply

      For a throw of dimensions (x, y) there are xy squares, each of which takes 6 units of time to knit.

      Each square has 4 edges, so there are 4xy edges, but the edges on the perimeter are not sewn together, so there are a total of 4xy − 2(x + y) edges that are sewn together, in pairs. And each pair take 5 units of time to sew together.

      Giving a total time for the throw of:

      time(x, y) = 6xy + 5(4xy − 2(x + y))/2
      time(x, y) = 6xy + 5(2xy − x − y)

      This Python program runs in 53ms.

      Run: [ @replit ]

      from enigma import irange, divisors_pairs, printf
      
      # total time for a throw measuring (x, y)
      time = lambda x, y: 6 * x * y + 5 * (2 * x * y - x - y)
      
      # consider the dimensions (x, y) of a "standard" throw (area < 100)
      for a in irange(1, 99):
        for (x, y) in divisors_pairs(a):
          if x == y: continue
          # total time involved
          t = time(x, y)
      
          # consider the time for a square (y, y) throw
          t2 = time(y, y)
          # the average time per square should be 2% longer
          # i.e. t2 / y^2 = 1.02(t / xy) => 100 x t2 = 102 y t
          if 100 * x * t2 == 102 * y * t:
            printf("a={a}; x={x} y={y} t={t}; t2={t2}")
      

      Solution: The standard throw is 5 ft × 7 ft.

      It has an area of 35 sq ft, and takes 500 time units to construct. i.e. 100/7 time units per square.

      A 7 ft × 7 ft throw has an area 49 sq ft, and takes 714 time units to construct. i.e. 102/7 time units per square.

      And we can easily see that this average is 1.02 times the average for a standard throw.

      Liked by 1 person

      • Jim Randell 6:39 pm on 20 August 2021 Permalink | Reply

        Solving the equation for the average time per square gives us:

        255y − 245x − 16xy = 0
        y = 245x / (255 − 16x)

        from enigma import irange, div, printf
        
        # calculate the dimension of a standard (x, y) throw
        for x in irange(1, 7):
          y = div(245 * x, 255 - 16 * x)
          if y is not None:
            printf("x={x} y={y}")
        

        Like

    • GeoffR 11:45 am on 22 August 2021 Permalink | Reply

      I found one other answer, much larger than the puzzle answer, which satisfies Jim’s equation:
      255y – 245x – 16xy = 0.

      It is x = 15, y = 245.

      Like

      • Jim Randell 1:00 pm on 22 August 2021 Permalink | Reply

        And (5, 7), (15, 245) are the only (x, y) solutions in positive integers. (Although x = 7 is very close). At x ≥ 16, y becomes negative.

        Like

    • GeoffR 2:41 pm on 23 August 2021 Permalink | Reply

      % A Solution in MiniZinc
      
      var 2..10:X;  % horizontal
      var 2..50:Y;  % vertical
      
      constraint Y > X;
      
      % Number of sewn edges = (Y - 1).X + (X - 1).Y
      % Area of rectangular throw = X * Y
      % Time to make throw and sew throw edges = 
      % 6.X.Y + 5.( (Y-1).X + (X-1).Y )
      
      % Square throw unit time = 51/50 * Rectangle throw unit time
      constraint (6*X*Y + 5*( (Y - 1)*X + (X - 1)*Y ) ) * 51 * Y * Y
      == (6*Y*Y + 10*Y*(Y - 1)) * 50 * X * Y;
      
      solve satisfy;
      
      output ["Throw dimensions (ft) are X = " ++ show(X) 
      ++ ", " ++ "Y = " ++ show(Y)];
      
      
      

      Like

  • Jim Randell 4:46 pm on 25 June 2021 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3066: Leaning tower of pesos 

    From The Sunday Times, 27th June 2021 [link]

    I have six old coins worth an odd number of pesos, comprising a mixture of one- and two-peso coins. Both denominations are of the same diameter and made of the same metal, but the two-peso coins are twice the thickness of the one-peso coins.

    After making a vertical stack of the coins I then slid each of the top five coins as far as possible to the right, to make the pile lean as much as possible in that direction, without toppling. I managed to get the rightmost edge of the top coin a distance of one and a quarter times its diameter further right than the rightmost edge of the bottom coin.

    Starting from the top, what is the value of each of the six coins?

    [teaser3066]

     
    • Jim Randell 6:04 pm on 25 June 2021 Permalink | Reply

      This is a block-stacking problem [@wikipedia] (or book-stacking, or coin-stacking, …).

      This paper [link] gives a good explanation of the basic idea. (See also this paper [link] for more complicated stackings).

      The lowest coin acts as the table, and we need to balance 5 coins on top of it.

      The following Python program runs in 53ms.

      Run: [ @replit ]

      from enigma import Rational, subsets, printf
      
      Q = Rational()
      
      # stack a collection of equal length blocks, with masses <ms>
      # return  (M, D) = (total mass, total displacement)
      def stack(ms):
        (M, D) = (0, 0)
        for m in ms:
          # considering moments: M' = M + m; M'D' = m(D + 1/2) + MD
          M += m
          D += Q(m, 2 * M)
        return (M, D)
      
      # consider the distribution of the top 5 coins
      for vs in subsets((1, 2), size=5, select="M", fn=list):
        # construct the stack
        (M, D) = stack(vs)
        # the required displacement is 5/4
        if D == Q(5, 4):
          # the bottom coin makes the total value odd
          vs.append((M % 2) + 1)
          # check each denomination is used
          if set(vs) == {1, 2}:
            printf("coins = {vs} [top to bottom]")
      

      Solution: The values of the coins are: 1, 2, 1, 2, 2, 1.

      Here is a diagram of the layout:

      The top coin is displaced from the bottom coin by 1.25 diameters.

      But this is not the maximal possible displacement, the following stacks (top to bottom) give greater displacement:

      (1, 1, 1, 2, 2, x) → 1.260 (529/420)
      (1, 2, 2, 2, 2, x) → 1.287 (811/630)
      (1, 1, 2, 2, 2, x) → 1.292 (31/24)

      Like

    • Tony Brooke-Taylor 11:57 am on 26 June 2021 Permalink | Reply

      I think I have followed a similar approach working from first principles.

      
      #Since the coins have the same diameter we can work in units of one coin radius. The thickness of the coins is irrelevant but we know that their mass is proportionate to their value
      
      #Find the horizontal position of the centre of mass for a list of coins
      #Vector A contains the positions of the centres of the coins and defines the list
      #Vector B contains the values of the coins
      def CoM(A,B):
        C=[a*b for a,b in zip(A[:len(B)],B)]
        return sum(C)/sum(A[:len(B)])
      
      #Loop over possible vectors of values for the top 5 coins (5 binaries = 32)
      for m in range(32):
        vals=[1+int(i) for i in bin(m)[2:].zfill(5)]
        dists=[2.5]#Given the position of the topmost coin...
        for d in range(5):#...find the maximum distance of the rest from the origin
          dists.append(CoM(vals,dists[:d+1])-1)
          #The edge of each coin must be immediately below the centre of mass of those above it
      
        if dists[5] == 0:#The centre of the bottom coin must be at the origin
          vals+=[1-sum(vals)%2]#To make the total value odd
          
          print("The values in order, starting from the top, were:")
          print(vals)
      
      
      

      Like

    • Hugh Casement 10:04 am on 4 July 2021 Permalink | Reply

      Given that the total value is odd, there must be an odd number of each denomination.
      Admittedly the value of the bottom coin is immaterial.

      I tested it with some parquet-floor slabs. The theoretical overhangs are not achievable in practice, as the stack starts to teeter. But one can get close.

      Like

  • Jim Randell 5:10 pm on 28 May 2021 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3062: Family stock 

    From The Sunday Times, 30th May 2021 [link]

    I have been transferring shares in the family business to my grandchildren, which I’ve done this as part of their birthday presents. On their first birthday I transferred one share, on their second birthday three shares, on their third birthday five shares etc. I have now four grandchildren and at the most recent birthday they were all of different ages. From my spreadsheet I noticed that the number of shares most recently transferred to each grandchild were all exact percentages of the cumulative total number of shares transferred to all of them so far.

    In increasing order, what are the ages of my grandchildren?

    [teaser3062]

     
    • Jim Randell 5:27 pm on 28 May 2021 Permalink | Reply

      I’m assuming the amounts transferred to each child at age k is (2k − 1) shares (so the cumulative total for this child will be k²). And the total amount transferred is the sum of all the shares transferred so far.

      The following Python program runs in 50ms.

      Run: [ @replit ]

      from enigma import irange, inf, subsets, sq, div, printf
      
      def solve():
        # consider the age of the eldest child
        for d in irange(4, inf):
          # and the younger children
          for (a, b, c) in subsets(irange(1, d - 1), size=3):
            T = sum(sq(k) for k in (a, b, c, d))
            if all(div(100 * (2 * k - 1), T) for k in (a, b, c, d)):
              yield (a, b, c, d)      
      
      for ages in solve():
        printf("ages = {ages}")
        break
      

      Solution: The children’s ages are: 1, 2, 3, 6.

      The total number of shares allocated so far is: (1) + (1 + 3) + (1 + 3 + 5) + (1 + 3 + 5 + 7 + 9 + 11) = 50.

      So any whole number of shares will be an exact percentage of the total, including the most recent allocations:

      1: 1; 1/50 = 2%
      2: 3; 3/50 = 6%
      3: 5; 5/50 = 10%
      6: 11; 11/50 = 22%

      The program stops after it finds the first solution, but I let it look for more, and there are no further solutions where the ages of the grandchildren are less than 200. (In fact it is sufficient to check d up to 49, beyond which the eldest child cannot achieve 4% of the total).


      There are also only 4 possible ages when the number of shares received by each child is required to be a whole number percentage of the total number of shares received by that child so far. (Which is how I originally read the puzzle — so I have modified the text slightly to clarify the intended interpretation).

      In this case the ages would be: 1, 2, 5, 10:

      1: 1; 1/1 = 100%
      2: 3; 3/4 = 75%
      5: 9; 9/25 = 36%
      10: 19; 19/100 = 19%

      Like

    • Brian Gladman 6:58 am on 29 May 2021 Permalink | Reply

      Jim, shouldn’t this be that at age k a grandchild receives 2.k – 1 shares?

      Like

      • Jim Randell 8:49 am on 29 May 2021 Permalink | Reply

        @Brian: Yes, it should be. Fixed up now. Thanks. I’m so used to writing odd numbers as (2k + 1).

        Like

    • GeoffR 7:31 am on 30 May 2021 Permalink | Reply

      from enigma import Timer
      timer = Timer('ST3062')
      timer.start()
           
      # Four grandchildren's ages are a, b, c, d
      for a in range(1, 19):  # child adult at age 18
        for b in range(a+1, 19):
          for c in range(b+1, 19):
            for d in range(c+1, 19):
              # Total number of shares issued
              T = a**2 + b**2 + c**2 + d**2
              # Test percentages are integers
              d1, r1 = divmod(((2 * a - 1) * 100), T)
              if r1 != 0:continue
              d2, r2 = divmod(((2 * b - 1) * 100), T)
              if r2 != 0:continue
              d3, r3 = divmod(((2 * c - 1) * 100), T)
              if r3 != 0:continue
              d4, r4 = divmod(((2 * d - 1) * 100), T)
              if r4 == 0 and a < b < c < d:
                print(f"Grandchildren's ages: {a}, {b}, {c}, {d}")
      
      timer.stop()
      timer.report()
      # [ST3062] total time: 0.0156250s (15.62ms)
      
      
      

      I tried the Timer from Jim’s enigma.py library as I could notget a time with the standard Python time module. The programme also runs satisfactorily by limiting the grandchildren’s ages to pre-teenage years (i.e. pre age 13), hence reducing the looping.
      @Jim:
      I got: [ST3062] total time: 0.0000000s (0.00us) for an upper bound of 13 for the loops.
      Am I using your Timer correctly?

      Like

      • Jim Randell 8:54 am on 30 May 2021 Permalink | Reply

        @geoff: Yes it looks like you are calling [[ Timer() ]] correctly.

        This what I get when I run your code:

        % python3.9 teaser3062geoff.py
        Grandchildren's ages: 1, 2, 3, 6
        [ST3062] total time: 0.0050900s (5.09ms)
        

        Could you tell me if you get more reasonable looking output with:

        timer = Timer('ST3062', timer='E')
        

        Like

    • GeoffR 9:05 am on 30 May 2021 Permalink | Reply

      @Jim:
      Yes, looks better – I get the following output:

      [ST3062] total time: 0.0129913s (12.99ms)

      Like

      • Jim Randell 9:27 am on 30 May 2021 Permalink | Reply

        @Geoff: Thanks.

        It means your system is claiming that it has a function for reporting process time, but that function doesn’t seem to work.

        Using the ‘E’ parameter measures elapsed time instead (sometimes referred to as “wall clock” time), and that does seem to be working.

        Let me know the value of [[ sys.platform ]] and I’ll update the code to use elapsed time as the default for that system.

        Like

    • GeoffR 9:36 am on 30 May 2021 Permalink | Reply

      @Jim:
      I get [win32] when I import sys and print sys.platform

      Like

    • Frits 2:55 pm on 30 May 2021 Permalink | Reply

      Shows the first solution (it is getting slow quite quickly).

      from enigma import inf, irange, div
      
      # decompose a number into 4 different positive square numbers
      def decompose(t, m=0, ss=[]):
        if t == 0 and len(ss) == 4:
          yield ss
        else:
          for i in range(m + 1, t):
            s = i * i
            if s > t: break
            yield from decompose(t - s, i, ss + [i])
      
      found = 0
      # check different cumulative total number of shares
      for T in irange(30, inf):
        s = list(decompose(T))
        if s:
          for x in s:
            # check for exact percentages
            if all(div(100 * (2 * k - 1), T) for k in x):
              print(f"Grandchildren's ages: {x},  cumulative total={T}")
              found = 1
          if found:   
            break # only show first solution
      

      Like

    • Frits 1:14 pm on 31 May 2021 Permalink | Reply

      Reporting all reasonable solutions.

      from enigma import is_square
      from math import ceil
      
      # decompose a number into 4 different positive square numbers
      def decompose(t, m=0, k=0, ss=[]):
        if k == 3:
          # check if last number is higher and a square  
          if t > ss[-1] ** 2:
            sr = is_square(t)
            if sr:
              yield ss + [sr]
        else:
          for i in range(m + 1, t):
            s = i * i
            # k = 1: 3*i^2 + 6*(i+1) - 1 < t        (i^2 + (i+1)^2 + (i+2)^2)
            # k = 2: 2*i^2 + 2*(i+1) - 1 < t        (i^2 + (i+1)^2) 
            if k > 0 and (4 - k) * s + (10 - 4 * k) * (i + 1) - 1 > t: break
            yield from decompose(t - s, i, k + 1, ss + [i])
      
      # only consider totals divisible by 5 and 10    
      # assume maximum age grand children to be 99
      for T in range(30, 38031, 5):
        # check which 2a - 1 parts have a whole number percentage compared to T
        sol = [2 * a - 1 for a in range(1, ceil(T ** 0.5)) 
               if (200 * a - 100) % T == 0]    
        if len(sol) > 3:    # at least 4 whole number percentages
          for s in list(decompose(T)):
            if all((2 * x - 1) in sol for x in s):
              print(f"Grandchildren's ages: {s},  cumulative total={T}")
      

      Shorter

      from math import ceil
      from itertools import combinations
      
      # only consider totals divisible by 5 and 10    
      # assume maximum age grand children to be 99
      for T in range(30, 38031, 5):
        # check which 2a - 1 parts have a whole number percentage compared to T
        sol = [2 * a - 1 for a in range(1, ceil(T ** 0.5)) 
               if (200 * a - 100) % T == 0]    
        if len(sol) > 3:    # at least 4 whole number percentages
          for c in combinations(sol, 4):
            if sum(((x + 1) // 2) ** 2 for x in c) == T:
              print(f"Grandchildren's ages: {[((x + 1) // 2) for x in c]}, "
                    f"cumulative total={T}")
      

      Like

      • Brian Gladman 5:47 pm on 2 June 2021 Permalink | Reply

        If the age of the oldest grandchild is M, their percentage of the shares is less than 100.(2.M – 1) / M^2 and this must be at least 4. Hence M is at most 49 and T is at most 9030.

        Like

        • Brian Gladman 10:31 pm on 2 June 2021 Permalink | Reply

          I believe this analysis can be improved to show that M < 18 (see here)

          Like

    • Tony Brooke-Taylor 10:16 am on 1 June 2021 Permalink | Reply

      Obsessed as I am with minimising the number of wasted trials, I ended up simplifying it down to an essentially manual solution. I have coded this up. I believe the solution is unique.

      
      #Find all sets of ages for a given number of granchildren, whose squares sum to a chosen value
      
      def find_ages(S=100,gc=4,found=[]):
        if gc<=1: 
          if (S**(1/2))%1==0: yield found + [int(S**(1/2))]
        else: 
          A_min=tuple([i+1 for i in range(gc)])
          eldest_max=int((S-sum([a**2 for a in A_min[:-1]]))**(1/2))
          if eldest_max>=A_min[-1]:
            eldest_min=max(A_min[-1]-1,int((S/2)**(1/2)))  
            for eldest in range(eldest_max,max(A_min[-1]-1,int((S/2)**(1/2))),-1):
              fnd = found + [eldest]
              yield from find_ages(S-eldest**2,gc-1,fnd)
      
        
      Grandchildren=4    
      min_ages=(i+1 for i in range(Grandchildren))
      min_shares=sum(a**2 for a in min_ages)
      
      #Consider cases in which total number of shares S is less than 100
      #If S<100 and S is an integer, k.S =100 where k is an integer factor of 100
      
      k=2
      S_cand=100
      S_vec=[]
      while S_cand > min_shares:
        S_cand=100/k
        if S_cand%1==0 and S_cand>min_shares:
          S_vec.append(S_cand)
        k+=1
      
      #Now consider cases in which total number of shares S is greater than 100
      #If S>100 and S is an integer, S =100k where k is an integer
      #For all ages a, 2a-1 = k.c(a), where all c(a) are integers
      #Further, for all positive integer a, k and c(a) must both be odd
      #Using these results, we can work out the lowest possible ages corresponding to each value of k, and thus the lowest possible value of the sum of the squares. This number exceeds 100k for all values of k above 3.
      
      S_vec+=[100*k for k in (1,3)]
      
      #Find all combinations of ages that meet the requirement for the total S
      for Shares in S_vec:
        test=find_ages(Shares,Grandchildren)  
        for t in test:
          if False not in [((a*2-1)*100/Shares)%1==0 for a in t]:
            print("If the total number of shares is", Shares,"then the grandchildren's ages are",t,"and they received", [(a*2-1)*100/Shares for a in t],"shares respectively on their last birthday.")
      
      
      

      This seems to be no quicker than an iterative solution, but it was fun dredging my memory for some O-level maths.

      Like

      • Jim Randell 3:23 pm on 1 June 2021 Permalink | Reply

        I used my program to look for additional solutions and there are no others where the ages of the grandchildren are less than 200. (Beyond which none of the amounts can be whole number percentages of the total).

        So I’m happy that the puzzle has a unique solution.

        Like

    • GeoffR 2:46 pm on 10 June 2021 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      % Upper bound as Brian/Jim's postings
      var 1..49:A; var 1..49:B; var 1..49:C; var 1..49:D;
      
      % Total cumulative shares of all grandchildren = T
      % Lower Bound of T = 1**2 + 2**2 + 3**2 + 4**2 = 30
      % Upper Bound of T = 46**2 + 47**2 + 48**2 + 49**2 = 9030
      
      var 30..9030: T = A*A + B*B + C*C + D*D;
      
      % All shares transferred are exact percentages
      constraint (2*A - 1) * 100 div T > 0 /\ (2*A - 1) * 100 mod T = 0 
      /\  (2*B - 1) * 100 div T > 0 /\ (2*B - 1) * 100 mod T = 0
      /\  (2*C - 1) * 100 div T > 0 /\ (2*C - 1) * 100 mod T = 0
      /\  (2*D - 1) * 100 div T > 0 /\ (2*D - 1) * 100 mod T = 0;
      
      % Ages are different and in increasing order
      constraint A < B /\ B < C /\ C < D;
      
      solve satisfy;
      
      output ["Grandchildrens' ages are " ++ show(A) ++ ", " ++ show(B)
      ++ ", " ++ show(C) ++ ", " ++ show(D) ];
      
      % Grandchildrens' ages are 1, 2, 3, 6
      % ----------
      % ==========
      
      

      Like

  • Jim Randell 6:03 pm on 1 April 2021 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3054: Discs a go-go 

    From The Sunday Times, 4th April 2021 [link]

    My kitchen floor is tiled with identically-sized equilateral triangle tiles while the floor of the bathroom is tiled with identically-sized regular hexagon tiles, the tiles being less than 1m across. In both cases the gaps between tiles are negligible. After much experimenting I found that a circular disc dropped at random onto either the kitchen or bathroom floor had exactly the same (non-zero) chance of landing on just one tile.

    The length of each side of the triangular tiles and the length of each side of the hexagon tiles are both even triangular numbers of mm (i.e., of the form 1+2+3+…).

    What are the lengths of the sides of the triangular and hexagonal tiles?

    [teaser3054]

     
    • Jim Randell 9:50 pm on 1 April 2021 Permalink | Reply

      For a disc of radius x dropped randomly onto the floor, the centre of it will lie in one of the tiles and we want to find out if the entire disc lies within the tile. Which it will do if the centre of the disc lies within a smaller version of the tile that has a perimeter that is a distance of x from the perimeter of the actual tile.

      If the triangular tiles have a side t, then the area of one tile is: A = (t²√3)/4

      And the inradius is: r = t/(2√3)

      The radius of the disc cannot be larger than the inradius of the triangle.

      So the smaller version of the triangle has an inradius of: (r − x)

      And the corresponding area is: a = (3√3)(r − x)²

      The probability of the disc landing entirely within a single tile is then: P = a / A

      Similarly for a hexagon with side h:

      The area of one hexagonal tile is: B = 3(h²√3)/2 (it is composed of 6 equilateral triangles).

      And the inradius is: s = h(√3)/2

      Again the radius of the disc cannot be larger than the inradius of the hexagon.

      We make a smaller hexagon with inradius = (s − x)

      And the corresponding area is: b = (2√3)(s − x)²

      And the probability of the disc landing entirely within a single tile is: Q = b / B

      This is enough to permit a programmed solution.


      The following program finds possible sides for the triangular and hexagonal tiles, and then looks for pairs that can be solved to give a disc that makes the probabilities the same.

      It runs in 73ms.

      Run: [ @replit ]

      from itertools import product
      from enigma import irange, inf, sqrt, fdiv, find_zero, printf
      
      # root 3
      r3 = sqrt(3)
      
      # find the radius of a disc that makes the probabilities equal
      def solve(t, h):
        # area of a triangular tile
        A = t * t * r3 * 0.25
        r = fdiv(t, 2 * r3)
      
        # hexagonal tile
        B = h * h * r3 * 1.5
        s = h * r3 * 0.5
      
        # find the difference between the probabilities
        def f(x):
          a = 3 * r3 * (r - x) ** 2
          b = 2 * r3 * (s - x) ** 2
          P = fdiv(a, A)
          Q = fdiv(b, B)
          return P - Q
      
        # find a zero of f
        try:
          r = find_zero(f, 1, min(r, s))
        except ValueError:
          return
      
        # output solution
        printf("t={t}mm h={h}mm [x={r.v:.2f}mm]")
      
      # generate even triangular numbers
      def tris(f):
        t = 0
        for i in irange(1, inf):
          t += i
          if t * f > 1000: break
          if t % 2 == 0: yield t
      
      # collect possible sides for the triangular tiles
      ts = list(tris(0.5 * r3))
      
      # collect possible sides for the hexagonal tiles
      hs = list(tris(r3))
      
      # select t and h, and look for a solution
      for (t, h) in product(ts, hs):
        solve(t, h)
      

      Solution: The triangular tiles have sides of 630mm. The hexagonal tiles have sides of 210mm.

      A bit more analysis (see below), shows us that the probabilities are the same when the triangular tiles have sides that are 3 times the sides of the hexagonal tiles. And as long as the disc is small enough to fit inside the tiles its size does not matter.

      So we are just looking for a pair of even triangular numbers (t, h) where t = 3h, which can be found manually or with a simple program.

      Like

      • Jim Randell 8:27 am on 2 April 2021 Permalink | Reply

        [Note: See my next comment for a better way of approach the problem and deriving the relationship between t and h].

        Wolfram Alpha [ link ] simplifies the calculation of x to:

        x = (√3)ht / (3h + t)

        Which gives a faster program:

        from itertools import product
        from enigma import irange, inf, sqrt, fdiv, printf
        
        # root 3
        r3 = sqrt(3)
        
        # find the radius of a disc that makes the probabilities equal
        def solve(t, h):
          if 3 * h <= t and t <= 3 * h:
            # output solution
            printf("t={t}mm h={h}mm")
        
        # generate even triangular numbers
        def tris(f):
          t = 0
          for i in irange(1, inf):
            t += i
            if t * f > 1000: break
            if t % 2 == 0: yield t
        
        # collect possible sides for the triangular tiles
        ts = list(tris(0.5 * r3))
        
        # collect possible sides for the hexagonal tiles
        hs = list(tris(r3))
        
        # select t and h, and look for a solution
        for (t, h) in product(ts, hs):
          solve(t, h)
        

        Like

        • Frits 10:42 am on 2 April 2021 Permalink | Reply

          @Jim,

          Could you explain the line 9 formula (which actually says if t == 3 * h)?

          If we forget about triangular numbers and we choose t=300 and h=100 and a disc so that exactly 3 discs fit in the triangle (touching the sides) do you now say that both chances are not the same?

          Like

          • Jim Randell 11:39 am on 2 April 2021 Permalink | Reply

            @Frits: It looks like the size of the disc doesn’t matter, as long as t = 3h the probabilities will be the same. I’ll look again at my equations to see why x didn’t drop out. (Line 9 is just a restatement of the inradius conditions).

            John Crabtree pointed me towards a better derivation of the relationship:


            If the triangular tiles have a side t, then the area of one tile is: A(t) = T⋅t², where T = (√3)/4

            And the inradius is: r = t/(2√3), so the disc has a radius less than this: x < r

            We make a smaller triangle with inradius = (r − x), it has sides of length: u = (t − 2(√3)x)

            If the centre of the disc lands within this triangle the entire disc will be inside the tile.

            So the area of this smaller triangle is: A(u) = T⋅u²

            And the probability of the disc falling entirely within the triangle (P) is the ratio of these areas:

            P = A(u) / A(t) = (u / t)²

            If the hexagonal tiles have a side h, then the area of the hexagon is: B(h) = H⋅h², where H = (3/2)(√3) (as it is composed of 6 equilateral triangles).

            And the inradius is: s = h(√3)/2, so the radius of the disc is also less than this: x < s

            We make a smaller hexagon with inradius = (s − x), it has sides of length: i = (h − 2x/√3), and the area is: B(i)

            So the probability of the disc falling entirely within the hexagon (Q) is the ratio of these two areas:

            Q = B(i) / B(h) = (i / h)²

            The probabilities are equal when their square roots are equal:

            P = Q
            → (u / t) = (i / h)
            → i⋅t = h⋅u
            → (h − 2x/√3)t = h(t − 2(√3)x)
            → ht − 2xt/√3 = ht − 2(√3)xh
            → 2xt/√3 = 2(√3)xh
            → t = 3h


            Hence the solution is found when t = 3h (and 0 < x < (√3)h/2), and we just need to find two even triangular numbers in the required range, where one is 3 times the other:

            from enigma import irange, inf, sqrt, divf, printf
            
            # max tile size
            M = divf(2000, sqrt(3))
            
            # collect even triangular numbers
            ts = set()
            t = 0
            for i in irange(1, inf):
              t += i
              if t > M: break
              if t % 2 == 0:
                (h, r) = divmod(t, 3)
                if r == 0 and h in ts:
                  printf("t={t}mm h={h}mm")
                ts.add(t)
            

            Like

    • Frits 9:55 pm on 1 April 2021 Permalink | Reply

      [corrected]

      # get triangular root
      tri = lambda n: 0.5 * ((8 * n + 1) ** 0.5 - 1.0)
      
      # For the same inner circle the side length of the (smallest outer) triangle
      # must be three times the side length of the (smallest outer) hexagon.
      
      # check triangular numbers
      for i in range(1, 50):
        lHex = (i * (i + 1)) // 2
        lTri = 3 * lHex
       
        # both sides must be even
        if lHex % 2 or lTri % 2: continue
       
        # the tiles being less than 1m across.
        # length across triangle: lTri, length across hexagon: lHex * sqrt(3)
        if lTri > 999:
          break
       
        if tri(3 * lHex) % 1 == 0 :
          print(f"lengths of the sides of the triangular and hexagonal tiles: "
                f"{lTri} mm and {lHex} mm")
      

      Like

      • Jim Randell 10:36 pm on 1 April 2021 Permalink | Reply

        @Frits: I don’t think that can be correct, because the answers have to be even numbers (that are also triangular).

        Like

        • Frits 10:53 pm on 1 April 2021 Permalink | Reply

          @Jim, I didn’t see that (about even).

          I calculated that for the same inner circle the side length of the (smallest outer) triangle must be three times the side length of the (smallest outer) hexagon. I hoped that would answer the probability question as well.

          Like

    • Jim Randell 6:28 pm on 3 April 2021 Permalink | Reply

      Another derivation using sectors of a regular n-gon:


      For a regular n-gon with a side length of s, we can consider a 1/n sector.

      The angle at the centre is 2θ = 360°/n ⇒ θ = 180°/n

      And the area of the entire sector is:

      A = s² / 4tan(θ)

      Reducing the height of the sector by the radius of the disc x gives:

      a = (s/2tan(θ) − x)² tan(θ) = (s − 2x tan(θ))² / 4 tan(θ)

      And the probability of the disc landing entirely within the complete tile is P = na/nA = a/A

      P = ((s − 2x tan(θ)) / s)² = (1 − (2x/s) tan(θ))²

      For the triangle tan(θ) = tan(60°) = √3, and the side length is t.

      For the hexagon tan(θ) = tan(30°) = 1/√3, and the side length is h.

      And the probabilities are equal when:

      (2x/t) tan(60°) = (2x/h) tan(30°)
      h tan(60°) = t tan(30°)
      3h = t


      Here’s a graphical demonstration of the probabilities when 3h = t.

      On the left, the hexagonal tile (green) fits exactly in the triangular tile (red), and we see that if each small triangle has area Z, then the hexagonal tile has an area 6Z and the triangular tile has an area 9Z.

      On the right there is also a smaller version of each tile, that is one radius of the disc away from the perimeter of the corresponding actual tile. If the small triangles have area z, then the small version of the hexagonal tile has an area 6z and the small version of the triangular tile has an area of 9z.

      The probability then of the disc falling in the hexagonal tile is 6z / 6Z = z/Z, and the probability of the disc falling in the triangular tile is 9z / 9Z = z/Z. Hence the probabilities are the same for each tile.

      Like

    • Tony Brooke-Taylor 10:03 am on 4 April 2021 Permalink | Reply

      I finally satisfied myself by working in terms of the vertical height of the triangles. Referring to Jim’s first diagram, for the triangular tiles, the vertical height of the inner triangle has the relationship:

      Mt’ = Mt-3x

      This is because the triangles are congruent and have the same centroid, the centroid being 1/3 of the way along the vertical height.

      For each of the six triangles in the hexagon, the inner triangle has vertical height:

      Mh’ = Mh-x

      This is because we only need to have a border for the circular disc at the outer edge of the hexagon, or the ‘bottom’ of each triangular sector.

      The area of each triangle is proportionate to the square of any relevant length, so we can ignore all constants of proportionality and state that:

      (Mt’/Mt)^2 = (Mh’/Mh)^2

      implies ((Mt-3x)/Mt)^2 = ((Mh-x)/Mh)^2

      This condition is satisfied if we make the substitution Mt=3Mh (or just take square roots of each side of the equation and rearrange).

      To find the solution, I just looped over possible values for h out of the set of even triangular numbers, setting the limit assuming the ‘across’ distance was measured from flat to flat, like a spanner.

      
      h_lim = 1000/3**(1/3)#limit width of a horizontal tile
      
      i_lim = int(((8*h_lim+1)**(1/2)-1)/2)+1#implied limit of possible triangular numbers
      
      result=[h for h in [member for item in [[i*(i+1)/2,(i+2)*(i+1)/2] for i in range(3,i_lim,4)] for member in item] if ((h*24+1)**(1/2)-1)%2==0]
      
      print("The triangles have side",result[0]*3,"mm; the hexagons",result[0],"mm")
      
      

      Like

  • Jim Randell 4:56 pm on 12 February 2021 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3047: Some permutations 

    From The Sunday Times, 14th February 2021 [link]

    I gave Robbie three different, non-zero digits and asked him to add up all the different three-digit permutations he could make from them. As a check for him, I said that there should be three 3’s in his total. I then added two more [non-zero] digits to the [original three digits] to make [a set of] five digits, all being different, and asked Robbie’s mother to add up all the possible five-digit permutations of these digits. Again, as a check, I told her that the total should include five 6’s.

    Given the above, the product of the five digits was as small as possible.

    What, in ascending order, are the five digits?

    I have changed the text of this puzzle slightly to make it clearer.

    [teaser3047]

     
    • Jim Randell 5:10 pm on 12 February 2021 Permalink | Reply

      (See also: Teaser 2863).

      This Python program runs in 64ms.

      Run: [ @repl.it ]

      from enigma import irange, subsets, nconcat, nsplit, diff, multiply, group, printf
      
      # total all permutations of a set of distinct digits
      psum = lambda ds: sum(nconcat(*s) for s in subsets(ds, size=len, select="P"))
      
      # count occurrences of digit d in number n
      dcount = lambda n, d: nsplit(n).count(d)
      
      # generate solutions
      def solve():
        # permissible digits
        digits = irange(1, 9)
      
        # choose the initial set of 3 digits
        for ds3 in subsets(digits, size=3):
          t3 = psum(ds3)
          # there should be three 3 digits in the total
          if not(dcount(t3, 3) == 3): continue
      
          # now add 2 more digits to the mix
          for ds in subsets(diff(digits, ds3), size=2):
            ds5 = ds3 + ds
            t5 = psum(ds5)
            # there should be five 6 digits in the total
            if not(dcount(t5, 6) == 5): continue
      
            printf("[{ds3} -> {t3}; {ds5} -> {t5}]")
            yield ds5
      
      # group solutions by product
      d = group(solve(), by=multiply)
      
      # output solutions
      if d:
        k = min(d.keys())
        for ds5 in d[k]:
          printf("{ds3} + {ds2}; product = {k}", ds3=ds5[:3], ds2=ds5[3:])
      

      Solution: The five digits are: 1, 2, 5, 8, 9.

      There are two scenarios with a minimal product of 720:

      (1) Robbie was given: 1, 5, 9; Additional digits: 2, 8.
      (2) Robbie was given: 2, 5, 8; Additional digits: 1, 9.

      The sum of all 3-digit permutations is 3330 (= 222 × 15).

      The sum of all 5-digit permutations is 6666600 = (266664 × 25).

      In total there are 16 candidate solutions, each with the same sums for the 3-digit and 5-digit permutations.


      In general, if we have a set of k different digits, then they can be rearranged in factorial(k) different ways, to form different numbers.

      And when these numbers are summed, each digit will appear factorial(k) / k = factorial(k − 1) times in each column.

      So we can calculate the total of all permutations without having to generate them all:

      from enigma import factorial, repdigit
      
      def psum(ds):
        k = len(ds)
        return factorial(k - 1) * repdigit(k) * sum(ds)
      

      In particular, for 3-digit numbers this simplifies to [[ 222 * sum(ds) ]] and for 5-digit numbers it simplifies to [[ 266664 * sum(ds) ]].

      The program above can be adapted using this analysis to give a solution with a run time of 51ms:

      from enigma import irange, subsets, nsplit, diff, multiply, Accumulator, inf, factorial, repdigit, printf
      
      # return multiplier for total sum of all permutations of a set of distinct digits
      psum = lambda k: factorial(k - 1) * repdigit(k)
      psum3 = psum(3)
      psum5 = psum(5)
      
      # count occurrences of digit d in number n
      dcount = lambda n, d: nsplit(n).count(d)
      
      # collect minimal products
      r = Accumulator(fn=min, value=inf, collect=1)
      
      # choose the set of 5 digits
      for ds5 in subsets(irange(1, 9), size=5):
        p = multiply(ds5)
        if p > r.value: continue
      
        # there should be five 6 digits in the total
        t5 = psum5 * sum(ds5)
        if not(dcount(t5, 6) == 5): continue
      
        # choose a subset of 3 digits
        for ds3 in subsets(ds5, size=3):
          t3 = psum3 * sum(ds3)
          # there should be three 3 digits in the total
          if not(dcount(t3, 3) == 3): continue
      
          # record the initial set of 3 digits, and the additional 2 digits
          r.accumulate_data(p, (ds3, diff(ds5, ds3)))
      
      # output solutions
      if r.count:
        for (ds3, ds2) in r.data:
          printf("{ds3} + {ds2}; product = {r.value}")
      

      Like

      • Tony Brooke-Taylor 3:11 pm on 13 February 2021 Permalink | Reply

        I think it is possible to simplify the problem to a point where the solution can be found manually. I admit I only spotted the simplifications once I had written an algorithm similar to yours Jim.

        In the 3-digit problem we can work out manually what the total must be: there is only one multiple of 222 that has three 3’s in it. Eight sets of three digits sum to the correct cofactor, of which four are symmetrical around the value 5.

        In the 5-digit problem we can also work out what the total must be: there is only one multiple of 266664 that has five 6’s in it, and I believe this is more obvious if we look at multiples of 11111. Thus we have a unique cofactor in this problem too, and the sum of the extra two digits must be the difference between the two cofactors. Only four pairs of digits make up this sum.

        If we combine the four pairs with the eight trios and deduplicate, we get ten possible sets of 5, of which six are symmetrical around the value 5.

        By trigonometry, the solution with the minimum product has the greatest distances between the central number and the others. My leap of faith is that we could also have applied this at the 3-digit stage to reduce the number of trios we needed to test.

        Like

        • Jim Randell 12:07 pm on 17 February 2021 Permalink | Reply

          @Tony: Once we’ve got the 8 pairs of triples that sum to 15, and we are extending them with a pair that sums to 10 (= (1,9) (2,8) (3, 7) (4,6)), then we only need to consider the first viable pair, as later ones will give a larger product.

          So we can exhaustively check the solution space by calculating only 7 products.


          Here’s some code that uses this analysis:

          from enigma import irange, Accumulator, printf
          
          # collect minimal product
          r = Accumulator(fn=min, collect=1)
          
          # look for sets of 3 digits (a, b, c) that sum to 15
          for a in irange(1, 4):
            for b in irange(a + 1, 6):
              c = 15 - (a + b)
              if not(b < c < 10): continue
          
              # and now add (d, e) that sum to 10
              for d in irange(1, 4):
                e = 10 - d
                if len({a, b, c, d, e}) != 5: continue
          
                # collect minimal product
                r.accumulate_data(a * b * c * d * e, ((a, b, c), (d, e)))
                break # only need to check the first viable (d, e) pair
          
          # output solutions
          if r.count:
            for (ds3, ds2) in r.data:
              printf("{ds3} + {ds2}; product = {r.value}")
          

          Like

      • Frits 10:31 am on 15 February 2021 Permalink | Reply

        @Jim,

        If you replace line 23 “t5 = psum(ds5) ” with

        t5 = 0
        for v, w, x, y, z in permutations(ds5):
          t5 += v * 10000 + w * 1000 + x * 100 + y * 10 + z
        

        your code is approx. 4.5 times faster (with Python 3.9.0).

        Maybe nconcat is not efficient if called multiple times?
        Subsets only seems to have minor overhead.

        Like

        • Jim Randell 12:40 pm on 15 February 2021 Permalink | Reply

          @Frits: In a program that runs pretty much instantaneously I am less concerned about coding for execution speed as I am that the program itself should be concise, clear and easy to modify (and, above all, correct).

          So using a general utility function like [[ nconcat() ]] makes it clear that I am turning a sequence of digits into a number, even if it is not the fastest way to achieve this.

          Although with a bit of analysis we find that we don’t have to construct numbers corresponding to all the permutations of the digits in order to arrive at the sum (and gives a general principle for attacking similar problems), which lets us write a program that runs even faster.

          But that is not to say I’m not at all interested in execution speed. I’ll have a look at improving [[ nconcat() ]], and another advantage of using utility functions is that if an improvement is made, every program that uses them gets the benefit.

          Like

    • Frits 11:23 am on 13 February 2021 Permalink | Reply

      Basic version, not really optimized for speed.

      from itertools import permutations, combinations
      
      sol = set()
      for a, b, c in combinations(range(1, 10), 3):
        t1 = 0
        for x, y, z in permutations([a, b, c]):
          t1 += x * 100 + y * 10 + z
       
        # there should be three 3's in the total
        if str(t1).count("3") == 3:
          for d in [q for q in range(1, 9) if q not in {a, b, c}]:
            for e in [q for q in range(d + 1, 10) if q not in {a, b, c}]:
              t2 = 0
              for v, w, x, y, z in permutations([a, b, c, d, e]):
                t2 += v * 10000 + w * 1000 + x * 100 + y * 10 + z
              
              # there should be five 6's in the total
              if str(t2).count("6") == 5:
                # put product up front so we can use if for sorting
                sol.add(tuple([a * b * c * d * e] + sorted([a, b, c, d, e])))
        
      if len(sol):  
        print(f"answer = {sorted(sol)[0][1:]}")   
      

      Like

    • Frits 2:07 pm on 18 February 2021 Permalink | Reply

      Partly based on Tony’s comments.

      from math import prod
      
      # Suppose a < b < c < d < e and (a + b + c + d + e) is a constant
      #
      # a * b * c * d * e is minimal 
      # if sum of distances with respect to c is maximal.
      # 
      # Proof:
      # 
      # sum of distances = (c - a) + (c - b) + (d - c) + (e - c) = d + e - a - b
      # 
      # Suppose we allow d or e to decrease with one and a or b to increase with 
      # one, so the sum stays the same. Say d' = d - 1 and b' = b + 1
      # 
      # b' * d' = (b + 1) * (d - 1) = b * d + (d - b) - 1
      # as c is between b and d we can say d - b > 1, thus d' * b' > d * b
      # so new product a * b' * c * d' * e  >  old product a * b * c * d * e
      
      # decompose number <t> into <k> different numbers from sequence <ns> 
      # so that  sum(<k> numbers) equals <t>
      # the result is already sorted on product !!
      def decompose(t, k, ns, s=[]):
        if k == 1:
          if t in ns:
            yield s + [t]
        else:
          for (i, n) in enumerate(ns):
            if not(n < t): break
            yield from decompose(t - n, k - 1, ns[i + 1:], s + [n])
      
      digits = [1, 2, 3, 4, 5, 6, 7, 8, 9]
      
      # sum permutations of 3 different digits is 222 * sum(digits)
      # last digit of sum can never be a 3 
      # so first 3 digits of sum must be all 3's
      s3 = 3340 // 222                   # sum of 3 digits
      if (s3 * 222) // 10 != 333: 
        exit()                           # no solution
      
      # sum permutations of 5 different digits is 266664 * sum(digits)
      sum5 = [x for x in range(s3 + 3, min(s3 + 18, 36)) 
              if str(266664 * x).count("6") == 5] 
              
      sol = []        
      
      for s5 in sum5:
        # we look for 5 digits a, b, c, d, e which sum to <s5>
        # and where three of them sum to <s3>
        # (a * b * c * d * e must be minimal)
      
        # choose <a> as low as possible and <e> as high as possible
        a = max(1, s5 - 30)
        e = min(9, s5 - 10)
        # d - b must be maximal
        b = max(2, s5 - 25 - a + 1)
        d = min(8, max(4, s5 - 15))
        c = s5 - (a + b + d + e)
        
        # check optimal solution 
        if len(list(decompose(s3, 3, [a, b, c, d, e]))) > 0:
          sol.append([prod([a, b, c, d, e]), (a, b, c, d, e)])
        else:
          for abcde in decompose(s5, 5, digits): 
            if len(list(decompose(s3, 3, abcde))) > 0:
              sol.append([prod(abcde), abcde])
              break  # decompose returns entries sorted on product!
        
      if len(sol) > 0:  
        sol.sort()   # sort on product
        print("answer = ", sol[0][1])
      

      Like

  • Jim Randell 4:36 pm on 18 December 2020 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3039: Three patterned paving 

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

    James is laying foot-square stones in a rectangular block whose short side is less than 25 feet. He divides this area into three rectangles by drawing two parallel lines between the longest sides and into each of these three areas he lays a similar pattern.

    The pattern consists of a band or bands of red stones laid concentrically around the outside of the rectangles with the centre filled with white stones. The number of red stone bands is different in each of the rectangles but in each of them the number of white stones used equals the number of outer red stones used.

    The total number of stones required for each colour is a triangular number (i.e., one of the form 1+2+3+…).

    What is the total area in square feet of the block?

    [teaser3039]

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

      (See also: Teaser 3007).

      After some head scratching I realised that the parallel lines are parallel to the short sides of the rectangular block, not the long sides.

      Considering a section of paving that is n stones wide and h stones long.

      If we count the number of border layers on both sides of the central area, we get an even number b, such that b < n.

      And if the border area is the same as the central area we have:

      (n − b)(h − b) = nh/2
      h = 2b(n − b) / (n − 2b)

      So for any (n, b) pair we can calculate a value for h, and accept values where b < h.

      The following Python program runs in 44ms.

      Run: [ @replit ]

      from enigma import (irange, div, subsets, all_different, is_triangular, printf)
      
      # consider values for the short side of the rectangle
      for n in irange(3, 24):
        # collect sets of (<section-length>, <border-width>)
        ss = list()
        # consider possible border values
        for b in irange(2, (n - 1) // 2, step=2):
          # calculate section length
          h = div(2 * b * (n - b), n - 2 * b)
          if h is None or not (b < h): continue
          printf("[n={n} b={b} -> h={h}]")
          ss.append((h, b))
        # choose the 3 sections
        for ((h1, b1), (h2, b2), (h3, b3)) in subsets(ss, size=3):
          # the borders are all different
          if not all_different(b1, b2, b3): continue
          # total length of the sections
          h = h1 + h2 + h3
          if not (h > n): continue
          # total number of stones for each colour
          t = div(n * h, 2)
          if t is None or not is_triangular(t): continue
      
          # output solution
          printf("{n} x {h} -> A={A} (t={t}); sections = (h={h1}, b={b1}) (h={h2}, b={b2}) (h={h3}, b={b3})", A=2 * t)
      

      Solution: The total area of the block is 2352 square feet.

      The block is 24 feet wide and 98 feet long, and is split into three sections:

      24 feet × 10 feet, border 2 deep. (120 slabs of each colour).

      24 feet × 18 feet, border 3 deep. (216 slabs of each colour).

      24 feet × 70 feet, border 5 deep. (840 slabs of each colour).

      In total 1176 slabs of each colour are required, and 1176 = T(48).

      Here’s a diagram of the three sections, with the longest one in the middle:

      Like

    • Frits 6:37 pm on 19 December 2020 Permalink | Reply

      I tried pythagorean_triples in combination with SubstitutedExpression (as n^2 + h^2 must be square) but that was too slow.

      from enigma import SubstitutedExpression, is_square
      
      # number of red stones: (n - b)(h - b)
      # number of white stones: nh/2
      # b^2 - (n + h)b + nh/2 = 0 
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [ 
        # AB = number of border layers on both sides of the central area
        # CDE = long side
        # FG = short side
        # FG is at least 15, 2+4+6 = 12, sum 3 different numbers of border layers
        #                    plus 3 whites
        "FG > 14",
        "FG < 25",
        "AB * AB - (CDE + FG) * AB + CDE * FG / 2 == 0",
        "AB > 0",
        "AB < CDE",
        "CDE > 0",
       
        # IJ = number of border layers on both sides of the central area
        # KLM = long side
        "IJ * IJ - (KLM + FG) * IJ + KLM * FG / 2 == 0",
        "IJ > 0",
        "KLM > 0",
        "IJ < KLM",
        "KLM > CDE", 
        
        # QR = number of border layers on both sides of the central area
        # STU = long side
        "QR * QR - (STU + FG) * QR + STU * FG / 2 == 0",
        "QR > 0",
        "STU > 0",
        "QR < STU",
        "STU > KLM",
        
        # the numbers of border layers are all different
        "len([AB, IJ, QR]) == len(set([AB, IJ, QR]))",
        
        # total number of stones for each colour must be triangular
        # if t is the nth triangular number, then t = n*(n+1)/2
        # and n = (sqrt(8t+1) - 1) / 2
      
        "is_square(4* FG * (CDE + KLM + STU) + 1)"
        ],
        answer="FG * (CDE + KLM + STU), FG, CDE, AB, KLM, IJ, STU, QR",
        # short side is even and < 25
        d2i=dict([(0, "F")] + \
                 [(1, "GBJR")] + \
                 [(k, "FGBJR") for k in {3, 5, 7, 9}] + \
                 [(k, "F") for k in {4, 6, 8}]),
        distinct="",
        reorder=0,
        verbose=0)   
      
      # collect and print answers 
      answs = sorted([y for _, y in p.solve()])
      print(" area,  n  h1  b1 h2  b1 h3  b3")
      for a in answs:
        print(f"{a}")
      

      Like

  • Jim Randell 4:43 pm on 23 October 2020 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3031: End of the beginning 

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

    Jenny is using her calculator, which accepts the input of numbers of up to ten digits in length, to prepare her lesson plan on large numbers. She can’t understand why the results being shown are smaller than she expected until she realizes that she has entered a number incorrectly.

    She has entered the number with its first digit being incorrectly entered as its last digit. The number has been entered with its second digit first, its third digit second etc. and what should have been the first digit entered last. The number she actually entered into her calculator was 25/43rds of what it should have been.

    What is the correct number?

    [teaser3031]

     
    • Jim Randell 4:59 pm on 23 October 2020 Permalink | Reply

      See also: Enigma 1036, Enigma 1161, Teaser 2565.

      If we have a number, where the leading digit is a and the remaining k digits are bcdefg… = r, then we have:

      r.10 + a = (25/43)(a.10^k + r)

      The following Python program runs in 45ms.

      Run: [ @replit ]

      from enigma import (irange, div, int2base, printf)
      
      # consider k digit numbers
      for k in irange(1, 9):
        m = 10 ** k
        # consider possible leading digit
        for a in irange(1, 9):
          r = div(a * (25 * m - 43), 405)
          if r is None or not (r < m): continue
          # output solution
          printf("{a}{r} -> {r}{a}", r=int2base(r, width=k))
      

      Solution: The correct number is: 530864197.

      So the number entered is: 308641975.

      >>> fraction(308641975, 530864197)
      (25, 43)
      

      For this particular puzzle we can do some analysis can reduce the solution space further. (From the 9×9 = 81 cases to consider in the general case).

      In the equation:

      43(r.10 + a) = 25(a.10^k + r)

      we see that that each side is divisible by 5, so a must be 5 (as it cannot be 0).

      Which leaves:

      r = (25.10^k − 43) / 81

      Which we can then check with the 9 possible values for k manually or with an even shorter program:

      from enigma import (irange, div, int2base, printf)
      
      for k in irange(1, 9):
        r = div(25 * 10 ** k - 43, 81)
        if r is not None:
          printf("5{r} -> {r}5", r=int2base(r, width=k))
      

      Or, for a complete manual solution:

      Numbers of the form: (25.10^k − 43) / 9, look like this:

      k=1: 23
      k=2: 273
      k=3: 2773
      k=4: 27773

      To divide by 9 again we need the number to have a digital root of 9, and the only one in the required range is:

      k=8: 277777773

      Dividing this by 9 gives:

      r = 277777773 / 9 = 30864197

      Hence the correct number is 530864197, and the incorrect number 308641975.

      Like

      • hans droog 10:01 am on 6 November 2020 Permalink | Reply

        Hi Jim. would be obliged if you could explain formula in teaser 3031. Many thanks, Hans Droog

        Like

        • Jim Randell 10:10 am on 6 November 2020 Permalink | Reply

          @hans:

          As an example, if we had an 7 digit number abcdefg which was entered incorrectly on the calculator as bcdefga, then we would have:

          bcdefga = (25/43)(abcdefg)

          If we represent the 6 digit number bcdefg as r we can write this expression as:

          r.10 + a = (25/43)(a.10^6 + r)

          The expression I give in my solution is the general case when r is a k digit number.

          (“.” is multiplication. “^” is exponentiation).

          Is that clear?

          Like

    • Frits 1:42 pm on 24 October 2020 Permalink | Reply

      Similar.

      print(["5"+str(lastpart // 81) for k in range(2, 10) 
            if (lastpart := (25 * 10**k - 43)) % 81 == 0][0])
      

      Like

    • Hugh Casement 4:15 pm on 7 November 2020 Permalink | Reply

      Hans may have been put off by Jim’s use of a decimal point to mean multiplication.
      The international convention is a raised dot.

      Like

      • Jim Randell 10:13 am on 8 November 2020 Permalink | Reply

        If I were handwriting a decimal number I would use a “middle dot” for the decimal point, and a dot on the line to denote multiplication. Of course when typing the “.” (full stop) symbol has to do for both.

        Fortunately we don’t often have to deal with numbers with decimal points in puzzles.

        Like

    • hans droog 9:01 am on 8 November 2020 Permalink | Reply

      thats right Hugh

      Like

  • Jim Randell 4:44 pm on 11 September 2020 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3025: Please mind the gap 

    From The Sunday Times, 13th September 2020 [link]

    Ann, Beth and Chad start running clockwise around a 400m running track. They run at a constant speed, starting at the same time and from the same point; ignore any extra distance run during overtaking.

    Ann is the slowest, running at a whole number speed below 10 m/s, with Beth running exactly 42% faster than Ann, and Chad running the fastest at an exact percentage faster than Ann (but less than twice her speed).

    After 4625 seconds, one runner is 85m clockwise around the track from another runner, who is in turn 85m clockwise around the track from the third runner.

    They decide to continue running until gaps of 90m separate them, irrespective of which order they are then in.

    For how long in total do they run (in seconds)?

    [teaser3025]

     
    • Jim Randell 5:28 pm on 11 September 2020 Permalink | Reply

      For the distances involved they must be very serious runners.

      I amused myself by writing a generic function to check the runners are evenly spaced. Although for the puzzle itself it is possible to use a simpler formulation that does not always produce the correct result. But once you’ve got that sorted out the rest of the puzzle is straightforward.

      This Python program runs in 55ms.

      Run: [ @replit ]

      from enigma import (irange, div, tuples, printf)
      
      # one lap of the track is 400m
      L = 400
      
      # time for separation of 85m
      T = 4625
      
      # check for equal separations
      def check_sep(ps, v):
        k = len(ps) - 1
        # calculate the remaining gap
        g = L - k * v
        if not (k > 0 and g > 0): return False
        # calculate positions of the runners
        ps = sorted(p % L for p in ps)
        # calculate the distances between them
        ds = list((b - a) % L for (a, b) in tuples(ps, 2, circular=1))
        # look for equal spacings
        return (g in ds and ds.count(v) >= k)
      
      # consider speeds for A
      for A in irange(1, 9):
        # A's distance after T seconds
        dA = A * T
        # B's distance after T seconds
        dB = div(dA * 142, 100)
        if dB is None: continue
        # A and B are separated by 85m or 170m
        if not (check_sep((dA, dB), 85) or check_sep((dA, dB), 170)): continue
      
        # now choose a whole number percentage increase on A
        for x in irange(143, 199):
          # C's distance after T seconds
          dC = div(dA * x, 100)
          if dC is None: continue
          # A, B, C are separated by 85m
          if not check_sep((dA, dB, dC), 85): continue
          printf("A={A} -> dA={dA} dB={dB}; x={x} dC={dC}")
      
          # continue until separation is 90m
          for t in irange(T + 1, 86400):
            dA = A * t
            dB = div(dA * 142, 100)
            dC = div(dA * x, 100)
            if dB is None or dC is None: continue
            if not check_sep((dA, dB, dC), 90): continue
            # output solution
            printf("-> t={t}; dA={dA} dB={dB} dC={dC}")
            break
      

      Solution: They run for 7250 seconds (= 2 hours, 50 seconds).

      After which time A will have covered 29 km (about 18 miles), B will have covered 41.2 km (about 25.6 miles), and C (who runs at a speed 161% that of A) will have covered 46.7 km (about 29 miles), which is pretty impressive for just over 2 hours.

      For comparison, Mo Farah on his recent world record breaking run of 21,330 m in 1 hour [link], would not have been able to keep up with C (who maintained a faster pace for just over 2 hours), and would be only slightly ahead of B at the 1 hour mark.

      Like

  • Jim Randell 4:59 pm on 24 July 2020 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3018: Debased 

    From The Sunday Times, 26th July 2020 [link]

    Sarah writes down a four-digit number then multiplies it by four and writes down the resultant five-digit number. She challenges her sister Jenny to identify anything that is special about these numbers. Jenny is up to the challenge as she identifies two things that are special. She sees that as well as both numbers being perfect squares she also recognises that if the five-digit number was treated as being to base 7 it would, if converted to a base 10 number, be the same as the original four-digit number.

    What is the four-digit number?

    [teaser3018]

     
    • Jim Randell 5:08 pm on 24 July 2020 Permalink | Reply

      It is straightforward to implement this directly.

      The following Python program runs in 52ms.

      Run: [ @repl.it ]

      from enigma import powers, int2base, printf
      
      # consider 4-digit squares, where 4n is a 5-digit number
      for n in powers(50, 99, 2):
        # what is n in base 7?
        n7 = int2base(n, base=7)
        # which if interpreted in base 10 is 4n
        if int2base(4 * n) == n7:
          printf("n={n} [= {n7} (base 7)]")
      

      Solution: The four digit number is: 2601.

      2601 = 51², so the answer is found on the second number tested by the program.

      4×2601 = 10404, and 10404 (base 7) = 2601 (base 10).

      Or, as a single Python expression:

      >>> peek(n for n in powers(50, 99, 2) if int2base(n, base=7) == int2base(4 * n))
      2601
      

      Like

      • Jim Randell 4:40 pm on 30 July 2020 Permalink | Reply

        Or, using the [[ SubstitutedExpression() ]] solver from the enigma.py library:

        #!/usr/bin/env python -m enigma -r
        
        SubstitutedExpression
        
        --answer="ABCD"
        --distinct=""
        
        # the 4-digit number is ABCD, and it is a square
        "is_square(ABCD)"
        
        # multiplied by 4 gives a 5 digit number
        "9999 < 4 * ABCD"
        
        # interpreting 4 * ABCD as a base 7 number gives ABCD
        "int2base(ABCD, base=7) == int2base(4 * ABCD, base=10)"
        

        Like

    • GeoffR 7:54 am on 26 July 2020 Permalink | Reply

      
      % A Solution in MiniZinc 
      include "globals.mzn";
       
      % digits for 4 digit number to base 10
      var 1..9:A; var 0..9:B; var 0..9:C; var 0..9:D; 
      var 1000..9999: ABCD = 1000*A + 100*B + 10*C + D;
      
      % digits for 5 digit number in base 7
      var 1..6:E; var 0..6:F; var 0..6:G; var 0..6:H; var 0..6:I;
      var 10000..99999: EFGHI = 10000*E + 1000*F + 100*G + 10*H + I;
      
      predicate is_sq(var int: y) =
        let {
           var 1..ceil(sqrt(int2float(ub(y)))): z
        } in
         z*z = y;
      
      % 5-digit number is four times the 4-digit number
      constraint 4 * ABCD == EFGHI;
      
      % Both 4-digit and 5-digit numbers are squares
      constraint is_sq(ABCD) /\ is_sq(EFGHI);
      
      % ABCD (base 10) = EFGHI (base 7)
      constraint ABCD == I + 7*H + 7*7*G + 7*7*7*F  + 7*7*7*7*E;
      
      solve satisfy;
      
      output [ "Four digit number (base 10) is " ++ show(ABCD) 
      ++ "\nFive digit number (base 7) is "++ show(EFGHI) ]; 
      
      

      Like

    • GeoffR 8:20 pm on 27 July 2020 Permalink | Reply

      
      from enigma import is_square, nsplit
      
      for n in range(50,100):
        if is_square(n*n):
          N4 = n*n      # 4-digit number (base 10)
          N5 = 4*n*n    # 5-digit number (base 7)
          
          # split 5-digit number N5 into digits
          a, b, c, d, e = nsplit(N5)
          
          # check N4 = N5 in specified bases
          if N4 == e + d*7 + c*7**2 + b*7**3 + a*7**4:
            print(f"4-digit number(base 10)= {n**2}")
            print(f"5-digit number(base 7)= {4*n**2}")
      
      
      

      Like

    • GeoffR 8:07 am on 28 July 2020 Permalink | Reply

      I have updated my programme to include a check that the digits (7,8,9) are not included in the 5-digit number before it is converted to base 7. In practice, the answer is found very early.

      
      from enigma import is_square, nsplit
      
      for n in range(50, 100):
        if is_square(n * n):
          N4 = n * n      # 4-digit number (base 10)
          N5 = 4 * n * n    # 5-digit number (base 7)
      
          # split 5-digit number N5 into digits
          a, b, c, d, e = nsplit(N5)
      
          # check digits 7,8,9 are not in N5, base 7
          if any(x in (a,b,c,d,e) for x in (7,8,9)):
            continue
          
          # check N4 = N5 in specified bases
          if N4 == e + d*7 + c*7**2 + b*7**3 + a*7**4:
            print(f"4-digit number(base 10)= {n**2}")
            print(f"5-digit number(base 7)= {4*n**2}")
      
      
      

      Like

      • Jim Randell 2:53 pm on 29 July 2020 Permalink | Reply

        @GeoffR: That’s why in my code I interpret a base 7 representation as base 10. There is no need to check for invalid digits, as every base 7 digit is a valid base 10 digit.

        Like

  • Jim Randell 7:06 pm on 19 June 2020 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3013: Arian Pen-blwydd 

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

    When I thought that my daughter was old enough to be responsible with money I gave her on her next, and all subsequent birthdays, cash amounts (in pounds) which were equal to her birthday age squared.

    On her last birthday her age was twice the number of years for which she received no such presents. I calculated at this birthday that if I had made these gifts on all of her birthdays then she would have received 15% more than she had actually received. I then decided that I would stop making the payments after her birthday when she would have received only 7.5% more if the payments had been made on all of her birthdays.

    What was the amount of the final birthday payment?

    There are now 300 puzzles available on the site.

    [teaser3013]

     
    • Jim Randell 9:43 pm on 19 June 2020 Permalink | Reply

      If she didn’t receive gifts for the first k years, then the “missing” gifts are the sum of the squares of 1 .. k. The amounts actually received are the sum of the squares of (k + 1) .. 2k.

      This Python program finds the value of k when the amount of the missing gifts is 15% of the actual amount, and then continues looking at future gifts until the amount becomes 7.5%.

      It runs in 53ms.

      Run: [ @repl.it ]

      from enigma import irange, inf, printf
      
      # solve the puzzle
      def solve():
        # consider the k years before the gifts started
        for k in irange(1, inf):
          # total before amount
          before = sum(x * x for x in irange(1, k))
          # total after amount
          after = sum(x * x for x in irange(k + 1, 2 * k))
          # before = 0.15 * after
          if not(100 * before == 15 * after): continue
          printf("k = {k}; before = {before}, after = {after}")
      
          # now add in future gifts
          future = after
          for n in irange(2 * k + 1, inf):
            future += n * n
            # before = 0.075 * future
            if not(1000 * before == 75 * future): continue
            printf("-> n = {n}; n^2 = {n2}, future = {future}", n2=n * n)
            return
      
      solve()
      

      Solution: The final gift was £ 1,764.

      The gifts started on the 18th birthday, so the “missing” gifts (years 1 – 17) would amount to £ 1,785.

      The actual gifts between ages 18 and 34 amount to £ 11,900, and 15% of £ 11,900 is £ 1,785.

      The gifts are to continue to age 42, making the total amount £ 23,800, and 7.5% of £ 23,800 is also £ 1,785.

      Which means the final gift is made on the 25th (silver) anniversary of the first gift.


      Analytically:

      (See: Enigma 1086).

      The sum of the first n squares is given by the square pyramidal numbers:

      SP(n) = n (n + 1) (2n + 1) / 6

      So the first part of the puzzle is to solve:

      SP(k) = 0.15 (SP(2k) − SP(k))
      20 SP(k) = 3 (SP(2k) − SP(k))
      23 SP(k) = 3 SP(2k)
      23k (k + 1) (2k + 1) = 6k (2k + 1) (4k + 1)
      23k + 23 = 24k + 6
      k = 17

      The second part is to solve, for n > 34:

      SP(k) = 0.075 (SP(n) − SP(k))
      3 SP(n) = 43 SP(k)
      SP(n) = 25585
      n = 42

      The required answer is then: n² = 42² = 1764.

      Like

      • Jim Randell 11:19 pm on 20 June 2020 Permalink | Reply

        Or, more simply:

        We are looking for values of n, k where:

        SP(k) = (3/43) SP(n)
        SP(2k) = (23/43) SP(n)

        This Python program runs in 51ms.

        Run: [ @repl.it ]

        from enigma import irange, inf, div, printf
        
        # accumulate the square pyramidal numbers, map: SP[n] -> n
        d = dict()
        x = 0
        for n in irange(1, inf):
          # calculate: x = SP(n)
          x += n * n
          d[x] = n
          # can we find a corresponding y = SP(k)?
          y = div(x * 3, 43)
          k = d.get(y, None)
          if k is None: continue
          # and verify z = SP(2k)
          z = div(x * 23, 43)
          k2 = d.get(z, None)
          if k2 is None or k2 != k * 2: continue
          printf("n^2={n2} [n={n} k={k}; SP[{k}]={y} SP[{k2}]={z} SP[{n}]={x}]", n2=n * n)
          break
        

        Like

  • Jim Randell 3:59 pm on 7 May 2020 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 3007: Paving stones 

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

    James has decided to lay square block paving stones on his rectangular patio. He has calculated that starting from the outside and working towards the middle that he can lay a recurring concentric pattern of four bands of red stones, then three bands of grey stones, followed by a single yellow stone band. By repeating this pattern and working towards the centre he is able to finish in the middle with a single line of yellow stones to complete the patio.

    He requires 402 stones to complete the first outermost band. He also calculates that he will require exactly 5 times the number of red stones as he does yellow stones.

    How many red stones does he require?

    [teaser3007]

     
    • Jim Randell 4:33 pm on 7 May 2020 Permalink | Reply

      Assuming an x by y rectangle, with x > y.

      If there are k repeats of the (red, grey yellow) bands, then y = 16k − 1.

      And the first band of red stones requires 2x + 2y − 4 = 402 stones, so x + y = 203.

      Here is a constructive program that counts the number of stones in each band. It runs in 78ms.

      from enigma import irange, inf, printf
      
      # calculate the number of stones with <k> repeats
      # and the initial band being <x> by <y>
      def stones(k, y, x):
        d = dict(R=0, G=0, Y=0)
        for i in ("RRRRGGGY" * k):
          if y < 2:
            d[i] += x * y
            break
          d[i] += 2 * (x + y - 2)
          x -= 2
          y -= 2
        return (d['R'], d['G'], d['Y'])
      
      # consider the number of repeats of the bands
      for k in irange(1, inf):
        y = 16 * k - 1
        x = 203 - y
        if not(x > y): break
       
        # calculate the number of stones needed
        (R, G, Y) = stones(k, y, x)
       
        # output solution
        if 5 * Y == R:
          printf("k={k}, y={y} x={x}; R={R} G={G} Y={Y}")
      

      Solution: James requires 5520 red stones.

      The patio consists of 6 red/grey/yellow layers, finishing with a single row of 14 yellow stones:

      The number of stones required is: red = 5520, grey = 3636, yellow = 1104; total = 10260.

      The outer band measures 108×95 stones.

      Like

    • Jim Randell 9:33 am on 10 May 2020 Permalink | Reply

      Each band requires 8 fewer stones than the previous band, so we can just start with the outermost band (402 stones) and work our way in. When we get to the number blocks for the yellow band we can adjust the number to account for a single line to see if we have reached the middle of the design, and if not carry on. We don’t need to do any analysis to work out the dimensions of the patio, or consider the number of repeats.

      This gives us a simpler, and slightly shorter, program.

      Run: [ @repl.it ]

      from enigma import irange, chunk, printf
      
      # number of blocks in outer band
      n = 402
      
      # record Red, Grey, Yellow blocks required
      R = G = Y = 0
      
      # work inwards in chunks of 8 bands
      # each band has 8 less blocks than the previous band
      for s in chunk(irange(n, 1, step=-8), 8):
        if len(s) < 8: break
        (r1, r2, r3, r4, g1, g2, g3, y) = s
        R += r1 + r2 + r3 + r4
        G += g1 + g2 + g3
        # the middle is a single row
        m = 1 + y // 2
        if 5 * (Y + m) == R:
          printf("R={R} G={G} Y={Y}", Y=Y + m)
        # otherwise, carry on
        Y += y
      

      Like

  • Jim Randell 4:56 pm on 13 March 2020 Permalink | Reply
    Tags: by: Howard Williams   

    Teaser 2999: Triangular card tower 

    From The Sunday Times, 15th March 2020 [link]

    Robbie leans two very thin playing cards together, then another two together, placing an identical card across the top forming a platform, and proceeding sideways and upwards to build a roughly triangular tower.

    For the bottom layers, he uses a whole number of 53-card packs of large cards (integer length above 70mm), the number of packs equalling the number of bottom layers. He then uses small cards (75% size) to complete the tower, which is 1428mm high. The distance between the bases of two leaning cards is always 0.56 of the length of each card.

    Robbie would like to extend the tower sideways and upwards to the next possible integer height (measured in mm), still using large cards only for the bottom layers.

    How many extra cards would be needed in total?

    [teaser2999]

     
    • Jim Randell 5:49 pm on 13 March 2020 Permalink | Reply

      I assumed a classic “house of cards” construction, where the bottom layer has n triangular supports, each constructed from 2 cards, and (n − 1) horizontal cards bridging between the supports. Each higher layer has one fewer supports than the layer below it, until we reach the top, which is composed of a single triangular support. (See my comment below for a justification of this assumption).

      For the bottom layer, if there are n supports, that uses 2n cards, and then (n − 1) horizontal cards to make the platform for the next layer. In total it requires (3n − 1) cards.

      So the total number of cards required in a tower with n layers is:

      T(n) = n (3n + 1) / 2

      The supports are isosceles triangles. If the length of card is x, and the base of the support is 0.56x across, then the height of the support is 0.96x.

      The cards are described as “very thin”, which I am assuming means they have zero thickness (even when multiple cards are measured).

      This makes the height of a tower with n layers, of which the top m layers are constructed with cards that are 75% smaller as:

      H(n, m) = 0.96x ((n − m) + 0.75m)
      H(n, m) = 0.24x (4n − m)

      And in the first tower this total height is 1428 mm. Giving:

      (4n − m) x = 5950

      So the height of the larger cards is a divisor of 5950, and we are told it is greater than 70.

      This Python program runs in 76ms.

      Run: [ @repl.it ]

      from enigma import divisors, irange, inf, div, printf
      
      # consider the length of the larger cards
      for x in divisors(5950):
        if not(x > 70): continue
        d = 5950 // x
      
        # consider the number of top rows m
        # and the total number of rows n
        for m in irange(1, inf):
          (n, r) = divmod(d + m, 4)
          if not(n > m): break
          if r != 0: continue
      
          # the total number of cards required (for the n rows)
          t = n * (3 * n + 1) // 2
          # the number of smaller cards required (for the top m rows)
          s = m * (3 * m + 1) // 2
          # and so the number of larger cards required (for the bottom n-m rows)
          b = t - s
          # the number of 53 card packs used is equal to the number of bottom rows
          if 53 * (n - m) != b: continue
      
          printf("x={x} -> m={m} n={n}; t={t} s={s} b={b}")
      
          # start adding k extra rows, counting the additional cards
          a = 0
          for k in irange(1, inf):
            # add 3 cards for each bottom row
            a += 3 * (n - m)
            # and 3 cards for each top row, plus 2 for the new top
            a += 3 * (m + k) - 1
            # calculate the new height
            h = div(6 * x * (4 * n + 3 * k - m), 25)
            # is it an integer?
            if h is not None:
              printf("-> additional cards = {a} [k={k} h={h}]")
              break
      

      Solution: 355 extra cards are required.

      The larger cards are 85 mm long (so the smaller cards are 63.75 mm long).

      The original tower consisted of 21 layers. The top 14 layers being built using the smaller cards.

      This requires 672 cards in total. 301 smaller cards are required, and 371 larger cards (= 7× 53).

      Adding 5 extra layers to the tower requires 105 larger cards (1 short of 2 extra packs), and 250 smaller cards. Making the total number of extra cards required 355.

      The height of the new tower is 1734 mm.


      Analytically:

      If n is the total number of layers in the tower (= the number of supports in the base layer), and m is the number of layers of smaller cards (so: m < n), then the requirement that the number of packs of larger cards used is the same as the number larger layers is:

      53(n − m) = T(n) − T(m)
      ⇒ 106(n − m) = 3(n² − m²) + (n − m)
      ⇒ 106 = 3(n + m) + 1
      ⇒ n + m = 35

      This gives us a limited number of (n, m) pairs.

      Then considering values for x:

      x = 5950 / (4n − m)
      ⇒ x = 5950 / (5n − 35)
      ⇒ x = 1190 / (n − 7)

      And given that x > 70, this narrows (n, m, x) down to a single value, which defines the initial tower.

      We then want to know how many lots of 0.72x we need to get an integer number of millimetres height increase.

      And this gives us the number of extra oblique columns we need to add to the initial tower, and from this we can calculate the number of extra cards required.

      All this can easily be tackled manually, or here is a quick program which looks at the possibilities:

      from enigma import divisors_pairs, irange, div, printf
      
      # consider possible card sizes
      for (n, x) in divisors_pairs(1190):
        if not(x > 70): break
        # calculate n and m
        n += 7
        m = 35 - n
        if not(n > m): continue
      
        # how many extra obliques to add?
        for k in irange(1, 25):
          h = div(18 * x * k, 25) 
          if h is None: continue
          # calculate the additional number of cards
          a = k * (3 * k + 6 * n + 1) // 2
          printf("x={x} n={n} m={m} -> k={k} h={h} a={a}")
          break
      

      Like

    • Jim Randell 4:45 pm on 15 March 2020 Permalink | Reply

      Here is a diagram of the solution found by my program, which assumes that each layer has one fewer supports than the layer below it.

      However, if the spacing of the supports is constant, then the result is only “very roughly triangular”:

      I also looked for a solution where a more “roughly triangular” shape is maintained, but this means that number of supports on the bottom layer of the smaller cards does not necessarily have one fewer supports than the layer of larger cards it is resting on (it will probably have more supports).

      And I did find a solution:

      However it does require the wording “layers” and “packs” in the puzzle text to include the possibility of a single layer and a single pack.

      I think that my original solution is probably the one the setter is looking for.


      In the original solution we can narrow the gaps between the supports in the lower part of the tower, and widen them in the upper part of the tower, to get a “roughly pentagonal” shape that is perhaps closer to the “rough triangle” that the setter is looking for. (Although applying it to the second solution would make it look even more triangular).

      Here is the first solution rendered with altered spacing (but still constant within the sections):

      And by varying the spacing within the sections it should be possible to reduce the kink in the oblique sides of the triangle, and possibly even eliminate it completely.

      In fact the idea of varying the spacing opens up the possibility of many more possible towers where the number of supports in bottom layer of smaller cards is not one less than the number of supports in the top layer of the larger cards. (Or even violating this rule within a section). So I think it makes sense to restrict the towers considered to those where the number of supports decreases by one from the layer below.

      Like

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
%d bloggers like this: