# Using a compass and straightedge, what is the shortest way to divide a line segment into $n$ equal parts?

Sometimes I help my next door neighbor’s daughter with her homework. Today she had to trisect a line segment using a compass and straightedge. Admittedly, I had to look this up on the internet, and I found this helpful site. There they claim that the fewest number of “steps” necessary to trisect the segment is $4$, where by one “step” we mean any stroke of the pencil, either with the compass or straightedge.

Immediately, this got me thinking about the length of other optimal constructions, which has led to the question of this post:

What is a the minimum number of steps necessary to construct a segment of length $\frac{1}{n}$ given a segment of length $1$?

If $s(n)$ is the quantity in question, then this other helpful site shows that $s(n)\le n+6$. However, $s(2)=3$ and $s(3)=4$, so the bound is not sharp. Also, we can see that $s(mn)\le s(m)+s(n)$ by creating a segment of length $\frac{1}{mn}$ from one of length $\frac{1}{n}$.

Finally, at the bottom of the first site, they hint at one method of construction, which involves drawing larger and larger circles. Assuming their hint leads to an optimal construction (which would need to be proved), I believe that the first eight values of $s(n)$ starting with $n=1$ are:

$$0,3,4,5,5,5,5,6$$

This returns nothing on OEIS. (The above numbers assume that the initial segment of length $1$ is marked off on a very long ray, else we’d have to add one for $n\ge3$ to lengthen the segment appropriately).

Any ideas?

#### Solutions Collecting From Web of "Using a compass and straightedge, what is the shortest way to divide a line segment into $n$ equal parts?"

Let starting segment is $AB$.
As one can see from first link, starting condition is “segment-on-the-line”.
Anyway one can add $1$ line at the start to get this starting condition.

Consider odd $n$.

Let coordinates of starting points are: $A(-1,0)$, $B(0,0)$.

If point $C$ has coordinates $C(n,0)$, then (see Figure 1) coordinates of other points are:
$D\left(\dfrac{1}{2n},\dfrac{\sqrt{4n^2-1}}{2n}\right)$;
$\qquad$
$E(1,0)$;
$\qquad$
$P\left(-1+\dfrac{1}{n},0\right)$.

Figure 1:

Consider even $n$.

Let coordinates of starting points are: $A(0,0)$, $B(1,0)$.

If point $C$ has coordinates $C\left(\dfrac{n}{2},0\right)$, then (see Figure 2) coordinates of other points are:
$D\left(\dfrac{1}{n},\dfrac{\sqrt{n^2-1}}{n}\right)$;
$\qquad$
$E\left(\dfrac{1}{n},-\dfrac{\sqrt{n^2-1}}{n}\right)$;
$\qquad$
$P\left(\dfrac{1}{n},0\right)$.

Figure 2:

Main idea: For given $m$ to draw point $C(m,0)$ as fast as possible.

As I checked (up to $m=2048$), it is possible to draw point $C(m,0)$, applying

$$1+\lfloor \log_2 m \rfloor$$

steps, where $\lfloor \cdot \rfloor$ is floor rounding function.

According to described construction, upper bound of (total) steps is
$$3+\lfloor \log_2 n \rfloor, \mbox{ if } n \mbox{ is odd} ;$$
$$2+\lfloor \log_2 n \rfloor, \mbox{ if } n \mbox{ is even}.$$

Upper bounds of steps (starting with $n=1$) are:
$$0; ~~ 3, 4; ~~ 4, 5, 4, 5; ~~ 5,6,5,6,5,6,5,6; ~~ 6,7,6,7, …$$

Examples:

$n=11$: build point $C(11,0)$ and follow figure 1 (total $6$ steps).

$n=12$: build point $C(6,0)$ and follow figure 2 (total $5$ steps).