Recent Updates Toggle Comment Threads | Keyboard Shortcuts

  • Jim Randell 5:27 pm on 9 April 2020 Permalink | Reply
    Tags:   

    Teaser 3003: All that glitters 

    From The Sunday Times, 12th April 2020 [link]

    My aunt has a collection of sovereigns, and she set me a challenge:

    “You can have the coins if you can work out the dates, which (in increasing order) are equally spaced and all in the 20th century. The number of coins is an odd prime. The highest common factor of each pair of dates is an odd prime. The sum of the number of factors of each of the dates (including 1 and the date itself) is an odd prime.”

    I worked out the dates, though the gift was much less valuable than I’d hoped.

    What were the dates?

    [teaser3003]

     

    • Jim Randell 5:46 pm on 9 April 2020 Permalink | Reply

      I assumed the dates we are looking for are the years in the 20th century for each coin.

      This Python program runs in 122ms.

      Run: [ @repl.it ]

      from enigma import Primes, subsets, irange, gcd, tau, printf

primes = Primes(100, expandable=1)

# check a number is an odd prime
check = lambda n: n > 2 and primes.is_prime(n)

# choose years for the first 2 coins
for (a, b) in subsets(irange(1901, 1999), size=2):
  # the common difference
  d = b - a

  # consider a sequence with n terms
  for n in primes.range(3):
    s = list(irange(a, a + (n - 1) * d, step=d))
    if s[-1] > 2000: break

    # gcd of each pair is an odd prime
    if not all(check(gcd(x, y)) for (x, y) in subsets(s, size=2)): break

    # sum of the number of divisors of each date is an odd prime
    if not check(sum(tau(x) for x in s)): continue

    printf("a={a} b={b}, d={d} -> n={n}: {s}")

      Solution: [To Be Revealed]

      Like

    • Robert Brown 9:08 pm on 9 April 2020 Permalink | Reply

      The only numbers with odd numbers of factors are perfect squares. There is only one of these in the 20th century, and that date has only has one factor >1 that’s an odd prime. Quite easy to find the answer by inspection.

      Like

  • Jim Randell 12:29 pm on 9 April 2020 Permalink | Reply
    Tags:   

    Teaser 2862: Algebria’s standard 

    From The Sunday Times, 30th July 2017 [link]

    The Algebrian rectangular flag is highly symbolic. Each of its sides is an even number of inches long and a diagonal divides it into two triangles, one blue and one green, representing its two founding tribes. The length of the diagonal (in inches) is the number of states in Algebria, and the area of the flag (in square inches) is the twentieth century year in which the country obtained independence.

    How many states are there in Algebria, and in which year did the country obtain independence?

    [teaser2862]

     

    • Jim Randell 12:30 pm on 9 April 2020 Permalink | Reply

      If the dimensions of the flag are X and Y (and the diagonal is Z), then the area XY is between 1901 and 2000.

      X and Y are even (say X = 2x, Y = 2y), which limits xy to be between 476 and 500.

      Originally I looked at the possible areas to find viable x, y, z values, but the following Python program uses the [[ pythagorean_triples() ]] generator from the enigma.py library to find x, y, z values that can be scaled up to give an appropriate flag. It runs in 76ms.

      Run: [ @repl.it ]

      from enigma import pythagorean_triples, irange, inf, printf

# consider primitive pythagorean triples
for (x, y, z) in pythagorean_triples(501, primitive=1):
  # and scale up to an appropriate size
  for k in irange(2, inf, step=2):
    (X, Y, Z) = (k * x, k * y, k * z)
    A = X * Y
    if A > 2000: break
    if A < 1901: continue
    printf("X={X} Y={Y} Z={Z} A={A} [x={x} y={y} z={z} k={k}]")

      Solution: There are 68 states in Algebria. It gained independence in 1920.

      Like

  • Jim Randell 3:34 pm on 7 April 2020 Permalink | Reply
    Tags: by: WT Blunt   

    Brainteaser 1805: Find the deuce 

    From The Sunday Times, 20th April 1997 [link]

    Adam, Bill, Charlie and Dave play a game using the ace (counting as 1) and 2 to 10 of spades. These cards are shuffled and placed face down on the table. Each player in turn draws one card and declares whether it is odd or even. Each then in turn draws a further card and must declare a number being either the sum or the product of the two cards held. The winner is the first to deduce which cards remain on the table. They are all perfect logicians, draw every possible inference, and rely on the fact that the others do too.

    In a recent game the calls went as follows:

    Adam: “odd”
    Bill: “odd”
    Charlie: “odd”
    Dave: “odd”
    Adam: “6”
    Bill: “12”
    Charlie: “15”

    But as Dave reached for his second card, a player claimed the game.

    Who was the winner and where was the 2?

    This puzzle was included in the book Brainteasers (2002, edited by Victor Bryant). The puzzle text above is taken from the book.

    [teaser1805]

     

    • Jim Randell 3:34 pm on 7 April 2020 Permalink | Reply

      They could just have easily played the game with 10 cards numbered 1 to 10.

      There are 5 odd cards (1, 3, 5, 7, 9) and only four players, so no one can win from the first round.

      This Python program collects the possible sequences of cards, and then works out it any of the players can determine the cards in the sequence given that they know their own cards. (If you can determine the cards in the sequence, you know which cards remain on the table). And then repeats this until the set of possible sequences remains unchanged (so all deductions have been made). It then moves on to the next play described in the text, with no-one winning until after C has drawn his second card. D is about to draw his second card when someone else claims victory.

      This Python program runs in 88ms.

      Run: [ @repl.it ]

      from enigma import irange, subsets, filter_unique, ordered, intersect, printf

# cards
cards = set(irange(1, 10))

# collect hand for player k from a sequence of cards
def hand(s, k, n=4):
  return ordered(*(s[i] for i in irange(k, len(s) - 1, step=n)))

# find wins from sequences ss
def win(ss):
  r = dict()
  us = list()
  # can player k win?
  for (i, k) in enumerate("ABCD"):
    (rk, uk) = filter_unique(ss, (lambda s: hand(s, i)), (lambda s: ordered(*s)))
    if rk: r[k] = rk
    us.append(uk)
  # return wins (dict), and sequences that do not give a win (set)
  return (r, intersect(us))

# analyse sequences ss
def analyse(ss):
  n = len(ss)
  while True:
    (r, ss) = win(ss)
    yield (r, ss)
    m = len(ss)
    if m == n: break
    n = m

# play a card for player k, who delares d
def play(ss, k, d):
  for s in ss:
    for x in cards.difference(s):
      if x + s[k] == d or x * s[k] == d:
        yield s + (x,)

# the first four plays are all odd cards
ss = list(subsets((1, 3, 5, 7, 9), size=4, select="P"))

# no-one wins
for (r, ss) in analyse(ss): pass

# A (player 0) declares 6
ss = list(play(ss, 0, 6))

# no-one wins
for (r, ss) in analyse(ss): pass

# B (player 1) declares 12
ss = list(play(ss, 1, 12))

# no-one wins
for (r, ss) in analyse(ss): pass

# C (player 2) declares 15
ss = list(play(ss, 2, 15))

