Monday, August 14, 2023

Seeing the forest for the cylinders

You find yourself amidst what appears to be an infinite grid of trees. For the purposes of this puzzle, let’s suppose each tree is a perfect cylinder. You are at the point $(0, 0),$ but there’s a tree with a radius of $r_1 = 0.25$ units (and diameter $0.5$ units) centered at every other point in the plane with integer coordinates.

Of course, you can’t actually see infinitely many trees. Most of them are obscured by the trees immediately around you. As you look around in all directions, how many distinct trees are you able to see?

Let's set up the generic problem, with some unknown radius $r \gt 0,$ then we can try to solve each of the pieces of this fiddle, er, riddle.

Assume that I am sitting at the origin and I look along the line $y=m x.$ If we assume for the time being that each of these perfectly cylindrical trees were see through, then I could see a tree centered at $(a,b) \in \mathbb{Z}^2$ if and only if the set $$\{ (x,y) \mid y = mx, (x-a)^2 + (y-b)^2 = r^2 \} \ne \emptyset.$$ Simplifying a bit, I could see any tree centered at $(a,b)$ provided that $$(x-a)^2 + (mx - b)^2 -r^2 = (1+m^2) x^2 -2( a + bm) x + (a^2 + b^2 - r^2) = 0$$ has a solution, that is, if and only if the discriminant \begin{align*}0 \leq \Delta( m \mid a, b, r ) &= 4(a + bm)^2 - 4(1 + m^2) (a^2 + b^2 - r^2) \\ &= 4 ( -(b^2 - r^2) + 2 ab m - (a^2 - r^2) m^2 ).\end{align*} Rearranging a bit, and solving for $m$ we see that these translucent trees would be visible if and only if $$\frac{ab - r \sqrt{(a+b)^2 - r^2}}{a^2 - r^2} \leq m \leq \frac{ab + r \sqrt{(a+b)^2 - r^2}}{a^2 - r^2}.$$ However, since we don't have translucent cylindrcal trees, if we are looking along $y = mx$ then we could only see the two trees in $$(\hat{a}(m), \hat{b}(m)) \in \arg\min \left\{ |a| + |b| \left|\right. \frac{ab - r \sqrt{(a+b)^2 - r^2}}{a^2 - r^2} \leq m \leq \frac{ab + r \sqrt{(a+b)^2 - r^2}}{a^2 - r^2} \right\}.$$ Due to all of the symmetry of this problem, only method is to allow $m$ to slowly increase from $m = 0$ to $m = 1,$ and then rely on symmetry (since there is nothing uniquely special about the trees in the lower half of the first quadrant) and inclusion/exclusion (since some of the trees will be double counted) to answer either the question of how many tress do we see or which trees is furthest away.

So in particular, we see that for $m \in [0, \frac{r}{\sqrt{1-r^2}}],$ I would be looking at the tree at $(1,0).$ Similarly, for any $m \in [\frac{1-r\sqrt{2-r^2}}{1-r^2}, 1],$ I would be looking at the tree centered at $(1,1).$ So in particular for $r = 0.25,$ we have filled in the set $$ m \in [0, \frac{\sqrt{15}}{15}] \sqcup [\frac{16-\sqrt{31}}{15}, 1]$$ covered by $(1,0)$ and $(1,1).$ The next smallest tree (based on the $1$-norm) is centered at $(2,1),$ which can be seen for any $m \in [ \frac{32-\sqrt{79}}{63}, \frac{32 + \sqrt{79}}{63} ].$ At this point we still have only filled a disjoint union of intervals with $(1,0),$ $(1,1)$ and $(2,1),$ so filling in the remaining gaps, in the translucent tree problem we would be able to see the tree centered at $(3,1)$ for any $m \in [\frac{48-\sqrt{159}}{143}, \frac{48+\sqrt{159}}{143} ],$ but since $\frac{48 + \sqrt{159}}{143} \gt \frac{32 - \sqrt{79}}{63} \gt \frac{\sqrt{15}}{15} \gt \frac{48-\sqrt{159}}{143}$, I can only see the tree $(3,1)$ for $m \in (\frac{\sqrt{15}}{15}, \frac{32 - \sqrt{79}}{63}).$ Similarly, I can see $(3,2)$ for any $m \in (\frac{48 + \sqrt{159}}{143}, \frac{16-\sqrt{31}}{15}),$ so in totality there are 8 trees in the lower half of the first quadrant that can be seen, that is, $$T(m) = \begin{cases} (1,0), & m \in [0, \frac{\sqrt{15}}{15}]; \\ (3, 1), & m \in ( \frac{\sqrt{15}}{15}, \frac{48 - \sqrt{159}}{143}); \\ (2, 1), & m \in [ \frac{48 - \sqrt{159}}{143}, \frac{48 + \sqrt{159}}{143} ];\\ (3,2), & m \in (\frac{48 + \sqrt{159}}{143}, \frac{16-\sqrt{31}}{15}); \\ (1,1), & m \in [\frac{16 - \sqrt{31}}{15}, 1].\end{cases}$$

So since there are 5 in the lower half of the first quadrant, we should multiply by 8 to get to 40 trees in the whole plane. However, this would double count the eight points $(\pm 1, 0),$ $(0, \pm 1),$ $(\pm 1, \pm 1),$ so we need to subtract 8 from the total, leaving $32$ trees of diameter $r=0.25$ can be seen from the origin.

No comments:

Post a Comment