Tagged: by: Peter Harrison Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 8:59 am on 4 October 2023 Permalink | Reply
    Tags: by: Peter Harrison   

    Teaser 2496: [Letter values] 

    From The Sunday Times, 25th July 2010 [link] [link]

    I have chosen 10 different letters of the alphabet before U to represent the digits 0 to 9. I can tell you that 0’s letter is in the word NOUGHT, 1’s letter is in the word ONE, 2’s letter is in TWO, and so on up to 9’s letter being in the word NINE.

    Furthermore, I can write down a particular five-figure number that is divisible by 8, and replacing the digits by their letters I get EIGHT. Similarly, a four-figure number divisible by 9 translates to NINE.

    What number is represented by TEN?

    This puzzle was originally published with no title.

    [teaser2496]

     
    • Jim Randell's avatar

      Jim Randell 9:00 am on 4 October 2023 Permalink | Reply

      We only need to consider the letters A–T, and of these only ten of them appear in the words mentioned. So we can assign the digits 0-9 to the letters EFGHINORST (in some order).

      We can use the [[ SubstitutedExpression ]] solver from the enigma.py library to do this, subject to the necessary conditions.

      The following run file executes in 126ms. (Internal runtime is 949µs).

      Run: [ @replit ]

      #! python3 -m enigma -rr

SubstitutedExpression

"EIGHT % 8 = 0"
"NINE % 9 = 0"

"0 in {N, O, G, H, T}"
"1 in {O, N, E}"
"2 in {T, O}"
"3 in {T, H, R, E}"
"4 in {F, O, R}"
"5 in {F, I, E}"
"6 in {S, I}"
"7 in {S, E, N}"
"8 in {E, I, G, H, T}"
"9 in {N, I, E}"

--answer="TEN"
--template=""

      Solution: TEN = 271.

      The assignment of digits to (bold) letters is:

      0 → (N) O (UGHT)
      1 → (O) N (E)
      2 → T (WO)
      3 → (T) H (REE)
      4 → (FOU) R
      5 → F (IVE)
      6 → S (IX)
      7 → (S) E (V) E (N)
      8 → (EI) G (HT)
      9 → (N) I (NE)

      And:

      EIGHT = 79832 = 8 × 9979
      NINE = 1917 = 9 × 213

      Like

  • Unknown's avatar

    Jim Randell 9:28 am on 6 June 2021 Permalink | Reply
    Tags: by: Peter Harrison   

    Teaser 2000: 2000 down 

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

    Many years ago. I took a thin strip of wood and cut it into four pieces, each a different whole number of centimetres long. I could use those pieces to form the sides of many different quadrilaterals, and of all the choices I made one of the largest area possible. I then mounted the quadrilateral on my study wall. When the magazine started numbering its Brainteasers (now known as Teasers), I did them each week, and on finishing the puzzle I shaded a new patch of area [exactly] one square centimetre within the quadrilateral.

    After today’s auspicious Teaser, I will have shaded the entire quadrilateral [exactly]. So next week I shall make another quadrilateral to cover precisely the next 2000 Teasers. Again its sides will be four different whole numbers of centimetres and its area will be the largest possible with those particular lengths. I shall need a strip of wood at least as long as the one I used last time.

    What are the lengths of the sides of my first quadrilateral?

    [teaser2000]

     
    • Jim Randell's avatar

      Jim Randell 9:29 am on 6 June 2021 Permalink | Reply

      For a quadrilateral with given sides, the maximal area occurs when the quadrilateral is cyclic, and is given by the formula:

      A = (1/4)√((−a + b + c + d)(a − b + c + d)(a + b − c + d)(a + b + c − d))

      (Which is a generalisation of Heron’s Formula, known as Brahmagupta’s formula).

      We are interested in cases where: A = 2000.

      Which means were are interested in when:

      (−a + b + c + d)(a − b + c + d)(a + b − c + d)(a + b + c − d) = 64000000

      And as each of a, b, c, d are integers, so are the terms on the LHS, so we can consider factorisations of the RHS into 4 integer factors, and then solve the resulting 4 equations to give us candidate side lengths.

      The [[ divisor_tuples() ]] function is borrowed from Enigma 1062.

      This Python program runs in 162ms.

      Run: [ @replit ]

      from enigma import divisors_pairs, matrix, as_int, seq_all_different, printf

# find ordered k-tuples that multiply to give n
def divisor_tuples(n, k, s=[]):
  if k == 1:
    if not(s and n < s[-1]):
      yield s + [n]
  else:
    for (a, b) in divisors_pairs(n):
      if not(s and a < s[-1]):
        yield from divisor_tuples(b, k - 1, s + [a])

# find maximal quadrilateral with area A
def solve(A):
  # coefficients of a, b, c, d in the factors
  eqs = [
    (-1, +1, +1, +1),
    (+1, -1, +1, +1),
    (+1, +1, -1, +1),
    (+1, +1, +1, -1),
  ]
  # factorise (4A)^2
  for fs in divisor_tuples(16 * A * A, 4):
    # and solve the equations (for positive integers)
    try:
      ns = list(as_int(x, '+') for x in matrix.linear(eqs, fs))
    except ValueError:
      continue
    else:
      yield sorted(ns)

