wu :: forums « wu :: forums - Infinite Grid of Sticks » Welcome, Guest. Please Login or Register. Jan 17th, 2022, 4:50pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Icarus, towr, ThudnBlunder, Grimbal, william wu, Eigenray, SMQ)    Infinite Grid of Sticks « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Infinite Grid of Sticks  (Read 1125 times)
william wu

Gender:
Posts: 1291
 Infinite Grid of Sticks   « on: Dec 10th, 2003, 10:26pm » Quote Modify

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?)
 IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Infinite Grid of Sticks   « Reply #1 on: Dec 11th, 2003, 12:29am » Quote Modify

::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. ::
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: Infinite Grid of Sticks   « Reply #2 on: Dec 11th, 2003, 12:37am » Quote Modify

6/pi2 it is then.
 « Last Edit: Dec 11th, 2003, 12:38am by Eigenray » IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Infinite Grid of Sticks   « Reply #3 on: Dec 11th, 2003, 12:41am » Quote Modify

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)
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: Infinite Grid of Sticks   « Reply #4 on: Dec 11th, 2003, 12:52am » Quote Modify

Roughly, the probability that m and n are both divisible by p is 1/p2, and since these are independent for p prime, the desired probability is:
[prod]p prime (1-1/p2)
= 1/[prod]1/(1-1/p2)
= 1/[prod](1+1/p2 + 1/p4 + . . . )
= 1/[sum]n=1[infty] 1/n2 = 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 has that dead horse pretty beat (see "Evaluating zeta(2)").
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Infinite Grid of Sticks   l1_855.gif « Reply #5 on: Dec 11th, 2003, 1:24am » Quote Modify

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..
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: Infinite Grid of Sticks   « Reply #6 on: Dec 11th, 2003, 4:29am » Quote Modify

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=1r[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?
 IP Logged
SWF
Uberpuzzler

Posts: 879
 Re: Infinite Grid of Sticks   « Reply #7 on: Dec 11th, 2003, 5:11pm » Quote Modify

This is related to Coprimaility of Two Randomly Chosen Integers and Random Line Segment in Square.
 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »