Edit on July 31: Now the upper bound is tight (up to replacing n by O(n)). The improvement over the older version is in the argument after Lemma 1. Now we consider the Weil absolute logarithmic height of an algebraic number instead of the length.
Here is a proof that D(n) < 22cn for some positive constant c>0 for sufficiently large n. In other words, the answer to the “can one do better” part of the question 2 is negative.
As Terry Tao pointed out, this problem can be rephrased in the algebraic form. We have z0=0 and z1=1, and any zn (n≥2) can be obtained from earlier numbers by addition, subtraction, multiplication, division or square root. The claim follows if |zn| < 22O(n).
Lemma 1: The degree of zn over ℚ is at most 2n.
Proof: Let Fn=ℚ(z0, …, zn) be the minimum field containing ℚ∪{z0, …, zn}. Then F0=ℚ, and Fn is either equal to Fn−1 or an extension of Fn−1 obtained by adjoining a square root. Since adjoining a square root of a non-square element gives an extension of degree 2, the extension degree [Fn:Fn−1] is either 1 or 2. By the degree formula, it holds that [Fn:ℚ] = [Fn:F0] = [Fn:Fn−1][Fn−1:Fn−2]…[F1:F0] ≤ 2n. Therefore, the degree of every element in Fn over ℚ is also at most 2n. (end of proof of Lemma 1)
There is a function called the Weil absolute logarithmic height h(α) defined on algebraic numbers α which takes nonnegative real values. See Section 3.2 of [Wal00] for its definition and the proof of the following properties:
- If α is an algebraic number of degree d, then |α| ≤ exp(dh(α)).
- If p and q are integers which are relatively prime, then h(p/q) = ln max{|p|,|q|}.
- If α and β are algebraic numbers, then h(α+β) ≤ h(α) + h(β) + ln 2.
- If α and β are algebraic numbers, then h(αβ) ≤ h(α) + h(β).
- If α is an algebraic number and n is an integer, then h(αn) = |n|h(α). In particular, h(√α)=h(α)/2.
By using the properties 2–5 and the mathematical induction, we can prove that h(zn) ≤ 2n ln 2. By combining the property 1 and Lemma 1, we obtain that |zn| ≤ 222n.
References
[Wal00] Michel Waldschmidt: Diophantine Approximation on Linear Algebraic Groups: Transcendence Properties of the Exponential Function in Several Variables, Springer, 2000.
The Ghosts and Ghostbusters problem can be solved in $O(n\log n)$ time, which is considerably faster than the $O(n^2\log n)$-time algorithm suggested by CLRS.
The ham sandwich theorem implies that there is a line $L$ that splits both the ghosts and the ghostbusters exactly in half. (If the number of ghosts and ghostbusters is odd, the line passes through one of each; if the number is even, the line passes through neither.) Lo, Matoušek, and Steiger [Discrete Comput. Geom. 1994] describe an algorithm to compute a ham-sandwich line in $O(n)$ time; their algorithm is also sketched here. Now recursively solve the problem on both sides of $L$; the recursion stops when all subsets are empty. The total running time obeys the mergesort recurrence $T(n) = O(n) + 2T(n/2)$ and thus is $O(n\log n)$.
This algorithm is optimal in the algebraic decision tree and algebraic computation tree models of computation, because you need $\Omega(n\log n)$ time in those models just to decide whether two sets of $n$ points are equal.
Best Answer
A bounded-length straightedge can emulate an arbitrarily large straightedge (even without requiring any compass), so the rusty compass theorem is sufficient.
Note that, in particular, it suffices to show that there exists an $\varepsilon > 0$ such that a straightedge of length $1$ is capable of joining two points separated by any distance $\leq 1 + \varepsilon$ (and therefore emulates a straightedge of length $1 + \varepsilon$, and therefore arbitrarily long straightedges by iterating this process).
We can use Pappus's theorem to establish this result for any $\varepsilon < 1$:
https://en.wikipedia.org/wiki/Pappus%27s_hexagon_theorem
In particular, given two points $A$ and $c$ (separated by a distance slightly greater than 1) which we wish to join, draw a line $g$ through $A$ and a line $h$ through $c$ which approach relatively close to each other. Then add arbitrary points $B, C$ on $g$ and $a, b$ on $h$ such that the four new points are within distance $1$ of each other and the two original points. We assume wlog $b$ is between $a, c$ and $B$ is between $A, C$.
Then we can construct $X$ by intersecting the short (length $< 1$) lines $Ab, Ba$, and construct $Z$ by intersecting the short lines $Bc, Cb$. Then $Y$ can be constructed by intersecting the short lines $XZ$ and $Ca$.
Now, $Y$ is positioned collinear with $A$ and $c$ and between them, so we can use it as a 'stepping stone' to draw a straight line between $A$ and $c$.
The result follows.
EDIT: I decided to do this with the edge of a coaster and two points slightly too far apart to be joined directly: