4
$\begingroup$

I asked this over in the puzzling SE and it has since been solved there. The question is best asked with a visual: enter image description here

I am looking to find a sequence (of any length) of strictly decreasing (strictly because otherwise you can pick seven 1s and pack a hex lattice) integer radii such that the final circle perfectly covers the central one. In other words, such that it is also tangent to the second circle (the first non-central).

The above image is the closest I've been able to brute force search (20, 19, 18, 17, 16, 14, 8, 5, 4, 3, 2), it misses by about 5.39x10e-6.

My search would be sped up if I knew more about how to do a weird version of Newton-Raphson with binary string permutations. Take the above example. I can encode the sequence like this (ignoring the central circle/implying its size by the length of the string): 1111010000010011110.

It is the smallest binary number with ten 1s that overlaps with the rightmost circle. The previous lexicographical permutation (1111010000010011101) should(?) represent the largest binary representation that does not overlap.

For a given central radius and number of surrounding circles, there should exist a pair of sequences that are lexicographically adjacent that span this overlap. I have a way to increment a binary string permutation, but have not found a way to find the midpoint of two distinct lexicographic permutations. That would speed up my search immensely and allow me to employ a bit of N-R.*

Edit: I'm becoming very skeptical of the above assertion the more I examine it, but I'll leave it up in case it helps on any level.

$\endgroup$
8
  • 2
    $\begingroup$ usual thing is to regard as circles in the complex plane. If the radius of the central circle is integer $R,$ map the picture by linear fractional (Moebius) transformation $w = \frac{-1}{z-R}$ so as to send the inner circle to a line. The circles (other than the first two) are mapped to circles. Radii will now be rational, the two new lines are parallel. Worth trying, the outcome has some resemblance to Ford circles. $\endgroup$
    – Will Jagy
    Commented May 8 at 17:05
  • 1
    $\begingroup$ @CalvinLin You may have a point; certainly the revised picture does not finish the problem immediately. The other picture to check is Apollonian Gaskets $\endgroup$
    – Will Jagy
    Commented May 8 at 18:06
  • 1
    $\begingroup$ There are examples of arbitrarily high number of circles. $\endgroup$ Commented May 8 at 19:26
  • 1
    $\begingroup$ This might be the law of small numbers talking, but I suspect that the problem is unsolvable. Combining a bunch of integers to get pi sounds like exactly the kind of thing that might be provably impossible. But I personally have no idea how you'd go about creating a proof of impossibility. $\endgroup$ Commented May 9 at 4:20
  • 1
    $\begingroup$ There are infinite Apollonian packings where all radii are reciprocals of integers. Scaling up to integer radii will give you arbitrarily large chains of circles with integer radii. $\endgroup$ Commented May 10 at 2:39

2 Answers 2

3
$\begingroup$

Some useful formulas

I don't have an answer, but here's some insights and formulas that may be helpful.

enter image description here

Formula for $\theta$
using Law of Cosines:
$$\theta = \cos^{-1}\left(\frac{(r_0+r_1)^2 + (r_0+r_2)^2 - (r_1+r_2)^2}{2(r_0+r_1)(r_0+r_2)}\right)$$ $$\theta = \cos^{-1}\left(1 - 2\cdot\frac{r_1}{r_0+r_1}\cdot\frac{r_2}{r_0+r_2}\right)$$

Instead of looking for integer radii, WLOG let's look for rational radii, with $r_0 = 1$. Then,

$$\theta = \cos^{-1}\left(1 - 2\cdot\frac{r_1}{1+r_1}\cdot\frac{r_2}{1+r_2}\right)$$

Next, let's define $s_i$ so that we can search for those values instead of $r_i$ $$s_i = \frac{r_i}{1+r_i}$$ $$\theta = \cos^{-1}\left(1 - 2s_1s_2 \right)$$

Note that $0 \lt r_i \lt 1$ which makes $0 \lt s_i < \frac{1}{2}$.

Sum of $\cos^{-1}$ terms

$$\cos^{-1}c = \cos^{-1}a + \cos^{-1}b$$ $$c = \cos(\cos^{-1}a + \cos^{-1}b)$$ $$c = \cos\cos^{-1} a \cdot \cos\cos^{-1} b - \sin\cos^{-1} a \cdot \sin\cos^{-1} b$$ $$c = ab \pm \sqrt{1-a^2} \cdot \sqrt{1-b^2}$$

Running total
Let's keep a running total of the angle spanned by our sequence of circles.

Let $T$ be the cosine of the total angle spanned so far. Let's add the angle spanned by circles with "values" $s_1$, $s_2$.

