Polya's Orchard Problem

Author(s): Thomas Tracy Allen

Source: The American Mathematical Monthly, Vol. 93, No. 2 (Feb., 1986), pp. 98-104
Published by: Mathematical Association of America
Stable URL: http://www.jstor.org/stable/2322700 .
Accessed: 12/01/2015 20:10

Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at .
http://www.jstor.org/page/info/about/policies/terms.jsp

.
JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of
content in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new forms
of scholarship. For more information about JSTOR, please contact support@jstor.org.

Mathematical Association of America is collaborating with JSTOR to digitize, preserve and extend access to
The American Mathematical Monthly.

http://www.jstor.org

This content downloaded from 128.235.251.160 on Mon, 12 Jan 2015 20:10:57 PM

All use subject to JSTOR Terms and Conditions
98 THOMASTRACYALLEN [February

Conclusion.The geometric methodgenerates thecorrectdistribution of Irlwhenp = 0. As a

of Fisher[3, p. 657]:
distribution
matterof fact,it is identicalto thefrequency
r(( no 1)/2) - -4)/2 .
df= F((no - 2)72)17(1/2)-(I - r2)P dr

thevalueof P in equation(3) is
For thisdensityfunction
P = I - r2)(no-4)/2dr f( - d

Substituter = cos u, n = no - 3 and equation(3) follows.

References

1. J. Durbin and M. G. Kendall,The geometry of estimation,Biometrika, 38 (1951) 150-158.

2. R. A. Fisher, Frequencydistributionof the values of the correlationcoefficientin samples from an
indefinitely 10 (1915) 507-521.
large population,Biometrika,
3. , The generalsamplingdistributionof the multiplecorrelationcoefficient, Proc. Roy. Soc. London,
121 (1928) 654-673.
4. Harold Hotelling,Tubes and spheresin n-space,and a class of statisticalproblems,Amer.J.Math.,61 (1939)
440-460.
5. coefficient
, New lighton thecorrelation and its transforms,J. Roy. Statist.Soc., 15 (1953) 193-232.
6. Dunham Jackson,Mathematicalprinciplesin thetheoryof smallsamples,thisMONTHLY, 42 (1935) 344-364.

POLYA'S ORCHARD PROBLEM

THOMAS TRACY ALLEN

201 WellmanHall, University
ofEntomology,
Department CA 94720
Berkeley,
ofCalifortnia,

1. Introduction. "How thickmustthetrunks of thetreesin a regularlyspacedcircularorchard

growif theyare to blockcompletely theviewfromthecenter?"(P6lyaand Szego[6].)
Let thetreesbe circular columns,all ofwhichhavethesameradiusr,so theproblemsimplifies
to one of circleson a plane.Let thecirclesbe centeredat integer-valued x and y coordinates,
satisfying(X2 + y2)1/2 < s, s theradiusof theorchard.A rayis a straight lineof sightfromthe
origin,(0,0). The firstcircleintersectedby a givenrayis visiblealongthatray.The problemis to
finda radiusof thetrees,p, suchthatforr > p onlytreescentered withintheorchardarevisible,
but suchthat forr < p thereis a view out alongat leastone ray. Of course,p willbe a function
of s.
The solutionby G. Polya,based on a methoddue to A. Speiser(reference cited above,
originallyin G. Polya[5]),and thesolutionby R. Honsberger [4],based on Minkowskii's Convex
Body Theorem,bothleave uncertainty about thevalue of p. Theyshowthatif s is an integer,
then
(1) 1/(S2 + 1)1/2 < p < l/s.
But whatis theexactvalueof p? And whatis p whens is notan integer?

ThomasTracyAllen: I receivedmyPh.D. in biophysicsfromtheUniversity of California,Berkeley.A fascination

with the intricatedynamicsof insectpopulationsled me to the mathematicsof coupled nonlinearoscillators,and
thencea circuitouspath not untypicalof scienceled me to the orchardproblemas I presentit here. My current
vocation is electronicinstrumentatiQn, applied to monitoringanimal populationsand theirenvironments. I have
threesons, ages 2, 4, and 8, whose favoriteorchardproblemis "hide-and-seek".

This content downloaded from 128.235.251.160 on Mon, 12 Jan 2015 20:10:57 PM

All use subject to JSTOR Terms and Conditions
1986] POLYA'S ORCHARD PROBLEM 99

o CLO@ of0

o o 0n
00 0SX 0 00

FIG. 1. Raysplottedto theirendpointson circles,

r .25.

y~~~~~~~~~xl

0 x
FIG. 2. To calculatethedistancer' from thelatticepoint(x', y') to theraysubtending theangle9, notethat
r' = h' cos0 and h' = V' - x' tan9, so r' = y' cos9 - x' sinG. If theraypassesthrough a latticepoint,(x, y), then
sino= y/(y2 + x2)1/2, COS9 = x/(y2 + X2)1/2 and equation (2a) follows-similarly forequation (2b). To
calculate0 givenr" and 4, where4 = arctany"/x", note that0 - 4 = arcsinr"/(x"2 + y"2)1/2. The
inequality of(7d) followsdirectly-similarly fortheotherinequalities (7a), (7b),and(7c).

Here I show,usingelementary methods,thatp = 1/ FX, whereX is thefirstintegergreater

than S2 thatcan be writtenas a sum of thesquaresof two coprimeintegers. If s is itselfan
a coupleof related
integer,thenequalityon thelefthand side of (1) is exact.I also formulate
problems,to showotheraspectsof thisprettyorchard.
2. Preliminaries.Observethefollowing: symmetry,
(1) The problemhas eightfold due to the
eightcirclesnearesttheorigin.See Fig. 1. It sufficestoconsideronlythefirst where
half-quadrant,

This content downloaded from 128.235.251.160 on Mon, 12 Jan 2015 20:10:57 PM

All use subject to JSTOR Terms and Conditions
100 THOMAS TRACY ALLEN [February

x > y > 0, (x, y) + (0,0). (2) Onlycirclescenteredat coprimecoordinatescan everbe visible.

For example,thecircleat (2,2) is totallyeclipsedby thecircleat (1,1), independent of r. (3) In
thelimitof r = 0, all circles-nowpoints-havingcoprimecoordinates are visible;theyare first
out along a ray. (4) At the otherlimit,when r = 1/2, the circlestouch,and only the circles
centeredat (1,0) and (1,1) (and theirimagesin thefourquadrants)are visible.
Considertheraythrough lyingaboveand belowthatray:(x', y')
(x, y) and thelattice-points
y'/x' > y/x,and (x", y") satisfying
satisfying y"/x" < y/x. The perpendicular distancesfrom
thesepointsto therayare,in normalform(see Fig. 2),

(2a) r' (y'x xy)/(X2 + y2)1/2

and
r" = (xy _
(2b) Y,,X)I(X2 + y2)1/2

When x, y are coprime(i.e.,theirgreatestcommondivisoris 1), themoduliin thenumerators

the
of the(x', y') and the(x", y"). Therefore,
take on all positiveintegralvaluesas functions
pointsclosestto therayare givenby
(3a) y'x - x'y = I1
and
(3b) x"y - y"x= +1,
distanceof
givinga minimum
(4 = = (X2 + y2)-1/2

Equations (3a) and (3b) are indeterminate; theyhave infinitely manysolutions.These are
(kx + x', ky + y') and (kx + x", ky+ y"), respectively,wherek is anyinteger, and (x', y') and
these
solutions.Collectively,
(x", y") are particular points lie on two lines parallelto therayand
equidistantat the minimum distancegivenby (4) on either side of it. For we wantthe
visibility,
solutionsthatare closerto theoriginthanis (x, y), and in thesamequadrant,say,
(5a) 0 s< x' < x
and
(5b) 0 < y" <y.

There exists exactlyone coordinate-pair,(x', y'), satisfying(3a) in the intervalgiven by (5a).

To see this,observethat(kx + x', ky+ y') placesexactlyone solutionin eachhalf-open interval
(x", y") is determined
of lengthx. Similarly, uniquelyby (3b) in theinterval
given by (Sb).
The abovereasoning showsthatthecirclescentered at thetwopointsdetermined by(3) and (5)
and havingthe radius(4) are tangentto theray through (x, y). Also, therayhitsbothof the
pointsof tangencybeforeit intersects anypointof thecirclecenteredat (x, y). To verifythis,
fromthePythagorean Theorem, thedistancesfromthepointsof tangency out to (x, y) alongthe
rayare

[X i2 + y"2 - 1/(X2 + y2)]1/2 and [x,2 + y'2 -

1/(X2 + y2)]'/2.

The minimum such distance occurs for (x, y) = (2, 1), (x", y") = (1,0), so the distance must
alwaysbe greaterthanor equal to [12 + 02 - 1/(22 + 12)]41/2 = 2/ r/. Butfrom(4), theradius
is less,namely,less thanor equal to (22 + 12) -1/2 = 1/ .
of thecirclesat tangency
In conclusion,thegivencirclecenteredat coprime(x, y) is visiblealongat least one rayso
longas r < (x2 + y2)-1/2, butitis totally whenr > (x2 + y2)-1/2.
eclipsed
3. The orchardproblem.Now we are readyto stringa fenceat a finiteradius,s, aroundthe

This content downloaded from 128.235.251.160 on Mon, 12 Jan 2015 20:10:57 PM

All use subject to JSTOR Terms and Conditions
1986] POLYA S ORCHARD PROBLEM 101

