42nd Putnam 1981 Problem A4 A particle moves in a straight line inside a square side 1. It is reflected from the sides, but absorbed by the four corners. It starts from an arbitrary point P inside the square. Let c(k) be the number of possible starting directions from which it reaches a corner after traveling a distance k or less. Find the smallest constant a 2 , such that from some constants a 1 and a 0 , c(k) ≤ a 2 k 2 + a 1 k + a 0 for all P and all k. Solution
: π. By a series of reflections we can transform the path into a straight line. The particle reaches a corner iff the transformed line passes through a lattice point. So the number of directions which lead to absorption in a distance k or less is the number of lattice points in a circle radius k. At least that would be true except for the shadowing problem - the starting point may lie on a line of lattice points in which case it could never reach the ones further out. Shadowing reduces the number of lattice points in the circle that we should count, so the number of lattice points is still an upper bound. Evidently what we need are some estimates for the number of lattice points in the circle. They do not need to be good estimates - we only need the highest power to be correct. We can regard each lattice point as the centre of a unit square. The resulting unit squares tile the plane. The circle radius k has area πk 2 , so it contains around πk 2 of the unit squares and hence around πk 2 lattice points. However, the squares around the edge may be incomplete and the incomplete squares may or may not include their centres. The maximum distance between two points of a unit square is √2, so the circle radius k + √2 contains the entirety of any square which overlaps the circle radius k. Hence the number of lattice points in the circle radius k is at most π(k + √2) 2 . Thus if we take a 2 = π, a 1 = 2π√2, a 0 = 2π, then c(k) ≤ a 2 k 2 + a 1 k + a 0 for all P and k. Similarly, any unit square overlapping the circle radius k - √2 is entirely contained in the circle radius k. There are at least π(k - √2) 2 such squares, so the circle radius k contains at least π(k - √2) 2 lattice points. Take a coordinate system with axes parallel to the sides of the squares. Then all lines joining lattice points have rational slope, so if we take the point P to have one coordinate rational and the other irrational, it cannot lie on any such lines. Thus for these points there is no shadowing problem and the number of directions is at least π(k - √2) 2 . This shows that π is the minimal value of a 2 (because for any smaller value and any a 1 , a 0 we would have a 2 k 2 + a 1 k + a 0 < π(k - √2) 2 for sufficiently large k). 42nd Putnam 1981 © John Scholes jscholes@kalva.demon.co.uk 16 Jan 2001