Teaser 3206: Support measures
From The Sunday Times, 3rd March 2024 [link] [link]
Two buildings on level ground with vertical walls were in need of support so engineers placed a steel girder at the foot of the wall of one building and leaned it against the wall of the other one. They placed a shorter girder at the foot of the wall of the second building and leaned it against the wall of the first one. The two girders were then welded together for strength.
The lengths of the girders, the heights of their tops above the ground, the distance between their tops and the distance between the two buildings were all whole numbers of feet. The weld was less than ten feet above the ground and the shorter girder was a foot longer than the distance between the buildings.
What were the lengths of the two girders?
[teaser3206]
Frits, 
GeoffR are discussing. 
Pete Good, 
NigelR, and 1 other are discussing. 
Hugo, and 
Tony Smith, 
Brian Gladman, 
S2T2 
Jim Randell 4:53 pm on 1 March 2024 Permalink |
See: Enigma 775 for the calculation of the height of the weld above the ground.
If the distance between the buildings is d, and the girders have lengths g1 and g2, and the top ends of the girders meet the walls at heights of h1 and h2, and cross each other at a height of H, and the tops are a distance z apart, then we have the following three Pythagorean triangles:
subject to:
This Python program considers possible Pythagorean triangles for the girders (up to a reasonable maximum length).
It runs in 59ms. (Internal runtime is 409µs).
from enigma import (defaultdict, pythagorean_triples, ihypot, fdiv, printf) # index pythagorean triples by non-hypotenuse sides ts = defaultdict(list) for (x, y, z) in pythagorean_triples(250): ts[x].append((y, z)) ts[y].append((x, z)) # consider possible distances for (d, vs) in ts.items(): # the second girder for (h2, g2) in vs: if not (g2 == d + 1): continue # the first girder for (h1, g1) in vs: if not (h1 > h2): continue # check the height of the weld is < 10 if not (h1 * h2 < 10 * (h1 + h2)): continue # calculate the distance between the tops z = ihypot(h1 - h2, d) if z is None: continue # output solution H = fdiv(h1 * h2, h1 + h2) printf("g1={g1} g2={g2}; h1={h1} h2={h2} H={H:.2f}; d={d} z={z}")Solution: The girders were 109 ft and 61 ft long.
The distance between the buildings is 60 ft, so the girders reach 11 ft and 91 ft up the walls, and the weld is about 9.81 ft above the ground (= 1001/102). The tops of the girders are 100 ft apart.
Without the restriction on the height of the weld there is a further theoretical solution where the buildings are 6160 ft apart, and the girders have lengths of 9050 ft and 6161 ft (they reach 6630 ft and 111 ft up the buildings, and cross at a height of 109.17 ft).
But this is the only other solution for girders with lengths up to 10 million feet.
LikeLike
Frits 8:09 am on 2 March 2024 Permalink |
@Jim, you seem to reject the possibility of h1 = 2 * h2 as then the “ts” entry may only have 2 entries.
LikeLike
Jim Randell 8:18 am on 2 March 2024 Permalink |
@Frits: Yes, I was supposing the three Pythagorean triangles were all different. Which is not necessarily the case.
LikeLike
Frits 1:42 pm on 2 March 2024 Permalink |
Using analysis of my other program.
from enigma import (defaultdict, pythagorean_triples, subsets) # set of valid widths ws = {2 * n * (n + 1) for n in range(1, 10)} M = 2717 # maximum any length # index pythagorean triples by non-hypotenuse sides ts = defaultdict(list) for (x, y, z) in pythagorean_triples(M): if x in ws: ts[x].append((y, z)) if y in ws: ts[y].append((x, z)) # smaller height must be less than 20 for k, vs in sorted(ts.items()): svs = sorted(vs) # pick two Pythagorean triangles for (c1, c2) in subsets(svs, 2): if c1[0] > 19: break if 2 * c1[0] == c2[0]: print(f"answer: {c1[1]} and {c2[1]}") # pick three Pythagorean triangles for (c1, c2 ,c3) in subsets(svs, 3): if c1[0] > 19: break if c1[0] + c2[0] == c3[0]: print(f"answer: {c1[1]} and {c3[1]}") if c2[0] < 20: print(f" or {c2[1]} and {c3[1]}")LikeLike
Frits 2:05 pm on 2 March 2024 Permalink |
Similar
from enigma import (defaultdict, pythagorean_triples, subsets) # set of valid widths ws = {2 * n * (n + 1) for n in range(1, 10)} M = 2717 # maximum any length # index pythagorean triples by non-hypotenuse sides ts = defaultdict(list) for (x, y, z) in pythagorean_triples(M): if x in ws: ts[x].append((y, z)) if y in ws: ts[y].append((x, z)) # smaller height must be less than 20 for k, vs in sorted(ts.items()): svs = sorted(vs) # pick two Pythagorean triangles for (c1, c2) in subsets(svs, 2): if c1[0] > 19: break if 2 * c1[0] == c2[0]: print(f"answer: {c1[1]} and {c2[1]}") if (c3 := (m := (c1[0] + c2[0]), (k**2 + m**2)**.5)) in vs: print(f"answer: {c1[1]} and {c3[1]}") if c2[0] < 20: print(f" or {c2[1]} and {c3[1]}")LikeLike
Frits 2:23 am on 5 March 2024 Permalink |
To explore the full solution set we can use maximum length 16199:
LikeLike
Frits 8:05 am on 2 March 2024 Permalink |
There is an upper bound for the width and/or smaller height but not always for the greater height.
from enigma import is_square # |\ | whole numbers: g1, g2, h1, h2, g3 and w # | \ | g1^2 = h1^2 + w^2 # h1| \g1 | g2^2 = h2^2 + w^2 # | \ _/ g3^2 = (h1 - h2)^2 + w^2 # | g2/\ |h2 g2 = w + 1 # |_/___\| h3 < 10 # w # h2^2 = g2^2 - w^2 = 2w + 1 # we have: # 1/h3 = 1/h1 + 1/h2 with h3 < 10 # 1/h1 + 1/h2 > 0.1 or 10 * (h1 + h2) > h1 * h2) # (h2 - 10) * h1 < 10 * h2 or h1 < 10 * h2 / (h2 - 10) # also h1 > h2 so when is 10 * h2 / (h2 - 10) equal to h2? # h2^2 - 20h2 = 0, h2(h2 - 20) = 0 --> h2 = 20 # w < 200 and h2 < 20 # h2 must be odd as h^2 = 2w + 1 --> h2 = 2n + 1, h2 < 20, n < 10 for n in range(1, 10): h2 = 2 * n + 1 # h2^2 = 4n^2 + 4n + 1 = 2w + 1 w = 2 * n * (n + 1) w2 = w * w ub_h1, r = divmod(10 * h2, h2 - 10) if not r: ub_h1 -= 1 if ub_h1 < 0: ub_h1 = 2717 # Burj Khalifa for h1 in range(h2 + 1, ub_h1 + 1): if not (g1 := is_square(h1**2 + w2)): continue if not (g3 := is_square((h1 - h2)**2 + w2)): continue print(f"answer: {(g2 := w + 1)} and {g1}")LikeLike
GeoffR 2:29 pm on 2 March 2024 Permalink |
Using WP Reader to post a MiniZinc solution.
LikeLike
Jim Randell 7:47 am on 3 March 2024 Permalink |
@GeoffR: I think for a complete solution you also need a constraint for the weld height (although in this case it doesn’t eliminate any solution candidates).
My MiniZinc specification looks like this:
%#! python3 -m minizinc use_embed=1 {var("1..250", ["d", "g1", "g2", "h1", "h2", "z"])}; predicate is_pythagorean(var int: x, var int: y, var int: z) = (x * x + y * y = z * z); % first girder constraint is_pythagorean(d, h1, g1); % second girder constraint is_pythagorean(d, h2, g2); constraint h2 < h1; constraint g2 = d + 1; % weld height H = (h1 * h2) / (h1 + h2) constraint h1 * h2 < 10 * (h1 + h2); % tops constraint is_pythagorean(d, h1 - h2, z); solve satisfy;LikeLike
GeoffR 4:31 pm on 3 March 2024 Permalink |
@Jim:
A neat MiniZinc solution.
Yes, the weld height would give a complete solution, although this is not a strict requirement of the teaser description.
I was more interested in the derivation of your formula for the weld height.
If x is the distance from left wall h1 to the weld height (h3), by similar triangles:
h3/x = h2/w and h1/w = h3/(w – x).
Algebraic manipulation gives 1/h3 = 1/h1 + 1/h2
or h3 = h1.h2/(h1 + h2).
As Brian has mentioned to me, this is the same formula in optics for the focal length, object and image distances, or two resistors in parallel.
LikeLike
Frits 7:06 am on 5 March 2024 Permalink |
I believe this program fully explores the solution set (without calculating complex upper bounds).
from math import isqrt # for any pythagorean triangle with side y and hypothenuse z: # if z = y + i then the square of other side = 2 * i * y + i^2 # index pythagorean triples by non-hypotenuse sides # set of valid widths (h2 = 2n + 1) ts = {w: [(dm[0], dm[0] + i) for i in range(w - 2, 0, -2) if (dm := divmod(w**2 - i**2, 2 * i))[1] == 0] for w in [2 * n * (n + 1) for n in range(1, 10)]} # smaller height must be less than 20 for n, (w, vs) in enumerate(ts.items(), start=1): # set up pythagorean triangle for smaller height t1 = (2 * n + 1, w + 1) # pick other Pythagorean triangles for t2 in vs: if t2 == t1: continue # we have a solution if greater height is double the small height if 2 * t1[0] == t2[0]: print(f"answer: {t1[1]} and {t2[1]} feet") # for non-hypotenuse sides h2 and (h1 - h2) check if h1^2 + w^2 is square if (z := isqrt((z2 := w**2 + (t1[0] + t2[0])**2)))**2 == z2: print(f"answer: {t1[1]} and {z} feet") if t2[0] < 20: print(f" or {t2[1]} and {z} feet")LikeLike
Jim Randell 2:32 pm on 5 March 2024 Permalink |
@Frits: Well done on reaching a complete solution.
I have to admit I just did a search for “longest steel girder” and chose a suitable upper value. (And I was surprised that the actual answer involved girders that were so long).
But I thought I would do a complete solution too:
If we know one of the non-hypotenuse sides of a Pythagorean triangle, say a in the triple (a, b, c), where c is the hypotenuse, then we have:
So by dividing a² into 2 divisors (say x and y), then we can find potential (b, c) pairs to make a Pythagorean triple as follows:
And there are only a finite number of divisor pairs, so there are only a finite number Pythagorean triangles that share a leg.
We can now provide a complete solution to the problem.
As Frits notes above, h2 must be an odd number between 3 and 19, and for a given value of h2 we can recover the distance between the buildings d and the length of the shorter girder g2:
So we can consider possible values for h2, calculate the corresponding value for d and then generate all possible Pythagorean triangles that have one leg d, and look for those with a longer g1 and corresponding h1, and then we can check for those that give an integer distance between the tops.
This Python program has an internal runtime of 442µs.
Run: [ @replit ]
from enigma import (irange, sq, div, ihypot, divisors_pairs, fdiv, printf) # h2 is odd, < 20 for h2 in irange(3, 19, step=2): d = div(sq(h2) - 1, 2) g2 = d + 1 # look for pythagorean triples with a leg of d for (y, x) in divisors_pairs(d, 2): (h1, g1) = (div(x - y, 2), div(x + y, 2)) if (not h1) or (not g1): continue # does this give a longer girder if not (g1 > g2): continue # check weld height H < 10 if not (h1 * h2 < 10 * (h1 + h2)): continue # check distance between tops z = ihypot(d, h1 - h2) if z is None: continue # output solution H = fdiv(h1 * h2, h1 + h2) printf("g1={g1} g2={g2}; h1={h1} h2={h2} H={H:.2f}; d={d} z={z}")LikeLike
Frits 1:32 am on 8 March 2024 Permalink |
@Jim, I keep forgetting this trick.
Processing the divisor pairs in reverse order allows for an early break with respect to the weld height check.
LikeLike