# someone (other than D) wins
for (r, ss) in analyse(ss):
  if r and 'D' not in r:
    for k in sorted(r.keys()):
      for v in r[k]:
        printf("{k} wins: {v}")
    break

      Solution: Charlie won. The 2 remained on the table.

      I agree with the published answer, but not with the full solution given at the back of the book.

      My solution is that C claims victory and the final situation when C wins is:

      A: 1 then 6
      B: 3 then 4
      C: 5 then 10 (or: 7 then 8)
      D: 9
      table: 2, 7, 8 (or: 2, 5, 10)

      It makes sense that C is the one who can claim victory as he could be holding (5, 10) or (7, 8), and only C knows for sure.

      The solution given in the book [ link ] says that the final situation when C wins is:

      A: 1 then 5 (or: 5 then 1)
      B: 3 then 4
      C: 9 then 6
      D: 7
      table: 2, 8 [and, presumably, 10]

      However the first four cards are odd, and if A drew the last remaining odd card, then he would know that the cards that remained on the table at this point were the 5 even cards and would claim victory.

      So this cannot be the situation (and given that A did not claim victory as soon as he drew his second card everyone would know that A cannot have 1 and 5 (so must have 3 and 2, or 1 and 6)).

      Like

      • John Crabtree 6:16 am on 10 April 2020 Permalink | Reply

        D does not win. Summarizing the successive elimination:
        After A’s 2nd call, if A = 1 + 5, A wins. Everybody knows this. This eliminates (a) and (b).
        After B’s 2nd call, if B = 3 + 9, B wins. Everybody knows this. This eliminates (c) and (d).
        After C’s 2nd call, if D = 1, 5 or 7, D wins. This eliminates (e), (g) and (i).
        This leaves two cases, (f) and (h) as noted by Jim.
        And so C wins and the 2 is on the table.

        It is ironic that the published solution was correct, but for the wrong reasons.

        Like

  • Jim Randell 4:52 pm on 3 April 2020 Permalink | Reply
    Tags:   

    Teaser 3002: Short-cut 

    From The Sunday Times, 5th April 2020 [link]

    To demonstrate a bit of geometry and trigonometry to my grandson, I took a rectangular piece of paper whose shorter sides were 24 cm in length. With one straight fold I brought one corner of the rectangle to the midpoint of the opposite longer side. Then I cut the paper along the fold, creating a triangle and another piece. I then demonstrated to my grandson that this other piece had double the area of the triangle.

    How long was the cut?

    [teaser3002]

     

    • Jim Randell 5:40 pm on 3 April 2020 Permalink | Reply

      If we assume the fold goes from one of the corners of the rectangle, then we get a nice answer. (See: Enigma 1402). I don’t think other constructions are possible. [This assumption is justified below].

      Brainteaser 1798 is a puzzle with a similar theme.

      The triangles X, Y, Z are all right-angled. We need to find the value of h, the hypotenuse of triangle X.

      The area of triangle X must be the same as the sum of the areas of triangles Y and Z, so:

      (24 – a)b = 12b + ab/2
      12b = 3ab/2
      a = 8

      From triangle Z:

      b² = 16² – 8² = 192

      (So the long side of the rectangle is 2b = 16√3, approximately 27.71 cm).

      And from triangle X:

      h² = 16² + 2²×192 = 1024
      h = 32

      Solution: [To Be Revealed]

      We can then demonstrate that X = Y + Z by constructing X from Y and Z:

      X, Y, Z are all (30°, 60°, 90°) triangles. The same shape as one of the standard set squares.

      Like

      • Jim Randell 3:39 pm on 5 April 2020 Permalink | Reply

        Adding a 24-by-2x strip on the left-hand side of the diagram (to account for the fold not going from a corner), and adjusting the bases of triangles Y and Z to (b – x) and (b + x) leads to the following 2 equations:

        [X = Y + Z + 48x] ⇒ 3b(8 – a) = (72 + a)x
        [Y and Z are similar] ⇒ (24 – a)x = 3b(8 – a)

        These can only be satisfied (for positive a, b) if x = 0 and a = 8 (i.e. a is 1/3 the height of the rectangle), as above.

        So the fold must go from one of the corners, and the assumption above is justified.

        Like

    • Benet Allen 7:49 pm on 5 April 2020 Permalink | Reply

      There’s only one shape where you can fold a corner to the midpoint of the opposite side and be left with a triangle. That’s a 2×1 rectangle. And surely, the remaining piece will have three times the area of the triangle? Am befuddled.

      Like

      • Jim Randell 9:23 pm on 5 April 2020 Permalink | Reply

        My diagram above [ link ] is actually to scale. If you print it out and cut out the rectangle you will find that you can fold the white X onto the grey X, and then fold Y and Z on top (or behind) to make another copy of X, neatly demonstrating that X = Y + Z as required.

        Like

  • Jim Randell 12:12 pm on 2 April 2020 Permalink | Reply
    Tags:   

    Brain-Teaser 516 

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

    In Northminster the Premier is planning a reshuffle of five positions in his Cabinet. They are (in decreasing order of rank):

    Deputy Premier,
    Chancellor of the Purse-strings,
    Minister of Mails,
    Secretary of Science,
    Head Whip.

    At the moment these jobs are held (not respectively) by:

    Attler,
    Balfy,
    Chamberton,
    Disreel,
    Edane.

    Soon these five jobs are to be re-allocated among these five people and each person will get a different job from the one he holds at the moment.

    In the reshuffle the Premier is going to promote Chamberton to Minister of the Mails, or above. Edane is also to be promoted. Attler has made it clear that if he is going to be junior to Chamberton, then the only Deputy Premier he would work under would be Disreel.

    Balfy is going to be demoted, but one consolation is that after the reshuffle he will be senior to someone to whom at the moment he is junior. Finally, Disreel will become Deputy Premier only if Balfy becomes Minister of Mails.

    The Premier tries to avoid a party split by arranging his reshuffle to satisfy all the above demands. Also he arranges it with the least number of demotions possible in the circumstances.

    Who is the present Secretary of Science? And, who is to become Secretary of Science?

    [teaser516]

     

    • Jim Randell 12:12 pm on 2 April 2020 Permalink | Reply

      In order to get a unique solution I had to add a couple of extra “implied” conditions (the kind that got me into trouble in Enigma 99).

      So: “… is going to promote Chamberton to Minister of the Mails, or above”, implies that C’s current position is below MoM.

      and: “Disreel will become Deputy Premier only if …”, implies that D is not currently Deputy Premier. (Also the fact that A would serve under D as Deputy Premier implies that D does not currently hold this position).

      and (maybe): “… Attler has made it clear that if he is going to be junior to Chamberton …”, implies that A is not currently junior to C (although this extra condition is not required to get a unique solution).

      With these conditions made explicit we find there is a single answer to the puzzle.

      This Python program runs in 86ms.

      Run: [ @repl.it ]

      from collections import defaultdict
from enigma import irange, subsets, printf

# "p -> q" = "if p then q", "q if p", "p only if q"
implies = lambda p, q: not(p) or q

# record (by number of demotions) who occupies position 4
r = defaultdict(set)

# consider "before" positions
for before in subsets(irange(1, 5), size=5, select="P"):
  (bA, bB, bC, bD, bE) = before

  # [implied] D is not currently 1
  if bD == 1: continue

  # [implied] A is not currently junior to C
  if (bC < bA): continue

  # [implied] C is currently below 3
  if not(bC > 3): continue

  # consider "after positions"
  for after in subsets(irange(1, 5), size=5, select="P"):
    (aA, aB, aC, aD, aE) = after

    # nobody keeps the same post
    if any(bX == aX for (bX, aX) in zip(before, after)): continue

    # if A is junior to C, then D must be 1
    if not implies(aA > aC, aD == 1): continue

    # D becomes 1 only if B becomes 3
    if not implies(aD == 1, aB == 3): continue

    # C is to be promoted to 3 or above
    if not(aC < 4 and aC < bC): continue

    # E is to be promoted
    if not(aE < bE): continue

    # B is to be demoted ...
    if not(aB > bB): continue

    # ... but will become senior to someone who was his junior
    if not any(aB < aX and bB > bX for (bX, aX) in zip(before, after)): continue

    # count the number of demotions
    d = sum(aX > bX for (bX, aX) in zip(before, after))

    printf("[d={d}, A: {bA}->{aA}; B: {bB}->{aB}; C: {bC}->{aC}; D: {bD}->{aD}; E: {bE}->{aE}]")
    b = dict(zip(before, "ABCDE"))
    a = dict(zip(after, "ABCDE"))
    r[d].add((b[4], a[4]))

# look for the fewest number of demotions
k = min(r.keys())
for (b4, a4) in r[k]:
  printf("{k} demotions: SoS = {b4}->{a4}")

      Solution: Chamberton is the current Secretary of Science. Edane will be the new Secretary of Science.

      There is only one scenario that has only 2 demotions:

      A: demoted from Deputy Premier to Head Whip
      B: demoted from Chancellor to Minister of Mails
      C: promoted from Secretary of Science to Chancellor
      D: promoted from Minster of Mails to Deputy Premier
      E: promoted from Head Whip to Secretary of Science

      We are told B is to be demoted, and someone else who was above B must also be demoted under B, so we cannot do better than 2 demotions.

      There are 2 further scenarios that satisfy the conditions that have 3 demotions.

      Like

    • John Crabtree 10:06 pm on 3 April 2020 Permalink | Reply

      Let the five positions in order of rank be P1, P2, P3, P4 and P5.

      C and E will be promoted, D can be promoted, and B has somebody senior to him, and so A is currently in P1.
      B can be demoted to P3, and so is currently in P2.
      A will move to P4 or P5 (lower than B), and so will be junior to C (P3 or above), and so D moves to P1, and so B moves to P3, and so C moves to P2.
      To minimise the number of demotions A moves to P5, and E moves from P5 to P4.
      The current positions are not in order, and so currently C is in P4, and D is in P3.

      Chamberton is the current Secretary of Science.
      Edane will become the Secretary of Science.

      Like

  • Jim Randell 10:30 am on 31 March 2020 Permalink | Reply
    Tags:   

    Teaser 2877: Four steadings and a numeral 

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

    Farmers Al, Bo, Cy and Di have different double-digit numbers of sheep kept in their respective steadings. Al has the fewest and his number of sheep is a certain fraction of Bo’s number of sheep. Also, Bo’s number of sheep is that same fraction of Cy’s number, and Cy’s number is that same fraction of Di’s.

    If I told you the total of Bo’s number of sheep added to Cy’s, then you would be unable to work out all their numbers of sheep. Similarly, if instead I told you just Bo’s number of sheep, then you would be unable to work out all the other numbers.

    What (in the order Al, Bo, Cy, Di) are their numbers of sheep?

    [teaser2877]

     

    • Jim Randell 10:31 am on 31 March 2020 Permalink | Reply

      This Python program looks for possible geometric sequences for A, B, C, D (the numbers of sheep). And then uses the [[ filter_unique() ]] function from the enigma.py library to find sets where (B + C) does not identify a single sequence, and where B does not identify a single sequence. The solution is in the intersection of these two sets.

      This Python program runs in 62ms.

      Run: [ @repl.it ]

      from enigma import subsets, irange, div, fraction, filter_unique, unpack, intersect, printf

# collect results as (A, B, C, D)
rs = list()

# start with values for A and B
for (A, B) in subsets(irange(10, 97), size=2):
  # f = B / A
  # C = f * B = B^2 / A
  C = div(B * B, A)
  if C is None or C > 98: continue
  # D = f * C = BC / A
  D = div(B * C, A)
  if D is None or D > 99: continue

  printf("[A={A} B={B} C={C} D={D}, f={f[0]}/{f[1]}]", f=fraction(B, A))
  rs.append((A, B, C, D))

# B + C does not uniquely identify the solution
(_, s1) = filter_unique(rs, unpack(lambda A, B, C, D: B + C))
printf("[s1 = {s1}]")

# B does not uniquely identify the solution
(_, s2) = filter_unique(rs, unpack(lambda A, B, C, D: B))
printf("[s2 = {s2}]")

