Counting the same thing twice — page 13
Applied
A core is a rare thing to find at random
A game has a core when the whole can be shared so that no group would do better on its own, and Bondareva and Shapley turned that into a finite list of checks. For three players there are five checks; for four, forty-one; for five, 1,291. Draw the coalitions' values at random and the list wins: a third of three-player games fail, nineteen four-player games in twenty, and not one five-player game in two thousand passes. The cores that theorems promise come from structure, and structure is exactly what a random game lacks.
Geometry
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.
Number
How close two sums of square roots come
Two different sums of square roots of whole numbers are never equal: square roots of different squarefree numbers are independent, so no cancellation can make them agree. But they can come very close. Among sums of two square roots of numbers up to 320, √88 + √289 and √171 + √177 agree to eight decimal places. How many digits must be computed, in the worst case, to tell two such sums apart is not known — the best proof allows a number of digits doubly exponential in the length of the sums, the examples suggest only a modest polynomial, and the gap between them is why nobody knows whether the shortest route through points in the plane can be checked quickly.