Download a PostScript version of this document
(PS, 285 KB)
---
Some mathematical problems involve functions that are simple to perform in one direction but are much more difficult to invert. Such functions are called "one-way" functions, and studying them is an important part of certain applied mathematical fields, such as cryptography.
I first saw the famous "crossed ladders" problem many years ago, but I hadn't attempted to solve it myself until recently. I found that the solution was rather difficult to come by, but some interesting properties of those solutions meant that generating new ones was fairly simple.
Suppose we have two ladders in a hallway with level floor and vertical walls. The first ladder M is leaning against the right wall, and its base is touching the left wall. Similarly, the second ladder N is leaning against the left wall, and its base is touching the right wall. The lengths of M and N are, respectively, m and n, both of which are longer than the width of the hallway. If the point at which they cross is h units above the floor, how wide is the hallway?
Fix the bottom left corner at the origin, so that the base of M sits at the point (0,0). We seek w, where (w,0) is the location of the bottom right corner--this is where the base of N sits. M makes an angle φ with the floor such that
cos(φ)=w/m
If we treat M as a line in the coordinate plane, the slope of M is tan(φ). Using the formula tan^2(φ)=sec^2(φ)-1, we can express the slope in terms of m and w:
tan(φ)=sqrt(m^2-w^2)/w
We can now write an equation for M in point-slope notation.
y_M=x_M(sqrt({m^2-w^2)/w
This process yields a similar equation for N, but because the slope of N is negative in our coordinate system, we must choose the negative square root (which we absorb into the x_N term for convenience).
y_N=(w-x_N)(sqrt{n^2-w^2)/w
Figure 1: Crossed ladders with Cartesian coordinates
(PNG, 850x1100, 19.2 KB)
We are only given the height of the crossing point of M and N from the floor. This is the y-coordinate of where our two lines intersect. If we set our expressions equal to each other now, however, we will cancel out y, which is unhelpful. We thus need to rewrite the equations to cancel out x instead.
x_M=(wy_M)/sqrt(m^2-w^2) x_N=(-wy_N)/sqrt(n^2-w^2)+w
We now set x_M=x_N and y_M=y_N=h.
hw/sqrt(m^2-w^2)=-hw/sqrt(n^2-w^2)+w h/sqrt(m^2-w^2)=-h/sqrt(n^2-w^2)+1
We have two unequal square root terms in our expression. Expanding it out would involve squaring twice, once to remove each square root. To avoid this, we use the substitution ν=sqrt(n^2-w^2). Note that ν represents the full height of the ladder N from the ground; instead of solving directly for the width of the hall, we will solve for this height.
νh/sqrt(m^2-w^2)=ν-h
ν^2*h^2/(m^2-w^2)=ν^2-2νh+h^2
ν^2*h^2/(ν^2+m^2-n^2)=ν^2-2νh+h^2
ν^2*h^2=(ν^2+m^2-n^2)(ν^2-2νh+h^2)
0=ν^4-2hν^3+(m^2+n^2)ν^2-2h(m^2+n^2)ν+h^2(m^2+n^2)
The width of the hall is then
w=sqrt(n^2-ν^2)
Are there any positive integer values for n, m and h such that w is also integral? Our solution method involves a quartic equation, for which finding any solution is a complicated process--much less an integral one.
Certain cases are easy to determine. For example, if m=n, the answer is clearly yes. Ladders of equal length rise the same height from the ground, and they cross at their midpoints. This arrangement forms a rectangle with width w and height ν=2h. It immediately follows that h and w are integral if and only if (w,ν,n) is a Pythagorean triple (which may or may not be primitive) and ν is even.
Figure 2: Ladders of equal length form a rectangle
(PNG, 850x1100, 18.4 KB)
If m≠n, the answer is still yes, but the relationship is less obvious. Assuming without loss of generality that n>m, the table below shows the "primitive" integer solutions (such that gcd(n,m,w,h)=1) for all n≤500.
+---+---+---+---+ | n | m | h | w | +---+---+---+---+ +---+---+---+---+ |105|87 |35 |63 + +---+---+---+---+ |116|100|35 |80 | +---+---+---+---+ |119|70 |30 |56 | +---+---+---+---+ |175|119|40 |105| +---+---+---+---+ |182|74 |21 |70 | +---+---+---+---+ |210|182|45 |168| +---+---+---+---+ |219|156|44 |144| +---+---+---+---+ |238|113|14 |112| +---+---+---+---+ |273|175|90 |105| +---+---+---+---+ |296|104|35 |96 | +---+---+---+---+ |364|175|80 |140| +---+---+---+---+ |401|58 |38 |40 | +---+---+---+---+ |420|273|80 |252| +---+---+---+---+ |429|187|72 |165| +---+---+---+---+ |442|425|70 |408| +---+---+---+---+ |500|375|144|300| +---+---+---+---+
At first glance, the table yields no obvious pattern. Can we find a method to generate these sets of values?
Suppose we had only been given m, n and w. Define μ=sqrt(m^2-w^2); this is the full height of ladder M from the ground, just as ν is to ladder N. Solving for h is straightforward: we can use the ladders' equations to find the y-coordinate of their intersection.
x(sqrt(m^2-w^2)/w)=(w-x)(sqrt(n^2-w^2)/w)
x(μ/w)=(w-x)(ν/w)
x((μ+ν/w)=ν
x=wν/(μ+ν)
h=x(μ/w)
=μν/(μ+ν)
To find integer solutions, we want h to be rational. However, since μ and ν are square roots, they may or may not be rational. Since the quotient of two irrationals can be rational, there might be several, even infinitely many, irrational values of μ or ν that produce a rational h. We thus need to establish a very important fact:
h is rational if and only if μ and ν are both integral.
Proof. We first note that μ and ν are square roots of positive integers. Square roots of positive integers are either integral or irrational, so if μ or ν are rational, they are integral. If exactly one of μ or ν is irrational, μ+ν is irrational, as a rational plus an irrational is irrational. If both are irrational, suppose μ+ν is rational; then
μ-ν=(m^2-n^2)/(μ+ν)
is also rational. But by adding and subtracting these expressions, it follows that μ and ν must be rational as well--a contradiction.
Further, suppose μ+ν is irrational but μν/(μ+ν) is rational. μν cannot be rational, as the quotient of a rational and an irrational is irrational. But
μν/(μ+ν)*((m^2-n^2)(μ-ν))/(μ-ν)=(m^2-w^2)ν-(n^2-w^2)μ
is rational; call its value e/f. Then f(m^2-w^2)ν=e(n^2-w^2)μ and ν/μ is rational. μ^2 is rational, so (ν/μ)μ^2=μν must be rational--a contradiction.
(The above argument is invalid if μ=ν, but in such case, h=μ^2/2μ=μ/2; this is rational if and only if μ is integral.) □
This fact tells us that when considering integer solutions, μ and ν are integral. More importantly, μ^2=m^2-w^2 and ν^2=n^2-w^2 are perfect squares. The triples (μ,w,m) and (ν,w,n) are thus Pythagorean triples.
If μ and ν are integral, h is rational, but it is not guaranteed to be integral. Consider the third quadruple in our table of solutions:
n=119, m=70, h=30, w=56
Here ν=sqrt(119^2-56^2)=105 and μ=sqrt(70^2-56^2)=42. By the nature of the ladders, (ν,w,n) and (μ,w,m) are both Pythagorean triples. We can verify the value of h using the equation above:
h=(105*42)/(105+42)=4410/147=30
The two Pythagorean triples involved are (105,56,119) and (42,56,70). These triples share a leg, 56, which is the width of the hallway. However, these triples are not primitive:
(105,56,119)=7(15,8,17) (42,56,70)=14(3,4,5)
The smallest multiples of these triples that share a leg are (6,8,10) and (15,8,17). These smaller triples produce an h value of:
h=(6*15)/(6+15)=90/21=30/7
When we put this information together, we can take an arbitrary Pythagorean triple (a,b,c) and work backwards from the definition of h to generate integral crossed ladders.
- Select any other Pythagorean triple (α,β,γ), which may or may not be the same triple as (a,b,c).
- Choose p and q such that p(a,b,c) shares a leg with q(α,β,γ). For example:
pa=qα
- Select the other legs from each triple and calculate the crossing value.
h'=pbqβ/(pb+qβ)
- Multiply by the denominator of h'. The generated solution is:
n=(pb+qβ)pc h=pbqβ m=(pb+qβ)qγ w=pa
- The solution is primitive if and only if \gcd(pbqβ,pb+qβ)=pb+qβ.
By swapping a with b, or α with β, we can produce three other sets of integral crossed ladders using the same triples. Some of these sets might be duplicates.
Once we know the properties of integer crossed ladders, generating a new set is quite easy. All we have to do is pick two Pythagorean triples, then choose two numbers to multiply them by that satisfy very basic properties. A few multiplications and additions later, we have a new set of ladders. This is a far simpler operation than choosing three unknowns to force the root of a quartic equation to be integral.
---
[Last updated: 2022-09-07]