Geometry — page 5
The busiest point in a set
Scatter points in the plane, not all on one line, and draw every line through two of them. Some point lies on many of those lines — but how many must? Gabriel Dirac guessed half: in any such set, some point is on about half of the lines it could be on. Split the points evenly between two lines and no point does better than half plus one, so the guess cannot be raised. Proving it is another matter. Seventy years on, the best theorem says a third.
Rounding to the nearest remainder
Euclid's algorithm divides and keeps the remainder, and the remainder it keeps is the one left after rounding the quotient down. Rounding to the nearest instead — allowing a remainder to be taken from above — never takes more steps, and Kronecker proved that no mixture of rounding up and down does better. On average it saves three steps in ten, the ratio of the logarithms of the golden ratio and of two. And its slowest inputs are not Fibonacci numbers but Pell numbers, because the worst case of each algorithm is the number its own kind of continued fraction expands most slowly: the golden ratio for one, the square root of two for the other.