Updates from Jim Randell Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 8:48 am on 1 June 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 771: Doctor Bungle bungles 

    From The Sunday Times, 25th April 1976 [link]

    The doctors in the country town of Keepwell are keen soccer fans and with the assistance of their staff they have formed themselves into 3 teams who are all to play each other once.

    I asked my friend, Dr Bungle, who is secretary of one of the teams, if he could let me know the current situation and he produced the following table:

    I knew that not more than 3 goals had been scored in any match and it did not take me long to see that there was something wrong with the table. I discovered subsequently that the doctor had been taking a non-truth drug of his own prescription. The drug was not 100% effective and so all but one of the figures were incorrect, and the remaining figure was correct.

    What were the scores in the matches played so far?

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

    [teaser771]

     
    • Jim Randell's avatar

      Jim Randell 8:49 am on 1 June 2021 Permalink | Reply

      This Python program uses the [[ Football() ]] helper class from the enigma.py library.

      It runs in 49ms.

      Run: [ @replit ]

      from itertools import product
      from enigma import Football, printf
      
      # possible scores (not more than 3 goals scored)
      score = dict()
      score['w'] = { (1, 0), (2, 0), (3, 0), (2, 1) }
      score['d'] = { (0, 0), (1, 1) }
      score['l'] = set((y, x) for (x, y) in score['w'])
      score['x'] = [None]
      
      def check(xs, ys):
        return sum(x == y for (x, y) in zip(xs, ys))
      
      # scoring system (matches may not be played)
      football = Football(games='wdlx')
      
      # there are 3 matches
      for (AB, AC, BC) in football.games(repeat=3):
        # table rows for A, B, C
        A = football.table([AB, AC], [0, 0])
        B = football.table([AB, BC], [1, 0])
        C = football.table([AC, BC], [1, 1])
      
        # check for correct digits (the can be at most one)
        d1 = check(
          [A.played, A.w, A.l, A.d, B.played, B.w, B.l, B.d, C.played, C.w, C.l, C.d],
          [1, 0, 1, 0, 2, 2, 0, 0, 1, 0, 2, 1],
        )
        if d1 > 1: continue
      
        # consider possible scores
        for (sAB, sAC, sBC) in product(score[AB], score[AC], score[BC]):
          # goals for/against
          (fA, aA) = football.goals([sAB, sAC], [0, 0])
          (fB, aB) = football.goals([sAB, sBC], [1, 0])
          (fC, aC) = football.goals([sAC, sBC], [1, 1])
      
          # check for correct digits
          d2 = check([fA, aA, fB, aB, fC, aC], [2, 0, 1, 2, 0, 3])
          if d1 + d2 != 1: continue
      
          printf("AB={AB}:{sAB} AC={AC}:{sAC} BC={BC}:{sBC}; d1={d1} d2={d2}")
          printf("A={A}; f={fA} a={aA}")
          printf("B={B}; f={fB} a={aB}")
          printf("C={C}; f={fC} a={aC}")
          printf()
      

      Solution: The scores were: A vs B = 1-1; A vs C = 3-0; B vs C = 1-2.

      The only correct figure is B’s played value (= 2).

      Like

  • Unknown's avatar

    Jim Randell 2:36 pm on 30 May 2021 Permalink | Reply
    Tags:   

    Brain teaser 1000: One thousand down 

    From The Sunday Times, 20th September 1981 [link]

    This auspiciously-numbered Brain-teaser has given my wife a chance to take stock of the teasers which she has tried over the years. When the Brain-teasers started to be numbered she did one of the early ones and took most of that Sunday over it. So she decided not to spend every Sunday on them, but only to do those teasers whose numbers were multiples of that first one she had tried.

    This worked very well for a long time until one Sunday there was an exceptional teaser which she couldn’t resist doing, even though she had done the previous week’s. She so enjoyed doing that extra puzzle that she decided she would in future try precisely those teasers whose numbers were the sum of two numbers (possibly the same) of teasers which she had tried previously. She didn’t try last week’s, but she’ll be busy today trying this one. But the rest of us have suddenly realised with horror that we’re never going to get a decent Sunday lunch again, because my wife is going to have to do every Brain-teaser from now on.

    (1) What was the first teaser which she tried?
    (2) What was the number of that “exceptional teaser which she couldn’t resist”?
    (3) How many of the first 1,000 Brain-teasers will she have tried?

    [teaser1000]

     
    • Jim Randell's avatar

      Jim Randell 2:37 pm on 30 May 2021 Permalink | Reply

      (See also: Enigma 1154, Enigma 1194, Enigma 228, Enigma 122).

      If the first Teaser is number x, then she will try 2x, 3x, 4x, …. Until one day, having done kx she can’t resist also doing (kx + 1).

      So we can consider this to be a “money changing” problem, using denominations of x and y = (kx + 1).

      And the largest amount that cannot be expressed using these denominations is 999.

      This is the Frobenius Number of the denominations:

      F(x, y) = x⋅y − x − y

      And the number of amounts that are not expressible using the denominations is:

      N(x, y) = (x − 1)(y − 1) / 2

      The following Python program runs in 53ms.

      Run: [ @replit ]

      from enigma import irange, div, printf
      
      F = lambda x, y: x * y - x - y
      N = lambda x, y: div((x - 1) * (y - 1), 2)
      
      # consider the first teaser x (< 100)
      for x in irange(2, 99):
        # and consider multiples of x < 1000
        for kx in irange(2 * x, 997, step=x):
          y = kx + 1
          if F(x, y) == 999:
            # output solutions
            n = 1000 - N(x, y)
            printf("(1) {x}; (2) {y}; (3) {n}") 
      

      Solution: (1) The first Teaser she tried was number 5; (2) The Teaser she couldn’t resist was number 251; (3) She will have tried 500 of the first 1000 Teasers.

      Like

      • Jim Randell's avatar

        Jim Randell 4:59 pm on 30 May 2021 Permalink | Reply

        And the following program shows the numbers of the Teasers that were attempted:

        from enigma import irange, printf
        
        (x, y) = (5, 251)
        
        # collect attempted teasers
        ns = set()
        
        # attempt teaser n
        def attempt(n):
          ns.add(n)
          printf("{n}" + ("" if len(ns) % 15 == 0 else " \\"))
        
        # consider increasing teaser numbers
        for n in irange(1, 1000):
          # start by doing multiples of x
          if n < y:
            if n % x == 0:
              attempt(n)
          elif n == y:
            # and then do y
            attempt(n)
          else:
            # and then any number that is the sum of two previous numbers
            if any(n - a in ns for a in ns):
              attempt(n)
        
        printf("\nattempted = {n}", n=len(ns))
        

        Output:

        5 10 15 20 25 30 35 40 45 50 55 60 65 70 75
        80 85 90 95 100 105 110 115 120 125 130 135 140 145 150
        155 160 165 170 175 180 185 190 195 200 205 210 215 220 225
        230 235 240 245 250 251 255 256 260 261 265 266 270 271 275
        276 280 281 285 286 290 291 295 296 300 301 305 306 310 311
        315 316 320 321 325 326 330 331 335 336 340 341 345 346 350
        351 355 356 360 361 365 366 370 371 375 376 380 381 385 386
        390 391 395 396 400 401 405 406 410 411 415 416 420 421 425
        426 430 431 435 436 440 441 445 446 450 451 455 456 460 461
        465 466 470 471 475 476 480 481 485 486 490 491 495 496 500
        501 502 505 506 507 510 511 512 515 516 517 520 521 522 525
        526 527 530 531 532 535 536 537 540 541 542 545 546 547 550
        551 552 555 556 557 560 561 562 565 566 567 570 571 572 575
        576 577 580 581 582 585 586 587 590 591 592 595 596 597 600
        601 602 605 606 607 610 611 612 615 616 617 620 621 622 625
        626 627 630 631 632 635 636 637 640 641 642 645 646 647 650
        651 652 655 656 657 660 661 662 665 666 667 670 671 672 675
        676 677 680 681 682 685 686 687 690 691 692 695 696 697 700
        701 702 705 706 707 710 711 712 715 716 717 720 721 722 725
        726 727 730 731 732 735 736 737 740 741 742 745 746 747 750
        751 752 753 755 756 757 758 760 761 762 763 765 766 767 768
        770 771 772 773 775 776 777 778 780 781 782 783 785 786 787
        788 790 791 792 793 795 796 797 798 800 801 802 803 805 806
        807 808 810 811 812 813 815 816 817 818 820 821 822 823 825
        826 827 828 830 831 832 833 835 836 837 838 840 841 842 843
        845 846 847 848 850 851 852 853 855 856 857 858 860 861 862
        863 865 866 867 868 870 871 872 873 875 876 877 878 880 881
        882 883 885 886 887 888 890 891 892 893 895 896 897 898 900
        901 902 903 905 906 907 908 910 911 912 913 915 916 917 918
        920 921 922 923 925 926 927 928 930 931 932 933 935 936 937
        938 940 941 942 943 945 946 947 948 950 951 952 953 955 956
        957 958 960 961 962 963 965 966 967 968 970 971 972 973 975
        976 977 978 980 981 982 983 985 986 987 988 990 991 992 993
        995 996 997 998 1000 
        attempted = 500
        

        Like

    • John Crabtree's avatar

      John Crabtree 9:54 pm on 31 May 2021 Permalink | Reply

      If y = n * x + 1, this leads to (x – 1) * n * x = 1000 = 2^3 * 5^3
      And so x = 5, n = 50, y = 251, etc

      Like

      • Jim Randell's avatar

        Jim Randell 8:39 am on 1 June 2021 Permalink | Reply

        @John: A neat bit of analysis. It also provides the answer to (3) directly:

        y = kx + 1
        F(x, y) = xy − x − y = 999
        ⇒ kx(x − 1) = 1000

        N(x, y) = (x − 1)(y − 1) / 2 = (x − 1)kx / 2 = 1000/2

        Like

  • Unknown's avatar

    Jim Randell 5:10 pm on 28 May 2021 Permalink | Reply
    Tags:   

    Teaser 3062: Family stock 

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

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

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

    [teaser3062]

     
    • Jim Randell's avatar

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

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

      The following Python program runs in 50ms.

      Run: [ @replit ]

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

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

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

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

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

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


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

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

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

      Like

    • Brian Gladman's avatar

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

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

      Like

      • Jim Randell's avatar

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

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

        Like

    • GeoffR's avatar

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

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

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

      Like

      • Jim Randell's avatar

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

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

        This what I get when I run your code:

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

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

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

        Like

    • GeoffR's avatar

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

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

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

      Like

      • Jim Randell's avatar

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

        @Geoff: Thanks.

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

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

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

        Like

    • GeoffR's avatar

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

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

      Like

    • Frits's avatar

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

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

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

      Like

    • Frits's avatar

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

      Reporting all reasonable solutions.

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

      Shorter

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

      Like

      • Brian Gladman's avatar

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

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

        Like

        • Brian Gladman's avatar

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

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

          Like

    • Tony Brooke-Taylor's avatar

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

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

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

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

      Like

      • Jim Randell's avatar

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

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

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

        Like

    • GeoffR's avatar

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

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

      Like

  • Unknown's avatar

    Jim Randell 12:21 pm on 27 May 2021 Permalink | Reply
    Tags:   

    Teaser 2797: Sunday Times table 

    From The Sunday Times, 1st May 2016 [link] [link]

    Do you remember reciting your “times tables” — for example, one seven is 7, two sevens are 14, three sevens are 21, continuing 28, 35, … ” and going on for ever?

    I have consistently replaced some digits by letters and in this way the five-figure number TIMES can be found in the times table of each of its digits but not in the times table of any other digit. On the other hand, TABLE can be found in the times table of seven different digits, each of which is a digit of TIMES or TABLE.

    What number would be BEST?

    [teaser2797]

     
    • Jim Randell's avatar

      Jim Randell 12:21 pm on 27 May 2021 Permalink | Reply

      Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      It runs in 130ms.

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      # collect digits that divide x
      --code="divs = lambda x: set(d for d in irange(1, 9) if x % d == 0)"
      
      # TIMES is divisible by each of its digits, but no other digits
      "divs(TIMES) == {E, I, M, S, T}"
      
      # TABLE is divisible by 7 different digits, each of which is in TIMES or TABLE
      "(lambda ds=divs(TABLE): len(ds) == 7 and ds.issubset({A, B, E, I, L, M, S, T}))()"
      
      --answer="BEST"
      

      Solution: BEST = 3842.

      Like

    • Frits's avatar

      Frits 10:39 am on 30 May 2021 Permalink | Reply

      from itertools import permutations
      
      # return 1-digit divisors of n
      divs = lambda n: [i for i in range(1, 10) if n % i == 0]
      # are all elements of sequence s2 part of sequence s1?
      issubset = lambda s1, s2: all(str(y) in s1 for y in s2)
      
      for T, I, M, E, S in permutations("123456789", 5):
       TIMES = T + I + M + E + S
       ds = divs(int(TIMES))
       # TIMES is divisible by each of its digits, but no other digits
       if len(ds) != 5: continue
       if not issubset(TIMES, ds): continue
       
       remaining = set('123456789').difference([T, I, M, E, S])
      
       for A, B, L in permutations(remaining, 3):
         TABLE = TIMES[0] + A + B + L + TIMES[3]
         
         ds = divs(int(TABLE))
         # TABLE is divisible by 7 different digits, 
         # each of which is in TIMES or TABLE
         if len(ds) == 7: 
           if issubset(TIMES + TABLE, ds):
             print("BEST =", B + E + S + T)
      

      Like

  • Unknown's avatar

    Jim Randell 8:47 am on 25 May 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 766: Engagement party 

    From The Sunday Times, 21st March 1976 [link]

    Alf Walker and Jill Jones celebrated their engagement at a dinner party with younger members of their families and some friends. Of the men, two were named Smith, two Jones, and two Walker; these were similarly the maiden names of the women.

    The party of six couples sat at a rectangular table, one pair at each end, and two pairs along each side. Engaged and married couples, also men and women, were arranged alternately around the table. Nobody was engaged or married to, or sat opposite to, anyone of the same original surname.

    Alf, with Jill on his left, sat at the table head, and Don and Greta sat at the foot. Two sisters, Ivy and Lena, were on Alf’s side of the table, while Jill’s brother Eddy sat next to Jill on her side. Fred and Lena each sat between a Smith and a Jones.

    Others present were Jill’s school friend Kate, Alf’s friend Bill and his sister Hilda, and Cyril and his sister Greta.

    Name the other engaged couples.

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

    [teaser766]

     
    • Jim Randell's avatar

      Jim Randell 8:48 am on 25 May 2021 Permalink | Reply

      A bit convoluted, but not that tricky.

      The following Python program runs in 49ms.

      Run: [ @replit ]

      from enigma import subsets, update, chunk, printf
      
      # paired and opposite positions
      pairs = { (0, 1), (2, 3), (4, 5), (6, 7), (8, 9), (10, 11) }
      opps  = { (0, 7), (1, 6), (2, 11), (3, 10), (4, 9), (5, 8) }
      
      # positions we know
      first = list('AJE...DG.L.I')
      last  = list('WJJ.........')
      
      # allocate the remaining male last names
      for ns in subsets('SSJW', size=len, select="mP"):
        ls = update(last, [4, 6, 8, 10], ns)
      
        # L (pos 9) is between S and J
        if {ls[8], ls[10]} != {'S', 'J'}: continue
      
        # allocate the remaining female last names
        for ns in subsets('SSJWW', size=len, select="mP"):
          ls = update(ls, [3, 5, 7, 9, 11], ns)
      
          # I (pos 11) and L (pos 9) are siblings
          if ls[11] != ls[9]: continue
      
          # no opposite last names are the same
          if any(ls[x] == ls[y] for (x, y) in opps): continue
      
          # no pairs of last names are the same
          if any(ls[x] == ls[y] for (x, y) in pairs): continue
      
          # allocate the remaining male first names
          for ns in subsets('BCF', size=len, select="P"):
            fs = update(first, [4, 8, 10], ns)
      
            # F is between S and J
            f = fs.index('F')
            if {ls[f - 1], ls[f + 1]} != {'S', 'J'}: continue
      
            # C and G are siblings
            if ls[fs.index('C')] != ls[fs.index('G')]: continue
      
            # allocate the remaining female first names
            for ns in subsets('HK', size=len, select="P"):
              fs = update(fs, [3, 5], ns)
      
              # B and H are siblings
              if ls[fs.index('B')] != ls[fs.index('H')]: continue
      
              # collect the names
              ns = list(f + l for (f, l) in zip(fs, ls))
      
              # output the layout in pairs
              for (i, (x, y)) in enumerate(chunk(ns, 2)):
                printf("{x} + {y}; {z}", z=['engaged', 'married'][i % 2])
              printf()
      

      Solution: The other two engaged couples are: Fred Smith & Hilda Jones; Cyril Smith & Lena Walker.

      Going round the table the couples are:

      Alf Walker & Jill Jones (engaged)
      Eddy Jones & Kate Smith (married)
      Fred Smith & Hilda Jones (engaged)
      Don Walker & Greta Smith (married)
      Cyril Smith & Lena Walker (engaged)
      Bill Jones & Ivy Walker (married)

      Like

  • Unknown's avatar

    Jim Randell 11:36 am on 24 May 2021 Permalink | Reply
    Tags:   

    Teaser 2527: [Number prefixes] 

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

    Without repeating a digit I wrote down two five-figure numbers. For the first of these, its first two digits form a number divisible by two, its first three digits form a number divisible by three, and likewise for four and five. For the second number, looking again at the numbers formed by the first few digits, those of prime length are prime and the one of length four is a square. Furthermore the sum of the digits of the difference between the two numbers is itself a digit. Without doing much division you should now be able to answer the question:

    What are the two five-figure numbers?

    This puzzle was originally published with no title.

    [teaser2527]

     
    • Jim Randell's avatar

      Jim Randell 11:37 am on 24 May 2021 Permalink | Reply

      Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      The following run file executes in 122ms.

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      # suppose the numbers are: ABCDE and FGHIJ
      
      SubstitutedExpression
      
      # first 2, 3, 4, 5 digits of ABCDE are divisible by 2, 3, 4, 5
      "AB % 2 = 0"  # or: "B % 2 = 0"
      "ABC % 3 = 0"
      "ABCD % 4 = 0"  # or: "CD % 4 = 0"
      "ABCDE % 5 = 0"  # or: "E % 5 = 0"
      
      # first 2, 3, 5 digits of FGHIJ are prime
      "is_prime(FG)"
      "is_prime(FGH)"
      "is_prime(FGHIJ)"
      
      # FGHI is a perfect square
      "is_square(FGHI)"
      
      # the sum of the digits of the difference is a single digit
      "dsum(ABCDE - FGHIJ) < 10"
      
      --answer="(ABCDE, FGHIJ)"
      

      Solution: The numbers are: 52840 and 73961.

      Like

    • Frits's avatar

      Frits 12:07 pm on 26 May 2021 Permalink | Reply

      from itertools import compress
      from math import isqrt
      
      # return true if an integer <n> is a perfect square
      def is_square(n):
        if n % 144 not in {0, 1, 4, 9, 16, 25, 36, 49, 52,
                           64, 73, 81, 97, 100, 112, 121}:
          return False
        return isqrt(n) ** 2 == n
      
      def primesbelow(n):
        # rwh_primes1v2(n):
        """ Returns a list of primes < n for n > 2 """
        sieve = bytearray([True]) * (n // 2 + 1)
        for i in range(1, int(n ** 0.5) // 2 + 1):
          if sieve[i]:
            sieve[2*i*(i+1)::2*i+1] = \
            bytearray((n // 2 - 2 * i * (i + 1)) // (2 * i + 1) + 1)
        return [2, *compress(range(3, n, 2), sieve[1:])]
        
      digits = "0123456789"
      P = primesbelow(100000)
      odds = ["1", "3", "5", "7", "9"]
      
      second = []
      # determine second number FGHIJ
      for FG in [str(x) for x in P if 11 < x < 100]:
        (F, G) = (FG[0], FG[1])
        for H in [x for x in odds if x not in {F, G}]:
          if int(FG + H) not in P: continue
          for I in [x for x in digits if x not in {F, G, H}]:
            if not is_square(int(FG + H + I)): continue
            for J in [x for x in odds if x not in {F, G, H, I}]:
              if int(FG + H + I + J) not in P: continue
              second.append(FG + H + I + J)
      
      for FGHIJ in second:
        remaining = "".join(x for x in digits if x not in FGHIJ)
       
        # determine first number ABCDE
        for E in [x for x in remaining if x in "05"]:
          for B in [x for x in remaining if x not in {E} and x in "02468"]:
            for A in [x for x in remaining if x not in {B, E} and x != "0"]:
              for C in [x for x in remaining if x not in {A, B, E}]:
                if int(A + B + C) % 3: continue
                for D in [x for x in remaining if x not in {A, B, C, E}]:
                  if int(C + D) % 4: continue
                  
                  ABCDE = int(A + B + C + D + E)
                  # the sum of the digits of the difference between the two numbers
                  # is itself a digit
                  if sum(int(x) for x in str(abs(int(FGHIJ) - ABCDE))) > 9: continue
                  print(f"the two five-figure numbers are: {ABCDE} and {FGHIJ}")
      

      Like

    • GeoffR's avatar

      GeoffR 4:20 pm on 26 May 2021 Permalink | Reply

      
      from itertools import permutations
      from enigma import is_prime
      
      sq4 = [x ** 2 for x in range(32, 100)]
      
      # Find digits for first 5-digit number
      for P1 in permutations('1234567890', 5):
          A, B, C, D, E = P1
          if A == '0':
              continue
      
          # two,three, four and five digit numbers
          # are divisible by two, three, four and five
          AB = int(A + B)
          if AB % 2 != 0:
              continue
          ABC = int(A + B + C)
          if ABC % 3 != 0:
              continue
          ABCD = int(A + B + C + D)
          if ABCD % 4 != 0:
              continue
          ABCDE = int(A + B + C + D + E)
          if ABCDE % 5 != 0:
              continue
      
          # Find digits for second 5-digit number
          Q1 = set('1234567890').difference([A, B, C, D, E])
          for P2 in permutations(Q1):
              F, G, H, I, J = P2
              if F == '0':
                  continue
      
              # two, three and five digit numbers are prime
              FG = int(F + G)
              if not is_prime(FG):
                  continue
              FGH = int(F + G + H)
              if not is_prime(FGH):
                  continue
              # four digit number is square
              FGHI = int(F + G + H + I)
              if FGHI not in sq4:
                  continue
              FGHIJ = int(F + G + H + I + J)
              if not is_prime(FGHIJ):
                  continue
              
              # the sum of the digits in the difference between
              # the two numbers is a digit
              dd = sum(int(x) for x in str(abs(ABCDE - FGHIJ)))
              if not dd < 10:
                  continue
              print(f"Two five-figure numbers are {ABCDE} and {FGHIJ}.")
      
      # Two five-figure numbers are 52840 and 73961.
      
      

      Like

    • John Crabtree's avatar

      John Crabtree 6:46 pm on 26 May 2021 Permalink | Reply

      As the 3rd digit of N2 is odd, the 4th digit is 6.
      (10a + 4)^2 = 100a(a + 1) – 20a + 16, with 2nd digit odd for 0 < a < 6
      (10a + 6)^2 = 100a(a + 1) + 20a + 36, with 2nd digit odd for 3 < a N2 but the sum of the digits of the difference (SDD) cannot be 2
      86^2 = 7396, N2 = 73961, N2 > N1, SDD = 7, N1 = 52840 (not 42850)

      Using a prime factor calculator, 739 and 73961 are all prime.

      Like

  • Unknown's avatar

    Jim Randell 4:46 pm on 21 May 2021 Permalink | Reply
    Tags:   

    Teaser 3061: Ratio 

    From The Sunday Times, 23rd May 2021 [link] [link]

    Liam has split a standard pack of 52 cards into three piles; black cards predominate only in the second pile. In the first pile the ratio of red to black cards is 3 to 1. He transfers a black card from this pile to the second pile; the ratio of black to red cards in the second pile is now 2 to 1. He transfers a red card from the first pile to the third pile; the ratio of red to black cards in this pile is now a whole number to one.

    Liam told me how many cards (a prime number) were initially in one of the piles; if I told you which pile you should be able to solve this teaser.

    How many cards were initially in the third pile?

    [teaser3061]

     
    • Jim Randell's avatar

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

      I assume that Liam told the setter a specific pile number, and the total number of cards that was initially in that pile and this number of cards was a prime number.

      So knowing the number of the pile, and the fact that the total number of cards in that pile was prime (but not knowing the number itself), is sufficient for us to determine the number of cards that were in the third pile.

      This Python program runs in 48ms.

      Run: [ @replit ]

      from enigma import (irange, div, is_prime, printf)
      
      # generate possible piles
      # return (piles = ((red, black), ...), {indices of prime piles})
      def piles():
        # choose the number of red cards in pile 1 (a multiple of 3)
        for r1 in irange(3, 26, step=3):
          # there are 3 times as many reds as blacks
          b1 = div(r1, 3)
      
          # choose the number of black cards in pile 2 (+1 = a multiple of 2)
          for b2 in irange(3, 26 - b1, step=2):
            # with 1 extra black there are twice as many blacks as reds
            r2 = div(b2 + 1, 2)
            if r1 + r2 > 26: break
      
            # pile 3 has the remaining cards
            r3 = 26 - r1 - r2
            b3 = 26 - b1 - b2
            if b3 > r3: continue
            # with 1 extra red there are k times as many reds as blacks
            k = div(r3 + 1, b3)
            if k is None: continue
      
            printf("[{r1}R+{b1}B; {r2}R+{b2}B; {r3}R+{b3}B; k={k}]")
            ps = ((r1, b1), (r2, b2), (r3, b3))
            pr = set(i for (i, (r, b)) in enumerate(ps) if is_prime(r + b))
            yield (ps, pr)
      
      # collect piles, that have a prime number of cards in one of the piles
      ss = list((ps, pr) for (ps, pr) in piles() if pr)
      
      # look for unique solutions, identified by pile i being prime
      for i in (0, 1, 2):
        rs = list(ps for (ps, pr) in ss if i in pr)
        if len(rs) == 1:
          ((r1, b1), (r2, b2), (r3, b3)) = rs[0]
          printf("{r1}R+{b1}B; {r2}R+{b2}B; {r3}R+{b3}B [pile {i} is prime]", i=i + 1)
      

      Solution: There were initially 11 cards in the third pile.

      There are only 4 ways to construct the piles as described:

      [1] 3R+1B; 12R+23B; 11R+3B (4 + 35 + 13)
      [2] 6R+2B; 12R+23B; 8R+1B (8 + 35 + 9)
      [3] 9R+3B; 10R+19B; 7R+4B (12 + 29 + 11)
      [4] 12R+4B; 11R+21B; 3R+1B (16 + 32 + 4)

      The only collections with a prime number of cards in at least one pile are [1] (pile 3) and [3] (pile 2, pile 3).

      So Liam must have revealed there were 29 cards in pile 2, which means he has constructed collection [3] (as that is the only collection with a prime number of cards in pile 2).

      Although if Liam had revealed just the prime numbers of cards in the pile (without giving the pile number); 11, 13, or 29, that would have been sufficient to determine which collection he had constructed.

      So the second paragraph could be:

      “Liam told me the total number of cards that was initially in one of the piles (but not the number of the pile). This was a prime number, and that enabled me to work out the composition (number of red and black cards) of each of the piles. If I now told you the number of the pile whose total Liam had revealed to me, you could also work out the composition of each of the piles.”

      Like

      • Frits's avatar

        Frits 9:02 pm on 22 May 2021 Permalink | Reply

        from enigma import SubstitutedExpression, is_prime, div
        
        # the alphametic puzzle
        p = SubstitutedExpression(
          [
          # (r1   , b1), (r2, b2), (r3, b3) = 
          # (3 * C, C),  (EF, GH), (IJ, KL)
          
          # both pile 1 and pile 3 contain at least 1 black card
          # black cards predominate only in the second pile
          "0 < EF < 13",
          
          "2 * EF - 1 = GH",
            
          # black cards predominate only in the second pile
          # "3 * C + EF <= C + GH",
          # "3 * C + EF <= C + 2 * EF - 1",
          "2 * C <= EF - 1",                #  EF < 13 --> C < 6 
          
          # with 1 extra red there are k times as many reds as blacks
          "div(27 - 3 * C - EF, 26 - C - GH)",
          
          # Liam told me how many cards (a prime number) were initially 
          # in one of the piles
          "any(is_prime(x) for x in [EF + GH, 52 - 3 * C - EF - C - GH])",
        
          ],
          answer="(3 * C, C), (EF, GH), (26 - 3 * C - EF, 26 - C - GH)",
          d2i=dict([(0, "C")] + 
                   [(k, "E") for k in range(2, 6)] + 
                   [(k, "CE") for k in range(6, 10)] 
                  ),
          distinct="",
          reorder=0,
          verbose=256)
        
        answs = [y for _, y in p.solve()]
        
        for p in range(3):  
          ps = [a for a in answs if is_prime(sum(a[p]))]
          if len(ps) == 1:  # unique
             print(f"third pile has {sum(ps[0][2])} cards")
        

        Based on the generated code and some more analysis (we can conclude r2 is even and b1 is less than 5) only 12 (r2, b1) combinations are considered:

        from enigma import is_prime
        
        answs = []
        # r2 must be even as last pile can't have only 2 cards
        # (so we deal with odd primes only)
        for r2 in range(4, 13, 2):
          b2 = 2 * r2 - 1
          p2 = is_prime(r2 + b2)
          for b1 in range(1, min(r2 // 2, 26 - b2)):
            # 26 - b1 - b2 > 0 --> b1 < 26 - b2 
            
            # with 1 extra red there are <k> times as many reds as blacks
            (d, r) = divmod(27 - 3 * b1 - r2, 26 - b1 - b2)
            if r > 0: continue
            # a prime number of cards were initially in one of the piles
            if p2 or is_prime(52 - 4 * b1 - r2 - b2): 
              answs.append([(3 * b1, b1), (r2, b2), (26 - 3 * b1 - r2, 26 - b1 - b2)])
        
        for p in range(3):  
          ps = [a for a in answs if is_prime(sum(a[p]))]
          if len(ps) == 1:  # unique
             print(f"third pile has {sum(ps[0][2])} cards") 
        

        Like

      • Tony Brooke-Taylor's avatar

        Tony Brooke-Taylor 6:31 pm on 25 May 2021 Permalink | Reply

        I wanted to visualise this problem as points on the line where two surfaces intersect. Because of the simple relationships between the red count and black count in each pile, we can easily define planes on the same 3 axes such that one plane represents the black values and the others represent the set of reds corresponding to a given value of N, where N is the ratio of reds to blacks in the third pile, after the swaps. I followed the maths through and arrived at a set of constraints such that I had to test 11 combinations of (b1,b2) to get the 4 possible results. I expect my analysis is much the same as Frits’, but the route depends on which parameters we choose to loop. My code for the solution is not very interesting, but I thought I’d share my graphical representation. The code below is based on an approach set out by banderlog013 on stackoverflow. If you draw the plot for the appropriate value of N, and run your mouse down the line of intersection, you will see that only one point has integer values for x,y,z that sum to 26.

        
        
        import numpy as np
        import plotly.graph_objects as go
        from plotly.subplots import make_subplots
        from typing import Tuple, Iterable
        
        def plotPlane(fig: go.Figure,
                      normal: Tuple[int, int, int],
                      d: int,
                      values: Iterable,
                      colorScaleName: str) -> None:
        
            # x, y, z
            x, y = np.meshgrid(values, values)
            z = (-normal[0] * x - normal[1] * y - d) * 1. / normal[2]
        
            # draw plane
            surface = go.Surface(x=x, y=y, z=z, colorscale=colorScaleName, showscale=False)
            fig.add_trace(surface, row=1, col=1)
        
        N=1#Not correct but if you have solved the puzzle you will know what is
        
        point1  = -26
        normal1 = (1,1,1)
        
        point2  = -26.5
        normal2 = (3,1/2,N)
        
        # create figure
        fig = make_subplots(rows=1, cols=1, specs=[[{'type': 'surface'}]])
        # plot two intersectioned surfaces
        values = range(1, 26)
        plotPlane(fig, normal1, point1, values, "Hot")
        plotPlane(fig, normal2, point2, values, "Greys")
        fig.show()
        
        

        Like

    • Robert Brown's avatar

      Robert Brown 9:19 am on 22 May 2021 Permalink | Reply

      Following the steps in your program, I find a different answer from the one posted by Brian.

      My values are
      b1 = 1, r1 = 3: (r1 = 3*b1): total not prime
      b2 = 23, r2 = 12: (b2+1/r2 = 2): total not prime
      b3 = 2, r3 = 11: (r3+1/b3 = 6): total (13) is prime

      Am I doing something silly?

      Like

      • Jim Randell's avatar

        Jim Randell 9:49 am on 22 May 2021 Permalink | Reply

        @Robert: There are actually four collections of piles that can be constructed following the rules of the first paragraph of the puzzle text.

        But the second paragraph allows you to identify which one of those four provides the answer to the puzzle.

        Like

        • Robert Brown's avatar

          Robert Brown 7:53 am on 23 May 2021 Permalink | Reply

          Yes, Brian’s solution has prime totals for piles 2 & 3, my alternative just for pile 3. The other two have no prime totals. So if Liam had quoted the total for pile 3, we would have a choice of 2 solutions. It follows that he quoted the total for pile 2, leading to Brian’s solution.

          Like

          • Jim Randell's avatar

            Jim Randell 11:33 am on 23 May 2021 Permalink | Reply

            @Robert: That’s correct.

            Interestingly if Liam had revealed just the initial total number of cards in one of the piles (without revealing the number of the pile), and that number was prime, it would be enough for the setter to work out the composition of each of the piles.

            The setter can then tell us the number of the pile that Liam was referring to, and the fact that the total number of cards in that pile was prime, and this is enough for us to also work out the composition of each of the piles.

            Like

    • Hugh Casement's avatar

      Hugh Casement 1:13 pm on 30 May 2021 Permalink | Reply

      More troublesome logic.
      As far as I can see, the constraints are:
      red1 = 3 × black1
      black2 + 1 = 2 × red2
      (red3 + 1) mod black3 = 0
      and the total is 52 (with no variables being 0).

      I found well over 100 sets that satisfy those conditions!
      Prime numbers abound, so I don’t see how any conclusions can be drawn.
      How is it that others found only four possible sets?

      Like

    • Hugh Casement's avatar

      Hugh Casement 6:14 pm on 30 May 2021 Permalink | Reply

      Thanks for that, Jim. You can tell it’s a long time since I had a pack of cards in my hands!

      Like

  • Unknown's avatar

    Jim Randell 8:56 am on 20 May 2021 Permalink | Reply
    Tags:   

    Teaser 2792: Easter Teaser 

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

    I have written down three numbers and then consistently replaced digits by letters, with different letters for different digits, to give:

    EASTER
    SUNDAY
    TEASER

    In fact the first number is the lowest and one of these numbers is the sum of the other two.

    What is this SUNDAY‘s number?

    [teaser2792]

     
    • Jim Randell's avatar

      Jim Randell 8:56 am on 20 May 2021 Permalink | Reply

      We can get a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      This run file executes in 421ms.

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      "abs(SUNDAY - TEASER) = EASTER"
      
      "E < S" # EASTER < SUNDAY
      "E < T" # EASTER < TEASER
      
      --answer="SUNDAY"
      

      Solution: SUNDAY = 816270.


      For a faster solution we can use the (experimental) [[ SubstitutedExpression.split_sum() ]] solver.

      The following Python program runs in 58ms.

      Run: [ @replit ]

      from enigma import SubstitutedExpression, printf
      
      # solve the sum <expr>
      def check(expr, *extra):
        p = SubstitutedExpression.split_sum(expr, extra=extra, answer="SUNDAY").solver()
        for (s, ans) in p.solve(verbose=0):
          printf("SUNDAY = {ans} [{expr} / {s}]", s=p.substitute(s, expr))
      
      # check the two possibilities
      check('EASTER + SUNDAY = TEASER', 'E < S')
      check('EASTER + TEASER = SUNDAY', 'E < T')
      

      There is only one possible solution even without the information that EASTER is the lowest number. So the [[ E < S ]] and [[ E < T ]] clauses could be removed.

      Like

    • GeoffR's avatar

      GeoffR 9:58 am on 31 May 2021 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..9: E; var 0..9: A; var 1..9: S;
      var 1..9: T; var 0..9: R; var 0..9: U;
      var 0..9: N; var 0..9: D; var 0..9: Y;
      
      constraint all_different ([E,A,S,T,R,U,N,D,Y]);
      
      var 100000..999999: EASTER = 100000*E + 10000*A + 1000*S + 100*T + 10*E + R;
      var 100000..999999: SUNDAY = 100000*S + 10000*U + 1000*N + 100*D + 10*A + Y;
      var 100000..999999: TEASER = 100000*T + 10000*E + 1000*A + 100*S + 10*E + R;
      
      constraint EASTER < SUNDAY /\ EASTER < TEASER;
      constraint EASTER + TEASER == SUNDAY \/ EASTER + SUNDAY == TEASER;
      
      solve satisfy;
      output ["SUNDAY's number = " ++ show(SUNDAY) ];
      % SUNDAY's number = 816270
      % ----------
      % ==========
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 9:39 am on 18 May 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 768: Bus ticket numbers 

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

    On a recent bus journey I purchased the tickets for my wife and myself. On each was a four-figure number, and the sum of all eight digits was twenty-five.

    I remarked upon this to my wife who thereupon asked if any digit appeared more than twice in total, and whether the sum of the digits on either ticket was equal to thirteen.

    I answered both questions and my wife was able to deduce the two numbers on the tickets.

    What were they?

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

    [teaser768]

     
    • Jim Randell's avatar

      Jim Randell 9:41 am on 18 May 2021 Permalink | Reply

      If the ticket numbers are randomised then there is no solution. So I assumed that the tickets are consecutively numbered (I think the puzzle text should have stated this).

      This Python program runs in 84ms.

      Run: [ @replit ]

      from enigma import irange, tuples, nsplit, unpack, multiset, filter_unique, nconcat, printf
      
      # consider possible consecutive values for two tickets
      tickets = tuples((nsplit(n, 4) for n in irange(1, 9999)), 2)
      
      # the sum of all the digits is 25
      tickets = filter(unpack(lambda xs, ys: sum(xs) + sum(ys) == 25), tickets)
      
      # questions asked
      def q(xs, ys):
        # does any digit appear more than twice?
        ds = multiset.from_seq(xs, ys)
        q1 = any(v > 2 for v in ds.values())
        # do the digits on either ticket sum to 13?
        q2 = (sum(xs) == 13 or sum(ys) == 13)
        return (q1, q2)
      
      # the answers to the questions allow the tickets to be deduced
      ss = filter_unique(tickets, unpack(q)).unique
      
      # output solutions
      for (xs, ys) in ss:
        printf("tickets = {x}, {y}", x=nconcat(xs), y=nconcat(ys))
      

      Solution: The ticket numbers were 1299 and 1300.

      So the answers to questions were: No (no digit appears more than twice in total), and no (the digits on neither ticket sum to 13).

      For (yes, no), there are only three pairs: 0399 and 0400; 2199 and 2200; 3099 and 3100.

      For (no, yes) there are 132 pairs, and for (yes, yes) there are 273 pairs.

      Like

    • Frits's avatar

      Frits 8:25 pm on 31 May 2021 Permalink | Reply

      Doing the same (but not allowing leading zeroes) without using all the handy stuff in enigma.py.
      Some steps could have been combined.

      # convert digits to number
      d2n = lambda args: int("".join(map(str, args)))
      
      # return entries where the combination of columns <col1> and <col2> is unique
      def unique_cols(seq, col1=0, col2=1):
        return [s1 for s1 in seq 
                if len([1 for s2 in seq if s2[col1] == s1[col1] and 
                                           s2[col2] == s1[col2]]) == 1] 
       
      
      # consider possible consecutive values for two tickets
      tickets = list(zip((s := [[int(x) for x in str(n)] 
                          for n in range(1000, 10000)]), s[1:]))
       
      # the sum of all the digits is 25
      tickets = [(x, y) for (x, y) in tickets if sum(x) + sum(y) == 25]
      
      # store answers to the 2 questions
      tickets = [(any((s := x + y).count(p) > 2 for p in s),
                 sum(x) == 13 or sum(y) == 13, x, y) for (x, y) in tickets]
      
      # the answers to the questions allow the tickets to be deduced
      tickets = unique_cols(tickets)
      
      for t in tickets:
        print(f"tickets = {d2n(t[2])}, {d2n(t[3])}")
      

      Like

  • Unknown's avatar

    Jim Randell 9:32 am on 16 May 2021 Permalink | Reply
    Tags: by: Andrew Pennycook   

    Brain-Teaser 34: Rouge et noir 

    From The Sunday Times, 12th November 1961 [link]

    Audrey, Barbara, Catherine, Dorothy and Elizabeth were visiting Monte Carlo and decided to form a syndicate to play roulette. They bought ten counters and played on red (an even chance) all the time. Each time red lost they doubled the stake of the lost throw, but staked only a single counter after a win, irrespective of who was playing next. In order that each should have a chance to play, they took turns in alphabetical order, to play five throws running.

    They each had three wins and two losses in their five throws. Audrey and Dorothy both started with two wins and a loss. Catherine and Elizabeth had three consecutive wins and showed profits of five and four counters respectively. Barbara was the only one who didn’t show a profit.

    What was the order of colours for the twenty-five throws?

    [teaser34]

     
    • Jim Randell's avatar

      Jim Randell 9:33 am on 16 May 2021 Permalink | Reply

      This Python program runs in 49ms.

      Run: [ @replit ]

      from enigma import printf
      
      # construct sequence of win (R)/ loss (B) outcomes
      # k = current kitty
      # s = current stake
      # w = winnings for current player
      # ps = outcomes for the current player
      # ss = all outcomes
      def solve(k, s, w=0, ps='', ss=[]):
        # player n, go g
        n = len(ss)
        g = len(ps)
        # has this player had 5 goes?
        if g == 5:
          # only B did not make a profit
          if (n != 1) != (w > 0): return
          # C had a profit of 5, E had a profit of 4
          if n == 2 and w != 5: return
          if n == 4 and w != 4: return
          # C and E had 3 wins in a row
          if (n == 2 or n == 4) and 'RRR' not in ps: return
      
          # have all 5 players had their turn?
          ss_ = ss + [(ps, w)]
          if len(ss_) == 5:
            yield (k, ss_)
          else:
            # set up the next player
            yield from solve(k, s, 0, '', ss_)
      
        elif not(s > k):
          # choose an outcome for player n:
          # A and D start with win, win, lose = RRB
          if g < 3 and (n == 0 or n == 3):
            qs = ('B' if g == 2 else 'R')
          else:
            qs = 'BR'
          for q in qs:
            ps_ = ps + q
            # each player get 3 wins and 2 losses
            if ps_.count('R') > 3 or ps_.count('B') > 2: continue
            # a win?
            if q == 'R':
              yield from solve(k + s, 1, w + s, ps_, ss)
            else:
              # a loss
              yield from solve(k - s, 2 * s, w - s, ps_, ss)
      
      # start with a kitty of 10 and a stake of 1
      for (k, ss) in solve(10, 1):
        for (n, (ps, w)) in zip("ABCDE", ss):
          printf("{n}: {ps} -> {w}")
        printf("profit = {w}", w=k - 10)
        printf()
      

      Solution: The colours were: (R R B B R) (R R R B B) (B R R R B) (R R B R B) (B B R R R)

      The corresponding wins/losses are: (+1 +1 −1 −2 +4) (+1 +1 +1 −1 −2) (−4 +8 +1 +1 −1) (+2 +1 −1 +2 −1) (−2 −4 +8 +1 +1)

      For each player: A=+3; B=0; C=+5; D=+3; E=+4.

      Making a total profit of +15.

      Like

    • Frits's avatar

      Frits 2:01 pm on 2 June 2021 Permalink | Reply

      To be run with PyPy, somehow the “denest=1” option doesn’t seem to work here.

      from enigma import SubstitutedExpression
      
      # determine score based on bet set by previous sequence  
      def score(seq, prevseq):
        # remove trailing zeroes
        while prevseq[-1] == 0:
          del prevseq[-1]
        
        bet = 2 ** (5 - len(prevseq))
        t = 0
        for x in seq:
          t = t - bet if x == 0 else t + bet
          bet = 2 * bet if x == 0 else 1
        return t 
        
      
      # the alphametic puzzle
      p = SubstitutedExpression(
      [
      # they each had three wins and two losses in their five throws
      "all(sum(x) == 3 for x in [[A,B,C,D,E], [F,G,H,I,J], [K,L,M,N,O], \
                                 [P,Q,R,S,T], [U,V,W,X,Y]])",
      
      # Catherine and Elizabeth had three consecutive wins and ...
      "all(x in [(1, 1, 0), (0, 0, 1), (0, 1, 1)] for x in [(K, L, N), (U, V, X)])",
      # ... showed profits of five and four counters respectively
      "score([K,L,M,N,O], [F,G,H,I,J]) == 5",
      "score([U,V,W,X,Y], [P,Q,R,S,T]) == 4",                                   
      
      # Barbara was the only one who didn't show a profit
      "score([F,G,H,I,J], [A,B,C,D,E]) < 1",  
      ],
      answer="[A,B,C,D,E], [F,G,H,I,J], [K,L,M,N,O], [P,Q,R,S,T], [U,V,W,X,Y]",
      digits=range(0, 2),
      # Audrey and Dorothy both started with two wins and a loss    
      d2i=dict([(0, "ABPQMW")] + [(1, "CR")]),
      env=dict(score=score),         
      distinct="",
      #denest=1, # [CPython] work around statically nested block limit
      verbose=0)
      
      # print answers
      for (_, ans) in p.solve():
        for a in ans:
          rb = "".join("R" if x else "B" for x in a)
          print(f"({rb})", end=" ")
      print("")
      

      Like

      • Jim Randell's avatar

        Jim Randell 2:55 pm on 2 June 2021 Permalink | Reply

        @Frits: You can specify a more aggressive “denest” strategy, try [[ denest=32 ]]. (The default is 50).

        Like

  • Unknown's avatar

    Jim Randell 4:10 pm on 14 May 2021 Permalink | Reply
    Tags:   

    Teaser 3060: Even or odd 

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

    My daughter and I once played a game based on the number 13 and the following rule:

    Think of a positive whole number greater than 1.
    If it is even, halve it.
    If it is odd multiply it by 13 and add 1.
    Either of these operations is to be regarded as one step.
    Apply another step to the outcome of the first step, and then further steps successively.

    For our game, we chose different starting numbers that were odd, and the winner was the person who by the fewer number of steps reached the number 1. My daughter won because she started with the number that leads to 1 in the fewest number of steps.

    What was my daughter’s starting number?

    [teaser3060]

     
    • Jim Randell's avatar

      Jim Randell 4:31 pm on 14 May 2021 Permalink | Reply

      Working backwards from 1 we can find numbers that require increasing numbers of steps to reach 1, and then look for the first odd number.

      This Python program runs in 49ms.

      Run: [ @replit ]

      from enigma import (div, join, printf)
      
      # consider increasing numbers of steps
      k = 0
      ns = [1]
      while True:
        # take 1 step back
        even = list()
        odd = list()
        for n in ns:
          even.append(2 * n)
          x = div(n - 1, 13)
          if x is not None and x > 1 and x % 2 == 1:
            odd.append(x)
      
        k += 1
        ns = sorted(even + odd)
        printf("[{k} steps -> {ns}]")
      
        if odd:
          printf("solution = {odd} [in {k} steps]", odd=join(odd, sep=", "))
          break
      

      Solution: Her starting number was 315.

      Which takes 13 steps to arrive at 1 (as 315×13 + 1 = 4096 = 2^12).


      The first odd number can easily be found by looking for the smallest power of 2 that has a residue of 1 when divided by 13:

      >>> peek(d for (d, r) in (divmod(n, 13) for n in bit_permutations(2)) if r == 1) 
      315
      

      And you can find the answer with a calculator in a few seconds. Just repeatedly multiply 1/13 by 2 until you get an answer of the form x + 1/13, and the answer is x.

      I feel the setter could have had more fun with this sequence. See: [ @wikipedia ]

      As an extra puzzle, you might like to find the two different odd numbers, that would lead to a draw in the fewest number of steps.


      The answer to my additional puzzle is: 977211 and 25407803.

      These both reach 1 after 34 steps:

      [0] 977211; 25407803
      [1] 12703744; 330301440
      [2] 6351872; 165150720
      [3] 3175936; 82575360
      [4] 1587968; 41287680
      [5] 793984; 20643840
      [6] 396992; 10321920
      [7] 198496; 5160960
      [8] 99248; 2580480
      [9] 49624; 1290240
      [10] 24812; 645120
      [11] 12406; 322560
      [12] 6203; 161280
      [13] 80640
      [14] 40320
      [15] 20160
      [16] 10080
      [17] 5040
      [18] 2520
      [19] 1260
      [20] 630
      [21] 315
      [22] 4096 = 2^12

      [34] 1

      After the first 13 steps both sequences have reached 80640, which after another 8 steps reaches 315. And then 315 takes a further 13 steps to reach 1.

      Like

    • Frits's avatar

      Frits 9:51 pm on 14 May 2021 Permalink | Reply

      In order to reach 1 you have to reach a power of 2 first.

      from enigma import irange, inf
      
      for i in irange(2, inf):
        (d, r) = divmod(2 ** i  - 1, 13)
        if r == 0:
          print("daughter's starting number", d)
          break
      

      Like

    • Tony Brooke-Taylor's avatar

      Tony Brooke-Taylor 8:55 am on 15 May 2021 Permalink | Reply

      My solution is similar to Frits’, and I have extended it to find the corresponding number of steps. I then put this in a loop to find a set of starting points that would give us a path through the solution. I failed to find a solution beyond the 18th in a reasonable time. I can’t decide whether this is because there is no further solution or my algorithm is too inefficient.

      
      def solve(d):
        p=d*2
        while (p-1)%13!=0:
          p*=2
        return (p-1)//13, len(bin(p//d))-1
      
      
      i=1
      dest=1
      while i<19:
        res=solve(dest)
        print(res)
        dest=res[0] 
        i+=1
      
      

      Regarding Jim’s bonus question, my approach above provides one possible set of starting points, each of which passes through its successors. The total number of steps is then the sum of the steps from each to its immediate successor. An alternative path is to find the first solution, but continue multipying by 2 and recording each multiple that would also derive from an odd starting point. I found that these increased in units of 2**12. So one possible solution to Jim’s challenge is to find a starting point in the list my code generates, with a cumulative number of steps to our first solution which is a multiple of 12, n. A starting point that draws this number of steps is 2**n times the first solution.

      Like

      • Brian Gladman's avatar

        Brian Gladman 11:14 pm on 15 May 2021 Permalink | Reply

        HI Tony,

        You pose the question of whether your algorithm is too inefficient to find further solutions or whether there are none. But there is another possibility, namely that the algorithm you are using can only find a subset of the solutions. And this turns out to be true.

        Your approach (which I also used) is fine for finding solutions that are reached in the minimum number of steps but it only finds solutions where the forward process lands on a power of two immediately after the initial ’13 step’ .

        But there are solutions where this doesn’t happen. For example, the forward sequence for 6203 starts 6203, 80640, 40320, 20160, 10080, 5040, 2520, 1260, 630, 315, 4096, 2048, .. with a number after the initial forward step (80640) that is not a power of two.

        This means that to answer Jim’s extra question, you have to use an algorithm such as the one Jim uses that finds all solutions for a given number of steps. This turns out to be very efficient because (somewhat to my surprise) the number of solutions only grows at a modest rate as the number of steps increase.

        Like

        • Brian Gladman's avatar

          Brian Gladman 11:48 pm on 15 May 2021 Permalink | Reply

          PS. I have quoted a sequence that your approach does find – I should have quoted one it doesn’t find.

          Like

          • Tony Brooke-Taylor's avatar

            Tony Brooke-Taylor 12:33 pm on 17 May 2021 Permalink | Reply

            Thanks Brian. I get your point about the powers of two. I had been too interested in exploring larger numbers of steps when really we only need to look at a few handfuls – and in more detail. I believe my path routine hangs beyond the 18th step because by then I am at such high powers of 2 my machine is struggling to compute.

            I have to conclude that Jim’s approach is much slicker than what I was trying to do. Nevertheless, out of pig-headedness I have extended my approach in an attempt to emulate the results from Jim’s algorithm. I still struggle to be certain of exhaustivity beyond a certain number of steps but my list is ALMOST the same as Jim’s: the first disagreement arises at 38 steps; where Jim produces a solution that I cannot replicate. To anyone who has not already moved on: I’d be grateful for any insight into what’s gone wrong.

            
            import itertools
            from functools import reduce
            
            #Finds the first odd starting point that produces input number d
            #Also reports the number of steps 
            def solve(d):
              rungs=[]
              step=1
              p=d*2
            #  while (p-1)%13!=0 and step<=50:
              while step<=13:
                p*=2
                step+=1
                if (p-1)//13 == (p-1)/13:
                  rungs+=((p-1)//13, len(bin(p//d))-2)
                  return ((p-1)//13, len(bin(p//d))-2)
            #    return rungs
            
            #Finds the ladder of starting points that produce the input number r
            #Each step in the ladder results in its predecessor in the list, with
            #the reported number of steps
            
            def ladder(r):
              i=1
              dest=r
              points=[]
              while i<50:
                res=solve(dest)
                if res == None:break
                points.append(res)
                dest=res[0]
                i+=1
              return points
            
            #Exploits Fermat's little theorem to generate a series of solutions from a single solution
            def project(rslt):
              rs = rslt[0]*13+1
              RS = [((rs*(2**(12*n))-1)//13) for n in range(1,6)]
              LT = [rslt[1]+12*n for n in range(1,6)]
              return [(rl,st) for rl,st in zip(RS,LT)]
            
            #Runs the ladder algorithm for each solution in a list
            def ladder_vector(vec):
              lad_vec=[]
              for v in vec:
                X=[l[0] for l in ladder(v[0])]
                Y=[v[1]+sum([l[1] for l in ladder(v[0])[:j+1]]) for j in range(len(ladder(v[0])))]
                lad_vec+=[(x,y) for x,y in zip(X,Y)]
              return lad_vec
            
            #Runs the project algorithm for each solution in a list
            def project_vector(vec):
              prj_vec=[]
              for v in vec:
                prj_vec+=project(v)
              return prj_vec
              
            #Using Fermat's little theorem to guarantee a list of starting points
            #Length of this list is arbitrary but long enough to find the winning results
            baseline = [((2**(12*n)-1)//13,12*n+1) for n in range(1,6)]
            
            #Alternate between Fermat and ladder to add solutions into the main list
            results=[]
            results+=baseline
            results+=ladder_vector(baseline)
            results+=project_vector(baseline)
            results+=project_vector(ladder_vector(baseline))
            results+=ladder_vector(project_vector(baseline))
            
            #Eliminate duplicates, sort and cut off results beyond solution
            final = [f for f in list(set(results)) if f[1]<51]
            final.sort(key=lambda a: a[1])
            print(*final, sep='\n')
            
            

            Like

            • Tony Brooke-Taylor's avatar

              Tony Brooke-Taylor 5:52 pm on 17 May 2021 Permalink | Reply

              Now replicated Jim’s result: needed to be smarter about looping in the main program.

              Like

              • Brian Gladman's avatar

                Brian Gladman 11:08 pm on 17 May 2021 Permalink | Reply

                Congratulations for sticking with it Tony!

                Like

  • Unknown's avatar

    Jim Randell 9:42 am on 13 May 2021 Permalink | Reply
    Tags:   

    Teaser 2501: [Triangular bipyramid] 

    From The Sunday Times, 29th August 2010 [link] [link]

    Mark took two identical regular tetahedra and stuck them together to make a “triangular bipyramid” with six triangular faces, five vertices and nine edges. On each edge he wrote a number, choosing them so the sum of the three numbers around any face gave the same “face total”. Furthermore if you chose any vertex and added up the numbers on the three or four edges meeting there, then you got the same “vertex sum” each time. Mark then noticed that if he reversed the order of the three digits in the “face sum” then he got the “vertex sum”.

    What is the sum of the nine numbers?

    This puzzle was originally published with no title.

    [teaser2501]

     
    • Jim Randell's avatar

      Jim Randell 9:42 am on 13 May 2021 Permalink | Reply

      If the face sum is F, and the vertex sum is V, and the total sum of the values of the edges is T.

      Then adding up the sums for all 6 faces counts each edge twice:

      6F = 2T

      Also adding up the sums for all 5 vertices counts each edge twice:

      5V = 2T

      Hence:

      6F = 5V

      So: F < V and F must be divisible by 5. And we know F and V are 3 digit numbers where one is the reverse of the other.

      There is only one possible solution for this scenario, so we can calculate T (the required answer).

      This Python program finds the values of F, V, T, and then also solves the equations to find the values on the edges. It runs in 53ms.

      from enigma import (irange, div, matrix, catch, nreverse, join, printf)
      
      # consider possible 3-digit values for F (must be divisible by 5)
      for F in irange(105, 999, step=10):
        # calculate V
        V = div(6 * F, 5)
        if V > 999: break
        # check V is the reverse of F
        if nreverse(F) != V: continue
        T = div(5 * V, 2)
        printf("F={F} V={V}; T={T}")
      
        # solve the equations to find edge values
        eq = matrix.equation("abcdefghi")
        # face sums = F
        fs = list(eq(fs, F) for fs in ["abe", "acd", "bcf", "dgi", "egh", "fhi"])
        # vertex sums = V
        vs = list(eq(vs, V) for vs in ["abc", "ghi", "adeg", "befh", "cdfi"])
      
        s = catch(matrix.linear, fs + vs)
        if s:
          printf("-> {s}", s=join(s, sep=", ", enc="()"))
      

      Solution: The sum of the numbers on the edges is 1485.

      The 3 edges that form the “equator” have values of 99. The other 6 edges have values of 198 (= 2×99). And 3×99 + 6×198 = 1485.

      Each face has a sum of 495 (= 5×99).

      Each vertex has a sum of 594 (= 6×99).


      It makes sense that there are only 2 different edge values, as there is nothing to distinguish the “north pole” from the “south pole”, nor the rotation of the bipyramid. The only edges we can distinguish are the “equator” edges (q) from the “polar” edges (e).

      Which gives a much simpler set of equations to solve:

      F = 2e + q
      V = 3e = 2e + 2q
      ⇒ q = V − F; e = 2q

      So for: F = 495, V = 594, we get: q = 99, e = 198.

      Like

    • GeoffR's avatar

      GeoffR 3:52 pm on 14 October 2021 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % Face, vertex and edge descriptions of tetrahedra.
      % Top tetrahedron has faces F2 and F3 visible, and back face F1 not visible.
      % Bottom tetrahedron has faces F5 and F6 visible, and back face F4 not visible.
      % Top and bottom vertices are V1 and V5 respectively.
      
      % Two tetrahedra join at vertices V2, V3 and V4.
      % Face F2 has vertices V1, V2 and V4, Face F3 has vertices V1, V3 and V4.
      % Face F1 has vertices V1, V2 and V3.
      % e1 = V1-V2, e2 = V1-V4, e3 = V1-V3
      % e4 = V2-V3, e5 = V2-V4, e6 = V3-V4
      % e7 = V2-V5, e8 = V4-V5, e9 = V3-V5
      
      % Edges
      var 34..333:e1; var 34..333:e2; var 34..333:e3;
      var 34..333:e4; var 34..333:e5; var 34..333:e6;
      var 34..333:e7; var 34..333:e8; var 34..333:e9;
      
      % Similar edges for two identical regular tetrahedra
      constraint e1 == e7 /\ e3 == e9 /\ e2 == e8; % sloping edges
      constraint e4 == e5 /\ e5 == e6;  % junction of two  tetrahedra
      
      % Sum of the nine numbers
      var 306..2997: Edge_Sum = e1 + e2 + e3 + e4 + e5 + e6 + e7 + e8 + e9;
      
      % Vertices
      var 102..999:V1; var 102..999:V2; var 102..999:V3;
      var 102..999:V4; var 102..999:V5; 
      
      % Faces
      var 102..999:F1; var 102..999:F2; var 102..999:F3;
      var 102..999:F4; var 102..999:F5; var 102..999:F6;
      
      % Face totals all the same
      constraint F1 == e1 + e2 + e4 /\ F2 == e1 + e2 + e5;
      constraint F3 == e2 + e3 + e6;
      constraint F4 == e4 + e7 + e9;
      constraint F5 == e5 + e7 + e8 /\ F6 == e6 + e8 + e9;
      constraint F1 == F2 /\ F1 == F3 /\ F1 == F4 /\ F1 == F5 /\ F1 == F6;
      
      % Vertex totals all the same
      constraint V1 == e1 + e2 + e3 /\ V2 == e1 + e4 + e5 + e7;
      constraint V3 == e3 + e4 + e6 + e9;
      constraint V4 == e5 + e6 + e8 + e2 /\ V5 == e7 + e8 + e9;
      constraint V1 == V2 /\ V1 == V3 /\ V1 == V4 /\ V1 == V5;
      
      % Three digits of  F1 = reverse three digits of V1
      constraint F1 div 100 == V1 mod 10;
      constraint F1 div 10 mod 10 == V1 div 10 mod 10;
      constraint F1 mod 10 == V1 div 100;
      
      solve satisfy;
      
      output [ "Total edge sum = " ++ show(Edge_Sum) 
      ++ "\n" ++ "Face sum = " ++ show(F1) 
      ++ "\n" ++ "Vertex sum = " ++ show(V1)];
      
      % Total edge sum = 1485
      % Face sum = 495
      % Vertex sum = 594
      % ----------
      % ==========
      
      
      
      

      Interesting to note that Euler’s polyhedron formula (V – E + F = 2) also applies to this triangular bipyramid, as V = 5, E = 9 and F = 6, so 5 – 9 + 6 = 2

      Like

  • Unknown's avatar

    Jim Randell 9:25 am on 11 May 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 763: Old Father Prime 

    From The Sunday Times, 29th February 1976 [link]

    Albert Prime will be joining us again today [*] for the 15th celebration of the anniversary of his birth since he was home on leave during the 1914-18 war.

    On that occasion, his son David’s age plus his brother Bert’s age was equal to his brother Charlie’s age; [and] Bert’s age plus Charlie’s age was equal to Albert’s age.

    All the ages except Albert’s were prime numbers and Albert’s was the cube of David’s. All four were born on 29th February in different years and the ages above are taken by counting how many 29th Februarys they have celebrated (for example, a man born on 29th February 1956 has an age of 5 today [*]).

    In what year was Albert born?

    Note: [*] This puzzle was originally published on 29th February 1976.

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

    [teaser763]

     
    • Jim Randell's avatar

      Jim Randell 9:26 am on 11 May 2021 Permalink | Reply

      B, C, D are prime, and A = D³ = B + C, also: B + D = C.

      So, given a value for D we can calculate the other values as follows:

      A = D³
      B = (A − D) / 2
      C = B + D

      And then determine the birth years.

      This Python program runs in 51ms.

      Run: [ @replit ]

      from datetime import date
      from enigma import Primes, cb, div, printf
      
      # find the year of the k'th 29th February before year y
      def year(k, y):
        while True:
          try:
            d = date(y, 2, 29)
            if k == 0: return y
            k -= 1
          except ValueError:
            pass
          y -= 1
      
      # some primes
      primes = Primes(100)
      
      # choose a value for D
      for D in primes:
        # calculate A
        A = cb(D)
        if A > 100: break
        # calculate B
        B = div(A - D, 2)
        if B not in primes: continue
        # calculate C
        C = B + D
        if C not in primes: continue
        printf("[A={A} B={B} C={C} D={D}]")
      
        # calculate birth years
        y = year(15, 1976)
        assert 1914 <= y <= 1918
        (a, b, c, d) = (year(x, y) for x in (A, B, C, D))
        printf("born: A={a} B={b} C={c} D={d} [y={y}]")
      

      Solution: Albert was born in 1880.

      Charlie was born in 1892. Bert was born in 1904. David was born in 1908.

      Note that 1900 was not a leap year.

      In 1916, Albert celebrated his 8th anniversary leap day (he was 36). Charlie celebrated his 5th anniversary leap day (he was 24). Bert celebrated his 3rd anniversary leap day (he was 12). David celebrated his 2nd anniversary leap day (he was 8).


      The fact: B + D = C and these values are all primes, implies that one of them must be 2. D is the obvious candidate, and the other values follow immediately. (D has to be a prime, whose cube is also relatively small, so there are very few options for D anyway).

      The only remaining wrinkle is remembering to skip the year 1900 when counting 8 leap years back from 1916.

      Like

  • Unknown's avatar

    Jim Randell 9:21 am on 9 May 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 33: Postal purchases 

    From The Sunday Times, 5th November 1961 [link]

    A rectangular sheet of postage stamps (i.e., one with each row containing the same number of stamps) was sold in such a way that each successive customer bought either a complete row or a complete column, thereby leaving the sheet rectangular after each purchase.

    The 2nd customer bought 6 stamps more than the 4th and half as many again as the 6th customer. The 5th customer bought twice as many stamps as the 12th. After the 7th customer had made his purchase exactly one-third of the original sheet had been sold.

    What was the size of the original sheet of stamps? And what was the total number of stamps bought by the first 12 customers?

    [teaser33]

     
    • Jim Randell's avatar

      Jim Randell 9:21 am on 9 May 2021 Permalink | Reply

      (See also: Enigma 460).

      This Python program runs in 51ms.

      Run: [ @replit ]

      from enigma import (irange, inf, printf)
      
      # make k purchases from an (x, y) rectangle
      def solve(k, x, y, t, ss=[]):
        # perform checks:
        n = len(ss)
        # the 2nd purchase is divisible by 3 and is greater than 6
        if n == 2 and not (ss[1] > 6 and ss[1] % 3 == 0): return
        # the 4th purchase is the 2nd less 6
        if n == 4 and not (ss[3] == ss[1] - 6): return
        # the 5th purchase is divisible by 2
        if n == 5 and not (ss[4] % 2 == 0): return
        # the 6th purchase is (2/3) the 2nd
        if n == 6 and not (ss[5] * 3 == ss[1] * 2): return
        # after the 7th purchase 1/3 of the original sheet is sold
        if n == 7 and not (sum(ss) * 3 == t): return
        # the 12th purchase is half the 5th
        if n == 12 and not (ss[11] * 2 == ss[4]): return
      
        # are we done?
        if k == 0:
          yield ss
        else:
          if y > 1:
            # buy a row of x stamps
            yield from solve(k - 1, x, y - 1, t, ss + [x])
          if x > 1:
            # buy a column of y stamps
            yield from solve(k - 1, x - 1, y, t, ss + [y])
      
      # diagonal enumeration of (x, y) pairs, x > y
      def pairs(a, b):
        # consider the sum of the dimensions
        for t in irange(a, b):
          # values for y
          for y in irange(1, t // 2):
            yield (t - y, y)
      
      def run():
        # consider (x, y) rectangles
        for (x, y) in pairs(12, inf):
          # attempt 12 purchases
          for ss in solve(12, x, y, x * y):
            yield (x, y, ss)
      
      for (x, y, ss) in run():
        printf("x={x} y={y}: {ss} -> {t}", t=sum(ss))
        break
      

      Solution: The original sheet consisted of 21 × 18 stamps (= 378 stamps in total). Between them, the 12 customers purchased 208 stamps.

      The individual purchases were (1st – 12th): 21, 21, 21, 15, 20, 14, 14, 18, 18, 18, 18, 10.

      The following diagram shows one way the original sheet could have been sold. Each purchase is numbered, and the number of stamps bought is given in brackets.

      Initially there are 378 stamps in the sheet.

      After the first 7 purchases (shown in red) the yellow and green squares remain. A total of 252 stamps, which is 2/3 of the original 378 stamps, so 1/3 have been sold.

      After all 12 purchases (red and yellow) only the green squares remain. A total of 170 stamps, so 208 stamps have been sold in all.

      Like

      • Frits's avatar

        Frits 10:41 am on 1 June 2021 Permalink | Reply

        You can already skip (x, y) combinations in run() if x * y is not a multiple of 3.

        Like

    • Frits's avatar

      Frits 11:20 am on 2 June 2021 Permalink | Reply

      Only one (x, y) rectangle is possible (without even considering purchases as the 6th).
      Second question is not dealt with.

      from enigma import irange
        
      # the 2nd purchase is divisible by 3 and is greater than 6
      # the 4th purchase is the 2nd less 6
      # the 5th purchase is divisible by 2
      # the 6th purchase is (2/3) the 2nd
      # after the 7th purchase 1/3 of the original sheet is sold
      # the 12th purchase is half the 5th
       
      # diagonal enumeration of (x, y) pairs, x > y
      def pairs(a, b):
        # consider the sum of the dimensions
        for t in irange(a, b):
          # values for y
          for y in irange(1, t // 2):
            yield (t - y, y)
            
      for (x, y) in pairs(12, 196):              # assume x < 100
        # consider x, y with y + 3 <= x <= y + 7 (purchase 2 and 4 rules)
        # and                x % 3 != 2          (purchase 2 rule)
        # purchase 7 rule makes x * y a multiple of 3
        if (x * y) % 3 or x < y + 3 or x > y + 7 or x % 3 == 2: continue
        
        # 2nd purchase comes from initial long side
        # 4th purchase comes from initial short side 
        for a in range(1, 7): 
          b = 7 - a
          # after the 7th purchase 1/3 of the original sheet is sold
          if (x - a) * (y - b) * 3 != 2 * (x * y): continue
             
          # if only 2nd purchase made from initial long side (b = 1)
          if b == 1:
            # 1st purchase is made from the initial short side 
            if (x - 1) % 3: continue
            
            # if y is odd then the 5th purchase is odd, impossible
            if y % 2: continue
            
            # purchases 3 - 7 must be equal to 2nd purchase - 6 (and even)
            # so 2nd purchase must be even as well
            if x % 2: continue
            
          
          # if only 4th purchase made from initial short side (a = 1)
          if a == 1:
            # x must be three higher than y (the 4th purchase is the 2nd less 6)
            if x != y + 3: continue
          
          # if initial long side is a multiple of 3 
          if x % 3 == 0: 
            # the 1st purchase must be made from the long side 
            # after the first 2 purchases the short side has decremented with 2
            if x > y + 4: continue    # 4th purchase rule
            
            if x == y + 4:
              # the 3rd purchase must be made from the initial short side 
              # (difference between sides may not become higher than 6)
              # so both sides after 4 purchases have decremented with 2
              if x % 2 and y % 2: continue    # 5th purchase must be even
         
          print(f"{(x, y) = } {(a, b) = } remaining {(x - a), (y - b) = }")
      
      # (x, y) = (21, 18) (a, b) = (3, 4) remaining (x - a), (y - b) = (18, 14)
      

      Like

  • Unknown's avatar

    Jim Randell 4:37 pm on 7 May 2021 Permalink | Reply
    Tags:   

    Teaser 3059: Nine blocks to the diner 

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

    “Sure, I can help. From this hotel it’s nine blocks to the diner; from there it’s five blocks to the library, and then six blocks back here. I guess instead you could come back from the diner to the museum — that’s four blocks — and then seven blocks back here. Or three blocks to the gallery and then eight blocks back here.”

    “So the diner’s straight along here?”

    “No sir, it’s not straight along one road for any of these trips; I just meant so many edges of blocks. The city’s on a square grid, and all these places are on corners, but, fact is, none of them is on the same street or avenue as any other one.”

    How many blocks between the library and the museum, museum and gallery, and gallery and library?

    [teaser3059]

     
    • Jim Randell's avatar

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

      Here’s a quick solution using the [[ SubstitutedExpression ]] solver from the enigma.py library. It runs in 127ms.

      Run: [ @replit ]

      #! python3 -m enigma -rr
      
      # suppose:
      #   (X, Y) = hotel
      #   (A, B) = diner
      #   (C, D) = library
      #   (E, F) = museum
      #   (G, H) = gallery
      
      SubstitutedExpression
      
      --digits="0-7" # smallest grid with solutions
      
      # each location has x, y co-ordinates different from all the other locations
      --distinct="ACEGX,BDFHY"
      
      # distance metric (work around PEP 3113)
      --code="dist = ulambda('(a, b), (x, y): abs(a - x) + abs(b - y)')"
      
      # 9 blocks from hotel (X, Y) to diner (A, B)
      "dist((X, Y), (A, B)) = 9"
      
      # 5 blocks from diner (A, B) to library (C, D)
      "dist((A, B), (C, D)) = 5"
      
      # 6 blocks from library (C, D) to hotel (X, Y)
      "dist((C, D), (X, Y)) = 6"
      
      # 4 blocks from diner (A, B) to museum (E, F)
      "dist((A, B), (E, F)) = 4"
      
      # 7 blocks museum (E, F) to hotel (X, Y)
      "dist((E, F), (X, Y)) = 7"
      
      # 3 blocks from diner (A, B) to gallery (G, H)
      "dist((A, B), (G, H)) = 3"
      
      # 8 blocks from gallery (G, H) to hotel (X, Y)
      "dist((G, H), (X, Y)) = 8"
      
      # eliminate some duplication
      "min(A, C, E, G, X) = 0"
      "min(B, D, F, H, Y) = 0"
      
      # answer is the distances between:
      #   library (C, D) and museum (E, F)
      #   museum (E, F) and gallery (G, H)
      #   gallery (G, H) and library (C, D)
      --answer="(dist((C, D), (E, F)), dist((E, F), (G, H)), dist((G, H), (C, D)))"
      
      # [optional] tidy up output
      --template="(X, Y) (A, B) (C, D) (E, F) (G, H)"
      --solution=""
      

      Solution: It is 7 blocks from the library to the museum. It is 7 blocks from the museum to the gallery. It is 4 blocks from the gallery to the library.

      Here is a possible layout:

      Reflections and rotations of this layout also provide viable solutions, to give the 8 different layouts found by the program.

      Like

      • Jim Randell's avatar

        Jim Randell 7:00 pm on 7 May 2021 Permalink | Reply

        And here is a standalone Python program that finds the same solution. It runs in 54ms.

        Run: [ @replit ]

        from collections import namedtuple
        from enigma import (irange, multiset, printf)
        
        # x/y coordinates
        P = namedtuple('P', 'x y')
        
        # distance metric between 2 points
        def dist(p, q):
          return abs(p.x - q.x) + abs(p.y - q.y)
        
        # generate positions at a distance d from point p
        def position(d, p):
          for dx in irange(0, d):
            dy = d - dx
            yield P(p.x + dx, p.y + dy)
            yield P(p.x + dx, p.y - dy)
            yield P(p.x - dx, p.y + dy)
            yield P(p.x - dx, p.y - dy)
        
        # check x/y co-ordinates are distinct
        def check(p, *qs):
          return all(p.x != q.x and p.y != q.y for q in qs) 
        
        # record solutions
        r = multiset()
        
        # fix the diner at (0, 0)
        D = P(0, 0)
        
        # the gallery is 3 blocks from the diner
        for G in position(3, D):
          if not check(G, D): continue
        
          # the hotel is 8 blocks from the gallery ...
          for H in position(8, G):
            if not check(H, G, D): continue
            # ... and 9 blocks from the diner
            if not (dist(H, D) == 9): continue
            
            # the museum is 4 blocks from the diner ...
            for M in position(4, D):
              if not check(M, H, G, D): continue
              # ... and 7 blocks from the hotel
              if not (dist(M, H) == 7): continue
        
              # the libray is 5 blocks from the diner ...
              for L in position(5, D):
                if not check(L, M, H, G, D): continue
                # ... and 6 blocks from the hotel
                if not (dist(L, H) == 6): continue
        
                # calculate the required distances
                ds = (dist(L, M), dist(M, G), dist(G, L))
        
                printf("[ds={ds}; D={D} G={G} H={H} M={M} L={L}]")
                r.add(ds)
        
        # output solution
        for (ds, n) in r.most_common():
          printf("ds = {ds} [{n} solutions]")
        

        The program fixes D at (0, 0) and then looks for possible positions for G at a distance of 3. There are 8 viable positions (think knight moves), and each layout corresponds to one of these positions. So we can eliminate multiple solutions by only considering just one viable position for G.

        Like

    • Tony Brooke-Taylor's avatar

      Tony Brooke-Taylor 1:26 pm on 9 May 2021 Permalink | Reply

      I saved a bit of time by constraining the diner to be in one quadrant relative to the hotel, and the other three destinations to be in either that quadrant or the two adjacent. This still gives two solutions by reflection in y=x but of course all solutions that meet the puzzle’s conditions are identical.

      Like

  • Unknown's avatar

    Jim Randell 9:51 am on 6 May 2021 Permalink | Reply
    Tags:   

    Teaser 2791: Four-square family 

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

    My four sons are all under 20 and just one of them is a teenager. Their ages (or, more precisely, the squares of their ages) have some remarkable properties. Firstly, two years ago the square of one of their ages equalled the sum of the squares of the other three ages. Secondly, this year the sum of the squares of two of their ages equals the sum of the squares of the other two ages.

    What, in increasing order, are their ages?

    [teaser2791]

     
    • Jim Randell's avatar

      Jim Randell 9:51 am on 6 May 2021 Permalink | Reply

      The following Python program runs in 48ms.

      Run: [ @replit ]

      from enigma import (irange, subsets, is_square, sq, printf)
      
      # choose the age of the teenager
      for d in irange(13, 19):
        # and the ages of the 2 youngests non-teenagers
        for (a, b) in subsets(irange(2, 12), size=2):
          # calculate c: a^2 + d^2 = b^2 + c^2
          c = is_square(sq(a) + sq(d) - sq(b))
          if c is None or c < b or c > 12: continue
          # check the ages 2 years ago: (a-2)^2 + (b-2)^2 + (c-2)^2 = (d-2)^2
          if not (sq(a - 2) + sq(b - 2) + sq(c - 2) == sq(d - 2)): continue
          # output solution
          printf("a={a} b={b} c={c} d={d}")
      

      Solution: Their current ages are: 4, 8, 11, 13.

      This year we have: 4² + 13² = 185 = 8² + 11².

      Two years ago the ages were: 2, 6, 9, 11, and 2² + 6² + 9² = 121 = 11².

      Like

  • Unknown's avatar

    Jim Randell 8:22 am on 4 May 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 752: Traffic cop 

    From The Sunday Times, 14th December 1975 [link]

    Some years ago I was lecturing to a group of policeman and I set them a traffic problem which they found difficult. Here it is:

    A column of vehicles 10 miles long drives 24 miles at a constant speed and then halts. A policeman on motor-cycle starts at the back of the column as it moves off, he rides to the front, turns round immediately and rides to the back of the column arriving at the moment the vehicles halt.

    Assuming that his speed has been constant throughout: how far has he ridden?

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

    [teaser752]

     
    • Jim Randell's avatar

      Jim Randell 8:23 am on 4 May 2021 Permalink | Reply

      The front of the convoy starts at a distance of 24 miles from the finish. And ends at distance zero.

      The back of the convoy starts at a distance of 34 miles, and ends at a distance of 10 miles.

      If we consider that the motorbike also starts at a distance of 34 miles, goes towards the finish until a distance x miles away (0 < x < 24), and then turns around and continues until it reaches the finish point of the end of the convoy. The distance travelled by the motorbike is:

      (34 − x) + (10 − x) = 44 − 2x

      And in the time taken for the motor bike to travel to the turnaround point the front of the convoy has travelled a distance: (24 − x) miles.

      And after the motorbike has turned around the convoy travels the remaining distance x miles.

      The speeds are constant, so the ratio of the convoy : motorbike distances must be the same in the two parts:

      (24 − x) : (34 − x) = x : (10 − x)

      (24 − x)(10 − x) = x(34 − x)
      240 − 34x + x² = 34x − x²
      x² − 34x + 120 = 0
      (x − 4)(x − 30) = 0

      So the turnaround point was 4 miles before the finish, and:

      Solution: The motorbike travelled a total distance of 36 miles.


      The two parts of the journey are:

      Before turnaround: Convoy travels from 24 miles away to 4 miles away; distance = 20 miles. Motorbike travels from 34 miles away to 4 miles away; distance = 30 miles.

      After turnaround: Convoy travels from 4 miles away to finish; distance = 4 miles. Motorbike travels from 4 miles away to 10 miles away; distance = 6 miles.

      And we see that the motorbike is travelling at 1.5× the speed of the convoy.

      Like

    • John Crabtree's avatar

      John Crabtree 10:40 pm on 4 May 2021 Permalink | Reply

      Let m be the motor-cycle speed and c be the convoy speed.
      The distance travelled by the policeman = d = 24m/c
      Considering the travel times, 10/(m – c) + 10/(m + c) = 24/c
      20mc = 24(m^2 – c^2)
      d^2 – 20d – 24^2 = 0
      d = 10 +/- 26 = 36 miles.

      Like

  • Unknown's avatar

    Jim Randell 7:34 am on 2 May 2021 Permalink | Reply
    Tags: by: C. R. J. Fleming,   

    Brain-Teaser 32: [Square farm] 

    From The Sunday Times, 29th October 1961 [link]

    A, B, & C are sitting in a railway carriage, and A, an Australian, is talking to B about his farm in Australia.

    “It is square”, he says, and tells B the length of its sides: a whole number of miles; “but I am thinking of selling a rectangular part of it whose sides are in length a whole plural number of miles”. He tells B the area of the rectangle: an odd number of square miles.

    B says: “If I knew whether its breadth was less than two-thirds of its length, I could tell you its dimensions”. A tells him that its breadth is more than two-thirds of its length.

    C, a stranger, who had been listening to this conversation, but missed the area of the rectangle, nevertheless correctly deduced its dimensions, although, he reflected, had A‘s farm had sides one mile longer he could not have done so.

    What are the lengths of the sides of  A‘s farm, and of the rectangular part to be sold?

    This puzzle was originally published with no title.

    [teaser32]

     
    • Jim Randell's avatar

      Jim Randell 7:34 am on 2 May 2021 Permalink | Reply

      I think this puzzle is flawed.

      B knows the size of A’s farm (which gives the maximum dimension of the rectangle – assuming the rectangle is aligned with the square), and also the area of the rectangle (which were are told is odd).

      And he must be able to narrow down the options (= non-trivial divisor pairs of the odd area, subject to the maximum dimension) to two possible values, which can then be distinguished by knowing if the breadth of the rectangle is less than 2/3 the length.

      So, for instance an area of 63 has two options:

      63 = 3 × 21 = 7 × 9

      So, if the size of the farm is at least 21 × 21, and B is told an area of 63, this is a candidate solution. (Or 17 × 17 if the rectangle does not have to be aligned with the square).

      If the rectangle is allowed to be a square the next candidate solution is when the size of the farm is at least 25 × 25, and B is told an area of 225:

      225 = 9 × 25 = 15 × 15.

      At 27 × 27, an area of 81 becomes viable:

      81 = 9 × 9 = 3 × 27

      When we get to 33 × 33 we get two further possible solutions:

      99 = 3 × 33 = 9 × 11
      165 = 5 × 33 = 11 × 15

      And so on.

      C knows the size of the farm, but did not hear the area of the rectangle, and so presumably also doesn’t know that the area is odd.

      But even for the minimum possible area of 21 × 21 there are 16 possible areas that have 2 decompositions into viable rectangles, and C has no way to choose between them.

      So let’s suppose that C does know that the area of the rectangle is odd. (Maybe B commented: “Ah, so the area of the rectangle is odd”, and C heard this, but not the actual value of the area).

      For a farm of size 21 × 21 to 24 × 24 there is only one possible area (= 63), and as we know the breadth of the rectangle is more than 2/3 the length, this means it must be 7 × 9. So if C had heard any of these farm areas, they could deduce the area of the rectangle.

      But when we get to 25 × 25 the possibility of a rectangle of area 225 appears (giving a rectangle of 15 × 15, where the breadth is more than 2/3 the length), so C cannot determine which rectangle it is.

      So the solution would seem to be:

      Solution: A’s farm is 24 × 24 miles. The rectangular area is 7 × 9 miles.

      However the published solution is that A’s farm is 25 × 25 miles.

      I suppose the perimeter of the square could be required to be unaffected, but that is not mentioned in the puzzle text. (And if the rectangle doesn’t have to be aligned with the sides of the square we can easily fit a 9×25 rectangle entirely within a 25×25 square, but not within a 24×24 square, which makes 24×24 a more likely answer).


      This Python program runs in 52ms.

      Run: [ @replit ]

      from enigma import (irange, inf, subsets, group, multiply, filter2, unpack, printf)
      
      # solve for an n mile x n mile area
      def solve(n):
        # group potential sub-rectangles by area
        d = group(subsets(irange(2, n), size=2, select="R"), by=multiply)
      
        for k in sorted(d.keys()):
          # k must be odd
          if k % 2 != 1: continue
          vs = d[k]
          # there must be 2 choices for the area
          if len(vs) != 2: continue
          # that are distinquished by known in a < (2/3) b
          (lt, ge) = filter2(unpack(lambda a, b: 3 * a < 2 * b), vs)
          if not (len(lt) == 1 and len(ge) == 1): continue
          printf("[n={n}] {k} -> {vs} -> {lt} + {ge}")
          yield (k, lt[0], ge[0])
      
      ps = list()
      for n in irange(1, inf):
        rs = list(solve(n))
        if len(rs) > 1:
          printf("farm = {n1} x {n1}", n1=n - 1)
          if len(ps) == 1:
            (k, _, (a, b)) = ps[0]
            printf("rectangle = {a} x {b} [area = {k}]")
          break
        ps = rs
      

      Like

  • Unknown's avatar

    Jim Randell 3:43 pm on 30 April 2021 Permalink | Reply
    Tags:   

    Teaser 3058: Total resistance 

    From The Sunday Times, 2nd May 2021 [link] [link]

    A physics teacher taught the class that resistors connected in series have a total resistance that is the sum of their resistances while resistors connected in parallel have a total resistance that is the reciprocal of the sum of their reciprocal resistances, as shown in the diagrams. Each pupil was told to take five 35-ohm resistors and combine all five into a network [using a combination of series and/or parallel connections]. Each pupil then had to calculate theoretically and check experimentally the resistance of his or her network. Every network had a different resistance and the number of different resistances was the maximum possible. The total sum of these resistances was a whole number.

    How many pupils were there in the class and what was the sum of the resistances?

    [teaser3058]

     
    • Jim Randell's avatar

      Jim Randell 4:13 pm on 30 April 2021 Permalink | Reply

      We can make a recursive function to calculate the set of resistances for a collection of k resistors, combined into a circuit using only series and parallel connections (and not “bridge”-type circuits).

      Any permissible circuit is constructed from the connection of two smaller circuits (i.e. circuits using fewer resistors) either in series or in parallel. And we don’t need to keep track of the layout of the smaller circuits, only their resistance values. (Which neatly eliminates the need to remove duplicate circuits). And we can cache these values to avoid recomputing them repeatedly.

      This Python program collects the resistance values of smaller circuits (starting with a single resistor) and combines them to calculate the resistance values of larger circuits. (A unit resistance value is used, which can be multiplied up for circuits consisting of resistors of the same value). It runs in 50ms.

      Run: [ @replit ]

      from enigma import (Rational, irange, cproduct, cached, arg, printf)
      
      Q = Rational()  # implementation of rationals
      
      # series and parallel combinations
      S = lambda x, y: x + y
      P = lambda x, y: Q(1, Q(1, x) + Q(1, y)) # = Q(x * y, x + y)
      
      # generate arrangements of k unit resistors
      @cached
      def arrange(k):
        # if there is only 1 resistor
        if k == 1:
          # there is only 1 arrangement
          return {1}
        else:
          # otherwise split the resistors
          s = set()
          for i in irange(1, k // 2):
            # consider the sub-arrangements
            for (x, y) in cproduct([arrange(i), arrange(k - i)]):
              # and combine them in series and parallel
              s.update({S(x, y), P(x, y)})
          return s
      
      # calculate the different resistances of 5 resistors
      k = arg(5, 0, int)
      R = arg(35, 1, int)
      s = arrange(k)
      printf("[k={k} R={R}] {n} different values; total = {t}", n=len(s), t=sum(s) * R)
      

      Solution: There were 22 pupils in the class. The total sum of the constructed resistance values was 1052 ohms.


      See also: OEIS A048211 [ @oeis ]. I have used my program to verify the sequence up to k = 21, but beyond that requires more memory than my machine has.

      The sequence OEIS A000084 [ @oeis ] gives the total number of different series/parallel circuit configurations that can be constructed, but some of them may have the same resistance value.

      For example the following combinations of 4 resistors give the same value:

      (R + R) | (R + R) = R
      (R | R) + (R | R) = R

      For k = 5 there are 24 different circuits that can be constructed, but only 22 different resistance values.

      The sequence OEIS A337516 [ @oeis ] also includes “bridge”-type circuits (the first of which appears at k = 5) and “fork”-type circuits (which appear at k = 7).

      Like

    • Tony Brooke-Taylor's avatar

      Tony Brooke-Taylor 7:27 pm on 30 April 2021 Permalink | Reply

      Jim, I tried to test my manual solution using your code and can’t reconcile your result for k=3. Have you included cases where there can be 1 resistor in parallel?

      Like

      • Tony Brooke-Taylor's avatar

        Tony Brooke-Taylor 7:43 pm on 30 April 2021 Permalink | Reply

        Sorry, I knew I should have thought a bit harder. Of course I realised my error as soon as I submitted my reply…

        Like

      • Jim Randell's avatar

        Jim Randell 7:53 pm on 30 April 2021 Permalink | Reply

        @Tony:

        With 1 resistor we have 1 way: {R}

        With 2 resistors they can be in series or parallel, 2 ways: {R+R, R|R } = { 2R, (1/2)R }

        With 3 resistors we can combine a group of 1 resistors with a group of two resistors in 4 ways: {R+(R + R), R+(R|R), R|(R + R), R|(R|R) } = { 3R, (2/3)R, (1/3)R, (3/2)R }.

        It is interesting to note that if we can make a resistance of r with a circuit of k unit resistors, then we can also make a resistance of 1/r (by interchanging series and parallel connections).

        Like

    • Alex.T.Sutherland's avatar

      Alex.T.Sutherland 4:57 pm on 2 May 2021 Permalink | Reply

      if bridging is allowed then my answer is 23 pupils and total resistance value = 1087.
      if bridging is not allowed 22 pupils = 1052.
      (the bridge network is 35 ohms)

      Like

      • Jim Randell's avatar

        Jim Randell 5:24 pm on 2 May 2021 Permalink | Reply

        Thanks for your comment.

        I think this puzzle is only concerned with networks that are composed from series and parallel connections (as that is all the children are told about, so they wouldn’t know how to calculate the theoretical resistance of other types of circuits). I have now clarified the puzzle text on this point.

        (I try not to directly reveal the solution to prize puzzles until after it is closed to entries).

        Like

    • Hugh Casement's avatar

      Hugh Casement 1:31 pm on 9 May 2021 Permalink | Reply

      >>
      For k = 5 there are 24 different circuits that can be constructed,
      but only 22 different resistance values.
      <<

      2R and ½R are each duplicated, where R = 35 ohms in this case.

      With four resistors it's just R that's duplicated, as Jim said in his original post on 30 Apr.
      Add an extra resistor to each of those circuits, once in series and once in parallel,
      and we have the duplicates for k = 5.

      Sorry if I'm stating the obvious!

      Like

  • Unknown's avatar

    Jim Randell 8:41 am on 29 April 2021 Permalink | Reply
    Tags:   

    Teaser 2788: Red-letter days 

    From The Sunday Times, 28th February 2016 [link] [link]

    The months of my 2016 calendar are headed M, T, W, Th, F, Sa, Su, with the dates 1, 2, 3… in a grid of squares underneath. I have shaded all the days on which I have meetings planned – all of them being on weekdays. For example, in February the days 1, 2, 3, 4, 8 and 9 are shaded: these shaded squares form a connected piece and the product of the numbers is a perfect cube. The same is true of the shaded squares in another month – and in fact it’s the largest possible such cube in the calendar. My last meeting in that month is on my aunt’s birthday.

    What is her birthday?

    [teaser2788]

     
    • Jim Randell's avatar

      Jim Randell 8:42 am on 29 April 2021 Permalink | Reply

      This Python program examines each month to find regions that give the maximum possible cube.

      For each month the grid is filled out, and then we calculate the total number of each possible prime factor available, and any date that contributes a prime factor that occurs fewer than 3 times is removed. We then examine subsets of the remaining numbers that have a product which is a cube, and form a connected region.

      It runs in 421ms.

      Run: [ @replit ]

      from datetime import (date, timedelta)
      from enigma import (grid_adjacency, irange, factor, multiset, call, subsets, multiply, is_cube, union, Accumulator, printf)
      
      # enable internal caching for is_cube
      is_cube.cache_enabled = 1
      
      # prime factors of numbers from 1 to 31
      factors = dict((n, factor(n)) for n in irange(1, 31))
      
      # the adjacency matrix for a 5x5 grid
      adj = grid_adjacency(5, 5)
      
      # is a region of the grid connected?
      def is_connected(js):
        # start with one of the cells, and try to connect the rest in
        rs = set(js[1:])
        js = js[:1]
        while js and rs:
          js = union(adj[i] for i in js).intersection(rs)
          rs.difference_update(js)
        return not rs
      
      # 1 day increment
      day = timedelta(days=1)
      
      # find regions with maximal product
      r = Accumulator(fn=max, collect=1)
      
      # consider possible months (although we could skip Feb)
      seen = dict()
      for m in irange(1, 12):
      
        # fill out the grid for a particular month
        grid = dict()
        (d, i) = (date(2016, m, 1), None)
        while d.month == m:
          j = d.weekday()
          if j < 5:
            i = (j if i is None else i + 1)
            grid[i] = d.day
          d += day
      
        # remove dates that cannot be used
        while 1:
          # accumulate all the prime factors of numbers in the grid
          fs = call(multiset.from_seq, (factors[n] for n in grid.values()))
          # remove any numbers with a factor with a count < 3
          ks = list(k for (k, n) in grid.items() if any(fs[f] < 3 for f in factors[n]))
          if not ks: break
          for k in ks: del grid[k]
      
        # have we already done this month
        k = tuple(sorted(grid.items()))
        if k in seen:
          printf("[month {m} duplicates month {x}]", x=seen[k])
          continue
        seen[k] = m
      
        printf("[month {m}: {grid}", grid=sorted(grid.values()))
      
        # find subsets whose product is a cube
        for ks in subsets(grid.keys(), min_size=1):
          p = multiply(grid[k] for k in ks)
          if not (is_cube(p) and is_connected(ks)): continue
          vs = sorted(grid[k] for k in ks)
          r.accumulate_data(p, (m, vs))
          printf("-> {vs} -> {p}^3", p=is_cube(p))
      
      printf("max product = {x}^3", x=is_cube(r.value))
      for (m, vs) in r.data:
        printf("month {m} -> {vs}")
      

      Solution: Her birthday is 27th June.

      Which is a Monday in 2016.

      The largest cube achievable is 15120³ = 3456649728000.

      It occurs in June using dates (1), 3, 6, 7, 8, 9, 10, 14, 15, 16, 20, 21, 27. (Using 1 is optional).

      The maximal cubes found for each month are:

      Jan: 2520³ = 16003008000; (1), 4, 5, 6, 7, 8, 14, 15, 20, 21, 27
      Feb: 120³ = 1728000; 1, 2, 3, 4, 5, 8, 10, 12, 15
      Mar: 168³ = 4741632; (1), 2, 7, 8, 9, 14, 16, 21
      Apr: = Jan
      May: 6³ = 216; 2, 3, 4, 9
      Jun: 15120³ = 3456649728000; (1), 3, 6, 7, 8, 9, 10, 14, 15, 16, 20, 21, 27
      Jul: = Jan
      Aug: 120³ = 1728000; 1, 2, 3, 4, 5, 8, 10, 12, 15 [= Feb]
      Sep: 7560³ = 432081216000; (1), 5, 6, 7, 8, 9, 12, 14, 15, 20, 21, 27
      Oct: 3³ = 27; 27
      Nov: = Mar
      Dec: = Sep

      The following diagram shows the regions that give the maximum cube for each month:

      (1 is optional, except where it is required to keep the region connected, i.e. Aug, Feb).

      Like

    • Frits's avatar

      Frits 6:49 pm on 30 April 2021 Permalink | Reply

      Based on Jim’s program with the idea to find the maximum product as soon as possible.

      from datetime import date, timedelta
      from itertools import combinations
      from enigma import multiply, is_cube
      
      # exclude days where a prime factor can not occur 3 times per month
      ex_days = [11, 13, 17, 19, 22, 23, 26, 29, 31]
      # also exclude days on small islands
      ex_days += [18, 24, 25, 30]
      
      zeroes = [[0 for x in range(5)] for y in range(5)] 
      
      # calculate minimal number of <s> entries to exceed <mprod>  
      def min_entries(s, lim):
        p = 1  
        for i, v in enumerate(s):
          p *= v
          if p > lim: break
        return len(s) - i
      
      # chain as many cells of sequence <s> as possible
      def chain_cells(i, j, s, done):
        if i < 0 or i > 4 or j < 0 or j > 4: return []
       
        if done[i][j] == 1: return []
        
        ind = i * 5 + j 
       
        if ind not in s: return []
        
        chain = [ind]
        done[i][j] = 1
        
        # check adjacent cells
        chain += chain_cells(i - 1, j, s, done)
        chain += chain_cells(i + 1, j, s, done)
        chain += chain_cells(i, j - 1, s, done)
        chain += chain_cells(i, j + 1, s, done)
        
        return chain
      
      # 1 day increment
      day = timedelta(days=1)
       
      (mprod, mentries, bday) = (0, 1, "")
      
      # consider possible months (although we could skip Feb)
      seen = dict()
      grids = dict()
      
      # build and store grids
      for m in range(1, 13):
        # fill out the grid for a particular month
        grid = dict()
        (d, i) = (date(2016, m, 1), None)
        while d.month == m:
          j = d.weekday()
          if j < 5:
            d1 = d.day
            i = (j if i is None else i + 1)
            if d1 not in ex_days:
              grid[i] = d1
          d += day
        grids[m] = grid
        
      # start with the month with the most entries  
      for m in sorted(grids, key=lambda m: len(grids[m]), reverse=True): 
        grid = grids[m]
        # have we already done this month
        k = tuple(sorted(grid.items()))
        if k in seen:
          continue
        seen[k] = m
       
        allprod = multiply(grid[k] for k in grid)
        
        if mprod:
          d1 = allprod / mprod
          # not enough numbers in grid to exceed mprod
          if d1 < 1:
            continue
          # calculate minimal number of entries to exceed <mprod>  
          mentries = min_entries(grid.values(), d1)
        
        # find subsets whose product is a cube
        for k in range(len(grid), 0, -1):
          if k < mentries: break
          
          for ks in combinations(grid.keys(), k):
            p = multiply(grid[k] for k in ks)
            
            if not(p >= mprod and is_cube(p)): continue
            
            (i, j) = (ks[0] // 5, ks[0] % 5)
            # days have to be connected
            if len(ks) > len(chain_cells(i, j, ks, [x.copy() for x in zeroes])): 
              continue
              
            if p > mprod: 
              mprod = p
              # calculate minimal number of entries to exceed <mprod>  
              mentries = min_entries(grid.values(), allprod / mprod)
              vs = [grid[k] for k in ks]
              bday = str(vs[-1]) + "-" + str(m) + "-2016"
              print(f"month {m}: -> {vs} -> {is_cube(p)}^3")
       
      print(f"max product = {is_cube(mprod)}^3")
      print(f"birthday {bday}")
      

      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