observation postat theorigin.To start,supposethatthefenceis an imaginary circlein an orchard

thatextendsto infinity all around.Whatis theradiusof thetrees,r = p, thatjust blockstheview
of all thetreesbeyondthefence?
From(4), each treebecomestotallyeclipsedwhenr equals thereciprocal of thedistanceofits
centerfromtheorigin.Therefore, thelast treeoutsidethefenceto be totallyeclipsedas thetrees
growmustbe theone closestto thefenceon theoutside.All treesfarther fromtheoriginwere
alreadyeclipsedat smallerr. Thus thereciprocalof thedistanceto thecenterof thetreeclosest
outsidethefenceis thedesiredp. Q.E.D.
The reasoningdoes not dependon havingactual treesoutsidethe fence,because the final
visibility dependsonlyupon thetreesinside.
If s is an integer, thens2 + 1 is thefirstintegergreaterthans2, and thereis alwaysa tree
centeredat (s, 1), (s2 + 1)1/2 unitsfromtheorigin.The criticalradiusfortheviewto theoutside
is therefore r = p = (s2 + I)-1/2. Theremaybe othertreesat thesamecriticaldistancefromthe
origin.For example,if s = 50, then(50,1), (49,10) and 14 imagesof thesetwopointslocatedin
thefourquadrantswouldall disappearat exactlythesameradius,r = p = 1/ 2501.
Note thatthe expression, p = (s2 + 1)-1/2, we have foundhereis thesame as thaton the
left-hand side of (1). The equalitythereis exact,so longas s is an integer.
If s is not necessarily an integer, a moreilluminating wayto statetheproblemis, "Whatis p
as a function of s?" Again,let x and y be arbitrary coprimeintegers. Then X2 + y2 = X iS, ipso
facto,a specialkindofinteger, one thatcan be represented as a sumofthesquaresoftwocoprime
integersin at least one way. Suppose XAand Xi+, are two successiveintegersof thiskind,
XI < Ai+ Then for X, < s < FX I, the criticalradius p mustbe constant,and it musthave the
value p = 1/ <X1, because <X11 is thedistanceto thefirstcenterbeyondthefence.Or to put
it anotherwayindependent of s: For 1/ X, 1 < r < 1/ FX,,thefarthest treevisibleis centered
X1 unitsfromtheorigin,becausethetree X unitsfromtheoriginis alreadyeclipsedwhen
r = 1/ X1 1.
To illustrate,in Fig.3 I havelistedpairsofcoprimeintegers in orderofincreasing X = X2 + y2.
The connecting lineson thefigureemphasizethateach treecan be eclipsedby exactlytwoothers
lyingnearertheorigin.Now,65 and 73 are successiveX,interesting because65 is thefirstinteger
thatcan be written as thesumof thesquaresof twocoprimeintegers in twodifferent ways.For
1/ 73 < r < 1/ 65, thefarthest treesvisibleare theones at (8,1) and (7,4) (and theirimages
in thefourquadrants).Werer > 1/ 65 thesewoulddisappearsimultaneously. And werewe to
stringa fenceat anyradiusin theinterval,61 < s < 65, thecriticalradiusfortheviewout
wouldbe r = p = /1 65 .
4. The continued fraction.Supposewe gaze permanently alonga singlerayas thetreesgrow.
Whichtreeswillwe see?
Let us expand the slope of the ray,tan0, into its continuedfraction.If p,l/q,,is the nth
convergent,thenwe knowthatpn/qnis a betterrationalapproximation to theslope of theray
thanall fractions
havingdenominators less thanor equal to q,1.That is, (Hardyand Wright[3,
Theorem181]) if n > 1, 0 < q < qn,and p/q + p,l/q,l,then

(6) lp, - q,tan0J< p - qtan0j.

In geometricterms,(6) says thattheverticaldistancefrom(q,1,p,1)to therayis less thanthe