# so the solution is in both sets
for (A, B, C, D) in intersect((s1, s2)):
  printf("A={A} B={B} C={C} D={D}")

      Solution: The numbers of sheep are: Al=16, Bo=24, Cy=36, Di=54.

      Each term in the 3/2 times the previous term.

      There are 6 possible geometric sequences:

      [1] A=10, B=20, C=40, D=80; f=2
      [2] A=11, B=22, C=44, D=88; f=2
      [3] A=12, B=24, C=48, D=96; f=2
      [4] A=16, B=24, C=36, D=54; f=3/2
      [5] A=24, B=36, C=54, D=81; f=3/2
      [6] A=27, B=36, C=48, D=64; f=4/3

      [1], [4] have the same value for B + C (= 60).

      [3], [4] have the same value for B (=24), and [5], [6] have the same value for B (= 36).

      The solution occurs in both sets, so is sequence [4].

      Like

    • GeoffR 5:06 pm on 1 April 2020 Permalink | Reply

      The following programme gives the same six sequences for A,B,C and D.

      for a in range(10,99):
  for b in range(a+1,99):
    for c in range(b+1,99):
      for d in range(c+1,99):
        # Ratios given are a/b = c/d and b/c = c/d
        if a*c == b*b and b*d == c*c:
          print(f"A={a}, B={b}, C={c}, D={d}")
 
# A=10, B=20, C=40, D=80
# A=11, B=22, C=44, D=88
# A=12, B=24, C=48, D=96
# A=16, B=24, C=36, D=54  << Answer - see Jim's logic above
# A=24, B=36, C=54, D=81
# A=27, B=36, C=48, D=64

      Like

  • Jim Randell 4:46 pm on 27 March 2020 Permalink | Reply
    Tags:   

    Teaser 3001: Tetragonal toy tiles 

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

    (see: [ @wikipedia ])

    Thirteen toy tiles comprised a square, rectangles, rhombuses (diamonds on a playing card are rhombuses) and kites (as shown in the diagram). All of each different type were identical. A rhombus’s longer diagonal was a whole number of inches (equalling any diagonal of any other type). Its shorter diagonal was half this. Also, one side of a rectangle was slightly over one inch.

    A pattern I made, using every tile laid flat, had all the symmetries of a square. After laying the first tile, each subsequent tile touched at least one other previously placed tile. Ultimately, any contact points were only where a vertex of a tile touched a vertex of just one other tile; only rhombuses touched every other tile type.

    What, in inches, was a square’s diagonal?

    [teaser3001]

     

    • Jim Randell 6:29 pm on 27 March 2020 Permalink | Reply

      I came up with a pattern for 13 tiles that has the same symmetries as a square (I’ll make a diagram of it later), and that gave me a way to calculate the sides of the rectangle, in terms of the larger diagonal of the rhombus, x.

      Once these are calculated the value of x can be determined manually, or here is a quick program to do it:

      Run: [ @repl.it ]

      from enigma import sqrt, irange, inf, printf

# multipliers for the sides of the rectangle
(ra, rb) = (sqrt(1, 8), sqrt(7, 8))

# consider the diagonal of the square piece
for x in irange(1, inf):
  # calculate the sides of the rectangle
  (a, b) = (ra * x, rb * x)
  if 1.0 < a < 1.1 or 1.0 < b < 1.1:
    printf("x={x} [a={a:.3f} b={b:.3f}]")
  elif a > 1.1:
    break

      Solution: The length of the square’s diagonal is 3 inches.

      I arranged 13 shapes (1 square, 4 rectangles, 4 rhombuses, 4 kites) into the following pattern:

      All the diagonals of all the shapes are equal (= x), except for the shorter diagonal of the rhombus (= x/2).

      In this arrangement the short side of the rectangle is the hypotenuse of a right-angled triangle where the other two sides have length x/4, so it has a length of x√(1/8), and so the longer side has a length of x√(7/8).

      Setting x = 3 gives dimensions of 1.061 × 2.806 inches. The smaller side being close to 1 + 1/16 inches. Which is “slightly over 1 inch” as required.

      The exact shape of the kite doesn’t matter (as long as both diagonals are x), it doesn’t affect the calculation for the rectangle. (In particular the kites could all be rotated through 180° to give a second arrangement).

      Placing the rhombuses the other way leaves a gap that cannot be filled by the required rectangle, and we don’t have enough shapes to fill the gap with multiple shapes.

      Like

    • Robert Brown 8:06 am on 28 March 2020 Permalink | Reply

      I did a scale drawing. My kite has the same aspect ratio as the one in the original text, which makes the large angle equal to that of the rhombus. I don’t think your program would have found my answer, which has the rectangle 1.03 inches high.

      Like

      • Jim Randell 8:13 am on 28 March 2020 Permalink | Reply

        @Robert: My arrangement looks like this [ link ], so the exact shape of the kite doesn’t affect the calculations. But I didn’t look too hard for alternative patterns (although you would hope the setter would have made sure there was a unique answer to the puzzle).

        Like

    • Robert Brown 11:54 am on 28 March 2020 Permalink | Reply

      Interesting. Each rhombus has a thin & thick ‘corner’. My layout has the thin corners connected to the square, then the kites & rhombuses are all angled to fit round the square. I tried (but failed) to get the rectangles in the corner, to give it ‘all the symmetries of a square’ ! My rectangle is long & thin, with diagonal =9 inches. I see Brian has 3 inches, I wonder what his layout looks like . . .

      Like

      • Jim Randell 12:36 pm on 28 March 2020 Permalink | Reply

        I tried my pattern with the rhombuses turned through 90°, but I found the gap between the remaining vertices was too large to fit any of the other shapes into.

        Looking at Brian’s attachment to the Google Sites page it looks like he has found the same layout I did (although I don’t think his kites are the right shape, but that doesn’t change the answer).

        Like

        • Brian Gladman 1:15 pm on 28 March 2020 Permalink | Reply

          That is because the teaser doesn’t explicitly constrain the non-rhombus shapes to have equal diagonals (of course, all except the kite do). The longest rhombus diagonal can be any diagonal of any other shape and I chose to match the longest diagonals of the rhombus and the kite.

          Like

          • Jim Randell 1:20 pm on 28 March 2020 Permalink | Reply

            @Brian: It does say that the longer diagonal of the rhombus should “equal any diagonal of any other type”, so I think the vertices of the kite must touch the sides of an x by x bounding box.

            Like

            • Brian Gladman 2:36 pm on 28 March 2020 Permalink | Reply

              Yes, you interpret it to mean “equal to the diagonals of the other types” (surely a simpler expression of this interpretation), whereas I interpret it to mean a choice between “any of the diagonals of any other type”. Fortunately this clear ambiguity (!) doesn’t have an impact on the answer.

              Like

    • Robert Brown 12:33 pm on 28 March 2020 Permalink | Reply

      So my alternative pattern lacks one of the required symmetries (it has clockwise & counter clockwise versions). We’ve had problems with words before . . . I guess Brian’s layout is similar to yours.

      Like

  • Jim Randell 9:49 am on 24 March 2020 Permalink | Reply
    Tags:   

    Teaser 2500 

    From The Sunday Times, 22nd August 2010 [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?

    [teaser2500]

     

    • 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 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: [ @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

  • Jim Randell 4:25 pm on 20 March 2020 Permalink | Reply
    Tags:   

    Teaser 3000: The three thousandth 

    From The Sunday Times, 22nd March 2020 [link]

    In this addition digits have been consistently replaced by letters, different letters representing different digits. But instead of an addition in base 10 in which the letters represent the digits 0 to 9 this is an addition in base 11, using X for the extra digit, in which the letters represent the digits 1 to X, with 0 unused.

    Please submit the number (still in base 11) represented by TEASER.

    Congratulations to The Sunday Times for publishing 3000 Teaser puzzles.

    [teaser3000]

     

    • Jim Randell 4:30 pm on 20 March 2020 Permalink | Reply

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

      The following run file executes in 272ms.

      Run: [ @repl.it ]

      #!/usr/bin/env python -m enigma -r

SubstitutedSum

--base="11"
--digits="1-10"

"THREE + THOUS + ANDTH = TEASER"

      Solution: TEASER = 12X523.

      There are two ways to assign values to the letters, as D and O are interchangeable:

      17322 + 17495 + X6817 = 12X523 / A=10 D=8 E=2 H=7 N=6 O=4 R=3 S=5 T=1 U=9
      17322 + 17895 + X6417 = 12X523 / A=10 D=4 E=2 H=7 N=6 O=8 R=3 S=5 T=1 U=9

      Like

    • GeoffR 1:48 pm on 21 March 2020 Permalink | Reply

      The teaser uses the 10 different letters ([T,H,R,E,O,U,S,A,N,D] in this teaser), which can convieniently represent the digits (1..10), as zero is not required,

      The programme produces a single solution with the third digit as 10 (or X), alltough there are two sets of digits, with values of O and D interchangeable.

      The programme uses the standard method of adding digits in columns, with carry digits to adjacent columns for column digit sums exceeding 11.

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

%    T H R E E
%    T H O U S
%    A N D T H
%  -----------
%  T E A S E R
%  -----------

% Using digits 1..10 in base 11
var 1..10:T; var 1..10:H; var 1..10:R; var 1..10:E;
var 1..10:O; var 1..10:U; var 1..10:S; var 1..10:A;
var 1..10:N; var 1..10:D;

constraint all_different ([T,H,R,E,O,U,S,A,N,D]);

var 0..2: carry1; var 0..2: carry2; var 0..2: carry3;
var 0..2: carry4; var 0..2: carry5;

% Adding up digits in columns, starting from right side
constraint (E + S + H) mod 11 == R 
/\ carry1 == (E + S + H) div 11;

constraint (E + U + T + carry1) mod 11 == E 
/\ carry2 == (E + U + T + carry1) div 11;

constraint (R + O + D + carry2) mod 11 == S 
/\ carry3 == (R + O + D + carry2) div 11;

constraint (H + H + N + carry3) mod 11 == A 
/\ carry4 = (H + H + N + carry3) div 11;

constraint (T + T + A + carry4) mod 11 == E 
/\ carry5 == (T + T + A + carry4) div 11;

constraint T == carry5;

solve satisfy;

output ["TEASER = " ++ show(T) ++ " " ++ show(E) ++ " " ++ show(A)
++ " " ++ show(S) ++ " " ++ show(E) ++ " " ++ show(R)  
++"\n" ++ "10 digits are [T,H,R,E,O,U,S,A,N,D] = " ++ show([T,H,R,E,O,U,S,A,N,D]) ];

      Like

  • Jim Randell 8:17 am on 17 March 2020 Permalink | Reply
    Tags: ,   

    Brainteaser 1798: Trisection 

    From The Sunday Times, 2nd March 1997

    We have taken a piece of paper in the shape of an equilateral triangle and folded it so that one of the corners lies at some point on the opposite side:

    In the figure triangle A has an area of 36 cm²  and triangle B has an area of 16 cm².

    What is the area of the unfolded piece of paper?

    This puzzle was included in the book Brainteasers (2002, edited by Victor Bryant). The puzzle text above is taken from the book.

    [teaser1798]

     

    • Jim Randell 8:17 am on 17 March 2020 Permalink | Reply

      (See also: Enigma 1402).

      We note that triangles A and B are similar (they both have angles of (60°, θ, 120° – θ)).

      And their areas are in the ratio 36:16 = 6²:4², so their sides are in the ratio 6:4 = 3:2.

      We can label the sides of A as (3x, 3y, 3z) and of B as (2x, 2y, 2z).

      Looking at the base of the original triangle we see it has a length of: (2x + 3y)

      And so the the missing lengths on the other sides are: (3y – x) and (2x + y)

      But these are also the lengths of the remaining sides of triangles A and B, hence:

      (3y – x) / (2x + y) = 3 / 2
      6y – 2x = 6x + 3y
      3y = 8x

      So triangle A has sides of 3x and 8x, separated by an angle of 60°, and it has an area of 36, so:

      36 = (1/2)(3x)(8x)sin(60°)
      36 = 6x²√3
      x²√3 = 6

      And the base of the original triangle is 8x + 2x = 10x, so the total area is:

      T = (√3/4)(10x)²
      T = 25x²√3
      T = 25×6 = 150

      Hence:

      Solution: The area of the original triangle is 150 cm².

      Like

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

    Teaser 2999: Triangular card tower 

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

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

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

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

    How many extra cards would be needed in total?

    [teaser2999]

     

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

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

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

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

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

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

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

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

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

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

      (4n – m) x = 5950

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

      This Python program runs in 76ms.

      Run: [ @repl.it ]

      from enigma import divisors, irange, inf, div, printf

# consider the length of the larger cards
for x in divisors(5950):
  if not(x > 70): continue
  d = 5950 // x

  # consider the number of top rows m
  # and the total number of rows n
  for m in irange(1, inf):
    (n, r) = divmod(d + m, 4)
    if not(n > m): break
    if r != 0: continue

    # the total number of cards required (for the n rows)
    t = n * (3 * n + 1) // 2
    # the number of smaller cards required (for the top m rows)
    s = m * (3 * m + 1) // 2
    # and so the number of larger cards required (for the bottom n-m rows)
    b = t - s
    # the number of 53 card packs used is equal to the number of bottom rows
    if 53 * (n - m) != b: continue

    printf("x={x} -> m={m} n={n}; t={t} s={s} b={b}")

    # start adding k extra rows, counting the additional cards
    a = 0
    for k in irange(1, inf):
      # add 3 cards for each bottom row
      a += 3 * (n - m)
      # and 3 cards for each top row, plus 2 for the new top
      a += 3 * (m + k) - 1
      # calculate the new height
      h = div(6 * x * (4 * n + 3 * k - m), 25)
      # is it an integer?
      if h is not None:
        printf("-> additional cards = {a} [k={k} h={h}]")
        break

      Solution: 355 extra cards are required.

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

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

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

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

      The height of the new tower is 1734 mm.

      Analytically:

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

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

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

      Then considering values for x:

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

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

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

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

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

      from enigma import divisors_pairs, irange, div, printf

# consider possible card sizes
for (n, x) in divisors_pairs(1190):
  if not(x > 70): break
  # calculate n and m
  n += 7
  m = 35 - n
  if not(n > m): continue

  # how many extra obliques to add?
  for k in irange(1, 25):
    h = div(18 * x * k, 25) 
    if h is None: continue
    # calculate the additional number of cards
    a = k * (3 * k + 6 * n + 1) // 2
    printf("x={x} n={n} m={m} -> k={k} h={h} a={a}")
    break

      Like

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

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

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

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

      And I did find a solution:

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

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

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

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

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

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

      Like

  • Jim Randell 9:17 am on 12 March 2020 Permalink | Reply
    Tags: by: Mary Connor   

    Brain-Teaser 515 

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

    Five little girls wanted herb gardens. Mother gave them five kinds and said:

    “There are three clumps of each sort. Now each take three clumps, but so that you have three different kinds in your garden, and so that not one of you has the same three as anyone else.”

    Anne now has two the same as Eve, whose third is common to Beth and Carol. Carol has two the same as Beth, but not the parsley, which Beth has. Dot has mint, and shares two others with Anne. Eve didn’t really like any of Dot’s choice, but they have to share the one Beth and Carol don’t have. Dot doesn’t have rue, and only one person has rue with mint, and one with parsley and thyme.

    Who had sage and who had thyme?

    [teaser515]

     

    • Jim Randell 9:18 am on 12 March 2020 Permalink | Reply

      Programatically, we can try all possible assignments of selections of herbs to the girls.

      This Python program runs in 94ms.

      Run: [ @repl.it ]

      from enigma import subsets, join, printf

# possible choices
ss = list(map(set, subsets("MPRST", size=3, select="C")))

# choose different sets for each of the girls
for (A, B, C, D, E) in subsets(ss, size=5, select="P"):

  # A does not have M
  # B has P
  # C does not have P
  # D has M, does not have R
  if 'M' in A or 'P' not in B or 'P' in C or 'M' not in D or 'R' in D: continue

  # A has 2 the same as E
  AnE = A.intersection(E)
  if len(AnE) != 2: continue

  # and E's other one is common to B and C
  # B and C share 2
  BnC = B.intersection(C)
  if len(BnC) != 2: continue
  EdA = E.difference(A)
  if not EdA.issubset(BnC): continue

  # A and D share 2
  AnD = A.intersection(D)
  if len(AnD) != 2: continue

  # D and E share 1, and neither B nor C have it
  DnE = D.intersection(E)
  if len(DnE) != 1 or DnE.issubset(B.union(C)): continue
  
  # only one has M+R, only one has P+T
  count = lambda s: sum(x.issuperset(s) for x in (A, B, C, D, E))
  if not(count('MR') == 1 and count('PT') == 1): continue

  # output solutions
  collect = lambda k: join(x for (x, s) in zip("ABCDE", (A, B, C, D, E)) if k in s)
  (A, B, C, D, E) = (join(sorted(x)) for x in (A, B, C, D, E))
  printf("A={A} B={B} C={C} D={D} E={E} -> S={S} T={T}", S=collect('S'), T=collect('T'))

      Solution: Anne, Dot, Eve have sage. Beth, Carol, Eve have thyme.

      There are two possible sets of herbs (B has a choice of two different selections):

      A: PRS
      B: MPT / PRT
      C: MRT
      D: MPS
      E: RST

      Like

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

    Brainteaser 1791: Untied problem 

    From The Sunday Times, 12th January 1997 [link]

    Here is an exact long division sum. In some places digits have been consistently replaced by letters, with different letters used for different digits. In all other places the digits have been replaced by asterisks.

    Untie this and find UNTIED.

    This puzzle was included in the book Brainteasers (2002, edited by Victor Bryant). The puzzle text above is taken from the book and differs slightly from the original puzzle.

    [teaser1791]

     

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

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

      The following run file executes in 147ms.

      Run: [ @repl.it ]

      #!/usr/bin/env python -m enigma -r

SubstitutedDivision

"UNTIED / JIM = ADAM"

"UNT - ??? = ??"
"??? - ??? = ??"
"??? - ??D = ??"
"??? - ??? = 0"

--answer="UNTIED"

      Solution: UNTIED = 986304.

      The correct division sum is: 986304 ÷ 132 = 7472.

      Like

    • GeoffR 6:32 pm on 10 March 2020 Permalink | Reply 

      
from itertools import permutations

for P in permutations('1234567890', 9):
    j, i, m, u, n, t, e, d, a = P

    # leading digits must not be zero
    if j == '0' or a =='0'or u == '0': continue
    jim = int(j + i + m)
    untied = int(u + n + t + i + e + d)
    adam = int(a + d + a + m)
    if jim * adam == untied:
        
        # check the lone 'D' position is correct
        if (int(a) * jim) % 10 == int(d):
          print (f"Sum is {untied} / {jim} = {adam}")
          
# Sum is 986304 / 132 = 7472

# There are only two solutions to the main division sum:
# 986304 / 132 = 7472
# and 785601 / 369 = 2129

# Checking the lone 'D' digit position is enough to eliminate the
# second solution ie 785601 / 369 =  2129. The last line of the
# second solution also has 4 digits, instead of 3 digits.
# It ran in 112 msec.

      Like

  • Jim Randell 5:09 pm on 6 March 2020 Permalink | Reply
    Tags:   

    Teaser 2998: Football league 

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

    In our league three points are awarded to a team for a win and one point goes to each team in a drawn match. In each division, the teams play each other twice per season.

    Comparison of the results of the two divisions at the end of last season showed that:

    (a) Division II had one more team than Division I.

    (b) The same total number of points was awarded in each division.

    (c) For the division with the larger number of drawn matches, that number was equal to the number of matches not drawn in the other division.

    (d) The number of drawn matches in one division was a multiple of the (3-digit) number of drawn matches in the other.

    How many teams were in Division II?

    The puzzle text has been reworded slightly to reduce ambiguity.

    [teaser2998]

     

    • Jim Randell 5:54 pm on 6 March 2020 Permalink | Reply

      If there are n teams in a division, and each team plays each other team twice, then the total number of matches played is:

      2 C(n, 2) = n(n – 1)

      So, if Division I has n teams the total number of matches played is:

      t1 = n(n – 1)

      And Division II has n + 1 teams, so the total number of matches played is:

      t2 = (n + 1)n

      These totals are divided into drawn matches and not-drawn matches. If the division with the lower number of drawn matches has x drawn matches (x is a 3-digit number), then the other division has kx draws (where k > 1), and this means the original division has kx not-drawn matches.

      So the total number of matches for the division with the lower number draws is also expressible as (k + 1)x, and the total number of points is:

      pts = 2x + 3kx = (2 + 3k)x

      If the division with the higher number of draws (kx draws) has y not-draws, then we also have:

      pts = 2kx + 3y

      This Python 3 program runs in 73ms.

      Run: [ @repl.it ]

      from enigma import irange, inf, printf

# check the total number of matches works
# tl = total number of matches for the division with the fewer draws
# th = total number of matches for the other division
# d = division with fewer draws
# return: (pts, (n1, t1, md1, mn1), (n2, t2, md2, mn2))
def check(d, tl, th, nl, nh):
  # divide the total into (k + 1) and x
  for k in irange(2, inf):
    (x, r) = divmod(tl, k + 1)
    if x < 100: break
    if r > 0 or x > 999: continue
    # calculate the number of points
    pts = (2 + 3 * k) * x
    y = th - k * x
    if 2 * k * x + 3 * y != pts: continue
    # return solution
    s = ((nl, tl, x, k * x), (nh, th, k * x, y))
    yield (pts,) + (s if d == 1 else s[::-1])

# find number of teams in each division
def solve():
  for n in irange(2, inf):
    (t1, t2) = (n * (n - 1), (n + 1) * n)
    yield from check(1, t1, t2, n, n + 1)
    yield from check(2, t2, t1, n + 1, n)

# output the first solution
for (pts, (n1, t1, md1, mn1), (n2, t2, md2, mn2)) in solve():
  printf("pts={pts} -> D1: n={n1} t={t1} md={md1} mn={mn1}; D2: n={n2} t={t2} md={md2} mn={mn2}")
  break

      Solution: There were 20 teams in Division II.

      There were 19 teams in Division I, giving a total of 342 matches. 114 of the matches were drawn, and the remaining 228 were won outright, giving a total number of points of 2×114 + 3×228 = 912.

      The 20 teams in Division II played a total of 380 matches. 228 of the matches were drawn (twice the number of drawn matches in Division I, and the same as the number of not-drawn matches in Division I), and the remaining 152 were won outright, giving a total number of points of 2×228 + 3×152 = 912.

      Like

    • Robert Brown 11:11 am on 7 March 2020 Permalink | Reply

      I found the first solution working by hand on the back of an envelope! But there are many solutions, and I don’t see anything in the text restricting the size of the divisions.

      Like

      • Jim Randell 11:13 am on 7 March 2020 Permalink | Reply

        @Robert: Are you sure you are using all the information? I found there was only one solution (even though my program only outputs the first solution it finds, but I did have it check for divisions with up to 5000 teams).

        Like

        • Jim Randell 12:02 pm on 7 March 2020 Permalink | Reply

          Some analysis allows us to fully explore the solution space, and confirm that there is only a single solution.

          We can derive the following expressions for x and k:

          x = n (n – 7) / 2
          k = (n + 5) / (n – 7)

          The values for n are thus limited by the acceptable values for x and k.

          Here is a Python 3 program that determines possible values for n:

          from enigma import irange, inf, div, printf

for n in irange(8, inf):
  x = div(n * (n - 7), 2)
  if x < 100: continue
  if x > 999: break
  k = div(n + 5, n - 7)
  if k is None or k < 2: continue
  (t1, t2) = ((n - 1) * n, n * (n + 1))
  printf("pts={(2 + 3 * k) * x} -> D1: n={n} t={t1} md={x} mn={k * x}; D2: n={n + 1} t={t2} md={k * x} mn={t2 - k * x}")

          Or the solution can be determined analytically:

          Restricting the value of n to positive integers, we have the following:

          x is a 3-digit number:

          100 ≤ n (n – 7) / 2 ≤ 999
          19 ≤ n ≤ 48

          k is a non-trivial integer multiplier:

          (n + 5) / (n – 7) ≥ 2
          n ≤ 19

          From which we see there is only a single possible value for n, which gives us the solution, and the values of the other parameters can be calculated.

          Like

    • GeoffR 11:09 am on 8 March 2020 Permalink | Reply 

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

var 1..50: Nteams;   % Division 2 teams
var 1..50: Mteams;   % Division 1 teams

var 100..999: Nnon_draw; var 100..999: Ndraw;
var 100..999: Mnon_draw; var 100..999: Mdraw;

% Number of matches for both divisions
constraint  Nteams * (Nteams - 1) == Nnon_draw + Ndraw;
constraint  Mteams * (Mteams - 1) == Mnon_draw + Mdraw;

% (a) Division 2 held one more team than Division I
constraint Nteams == Mteams + 1;

% (b) The same total number of points was awarded in each division
constraint Mnon_draw * 3 + Mdraw * 2 = Nnon_draw * 3 + Ndraw * 2;

% (c) For the division with the larger number of draws (drawn matches), 
% that number was equal to the number of matches not drawn in the other division.
constraint  Ndraw == Mnon_draw;

% (d) The number of draws in one division was a multiple 
% of the (3-digit) number of draws in the other
constraint Mdraw mod Ndraw == 0 \/ Ndraw mod Mdraw == 0; 

solve satisfy;

output [ "Division 2 teams = " ++ show(Nteams) ++ " No."
++ "\n" ++ "Division 1 teams = " ++ show(Mteams)  ++ " No."
++ "\n" ++ "Div2 draw = " ++ show(Ndraw) ++ ", Div2 non-draw = " ++ show(Nnon_draw) 
++ "\n" ++ "Div1 draw = " ++ show(Mdraw) ++ ", Div1 non-draw = " ++ show(Mnon_draw) 
 ];

      Like

    • Robert Brown 1:46 pm on 8 March 2020 Permalink | Reply

      I had made the classic error of awarding 1 point per draw to each division. As the points are awarded to teams, you get 2 points for every drawn match. Sorry about that!

      Like

  • Jim Randell 7:30 am on 3 March 2020 Permalink | Reply
    Tags:   

    Brain-Teaser 514 

    From The Sunday Times, 18th April 1971 [link]

    On the occasion of the Early Risers Aquatic Club Easter Regatta, Mrs Perch packed a large picnic hamper, including nine dozen small buns, and dispatched her husband with seven of their children, all of different ages under 17, to enjoy the occasion.

    At lunch time the family party attacked the buns with gusto, but Mr Perch, having eaten more buns than any of the children, felt rather uncomfortable and managed to persuade Mr Fish, the President, to dispose of as many buns as he (Mr Perch) and his oldest child had eaten between them.

    Each of the children had eaten at least one bun, and there were sufficient left for each of the family party to eat another two at tea time and a further three on the journey home, which they dutifully did, returning home with an empty hamper.

    It happened that both after lunch and after tea, two of the children had each consumed three times as many buns and two of the children had consumed twice as many buns as one or other of the other children, and that by the time they arrived home each of the children had eaten exactly as many buns as he was years of age.

    How many buns were given to Mr Fish?

    [teaser514]

     

    • Jim Randell 7:31 am on 3 March 2020 Permalink | Reply

      There are seven children of different ages, less than 17. Each child’s age is also the total number of buns eaten by that child during the day, so the minimum possible value is 6.

      This Python program considers possible ages, and checks that the numbers of buns consumed meet the required conditions. It runs in 70ms.

      Run: [ @repl.it ]

      from enigma import subsets, irange, div, icount_exactly as icount, printf

# check numbers in the list s (each reduced by d) have exactly 2
# matches that are 2x and 3x other numbers on the list
def check(s, d):
  # calculate the required list
  s = list(x - d for x in s)
  # two must be 3x and two must be 2x other numbers on the list
  return all(icount(s, (lambda x: k * x in s), 2) for k in (2, 3))

# consider possible ages for the children
for s in subsets(irange(6, 16), size=7):
  # so the total number of buns eaten by the children is...
  t = sum(s)
  # the remaining buns are eaten by...
  # the father: x + 5
  # fish: (x + g - 5)
  # giving a total of: 2x + g
  g = s[-1]
  x = div(108 - t - g, 2)
  if x is None or not(x > g - 5): continue

  # the total number of buns eaten by the children after lunch and tea
  if not(check(s, 5) and check(s, 3)): continue

  # calculate the number of buns eaten by fish
  f = x + g - 5
  printf("fish = {f} [father = {x5}; ages = {s}]", x5=x + 5)

      Solution: Mr. Fish ate 21 of the buns.

      The children are aged: 6, 7, 8, 9, 12, 14, 15.

      And this is the total number of buns consumed by them at the end of the day. Accounting for 71 buns in total.

      They each ate 3 buns on the journey home, so after tea the bun tally was: 3, 4, 5, 6, 9, 11, 12.

      We see that two of the children have consumed 3× the number of buns as some other child: 9 (=3× 3), 12 (=3× 4).

      And also two of the children have consumed 2× the number of buns as some other child: 6 (=2× 3), 12 (=2× 6).

      And before that they each had 2 buns at tea time, so after lunch the bun tally was: 1, 2, 3, 4, 7, 9, 10.

      Again we have: 3 (=3× 1), 9 (=3× 3); and: 2 (=2× 1), 4 (=2× 2).

      So the children consumed 71 buns in all, leaving 37 to be accounted for.

      Of these Mr Fish ate 21, this being the same number that the father ate at lunch, plus the number the eldest child ate at lunch (= 10).

      So the father must have eaten 11 buns at lunch (which is more than the eldest child). With the 2 at tea, and 3 on the way home, this brings the fathers total to 16.

      So adding the total number of buns eaten by the children, the father and Mr. Fish we get: 71 + 16 + 21 = 108, exactly 9 dozen (= 9 × 12).

      Like

  • Jim Randell 5:10 pm on 28 February 2020 Permalink | Reply
    Tags:   

    Teaser 2997: Cemetery lottery symmetry 

    From The Sunday Times, 1st March 2020 [link]

    Our local cemetery conservation lottery tickets have four numbers for a line. Using eight different numbers, my two lines have several symmetries. For each line: just one number is odd; there is one number from each of the ranges 1-9, 10-19, 20-29 and 30-39, in that order; the sum of the four numbers equals that sum for the other line; excluding 1 and the numbers themselves, the 1st and 2nd numbers share just one factor — as do the 2nd and 3rd (a different factor) and the 3rd and 4th (another different factor) and, finally, the 4th and 1st.

    Printed one line directly above the other, my top line includes the largest of the eight numbers.

    What is the bottom line?

    [teaser2997]

     

    • Jim Randell 5:31 pm on 28 February 2020 Permalink | Reply

      This Python program runs in 239ms.

      Run: [ @repl.it ]

      from collections import defaultdict
from enigma import irange, subsets, divisors, printf

# check x and y share a single divisor (not 1, x, y)
def divisor(x, y):
  ds = set(divisors(x)).intersection(divisors(y)).difference([1, x, y])
  if len(ds) == 1:
    return ds.pop()

# collect sets of 4 numbers by sum
ns = defaultdict(list)

# consider possible values for the units digits
for (a, b, c, d) in subsets(irange(0, 9), size=4, select="M"):
  # a cannot be 0
  if a == 0: continue
  # only one of them is odd
  if sum(x % 2 == 1 for x in (a, b, c, d)) != 1: continue
  # construct the numbers
  b += 10
  c += 20
  d += 30
  # each consecutive pair shares a single divisor
  s = list(divisor(*xy) for xy in ((a, b), (b, c), (c, d), (d, a)))
  if None in s: continue
  if len(set(s[:3])) != 3: continue

  ns[a + b + c + d].append((a, b, c, d))

# consider possible sums
for (t, vs) in ns.items():
  # choose two lines
  for (p, q) in subsets(vs, size=2):
    if len(set(p + q)) != 8: continue
    # the largest number is on the top line
    if max(q) > max(p): (p, q) = (q, p)
    printf("{p} / {q}")

      Solution: The numbers on the bottom line are: 6, 15, 20, 34.

      The numbers on the top line are: 4, 14, 21, 36.

      These are the only two candidate lines that have the same sum (they both sum to 75).

      There are three other candidate lines, but they all have different sums.

      The full list of candidate lines is:

      sum=69: (4, 14, 21, 30)
      sum=73: (8, 14, 21, 30)
      sum=75: (4, 14, 21, 36) (6, 15, 20, 34)
      sum=79: (6, 15, 20, 38)

      Like

  • Jim Randell 11:50 am on 27 February 2020 Permalink | Reply
    Tags:   

    Brainteaser 1785: Back to front 

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

     

    Given a row of eleven playing cards:

    [J] [10] [9] [8] [7] [6] [5] [4] [3] [2] [1]

    I wish to reverse the order to give:

    [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [J]

    To do this we are allowed at any stage to make a “move” of the following type:

    remove any section of adjacent cards from the pack and move them elsewhere.

    For example, one possible move from the starting position would be to take:

    [9] [8] [7]

    and move it to the right to give:

    [J] [10] [6] [5] [9] [8] [7] [4] [3] [2] [1]

    What is the minimum number of moves required to reverse them?

    This puzzle was included in the book Brainteasers (2002, edited by Victor Bryant). The puzzle text above is taken from the book and differs slightly from the original puzzle.

    [teaser1785]

     

    • Jim Randell 11:51 am on 27 February 2020 Permalink | Reply

      (See also: Puzzle #32).

      We can measure the “disorderedness” of a list by going through it and looking how each element compares to the next element. If it is less than the next element, then it is “ordered”. If it is greater than the next element, then it is “disordered”.

      Looking at the initial list we have:

      [11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

      which gives the following pairs:

      (11, 10) (10, 9) (9, 8) (8, 7) (7, 6) (6, 5) (5, 4) (4, 3) (3, 2) (2, 1)

      all of which are disordered, giving the initial list a score of 10.

      The target list is:

      [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

      which gives the following pairs:

      (1, 2) (2, 3) (3, 4) (4, 5) (5, 6) (6, 7) (7, 8) (8, 9) (9, 10) (10, 11)

      all of which are ordered, give the target list a score of 0.

      Suppose the list is:

      [? … a] [b … c] [d … e] [f … ?]

      And we move the [b … c] section to between e and f.

      Then we end up with

      [? … a] [d … e] [b … c] [f … ?]

      In the process we lose the adjacent pairs (a, b) (c, d) (e, f) and we gain the adjacent pairs (a, d) (e, b) (c, f).

      So the best improvement we could hope for is if the first three pairs are disordered, and the second three pairs are ordered, then we has reduced the disorderedness score by 3.

      For this to happen we need:

      a > b
      c > d
      e > f

      and:

      a < d
      e < b
      c < f

      We can write all six inequalities as the following chain:

      a < d < c < f < e < b < a

      So it is not possible for all the inequalities to hold simultaneously. So the best we can hope for in a move is to reduce the disorderedness score by 2.

      A similar argument holds if a block is moved to the left.

      Furthermore, if we consider the first move, we know the values a, b, c, d, e, f are in descending order. So the pairs (a, b), (c, d), (e, f) are disordered, and of the pairs (a, d) (e, b) (c, f) only (e, b) is ordered, so we can only reduce the disorderedness by 1 on the first move.

      Similarly, on the final move the list ends up correctly ordered, and a similar argument shows that we can only reduce the disorderedness by 1 on the final move.

      So, for a sequence of length 11, we start with a disorderedness score of 10, and to reduce this to a disorderedness score of 0 will require at least 6 moves (the score being reduced by 1+2+2+2+2+1 = 10). In general reversing a sequence of length n > 2 will require at least 1 + [n / 2] moves (where [x] denotes the integer part of x).

      But can we achieve a reversal in 6 moves?

      I wrote a program to try.

      The following program can be used to examine the behaviour of sequences up to length 9 in less than 7s (and length 10 takes 23 minutes). All of these were achievable with the expected minimum number of moves. Unfortunately we want to know about sequences of length 11 (which takes 93m).

      However, in my experiments with smaller sequences, I found that the minimal sequence found always had as an initial move, removing the two leftmost elements, and then re-inserting them at position (m – 1) // 2 (where m is the length of the original sequence).

      Using this as the first move reduces the run time for a length 10 sequence to 6s, and produces a solution of 6 moves for a length 11 sequence in just 29s.

      Run: [ @repl.it ]

      from enigma import irange, inf, subsets, first, arg, printf

# start with a [1..m] list, reversed
m = arg(9, 0, int)
f = arg(1, 1, int)
printf("[m={m}, f={f}]")

# collect possible different moves
move = dict()
s = list(irange(0, m - 1))
for (i, j) in subsets(irange(0, m - 1), size=2):
  for k in irange(1, m - j + i - 1):
    if k == i: continue
    r = s[i:j + 1]
    t = s[:i] + s[j + 1:]
    r = t[:k] + r + t[k:]
    if r not in move.values():
      move[(i, j, k)] = r

# disorderedness score
def score(s):
  r = 0
  a = None
  for b in s:
    if a is not None: r += (a > b)
    a = b
  return r

# sort s in n (or fewer moves)
def solve(s, n, d, ms=[]):
  # are we done?
  if d == 0:
    yield ms
  elif n > 0:
    # choose a move
    (diff1, diff2) = (list(), 0)
    for (m, v) in move.items():
      s1 = list(s[x] for x in v)
      d1 = score(s1)
      diff = d - d1
      if diff == 2:
        # try diff 2
        for z in solve(s1, n - 1, d1, ms + [m]): yield z
        diff2 += 1
      elif diff == 1:
        # save up diff 1
        diff1.append((s1, d1, m))
    # try any diff 1 moves
    if not diff2:
      for (s1, d1, m) in diff1:
        for z in solve(s1, n - 1, d1, ms + [m]): yield z

s0 = list(irange(m, 1, step=-1))
for n in irange(1 + m // 2, inf):

  # make an initial move...
  if f:
    m1 = (0, 1, (m - 1) // 2)
    s1 = list(s0[x] for x in move[m1])
    (s, n, ms) = (s1, n - 1, [m1])
  else:
    (s, ms) = (s0, [])

  ss = first(solve(s, n, score(s), ms), 1)
  for ms in ss:
    # output solution
    printf("n={n}: {ms}", n=len(ms))
    s = s0
    for (i, j, k) in ms:
      t = list(s[x] for x in move[(i, j, k)])
      printf("  [{i}, {j}] @ {k}: {s} -> {t} ({ss} -> {st})", ss=score(s), st=score(t))
      s = t
    printf()
  if ss: break

      Solution: The minimum number of moves required is 6.

      Here is one set of 6 moves that achieves the reversal:

      (Adjacent pairs that are ordered are linked with a hyphen).

      Like

    • Jim Randell 11:19 am on 1 March 2020 Permalink | Reply

      John Crabtree has come up with the following procedure to reverse a sequence using a minimal number of moves.

      The first move partitions the sequence into an ordered sequence (to the left) and a subsequence from which ordered pairs can be removed and inserted into the ordered sequence (to the right). The total number of moves required is 1 + [n / 2].

      Here is the procedure used to reverse a length 11 sequence in 6 moves:

      And here is the procedure encapsulated in a Python program:

      Run: [ @repl.it ]

      from enigma import irange, tuples, arg, printf

# generate the moves to reverse a sequence of length n
def reverse(n):
  if n < 3:
    if n == 2: yield (1, 1, 0)
    return
  (h, r) = divmod(n, 2)
  # 1st move
  yield (h + r, n - 1, r)
  # then move successive pairs into position
  for k in irange(0, h - 1):
    i = k + h + r - 1
    j = i + 1
    yield (i, j, k)
    

# disorderedness score
score = lambda s: sum(a > b for (a, b) in tuples(s, 2))

# make a block move
def move(s, i, j, k):
  r = s[i:j + 1]
  t = s[:i] + s[j + 1:]
  return t[:k] + r + t[k:]

n = arg(11, 0, int)

# collect the moves
ms = list(reverse(n))
printf("[n={n}, {m} moves]", m=len(ms))
s = list(irange(n, 1, step=-1))
for (i, j, k) in ms:
  t = move(s, i, j, k)
  printf("  [{i}, {j}] @ {k}: {s} -> {t} ({ss} -> {st})", ss=score(s), st=score(t))
  s = t
printf()

      Like

  • Jim Randell 8:16 am on 25 February 2020 Permalink | Reply
    Tags:   

    Teaser 2880: Golfing greats 

    From The Sunday Times, 3rd December 2017 [link]

    Following the success of this summer’s programmes about cricketing greats, there is to be an equivalent series about golfers. On each of the next seven evenings a different media pundit will advocate the merits of two golfers.

    The pundits are: Coltart, Critchley, Harmon, Livingstone, Lee, Murray, Roe.

    The fourteen golfers to be discussed are: Chappell, Els, Faldo, Harrington, Hogan, Mcllroy, Moore, Nicklaus, Poulter, Reed, Singh, Snead, Stenson, Woods.

    Each evening, looking at the names of the pundit and the two golfers, then for any two out of the three names there are just two letters of the alphabet that occur (once or more) in both.

    (a) Which golfers will Critchley advocate?
    (b) Which golfers will Harmon advocate?

    [teaser2880]

     

    • Jim Randell 8:17 am on 25 February 2020 Permalink | Reply

      This puzzle can be solved using the [[ grouping ]] functionality in the enigma.py library.

      The following program runs in 72ms.

      Run: [ @repl.it ]

      from enigma import grouping

pundits = (
  'Coltart', 'Critchley', 'Harmon', 'Livingstone', 'Lee', 'Murray', 'Roe'
)
subjects = (
  'Chappell', 'Els', 'Faldo', 'Harrington', 'Hogan', 'Mcllroy', 'Moore',
  'Nicklaus', 'Poulter', 'Reed', 'Singh', 'Snead', 'Stenson', 'Woods'
)

# form the 2-gangs
grouping.solve_gangs(2, pundits, subjects, grouping.share_letters(2))

      Solution: Critchley advocates Moore and Reed. Harmon advocates Singh and Snead.

      The full schedule is:

      Coltart → Hogan, Stenson
      Critchley → Moore, Reed
      Harmon → Singh, Snead
      Livingstone → Faldo, Woods
      Lee → Chappell, Els
      Murray → Nicklaus, Poulter
      Roe → Harrington, Mcllroy

      Like

  • Jim Randell 5:22 pm on 21 February 2020 Permalink | Reply
    Tags:   

    Teaser 2996: Piece it together 

    From The Sunday Times, 23rd February 2020 [link]

    I have some jigsaw-type pieces each consisting of one, two, three or four 1cm-by-1cm squares joined together without overlapping. The pieces are black on one side and white on the other, and they are all different. I have used all my pieces to simultaneously make some different-sized white squares in jigsaw fashion, with each square using more than one piece. Even if you knew what all my pieces were like, you would not be able to determine the sizes of my squares.

    How many pieces do I have?

    [teaser2996]

     

    • Jim Randell 8:55 pm on 21 February 2020 Permalink | Reply

      (See also: Enigma 321).

      There are only a limited number of 1-sided, 1-, 2-, 3-, 4-onimoes, and as the pieces are all different this gives us an upper limit to the total area of the squares.

      It is fairly straightforward to narrow the required answer down to one of two values on the back of an envelope. But it is fun to make a constructive solution from scratch, so here goes…

      The following program looks for possible total areas that can be made into multiple different squares.

      We then select pieces with the appropriate area and attempt to construct the different sets of squares.

      This Python 3 program is adapted from my initial solution to Enigma 321. It’s not hugely fast, but it does find the solution in 50s.

      from itertools import product
from copy import deepcopy
from enigma import irange, inf, subsets, diff, first, printf

# possible pieces in all possible orientations
pieces = [

  # 1 square - 1x1 block ["O1"]
  (
    [(0, 0)],
  ),

  # 2 squares - 2x1 block ["I2"]
  (
    [(0, 0), (1, 0)],
    [(0, 0), (0, 1)],
  ),

  # 3 squares - linear, 3x1 block ["I3"]
  (
    [(0, 0), (1, 0), (2, 0)],
    [(0, 0), (0, 1), (0, 2)],
  ),

  # 3 squares - L shape ["V3"]
  (
    [(0, 0), (1, 0), (1, 1)],
    [(1, 0), (0, 1), (1, 1)],
    [(0, 0), (1, 0), (0, 1)],
    [(0, 0), (0, 1), (1, 1)],
  ),

  # 4 squares - 4x1 block, ["I4"]
  (
    [(0, 0), (1, 0), (2, 0), (3, 0)],
    [(0, 0), (0, 1), (0, 2), (0, 3)],
  ),

  # 4 squares - square, 2x2 block ["O4"]
  (
    [(0, 0), (1, 0), (0, 1), (1, 1)],
  ),

  # 4 squares - T shape ["T4"]
  (
    [(1, 0), (0, 1), (1, 1), (2, 1)],
    [(0, 0), (0, 1), (1, 1), (0, 2)],
    [(0, 0), (1, 0), (2, 0), (1, 1)],
    [(1, 0), (0, 1), (1, 1), (1, 2)],
  ),

  # and now the chiral ones

  # 4 squares - Z shape ["Z4"]
  (
    [(0, 1), (1, 1), (1, 0), (2, 0)],
    [(0, 0), (0, 1), (1, 1), (1, 2)],
  ),

  # 4 squares - S shape ["Z4'", "S4"]
  (
    [(0, 0), (1, 0), (1, 1), (2, 1)],
    [(1, 0), (1, 1), (0, 1), (0, 2)],
  ),

  # 4 squares - L shape ["L4"]
  (
    [(0, 0), (0, 1), (0, 2), (1, 2)],
    [(0, 0), (1, 0), (2, 0), (2, 1)],
    [(1, 0), (1, 1), (1, 2), (0, 2)],
    [(0, 0), (0, 1), (1, 1), (2, 1)],
  ),

  # 4 squares - L shape ["L4'", "R4"]
  (
    [(0, 0), (1, 0), (1, 1), (2, 1)],
    [(0, 1), (1, 1), (2, 1), (2, 0)],
    [(0, 0), (0, 1), (0, 2), (1, 2)],
    [(0, 0), (0, 1), (1, 0), (2, 0)],
  ),
]

# try to place piece <p> at <x>, <y> in grid <grid> of dimensions <a>, <b>
# using label <n>
def place(p, y, x, n, grid, a, b):
  g = deepcopy(grid)
  for (dy, dx) in p:
    (py, px) = (y + dy, x + dx)
    try:
      q = g[py][px]
    except IndexError:
      return None
    if q is not None:
      return None
    g[py][px] = n
  return g

# try to fit pieces <ps> into grid <grid> of dimensions <a>, <b>
def fit(ps, n, grid, a, b):
  if not ps:
    yield grid
  else:
    # choose a piece
    for p in ps[0]:
      # try to place the piece at x, y
      for (y, x) in product(irange(0, a - 1), irange(0, b - 1)):
        g = place(p, y, x, n, grid, a, b)
        if g is not None:
          yield from fit(ps[1:], n + 1, g, a, b)

# select at least <n> pieces from <ps> with a total area of <k>
def select(ps, k, n):
  for i in irange(n, len(ps)):
    f = 0
    for s in subsets(ps, size=i):
      t = sum(len(p[0]) for p in s) 
      if t == k:
        yield s
      if not(t > k):
        f += 1
    if f == 0: break

# fit the pieces <ps> into squares with sides <squares>
def fit_squares(ps, squares, ss=[]):
  # are we done?
  if not ps:
    yield ss
  else:
    # try to fill the next square
    s = squares[0]
    # choose pieces with the right area
    for fs in select(ps, s * s, 2):
      # create an s x s empty grid and assemble the pieces in it
      grid = list([None] * s for _ in irange(1, s))
      for g in fit(fs, 1, grid, s, s):
        # fit the remaining squares
        yield from fit_squares(diff(ps, fs), squares[1:], ss + [g])

# find an example fit of the pieces <ps> into each of the list of squares <ss>
def solve(ps, ss):
  fs = list()
  for s in ss:
    f = first(fit_squares(ps, s))
    if not f: return
    fs.extend(f)
  return fs


# express n as a sum of increasing squares (minimum: m)
def sum_of_squares(n, m=1, s=[]):
  if n == 0:
    if len(s) > 1:
      yield s
  else:
    for i in irange(m, inf):
      i2 = i * i
      if i2 > n: break
      yield from sum_of_squares(n - i2, i + 1, s + [i])

# consider increasing total area of the squares
T = sum(len(p[0]) for p in pieces)
for n in irange(4 + 9, T):
  sqs = list(sum_of_squares(n, 2))
  if len(sqs) < 2: continue
  printf("total area = {n} -> squares = {sqs}")

  # choose some of the squares
  for ss in subsets(sqs, min_size=2):

    # make a set of polyominoes with the appropriate total area
    for ps in select(pieces, n, 2 * max(len(s) for s in ss)):

      # try and fit them into the squares
      fs = solve(ps, ss)
      if fs is None: continue

      # output solution (number of pieces), and constructed squares
      printf("  {m} pieces", m=len(ps))
      for (s, f) in zip(ss, fs):
        printf("  {s} -> {f}")
      printf()

      There is only a single candidate area that can be expressed as the sum of different, non-unit squares in multiple ways.

      There are two sets of pieces that can be assembled into the required squares, but they both have the same number of pieces (one set is a mirror image of the other), and so this gives the answer.

      Solution: There are 9 jigsaw pieces.

      The 9 pieces have a total area of 29, and can be assembled into a set of (2×2, 3×3, 4×4) squares, or a set of (2×2, 5×5) squares.

      Here is a solution using the 9 pieces: O1, I2, I3, V3, I4, O4, L4, L4′, Z4.

      Note that we can’t turn the pieces over, so L4 and its mirror image (L4′) are different pieces (you cannot rotate one of them to give the same shape as the other), as are Z4 and its mirror image (Z4′).

      And here is another solution using the 9 pieces: O1, I2, I3, V3, I4, O4, L4, L4′, Z4′.

      The second set uses Z4′ instead of Z4. These pieces are mirror images of each other, so any solution for the first set also gives a solution for the second set, by reflecting it.

      There are no further solutions, even if we were are allowed to have squares that are the same size.

      It occurred to me that the squares are the same sizes as the collection of Rubik’s cubes I have available to me, so here are the diagrams made with cubes:

      (I’ve only got one 2×2×2 cube, so it has to be shared between the sets of squares).

      Like

      • Jim Randell 10:55 am on 23 February 2020 Permalink | Reply

        I encapsulated the code that deals with polyominoes into a separate file [[ polyominoes.py ]] that can be used to solve this puzzle (and Enigma 321), and I switched to using Knuth’s Algorithm X, rather than the simplistic [[ fit() ]].

        So the following program runs in a more reasonable 1.1s.

        Run: [ @repl.it ]

        import polyominoes
from enigma import irange, inf, subsets, diff, first, printf

# select at least <n> pieces from <ps> with a total area of <k>
def select(ps, k, n):
  for i in irange(n, len(ps)):
    f = 0
    for s in subsets(ps, size=i):
      t = sum(len(p[0]) for p in s) 
      if t == k:
        yield s
      if not(t > k):
        f += 1
    if f == 0: break

# fit the pieces <ps> into squares with sides <squares>
def fit_squares(ps, squares, ss=[]):
  # are we done?
  if not ps:
    yield ss
  else:
    # try to fill the next square
    s = squares[0]
    # choose pieces with the right area
    for fs in select(ps, s * s, 2):
      # create an s x s empty grid and assemble the pieces in it
      for g in polyominoes.fit(fs, s, s):
        # fit the remaining squares
        yield from fit_squares(diff(ps, fs), squares[1:], ss + [g])

# find an example fit of the pieces <ps> into each of the list of squares <ss>
def solve(ps, ss):
  fs = list()
  for s in ss:
    f = first(fit_squares(ps, s))
    if not f: return
    fs.extend(f)
  return fs


# express n as a sum of increasing squares (minimum: m)
def sum_of_squares(n, m=1, s=[]):
  if n == 0:
    if len(s) > 1:
      yield s
  else:
    for i in irange(m, inf):
      i2 = i * i
      if i2 > n: break
      yield from sum_of_squares(n - i2, i + 1, s + [i])

# available pieces, and total area
pieces = polyominoes.shapes("O1 I2 I3 V3 O4 I4 T4 Z4 Z4' L4 L4'", "ONE_SIDED")

# consider increasing total area of the squares
T = sum(len(p[0]) for p in pieces)
for n in irange(4 + 9, T):
  sqs = list(sum_of_squares(n, 2))
  if len(sqs) < 2: continue
  printf("total area = {n} -> squares = {sqs}")

  # choose some of the squares
  for ss in subsets(sqs, min_size=2):

    # make a set of polyominoes with the appropriate total area
    for ps in select(pieces, n, 2 * max(len(s) for s in ss)):

      # try and fit them into the squares
      fs = solve(ps, ss)
      if fs is None: continue

      # output solution (number of pieces), and constructed squares
      printf("  {m} pieces", m=len(ps))
      for (s, f) in zip(ss, fs):
        printf("  {s} -> {f}")
      printf()

        Like

    • Robert Brown 12:57 pm on 25 February 2020 Permalink | Reply

      This teaser reminds me of enigma 1491 (not on your site?) from 2008. Box of tiles 1×3, 2×4, 3×5 etc. Takes tiles out in order, one at a time, and tries to make a rectangle. Required to find a) smallest possible rectangle & b) next largest. Everyone could all do a) by hand, but b) needed a fairly complex program. Ongoing discussions gradually simplified the program algorithm, and ultimately we got it down to a series of steps that could be followed manually – could be done in about 10 minutes. It’s all on the newenigma site, but you need a user name & password to log in!

      Like

    • Robert Brown 1:03 pm on 25 February 2020 Permalink | Reply

      Sorry, I misquoted that slightly – should say ‘required to find how many tiles for smallest rectangle’ (which of course has no gaps or overlaps)

      Like

      • Jim Randell 2:20 pm on 25 February 2020 Permalink | Reply

        I remember Enigma 1491. It was a fun puzzle. My notes for it are here [ @enigmaticcode ].

        When it was originally published in 2008 I wrote a Perl program to solve it, but that took 50 minutes to run. So while it was running I coded up the same algorithm in C, and that ran in 11 seconds.

        When I came to add the puzzle to the Enigmatic Code site in 2012 I wrote a Python program using a slightly different approach, and found that it ran in 9.2s. Now the same program runs in just 2.5s (probably due to improvements in the PyPy environment — I’m still using the same laptop I was using in 2012).

        Like

  • Jim Randell 8:10 am on 18 February 2020 Permalink | Reply
    Tags:   

    Teaser 2881: A month of meetings 

    From The Sunday Times, 10th December 2017 [link]

    In one particular month this year I had one-day meetings in each of Geneva, London, Rome, Tallinn, Venice and York. For any two of these cities their names had at least one letter in common precisely when the days of their meetings (1st, 2nd, 3rd …) had no common factor larger than one. No two meetings were on the same day of the week (e.g., no two meetings were on Wednesdays). The Geneva meeting was the first and the London meeting was the last, the London meeting being on a Friday.

    What was the date of the Tallinn meeting (month and day)?

    The original puzzle text used the spelling “Tallin”. In the text above I’ve used the more usual spelling, but the puzzle works with either.

    [teaser2881]

     

    • Jim Randell 8:11 am on 18 February 2020 Permalink | Reply

      This Python 3 program runs in 372ms.

      Run: [ @repl.it ]

      from datetime import date
from enigma import irange, gcd, unpack, cached, printf

# the set of letters in a string
def letters(s):
  return set(x for x in s.lower() if x.isalpha())

# return the number of letters shared by two strings
@cached
def share_letters(a, b):
  return len(letters(a).intersection(letters(b)))

# find dates for places <ps>, starting from date <d0>
# s = (place, date) pairs allocated so far
def solve(ps, d0, s=[]):
  # are we done?
  if not ps:
    yield s
  else:
    p = ps[0]
    # choose a date
    for d in irange(d0, 31):
      # no meetings are on the same day of the week
      if any((d - d1) % 7 == 0 for (p1, d1) in s): continue
      # places have a letter in common iff their dates are coprime
      if any(bool(share_letters(p, p1)) != (gcd(d, d1) == 1) for (p1, d1) in s): continue
      # solve for the remaining places
      yield from solve(ps[1:], d0, s + [(p, d)])

# the Geneva meeting was first, so choose a date for that
for dG in irange(1, 26):
  # solve for the remaining places (except London)
  for s1 in solve(['Rome', 'Tallinn', 'Venice', 'York'], dG + 1, [('Geneva', dG)]):
    # and then solve for London (last meeting)
    dM = max(d for (p, d) in s1)
    for s in solve(['London'], dM + 1, s1):
      # find a month in 2017 where the London meeting is a Friday
      (_, dL) = s[-1]
      for m in irange(1, 12):
        try:
          d = date(2017, m, dL)
        except ValueError:
          continue
        # Friday is weekday 4
        if d.weekday() != 4: continue

        # output a solution (ordered by date)
        for (p, d) in sorted(s, key=unpack(lambda p, d: d)):
          printf("{d} {p}", d=date(2017, m, d).strftime("%a %d %b %Y"))
        printf()

      Solution: The Tallinn meeting was on Wednesday 22nd March 2017.

      There are two possible itineraries:

      Sun 05 Mar 2017 Geneva
      Sat 11 Mar 2017 Rome
      Tue 21 Mar 2017 Venice
      Wed 22 Mar 2017 Tallinn
      Thu 30 Mar 2017 York
      Fri 31 Mar 2017 London

      Sun 05 Mar 2017 Geneva
      Sat 11 Mar 2017 Rome
      Wed 22 Mar 2017 Tallinn
      Mon 27 Mar 2017 Venice
      Thu 30 Mar 2017 York
      Fri 31 Mar 2017 London

      Like

← Older posts

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
Create your website at WordPress.com
Get started
%d bloggers like this: