# You are standing at the origin of an “infinite forest” holding an “infinite bb-gun”

I use stories like these to develop intuition... or perhaps to destroy it. I have my own answers in mind, but I want to see if I have made any mistakes...

You are standing at the origin of an "infinite forest" holding an "infinite bb-gun." The "trees" in this forest are at the lattice points all around you. (The lattice points are like those on graph paper and they align with the cardinal directions: N, S, E, W.) The "forest" is Euclidean in the sense that the trees have no width. To hit a tree with your bb-gun you must aim perfectly at it.

You would, for example, hit a tree if you fired the gun due north, south east or west. (Your bullets also have no width.)

A. You fire the gun in an arbitrary direction without bothering to aim. What happens?

B. You get a new bb-gun and the bullets have a little width to them. ($\delta$?) You fire the gun in an arbitrary direction without bothering to aim. What happens?

C. All of the trees are removed that have coordinates whose absolute values are not perfect squares. (So, only points such as $(25, 100)$ and $(4,-1600)$ remain.) Again you use width-less bullets. You fire the gun in an arbitrary direction without bothering to aim. What happens?

D. Again, only with perfect squares, but now the bullets have width. What happens?

-
I believe it's discouraged here to create extremely narrow tags that are unlikely to be used by many questions, so I think the tag triples should be removed. I don't even see how it relates to the question. – Rahul Oct 24 '10 at 0:27
I was thinking pythagorean triples. I'll change it to that. – futurebird Oct 24 '10 at 5:10
@a little don: I'm not sure you get a notification when an answer is edited, so I'm letting you know I edited my answer to include the solution to D. – Qiaochu Yuan Oct 24 '10 at 15:14

A., C. The probability that you hit a tree is $0$. This is equivalent to the statement that the set of angles at which you can see a tree is of measure zero in $[0, 2\pi)$ with the Lebesgue measure, which follows because it is countable.

B. The probability that you hit a tree is $1$. By Dirichlet's approximation theorem, for any real $\alpha$ there exist infinitely many pairs $p_n, q_n$ of integers such that $|\alpha - \frac{p_n}{q_n}| < \frac{1}{q_n^2}$. It follows that the distance between the points $(q_n, q_n \alpha)$ and $(q_n, p_n)$ is at most $\frac{1}{q_n}$, and since the sequence $q_n$ tends to $\infty$ it follows by letting $\alpha = \tan \theta$ where $\theta$ is the angle at which you fired that for any bullet size $\delta > 0$ we will hit a tree at $(q_n, p_n)$ where $q_n > \frac{1}{\delta}$.

D. The probability that you hit a tree is still $1$. This is a consequence of the following theorem, which I just learned about by asking this MO question.

Theorem (Khinchin): Let $\phi(q) : \mathbb{N} \to \mathbb{R}$ be a monotonically decreasing function. For almost all real numbers $\alpha$, the number of pairs of positive integers $(q, p)$ satisfying

$$\left| p - q\alpha \right| < \phi(q)$$

is infinite if $\sum \phi(q)$ diverges, and finite if $\sum \phi(q)$ converges.

In particular, taking $\phi(q) = \frac{1}{q \ln q}$ (the sum of which diverges, for example by the integral test), we get that for almost all real $\alpha$ there are infinitely many solutions $(q, p)$ to

$$\left| \frac{p}{q} - \alpha \right| < \frac{1}{q^2 \ln q}.$$

Now let $\alpha = \sqrt{\tan \theta}$. With probability $1$ there will be infinitely many $(q, p)$ satisfying the above condition. Then

$$\left|p^2 - q^2 \tan \theta \right| < \frac{\left| \frac{p}{q} + \sqrt{\tan \theta} \right|}{\ln q}.$$

By taking $q$ large enough so that the RHS is less than $\frac{\delta}{2}$ it follows that a bullet shot at angle $\theta$ will hit the tree at $(q^2, p^2)$. (I'm only working in the positive quadrant but the generalization to the other quadrants should be clear.)

-
@Qiaochu: For B, I wonder how far the bullet would travel before hitting a tree, as a function of the bullet radius $\delta$? – Joseph O'Rourke Oct 24 '10 at 0:54
The probability that you hit a tree is 0 means that you could still hit it right? – PEV Oct 24 '10 at 1:00
@Trevor: yes. After all, there exists at least one tree. – Qiaochu Yuan Oct 24 '10 at 1:06
Your answer for D is more through. I had thought the answer to D would be "you hit a tee with probability 1" becuase of this: math.stackexchange.com/questions/7143/… – futurebird Oct 25 '10 at 11:53
@a little don: no, it's more subtle than that. The problem is that the angle that the bullet subtends decreases as it travels. If I'm not mistaken there are many angles at which you won't hit a tree for sufficiently small delta; see the answer to the MO question I linked to. – Qiaochu Yuan Oct 25 '10 at 12:55

Interestingly, the fraction of the lattice points that you could hit (in question A—not what you asked) from the origin is $$6 / {\pi}^2$$ or about 61%. See Research Problems in Discrete Geometry, Peter Brass, W. O. J. Moser, János Pach, p.430, "Visibility problems for lattice points."

-
I have to say I keep getting surprised at the situations that number (or its reciprocal) pops up... – J. M. Oct 24 '10 at 0:49
@J. M.: why? This is the same situation as the others. – Qiaochu Yuan Oct 24 '10 at 1:07
@Qiaochu: After you go though the mathematics, it's clear why that should be the result, yes. Still, it's not entirely obvious (at least to myself) why it pops up. – J. M. Oct 24 '10 at 5:19
$\frac{\pi^2}{6}=\sum_{n=1}^\infty\frac{1}{n^2}$. – futurebird Oct 24 '10 at 5:31
@J. M.: if one places the probability distribution on the positive integers which assigns a number n the probability n^{-s}/zeta(s) (the one coming from the Riemann zeta function), then the probability that two integers are relatively prime is 1/zeta(2s). This is the limit as s approaches 1. See my answer at math.stackexchange.com/questions/540/… . – Qiaochu Yuan Oct 24 '10 at 9:16

The problem with trees of finite width at all lattice points is called "Polya's Orchard Problem". Other variants such as higher dimensions and different shapes of the orchard are in the literature under the same name, or variations on visibility, lattice point, and orchard. Sample search result:

http://www.rose-hulman.edu/mathjournal/archives/2006/vol7-n2/paper9/v7n2-9pd.pdf

For the problem with zero-width trees and visibility from the origin (ie., primitive lattice points) I think the $6/\pi^2$ density is attributed to Chebyshev in the 1800's, but it seems like the type of result that could have been known considerably earlier and frequently rediscovered.

-

B. in the annulus from $r$ to $r+dr$ there are $2*\pi *r*dr$ trees. If we move the diameter from the bullet to the trees, they subtend an angle $\delta*2*\pi*r*dr/r$. This reaches $2\pi$ at $r=1/\delta$, so that is about where we would expect to hit a tree. As the integral diverges, we are guaranteed to hit a tree.

D. If we make the tree size δ it subtends an angle $\delta /\sqrt {i^4+j^4}$ Does the sum of this diverge? We need it to exceed $\pi /2$ as I have just covered the first quadrant.

-
I don't understand what i and j are in D. In any case I don't think this type of argument can work for D; it's much more subtle than that. – Qiaochu Yuan Oct 24 '10 at 1:02
i and j range over N. Each tree is at (i^2,j^2). I just realized (seeing Joseph O'Rourke's comment) that I have ignored the fact that some trees hide others. – Ross Millikan Oct 24 '10 at 1:08
Ross, can you identify your variables... starting with d? I'm a little lost reading this response. – futurebird Oct 24 '10 at 5:33
@Ross: you really should think harder about D. The points are too sparse for an area-based argument to work without a lot more effort. – Qiaochu Yuan Oct 24 '10 at 9:18
@a little don: in part B I was counting trees in a small annulus starting at radius r and going to radius r + dr. As they are all at the same distance (within dr), they subtend the same angle. I used the fact that there is one tree per square unit. For D I listed the trees by i and j, the square roots of their coordinates and again tried (but failed) to add up the angle they subtend. Qiaochu has an answer above using a better theorem. My tools weren't good enough. – Ross Millikan Oct 24 '10 at 15:14