verticaldistancesfromanyofthenamed(q, p) to theray.The verticaldistancesare theh on Fig.
2, includingboththeh' above and theh" belowtheray.Multiplying bothsidesof (6) by cos0
gives expressionsfor the perpendicular distances,the r. Since cos 0 is positivein the first
quadrant,theconclusionof thetheorem carriesoverto theseperpendicular distances:The point
(q,,,p,) is closerto theraythanare anyof the(q, p).
Also we knowthatq, < qn+1, so thissametheorem assuresus that(q,,?1' P, +1) is closerto the
ray thanis (q, pj), forall n. Completingthe reasoningas before,the circlescenteredat the

This content downloaded from 128.235.251.160 on Mon, 12 Jan 2015 20:10:57 PM

All use subject to JSTOR Terms and Conditions
102 THOMAS TRACY ALLEN [February

X2+y2 X,y

1 1,0
211
5 2,1

13 /32
17 4,1
25 /4,3
26
29 /
5,1
5,2
37 6,11
41 15,4
50 7,1
53 1 7,2
58 Ii
61 j6,5
65 8,11 7,4
73 8,3
FIG. 3. The points (x, y) are listedin orderof increasingx2 + y2. The connectinglines emphasizethatthe circle
centeredat each of thesepointswill be eclipsedby exactlytwo otherscenteredcloser to the originas the radius
increases.

points, , (qtl+A1,p11+,) (qC,,pn) (q,-i' 1

A-1),*.. are the ones visiblealong the ray in sequence as
r increases.
The numberof convergents and of visibletreesis finiteif tan0 is rational,becausewe are
lookingrightat a latticepointwhenr = 0. To be correct, thecontinuedfraction mustbe written
with the final coefficient greaterthan one. Otherwise,as a simple calculationshows,the
next-to-the-last and thesecond-to-the-last convergentsgivepointsthatareequidistant on opposite
sidesof theray.Butonlythecirclecloserto theoriginis evervisiblealongthatray.For example,
the convergents of 21/16 = [1,3,4,1] are 1/1, 4/3, 17/13 and 21/16. But onlythe circlesat
(1, 1), (3,4) and (16,21) are evervisiblealongtana = 21/16. So we write21/16 = [1,3,5].
If tan0 is irrational,
thenumberof convergents For example,if
and of visibletreesis infinite.
theslopeis tan0 = (Vi+ 1)/2, thesequenceof circlesvisibleas a function of decreasing
radius,
forr < 1/2, wouldbe theFibonaccisequence(1,1),(1,2),(2,3),(3, 5),(5, 8),(8,13), etc.Note that
the tree at (0, 1) would not be visiblealong that ray unless the treesoverlap,unless r >
2t(- + 1)2 + 22}-1/2 = .53.
5. Single trees.I claim that the circlecenteredat arbitrary, coprime(x, y), x > y > 0,
(x, y) + (0,0) and forr < 1/2,is visiblethrough
theinterval of angles(relativeto thepositivex
of thefollowing
axis) givenby theintersection inequalities:
(7a) 0 < arctan y/x + arcsin r/(x2 + y2)1/

for0 < r < r+,

This content downloaded from 128.235.251.160 on Mon, 12 Jan 2015 20:10:57 PM

All use subject to JSTOR Terms and Conditions
1986] POLYA S ORCHARD PROBLEM 103

