Design a site like this with WordPress.com
Get started

Updates from April, 2022 Toggle Comment Threads | Keyboard Shortcuts

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

    Brain-Teaser 910: The Teaser Club 

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

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

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

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

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

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

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

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

    How many Christmas cards were sent in 1975?

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

    [teaser910]

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

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

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

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

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

      It runs in 55ms.

      Run: [ @replit ]

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

      Solution: 552 Christmas cards were sent in 1975.

      Like

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

    Brain-Teaser 907: Snakes & ladders 

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

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

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

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

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

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

    Which of the lines are snakes?

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 2 (1981, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    It was also included in the book The Sunday Times Book of Brainteasers (1994, edited by Xerxes).

    [teaser914]

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

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

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

      Run: [ @replit ]

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

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

      And the rest are ladders.

      So play proceeds:

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

      Like

  • Jim Randell 9:01 am on 2 November 2021 Permalink | Reply
    Tags: by: W H St John-Brooks   

    Brain-Teaser 914: Advancing numeracy 

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

    My mathematics class is much more reliable than formerly. I can now be certain that each pupil will always follow a completely true statement by a false one, and vice versa.

    It is clear that some difficulties still arise, but when I asked three of them to select one five-figure number between them, and to make two statements each about it, it was possible to deduce the number they had in mind.

    They used a, b, c, d and e to indicate the positions of the successive digits, which were not necessarily all different.

    Anne said:
    1. The sum of the number and 969 Is divisible by 714.
    2. The sum of c and e is one third of the sum of the five
    digits.

    Bill said:
    1. The sum of the number and 798 is divisible by 693.
    2. The sum of the number and 987 is divisible by 658.

    Carol said:
    1. The sum of b and d equals three times the first digit.
    2. The sum of the number and 988 is divisible by 741.

    What was the number?

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

    [teaser914]

     
    • Jim Randell 9:02 am on 2 November 2021 Permalink | Reply

      This Python program runs in 60ms.

      Run: [ @replit ]

      from enigma import irange, nsplit, printf
      
      # consider the 5-digit number
      for n in irange(10000, 99999):
      
        # consider Bill's statements (can't both have the same truth value)
        if ((n + 798) % 693 == 0) == ((n + 987) % 658 == 0): continue
      
        # and Anne's
        (a, b, c, d, e) = nsplit(n)
        if ((n + 969) % 714 == 0) == (3 * (c + e) == a + b + c + d + e): continue
      
        # and Carol's
        if (b + d == 3 * a) == ((n + 988) % 741 == 0): continue
      
        printf("{n}")
      

      Solution: The number was: 32571.

      Anne’s statements are: False, True.

      Bill’s statements are: False, True.

      Carol’s statements are: True, False.

      Liked by 1 person

      • Jim Randell 10:27 am on 3 November 2021 Permalink | Reply

        Or, checking fewer candidates:

        from enigma import irange, nsplit, printf
        
        # exactly one of Bill's statements must be true
        b1 = set(irange(10290, 99999, step=693))
        b2 = set(irange(10199, 99999, step=658))
        for n in b1.symmetric_difference(b2):
          (a, b, c, d, e) = nsplit(n)
          if (
            # Anne
            ((n + 969) % 714 == 0) != (3 * (c + e) == a + b + c + d + e) and
            # Carol
            (b + d == 3 * a) != ((n + 988) % 741 == 0)
          ):
            printf("{n}")
        

        Like

    • GeoffR 8:52 am on 13 January 2022 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      % the five digits - assuming no digit is zero
      var 1..9:a; var 1..9:b; var 1..9:c; var 1..9:d;  var 1..9:e;
      
      % the five digit number
      var 10000..99999:num = 10000*a + 1000*b + 100*c + 10*d + e;
      
      % Anne - one of two statements is true
      constraint ((num + 969) mod 714 == 0) 
      \/ (3 *(c + e) = (a  + b + c + d + e));
      
      % Bill - one of two statements is true
      constraint ((num + 798) mod 693 == 0) 
      \/ ((num + 987) mod 658 == 0);
      
      % Carol - one of two statements is true
      constraint ((b + d) == 3 * a) 
      \/ ((num  + 988) mod 741 == 0);
      
      solve satisfy;
      output ["Number is " ++  show(num) ];
      
      % Number is 32571
      % ----------
      % ==========
      
      
      

      Like

      • Jim Randell 12:51 pm on 13 January 2022 Permalink | Reply

        @GeoffR: This model checks that at least one of the two statements for A, B, C is true. Rather than exactly one.

        But changing \/ to xor (or !=) will do the job.

        Like

    • GeoffR 2:31 pm on 13 January 2022 Permalink | Reply

      @ Jim: Ok, I see what you mean. This programme confirms it gets the same answer.

      
      % A Solution in MiniZinc
      include "globals.mzn";
       
      % the five digits - assuming no digit is zero
      var 1..9:a; var 1..9:b; var 1..9:c; var 1..9:d;  var 1..9:e;
       
      % the five digit number
      var 10000..99999:num = 10000*a + 1000*b + 100*c + 10*d + e;
       
      % Anne - one of two statements is true
      constraint ((num + 969) mod 714 == 0) 
      != (3 *(c + e) = (a  + b + c + d + e));
       
      % Bill - one of two statements is true
      constraint ((num + 798) mod 693 == 0) 
      != ((num + 987) mod 658 == 0);
       
      % Carol - one of two statements is true
      constraint ((b + d) == 3 * a) 
      != ((num  + 988) mod 741 == 0);
       
      solve satisfy;
      output ["Number is " ++  show(num) ];
       
      % Number is 32571
      % ----------
      % ==========
      
      

      Like

  • Jim Randell 10:16 am on 28 October 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 905: Prime square 

    From The Sunday Times, 25th November 1979 [link]

    “Here”, said Uncle Henry to the twins, “is a magic square which I’ve started for you”:

    “You must complete it by putting eight different prime numbers in the eight empty squares, so that the [rows], the columns and the diagonals add up to the same total; and it must be the smallest possible total under the conditions.”

    There followed half an hour of comparative peace… after which the twins could bear it no longer.

    “Oh. Uncle”, complained Betty, “It looks so easy and yet it’s much too difficult”. And Brian fervently agreed.

    “All right”, said Uncle Henry, “I’ll tell you a couple more things: there is one such magic square where the number in the middle square is the average of the two numbers directly above and below it; the third largest number is not in the right-hand column; and each square contains one or two digits”.

    After a further ten minutes, the twins managed to produce the right solution.

    Can you complete the magic square?

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    It was also included in the book The Sunday Times Book of Brainteasers (1994, edited by Xerxes).

    [teaser905]

     
    • Jim Randell 10:17 am on 28 October 2021 Permalink | Reply

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

      The following run file executes in 64ms.

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      #  AB  CD  EF
      #  GH  IJ  KL
      #  MN  01  PQ
      
      SubstitutedExpression
      
      --distinct=""
      --invalid=""
      
      # missing numbers are different 1 or 2 digit primes
      "is_prime(AB)"
      "is_prime(CD)"
      "is_prime(EF)"
      "is_prime(GH)"
      "is_prime(IJ)"
      "is_prime(KL)"
      "is_prime(MN)"
      "is_prime(PQ)"
      "all_different(AB, CD, EF, GH, IJ, KL, MN, PQ)"
      
      # in an additive magic square the magic constant is 3 times the centre value (= 3 * IJ)
      "2 * IJ - 1 = CD"
      "2 * IJ - AB = PQ"
      "2 * IJ - EF = MN"
      "2 * IJ - GH = KL"
      "3 * IJ - AB - CD = EF"
      "3 * IJ - MN - 1 = PQ"
      "3 * IJ - AB - GH = MN"
      "3 * IJ - EF - KL = PQ"
      
      # third largest number is _not_ in the RH column
      "ordered(1, AB, CD, EF, GH, IJ, KL, MN, PQ)[-3] not in {EF, KL, PQ}"
      
      --template="(AB CD EF) (GH IJ KL) (MN 01 PQ)"
      --solution=""
      

      Solution: Here is a diagram of the completed square:

      Like

      • Mark Valentine 1:21 pm on 28 October 2021 Permalink | Reply

        Third largest number can’t be in right-hand column. Need to flip it.

        Like

        • Mark Valentine 1:23 pm on 28 October 2021 Permalink | Reply

          Apologies. Misread it. Yours is correct.

          Like

      • Frits 3:41 pm on 28 October 2021 Permalink | Reply

        Using “3 * IJ – AB – MN = GH” instead of “3 * IJ – AB – GH = MN” you don’t have to internally loop over G and H.

        Like

      • Jim Randell 12:35 pm on 29 October 2021 Permalink | Reply

        And here is a Python program that can be used to generate magic squares with larger magic constants:

        from enigma import primes, ordered, arg, printf
        
        # the magic square is:
        #
        #  A B C
        #  D E F
        #  G 1 H
        #
        # so the magic constant k = 3E
        
        # generate magic squares
        def generate():
          # consider values for E
          for E in primes.range(3):
            k = 3 * E
            B = k - E - 1
            if B not in primes: continue
        
            # choose a value for A
            for A in primes.range(3, k - E):
              # calculate the remaining values
              H = k - A - E
              if H not in primes: continue
              C = k - A - B
              if C not in primes: continue
              F = k - C - H
              if F not in primes: continue
              G = k - C - E
              if G + 1 + H != k or G not in primes: continue
              D = k - E - F
              if A + D + G != k or D not in primes: continue
              # check conditions
              if len({A, B, C, D, E, F, G, H}) != 8: continue
              ns = ordered(A, B, C, D, E, F, G, 1, H)
              if ns[-3] in {C, F, H}: continue
              # valid layout
              yield (A, B, C, D, E, F, G, H)
        
        N = arg(1, 0, int)
        for (n, (A, B, C, D, E, F, G, H)) in enumerate(generate(), start=1):
          printf("[ {A} {B} {C} | {D} {E} {F} | {G} 1 {H} ] {k}", k=3 * E)
          if n == N: break
        

        Like

    • Hugh Casement 2:47 pm on 28 October 2021 Permalink | Reply

      It’s superfluous information (though perhaps helpful) that the middle column is an arithmetic progression.
      Rather than say “the third largest number is not in the right-hand column” it would have been simpler to tell us that the smallest prime is in the left-hand column (otherwise we find a reflection in the vertical axis).
      Without the 1 we would need at least two 3-digit primes to make a magic square.

      Like

    • GeoffR 4:12 pm on 28 October 2021 Permalink | Reply

      My solution shows that the 3rd highest number must not be in the right hand column is a definite requirement, as shown in the note at the end of the programme output. I initially wrote a programme without this constraint. I am not sure how this constraint would be programmed in MiniZinc.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      %  A  B  C
      %  D  E  F
      %  G  H  I
      
      var 2..97:A; var 2..97:B; var 2..97:C; 
      var 2..97:D; var 2..97:E; var 2..97:F;
      var 2..97:G; var 2..97:I;
      
      int: H == 1;
      constraint all_different([A, B, C, D, E, F, G, H, I]);
      
      predicate is_prime(var int: x) = 
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) ((i < x) -> (x mod i > 0));
      
      % All values of the grid (except H) are primes
      constraint is_prime(A) /\ is_prime(B) /\ is_prime(C)
      /\ is_prime(D) /\ is_prime(E) /\ is_prime(F)
      /\ is_prime(G) /\ is_prime(I);
      
      % All rows, columns and diagonals add to the same total
      constraint A + B + C == D + E + F /\ A + B +  C == G + H + I
      /\  A + B + C == A + D + G /\  A + B + C == B + E + H 
      /\  A + B + C == C + F + I /\  A + B + C == A + E + I
      /\  A + B + C == C + E + G;
      
      % the middle square is the average of the two numbers directly above and below it
      constraint 2 * E == B + H \/ 2 * D == A + G \/ 2 * F == C + I;
      
      %  the smallest possible total
      solve minimize(A + B + C);
      
      output [ "[A,B,C,D,E,F,G,H,I] = " ++ show([A,B,C,D,E,F,G,H,I] ) ];
      
      % [A, B, C, D, E, F, G, H, I] = [31, 73, 7, 13, 37, 61, 67, 1, 43]
      % ----------
      % ==========
      % Analysis of this solution
      % -------------------------
      % the third highest number (61) must not be in the third column
      % it is moved to the left hand column by transposing left and right columns
      % 31  73  7   =>   7  73  31
      % 13  37  61  =>  61  37  13
      % 67   1  43  =>  43   1  67
      
      
      
      

      Like

      • Frits 10:28 am on 29 October 2021 Permalink | Reply

        @GeoffR, you can declare an array, fill it with same elements as the original array and add an “increasing” constraint.

          
        % A Solution in MiniZinc
        include "globals.mzn";
         
        %  A  B  C
        %  D  E  F
        %  G  H  I
         
        var 2..97:A; var 2..97:B; var 2..97:C; 
        var 2..97:D; var 2..97:E; var 2..97:F;
        var 2..97:G; var 2..97:I;
         
        int: H == 1;
        constraint all_different([A, B, C, D, E, F, G, H, I]);
        
        array[1..9] of var 1..97: nbrs = [A, B, C, D, E, F, G, H, I];
        array[1..9] of var 1..97: sorted;
        
        % make sure both arrays contain same elements
        constraint forall(X in nbrs)(
                      exists(i in 1..9) ( X = sorted[i])
        );
        
        % make sure array "sorted" is sorted
        constraint increasing(sorted);
         
        predicate is_prime(var int: x) = x > 1 /\ 
        forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) ((i < x) -> (x mod i > 0));
         
        % All values of the grid (except H) are primes
        constraint is_prime(A) /\ is_prime(B) /\ is_prime(C)
        /\ is_prime(D) /\ is_prime(E) /\ is_prime(F)
        /\ is_prime(G) /\ is_prime(I);
         
        % All rows, columns and diagonals add to the same total
        constraint A + B + C == D + E + F /\ A + B + C == G + H + I
        /\  A + B + C == A + D + G /\  A + B + C == B + E + H 
        /\  A + B + C == C + F + I /\  A + B + C == A + E + I
        /\  A + B + C == C + E + G;
         
        % the middle square is the average of the two numbers
        % directly above and below it
        constraint 2 * E == B + H;
        
        % third largest number is not in the RH column
        constraint C != sorted[7] /\ F != sorted[7] /\ I != sorted[7];
         
        %  the smallest possible total
        solve minimize(A + B + C);
         
        output [show([A,B,C]) ++ "\n" ++ show([D,E,F]) ++ "\n" ++ show([G, H, I])];
        

        Like

    • GeoffR 11:00 am on 29 October 2021 Permalink | Reply

      @Frits:

      Yes, that is a neat solution to ensure that the third largest number is not in the right-hand column.

      Like

  • Jim Randell 9:05 am on 29 March 2021 Permalink | Reply
    Tags: by: L. J. Upton   

    Brainteaser 1040: An uncommon number 

    From The Sunday Times, 4th July 1982 [link]

    Your problem this week is to find an unusual nine-digit number. It comprises the digits from 1 to 9, in some order, each used once and only once.

    The number formed by the first digit (reading from the left) is exactly divisible by 1 (which doesn’t tell you a lot!), the number formed by the first two digits is exactly divisible by 2, that formed by the first three digits is exactly divisible by 3, and so on, which the number formed by the first eight digits being divisible by 8, and with the complete number of nine digits being divisible by 9.

    It is perhaps surprising that such a number exists, and even more surprising that is should be unique.

    What is the number?

    This puzzle was included in the book The Sunday Times Book of Brainteasers (1994, edited by Xerxes).

    [teaser1040]

     
    • Jim Randell 9:06 am on 29 March 2021 Permalink | Reply

      This puzzle has also appeared recently as Puzzle #102, Teaser 3053.

      See my comment on Enigmatic Code for the solution.


      Here are the results for an n-digit (decimal) number, consisting of some arrangement of the digits 1..n, such that the leftmost k digits are divisible by k, for k = 1..n:

      [1] = 1
      [1..2] = 12
      [1..3] = 123; 321
      [1..4] = none
      [1..5] = none
      [1..6] = 123654; 321654
      [1..7] = none
      [1..8] = 38165472
      [1..9] = 381654729
      [1..0] = 3816547290

      And taking the final entry, a 10-digit number in base 10, using all 10 digits, such that the leftmost k digits are divisible by k, for k = 1..10; we can extend this to other bases:

      base 2: 10
      base 4: 1230; 3210
      base 6: 143250; 543210
      base 8: 32541670; 52347610; 56743210
      base 10: 3816547290
      base 12: none
      base 14: 9C3A5476B812D0
      base 16-30: none

      (see: OEIS A11456 [ @oeis ]).

      Like

      • Jim Randell 6:01 pm on 29 March 2021 Permalink | Reply

        And if we drop the requirement that digits cannot be reused, we can see that any left prefix of a polydivisible number [ @wikipedia ] must also be polydivisible.

        This program generates all possible polydivisible numbers in a given base (and with a given set of digits):

        from enigma import irange, int2base, args, printf
        
        ds = args([10], 0, int)
        base = ds.pop(0)
        if not ds: ds = list(irange(base))
        printf("[base = {base}; digits = {ds}]")
        
        (k, ns) = (1, list(ds))
        while ns:
          (k_, ns_) = (k + 1, list())
          
          for n in ns:
            # output current numbers
            printf("{k} -> {n}", n=int2base(n, base=base))
            # can we extend this number?
            if n > 0:
              for d in ds:
                n_ = base * n + d
                if n_ % k_ == 0:
                  ns_.append(n_)
        
          (k, ns) = (k_, ns_)
        

        And we find that the longest base 10 polydivisible number, using the digits 0-9 (although 1 and 9 do not appear), has 25 digits:

        3608528850368400786036725

        In base 16 there are 3 maximal length (39-digit) polydivisible numbers:

        34E4A468166CD8604EC0F8106AB4326098286CF;
        AA44CE207C78FC30003C3CC0D8382E2078D07EF;
        FAE06678C2E884607EB8B4E0B0A0F0603420342

        Like

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