wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Infinite Grid of Sticks
        
(Message started by: william wu on Dec 10^th, 2003, 10:26pm)

Title: Infinite Grid of Sticks
Post by william wu on Dec 10^th, 2003, 10:26pm

Imagine planting a pole into every point with integral coordinates on the 2D cartesian plane, except for the origin at (0,0). Now imagine that you are standing exactly at the origin. You cannot move from the origin, but you are allowed to rotate in place.

What proportion of the infinitude of sticks are visible to your eyes? (In other words, what proportion of the sticks could you hit by shooting a unobstructed ray from the origin?)

Title: Re: Infinite Grid of Sticks
Post by towr on Dec 11^th, 2003, 12:29am

::[hide]My first guess would be about the proportion that is relatively prime, since any (x,y) blocks the view of (ax,ay) for integers a > 1. [/hide]::

Title: Re: Infinite Grid of Sticks
Post by Eigenray on Dec 11^th, 2003, 12:37am

[hide]6/pi²[/hide] it is then.

Title: Re: Infinite Grid of Sticks
Post by towr on Dec 11^th, 2003, 12:41am

yep.. That's what I found at mathworld as well..
I'm not sure how to derive it though.. I can't find Castellanos' paper online anywhere either.. (The only calculation I can find isn't much better than just giving the answer)

Title: Re: Infinite Grid of Sticks
Post by Eigenray on Dec 11^th, 2003, 12:52am

Roughly, the probability that m and n are both divisible by p is 1/p², and since these are independent for p prime, the desired probability is:
[prod]_{p prime} (1-1/p²)
= 1/[prod]1/(1-1/p²)
= 1/[prod](1+1/p² + 1/p⁴ + . . . )
= 1/[sum]_n=1^[infty] 1/n² = 1/[zeta](2),
since there is a 1-1 correspondence of terms in the product and the sum by the fundamental theorem of arithmetic.
As for evaluating [zeta](2), Robin Chapman (http://www.maths.ex.ac.uk/~rjc/rjc.html) has that dead horse pretty beat (see "Evaluating zeta(2)").

Title: Re: Infinite Grid of Sticks
Post by towr on Dec 11^th, 2003, 1:24am

Here's another calculation, which I found at http://www.itu.dk/bibliotek/encyclopedia/math/l/l111.htm

I think N(r) is the same as in http://mathworld.wolfram.com/CircleLatticePoints.html
But I'm not sure why N'(r)/N(r) would give the right answer..

Title: Re: Infinite Grid of Sticks
Post by Eigenray on Dec 11^th, 2003, 4:29am

If I had to guess, I'd say that N(r) is the number of lattice points in a square of side 2r centered at the origin, and N'(r) ~ 4r[sum]_k=1^r[phi](k)/k is the number of those which are visible.

Related problem: Show that there are arbitrarily large circles such that all the poles in the circle are invisible.

Related problem: Suppose now that the poles are cylinders with a radius r>0. What's the maximum distance you can see?

Title: Re: Infinite Grid of Sticks
Post by SWF on Dec 11^th, 2003, 5:11pm

This is related to Coprimaility of Two Randomly Chosen Integers (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1061500629) and Random Line Segment in Square (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1049132168).