(7b) 0 < arctany'/x' - arcsinr/( X'2 + Y/2)1/2

for r+ <ro,
(7c) 0 > arctany/x - arcsinr/(x2 ? 2)1/
for0 < r < r-,
(7d) 0 > arctany"/x" + arcsinr/(x"2 + Y,,2)1/

forr-< r <r
wherex', y' and x", y" satisfy
(3) and (5), and where

r? = ( x2 + y2) -l/2,r+= [( x + X/)2+ ( y + Y')2] 1/2 and r= [(x + X",)2 + (y + Y/1)2|1/2

The reasoningof Section2 does not establishthisresult.I need to provethatthe circles
centeredat (x', y') and (x", y") determine notonlythecriticalradius,r?, fortotaleclipse,but
also all degreesof partialeclipseas claimed.

(X+ X y+Y')

(x
FIG. 4. Circles centeredat points (x', v') and (x, y), satisfying
(3a) and (5a), are tangentto the ray through
(x + x', v + y') when r = r+= {(x + x')2 + (y + V,)2}-l/2. Above this criticalradius, the former circle en-
croaches fromabove on thevisibility of the latter.The circlecenteredat (x*, Y*), y*/x* > Y'/x', is irrelevant.

Considertheconstruction shownon Fig. 4. Applyingtheformulae (2), we findthatthepoints

(x, y) and (x', y') are equidistant at theminimum distancer+ on eitherside of theraythrough
(x + x', y + y'). Therefore, whenr < r+ theupperpartof thecirclecenteredat (x, y) is visible
and (7a) appliesfortheupperboundon visibility. (I justifytheformof thefunctions of(x, y) and
r in the caption to Fig. 2.) However,when r+ r < ro, the lowerray tangentto the circle
centeredat (x', y') coincideswithraysin the wedgeshownshaded on Fig. 4. So the circle
centeredat (x, y) is partlyeclipsedfromabove.Observethatthepoint(x', y') is less than2r+
distantfromall of theraysin theshadedwedge.Otherpoints,(x*, y*), y*/x* > y/x,0 < x* <
x, are morethan2r+ distantfromraysin thewedge,becausethepointsof thelatticeare (from
the modulusin the expressionfordistance)spaced at multiplesof r+ fromthe ray through
(x + x', y + y'). Only(x', y') liesexactlyr+ abovetherayin theinterval [0,x). Thus(7b) is both
necessaryand sufficient to describetheupperboundon visibility when r+< r < ro. The same
reasoningappliesto theeffect of thecirclecenteredat (x", y"), as it eclipsesfrombelow,whence
(7c) and (7d) forthelowerboundon visibility.
On Fig. 5 I haveplottedthedomainsdefinedby(7a) through (7d) forenough(x, y) to convey
thepatternof tessellation of ther-8 plane.Ofcourse,everycoprime(x, y) wouldhavean areaon
thatplane,fillingit completely as x, y -s o.
6. Postscript.A problemof visibility
in a latticeof triangles
(insteadof circles)arisesfroma

This content downloaded from 128.235.251.160 on Mon, 12 Jan 2015 20:10:57 PM

All use subject to JSTOR Terms and Conditions
104 THOMASTRACY ALLEN

0~~~~~~~~0

al) Im=1_=

0 radius ^2
1/
FIG. 5. The intervalsof anglesthroughwhichdifferent circlesare visibleare functionsof the radiusof the circles.
Lettersbeside the ordinatescorrespondto circlescenteredat: a-(3, 5), b-v(3, 4), c-(4, 5), cl-(6, 5), e-(5, 4),
f-(4, 3), g-(7, 5), h-(8, 5), i-(5, 3), j-(7, 4), k-(7, 3), 1-(5, 2), mn-(8,3), n-(3,1), o-(7, 2), p-(9, 2),

simplemodel of coupledneurons,suchas theneuronsthatcoordinatethebeatingof theheart

(Allen[1]).The samelatticeis also a pretty
goodmodelofcertainelectronic circuits,
suchas those
thathold thepicturesteadyon television sets(Allen[2]).The solutionsaresimilarto theone given
here.For example,a diagramanalogousto Fig.5 depictshowone oscillator can lockontorational
multiplesof theperiodof a secondoscillator, depending on thestrengthof thecouplingbetween
themand on theratioof theirnaturalperiods,and indicateshow thislockingfairsagainstthe
destabilizing
effects
ofnoise.
Acknowledgements.
I thankR. Honsbergerforthoughtful
suggestions.

References
1. T. T. Allen, On the arithmeticof phase locking:coupled neuronsas a latticeon R2, Phys. D, 6 (1983)
305-320.
2. , Complicated,but rational,phase lockingresponsesof a simple time-baseoscillator,IEEE Trans.
Circuitsand Systems,30 (1983) 627-632.
3. G. H. Hardy and E. M. Wright,An Introduction to theTheoryof Numbers,ClarendonPress,Oxford,1979.
4. R. Honsberger,MathematicalGems I, Dolciani MathematicalExpositions,no. 1, Chap. 4, Mathematical
Associationof America,Washington, DC, 1973.
5. G. P6lya, Zahlentheoretisches und wahrscheinlichkeits-theoretisches
uber die sichtweiteim walde, Arch.
Math. und Phys.,27, Series2 (1918) 135-142.
6. G. P6lya and G. Szeg6,Problemsand Theoremsin Analysis,vol. 2, Chap. 5, Problem239, Springer-Verlag,
New York, 1976.

This content downloaded from 128.235.251.160 on Mon, 12 Jan 2015 20:10:57 PM

All use subject to JSTOR Terms and Conditions