4

Here's a problem I saw:

How many equilateral triangles (with length $1$ cm) on a triangle grid can be covered with a circle centered at a point with radius $r$ cm?

At first I thought the answer is just $r^2\times 6$, but then I found out it's only for small $r$.

For example:

enter image description here

Here the grey part is the answer, but then if the circle gets bigger, the orange part might cover some triangles, which makes the answer different.

Can anyone help me with it? I want a formula for at least $1\leq r\leq 100000$. Thanks.

blastzit
  • 800
  • 2
    This is just Gauss' circle problem for $\mathbb{Z}[\omega]$. For large radii the maximum number of triangles should be close to $$\frac{\pi r^2}{\frac{\sqrt{3}}{4}} = \frac{4\pi}{\sqrt{3}} r^2$$ minus a $O(r)$ (probably a $O(r^{2/3})$) term. – Jack D'Aurizio Jul 06 '17 at 03:30
  • https://en.wikipedia.org/wiki/Gauss_circle_problem – Jack D'Aurizio Jul 06 '17 at 03:31
  • But is there an explicit formula for the problem? I really need the exact value though... :( @JackD'Aurizio – blastzit Jul 06 '17 at 03:37
  • Each triangle is root (3)/2 high so you can stack 2r/root(3) triangles perpendicular to the diameter and 2r an Lang the diameter. Roughly. – fleablood Jul 06 '17 at 03:39
  • https://math.stackexchange.com/questions/1411295/maximum-number-of-equilateral-triangles-in-a-circle – MattW Jul 06 '17 at 03:42
  • @MattWatkins But the post still doesn't give a nice approximation (at least close to the actual value) to the problem. I want an actual formula for it. – blastzit Jul 06 '17 at 03:50
  • I don't have a formula, but I see an algorithm for finding the exact number. Interested? – Jens Jul 10 '17 at 13:32
  • @Jens Yes! I would like to see anything related to this question! – blastzit Jul 13 '17 at 12:24

1 Answers1

1

To find the number of triangles in the orange part, we first determine how many levels $L$ of triangles it can contain. In the figure below is an example where $r=9$ and $L=1$:

enter image description here

The number of levels is just the number of times the height of a triangle $h=\frac {\sqrt 3}{2}$ fits into the distance $|AB|$ and since $|AB|=r-d = r- \frac {\sqrt 3}{2}r$, we get:

$$L=\left \lfloor \frac{|AB|}{h} \right \rfloor =\left \lfloor \frac{2-\sqrt 3}{\sqrt 3}r \right \rfloor$$ With $r=9$ we see that $L=1$. To find the number of triangles in each level, we need to find the length of the chord that delimits that level. In the figure above the chord that delimits the first (and only) level is shown in green. The length of a chord is given by: $$c=2\sqrt{r^2-d_O^2}$$ where $d_O$ is the distance from the chord to the circle center $O$. So for a given level $k \le L$ we would have a chord length of $$c_k = 2\sqrt{r^2-(d+k\cdot h)^2}$$ So how do we determine the number of triangles $t_k$ in a level, given the chord length? It depends on which way the middle triangle of the level is pointing. If it's pointing away from the center circle (as in the figure above) we have

$$t_k = \begin{cases} 1, & c_k \lt 2 \\ 5, & 2 \le c_k \lt 4 \\ 9, & 4 \le c_k \lt 6 \\ \text{etc} \end{cases}$$

and if it's pointing toward the circle center we have

$$t_k = \begin{cases} 0, & c_k \lt 1 \\ 3, & 1 \le c_k \lt 3 \\ 7, & 3 \le c_k \lt 5 \\ \text{etc} \end{cases}$$

The pattern for calculating $t_k$ in each case, should be clear.

The first level "points away" if $r$ is odd and "points towards" if $r$ is even. Subsequent levels of course alternate between the two. Below is a figure with $r=18$ and hence $L=2$:

enter image description here

We see that the first level points towards the circle center.

So, to sum up:

  1. Determine the number of levels

  2. Sum the number of triangles in each level

  3. Add this sum to $r^2$

  4. Multiply this number by $6$.

I made a program in Visual Basic which does the job in some $30$ lines of code.

Jens
  • 5,686
  • 2
  • 20
  • 38