# collect solutions consisting of different integers
ss = sorted((ns for ns in solve(2000) if seq_all_different(ns)), key=sum)

# output solutions
for ns in ss:
  printf("{ns} -> {t}", t=sum(ns))
  break  # we only need the smallest solution

      Solution: The first quadrilateral has sides of length: 5 cm, 55 cm, 65 cm, 85 cm.

      The minimal perimeter is 210 cm, and the sides are all multiples of 5cm. One possible quadrilateral with these side lengths looks like this:

      This is the collection of side lengths with the smallest perimeter. But the program finds 8 possible collections (ordered by perimeter):

      210: (5, 55, 65, 85)
      240: (20, 40, 70, 110)
      288: (16, 19, 119, 134)
      294: (22, 47, 83, 142)
      308: (26, 29, 104, 149)
      330: (5, 40, 125, 160)
      486: (43, 83, 118, 242)
      504: (2, 124, 127, 251)

      If the setter choose the next smallest perimeter for Teasers 2001 – 4000, the quadrilateral will have sides: 20 cm, 40 cm, 70 cm, 110 cm (perimeter = 240 cm), which are all multiples of 10 cm.

      Like

    • Hugh Casement's avatar

      Hugh Casement 10:01 am on 6 June 2021 Permalink | Reply

      I reckon to have found a near-solution with a shorter perimeter.
      If a = 39, b = 42, c = 47, d = 52, then the perimeter is 180 and the area is about 2000.008 units.
      It takes only a very slight deviation from cyclic to reduce that to 2000.

      Like

      • Jim Randell's avatar

        Jim Randell 10:32 am on 6 June 2021 Permalink | Reply

        For all practical purposes this is a viable answer (and a nicer looking quadrilateral).

        If I’ve calculated correctly you would have to be able to measure and cut the wooden strip to an accuracy of about 2e-14 cm to disallow this. Which I think is about 1/1000000 th the width of an atom.

        Like

    • GeoffR's avatar

      GeoffR 5:38 pm on 6 June 2021 Permalink | Reply

      I tried a brute force solution in MiniZinc, experimenting with the upper bound value of the four sides.

      I found setting an upper bound of 150 produced four out of five of Jim’s smallest perimeter solutions, but missed the perimeter of 294. It did, however, find the same two lowest perimeters of 210 and 240.

      I found the Chuffed Solver was necessary to run it satisfactorily, and it took several seconds to run.

      % A Solution in MiniZinc
include "globals.mzn";

var 1..150:a; var 1..150:b; var 1..150:c; var 1..150:d; 
constraint all_different([a, b, c, d]);

% Using Jim's version of the Brahmagupta formula for maximising the area
constraint (-a + b + c + d) * (a - b + c + d) * (a + b - c + d) 
* (a + b + c - d) == 64000000;

% Minimising the perimeter finds different solutions
solve minimize(a + b + c + d);

output [" Four sides = " ++ show([a, b, c, d]) ++ 
", Perimeter = " ++ show(a + b + c + d)  ];

%  Four sides = [104, 29, 26, 149], Perimeter = 308
%  ----------
%  Four sides = [16, 119, 19, 134], Perimeter = 288
% ----------
%  Four sides = [40, 110, 20, 70], Perimeter = 240
% ----------
%  Four sides = [55, 5, 85, 65], Perimeter = 210  <<< first quadrilateral
% ----------
% ==========

      Like

      • Frits's avatar

        Frits 3:57 pm on 7 June 2021 Permalink | Reply

        Adding the following is a bit faster

        set of int: forbidden = {3, 7, 9};

var 1..999: p1 = -a + b + c + d;
var 1..999: p2 = a - b + c + d;
var 1..999: p3 = a + b - c + d;
var 1..999: p4 = a + b + c - d;

% numbers may not end on 3, 7 or 9
constraint forall( [p1 mod 10 != i | i in forbidden] );
constraint forall( [p2 mod 10 != i | i in forbidden] );
constraint forall( [p3 mod 10 != i | i in forbidden] );
constraint forall( [p4 mod 10 != i | i in forbidden] );

        Also adding the following slows it down again but it does report all 8 solutions (with 1..300 for a,b,c,d) with the Chuffed Solver.

        set of int: forbidden2 = {3, 7};

% numbers may not be multiples of 3 or 7
constraint forall( [p1 mod i != 0 | i in forbidden2] );
constraint forall( [p2 mod i != 0 | i in forbidden2] );
constraint forall( [p3 mod i != 0 | i in forbidden2] );
constraint forall( [p4 mod i != 0 | i in forbidden2] );

        Like

      • Frits's avatar

        Frits 7:38 pm on 9 June 2021 Permalink | Reply 

         
constraint a < b /\ b < c /\ c < d; 

is a lot faster than 

constraint all_different([a, b, c, d]);

        Like

    • GeoffR's avatar

      GeoffR 7:15 am on 8 June 2021 Permalink | Reply

      @Frits: Yes, interesting code enhancements.
      If the UB of a,b,c,d is set to 100, it produces the single smallest answer.

      Like

    • Frits's avatar

      Frits 5:14 pm on 9 June 2021 Permalink | Reply

      Runs a lot faster with PyPy than with Python 3.9.

      T = 64000000

