In the classic “Crossing Ladders” problem, we are given the lengths $x$ and $y$ of two ladders resting on the opposite walls of a narrow, level street. We are also given the height $h$ above the street where the two ladders cross and we are asked to find the width of the street ($w$).
Here, we are only concerned with instances where all four variables are positive integers.
For example, if $x = 70$, $y = 119$ and $h = 30$, we can calculate that $w = 56$.
In fact, for integer values $x$, $y$, $h$ and $0 \lt x \lt y \lt 200$, there are only five triplets $(x, y, h)$ producing integer solutions for $w$:
$(70, 119, 30)$, $(74, 182, 21)$, $(87, 105, 35)$, $(100, 116, 35)$ and $(119, 175, 40)$.
For integer values $x, y, h$ and $0 \lt x \lt y \lt 1\,000\,000$, how many triplets $(x, y, h)$ produce integer solutions for $w$?
This problem cannot be solved directly because it needs a program or script to iterate through all possible combinations of $x$, $y$, and $h$ and check if they produce an integral solution for $w$.
That said, we already know some important information about these four variables. From a geometrical perspective, if we label $w_1$ as the distance from the foot of the first ladder (of length $x$) to the point where the ladders cross and $w_2$ as the distance from the foot of the second ladder (of length $y$) to the point where the ladders cross, we can derive the following relationships using similar triangles:
– $w_1 = w \cdot \frac{x}{h}$
– $w_2 = w \cdot \frac{y}{h}$
Also, a key geometrical insight is that the sum of $w_1$ and $w_2$ equals the total width ($w$) of the street. Therefore:
– $w = w_1 + w_2 = w \cdot \frac{x}{h} + w \cdot \frac{y}{h}$
Solving this equation for $w$, we find:
– $w = \frac{hxy}{hx + hy}$
Now, looking at the equation for $w$, we can see that $w$ is an integer if $hx + hy$ divides evenly into $hxy$, i.e., $hx + hy$ is a divisor of $hxy$.
A brute-force way of solving this problem is to iterate through all $h
Chip Defects
An Amazing Prime-generating Automaton