$$\cos^{-1} T' = \cos^{-1} T + \cos^{-1}\left(1 - 2s_1s_2 \right)$$

Let $u = s_1s_2$. Then,

$$\cos^{-1} T' = \cos^{-1} T + \cos^{-1}\left(1 - 2u \right)$$

We now know how to sum $\cos^{-1}$ terms.

$$T' = T\cdot (1 - 2u) \pm \sqrt{1-T^2}\sqrt{1-(1 - 2u)^2}$$

$$T' = T\cdot (1 - 2u) \pm 2\sqrt{1-T^2}\sqrt{u-u^2}$$

Eventually $T$ needs to reach $1$.
It might be important to keep the running total rational.

Algorithm for N=7

EdwardH posted a great solution, but it's hard to understand for me, and it would be nice to have a solution with smaller radii. Here's my take.

WLOG, we'll make the central circle radius 1 and make the others circles all have rational radii.

How to construct tangent circles with rational radii
First, pick some rational coordinates $p_1, ..., p_7$ on the top half of the unit circle. (Each point will eventually correspond to a circle's position.) For example:
enter image description here

We can think of each coordinate as an angle $\frac{\theta}{2}$, and the coordinates as $(\cos\frac{\theta}{2},\sin\frac{\theta}{2})$.

Our construction will eventually double these angles: $$(\cos\frac{\theta}{2},\sin\frac{\theta}{2}) \rightarrow (\cos \theta,\sin \theta)$$ Using the double angle formulas this can be written as $$(x,y) \rightarrow (x^2-y^2, 2xy)$$

These new coordinates are the normalized positions of the 7 circle centers: enter image description here

The calculations:
First we calculate $\sin \frac{\theta}{2}$, where $\frac{\theta}{2}$ is the angle between two consecutive points (on the half-circle): (Note: the sign of the result ends up not being important)
$$u_i = p_{i_x}p_{{i+1}_y} - p_{i_y}p_{{i+1}_x}$$

From the previous section we have $$\theta = \cos^{-1}\left(1 - 2s_1s_2 \right)$$ solving for $s_1s_2$: $$s_1s_2 = \frac{1-\cos\theta}{2} = \sin^{2}{\frac{\theta}{2}} = {u_1}^2$$

So $$s_1s_2 = {u_1}^2$$ $$s_2s_3 = {u_2}^2$$ $$s_3s_4 = {u_3}^2$$ $$s_4s_5 = {u_4}^2$$ $$s_5s_6 = {u_5}^2$$ $$s_6s_7 = {u_6}^2$$ $$s_7s_1 = {u_7}^2$$

Solving for $s_i$: (Note: here's where 7 being odd matters) $$s_1 = \frac{u_1u_3u_5u_7}{u_2u_4u_6}$$ $$s_2 = \frac{u_2u_4u_6u_1}{u_3u_5u_7}$$ $$s_3 = \frac{u_3u_5u_7u_2}{u_4u_6u_1}$$ $$s_4 = \frac{u_4u_6u_1u_3}{u_5u_7u_2}$$ $$s_5 = \frac{u_5u_7u_2u_4}{u_6u_1u_3}$$ $$s_6 = \frac{u_6u_1u_3u_5}{u_7u_2u_4}$$ $$s_7 = \frac{u_7u_2u_4u_6}{u_1u_3u_5}$$

And finally the radii, $r_i$: $$r_i = \frac{s_i}{1-s_i}$$

And we get this result: enter image description here $$r_1=\frac{13125}{17851}, r_2=\frac{216832}{955043}, r_3=\frac{75}{37}, r_4=\frac{336}{289}, r_5=\frac{336}{289}, r_6=\frac{75}{37}, r_7=\frac{216832}{955043}$$

In general, it's clear that rational inputs will produce rational radii.

The remaining problem becomes picking input coordinates such that the resulting circle radii are sorted correctly.

$\endgroup$
0
0
$\begingroup$

In Figure 12, one possible solution is depicted, with radii $1/146$, $1/27$, $1/23$, and $1/18$, respectively. This can easily be scaled by $90666$ times (the LCM) to become integers, namely $621$, $3358$, $3942$, $5037$. Judging from the magnitude of the numbers, its no wonder brute force computer search wasn't fruitful.

$\endgroup$
1
  • 2
    $\begingroup$ This isn't a solution because the central circle isn't the largest circle. A true solution needs to have at least 8 circles total (since 6 smaller circles definitely can't close the gap around a larger central circle). $\endgroup$ Commented May 9 at 16:40

You must log in to answer this question.

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