# loop over perimeter (sum of the side lengths)
# as from (4 * sqrt(2000))
for P in range(179, 999999):
  for a in range(1, P // 4 + 1):
    for b in range(a + 1, (P - a) // 3 + 1):
      for c in range(b + 1, (P - a - b) // 2 + 1):
        d = P - (a + b + c)
        p1 = -a + b + c + d
        p2 = a - b + c + d
        p3 = a + b - c + d
        p4 = a + b + c - d
      
        if p1 * p2 * p3 * p4 != T: continue

        print(f"side lengths {a}, {b}, {c}, {d} with perimeter {P}")  
        exit()

      (Modified as per comment below).

      Like

      • Jim Randell's avatar

        Jim Randell 5:22 pm on 9 June 2021 Permalink | Reply

        @Frits: You can start looking for perimeters at [[ intc(4 * sqrt(2000)) ]] = 179, as a square has the minimal perimeter for a given area.

        Like

    • GeoffR's avatar

      GeoffR 8:54 pm on 9 June 2021 Permalink | Reply

      A straight translation of my MiniZinc programme for the single solution.

      
from enigma import Timer
timer = Timer('ST2000', timer='E')
timer.start()

for a in range(1,100):
  for b in range(a+1,100):
    for c in range(b+1,100):
      for d in range(c+1, 100):
        if (-a + b + c + d) * (a - b + c + d) \
           * (a + b - c + d) * (a + b + c - d) == 64000000:
          print(f"4 Sides/Perimeter: {a}, {b}, {c}, {d}, {a+b+c+d}")
          timer.stop()      
          timer.report()
          exit()  

# 4 Sides/Perimeter: 5, 55, 65, 85, 210
# ST2000] total time: 0.4669819s (466.98ms)

      Like

  • Unknown's avatar

    Jim Randell 9:10 am on 29 September 2020 Permalink | Reply
    Tags: by: Peter Harrison   

    Teaser 1904: Neat answer 

    From The Sunday Times, 14th March 1999 [link]

    I have started with a four-figure number with its digits in decreasing order. I have reversed the order of the four digits to give a smaller number. I have subtracted the second from the first to give a four-figure answer, and I have seen that the answer uses the same four digits — very neat!

    Substituting letters for digits, with different letters being consistently used for different digits, my answer was NEAT!

    What, in letters, was the four-figure number I started with?

    This puzzle is included in the book Brainteasers (2002). The puzzle text above is taken from the book.

    [teaser1904]

     
    • Jim Randell's avatar

      Jim Randell 9:19 am on 29 September 2020 Permalink | Reply

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

      The following run file executes in 91ms.

      Run: [ @replit ]

      #! python -m enigma -rr

SubstitutedExpression

"WXYZ - ZYXW = NEAT"
"ordered(N, E, A, T) == (Z, Y, X, W)"

--distinct="WXYZ,NEAT"
--answer="translate({WXYZ}, str({NEAT}), 'NEAT')"

      Solution: The initial 4-figure number is represented by: ANTE.

      So the alphametic sum is: ANTE − ETNA = NEAT.

      And the corresponding digits: 7641 − 1467 = 6174.

      Like

    • Hugh Casement's avatar

      Hugh Casement 1:37 pm on 29 September 2020 Permalink | Reply

      If we had not been told the digits were in decreasing order there would have been three other solutions:
      2961 – 1692 = 1269, 5823 – 3285 = 2538, 9108 – 8019 = 1089.

      Like

      • Finbarr Morley's avatar

        Finbarr Morley 10:58 am on 24 November 2020 Permalink | Reply

        I’m not sure that’s right:
        2961-1692= 1269
        ANTE-ETNA=EATN
        It’s true, but it’s not NEAT!

        Like

        • Jim Randell's avatar

          Jim Randell 8:57 am on 25 November 2020 Permalink | Reply

          The result of the sum is NEAT by definition.

          Without the condition that digits in the number you start with are in descending order, we do indeed get 4 different solutions. Setting the result to NEAT, we find they correspond to four different alphametic expressions:

          9108 − 8019 = 1089 / TNEA − AENT = NEAT
          5823 − 3285 = 2538 / ETNA − ANTE = NEAT
          7641 − 1467 = 6174 / ANTE − ETNA = NEAT
          2961 − 1692 = 1269 / ETAN − NATE = NEAT

          Like

    • GeoffR's avatar

      GeoffR 6:30 pm on 29 September 2020 Permalink | Reply 

      
from itertools import permutations
from enigma import nreverse, nsplit

for p1 in permutations((9, 8, 7, 6, 5, 4, 3, 2, 1, 0), 4):
  W, X, Y, Z = p1
  if W > X > Y > Z:
    WXYZ = 1000 * W + 100 * X + 10 * Y + Z
    ZYXW = nreverse(WXYZ)
    NEAT = WXYZ - ZYXW
    N, E, A, T = nsplit(NEAT)
    # check sets of digits are the same
    if {W, X, Y, Z} == {N, E, A, T}:
      print(f"Sum is {WXYZ} - {ZYXW} = {NEAT}")

# Sum is 7641 - 1467 = 6174

      Like

    • GeoffR's avatar

      GeoffR 8:56 am on 25 November 2020 Permalink | Reply

      I checked Hugh’s assertion, changing my programme to suit, and it looks as though he is correct.
      My revised programme gave the original correct answer and the three extra answers, as suggested by Hugh.
      @Finnbarr:
      If we take NEAT = 1269, then ETAN – NATE = NEAT – (Sum is 2961 – 1692 = 1269)

      
from itertools import permutations
from enigma import nreverse, nsplit
 
for p1 in permutations((9, 8, 7, 6, 5, 4, 3, 2, 1,0), 4):
    W, X, Y, Z = p1
    #if W > X > Y > Z:
    WXYZ = 1000 * W + 100 * X + 10 * Y + Z
    ZYXW = nreverse(WXYZ)
    NEAT = WXYZ - ZYXW
    if NEAT > 1000 and WXYZ > 1000 and ZYXW > 1000:
        N, E, A, T = nsplit(NEAT)
        # check sets of digits are the same
        if {W, X, Y, Z} == {N, E, A, T}:
          print(f"Sum is {WXYZ} - {ZYXW} = {NEAT}")
 
# Sum is 9108 - 8019 = 1089
# Sum is 7641 - 1467 = 6174  << main answer
# Sum is 5823 - 3285 = 2538
# Sum is 2961 - 1692 = 1269

      Like

    • Finbarr Morley's avatar

      Finbarr Morley 9:41 am on 30 November 2020 Permalink | Reply

      A maths student would view this as 4 unknowns (A,N,T, & E) and 4 Equations.
      So it can be uniquely solved with simultaneous equations.

      And there’s a neat ‘trick’ recognising the pairs of letters:

      A E
      E A

      And

      N T
      T N

      The ANSWER is the easy bit:

      ANTE
      7641

      The SOLUTION is as follows:

      Column 4321
       ANTE
     - ETNA
     = NEAT

      From the 1,000’s column 4 we seen that A>E, otherwise the answer would be negative.
      ∴ in the 1’s column, (where E is less than A) E must borrow 1 from the T in the 10’s column:

      Col.   2        1
       T-1   10+E
       N        A
       A        T

      There are 2 scenarios:
      (A) N>T
      (B) N<T

      As before, T in the 10’s column must borrow 1 from the N in the 100’s column.

          4    3     2       1
    A  N-1  10+T-1  10+E             
  - E    T     N       A
  = N    E     A       T

      The equations for each of the 4 columns are:

      (1) 10+E-A = T
      (2) 10+T-1-N = A
      (3) N-1-T = E
      (4) A-E = N

      Rearrange to:

      (1) A-E = 10-T
      (4) A-E = N

      (2) N-T = 9-A
      (3) N-T = E+1

      (1-4) 10-T = N (because they both equal A-E) rearrange to N+T = 10
      (2-3) 9-A = E+1 (because they both equal N-T) rearrange to A+E = 8

      From here either solve by substituting numbers, or with algebra.

      SUBSTITUTION:

      A+E=8 and A>E. So A = 5,6,7 or 8

      A   E     A-E=N     N+T=10
5   3         2       8  N>T
6   2         4       6  N>T
7   1         6       4  *** THIS IS THE ONLY SOLUTION ***
8   0         8	      2 can’t have 2 numbers the same

      ALGERBRA:

                N+T=10             A+E=8
     (2)-(N-T=9-A)      (1)+(A-E=10-T)	
           2T=1+A  			                    2A    =(18-T)
 (x2)      4T=2+(2A)

∴   4T=2+(18-T)   
    5T=20
     T=4
∴    N=6 (N+T=10)
∴    E=1  (N-T=1+E)
∴    A=7  (A+E=8)

      Check assumption (A) N>T TRUE (6>4)

      ANSWER:
      ANTE 7641
      - ETNA – 1467
      = NEAT = 6174

      Like

      • Finbarr Morley's avatar

        Finbarr Morley 9:43 am on 30 November 2020 Permalink | Reply

        Now repeat for Assumption (B) N < T, to see if it is valid.

        Equations are similar but different:

        This time the N in the 100’s column must borrow 1 from the A in the 1000’s column.

           4      3      2      1

  A-1   10+N    T-1   10+E             

-  E      T      N      A

=  N      E      A      T

        The equations for each of the 4 columns are:

        (1) 10+E-A=T (exactly the same as before)

        (2) T-1-N=A

        (3) 10+N-T=E

        (4) A-1-E=N

        Rearrange to:

        (1) A-E = 10-T

        (4) A-E = N+1

        (2) T-N = A+1

        (3) T-N = 10-E

        (1-4) 10-T=N+1 (because they both equal A-E) rearrange to T+N=9

        (2-3) A+1=10-E (because they both equal T-N) rearrange to A+E=9

        From here either solve by substituting numbers, or with algebra.

        SUBSTITUTION:

        A+E=9 and A>E.

        So A = 5,6,7 or 8 or 9

        A   E     A-E=N+1     N+T=9      T-N=10-E
5   4         0         9           no           
6   3         2         7           no
7   2         4         5           no
8   1         6         3           N<T
9   0         8         1           N<T

        There are no valid answers with N<T.

        ALGEBRA:

                  T+N = 9               A+E = 9
      2) +T-N = A+1        1) +(A-E = 10-T)	
         2T   = 10+A           2A   = 19-T
     x2) 4T   = 20+2A

∴   4T = 20+19-T   
    3T = 39
     T = 13

        Since this is not 0 to 9, the assumption (B) N<T is invalid.

        Assumption A is the only valid solution.

        There can be only one – William Shakespeare

        Like

        • Jim Randell's avatar

          Jim Randell 11:55 am on 30 November 2020 Permalink | Reply

          @Finbarr: Thanks for your comments. (And I hope I’ve tidied them up OK).

          Although I think we can take a bit of a shortcut:

          If we start with:

          WXYZ + ZYXW = NEAT
          where: W > X > Y > Z

          Then considering the columns of the sum we have:

          (units) T = 10 + Z − W
          (10s) A = 9 + Y − X
          (100s) E = X − 1 − Y
          (1000s) N = W − Z

          Then, (units) + (1000s) and (10s) + (100s) give:

          N + T = 10
          A + E = 8

          which could be used to shorten your solution.

          Like

          • Jim Randell's avatar

            Jim Randell 1:53 pm on 30 November 2020 Permalink | Reply

            Or we can extend it into a full solution by case analysis:

            Firstly, we see Z ≠ 0, as ZYXW is a 4-digit number.

            And W > 5, as 5 + 4 + 3 + 2 < 18.

            So considering possible values for W:

            [W = 6]

            There is only one possible descending sequence that sums to 18, i.e. (6, 5, 4, 3)

            So the sum is:

            6543 − 3456 = 3087

            which doesn’t work.

            [W = 7]

            W must be paired with 3 (to make 10) or 1 (to make 8).

            If it is paired with 3, then the other pair is 2+6. So the sum is:

            7632 − 2367 = 5265

            which doesn’t work.

            If it is paired with 1, then the other pair is either 2+8 or 4+6, which gives us the following sums:

            8721 − 1278 = 7443
            7641 − 1467 = 6174

            The first doesn’t work, but the second gives a viable solution: ANTE − ETNA = NEAT.

            And the following cases show uniqueness:

            [W = 8]

            W must be paired with 2, and the other pair is either 1+7 or 3+5, and we have already looked at (8, 7, 2, 1)

            8532 − 2358 = 6174

            This doesn’t work.

            [W = 9]

            W must be paired with 1, and the other pair either 2+6 or 3+5:

            9621 − 1269 = 8352
            9531 − 1359 = 8173

            Neither of these work.

            Like

    • Finbarr Morley's avatar

      Finbarr Morley 3:14 pm on 30 November 2020 Permalink | Reply

      I’m curious about the properties of these Cryptarithmetics.
      How is it that ANTE-ETNA=NEAT has 1 unique solution out of 10,000.
      But ANTE-ETNA=NAET has none?

      A Google search reveals some discussion:
      http://cryptarithms.awardspace.us/primer.html
      https://www.codeproject.com/Articles/176768/Cryptarithmetic
      https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1949-8594.1987.tb11711.x

      The latter seems to be heading for a discussion on the rules, but it’s ony the first page of an extract.
      Any thoughts from the collective on what the natural rules are?

      Like

  • Unknown's avatar

    Jim Randell 8:55 am on 27 September 2020 Permalink | Reply
    Tags: by: Peter Harrison   

    Teaser 1892: Puzzling present 

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

    I have received an astonishing letter from a fellow puzzle-setter. He writes:

    “I am sending you a puzzle in the form of a parcel consisting of an opaque box containing some identical marbles, each weighing a whole number of grams, greater than one gram. The box itself is virtually weightless. If I told you the total weight of the marbles, you could work out how many there are.”

    He goes on:

    “To enable you to work out the total weight of the marbles I am also sending you a balance and a set of equal weights, each weighing a whole number of grams, whose total weight is two kilograms. Bearing in mind what I told you above, these weights will enable you to calculate the total weight of the marbles and hence how many marbles there are.”

    I thought that he was sending me these items under seperate cover, but I had forgotten how mean he is. He went on:

    “I realise that I can save on the postage. If I told you the weight of each weight you would still be able to work out the number of marbles. Therefore I shall not be sending you anything.”

    How many marbles were there?

    This puzzle is included in the book Brainteasers (2002). The puzzle text above is taken from the book.

    [teaser1892]

     
    • Jim Randell's avatar

      Jim Randell 8:55 am on 27 September 2020 Permalink | Reply

      (See also: Enigma 1606).

      There must be a prime number of balls, each weighing the same prime number of grams.

      This Python program uses the same approach I took with Enigma 1606 (indeed if given a command line argument of 4000 (= the 4kg total of the weights) it can be used to solve that puzzle too).

      It runs in 48ms.

      Run: [ @repl.it ]

      from enigma import Primes, isqrt, divisor, group, arg, printf

