24
$\begingroup$

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?

  • 0
    https://www.youtube.com/watch?v=p-xa-3V5KO8&list=WL&index=2522018-01-26

4 Answers 4

26

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.)

  • 1
    @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.2010-10-25
9

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."

  • 0
    @Qiaochu: _Very_ thorough!2010-11-10
3

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.

1

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.

  • 0
    The paper cited by T.. proves that in case B you hit a tree within $1/\delta$2010-10-25