Tagged: by: John P McCarthy Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 7:56 am on 17 April 2026 Permalink | Reply
    Tags: by: John P McCarthy   

    Teaser 2448: [Contractors] 

    From The Sunday Times, 23rd August 2009 [link]

    Zachary, a contractor, wants to place a stone wall round a new development. He knows he can hire two masons for as long as it takes: Angus, who could do the job on his own in 21 days, and Bruce who could complete it on his own in 28 days. Together, they could finish the job in a certain number of days, but Zachary would like it done in three fewer days. So, as well as hiring Angus and Bruce for the whole time, he hires Chuck, who could do it on his own in 24 days, for the few days necessary to achieve his aim.

    For how many days does he employ Chuck?

    This puzzle was originally published with no title.

    [teaser2448]

     
    • Jim Randell's avatar

      Jim Randell 7:57 am on 17 April 2026 Permalink | Reply

      If we say there is 1 unit of work to do, then:

      A does 1/21 units of work per day
      B does 1/28 units of work per day
      C does 1/24 units of work per day

      We can calculate how long it would take A + B to do the job by combining their work rates:

      1/21 + 1/28 = 1/12

      So together A + B could complete the job in 12 days.

      But Z wants the work to be completed in 9 days.

      In 9 days A + B can do 9/12 (= 3/4) of the job, leaving C to do the remaining 1/4.

      And: 1/4 = 6/24, so C would have to work for 6 days.

      Solution: Chuck works for 6 days.

      This Python program runs in 73ms. (Internal runtime is 64µs).

      from enigma import (Rational, as_int, printf)

Q = Rational()

# work rates for A, B, C
(A, B, C) = (Q(1, x) for x in [21, 28, 24])

# calculate number of days for A and B together
d = as_int(Q(1, A + B))
printf("A + B = {d} days")

# target number of days
t = d - 3
printf("target = {t} days")

# calculate number of extra days = x
# (A + B) * 9 + C * x = 1
# => x = (1 - 9(A + B)) / C
x = Q(1 - 9 * (A + B), C)
printf("C works for {x} days")

      Like

  • Unknown's avatar

    Jim Randell 8:39 am on 9 January 2024 Permalink | Reply
    Tags: by: John P McCarthy   

    Teaser 2198: Developing houses 

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

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

    What was the largest house number that he bought?

    1000 Teasers and nearly 20 years ago.

    [teaser2198]

     
    • Jim Randell's avatar

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

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

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

      from enigma import (irange, tuples, is_square, intersect, printf)

# find <k> numbers from <seq> that sum to a perfect square
def numbers(k, seq):
  # collect sequences by sum
  d = dict()
  for ns in tuples(seq, k):
    s = sum(ns)
    if is_square(s):
      d[s] = ns
  return d

# find 8 adjacent odd numbers that sum to a perfect square
odd = numbers(8, irange(1, 399, step=2))

# find 7 adjacent even numbers that sum to a perfect square
even = numbers(7, irange(2, 399, step=2))

# and look for common sums
for k in intersect([odd.keys(), even.keys()]):
  printf("{k} = {r}^2", r=is_square(k))
  printf("{k} = {ns}", ns=odd[k])
  printf("{k} = {ns}", ns=even[k])
  printf()

      Solution: The largest numbered house bought was number 118.

      The houses bought were:

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

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

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

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

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

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

      And the sums are equal:

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

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

      This can be investigated manually or programatically:

      from enigma import (irange, inf, sq, is_square, printf)

# output a list of numbers, sum, and sqrt(sum)
def output(t, ns):
  s = sum(ns)
  r = is_square(s)
  printf("-> {t} = {ns} = {s} (= {r}^2)")

# consider squares for (a + 4) = i^2
for i in irange(2, inf):
  a = sq(i) - 4
  # calculate b
  (b, r) = divmod(8 * a + 11, 7)
  if 2 * b + 12 > 399: break
  if r != 0: continue
  # output solution
  printf("a={a} b={b}")
  output('odds', list(irange(2 * a + 1, 2 * a + 15, step=2)))
  output('evens', list(irange(2 * b, 2 * b + 12, step=2)))

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

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

      Which gives rise to the two sequences given above.

      Like

      • Frits's avatar

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

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

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

        Like

    • John Crabtree's avatar

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

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

      Like

    • GeoffR's avatar

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

      
from math import isqrt

