25
$\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?

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – user856
    Oct 24, 2010 at 0:27
  • $\begingroup$ I was thinking pythagorean triples. I'll change it to that. $\endgroup$
    – futurebird
    Oct 24, 2010 at 5:10
  • 1
    $\begingroup$ @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. $\endgroup$ Oct 24, 2010 at 15:14
  • $\begingroup$ numberphile did a video on this $\endgroup$
    – futurebird
    Jan 26, 2018 at 17:45
  • $\begingroup$ youtube.com/watch?v=p-xa-3V5KO8&list=WL&index=252 $\endgroup$
    – futurebird
    Jan 26, 2018 at 17:45

4 Answers 4

28
$\begingroup$

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

$\endgroup$
6
  • 2
    $\begingroup$ @Qiaochu: For B, I wonder how far the bullet would travel before hitting a tree, as a function of the bullet radius $\delta$? $\endgroup$ Oct 24, 2010 at 0:54
  • 1
    $\begingroup$ The probability that you hit a tree is 0 means that you could still hit it right? $\endgroup$ Oct 24, 2010 at 1:00
  • $\begingroup$ @Trevor: yes. After all, there exists at least one tree. $\endgroup$ Oct 24, 2010 at 1:06
  • 1
    $\begingroup$ 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/… $\endgroup$
    – futurebird
    Oct 25, 2010 at 11:53
  • 1
    $\begingroup$ @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. $\endgroup$ Oct 25, 2010 at 12:55
10
$\begingroup$

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

$\endgroup$
8
  • 4
    $\begingroup$ I have to say I keep getting surprised at the situations that number (or its reciprocal) pops up... $\endgroup$ Oct 24, 2010 at 0:49
  • 1
    $\begingroup$ @J. M.: why? This is the same situation as the others. $\endgroup$ Oct 24, 2010 at 1:07
  • 5
    $\begingroup$ @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. $\endgroup$ Oct 24, 2010 at 5:19
  • $\begingroup$ $\frac{\pi^2}{6}=\sum_{n=1}^\infty\frac{1}{n^2}$. $\endgroup$
    – futurebird
    Oct 24, 2010 at 5:31
  • 2
    $\begingroup$ @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/… . $\endgroup$ Oct 24, 2010 at 9:16
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 24, 2010 at 1:02
  • $\begingroup$ 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. $\endgroup$ Oct 24, 2010 at 1:08
  • $\begingroup$ Ross, can you identify your variables... starting with d? I'm a little lost reading this response. $\endgroup$
    – futurebird
    Oct 24, 2010 at 5:33
  • $\begingroup$ @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. $\endgroup$ Oct 24, 2010 at 9:18
  • 1
    $\begingroup$ @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. $\endgroup$ Oct 24, 2010 at 15:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .