Updates from Jim Randell Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 5:16 pm on 19 February 2024 Permalink | Reply
    Tags:   

    Teaser 2671: On the face of it 

    From The Sunday Times, 1st December 2013 [link] [link]

    At the beginning of last year my wife and I were each given a clock. When we first looked at them the hands on both clocks showed the correct time but thereafter (although the two clocks coincided at least once more during the year) they generally showed different times.

    The problem was that my clock gained a certain whole number of minutes each day, and the same was true of my wife’s clock, but hers was even faster than mine. Actually my clock showed the correct time at least once in every month last year but that was not the case for my wife’s clock.

    How many minutes did each clock gain in a day?

    [teaser2671]

     
    • Jim Randell's avatar

      Jim Randell 5:17 pm on 19 February 2024 Permalink | Reply

      In this puzzle I am assuming that the clocks are standard 12-hour analogue clocks, that are not adjusted during the year (even for daylight savings time), and the correct time is also not adjusted for DST, and that the puzzle takes place in the year 2012 (it was originally published in 2013).

      Clock 1 showed the correct time at least once each month in 2012, but Clock 2 did not.

      Some time in January both clocks are correct, and some other time during the year (2012 had 366 days), both clocks are showing the same time. And the first time this happens Clock 2 is exactly 12 hours ahead of Clock 1. So during the course of up to 366 days, it has gained 720 minutes over Clock 1, this means the Clock 2 is gaining at least 2 minutes per day more than Clock 1.

      If it gains only 2 minutes more then it will take 360 days to get 720 minutes ahead of Clock 1, and so this will only work if the clocks are first looked at during the first 6 days of January. If it gains 3 or more minutes, any time in January will suffice.

      But if Clock 2 gains 720 minutes (or more) in any 29 day period, then it cannot avoid showing the right time in every month. So Clock 2 must gain less than 25 minutes per day.

      For each possible set of gains per day, this Python program looks for the earliest time in January when the clocks could give a correct time.

      It runs in 56ms. (Internal runtime is 302µs).

      Run: [ @replit ]

      from datetime import (datetime, timedelta)
      from enigma import (irange, irangef, fdiv, repeat, inc, divf, arg, printf)
      
      # year
      Y = arg(2012, 0, int)
      
      # calculate max gain for clock 2 (depends on number of days in Feb)
      M = divf(720, (datetime(Y, 3, 1) - timedelta(days=1)).day)
      
      # return day offsets when a clock gaining <x> minutes per day
      # has gained multiples of 720 minutes
      offsets = lambda x: list(irangef(0, 366, step=fdiv(720, x)))
      
      # look for earliest time when clocks are correct
      # with clock 1 gaining x min/day
      for x in irange(1, M - 2):
        # day offsets for clock 1
        ds1 = offsets(x)
        # clock 1 is correct at least once in each month
        if len(ds1) < 12: continue
      
        # clock 2 gains at least 2 min/day more than clock 1
        for y in irange(x + 2, M):
      
          # choose a time in Jan when the clocks are correct
          for t in repeat(inc(timedelta(minutes=1)), datetime(Y, 1, 1, 0, 0, 0)):
            if t.month > 1: break
      
            # find dates when clock 1 shows the correct time
            ts1 = list(t + timedelta(days=x) for x in ds1)
            # look for these occurring in 12 different months
            if not (len({t.month for t in ts1}) == 12): continue
      
            # find the dates when clock 2 is correct
            ts2 = list(t + timedelta(days=x) for x in offsets(y))
            # look for these occurring in fewer than 12 different months
            if not (len({t.month for t in ts2}) < 12): continue
            # check when the clocks are showing the same time
            s = t + timedelta(days=fdiv(720, y - x))
            if s.year > Y: continue
      
            # earliest solution found
            printf("clock 1 gains {x} mins/day")
            for z in ts1: printf("-> clock 1 correct @ {z}")
            printf("clock 2 gains {y} mins/day")
            for z in ts2: printf("-> clock 2 correct @ {z}")
            printf("clocks read same time @ {s}")
            printf()
            break
      

      Solution: The clocks gain 22 minutes and 24 minutes per day.

      If the clocks both show the correct time at midnight on 1st January 2012 then clock 1 shows the correct time at:

      2012-01-01 @ 00:00
      2012-02-02 @ 17:27
      2012-03-06 @ 10:54
      2012-04-08 @ 04:21
      2012-05-10 @ 21:49
      2012-06-12 @ 15:16
      2012-07-15 @ 08:43
      2012-08-17 @ 02:10
      2012-09-18 @ 19:38
      2012-10-12 @ 13:05
      2012-11-23 @ 06:32
      2012-12-26 @ 00:00

      We see that each of the 12 correct times occurs in a different month.

      And clock 2 shows the correct time at:

      2012-01-01 @ 00:00
      2012-01-31 @ 00:00
      2012-03-01 @ 00:00
      2012-03-31 @ 00:00
      2012-04-30 @ 00:00
      2012-05-30 @ 00:00
      2012-06-29 @ 00:00
      2012-07-29 @ 00:00
      2012-08-28 @ 00:00
      2012-09-27 @ 00:00
      2012-10-27 @ 00:00
      2012-11-26 @ 00:00
      2012-12-26 @ 00:00

      Although this clock shows 13 correct times in the same interval that the other clock shows 12 correct times, it has 2 correct times in January, 2 correct times in March, and no correct times in February.

      After 360 days, on 2012-12-26 @ 00:00, clock 1 has gained 7920 min = 5.5 days, and clock 2 has gained 8640 min = 6 days, so both clocks are showing the same (correct) time of 12:00.


      However, if we were to run the same puzzle in 2013 (not a leap year), we still get a solution with 22 min/day and 24 min/day (although dates after Feb are a day earlier, so clock 2 has 2 correct times in May not March), but we also find there is a second solution, where clock 1 gains 23 min/day and clock 2 gains 25 min/day.

      For example if the clocks both clocks show the correct time at 9:36am on 2nd January 2013, then clock 1 shows the correct time at:

      2013-01-02 @ 09:36
      2013-02-02 @ 16:54
      2013-03-06 @ 00:12
      2013-04-06 @ 07:30
      2013-05-07 @ 14:49
      2013-06-07 @ 22:07
      2013-07-09 @ 05:25
      2013-08-09 @ 12:43
      2013-09-09 @ 20:02
      2013-10-11 @ 03:20
      2013-11-11 @ 10:38
      2013-12-12 @ 17:56

      And clock 2 shows the correct time at:

      2013-01-02 @ 09:36
      2013-01-31 @ 04:48
      2013-03-01 @ 00:00
      2013-03-29 @ 19:12
      2013-04-27 @ 14:24
      2013-05-26 @ 09:36
      2013-06-24 @ 04:48
      2013-07-23 @ 00:00
      2013-08-20 @ 19:12
      2013-09-18 @ 14:24
      2013-10-17 @ 09:36
      2013-11-15 @ 04:48
      2013-12-14 @ 00:00

      After 360 days, on 2012-12-28 @ 09:36, clock 1 has gained 8280 min = 5.75 days, and clock 2 has gained 9000 min = 6.25 days, so both clocks are showing the same (incorrect) time of 3:36.

      And a third solution with the clocks gaining 22 min/day and 25 min/day, where the clocks start on 2013-01-02 @ 09:36 and show the same time after 240 days at 2013-08-30 @ 09:36.

      Like

    • Frits's avatar

      Frits 9:51 am on 23 February 2024 Permalink | Reply

         
      from datetime import date, timedelta
      from math import ceil
      
      DAYS = 366
      
      # dictionary month number per day (day 31 becomes month 2 (2012-02-01 00:00))
      d = {i: (date(2012, 1, 1) + timedelta(days=i)).month 
              for i in range(1, DAYS + 1)}
      
      # "I" need to have a correct time in at least another 11 months 
      mn = ceil(11 * 720 / DAYS)
      # maximum gain for not to have a guaranteed correct time at least once a month
      mx = ceil(720 / 29) - 1
      
      for my in range(mn, mx - 1):
        mths = set(d[ceil((m * 720) / my)]
                   for m in range(1, (my * DAYS) // 720 + 1)) 
        # at least twelve different months?
        if len({1} | mths) == 12:
          mytimes = set(ceil((m * 720) / my) 
                        for m in range(1, (my * DAYS) // 720 + 1))
        
          # my wife's clock is gaining at least 2 minutes per day more than my clock
          for wife in range(my + 2, mx + 1):
            mths = set(d[ceil((m * 720) / wife)]
                       for m in range(1, wife * DAYS // 720 + 1)) 
            if len({1} | mths) < 12:
              wifetimes = {ceil((m * 720) / wife) 
                           for m in range(1, wife * DAYS // 720 + 1)}
              # the two clocks coincided at least once more during the year     
              if mytimes & wifetimes:
                print(f"answer: {my} and {wife}")  
      

      Like

  • Unknown's avatar

    Jim Randell 4:39 pm on 16 February 2024 Permalink | Reply
    Tags: ,   

    Teaser 3204: Pressing problem 

    From The Sunday Times, 18th February 2024 [link] [link]

    The Mint’s machine can press circular coins from square plates of precious metal in straight rows with no gaps between coins. Currently, the coins are pressed with the same number of coins in each column and row, with their centres lying on the same vertical and horizontal straight lines.

    As newly appointed Warden of the Mint, Newton set about reviewing its operational efficiency. He found that more rows can be squeezed into the same plate by shifting some rows so that each coin in it touches two coins in the row above; each of these rows will have one fewer coin in it. With this method, the best that can be done is to produce exactly 8 per cent more coins per plate.

    How many more coins per plate can be produced in this way?

    Note: The intention of this puzzle is that the size of the plate allows the rows and columns of the coins in the original (square-packed) configuration to fit exactly with no extra metal around the edges. Without this condition the puzzle has multiple solutions.

    [teaser3204]

     
    • Jim Randell's avatar

      Jim Randell 4:59 pm on 16 February 2024 Permalink | Reply

      Note: See my comment below for a better program that solves the intended puzzle (and can also be used to find the multiple solutions for the original puzzle where the plate can have non-integer sizes).

      If the coins have diameter of 1, then in hexagonal packing the distance between the centres of alternate rows is (√3)/2.

      This Python program considers increasing sized squares until we achieve an 8% better yield from hexagonal packing vs. square packing.

      It runs in 56ms. (Internal runtime is 342µs).

      Run: [ @replit ]

      from enigma import (irangef, inf, intf, divf, sqrt, printf)
      
      r34 = sqrt(3, 4)
      
      # pack the coins in a square of side <x>
      # return (<number in square packing>, <number in hex packing>)
      def pack(x):
        n = intf(x)  # number of rows in square packing
        ns = n * n
        h = divf(x - 1, r34) + 1  # number of rows in hex packing
        nh = n * h
        if x % 1 < 0.5: nh -= divf(h, 2)
        return (ns, nh)
      
      # consider increasing sheet size
      for x in irangef(1.0, inf, step=0.01):
        if not (x % 1 < 0.5): continue
        (ns, nh) = pack(x)
        # does hex packing give 8% more coins? (nh/ns = 1.08)
        if 100 * nh == 108 * ns:
          printf("{d} additional coins [x={x:.2f}: ns={ns} nh={nh}]", d=nh - ns)
          break
      

      Solution: [see my comment below]

      Like

      • Frits's avatar

        Frits 12:31 pm on 17 February 2024 Permalink | Reply

        @Jim, as must be a divisible by 25 I thought you would use a different step.

        The puzzle doesn’t ask for the first solution (you use “break”).
        I am always in favour of exploring the full solution space. I still have to figure out if we can use a break based on logic

        Like

        • Jim Randell's avatar

          Jim Randell 12:55 pm on 17 February 2024 Permalink | Reply

          @Frits: You can remove the [[ break ]] to look for further solutions. But eventually you reach a point where the hexagonal packing is always better than an 8% improvement so you can stop then (without finding any further layouts – although there is a range of square sizes that give the required solution).

          Like

    • NigelR's avatar

      NigelR 9:35 am on 18 February 2024 Permalink | Reply

      It seems odd – bordering on bizarre – that, to make this teaser work in the way that most seem to be interpreting it, you have to assume that the original sheet is bigger than it needs to be by 0.33 of the coin diameter, or some 6.6%. By extension, and also noting that the puzzle is curiously worded: ‘… by shifting some rows…’ rather than: ‘…by shifting alternate rows..’, there are several solutions possible. For example, strictly consistent with the teaser as worded and using the same assumption, there is a valid solution for a much larger plate but leaving the first n rows unchanged. Only the last few rows are shifted, with a full row being added on the bottom. This yields the same required increase in coin number, but with the original sheet being oversized by a smaller percentage!

      Like

      • Jim Randell's avatar

        Jim Randell 9:53 am on 18 February 2024 Permalink | Reply

        @NigelR: Would that be “best that can be done” with that size of square though?

        I supposed the size of square depends on the pressing machine rather than the coins, as it may be used to make coins of several different sizes. And presumably the unused metal is then recycled into new plates.

        Like

        • NigelR's avatar

          NigelR 11:10 am on 18 February 2024 Permalink | Reply

          @Jim: Point taken – while my scheme would yield the right gain in coin number, it would not be optimal so is not a valid solution. I’m still troubled by the apparently arbitrary size of the original plate….!!

          Like

    • Frits's avatar

      Frits 10:43 am on 18 February 2024 Permalink | Reply

      I followed the same method as Jim and Brian but am not convinced that this is a correct approach as the wording of the puzzle isn’t fully clear to me.

      from fractions import Fraction as RF
      
      # final number of coins = 27/25 * n^2 so n must be a multiple of 5
      n = 5
      while True:
       
        # final situation: m rows with m * n - m / 2 coins and m > n
        # (starting with a row of n coins followed by a row of n - 1 coins, etc)
      
        # we may have a solution if m * n - m / 2 equals 1.08 * n^2
        # or m = (54 * n^2) / (50 * n - 25)
        # or m = 1.08 * n + 27 / (100 * n - 50) + 0.54
      
        # assume diameter coin is 1
        # height of <m> packed rows: 1 + (m - 1) * sqrt(0.75)
        # squeeze as many rows as possible (sheet is less than (n + 1) x (n + 1):
        # n + 1 - sqrt(0.75) <= height of m rows < n + 1
       
        # n + 1 - sqrt(0.75) <= 1 + (m - 1) * sqrt(0.75) < n + 1
       
        # n <= m * sqrt(0.75)
      
        # as 1.08 * sqrt(0.75) < 1 every increment of 1 of n will result in
        # an increment of the height of less than 1
        # thus as soon for a certain <n> the height is less than <n> we can
        # stop processing
      
        # final number of rows
        m = RF(54 * n**2, 50 * n - 25)
        # whole number of rows?
        if m.denominator == 1:
          # if we can't squeeze in one more row
          if n + 1 - 3**.5 / 2 <= (h := 1 + (m - 1) * 3**.5 / 2) < n + 1:
            print(f"answer: {m * n - m // 2 - n**2} coins")
       
        # when can we stop processing?
        if not (2 * n <= m * 3**.5):
          break
      
        n += 5
      

      Like

    • Pete Good's avatar

      Pete Good 5:40 pm on 19 February 2024 Permalink | Reply

      Jim,
      I solved this teaser analytically by deriving two quadratic equations for the number of coins pressed after Newton’s change. The first equation assumes that an even number of rows can be pressed and the second one assumes that an odd number of rows can be pressed. The first quadratic equation has a whole number solution and the second has none. The solution follows directly from this result.

      Like

    • Jim Randell's avatar

      Jim Randell 12:58 pm on 20 February 2024 Permalink | Reply

      It seems the way the setter intended the puzzle to work is that that square plate is an exact number of coin diameters across, and the alternate packing consists of some (but not necessarily every other) shifted, shorter rows.

      I have added a note to the puzzle text.

      Like

      • Jim Randell's avatar

        Jim Randell 1:40 pm on 20 February 2024 Permalink | Reply

        Here is a Python program that solves the intended puzzle:

        Run: [ @replit ]

        from enigma import (Accumulator, irange, irangef, inf, sqrt, intf, divf, printf)
        
        r3 = sqrt(3)
        
        # consider increasing sheet size
        for x in irangef(1.0, inf, step=1.0):
          n = intf(x)
          ns = n * n  # square packing
        
          # find maximal packing for some shifted rows
          acc = Accumulator(fn=max)
          f = x % 1
          # max number of rows in hex packing
          m = divf(x - 1, 0.5 * r3) + 1
          # consider the number of shifted rows
          for s in irange(0, divf(m, 2)):
            # calculate the number of unshifted rows we can fit in
            u = s + intf(x - 1 - s * r3) + 1
            nh = u * n + s * (n - 1 if f < 0.5 else n)
            acc.accumulate_data(nh, (u, s))
          (nh, (u, s)) = (acc.value, acc.data)
        
          # can we fit in 8% more coins?
          if 100 * nh == 108 * ns:
            printf("{d} additional coins [x={x:.2f} u={u} s={s}: ns={ns} nh={nh}]", d=nh - ns)
            break
        

        Solution: 32 additional coins per plate can be produced.

        If the coins have diameter 1 and the plate measures 20 × 20, then the original square packing produces 400 coins per sheet.

        However, by shifting 8 of the rows, we have room for 2 more unshifted rows, for a total of 432 coins, and this is an 8% increase over the original packing.

        And this is the only solution if the size of the plate is constrained to be an exact multiple of the coin diameter.


        However if size of the plate is not so constrained there are 2 further solutions.

        If we change the step at line 6 to allow non-integer square sizes (and remove the break statement), we can find the three sizes of square that give us a possible solution. The smallest is that found by my original program, and the largest is an integer sized square that gives the intended answer.

        Here is a diagram of square packing and hexagonal packing with a 5.4 × 5.4 sheet:

        This is a full hexagonal packing, where every other row is shifted (and this was how I originally interpreted the puzzle, and was the solution found by my original program above).

        We get 25 coins/sheet using square packing and 27 coins/sheet using hexagonal packing, an 8% increase.

        The minimal size square that gives this configuration is: (5√3)/2 + 1 ≈ 5.3301…

        But for squares of size 5.5 or larger the alternate rows in the hexagonal packing do not have to be reduced by one coin (as specified by the puzzle text). So the square size must be in the range 5.33… < x < 5.50.


        And with a 10.47 × 10.47 square, the square packing gives 100 coins, but by shifting 2 rows we have room for an extra row:

        This alternate packing has 108 coins, which is also an 8% increase.

        Like

  • Unknown's avatar

    Jim Randell 4:04 pm on 15 February 2024 Permalink | Reply
    Tags:   

    Teaser 2574: Higher powers 

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

    I have chosen two different two-digit numbers. They use the same two digits as each other, but in different orders. If I start with either number and raise it to a power equal to either of the two numbers, then I find that the answer is a number whose last two digits form the number with which I started.

    What are my two numbers?

    [teaser2574]

     
    • Jim Randell's avatar

      Jim Randell 4:04 pm on 15 February 2024 Permalink | Reply

      The following run file executes in 68ms. (Internal runtime of the generated program is 128µs).

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      "pow(AB, AB, 100) = AB"
      "pow(AB, BA, 100) = AB"
      
      "pow(BA, AB, 100) = BA"
      "pow(BA, BA, 100) = BA"
      
      "A < B"  # remove duplicate solution
      

      Solution: The numbers are 16 and 61.

      The powers can be calculated. We have:

      16^16 = 18 446744 073709 551616
      16^61 = 28 269553 036454 149273 332760 011886 696253 239742 350009 903329 945699 220681 916416

      Both of which end in 16, and:

      61^16 = 36751 693856 637464 631913 392961
      61^61 = 8 037480 562545 943774 063961 638435 258139 453693 382991 023311 670379 647429 452389 091570 630196 571368 048020 948560 431661

      both of which end in 61.

      Like

      • Hugo's avatar

        Hugo 4:26 pm on 15 February 2024 Permalink | Reply

        Successive powers of 16 end in 16, 56, 96, 36, 76, a repeating cycle.
        Successive powers of 61 end in 61, 21, 81, 41, 01, a repeating cycle.
        16 mod 5 = 1 = 61 mod 5. So for powers modulo 100 we take the first in each cycle
        (at least, I think that’s a logical conclusion!).

        Like

    • GeoffR's avatar

      GeoffR 7:01 pm on 15 February 2024 Permalink | Reply

       
      for A in range(1, 10):
          for B in range(A+1, 10):
              AB = 10*A + B
              BA = 10*B + A
              #  1st number properties
              if AB ** AB % 100 != AB:
                  continue
              if AB ** BA % 100 != AB:
                  continue
              # 2nd number properties
              if BA ** AB % 100 != BA:
                  continue
              if BA ** BA % 100 == BA:
                  print (f"Two numbers are {AB} and {BA}.")
      
      # Two numbers are 16 and 61.
      

      Like

  • Unknown's avatar

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

    Teaser 2661: Three clocks 

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

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

    What time did the correct clock show at that moment?

    [teaser2661]

     
    • Jim Randell's avatar

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

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

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

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

      Run: [ @replit ]

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

      Solution: The correct clock was showing: 2301.

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

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

      23:01.75 → 2301

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

      01:32.25 → 0132

      and the slow clock is showing:

      20:31.25 → 2031

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

      Like

    • Frits's avatar

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

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

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

      Like

  • Unknown's avatar

    Jim Randell 4:36 pm on 9 February 2024 Permalink | Reply
    Tags:   

    Teaser 3203: Circuit maker 

    From The Sunday Times, 11th February 2024 [link] [link]

    The racing chief tasked his designer for a new circuit. To create a 100:1 scale plan of the circuit the designer cut paper circles of 10cm radius into 12 equal sectors, then removed the top segments to create isosceles triangles with the two equal sides being 10cm. He arranged them on his desk to make a closed loop with no overlaps. Adjacent pieces always share the entire 10cm edge without overlap, but the short edges remain open.

    The chief gave the following requirements. The start-finish line must be located on a straight section of at least 140m in length. Two circular viewing towers of 19m diameter must fit into the internal area, with one at either end of the circuit.

    The designer minimised the internal area. How many triangles did he use?

    [teaser3203]

     
    • Jim Randell's avatar

      Jim Randell 5:06 pm on 9 February 2024 Permalink | Reply

      I am assuming we place triangles together so that the track runs though the long edges of the triangles, and the short edges form the edge of the track (with barriers).

      The smaller sides of the triangles would correspond to ≈5.18m (= 1 unit). So we would need 28 of them to allow a straight 140m long (27 is slightly too short). And a length of 4 of them would allow the viewing towers to fit in a central rectangle.

      So this would require 2 × (28 + 4) = 64 triangles around the inside, and another 2 × (27 + 3) + 4 × 4 = 76 to complete a simple circuit. Making 140 triangles in total, and the enclosed area is 28 × 4 = 112 sq units (≈ 3001 sq m).

      But is this simple design minimal?

      Like

      • Jim Randell's avatar

        Jim Randell 5:18 pm on 9 February 2024 Permalink | Reply

        No, it isn’t.

        I have found another design that allows the viewing towers to fit in a smaller central area (110.42 sq units ≈ 2959 sq m) (and also uses fewer triangles).

        Like

      • Jim Randell's avatar

        Jim Randell 3:47 pm on 10 February 2024 Permalink | Reply

        And now I’ve found another design that I’m fairly convinced must have a minimal enclosed area for the viewing towers.

        The total area enclosed is 623.2 sq m, and 567.1 sq m is taken up by the viewing towers, leaving just over 56 sq m of unused area.

        However this does lead to a family of designs with the same enclosed area, but different numbers of triangles. Maybe we want the smallest number of triangles made from a whole number of circles?

        Like

        • Mark Valentine's avatar

          Mark Valentine 6:25 pm on 10 February 2024 Permalink | Reply

          Interesting. Can’t visualise how there are multiple triangle numbers for the minimal area.

          Like

    • Jim Randell's avatar

      Jim Randell 9:26 am on 12 February 2024 Permalink | Reply

      I thought I would share a couple of the answers I have found (as links for now):

      This is the smallest enclosed area I found (623 sq m), but the area is split into two parts and the track can be extended without altering the area, so I don’t think this is what the setter had in mind. [ link ]

      And here is the smallest area I have found with a single enclosed area (about 820 sq m – which I calculated numerically). [ link ]

      Like

      • Brian Gladman's avatar

        Brian Gladman 2:03 pm on 12 February 2024 Permalink | Reply

        @Jim, Your first answer was my second published answer on the Sunday Times Teaser discussion group and was ruled inadmissible by Mark himself because the base sides of the triangular tiles must remain open.

        Like

        • Jim Randell's avatar

          Jim Randell 3:21 pm on 12 February 2024 Permalink | Reply

          @Brian: I thought the method of constructing the circuit could have been explained better, and I wasn’t really sure what “the short edges remain open” was meant to mean in this context, although after a while I think I worked out how the track was to be constructed.

          But as this first layout leads to multiple possible answers for the puzzle I thought it probably wasn’t what the setter was looking for, so I looked for a solution where the enclosed area was a simple polygon, and came up with the second layout. (Although I followed a systematic approach for this layout, I don’t know for sure that the enclosed area is minimal).

          Like

          • Brian Gladman's avatar

            Brian Gladman 4:37 pm on 12 February 2024 Permalink | Reply

            I got a bit bored with drawing layouts so I thought this morning about the vertical displacement in half wrapping a tower which is 1 + 2s + 2c where s and c are sin(30) and cos(30).

            For the other half of the (partial) tower wrapping we want combinations of s ‘s and c’s that fall just short of cancelling out the vertical displacement on the other side.

            The two smallest results are 4s + 2c == 0 and 2s + 3c = 0.13. The last is your second layout which hence seems the best that can be done if 0 is ruled out.

            Like

    • Jim Randell's avatar

      Jim Randell 8:48 am on 18 February 2024 Permalink | Reply

      Here are more complete notes on the solution(s) I found:

      I found a design that uses 180 triangles, and has hardly any unused enclosed space.

      The enclosed space is 623.21 sq m, but 567.06 sq m of this is taken up by the viewing towers, leaving just 56.15 sq m of unused space.

      The “spine” of the track uses two rows of 28 triangles, which gives a distance of 144.94m between the centre lines of the outside pair, and this is enough to fit the required straight.

      Although if we are allowed to extend the straight slightly into the corners, we could reduce this to two rows of 27 triangles (to give a total of 176 triangles), with a distance of 139.76m between the centre lines of the outside pair. But as we are not trying to minimise the number of triangles, and the length of the straight is an absolute minimum the total of 180 triangles is a better fit to the requirements.

      And if the designer used a whole number of circles to make the triangles, then 15 circles would give him 180 triangles (but we can expand the design by adding 4 triangles on the spine to use any larger multiple of 4 triangles while enclosing the same area).


      A variation on this puzzle is where there is a single connected area in the middle of the track, and the solution above does not provide this. (And this may be what the setter of the puzzle originally had in mind – the requirement that the “short edges remain open” is apparently meant to restrict a triangle from being zero distance away from another triangle along the short edge).

      And we can modify the solution above to give the following layout:

      This uses 168 triangles (which is 14 circles) and gives an enclosed area of 820.13 sq m (unused area = 253.07 sq m). Although I don’t know if this is the smallest possible contiguous internal area, but if we were to extend the long straights the enclosed area would increase.

      Solution: The track was constructed using 168 triangles.


      The program I used to plot the circuits, and to calculate the internal area is here [@replit].

      Like

    • Hugo's avatar

      Hugo 11:18 am on 18 February 2024 Permalink | Reply

      It is not usual for racing cars to go round sharp corners.
      Unrealistic, even in Puzzleland. One of the worst Teasers in recent times.

      Like

      • Tony Smith's avatar

        Tony Smith 8:50 am on 19 February 2024 Permalink | Reply

        Station Hairpin, Monaco Grand Prix.

        Like

  • Unknown's avatar

    Jim Randell 11:30 am on 8 February 2024 Permalink | Reply
    Tags:   

    Teaser 2659: Two by two 

    From The Sunday Times, 8th September 2013 [link] [link]

    I have given each letter of the alphabet a different value from 0 to 25, so some letters represent a single digit and some represent two digits.

    Therefore, for example, a three-letter word could represent a number of three, four, five or six digits. With my values it turns out that:

    TWO × TWO = FOUR

    Another “obvious” fact that I can tell you is that every digit occurring in TWO is a prime!

    What is the number FOUR?

    Interestingly, one of the earliest published alphametic puzzles was:

    TWO × TWO = THREE

    (using more usual alphametic rules), which appeared almost 100 years ago in the July 1924 issue of Strand Magazine.

    [teaser2659]

     
    • Jim Randell's avatar

      Jim Randell 11:31 am on 8 February 2024 Permalink | Reply

      Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library (although the method of constructing alphametic words is different from the usual alphametic rules).

      It runs in 194ms. (Internal runtime of the generated program is 78ms).

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      --base=26
      
      --code="nconc = lambda *ss: int(concat(ss))"
      --macro="@TWO = nconc(T, W, O)"
      --macro="@FOUR = nconc(F, O, U, R)"
      
      "sq(@TWO) == @FOUR"
      
      --answer="@FOUR"
      
      # T, W, O are chosen from: 2, 3, 5, 7, 22, 23, 25
      --invalid="0|1|4|6|8-21|24,TWO"
      
      # [optional] speeds things up a bit
      # FOUR is a square ...
      "is_square(@FOUR)"
      # ... so R must be the final digits of a square
      --invalid="2-3|7-8|10-15|17-20|22-23,R"
      

      Solution: FOUR = 105625.

      We have:

      TWO = 3:2:5 = 325
      FOUR = 10:5:6:25 = 105625 = 325^2


      And the solution to the TWO × TWO = THREE puzzle is:

      % python3 enigma.py SubstitutedExpression "TWO * TWO = THREE"
      (TWO * TWO = THREE)
      (138 * 138 = 19044) / E=4 H=9 O=8 R=0 T=1 W=3
      [1 solution]
      

      Like

    • GeoffR's avatar

      GeoffR 4:04 pm on 8 February 2024 Permalink | Reply

      from enigma import all_different
      from math import isqrt
      
      def is_sq(x):
         return isqrt(x) ** 2 == x
      
      tup_TWO = (2, 3, 5, 7, 22, 23, 25)
       
      for F in range(1, 26):
        for O in tup_TWO:
          if O == F:continue
          for U in range(26):
            if U in (F, O):continue
            for R in (4, 9, 25): # max value of R = 25
              if R in (U, O, F):continue
              FOUR = int(str(F) + str(O) + str(U) + str(R))
              if not is_sq(FOUR):continue
              for T in tup_TWO:
                for W in tup_TWO:
                  if not all_different(T, W, O, F, U, R):continue
                  TWO = int(str(T) + str(W) + str(O))
                  if TWO * TWO == FOUR:
                    print(f"TWO = {TWO}, FOUR = {FOUR}.")
                    
      # TWO = 325, FOUR = 105625.
      
      

      Like

    • GeoffR's avatar

      GeoffR 8:55 pm on 8 February 2024 Permalink | Reply

      TWO × TWO = THREE is much easier than TWO × TWO = FOUR, as the former has only digits 0..9 to consider.

      from itertools import permutations
      
      for p1 in permutations('1234567890', 3):
         T, W, O = p1
         if T == '0':continue
         TWO = int(T + W + O)
         q1 = set('01234560789').difference([T, W, O])
         for p2 in permutations(q1, 3):
            R, H, E = p2
            THREE = int(T + H + R + E + E)
            if TWO * TWO == THREE:
               print(f"Sum: {TWO} * {TWO} = {THREE}.")
      
      # Sum: 138 * 138 = 19044.
      

      Like

  • Unknown's avatar

    Jim Randell 11:14 pm on 4 February 2024 Permalink | Reply
    Tags:   

    Teaser 2660: Oblonging 

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

    I have made a set of “oblongs”, which is what I call rectangles where the longer sides are one centimetre longer than the shorter sides. I made this set from some A4 sheets of card (without any pasting), cutting out one oblong of each of the sizes 1 cm × 2 cm, 2 cm × 3 cm, 3 cm × 4 cm, and so on up to a particular size. I needed more than one A4 sheet to do this. I have given the set to my family and challenged them to use all the card in jig-saw fashion to make another oblong. After considerable effort they have managed to do this.

    How many oblongs are in the set?

    There are now 1000 Teaser puzzles available on the site.

    [teaser2660]

     
    • Jim Randell's avatar

      Jim Randell 11:15 pm on 4 February 2024 Permalink | Reply

      See also: Enigma 1491.

      An A4 sheet is 21.0 cm × 29.7 cm, so the largest oblong that can be made is 21 × 22.

      And the total area is more than 21 × 29 = 609 sq cm, then we will need multiple A4 sheets to make the oblongs.

      This is sufficient to find a single candidate solution.

      Run: [ @replit ]

      from enigma import (irange, quadratic, printf)
      
      # consider possible oblongs a x (a + 1) and accumulate total area
      t = 0
      for a in irange(1, 21):
        t += a * (a + 1)
        # total area > A4
        if not (t > 609): continue
        # look for an oblong with same area: x(x + 1) = t
        for x in quadratic(1, 1, -t, domain='Z', include='+'):
          printf("1x2 .. {a}x{a1} -> t = {t} -> {x}x{x1}", a1=a + 1, x1=x + 1)
      

      Solution: There are 20 oblongs in the set.

      The oblongs 1×2, 2×3, …, 20×21 have total area of 3080, which is the same as a 55×56 oblong.

      This is the only possible candidate, but it is perhaps more difficult to actually fit the tiles together to make the large oblong.

      However, here is one possible packing:

      Like

  • Unknown's avatar

    Jim Randell 4:40 pm on 2 February 2024 Permalink | Reply
    Tags:   

    Teaser 3202: Long odds 

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

    A group of fewer than twenty of us play a simple gambling game. We have a set of cards labelled 1, 2, 3, … up to a certain number and each player is allocated one of the cards at random. There is a prize for the player with the highest number from those allocated, and a booby prize for the lowest.

    In a recent game I was unfortunately allocated a very middling number (in fact exactly half of the highest possible number). I calculated that my chance of winning the booby prize was 1 in N (where N is a whole number) and that my chance of winning the top prize was even lower at 1 in 2N.

    How many cards are there in the set, and how many players?

    [teaser3202]

     
    • Jim Randell's avatar

      Jim Randell 5:05 pm on 2 February 2024 Permalink | Reply

      This Python program runs in 71ms. (Internal runtime is 3.3ms).

      Run: [ @replit ]

      from enigma import (Rational, irange, multiply, printf)
      
      Q = Rational()
      
      # consider number of players
      for k in irange(2, 19):
      
        # consider number of cards (must be even)
        for n in irange(k + (k % 2), 100, step=2):
      
          # my card is x (= n/2)
          x = n // 2
          if x < k: continue
      
          # chance of winning the booby prize = pB
          # consider each of the (k - 1) other players
          # each of them must have one of the x cards higher than mine
          pB = multiply(Q(x + 1 - i, n - i) for i in irange(1, k - 1))
          if pB.numerator != 1: continue
      
          # chance of winning the top prize = pT
          # consider each of the (k - 1) other players
          # each of them must have one of the (x - 1) cards lower than mine
          pT = multiply(Q(x - i, n - i) for i in irange(1, k - 1))
          if not (2 * pT == pB): continue
      
          # output solution
          printf("{k} players, {n} cards -> x={x} pB={pB} pT={pT}")
      

      Solution: There were 40 cards in the set. And there were 11 players in the game.

      The cards are numbered 1 … 40, so the setter was dealt the 20 card.

      The probability of each of the remaining 10 players receiving a card that is higher than 20 is:

      pB = (20/39) × (19/38) × … × (11/30) = 1/3441

      And the probability of each of the remaining 10 players receiving a card that is lower than 20 is:

      pT = (19/39) × (18/38) × … × (10/30) = 1/6882


      Analytically:

      If my card is x, then there are 2x cards (numbered 1 … 2x).

      And if there are (k + 1) players in total (i.e. k other players), then:

      pB = product[ x/(2x − 1), (x − 1)/(2x − 2), …, (x − k + 1)/(2x − k) ]
      pT = product[ (x − 1)/(2x − 1), (x − 2)/(2x − 2), … (x − k)/(2x − k) ]

      The denominators are the same so:

      numerator(pB) = 2 numerator(pT)

      product[ x, (x − 1), …, (x − k + 1) ] = 2 product[ (x − 1), (x − 2), …, (x − k) ]
      x = 2(x − k)
      x = 2k

      And we can simplify:

      pB = product[ 2k, 2k − 1, …, k + 1 ] / product[ 4k − 1, 4k − 2, …, 3k ]

      so we can consider possible values for k (= 1 .. 18) and look for situations where pB = 1/N.

      The internal runtime of this program is 200µs.

      Run: [ @replit ]

      from enigma import (irange, factorial, fraction, printf)
      
      # consider number of players - 1
      for k in irange(1, 18):
      
        # probability of winning booby prize
        (pBn, pBd) = fraction(factorial(2 * k, k), factorial(4 * k - 1, 3 * k - 1))
        if pBn != 1: continue
      
        # output solution
        (n, k, pTd) = (4 * k, k + 1, 2 * pBd)
        printf("{k} players, {n} cards -> pB=1/{pBd} pT=1/{pTd}")
      

      Like

      • Frits's avatar

        Frits 1:18 pm on 4 February 2024 Permalink | Reply

        @Jim, as x >= k you can also start the “n” loop with 2 * k and remove the continue statement.

        Like

        • Jim Randell's avatar

          Jim Randell 1:50 pm on 4 February 2024 Permalink | Reply

          @Frits: Good point. I’ve got a much shorter program that uses some analysis to do without a loop for n at all. I’ll post it when I put the answer up (or it is on @replit).

          Like

          • Frits's avatar

            Frits 2:36 pm on 4 February 2024 Permalink | Reply

            Yes, I have done the (probably same) analysis to get rid of a loop (the program is on PuzzlingInPython).

            I try to alternate posting between your and Brian’s site.

            Like

  • Unknown's avatar

    Jim Randell 9:16 am on 1 February 2024 Permalink | Reply
    Tags:   

    Teaser 2619: First and last 

    From The Sunday Times, 2nd December 2012 [link] [link]

    A “First and last” number (FLN) is any number that is divisible by its first and last digits. Using each non-zero digit just once, I wrote down a 3-digit FLN followed by three 2-digit FLNs. Putting these in one long line in that order gave me a 9-digit FLN. When the first and last digits were removed from this 9-digit number, I was left with a 7-digit FLN.

    What was the 9-digit number?

    [teaser2619]

     
    • Jim Randell's avatar

      Jim Randell 9:16 am on 1 February 2024 Permalink | Reply

      This run file executes in 83ms. (Internal runtime of the generated program is 202µs).

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      --digits="1-9"
      
      # the following are FLNs:
      #
      #   ABC, DE, FG, HI
      #   ABCDEFGHI
      #   BCDEFGH
      
      # 3-digit FLN
      "ABC % A = 0" "ABC % C = 0"
      
      # 3x 2-digit FLNs
      "DE % D = 0" "DE % E = 0"
      "FG % F = 0" "FG % G = 0"
      "HI % H = 0" "HI % I = 0"
      
      # 9-digit FLN
      "ABCDEFGHI % A = 0" "ABCDEFGHI % I = 0"
      
      # 7-digit FLN
      "BCDEFGH % B = 0" "BCDEFGH % H = 0"
      
      --answer="ABCDEFGHI"
      --template="(ABC DE FG HI)"
      --solution=""
      

      Solution: The 9-digit FLN is: 972364815.

      So we have the following FLNs:

      3-digit: 972
      2-digit: 36, 48, 15
      9-digit: 972364815
      7-digit: 7236481

      Like

    • GeoffR's avatar

      GeoffR 9:49 pm on 1 February 2024 Permalink | Reply

      
      from itertools import permutations
      from functools import reduce
      
      nfd = lambda ns: reduce(lambda x, y: 10 * x + y, ns)
      
      # 3-digit FLN number
      for a, b, c  in permutations(range(1, 10), 3):
          abc = nfd([a, b, c])
          if not(abc % c == 0 and abc % a == 0):continue
         
          # find remaining three 2-digit FLN numbers
          q1 = set(range(1, 10)).difference({a,b,c})
          for p2 in permutations(q1):
              d, e, f, g, h, i = p2
              de, fg, hi = 10*d + e, 10*f + g, 10*h + i
              if not (de % d == 0 and de % e == 0):continue
              if not (fg % f == 0 and fg % g == 0):continue
              if not (hi % h == 0 and hi % i == 0):continue
              
              # check 9-digit and 7-digit FLN numbers
              dig9 = nfd([a, b, c, d, e, f, g, h, i])
              if not (dig9 % a == 0 and dig9 % i == 0):continue
              # remove first and last digits from 9-digit number
              dig7 = nfd([b, c, d, e, f, g, h])
              if dig7 % b == 0 and dig7 % h == 0:
                  print(f"Nine digit number = {dig9}.")
      
      # Nine digit number = 972364815.
      

      Like

  • Unknown's avatar

    Jim Randell 8:40 am on 30 January 2024 Permalink | Reply
    Tags:   

    Brain teaser 1004: Ladder limit 

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

    The outside of the house was almost painted; there remained only the barge board on the gable end to do. This wall of the house has the garage running along it, and immediately adjacent to it. My garage serves as an outhouse as well, so it is well proportioned, being 12 feet high, and having a flat roof 12 feet wide.

    My ladder is 35 feet long. Making sure that the foot of the ladder was firmly established on the ground, I rested the upper end against the wall. The top of the ladder just touched the apex: I had been very lucky, for I realised that it would have been impossible for the ladder to reach the apex had that apex been any higher.

    Later, after removing the ladder, I noticed that there was a small unpainted area where the ladder had rested. To save getting the ladder out again, I decided to touch-up this spot by standing on the garage roof, and using a brush tied to a long cane. In order to see if this were possible, I had to calculate the height of the apex above the garage roof.

    What was that height?

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

    [teaser1004]

     
    • Jim Randell's avatar

      Jim Randell 8:40 am on 30 January 2024 Permalink | Reply

      If the ladder makes an angle θ with the ground (0 < θ < 90°), and the amount of ladder above the garage is x (0 < x < 35), then:

      cos(θ) = 12 / x

      And the amount of ladder below the garage is (35 − x):

      sin(θ) = 12 / (35 − x)

      Using sin² + cos² = 1, we have:

      (12/x)^2 + (12/(35 − x))^2 = 1

      (12^2)((35 − x)^2 + x^2) = x^2(35 − x)^2

      So we need to find roots of the polynomial:

      x^4 − 70 x^3 + 937 x^2 + 10080 x − 176400 = 0

      This can be factorised as:

      (x − 15)(x − 20)(x^2 − 35x – 588) = 0

      And the only roots in the required range are the rational roots x = 15, x = 20.

      The height of the apex above the garage roof is given by:

      h = 12x / (35 − x)

      So:

      x = 15 → h = 9
      x = 20 → h = 16

      And we want the maximum value.

      Solution: The apex is 16 feet above the roof of the garage.


      And we can do a similar thing programatically:

      Run: [ @replit ]

      from enigma import (Polynomial, Accumulator, sq, fdiv, catch, printf)
      
      # (12/(35 - x))^2 + (12/x)^2 = 1
      p1 = sq(Polynomial([35, -1]))  # p1 = (35 - x)^2
      p2 = Polynomial([0, 0, 1])  # p2 = x^2
      
      # calculate the polynomial
      p = p1 * p2 - sq(12) * (p1 + p2)
      printf("[p = {p}]")
      
      # look for real roots of p
      r = Accumulator(fn=max)
      for x in p.find_roots(domain='F'):
        h = catch(fdiv, 12 * x, 35 - x)
        printf("[x={x} -> h={h}]")
        if 0 < x < 35:
          r.accumulate(h)
      
      # answer is the maximum result
      h = r.value
      printf("h = {h:.2f}")
      

      Like

      • Jim Randell's avatar

        Jim Randell 10:45 am on 30 January 2024 Permalink | Reply

        I wonder if this puzzle (set 42 years ago) is set by the same Paul Hughes who recently set Teaser 3191.

        According to The Sunday Times Book of Brainteasers (1994), the Paul Hughes who set Teaser 1004 is:

        Seaman, mountaineer, historian and pilot. This problem occurred while navigating through the Trobriand Islands, but was set differently for publication.

        Like

    • Hugo's avatar

      Hugo 2:08 pm on 30 January 2024 Permalink | Reply

      So the ladder formed the hypotenuse of two triangles with ratio 3:4:5, one below and one above the corner of the garage roof.
      It doesn’t sound a safe angle for a ladder: I hope he secured the foot before climbing it.

      Like

  • Unknown's avatar

    Jim Randell 4:39 pm on 26 January 2024 Permalink | Reply
    Tags:   

    Teaser 3201: Spare routes 

    From The Sunday Times, 27th January 2024 [link] [link]

    Three companies run scenic coach trips in both directions between some pairs of towns in my holiday destination. Each route between two towns is served by just one company, but has one or more alternatives via another town. In particular, every Redstart route could be replaced by a unique combination of two Bluetail routes, every Bluetail by a unique combination of two Greenfinches, and every Greenfinch by a unique combination of a Redstart and a Greenfinch. This wouldn’t be possible with fewer towns or fewer routes.

    I toured one route each day, starting from the town I’d arrived at the previous day but changing the company, never repeating a route in either direction, and involving as many of the routes as I could.

    Which companies did I use, in order (as initials, e.g., R, B, G, B)?

    [teaser3201]

     
    • Jim Randell's avatar

      Jim Randell 8:51 pm on 26 January 2024 Permalink | Reply

      There is probably some (isomorphic) duplication in the minimal graphs found, and this is not an efficient approach for larger graphs (but fortunately the minimal graphs found are quite small).

      Run: [ @replit ]

      from enigma import (Accumulator, irange, inf, subsets, ordered, singleton, join, map2str, printf)
      
      # find routes between x and y via z
      def route(m, x, y, zs, ss):
        for z in zs:
          if z == x or z == y: continue
          if ordered(m.get(ordered(x, z), 'X'), m.get(ordered(y, z), 'X')) == ss:
            yield z
      
      # requirements: colour -> replacements
      reqs = {
        'R': ('B', 'B'),  # R can be replaced by B+B
        'B': ('G', 'G'),  # B can be replaced by G+G
        'G': ('G', 'R'),  # G can be replaced by G+R
      }
      
      # check the requirements on map <m> with nodes <ns>
      def check(m, ns):
        vs = set()
        for ((x, y), v) in m.items():
          if v != 'X': vs.update((x, y))
          ss = reqs.get(v)
          # look for unique replacement
          if ss and singleton(route(m, x, y, ns, ss)) is None: return False
        # check all nodes are non-trivial
        return vs.issuperset(ns)
      
      # find paths on map <m> without repeated edges, and different colours on adjacent edges
      # vs = visited vertices
      # ks = visited edges
      def paths(m, vs=list(), ks=list()):
        if ks and ks[0] < ks[-1]: yield (vs, ks)
        # can we extend the path?
        for (k, v) in m.items():
          if v == 'X': continue
          if ks and (k in ks or v == m[ks[-1]]): continue
          if k[0] == vs[-1]:
            yield from paths(m, vs + [k[1]], ks + [k])
          if k[1] == vs[-1]:
            yield from paths(m, vs + [k[0]], ks + [k])
      
      # find minimal graphs (by (number of nodes, number of edges))
      graphs = Accumulator(fn=min, collect=1)
      
      # consider increasing numbers of towns (at least 4)
      for n in irange(4, inf):
        # vertices (= towns)
        ns = list(irange(n))
        # edges (= routes)
        rs = list(subsets(ns, size=2))
      
        # assign colours to routes ('X' = no route)
        for ss in subsets("RBGX", size=len(rs) - 1, select='M', fn=list):
          # check minimum number of routes
          if ss.count('B') < 2: continue
          if ss.count('G') < 3: continue
          ss.insert(0, 'R')
      
          # make the map
          m = dict(zip(rs, ss))
          # check requirements
          if check(m, ns):
            # record (number of nodes, number of edges)
            graphs.accumulate_data((n, len(ss) - ss.count('X')), m)
      
        if graphs.data: break  # we only need the minimal number of vertices
      
      # collect answers
      ans = set()
      
      # process minimal graphs
      (n, e) = graphs.value
      ns = list(irange(n))
      printf("minimal graph has {n} vertices, {e} edges")
      
      for m in graphs.data:
        printf("-> {m}", m=map2str(m))
      
        # collect maximal paths on this map
        r = Accumulator(fn=max, collect=1)
        for v in ns:
          for (vs, ks) in paths(m, [v]):
            r.accumulate_data(len(ks), (vs, ks))
      
        printf("max path len = {r.value}")
        # output paths
        for (vs, ks) in r.data:
          ss = join(m[k] for k in ks)
          printf("-> {vs} {ss}")
          ans.add(ss)
        printf()
      
      # output solution
      printf("tour = {t}", t=join(ans, sep=", "))
      

      Solution: The companies used are: G, B, R, B, R, B, G.

      A minimal graph has 5 vertices and 9 edges:

      The program finds 12 graphs in total, but they are all isomorphic to the one above.

      We see that node 4 only has green edges (and all green edges lead to 4), so that can only act as the start/end of the path, and we can use a maximum of 7 of the 9 edges. Each path can be traversed in both directions, so there are essentially 3 different maximal paths that can be taken. And the fact that puzzle should have a unique solutions implies the answer should be palindromic (otherwise the reverse would also be a valid answer), even though the example given in the puzzle text is not.

      Liked by 1 person

      • Jim Randell's avatar

        Jim Randell 10:15 am on 27 January 2024 Permalink | Reply

        I augmented my code to detect isomorphic graphs [@replit], and there is essentially only one viable minimal layout.

        from enigma import (Accumulator, irange, inf, subsets, ordered, singleton, join, map2str, printf)
        
        # find routes between x and y via z
        def route(m, x, y, zs, ss):
          for z in zs:
            if z == x or z == y: continue
            if ordered(m.get(ordered(x, z), 'X'), m.get(ordered(y, z), 'X')) == ss:
              yield z
        
        # requirements: colour -> replacements
        reqs = {
          'R': ('B', 'B'),  # R can be replaced by B+B
          'B': ('G', 'G'),  # B can be replaced by G+G
          'G': ('G', 'R'),  # G can be replaced by G+R
        }
        
        # check the requirements on map <m> with nodes <ns>
        def check(m, ns):
          vs = set()
          for ((x, y), v) in m.items():
            if v != 'X': vs.update((x, y))
            ss = reqs.get(v)
            # look for unique replacement
            if ss and singleton(route(m, x, y, ns, ss)) is None: return False
          # check all nodes are non-trivial
          return vs.issuperset(ns)
        
        # find paths on map <m> without repeated edges, and different colours on adjacent edges
        # vs = visited vertices
        # ks = visited edges
        def paths(m, vs=list(), ks=list()):
          if ks and ks[0] < ks[-1]: yield (vs, ks)
          # can we extend the path?
          for (k, v) in m.items():
            if v == 'X': continue
            if ks and (k in ks or v == m[ks[-1]]): continue
            if k[0] == vs[-1]:
              yield from paths(m, vs + [k[1]], ks + [k])
            if k[1] == vs[-1]:
              yield from paths(m, vs + [k[0]], ks + [k])
        
        # check 2 graphs for isomorphism
        def is_isomorphic(vs, m1, m2):
          # choose a mapping of vs
          for ss in subsets(vs, size=len, select='P'):
            # remap m1
            m3 = dict((ordered(ss[x], ss[y]), v) for ((x, y), v) in m1.items())
            if m3 == m2: return True
          return False
        
        # find minimal graphs
        graphs = Accumulator(fn=min, collect=1)
        
        # consider increasing numbers of towns (at least 4)
        for n in irange(4, inf):
          # vertices (= towns)
          ns = list(irange(n))
          # edges (= routes)
          rs = list(subsets(ns, size=2))
        
          # assign colours to routes ('X' = no route)
          for ss in subsets("RBGX", size=len(rs) - 1, select='M', fn=list):
            # check minimum number of routes
            (nR, nB, nG) = (ss.count('R') + 1, ss.count('B'), ss.count('G'))
            if nB < 2 or nG < 3 or nB < nR or nG < nB: continue
            ss.insert(0, 'R')
        
            # make the map
            m = dict(zip(rs, ss))
            # check requirements
            if check(m, ns):
              # record (number of nodes, number of edges)
              graphs.accumulate_data((n, len(ss) - ss.count('X')), m)
        
          if graphs.data: break  # we only need the minimal number of vertices
        
        # collect answers
        ans = set()
        morphs = list()
        
        # process minimal graphs
        (n, e) = graphs.value
        ns = list(irange(n))
        printf("minimal graph has {n} vertices, {e} edges")
        
        for m in graphs.data:
          printf("-> {m}", m=map2str(m))
        
          # check morphs
          if any(is_isomorphic(ns, m, m1) for (j, m1) in enumerate(morphs)): continue
          printf("= isomorph {n}", n=len(morphs))
          morphs.append(m)
        
          # collect maximal paths on this map
          r = Accumulator(fn=max, collect=1)
          for v in ns:
            for (vs, ks) in paths(m, [v]):
              r.accumulate_data(len(ks), (vs, ks))
        
          printf("max path len = {r.value}")
          # output paths
          for (vs, ks) in r.data:
            ss = join(m[k] for k in ks)
            printf("-> {vs} {ss}")
            ans.add(ss)
          printf()
        
        # output solution
        printf("tour = {t}", t=join(ans, sep=", "))
        

        Like

    • Frits's avatar

      Frits 7:42 am on 27 January 2024 Permalink | Reply

      Similar, the tour also finishes where it started.
      The generated routes and/or tours may contain duplicates.

        
      from itertools import product
      
      # is route <k> doable by a unique combination via two routes of types <tps> 
      def check_alt(m, n, k, tps):
        rem_towns = [i for i in range(n) if i not in k]
        alt = [a for a in rem_towns 
               if {m[tuple(sorted([a, x]))] for x in k} == tps]
        return len(alt) == 1
      
      def check(m, n):
        d = dict(zip(["R", "B", "G"], [{"B"}, {"G"}, {"R", "G"}]))
       
        # check for unique alternative combinations
        for k, v in m.items():
          if v in "RBG":
            if not check_alt(m, n, k, d[v]): return False
        return True    
              
      # generate routes that meet the requirements
      def gen_routes(n):
        # routes
        rs = [(i, j) for i in range(n - 1) for j in range(i + 1, n)]
      
        # assign company to a route (or not), (blank = no route)
        for cs in product("RBG ", repeat = n * (n - 1) // 2 - 1):
          cs = ("R", ) + cs
          # R < B < G
          if (cntR := cs.count('R')) >= (cntB := cs.count('B')): continue
          if cntB >= (cntR := cs.count('G')): continue
          
          # check requirements
          if check(d := dict(zip(rs, cs)), n):
            yield d
      
      # add route to tour
      def add_route(m, ss=[]):
        if not ss: # start
          for k, v in m.items():
            yield from add_route(m, ss + [(k, v)])
        else:
          yield ss
          # find a new unused route for a different company from the last
          rt, tp = ss[-1]
          for k, v in m.items():
            if v == tp: continue 
            # already added?
            if (k, v) in ss or (k[::-1], v) in ss: continue
            if k[0] == rt[1]:
              yield from add_route(m, ss + [(k, v)]) 
            if k[1] == rt[1]:
              yield from add_route(m, ss + [(k[::-1], v)])    
      
      n = 4 # we need at least 6 routes (1 R, 2 B, 3 G)
      # increase number of towns until all alternative routes can be made
      while True:
        sols = set()
        mx = 0
        
        # generate valid routes
        for r in gen_routes(n):
          # find longest tour
          mx = 0
          for tour in add_route({k: v for k, v in r.items() if v in "RGB"}):
            lt = len(tour)
            if lt >= mx:
              if lt > mx:
                sols = set() 
                mx = lt
              # finish where we have started (is this a feature of a tour?)    
              if tour[0][0][0] != tour[-1][0][1]: continue    
              sols.add(''.join(t for _, t in tour))
            
        if mx:
          print(f"answer: {' or '.join(sols)}") 
          break 
        else:
          n += 1
      

      Like

      • Jim Randell's avatar

        Jim Randell 11:35 am on 31 January 2024 Permalink | Reply

        @Frits: I don’t think it is required for the tour to start and finish at the same town. (Certainly this is not explicitly stated).

        Also, how does your program ensure that the condition “this wouldn’t be possible with … fewer routes” is met?

        Like

    • Frits's avatar

      Frits 3:55 am on 1 February 2024 Permalink | Reply

      Without demanding for cyclic tours and with minimal routes.
      Program is also running a little bit faster (due to the extra “cntR” condition).

       
      from itertools import product
      
      # is route <k> feasible by a unique combination via two routes of types <tps> 
      def check_alt(m, n, k, tps):
        alt = [a for a in [i for i in range(n) if i not in k]
               if {m[(a, x) if a < x else (x, a)] for x in k} == tps]
        return len(alt) == 1
      
      # perform checks for all routes
      def check(m, n):
        d = dict(zip(["R", "B", "G"], [{"B", "B"}, {"G", "G"}, {"R", "G"}]))
       
        # check for unique alternative combinations
        for r, c in m.items():
          if c in "RBG":
            if not check_alt(m, n, r, d[c]): return False
        return True    
              
      # generate routes that meet the requirements
      def gen_routes(n):
        # routes
        rs = [(i, j) for i in range(n - 1) for j in range(i + 1, n)]
      
        # assign company to a route (or not), (blank = no route)
        for cs in product("RBG ", repeat = n * (n - 1) // 2 - 1):
          cs = ("R", ) + cs
          # nR < nB < nG
          # 3 * r + 3 <= n * (n - 1) // 2
          if not ((cntR := cs.count('R')) <= (n * (n - 1) - 6) // 6): continue
          
          if not (cntR < cs.count('B') < cs.count('G')): continue
          # check requirements
          if check(d := dict(zip(rs, cs)), n):
            yield d
      
      # generate all valid tours (credit: John Z)
      def tours(m, prevt, prevc="x", rts = []):
        
        # consider next town to visit
        for nt in set(range(n)) - {prevt}:
          
          route = (prevt, nt) if prevt < nt else (nt, prevt) 
          if route not in rts and m[route] not in {" ", prevc}:
            yield from tours(m, nt, m[route], rts + [route])
      
        # any route is linked to 2 other routes
        if len(rts) > 2:
         yield ''.join(m[x] for x in rts)
      
      n = 4 # we need at least 6 routes (1 R, 2 B, 3 G)
      # increase number of towns until all alternative routes can be made
      while True:
        mrts = dict()  
        # generate valid routes and calculate number of blank routes
        for r in gen_routes(n):
          mrts[brts] = mrts.get(brts := list(r.values()).count(" "), []) + [r]
          
        if mrts:
          trs = set()
          # get minimimal routes by maximising the number of blank routes
          for r in mrts[max(mrts.keys())]:
            # find all valid tours
            trs |= set(tr for twn in range(n) for tr in tours(r, twn))
      
          print("answer:", ' or '.join([tr for tr in trs 
                                        if len(tr) == len(max(trs, key=len))]))
          break 
        else:
          n += 1   
      

      Like

  • Unknown's avatar

    Jim Randell 11:11 am on 25 January 2024 Permalink | Reply
    Tags:   

    Teaser 2620: Stating the obvious 

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

    I have replaced the letters of the alphabet by the numbers 0 to 25 in some order, using different numbers for different letters. So, for example, a three-letter word could represent a number of three, four, five or six digits. With my particular values:

    ONE + ONE = TWO, and
    ONE is a perfect square.

    What number does TWO represent?

    [teaser2620]

     
    • Jim Randell's avatar

      Jim Randell 11:13 am on 25 January 2024 Permalink | Reply

      The value of a word is formed by concatenating the values (in base 10) of the digits, and then reading the result as a number.

      So, for example, if O = 10, N = 6, E = 25, then the value of ONE is 10625 (= 10:6:25).

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

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      --base=26
      --code="word = lambda *vs: int(concat(vs))"
      --macro="@ONE = word(O, N, E)"
      --macro="@TWO = word(T, W, O)"
      --invalid="0,OT"
      
      # ONE is a perfect square
      "is_square(@ONE)"
      
      # ONE + ONE = TWO
      "2 * @ONE == @TWO"
      
      --answer="@TWO"
      

      Solution: TWO = 4232.

      There are two assignments that achieve this:

      E=6 N=11 O=2 T=4 W=23 → ONE=2116 TWO=4232
      E=16 N=1 O=2 T=4 W=23 → ONE=2116 TWO=4232

      And if we allow leading zeros (i.e. O or T is 0), we can also have:

      E=25 N=2 O=0 T=4 W=5 → ONE=225 TWO=450
      E=25 N=6 O=0 T=12 W=5 → ONE=625 TWO=1250
      E=25 N=12 O=0 T=24 W=5 → ONE=1225 TWO=2450

      So perhaps the puzzle would have been better if the values used were 1 to 26.

      Like

    • GeoffR's avatar

      GeoffR 3:00 pm on 25 January 2024 Permalink | Reply

      from math import isqrt
      def is_sq(x):
         return isqrt(x) ** 2 == x
      
      for O in range(1, 27):
          for N in range(26):
              if N == O:
                  continue
              for E in range(26):
                  if E in (O, N):
                      continue
                  #1. ONE is a perfect square.
                  ONE = int(str(O) + str(N) + str(E))
                  if is_sq(ONE):
                      for T in range(1, 27):
                          if T in (O, N, E):
                              continue
                          for W in range(26):
                              if W in (T, O, N, E):
                                  continue      
                              #2. ONE + ONE = TWO
                              TWO = int(str(T) + str(W) + str(O))
                              if ONE + ONE == TWO:
                                  print(f"ONE = {ONE} and TWO = {TWO}")
                                  print(f"O={O}, N={N}, E={E}, T={T}, W={W}")
                                  print()
                                                    
      # ONE = 2116 and TWO = 4232
      # O=2, N=1, E=16, T=4, W=23
      
      # ONE = 2116 and TWO = 4232
      # O=2, N=11, E=6, T=4, W=23
      
      

      Like

    • Frits's avatar

      Frits 4:50 am on 26 January 2024 Permalink | Reply

          
      from itertools import permutations
      from enigma import is_square
      
      sols = set()
      # O has to be even as 2 * ONE = TWO  
      for O in range(2, 26, 2):
        lnO = 1 + (O > 9)
        for N, E in permutations([n for n in range(26) if n != O], 2):
          if not is_square(ONE := int(str(O) + str(N) + str(E))): continue
          
          # parse TWO into TW and O_
          (sTW, sO_) = ((sTWO := str(ONE + ONE))[:-lnO], sTWO[-lnO:])
          if sO_ != str(O): continue
          
          # parse TW into T and W
          for t in range(1 + (len(sTW) == 4), 2 + (len(sTW) > 2)):
            (T, W) = (int(sTW[:t]), int(sTW[t:]))
            # different numbers
            if T == W or any(n in {O, N, E} or n > 25 for n in [T, W]): continue
            sols.add(sTWO)
      
      print(f"answer: {' or '.join(sols)}")      
      

      Like

  • Unknown's avatar

    Jim Randell 1:33 pm on 23 January 2024 Permalink | Reply
    Tags:   

    Teaser 2669: Extending the garden 

    From The Sunday Times, 17th November 2013 [link] [link]

    George and Martha used to have a square garden with sides of length 10 metres, but they have extended it by adding an acute-angled triangle on each side of the square. The result is that the new garden has eight straight sides, each of which is fenced. The fences are different whole number of metres long, with the shortest being one metre and the longest 13 metres. George remarked that the average length of the fences was also a whole number of metres.

    In increasing order, what were the lengths of the eight fences?

    [teaser2669]

     
    • Jim Randell's avatar

      Jim Randell 1:34 pm on 23 January 2024 Permalink | Reply

      If we consider the side of the 10 metre square to be the base of a triangle, then the vertex of the triangle formed by the new fences must lie above the interior of the base, and outside a semicircle whose diameter is the base.

      This Python program finds possible side configurations (for a shorter and longer site, chosen from 1..13), and then combines 4 of these configurations to find viable sets of triangles.

      It runs in 59ms. (Internal runtime is 3.5ms).

      Run: [ @replit ]

      from enigma import (irange, fdiv, sq, disjoint_union, printf)
      
      # generate possible (a, b) extensions
      def sides():
        # consider possible sides (from 1 - 13) to make an acute angled triangle
        # the shorter side
        for a in irange(1, 12):
          # the longer side
          for b in irange(max(a + 1, 11 - a), 13):
            # determine vertex points
            x = fdiv(sq(b) - sq(a), 20)
            # vertex must be above base
            if not (x < 5): continue
            x2 = sq(x)
            y2 = sq(b) - sq(x + 5)
            # vertex must lie outside a radius 5 semicircle
            if not (x2 + y2 > 25): continue
            # this is a viable configuration
            yield (a, b)
      
      # generate solutions
      def solve(sides, k, ts=list(), ss=set()):
        # are we done?
        if k == 0:
          # mean is an integer
          if sum(ss) % len(ss) != 0: return
          # smallest side is 1, largest is 13
          ss = sorted(ss)
          if not (ss[0] == 1 and ss[-1] == 13): return
          # viable solution
          yield (ts, ss)
        else:
          # add in another triangle
          for (i, t) in enumerate(sides):
            # all sides are different
            ss_ = disjoint_union([ss, t])
            if ss_:
              yield from solve(sides[i:], k - 1, ts + [t], ss_)
      
      # find solutions
      rs = set()
      for (ts, ss) in solve(list(sides()), 4):
        printf("{ts} -> {ss}")
        rs.add(tuple(ss))
      
      # output solutions
      for ss in rs:
        printf("sides = {ss}")
      

      Solution: The lengths of the fencing are (in metres): 1, 5, 7, 8, 9, 10, 11, 13.

      There are 2 configurations that use this set of fences:

      (1, 10) (5, 9) (7, 8) (11, 13)
      (1, 10) (5, 11) (7, 8) (9, 13)

      Here are examples of these configurations:

      I did consider adding code to ensure the fences could be arranged such that the two fences meeting at the corner were not co-linear, but from the example diagrams it is clear that this can be done in both cases.

      Like

  • Unknown's avatar

    Jim Randell 10:25 am on 21 January 2024 Permalink | Reply
    Tags: by: Chris Maslanka   

    Brainteaser 1389: A redistribution of wealth 

    From The Sunday Times, 23rd April 1989 [link]

    Etherdred the Every-ready had been unwise enough to promise to distribute among his four unworthy sons the contents of an old oak coffer which had subsequently turned out to contain the over-magnanimous sum of 405,405,135,015 talents and nothing else. As his own abacus had only eight significant but venerable beads, he summoned his astrologer, Easirede the Farsighted, for advice.

    “I feel that once my fee is determined, the rest of the problem will fall into place. Let us suppose His Majesty’s generosity extends to granting me X talents, where X is a whole number. I see that His Majesty has already divided all of the money into four unequal heaps, one for each son. Now, adding undoes subtraction. So let us take X talents from Aardman’s heap and put X on to Beergutt’s heap. Also, multiplying undoes division, so let us divide Ceedigrin’s heap by X and mutliply Dampfish’s by X. Each son will then have the same amount. After X talents has been paid to me from the remainder His Majesty can keep the rest”.

    The redistribution was made as the astrologer suggested and he left the castle only to be robbed of his X talents by a disgruntled Aardman a mile down the road.

    How many talents were received by each son under the new distribution?

    [teaser1389]

     
    • Jim Randell's avatar

      Jim Randell 10:26 am on 21 January 2024 Permalink | Reply

      If we start with T talents, and in the end distribute N to each of the 4 sons, and X to the astrologer, then:

      4N + X ≤ T

      And the initial piles were:

      A = N + X
      B = N − X
      C = NX
      D = N/X

      And these are all different positive integers, which sum to T.

      (N + X) + (N − X) + NX + N/X = T

      N = TX / (X + 1)^2

      Hence:

      D = N/X = T / (X + 1)^2

      So we can determine values for X by looking at squares that are divisors of T.

      Run: [ @replit ]

      from enigma import (divisors, div, printf)
      
      T = 405405135015
      
      # consider divisors of T
      for X in divisors(T):
        if X < 2: continue
      
        # is the square of X also a divisor?
        X2 = X * X
        if X2 > T: break
        d = div(T, X2)
        if d is None: continue
        X -= 1
      
        # calculate N
        N = X * d
      
        # and the initial piles
        ps = (N + X, N - X, N * X, div(N, X))
        if any(p is None or p < 1 for p in ps) or len(set(ps)) != 4: continue
        assert sum(ps) == T
      
        # output solution
        printf("X={X} -> N={N} ps={ps}")
      

      Solution: Each son received 135045000 talents.

      So each son receives 0.033% of the total.

      And the astrologer receives a modest 3000 talents, which is 0.00000074% of the total.

      And so Etherdred keeps 99.87% of the total.

      Although A mugged the astrologer, C has lost much more by his scheme.


      If we factorise T we get:

      T = 3 × 5 × 3001^3

      So we see that X = 3000 is the only viable candidate.

      Like

  • Unknown's avatar

    Jim Randell 4:31 pm on 19 January 2024 Permalink | Reply
    Tags:   

    Teaser 3200: Puzzling sum 

    From The Sunday Times, 21st January 2024 [link] [link]

    Liam was given a set of addition sums as part of his homework. The teacher had cleverly chosen sums where the answer, together with the two numbers to be added, used all the digits from 1 to 9 just once (and there were no zeros). For instance, one of the sums was 193 + 275 = 468. I noticed that one of them was particularly interesting in that the two numbers to be added were perfect powers (squares, cubes etc).

    In the interesting sum, what are the two numbers that were to be added?

    [teaser3200]

     
    • Jim Randell's avatar

      Jim Randell 4:48 pm on 19 January 2024 Permalink | Reply

      This Python program uses the [[ SubstitutedExpression() ]] solver from the enigma.py library to consider all possible sums that the teacher could have set, and then looks for those with summands that are perfect powers.

      It runs in 87ms.

      Run: [ @replit ]

      from enigma import (
        SubstitutedExpression, decompose, irange, prime_factor,
        mgcd, unpack, sprintf as f
      )
      
      # symbols for the 9 different digits
      syms = "ABCDEFGHI"
      
      # check a number is a perfect power (> 1)
      def is_ipower(n, gcd=unpack(mgcd)):
        if n == 1: return True
        return gcd(e for (p, e) in prime_factor(n)) > 1
      
      # split the symbols into 2 addends and a result (x + y = z)
      for (a, b, c) in decompose(len(syms), 3, increasing=1, sep=0, min_v=1, max_v=4):
        # create the sum
        (x, y, z) = (syms[:a], syms[a:a + b], syms[a + b:])
        # create an alphametic puzzle
        exprs = [ f("{x} + {y} = {z}") ]
        if len(x) == len(y): exprs.append(f("{x0} < {y0}", x0=x[0], y0=y[0]))
        p = SubstitutedExpression(
          exprs,
          digits=irange(1, 9),
          answer=f("({x}, {y}, {z})"),
          verbose='',
        )
        # and solve it
        for (x, y, z) in p.answers():
          if is_ipower(x) and is_ipower(y):
            # output solution
            print(f("{x} + {y} = {z}"))
      

      Solution: The interesting sum is: 243 + 576 = 819.

      And:

      243 = 3^5
      576 = 24^2

      There are 168 possible sums using the digits 1-9, but only this one has summands that are perfect powers. And all of them are of the form: ABC + DEF = GHI.

      Like

      • Jim Randell's avatar

        Jim Randell 8:10 pm on 19 January 2024 Permalink | Reply

        An alternative approach is just to look for two powers that give a sum with the required properties. (The code to generate powers is borrowed from Teaser 3119).

        This Python program has an internal runtime of 1.2ms.

        Run: [ @replit ]

        from enigma import (Primes, nsplit, printf)
        
        # generate powers (x^y) in numerical order, x >= 0, y >= 2,
        def ipowers():
          # powers less than 2^2
          yield 0
          yield 1
          # powers from 2^2 upwards
          base = { 2: 2 }
          power = { 2: 4 }
          maxp = 2
          primes = Primes(35, expandable=1).generate(maxp + 1)
          while True:
            # find the next power
            n = min(power.values())
            yield n
            # what powers are involved
            ps = list(p for (p, v) in power.items() if v == n)
            # increase the powers
            for p in ps:
              base[p] += 1
              power[p] = pow(base[p], p)
            # do we need to add in a new power?
            if maxp in ps:
              maxp = next(primes)
              base[maxp] = 2
              power[maxp] = pow(2, maxp)
        
        # check for valid digits, must be all different and not include 0
        valid = lambda ds: 0 not in ds and len(set(ds)) == len(ds)
        
        # collect powers
        ps = list()
        for p in ipowers():
          ds = nsplit(p)
          if len(ds) > 4: break
          if not valid(ds): continue
        
          # look for a smaller power to pair with this one
          for (p1, ds1) in ps:
            t = p1 + p
            dst = nsplit(t)
            # check all 9 digits used
            ds9 = ds + ds1 + dst
            n = len(ds9)
            if n < 9: continue
            if n > 9: break
            if not valid(ds9): continue
            # output solution
            printf("{p1} + {p} = {t}")
        
          # record this power
          ps.append((p, ds))
        

        I will add the [[ ipowers() ]] function to the enigma.py library (from version 2024-01-19).

        Like

        • Frits's avatar

          Frits 1:53 am on 20 January 2024 Permalink | Reply

          @Jim, did you forget to check dst for zeroes?

          Like

        • Brian Gladman's avatar

          Brian Gladman 6:53 pm on 20 January 2024 Permalink | Reply

          @Jim. That is a very neat subroutine for generating integer powers in order.

          Like

        • Brian Gladman's avatar

          Brian Gladman 9:21 pm on 21 January 2024 Permalink | Reply

          @Jim, I looked at alternatives to your ipowers() routine and found this quite a bit faster:

          from heapq import heappush, heappop
          
          def ipowers(maths=True):
            if maths:
              yield 0
              yield 1
            heap, pv, m = [], None, 2
            heappush(heap, (2 ** 2, 2, 2))
            while True:
              m += 1
              v = 2 ** m
              while heap[0][0] <= v:
                (v1, n1, m1) = heappop(heap)
                if v1 != v and v1 != pv:
                  yield v1
                  pv = v1
                heappush(heap, ((n1 + 1) ** m1, n1 + 1, m1))
              heappush(heap, (2 ** m, 2, m))
          

          Like

          • Jim Randell's avatar

            Jim Randell 10:37 am on 22 January 2024 Permalink | Reply

            @Brian: Yes, using a heap is faster (especially in CPython which I think has heaps implemented via a C module).

            So, this is even faster:

            from heapq import (heapify, heappush, heappop)
            
            def ipowers():
              # powers less than 4
              yield 0
              yield 1
            
              # powers from 4 upwards
              hi = 1
              maxe = 2
              pows = [(4, 2, 2)]
              heapify(pows)
              exps = Primes(35, expandable=1).generate(3)
              while True:
                # find the next power
                (p, b, e) = heappop(pows)
                if p > hi:
                  yield p
                  hi = p
                heappush(pows, (pow(b + 1, e), b + 1, e))
                # do we need to add in a new exponent?
                if b == 2:
                  maxe = next(exps)
                  heappush(pows, (pow(2, maxe), 2, maxe))
            

            Liked by 1 person

            • Brian Gladman's avatar

              Brian Gladman 9:02 am on 23 January 2024 Permalink | Reply

              It is faster if you don’t count the cost of the extra import of Primes() which dwarfs the running cost for low power limits. Including import cost for powers below 1000 I measured 338 microseconds and 2.5 milliseconds on CPython. In my test, it overtakes the non-import version at a power limit of about 10^9.

              Like

            • Jim Randell's avatar

              Jim Randell 1:47 pm on 23 January 2024 Permalink | Reply

              I was more interested in algorithmic efficiency, so I was testing by generating the first 5 million perfect powers, and using primes for exponents was a clear winner on all the Python environments I tested.

              I generally have the enigma module loaded, so there is essentially no overhead in using the primes generator, but the candidate exponents can be any superset of the primes (as the algorithm will discard duplicates), so you can use something like [[ irange(3, inf, step=2) ]] if you don’t want to use primes, and still get a performance improvement.

              Like

    • GeoffR's avatar

      GeoffR 6:55 pm on 19 January 2024 Permalink | Reply

      from enigma import nsplit
      
      # A manual search for all three digit powers gave the following list
      d3_powers = [125, 128, 216, 243, 256, 512, 529, 576, 625, 729, 784, 961]
      
      for r in range(123, 987):  # result of the sum
        g, h, i = nsplit(r)
        if len(set((g, h, i))) != 3:continue
        if r in d3_powers:continue
        
        # find the two summands, which must both be powers
        for n in d3_powers:
          for m in d3_powers:
            if n == m:continue
            a, b, c = nsplit(n)
            d, e, f = nsplit(m)
            if len(set((a, b, c, d, e, f))) == 6:
              if m + n == r:
                if m > n and len(set((a,b,c,d,e,f,g,h,i))) == 9:
                  print(f"The sum is {m} + {n} = {r}.")
      
      

      Like

    • GeoffR's avatar

      GeoffR 8:27 pm on 19 January 2024 Permalink | Reply

      Seems faster to use the remaining digits, after the two squares, for the addition result.

      
      from enigma import nsplit
      
      # A manual search for all three digit powers gave the following list
      d3_powers = [125, 128, 216, 243, 256, 512, 529, 576, 625, 729, 784, 961]
      
      # find the two summands, which must both be powers
      for n in d3_powers: 
          for m in d3_powers:
            if n == m:continue
            a, b, c = nsplit(n)
            d, e, f = nsplit(m)
            if len(set((a, b, c, d, e, f))) == 6:
              
              # find result of additon from remaining digits
              g, h, i = set(range(1,10)).difference((set((a, b, c, d, e, f))))
              if len(set((g, h, i))) != 3:continue
              r = 100*g + 10*h + i
              if r in d3_powers:continue
              if m + n == r:
                if m > n and len(set((a, b, c, d, e, f, g, h, i))) == 9:
                  print(f"The sum is {m} + {n} = {r}.")
      

      Like

    • GeoffR's avatar

      GeoffR 2:50 pm on 22 January 2024 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..9:A; var 1..9:B; var 1..9:C;
      var 1..9:D; var 1..9:E; var 1..9:F;
      var 1..9:G; var 1..9:H; var 1..9:I;
      
      var 100..999:ABC == 100*A + 10*B + C;
      var 100..999:DEF == 100*D + 10*E + F;
      var 100..999:GHI == 100*G + 10*H + I;
      
      constraint all_different ([A,B,C,D,E,F,G,H,I]);
      
      constraint ABC + DEF == GHI;
      
      set of int: powers == {125,128,216,243,256,512,529,576,625,729,784,961};  
      
      constraint ABC > DEF /\ ABC in powers /\ DEF in powers;
      
      solve satisfy;
      output ["Sum is " ++ show(ABC) ++ " + " ++ show(DEF) ++ " = " ++ show(GHI)];
      
      

      Like

  • Unknown's avatar

    Jim Randell 3:09 pm on 15 January 2024 Permalink | Reply
    Tags:   

    Teaser 2666: Multiple calls 

    From The Sunday Times, 27th October 2013 [link] [link]

    In my office each of the 100 employees has a different two-digit phone number, from 00 to 99. Recently my phone was rewired so that each number button generated an incorrect digit. Trying to phone four of my colleagues resulted in me calling double the intended number, and, for more than ten of my colleagues, trying to phone their number resulted in me calling triple the intended number. Also if I tried to phone any colleague and then asked for their phone number, then phoned that number and asked that person for their number, then phoned that number … and so on, it always took ten calls to contact the person I intended.

    If I tried to phone the numbers 01, 23, 45, 67 and 89 respectively, which numbers would I actually get?

    [teaser2666]

     
    • Jim Randell's avatar

      Jim Randell 3:09 pm on 15 January 2024 Permalink | Reply

      Numbers that map to their double must be in the range 01 – 49, and numbers that map to their triple in the range 01 – 33, and we need more than 10 of them.

      If start with any number we always get a chain of 10 numbers before we reach the intended number. So the reassignment of digits must form a complete (length 10) cycle.

      We could generate all possible complete cycles and look for any that meet the remaining conditions, but this is a slow approach (although quite short to program).

      This Python program considers possible mappings that give 11 or more numbers that map to their triple, and then attempts to fill out the remaining values such that a complete cycle is formed.

      It runs in 73ms. (Internal runtime is 9.9ms).

      from enigma import (irange, diff, subsets, peek, map2str, printf)
      
      digits = list(irange(0, 9))
      
      # check a mapping is a complete cycle
      def is_cycle(m):
        if not m: return
        k = peek(m.keys())
        (v, n) = (m[k], 1)
        while v != k:
          v = m[v]
          n += 1
        return n == len(m.keys())
      
      # update a mapping
      def update(m, ks, vs):
        m = m.copy()
        for (k, v) in zip(ks, vs):
          # must be a derangement
          if k == v: return
          # existing key
          if k in m:
            if m[k] != v: return
          else:
            # new key
            if v in m.values(): return
            # make the update
            m[k] = v
        return m
      
      # construct mappings with more than 10 triples
      def solve(k=0, m=dict(), ts=set()):
        # are we done?
        if k > 33:
          if len(ts) > 10:
            yield m
        else:
          # consider mapping k -> 3k
          m_ = update(m, divmod(k, 10), divmod(3 * k, 10))
          if m_:
            yield from solve(k + 1, m_, ts.union({k}))
          # or not
          if m_ != m:
            yield from solve(k + 1, m, ts)
      
      # look for potential mappings
      for r in solve():
        # map remaining keys to remaining values
        ks = diff(digits, r.keys())
        vs = diff(digits, r.values())
        for ss in subsets(vs, size=len, select='P'):
          m = update(r, ks, ss)
          # the map must form a complete cycle
          if not is_cycle(m): continue
          # find doubles and triples
          (ds, ts) = (list(), list())
          for k in irange(0, 49):
            (a, b) = divmod(k, 10)
            v = 10 * m[a] + m[b]
            if v == 2 * k: ds.append(k)
            if v == 3 * k: ts.append(k)
          # we need exactly 4 doubles and more than 10 triples
          if not (len(ds) == 4 and len(ts) > 10): continue
          # output solution
          printf("{m}", m=map2str(m, arr="->", enc=""))
          printf("doubles = {ds}")
          printf("triples = {ts}")
          printf()
      

      Solution: 01 → 13; 23 → 69; 45 → 20; 67 → 84; 89 → 57.

      So the 4 numbers that map to their doubles are:

      05 → 10
      07 → 14
      15 → 30
      17 → 34

      and the 11 numbers that map to their triples are:

      04 → 12
      06 → 18
      11 → 33
      12 → 36
      13 → 39
      21 → 63
      22 → 66
      23 → 69
      31 → 93
      32 → 96
      33 → 99

      Like

    • Frits's avatar

      Frits 2:34 pm on 19 January 2024 Permalink | Reply

      Nice solution.

      I also tried the same setup starting with mappings of exactly 4 doubles but that was a lot slower.
      I can’t find the “Run” button anymore when using the replit link.

      Like

      • Jim Randell's avatar

        Jim Randell 5:38 pm on 19 January 2024 Permalink | Reply

        It looks like replit have changed their interface so you can no longer directly run someone else’s code. Now you need to fork it to your own account before you can run it.

        It seems like this means you can no longer use replit to share code as easily as before, which is a bit annoying.

        Like

  • Unknown's avatar

    Jim Randell 4:54 pm on 12 January 2024 Permalink | Reply
    Tags:   

    Teaser 3199: County cup 

    From The Sunday Times, 14th January 2024 [link] [link]

    In our county football competition, fewer than 100 teams compete in two stages. First, the teams are allocated to more than two equally-sized groups, and in each group there is one match between each pair of teams. The top two teams in each group proceed to the first round of the knockout stage, where a single match between two teams eliminates one of them. If the number of teams entering the knockout stage is not a power of 2, sufficiently many teams are given byes (they don’t have to play in the first round), so that the number of teams in the second round is a power of 2. The knockout stage continues until only one team remains. In one year the competition was played with a single match on every day of the year.

    How many teams were in the competition that year?

    [teaser3199]

     
    • Jim Randell's avatar

      Jim Randell 5:40 pm on 12 January 2024 Permalink | Reply

      (See also: Teaser 2965, Enigma 1067, Enigma 1169, Enigma 1276, Enigma 176, Enigma 1398).

      This Python program runs in 57ms. (Internal runtime is 229µs).

      Run: [ @replit ]

      from enigma import (irange, C, printf)
      
      # consider number of groups in stage 1
      for k in irange(3, 33):
        # consider number of teams per group
        for g in irange(3, 99 // k):
          # number of matches in stage 1 (in each group each pair plays)
          m1 = k * C(g, 2)
          # stage 2: the top 2 teams from each group progress to knockout
          q = 2 * k
          # number of matches in stage 2 (1 team is eliminated in each match)
          m2 = q - 1
          # total number of matches in the tournament
          t = m1 + m2
          if t in {365, 366}:
            printf("[{n} teams]", n=k * g)
            printf("stage 1: {k} groups of {g} teams = {m1} matches")
            printf("stage 2: {q} teams = {m2} matches")
            printf("total = {t} matches")
            printf()
      

      Solution: There were 48 teams in the tournament.

      Stage 1 consisted of 3 groups, each with 16 teams. In each group there were 120 matches. So stage 1 consisted of 360 matches.

      Stage 2 consisted of 6 teams (the top 2 teams from each of the 3 groups), so 5 matches were played to find the winner of the tournament. (2 matches in the first round, leaving 4 teams in the second round. 2 matches in the second round (semi-finals), leaving 2 teams to play in the final match).

      In total there were 365 matches.

      If there was an additional match for 3rd/4th place in the tournament there would be 1 extra match, which would bring the total to 366, but this could be played one match per day in a leap year, so the answer remains the same.


      With a bit of analysis:

      If M is the total number of matches, we get:

      k.g(g − 1)/2 + (2k − 1) = M

      k(g(g − 1) + 4) = 2(M + 1)

      And in this case we are looking for solutions where M = 365 or 366.

      So k is a divisor of 732 or 734 (k ≥ 3), and the remainder is g(g − 1) + 4 (which has a minimum value of 10).

      The only options are:

      M=365: k = 3, 4, 6, 12, 61.

      And only one of these gives a viable g value.

      Run: [ @replit ]

      from enigma import (divisors_pairs, quadratic, printf)
      
      # look for total number of matches = M
      def solve(M):
        # consider possible k values
        for (k, x) in divisors_pairs(2 * (M + 1), every=1):
          if k < 3 or x < 10: continue
          # look for possible g values
          for g in quadratic(1, -1, 4 - x, domain='Z', include='+'):
            if g < 3: continue
            printf("M={M}: k={k} g={g} -> n={n}", n=k * g)
      
      # consider possible total numbers of matches
      solve(365)
      solve(366)
      

      Like

    • Frits's avatar

      Frits 7:29 pm on 12 January 2024 Permalink | Reply

          
      # next higher power (<= 128)
      nhp = lambda n: [x for x in [2 ** i for i in range(1, 8)] if x >= n][0]
      
      # we have a least 3 groups of at least 2 players
      for n in range(6, 100):
        # the teams are allocated to more than two equally-sized groups
        divpairs = {(i, n // i) for i in range(2, int(n**.5) + 1) if n % i == 0}
        # for divisor pair (a, b) add pair (b, a)
        divpairs |= {(d2, d1) for d1, d2 in divpairs}
        divpairs = [(d1, d2) for d1, d2 in divpairs if d1 > 2]
        
        for ngrps, grpsz in divpairs:
          # number of games in stage 1 = ngrps * (grpsz * (grpsz - 1) // 2)
          # number of byes = next higher power - 2 * ngrps
          # tot = number of games in stage 1 plus (next power - 1 - number of byes)
          if ngrps * (grpsz * (grpsz - 1) // 2 + 2) - 1 in {365, 366}:
            print(f"answer: {n} teams")
      

      Like

    • Brian Gladman's avatar

      Brian Gladman 10:32 pm on 12 January 2024 Permalink | Reply

      I am not getting a solution (here) because I constrain the number of teams in round two to be a power of two by adding byes. Am I misreading the need for this constraint?

      Like

      • Brian Gladman's avatar

        Brian Gladman 1:21 am on 13 January 2024 Permalink | Reply

        I did misinterpret this.

        Like

      • Jim Randell's avatar

        Jim Randell 9:50 am on 13 January 2024 Permalink | Reply

        Although byes are used in the first round of stage 2 (the knockout stage), you don’t need to worry about them. In a knockout tournament each match eliminates 1 team, so starting with n teams you get down to 1 team after (n − 1) matches. (And if there is a match to determine 3rd/4th place there will be n matches in total).

        Like

        • Brian Gladman's avatar

          Brian Gladman 10:18 am on 13 January 2024 Permalink | Reply

          Thanks Jim, I did eventually figure out how it works. Thanks for correcting my link (but it is not very useful now since I have changed my code).

          Like

        • Guy's avatar

          Guy 11:04 am on 15 January 2024 Permalink | Reply

          Unfortunately, unlike Brian, I’m still confused.
          I think you have an unusual knockout tournament when there is not a power of 2 (eg 6) number of teams. With 6 teams in the Knockout Stage, the two teams in the final game will have played a different number of games in the Knockout Stage.
          The question appears to require that the Knockout Stage must have a power of 2 number of teams. So the number of groups determines the number of Stage One byes required. With 48 teams and 3 groups, you would get 6 teams (2 per Stage One group) through the Stage One route and need additional 2 byes to make up to 8 (next Power of 2) teams for the Knockout Stage. The teams with byes don’t play a game in Stage One. Hence the adjusted, now unequal, Stage One groups would be either 15,15,16 or 14,16,16. Total games would then be 337 (330+7) or 338 (331+7).

          Like

        • Jim Randell's avatar

          Jim Randell 1:41 pm on 15 January 2024 Permalink | Reply

          Here’s an example of how the tournament would work with 10 groups in stage 1 (so there would be 30, 40, 50, …, 90 teams in total).

          2 teams from each group proceed to stage 2 (the knockout stage), so there are 20 teams entering stage 2.

          But 20 is not a power of 2, so in the first round (of stage 2) we play pairs of teams against each other until the number of teams remaining is a power of 2.

          So in the example, 2 teams play, 1 is eliminated and 1 goes through to the second round (of stage 2), and there are 19 teams left in the tournament. This still isn’t a power of two, so another 2 teams play, 1 is eliminated and 1 goes through to the second round. And there are 18 teams left. Another 2 play, and there are 17 teams left. Another 2 play and there are 16 teams left, which is a power of 2.

          So, after 4 matches in round 1 of the knockout stage there are 16 teams remaining. The 12 teams that are still in round 1 are all given byes to round 2, and so there are 16 teams in round 2, so we have 8 matches in round 2, the winners go through to round 3, so there are 4 matches in round 3, 2 matches in round 4, and 1 (the final) match in round 5.

          The total number of matches in the knockout stage was: 4 + 8 + 4 + 2 + 1 = 19.

          But the simpler way to look at it is that one team is eliminated from the tournament with each knockout match, and we start with 20 teams, so after 19 matches there is only 1 team remaining (the winner).

          Like

          • Guy's avatar

            Guy 2:14 pm on 15 January 2024 Permalink | Reply

            OK, finally got it, thank you! Re-reading the question, the first round in “(they don’t have to play in the first round)” refers to first round of Knockout Stage, not the Group Stage. Following you help, it’s annoyingly obvious now.

            [The alternative problem with byes in Group Stage was still fun. Would have 99 teams split into 11 groups, you need to give 10 byes, so a possible arrangement for the 11 groups could be (3, 6, 8, 9, 9, 9, 9, 9, 9, 9, 9). The knockout stage then begins with 32 teams (11×2 from Group Stage plus the 10 byes).]

            Like

  • Unknown's avatar

    Jim Randell 8:39 am on 9 January 2024 Permalink | Reply
    Tags:   

    Teaser 2198: Developing houses 

    From The Sunday Times, 31st October 2004 [link]

    My Uncle Silas is a property developer. He recently bought some properties along a street of fewer than 400 houses. The odd-numbered houses were on the left side of the street, and the even-numbered houses were on the right. He bought eight adjacent houses on the left side of the street and seven adjacent houses on the right side. The sum of the house numbers on the left was a perfect square and was the same as the sum of the house numbers on the right.

    What was the largest house number that he bought?

    1000 Teasers and nearly 20 years ago.

    [teaser2198]

     
    • Jim Randell's avatar

      Jim Randell 8:40 am on 9 January 2024 Permalink | Reply

      I assumed that the houses are numbered consecutively, starting with 1.

      This Python program runs in 57ms. (Internal runtime is 421µs).

      Run: [ @replit ]

      from enigma import (irange, tuples, is_square, intersect, printf)
      
      # find <k> numbers from <seq> that sum to a perfect square
      def numbers(k, seq):
        # collect sequences by sum
        d = dict()
        for ns in tuples(seq, k):
          s = sum(ns)
          if is_square(s):
            d[s] = ns
        return d
      
      # find 8 adjacent odd numbers that sum to a perfect square
      odd = numbers(8, irange(1, 399, step=2))
      
      # find 7 adjacent even numbers that sum to a perfect square
      even = numbers(7, irange(2, 399, step=2))
      
      # and look for common sums
      for k in intersect([odd.keys(), even.keys()]):
        printf("{k} = {r}^2", r=is_square(k))
        printf("{k} = {ns}", ns=odd[k])
        printf("{k} = {ns}", ns=even[k])
        printf()
      

      Solution: The largest numbered house bought was number 118.

      The houses bought were:

      odds = (91, 93, 95, 97, 99, 101, 103, 105), sum = 784 (= 28^2)
      evens = (106, 108, 110, 112, 114, 116, 118), sum = 784 (= 28^2)


      If the first odd number is (2a + 1), then the odd numbers are:

      (2a + 1, 2a + 3, 2a + 5, 2a + 7, 2a + 9, 2a + 11, 2a + 13, 2a + 15)
      sum = 16a + 64 = 16(a + 4)

      And this sum is a square, so (a + 4) must be a square number:

      If the first even number is 2b, then the even numbers are:

      (2b, 2b + 2, 2b + 4, 2b + 6, 2b + 8, 2b + 10, 2b + 12)
      sum = 14b + 42

      And the sums are equal:

      16a + 64 = 14b + 42
      b = (8a + 11) / 7

      So we can consider possible square numbers for (a + 4) and look for corresponding b values that are integers.

      This can be investigated manually or programatically:

      Run: [ @replit ]

      from enigma import (irange, inf, sq, is_square, printf)
      
      # output a list of numbers, sum, and sqrt(sum)
      def output(t, ns):
        s = sum(ns)
        r = is_square(s)
        printf("-> {t} = {ns} = {s} (= {r}^2)")
      
      # consider squares for (a + 4) = i^2
      for i in irange(2, inf):
        a = sq(i) - 4
        # calculate b
        (b, r) = divmod(8 * a + 11, 7)
        if 2 * b + 12 > 399: break
        if r != 0: continue
        # output solution
        printf("a={a} b={b}")
        output('odds', list(irange(2 * a + 1, 2 * a + 15, step=2)))
        output('evens', list(irange(2 * b, 2 * b + 12, step=2)))
      

      There is only one a value that gives an integer value for b:

      sum = 16×49 = 784
      a = 45, b = 53

      Which gives rise to the two sequences given above.

      Like

      • Frits's avatar

        Frits 10:44 pm on 9 January 2024 Permalink | Reply

        b = (8a + 11) / 7 = (8 * (i^2 – 4) + 11) / 7 = (8 * i^2) / 7 – 3

        so i^2 must be divisible by 7 and
        as variable a can be seen to be less than 168.375 only i = 7 is an option
        leading to b = 53 and 2b + 12 = 118

        Like

    • John Crabtree's avatar

      John Crabtree 4:25 am on 10 January 2024 Permalink | Reply

      Let L and R be the integer averages on the left and right sides of the street.
      8L = 7R = n^2, which is less than 2800, ie n < 53.
      n = 0 (mod (4 * 7)) = 0 (mod 28), and so n = 28 and R = 112.
      The highest house number = 112 + 6 = 118.

      Like

    • GeoffR's avatar

      GeoffR 7:33 pm on 12 January 2024 Permalink | Reply

      
      from math import isqrt
      
      def is_sq(x):
         return isqrt(x) ** 2 == x
      
      # Eight odd numbers on left side of the street
      for n in range(1, 400, 2):
          L1, L2 = [], []
          L1 = [n, n+2, n+4, n+6, n+8, n+10, n+12, n+14]
          if not is_sq(sum(L1)):
              continue
          # Seven even numbers on right side of the street
          for m in range(2, 402, 2):
             L2 = [m, m+2, m+4, m+6, m+8, m+10, m+12]
             if sum(L2) == sum(L1):
                # Find  the largest house number
                if n+14 > m+12:
                   print('Largest house mumber = ', n+14)
                else:
                   print('Largest house mumber = ', m+12)
                     
      # Largest house mumber =  118  
      

      Like

  • Unknown's avatar

    Jim Randell 12:36 pm on 7 January 2024 Permalink | Reply
    Tags:   

    Teaser 2668: Small cubes 

    From The Sunday Times, 10th November 2013 [link] [link]

    Oliver and Megan each had a different- sized cuboid whose sides were all whole numbers of centimetres in length. Their cuboids were painted all over. They each cut their cuboid into one-centimetre cubes, some of which were unpainted, the rest being painted on one or more face. Oliver observed that for both cuboids, the number of cubes with no painted faces was the same as the number with two painted faces. Then Megan added: “I have more cubes than you, and the difference between our totals is equal to the number of your unpainted cubes”.

    How many of Megan’s cubes had just one painted face?

    [teaser2668]

     
    • Jim Randell's avatar

      Jim Randell 12:37 pm on 7 January 2024 Permalink | Reply

      Consider a cubiod with dimensions a × b × c. Then we can calculate the number of cubelets that are painted on the required number of faces:

      3 faces = 8
      2 faces = 4(a + b + c − 6)
      1 face = 2((a − 2)(b − 2) + (a − 2)(c − 2) + (b − 2)(c − 2))
      0 faces = (a − 2)(b − 2)(c − 2)

      providing the smallest dimension is greater than 1.

      And as some of the cubelets are unpainted the cuboids we are interested in must have smallest dimension of at least 3.

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

      Run: [ @replit ]

      from enigma import (defaultdict, irange, inf, decompose, map2str, printf)
      
      # total number of faces is indicated by key 7
      total = 7
      
      # for a cuboid of dimensions a x b x c
      # return number of cubelets by faces painted, and the total number of cubelets
      def cubelets(a, b, c):
        assert min(a, b, c) > 1
        r = dict()
        r[3] = 8
        r[2] = 4 * (a + b + c - 6)
        r[0] = (a - 2) * (b - 2) * (c - 2)
        t = a * b * c
        r[1] = t - sum(r.values())
        r[total] = t
        return r
      
      def solve():
        # collect cubes by total
        g = defaultdict(list)
        # consider increasing a + b + c dimensions
        for s in irange(3, inf):
          # consider cuboids for M
          for (a, b, c) in decompose(s, 3, increasing=-1, sep=0, min_v=3):
            # calculate number of cubelets
            r = cubelets(a, b, c)
            # we are interested in those cubes where r[0] = r[2]
            if not (r[2] == r[0] > 0): continue
      
            # consider smaller totals (for O)
            for (k, vs) in g.items():
              # difference between totals
              d = r[total] - k
              if d < 1: continue
              for (r_, (a_, b_, c_)) in vs:
                if r_[0] == d:
                  # return (M, O) as (cubelets, dimensions)
                  yield ((r, (a, b, c)), (r_, (a_, b_, c_)))
            # record this cuboid
            g[r[total]].append((r, (a, b, c)))
      
      # find possible (M, O) values
      for ((r, (a, b, c)), (r_, (a_, b_, c_))) in solve():
        fmt = lambda r: map2str(r, arr='->', enc="")
        printf("M = {a} x {b} x {c} [{r}]; O = {a_} x {b_} x {c_} [{r_}]", r=fmt(r), r_=fmt(r_))
        break  # only need the first answer
      

      Solution: Megan has 112 cubelets painted on just one face.

      Megan has a cuboid with dimensions: 12 × 5 × 4.

      12 × 5 × 4 = 240 cubelets
      8 painted on 3 faces
      60 painted on 2 faces
      112 painted on 1 face
      60 painted on 0 faces

      Oliver has a cuboid with dimensions: 8 × 6 × 4.

      8 × 6 × 4 = 192 cubelets
      8 painted on 3 faces
      48 painted on 2 faces
      88 painted on 1 face
      48 painted on 0 faces

      And:

      240 − 192 = 48


      If cuboids with a dimensions less than 3 were allowed, then we can find further solutions using cuboids that give 0 unpainted cubelets, such as:

      Oliver = 8 × 6 × 4 (= 192 cubelets, 48 unpainted, 48 painted on 2 faces)
      Megan = 120 × 2 × 1 (= 240 cubelets, 0 unpainted, 0 painted on 2 faces)

      Like

  • Unknown's avatar

    Jim Randell 4:42 pm on 5 January 2024 Permalink | Reply
    Tags:   

    Teaser 3198: The sixth element 

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

    Agent J discovered that S.P.A.M.’s IQ booster drug comprises five elements with atomic numbers Z under 92. Some information had been coded as follows: Z1[4;6], Z2[1;4], Z3[4;6], Z4[0;6] and Z5[7;2], where Z5 is lowest and Z3 is highest. Code key: [Remainder after dividing Z by 8; Total number of factors of Z (including 1 and Z). The drug’s name is the elements’ chemical symbols concatenated in encoded list order.

    J subsequently discovered the Z3 and Z5 values. Now MI6 had just fifteen possible sets of atomic numbers to consider. Finally, J sent a sixth element’s prime Z value (a catalyst in the drug’s production, not part of it). She’d heard it was below Z1 and above Z2, without knowing these. MI6 boffins were now sure of the drug’s name.

    Give the catalyst’s atomic number.

    [teaser3198]

     
    • Jim Randell's avatar

      Jim Randell 5:05 pm on 5 January 2024 Permalink | Reply

      This Python program checks that the six Z numbers are all different (although this is not explicitly stated in the puzzle text, but it seems like a reasonable additional requirement).

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

      Run: [ @replit ]

      from enigma import (
        defaultdict, irange, tau, group, cproduct, primes,
        singleton, printf
      )
      
      # map Z numbers to code
      code = lambda z: (z % 8, tau(z))
      
      # group Z numbers by code
      g = group(irange(1, 91), by=code)
      
      # choose a sequence from the given codes
      codes = [(4, 6), (1, 4), (4, 6), (0, 6), (7, 2)]
      
      # collect possible sequences by (z3, z5) values
      d = defaultdict(list)
      for (z1, z2, z3, z4, z5) in cproduct(g[k] for k in codes):
        if len({z1, z2, z3, z4, z5}) != 5: continue
        # z5 is the lowest
        if not (z5 < min(z1, z2, z3, z4)): continue
        # z3 is the highest
        if not (z3 > max(z1, z2, z4, z5)): continue
        d[(z3, z5)].append((z1, z2, z3, z4, z5))
      
      # knowing z3 and z5 gives 15 possible sequences
      for (k, vs) in d.items():
        if len(vs) != 15: continue
        # consider possible prime z6 values
        for z6 in primes.between(1, 91):
          # look for matching sequences
          check = lambda z1, z2, z3, z4, z5: z2 < z6 < z1 and z6 != z4
          zs = singleton(zs for zs in vs if check(*zs))
          if zs is None: continue
          # output solution
          printf("z6={z6} -> zs={zs}")
      

      Solution: The catalyst has atomic number 47.

      The constituent elements (Z1..Z5) have atomic numbers: 52, 33, 68, 32, 7.

      So, the name of the drug is: TEASERGEN (= Te As Er Ge N).

      And the catalyst (Z6) has atomic number 47 (= Ag (Silver)).

      Like

    • NigelR's avatar

      NigelR 12:48 pm on 7 January 2024 Permalink | Reply

      A bit convoluted but it seems to work!!

      from itertools import product
      
      def is_prime(n):
          if (n % 2 == 0 and n > 2) or n < 2: return False
          for i in range(3, int(n**0.5) + 1, 2):
              if n % i == 0: return False
          return True
      
      factno = lambda n: len([i for i in range(1, n + 1) if n % i == 0])
      zvals = lambda a,b: [i for i in range(1,92) if i%8 == a and factno(i) == b] 
      #Code values for z1 - z5
      Z = [[4,6], [1,4], [4,6], [0,6], [7,2]]
      #create dictionary d with lists of possible values for each element
      d = {i:zvals(x[0],x[1]) for i,x in enumerate(Z,1)}
      #create cand as list with valid sets of element values
      cand = []
      for x in (dict(zip(d.keys(), values)) for values in product(*d.values())):
          #z3 is highest, z5 is lowest and 5 different elements
          if x[3] != max(vals:= x.values()) or len(set(vals)) != 5 or x[5] != min(vals): continue
          else: cand.append(x)
      #remove duplicates and create list of valid x3 & x5
      z3z5 = [list(tupl) for tupl in {tuple(item) for item in [[x[3],x[5]] for x in cand]}]
      #Find z3z5 entry that has 15 possible sets
      res = [x for x in z3z5 if len([y for y in cand if y[3]==x[0] and y[5]==x[1]])==15 ]
      if len(res)>1 :
          print('unique solution not found')
          exit()
      else:
          res = res[0] #flatten res to list of selected x3 & x5
      #strip invalid sets from cand
      cand = [x for x in cand if x[3]==res[0] and x[5]==res[1]]
      z6lst=[]
      #look for possible prime values of z6 between z2 and z1
      for x in cand:
          if x[2]>x[1]:continue
          for y in range(x[2]+1,x[1]): 
              if is_prime(y):
                  z6lst.append([y,x])
      z6set = [x[0] for x in z6lst]
      #look for singleton value of z6
      z6 = [x for x in z6set if z6set.count(x)==1]
      if len(z6)==1:
          z6 = z6[0]
      else:
          print('unique solution not found')
          exit()
      soltn = [x for x in z6lst if x[0]==z6][0]
      print(f'Catalyst atomic number was {soltn[0]}.')
      outstr = 'Z' + '  Z'.join([str(i)+' = '+ str(soltn[1][x]) for i,x in enumerate (soltn[1],1)])
      print('Element values were: ', outstr,'.')
      

      Like

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