# total weights
T = arg(2000, 0, int)

# find prime squares up to T
squares = list(p * p for p in Primes(isqrt(T)))

printf("[T={T}, squares={squares}]")

# each weight is a divisor of T
for w in divisor(T):

  # make a "by" function for weight w
  def by(p):
    (k, r) = divmod(p, w)
    return (k if r > 0 else -k)

  # group the squares into categories by the number of weights required
  d = group(squares, by=by)
  # look for categories with only one weight in
  ss = list(vs[0] for vs in d.values() if len(vs) == 1)
  # there should be only one
  if len(ss) != 1: continue

  # output solution
  p = ss[0]
  printf("{n}x {w}g weights", n=T // w)
  printf("-> {p}g falls into a {w}g category by itself")
  printf("-> {p}g = {r} balls @ {r}g each", r=isqrt(p))
  printf()

      Solution: There are 37 marbles.

      There are 4× 500g weights (2000g in total), and when these are used to weigh the box we must find that it weighs between 1000g (2 weights) and 1500g (3 weights). The only prime square between these weights is 37² = 1369, so there must be 37 balls each weighing 37g.

      Telling us that “if I told you the weight of the weights you would be able to work out the number of marbles” is enough for us to work out the number of marbles, without needing to tell us the actual weight. (As there is only one set of weights that gives a category with a single prime square in). And we can also deduce the set of weights.

      However, in a variation on the puzzle where the set of weights total 2200g, we find there are two possible sets of weights that give a category with a single square in (8× 275g and 4× 550g), but in both cases it is still 1369 that falls into a category by itself, so we can determine the number (and weight) of the marbles, but not the weight (and number) of the weights. So the answer to the puzzle would still be the same.

      Likewise, if the set of weights total 3468g, there are 3 possible sets of weights that give a category with a single square in (6× 578g, 4× 867g and 3× 1156g). However in each of these cases 2809 falls into a category by itself, and so the solution would be 53 marbles each weighing 53g. Which is the answer to Enigma 1606.

      Like

    • Frits's avatar

      Frits 11:36 pm on 27 September 2020 Permalink | Reply 

       
from enigma import SubstitutedExpression
from collections import defaultdict

# list of prime numbers
P = {2, 3, 5, 7}
P |= {x for x in range(11, 45, 2) if all(x % p for p in P)}
# list of squared prime numbers
P2 = [p * p for p in P]

# check if only one total lies uniquely between k weights and k+1 weights
def uniquerange(weight):
  group = defaultdict(list)
  for total in P2:
    # total lies between k weights and k+1 weights
    k = total // weight
    if group[k]:
      group[k].append(total)
    else:
      group[k] = [total]

  singles = [group[x][0] for x in group if len(group[x]) == 1]
  if len(singles) == 1:
    return singles[0]
    
  return 0  
      
# the alphametic puzzle
p = SubstitutedExpression(
  [ # ABCD is a weight and a divisor of 2000
    "2000 % ABCD == 0",
    "uniquerange(ABCD) != 0",
  ],
  answer="(ABCD, uniquerange(ABCD))",
  env=dict(uniquerange=uniquerange), # external functions
  verbose=0,
  d2i="",        # allow number representations to start with 0
  distinct="",   # allow variables with same values
)
 
# Print answers
for (_, ans) in p.solve():
  print(f"{int(2000/ans[0])} x {ans[0]}g weigths")
  print(f"-> {ans[1]}g falls into a {ans[0]}g category by itself")
  print(f"-> {ans[1]}g = {ans[1] ** 0.5} balls @ {ans[1] ** 0.5}g each")

      Like

  • Unknown's avatar

    Jim Randell 9:49 am on 24 March 2020 Permalink | Reply
    Tags: by: Peter Harrison   

    Teaser 2500: [Rogue ball detection] 

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

    A well-known puzzle asks:

    “If among 12 snooker balls one is a different weight, how can the rogue ball be identified – together with deciding whether it is heavier or lighter – in three weighings on a balance?”

    Recently I faced a very similar problem of finding a rogue ball among a consignment of 39 identical-looking balls – and deciding if it was heavier or lighter. I had at my disposal a two-pan balance.

    How many weighings did I need?

    This puzzle was originally published with no title.

    [teaser2500]

     
    • Jim Randell's avatar

      Jim Randell 9:50 am on 24 March 2020 Permalink | Reply

      We dealt with a similar puzzle in Enigma 1589 (also set by Peter Harrison). For that puzzle I wrote a program that searches for a minimal decision tree.

      For an analytical solution the paper Weighing Coins: Divide and Conquer to Detect a Counterfeit by Mario Martelli and Gerald Gannon [ link ] provides an elegant analysis to determine the maximum number of coins that can be distinguished using a certain number of weighings for four related problems.

      And this gives us the solution to this puzzle:

      Solution: 4 weighings can be used to find the rogue object in a set of 39.

      Like

    • Jim Randell's avatar

      Jim Randell 9:44 pm on 24 March 2020 Permalink | Reply

      For Enigma 1589 I wrote the following code to generate the decision trees for the four types of problem described in the linked paper.

      It can be used to generate decision trees for either puzzle.

      Run: [ @codepad ] [ @repl.it ]

      from enigma import (irange, arg, printf)

# weigh 3^n coins in n weighings, suspect coin is lighter
def solve_lighter(n, coins, p=''):
  assert len(coins) == 3**n
  # 3 coins
  if n == 1:
    # weigh two of the coins
    printf("{p}{coins[0]} < {coins[1]} -> {coins[0]}L")
    printf("{p}{coins[0]} = {coins[1]} -> {coins[2]}L")
    printf("{p}{coins[0]} > {coins[1]} -> {coins[1]}L")
  else:
    # divide the coins into 3 piles
    k = len(coins) // 3
    (c1, c2, c3) = (coins[:k], coins[k:2 * k], coins[2 * k:])
    printf("{p}{c1} < {c2}")
    solve_lighter(n - 1, c1, p + '  ')
    printf("{p}{c1} = {c2}")
    solve_lighter(n - 1, c3, p + '  ')
    printf("{p}{c1} > {c2}")
    solve_lighter(n - 1, c2, p + '  ')


# weigh 3^n coins in n weighings
# suspect coin is in reds if heavier, in blacks if lighter
def solve_red_black(n, reds, blacks, red='H', black='L', p=''):
  assert len(reds) + len(blacks) == 3**n and len(reds) == len(blacks) + 1
  # 2 red, 1 black
  if n == 1:
    # weigh the two reds
    printf("{p}{reds[0]} < {reds[1]} -> {x[0]}{x[1]}", x=((reds[1], 'H') if red == 'H' else (reds[0], 'L')))
    printf("{p}{reds[0]} = {reds[1]} -> {blacks[0]}{black}")
    printf("{p}{reds[0]} > {reds[1]} -> {x[0]}{x[1]}", x=((reds[0], 'H') if red == 'H' else (reds[1], 'L')))
  else:
    # weigh (3^(n-1) + 1)/2 reds against (3^(n-1) - 1)/2 of the blacks
    k = (3**(n - 1) + 1) // 2
    (r1, r2, r3) = (reds[:k], reds[k:2 * k], reds[2 * k:])
    (b1, b2, b3) = (blacks[:k - 1], blacks[k - 1:2 * k - 2], blacks[2 * k - 2:])
    (left, right) = (r1 + b1, r2 + b2)
    printf("{p}{left} < {right}")
    solve_red_black(n - 1, r2, b1, red, black, p + '  ')
    printf("{p}{left} = {right}")
    solve_red_black(n - 1, b3, r3, black, red, p + '  ')
    printf("{p}{left} > {right}")
    solve_red_black(n - 1, r1, b2, red, black, p + '  ')


# weigh (3^n - 1) / 2 suspect coins in n weighings
# given a known good coin
def solve_test_coin(n, good, coins, p=''):
  assert len(coins) == ((3**n) - 1) // 2
  if n == 1:
    # weigh the coin against the good coin
    printf("{p}{good} < {coins[0]} -> {coins[0]}H")
    printf("{p}{good} = {coins[0]} -> #")
    printf("{p}{good} > {coins[0]} -> {coins[0]}L")
  else:
    k = (3**(n - 1) + 1) // 2
    (c1, c2, c3) = (coins[:k], coins[k:2 * k - 1], coins[2 * k - 1:])
    (left, right) = (c1, [good] + c2)
    printf("{p}{left} < {right}")
    solve_red_black(n - 1, c1, c2, 'L', 'H', p + '  ')
    printf("{p}{left} = {right}")
    solve_test_coin(n - 1, good, c3, p + '  ')
    printf("{p}{left} > {right}")
    solve_red_black(n - 1, c1, c2, 'H', 'L', p + '  ')


# weigh (3^n - 3) / 2 suspect coins in n weighings
def solve_general(n, coins, p=''):
  assert len(coins) == ((3**n) - 3) // 2
  # divide the coins into 3 piles
  k = len(coins) // 3
  (c1, c2, c3) = (coins[:k], coins[k:2 * k], coins[2 * k:])
  printf("{p}{c1} < {c2}")
  solve_red_black(n - 1, c1 + c3[:1], c2, 'L', 'H', p + '  ')  
  printf("{p}{c1} = {c2}")
  solve_test_coin(n - 1, c1[0], c3, p + '  ')
  printf("{p}{c1} > {c2}")
  solve_red_black(n - 1, c1 + c3[:1], c2, 'H', 'L', p + '  ')
  

# number of weighings and problem type
n = arg(3, 0, int, prompt="number of weighings")
p = arg(2, 1, int, prompt="problem number")
printf("[n={n}; p={p} (of 1-4)]")

if p == 1:
  # solve the general case
  k = (3**n - 3) // 2
  if k > 0:
    printf("---\n{n} weighings finds the suspect coin from {k} coins\n---")
    solve_general(n, list(irange(1, k)))

elif p == 2:
  # solve with a known good coin
  k = (3**n - 1) // 2
  printf("---\n{n} weighings finds the suspect coin from {k} coins, with an extra known good coin (0)\n---")
  solve_test_coin(n, 0, list(irange(1, k)))

elif p == 3:
  # solve red/black
  k = 3**n
  j = (k + 1) // 2
  printf("---\n{n} weighings finds the suspect coin from {k} coins, where {j} of the coins are red and {j1} of the coins are black\nif the suspect coin is red it is heavier, if it is black it is lighter\n---", j1=j - 1)
  solve_red_black(n, list(irange(1, j)), list(irange(j + 1, k)))

elif p == 4:
  # solve lighter
  k = 3**n
  printf("---\n{n} weighings finds the suspect lighter coin from {k} coins\n---")
  solve_lighter(n, list(irange(1, k)))

      Like

  • Unknown's avatar

    Jim Randell 7:49 am on 17 September 2019 Permalink | Reply
    Tags: by: Peter Harrison,   

    Teaser 1973: Straw store 

    From The Sunday Times, 9th July 2000 [link]

    Farmer Fermat has more straw than he can safely stack on his usual rectangular storage area. So he extends the shorter sides of the area to equal the longer sides, thereby forming a square. Alongside he adds another square area, whose side is equal to the shorter side of the original rectangle. The total area of the two squares together is 243 square feet larger than the original rectangle.

    He can now stack straw on each square, up to a height equal to the length of the side of each square, effectively forming two cubes, and the total volume in cubic feet is a perfect cube.

    What was the perimeter of the original rectangle?

    [teaser1973]

     
    • Jim Randell's avatar

      Jim Randell 7:50 am on 17 September 2019 Permalink | Reply

      As presented this puzzle has multiple solutions. However if the perimeter of the original rectangle is required to be a whole number of feet, then only one of the solutions remains.

      This Python program finds all the solutions to the puzzle numerically using the [[ find_zero() ]] function from the enigma.py library. It runs in 63ms.

      Run: [ @replit ]

      from enigma import (irange, cb, cbrt, sq, find_zero, catch, printf)

# consider values for t, where T = t^3 is the total volume
for t in irange(1, 100):
  T = cb(t)

  # calculate y (for x in [0, t])
  def Y(x):
    return cbrt(T - cb(x))

  # how close is x^2 + y^2 - xy to 243?
  def f(x):
    y = Y(x)
    return abs((sq(x) + sq(y) - x * y) - 243)

  # find a zero for f
  r = catch(find_zero, f, 0, cbrt(0.5 * T))
  if r is None: continue
  x = r.v
  y = Y(x)
  p = 2 * (x + y)

  # output solution
  printf("t={t}: x={x:.3f}, y={y:.3f}, p={p:.3f}")

      Solution: The (integer) perimeter of the original rectangle was 48 feet.

      Allowing non-integer solutions for the perimeter we get four solutions:

      t=16: x=0.857, y=15.999, p=33.712
      t=17: x=3.258, y=16.960, p=40.436
      t=18: x=6.255, y=17.745, p=48.000
      t=19: x=10.291, y=17.935, p=56.453

      Graphically we get a solution when the ellipse x² + y² − xy = 243 intersects the curve x³ + y³ = t³ for integer values of t.

      For positive x and y we get solutions for t = 16, 17, 18, 19, as shown in the graph below:

      The original rectangle has sides of length x and y, so the perimeter of the original rectangle is 2(x + y). Only t=18 gives an integer value for the perimeter (although the values for x and y are not integers). In this case the exact values are: x, y = 12 ± √33.

      Like

      • Jim Randell's avatar

        Jim Randell 8:39 am on 19 September 2019 Permalink | Reply

        Here is an analytical solution.

        Given the equations:

        x³ + y³ = t³
        x² + y² − xy = 243

        If we consider the product (x + y)(x² + y² − xy) we have:

        (x + y)(x² + y² − xy) = x³ + y³ = t³
        (x + y) = t³ / 243

        We also have:

        (x + y)² = (x² + y²) + 2xy
        (x + y)² = (243 + xy) + 2xy
        (x + y)² = 243 + 3xy
        xy = (x + y)² / 3 − 81

        So for a given value of t we can determine values for x + y and xy, say:

        x + y = a
        xy = b

        These have positive real solutions for x and y when a² ≥ 4b and b ≥ 0

        a² ≥ 4b
        (x + y)² ≥ 4xy
        (x + y)² ≥ (4/3)(x + y)² − 324
        (x + y)² ≤ 973
        (x + y) ≤ √973
        t³ ≤ 243 × √973
        t ≤ 19.643…

        b ≥ 0
        (x + y)² / 3 − 81 ≥ 0
        (x + y)² ≥ 243
        (x + y) ≥ √243
        t³ ≥ 243 × √243
        t ≥ 15.588…

        So t is in the range 16 to 19. And the required perimeter is given by p = 2(x + y) = 2t³ / 243.

        We can consider the 4 candidate values manually and look for an integer solution, or use a short program:

        Run: [ @replit ]

        from enigma import (irange, cb, div, printf)

for t in irange(16, 19):
  p = div(2 * cb(t), 243)
  if p is None: continue
  printf("t={t}: p={p}")

        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