def is_sq(x):
   return isqrt(x) ** 2 == x

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

      Like

  • Unknown's avatar

    Jim Randell 9:14 am on 18 July 2023 Permalink | Reply
    Tags: by: John P McCarthy   

    Brainteaser 1746: Party time 

    From The Sunday Times, 3rd March 1996 [link]

    In the volatile world of Ruritanian politics, each of the three parties can safely expect to lose a fixed proportion of its supporters to each of the other parties from one election to the next. Thus, the Story party would retain a fixed proportion of its supporters, and lose fixed proportions (which may differ) to the Laboured party and to the Mauve Shirts, and so on. Three elections ago, the Story party and the Laboured party each won 40,000 votes and the Mauve Shirts won 20,000. Two elections ago, the Story party and the Mauve Shirts each won 35,000 votes, while the Laboured party won 30,000 votes. In the last election the Story party and the Laboured party each won 35,000 votes and the Mauve Shirts won 30,000. The total electorate in the current election remains at 100,000.

    What is the minimum number of votes the Mauve Shirts should expect to win in the current election?

    [teaser1746]

     
    • Jim Randell's avatar

      Jim Randell 9:15 am on 18 July 2023 Permalink | Reply

      See also: Enigma 662.

      Given election 1 and election 2 we have 9 variables, of the form XY, that denote the fraction of voters for party X in election 1 that voted for party Y in the election 2.

      All votes for each party are redistributed among the three parties, so:

      SS + SL + SM = 1
      LS + LL + LM = 1
      MS + ML + MM = 1

      and (working in units of 1000 votes) for election 2:

      35 = 40 SS + 40 LS + 20 MS
      30 = 40 SL + 40 LL + 20 ML
      35 = 40 SM + 40 LM + 20 MM

      and for election 3:

      35 = 35 SS + 30 LS + 35 MS
      35 = 35 SL + 30 LL + 35 ML
      30 = 35 SM + 30 LM + 35 MM

      and for election 4 we have:

      S = 35 SS + 35 LS + 30 MS
      L = 35 SL + 35 LL + 30 ML
      M = 35 SM + 35 LM + 30 MM

      where S, L, M must be whole numbers of votes.

      The first 3 blocks give us 9 equations in 9 variables, so it looks like we could solve this system and get the answers for the final block.

      However if we try to do this, we find that the 9 equations are not enough to solve the system (i.e. we do not have 9 independent equations, so the system of equations is incomplete). And this makes sense, as the puzzle asks us for the minimum number of votes M can expect to win, so the equations will give a range of values for S, L, M.

      But we can solve the system by choosing values for some of the variables until the system becomes complete. It turns out that if we give the values for 2 of the variables the rest can be determined.

      By dividing the 20k votes for M in the first election into votes that subsequently go to S, L, M, we can determine values for MS, ML, MM and so the remaining values are determined.

      This program looks at different ways to allocate the 20k votes in blocks of 1000 votes, and calculates the results of the 4th election, discarding situations where we do not end up with a whole number of votes.

      The program runs in 129ms. (Internal runtime is 60ms).

      Run: [ @replit ]

      from enigma import (
  Rational, Matrix, Accumulator, decompose, as_int, seq2str, printf
)

Q = Rational()

eqs = [
  # SS  LS  MS  SL  LL  ML  SM  LM  MM
  (( 1,  0,  0,  1,  0,  0,  1,  0,  0),  1),
  (( 0,  1,  0,  0,  1,  0,  0,  1,  0),  1),
  (( 0,  0,  1,  0,  0,  1,  0,  0,  1),  1),
  ((40, 40, 20,  0,  0,  0,  0,  0,  0), 35),
  (( 0,  0,  0, 40, 40, 20,  0,  0,  0), 30),
  (( 0,  0,  0,  0,  0,  0, 40, 40, 20), 35),
  ((35, 30, 35,  0,  0,  0,  0,  0,  0), 35),
  (( 0,  0,  0, 35, 30, 35,  0,  0,  0), 35),
  (( 0,  0,  0,  0,  0,  0, 35, 30, 35), 30),
]

# validate a fraction in the interval 0 .. 1
def valid(x):
  if x < 0 or x > 1: raise ValueError()
  return x

# record minimum value for M is 4th election
r = Accumulator(fn=min, collect=1)

# choose MS, ML, MM as fractions of N
N = 20
for (a, b, c) in decompose(N, 3, increasing=0, sep=0, min_v=0):

  # add these into the mix
  eqs_ = [
    # SS LS MS SL LL ML SM LM MM
    (( 0, 0, 1, 0, 0, 0, 0, 0, 0), Q(a, N)),
    (( 0, 0, 0, 0, 0, 1, 0, 0, 0), Q(b, N)),
    (( 0, 0, 0, 0, 0, 0, 0, 0, 1), Q(c, N)),
  ]

  try:
    vs = Matrix.linear(eqs + eqs_, field=Q, valid=valid)
  except ValueError:
    continue

  # calculate total votes in the 4th election
  (SS, LS, MS, SL, LL, ML, SM, LM, MM) = vs

  S = 35*SS + 35*LS + 30*MS
  L = 35*SL + 35*LL + 30*ML
  M = 35*SM + 35*LM + 30*MM
  # check the values are integers
  try:
    (S, L, M) = (as_int(1000 * x) for x in (S, L, M))
  except ValueError:
    continue
  printf("[S={S} L={L} M={M} {vs}]", vs=seq2str(vs))
  r.accumulate_data(M, vs)

# output solutions
M = r.value
for vs in r.data:
  printf("M={M} {vs}", vs=seq2str(vs))

      Solution: The Mauve Shirts should expect to win at least 30625 votes.

      Here is one set of fractions that give the required values:

      Note that no-one who votes for M in one election, votes for M in the next election.

      But this is not the only set that gives us the minimum value for M, by increasing the value of N at line 29, we can find further viable sets of values, for example:

      However, the fractions in the bottom row are always the same:

      SM = 3/4, LM = 1/8, MM = 0

      Giving the total votes for M in the 4th election:

      M = 35000 × 3/4 + 35000 × 1/8
      M = 26250 + 4375
      M = 30625

      Like

      • Jim Randell's avatar

        Jim Randell 10:22 pm on 19 July 2023 Permalink | Reply

        The equations can be simplified to give:

        The values of x and y can be restricted by noting that the value of the fraction in each box is between 0 and 1.

        And we can calculate the number of votes for M in the 4th election:

        M = 35000 (S→M) + 35000 (L→M) + 30000 (M→M)
        M = 43125 − 12500z

        And the maximum value for z (= x + y) is 1, which gives a minimum value for M = 30625.

        All that remains is to show that the minimum value is achievable, which we can do by considering an example, and checking that all the numbers of votes remain whole numbers.

        With x = 2/5 and y = 3/5 (as mentioned above) we have:

        1: S=40000 [→S 6000, →L 4000, →M 30000]
        1: L=40000 [→S 21000, →L 14000, →M 5000]
        1: M=20000 [→S 8000, →L 12000, →M 0]

        2: S=35000 [→S 5250, →L 3500, →M 26250]
        2: L=30000 [→S 15750, →L 10500, →M 3750]
        2: M=35000 [→S 14000, →L 21000, →M 0]

        3: S=35000 [→S 5250, →L 3500, →M 26250]
        3: L=35000 [→S 18375, →L 12250, →M 4375]
        3: M=30000 [→S 12000, →L 18000, →M 0]

        4: S=35625
        4: L=33750
        4: M=30625

        With these values it is not possible for another election to follow the same pattern keeping the votes as integers.

        But, if we allow fractional votes the situation settles into a steady state with (to 2dp):

        S = 35384.62
        L = 33846.15
        M = 30769.23

        Like

    • Hugo's avatar

      Hugo 10:18 am on 18 July 2023 Permalink | Reply

      According to my calculations the fewest and most votes that each party can expect are
      L 32500 – 34060, M 30625 – 32965, S 33750 – 36090.
      I’ve forgotten how I got there!

      Like

      • Jim Randell's avatar

        Jim Randell 10:16 pm on 19 July 2023 Permalink | Reply

        I agree with these values.

        I found there are 122,304 splits of votes from the 1st election that allow whole votes in the 4th election.

        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