26
$\begingroup$

I have a serious problem with this problem: Is it possible to Draw circles on the plane such that every line intersects at least one of them but no line intersects more that 100 of them !?

Any help or suggestion would be helpful.

$\endgroup$
5
  • 1
    $\begingroup$ I guess I'd start with a hyperbola, plug the central hole with a single circle, then place sufficiently small circles along the curve to catch all lines which intersect it. You'd get into trouble along the asymptotes, where the hyperbola becomes arbitrary straight towards infinity. Reducing radii might compensate for that, making the curvature sufficient to limit the number of intersections. If not, then perhaps you can find some bound on the curvature, and use that to prove that no such curve can exist. Which doesn't rule out non-curve arrangements, but might still help. $\endgroup$ – MvG Sep 3 '13 at 15:37
  • 4
    $\begingroup$ This is from Miklos Schweitzer competition 2008. 10 days and all resources were allowed. $\endgroup$ – Abdulh Khazzak Gustav ElFakiri Sep 3 '13 at 18:50
  • 1
    $\begingroup$ @MvG: A nice idea! What about using two parabolas, say $y=\pm x^2$. Every line will intersect at least one, as at least one of $b^2\pm 4c$ will be non-negative. Then the asymptotes wouldn't be such a problem. $\endgroup$ – Jyrki Lahtonen Sep 7 '13 at 21:19
  • $\begingroup$ @AbdulhKhazzakGustavElFakiri Correct me if I am wrong. But it seems to me that you mean because the problem has 10 days and all resources are allowed then it is a GIANT and its better we do not waste our time trying to solve it. $\endgroup$ – Robert M Sep 11 '13 at 20:30
  • $\begingroup$ 100 seems to just be an arbitrary large number when thinking about the plane. If it's false, I expect any line would actually hit an infinite number of them. We might think about stereographic projection. Lines in the plane correspond to circles on the sphere that pass through the north pole. And regular circles in the plane correspond to circles on the sphere that don't pass through the pole. Since every line intersects at least one circle, these circles are necessarily going to cluster at the pole. Don't know if that can be used. $\endgroup$ – user123641 Feb 22 '18 at 0:00
4
+25
$\begingroup$

I have only a partial (negative) solution.

I can prove that there is no chain of circles of infinite length. That is, no sequence of circles without repetitions, where every two consecutive circles intersect or touch and the sum of the radii of the circles diverges. In particular, this rules out the suggestions with hyperbolas or parabolas, if I understand them correctly.

Proof by contradiction. Let $C$ be one of the circles of the chain and let $P$ be its center. We will prove that some ray starting in $P$ intersects infinitely many circles. Let's call $P$-rays the rays starting at $P$.

A circle of radius $r$ with center at distance $\ell$ from $P$ intersects at least $2r/(\ell\cdot 2\pi)$ fraction of the $P$-rays. (This is not true if $r>\ell\cdot \pi$, of which we take care at the end.)

Let $r_i$ be the sequence of radii of the circles along the chain starting with $C$. Then the distance $\ell_i$ between $P$ and the center of the $i$-th circle is at most $2(r_1+r_2+\cdots + r_i)$. So the $i$-th circle blocks at least $(1/(2\pi)) \cdot r_i/(r_1+\cdots +r_i)$ fraction of $P$-rays. Since the chain has infinite length, the sum $r_1 + r_2 + \cdots$ diverges. Then also the sum of $r_i$ divided by partial sums diverges. That is, the sum of fractions of blocked $P$-rays goes to infinity and some $P$-ray is blocked infinitely many times.

We still need to do something with the circles of the chain with $r>\ell\cdot \pi$. First of all, $C$ is one of them: we counted that it blocks $(1/(2\pi)) \cdot r_1/r_1$ fraction, and that's true. For others, we may have counted that they block many times more than 100% percent of the $P$-rays. But since each such circle contains $P$ and crosses every $P$-ray, there are at most $99$ of such circles. So the excess counted to the sum is finite and the corrected sum still diverges.

$\endgroup$
2
  • $\begingroup$ When suggesting my hyperbolas approach, I had $\lim_{i\to\infty}r_i=0$ in mind, but this was more of a gut feeling, and I wasn't sure. Your proof makes it clear that divergent radii don't stand a chance, and I know that rqual radii won't work either (the asymptotes would intersect infinitely many of these), so the only thing that remains is ruling out an ever decreasing sequence of radii. Probably by prooving that the radii would have to decrease so fast that the chain would end well before reaching infinity. $\endgroup$ – MvG Sep 9 '13 at 8:20
  • 1
    $\begingroup$ My proof rules out divergent sums of radii, not only series. That is, if no line crosses 100 circles, the sum of the radii of the circles of every chain converges and the chain ends before reaching infinity. $\endgroup$ – pepan Sep 9 '13 at 15:54
1
+500
$\begingroup$

This is impossible.

$\bf{Proof}$: by contradiction. Suppose it were possible to draw circles on the plane such that every line intersects at least one of them but no line intersects more that 100 of them. Denote $\mathbb{R}/\pi\mathbb{R}$ with $\mathbb{R}_\pi$, choose a point $(x_0,y_0)$ on the plane, and define $c_{(x_0,y_0)}:\mathbb{R}_\pi\to\mathbb{Z}_{\leq100}$ such that $c_{(x_0,y_0)}(\theta)$ be the number of circles which the line $(y-y_0)=\tan(\theta)(x-x_0)$ intersects (or the line $x=x_0$ if $\theta=\frac{\pi}{2}$). $c_{(x_0,y_0)}$ must reach a maximum for every open interval $(a,b)\subseteq\mathbb{R}_\pi$ since it is positive and integer valued, say this maximum is reached at $\phi\in (a,b)$. Let $S_\phi$ denote the set of circles which the line $(y-y_0)=\tan(\phi)(x-x_0)$ intersects, and $f(C)$ be the set of angles $\theta$ such that $(y-y_0)=\tan(\theta)(x-x_0)$ intersects circle $C$. Define $M(a,b)$ as the open set $$(a,b)\cap\bigcap_{C\in S_\phi}f(C)$$ with endpoint removed if closed. Since $\phi$ maximizes $c_{(x_0,y_0)}$ on $(a,b)$, and every line going through $(x_0, y_0)$ with angle in $M(a,b)$ must go through all the circles which the line with angle $\phi$ goes through (and cannot go through any other circles as $\phi$ is the maximum), the open cone of lines $(y-y_0)=\tan(\theta)(x-x_0)$, $\theta\in M(a,b)$ must contain a finite number of circles. Let $$B_{(x_0,y_0)}=\bigcup_{a,b\in \mathbb{R}/\pi\mathbb{R}}M(a,b)$$ I originally attempted to demonstrate that $B_{(x_0,y_0)}=\mathbb{R}_\pi$ and then, since $\mathbb{R}_\pi$ is compact, find a finite open cover and deduce a finite number of circles, but failed ($B_{(x_0,y_0)}=\mathbb{R}_\pi$ isn't always a true statement). This obstacle can however be surmounted.

One can demonstrate that $|\mathbb{R}_\pi-B_{(x_0,y_0)}|$ cannot be infinite (again, by contradiction). Suppose it were. Since the set is an infinite subset of a compact set, it must have a limit point in $\mathbb{R}_\pi$, which we denote with $\theta_l$, and let $\theta_1<\theta_2<...<\theta_n<...$ all be in $\mathbb{R}_\pi-B_{(x_0,y_0)}$ and converge to $\theta_l$. Pick some $C_1\in S_{\theta_l}$. There must be some $\theta_{m_1}\in f(C_1)$ since $\theta_i$ converges to $\theta_l$. However, since $\theta_{m_1}\not\in B_{(x_0,y_0)}$, there must exist another circle $C_2\in S_{\theta_l}$ such that $\theta_{m_1}\not\in f(C_2)$, and there must be some $\theta_{m_2}\in f(C_2)$. We repeat this process to find a $C_3$ distinct from $C_1$ and $C_2$, and so on. Since this can be iterated infinitely many times as there are infinitely many terms in the sequence which converges to $\theta_l$, we conclude that we can find infinitely many distinct circles in $S_{\theta_l}$, which is a contradiction. Therefore, there can be only a finite number of elements in $\mathbb{R}_\pi-B_{(x_0,y_0)}$.

Let $L_{(x,y)}(A)$ denote the set of lines going through the point $(x,y)$ at an angle $\theta\in A$, and pick $(x_1,y_1)\not\in L_{(x_0,y_0)}(\mathbb{R}_\pi-B_{(x_0,y_0)})$. There exists compact subsets $\overline{B}_{(x_0,y_0)}\subset B_{(x_0,y_0)}$ and $\overline{B}_{(x_1,y_1)}\subset B_{(x_1,y_1)}$ such that $$L_{(x_0,y_0)}(\mathbb{R}_\pi-\overline{B}_{(x_0,y_0)})\cap L_{(x_1,y_1)}(\mathbb{R}_\pi-\overline{B}_{(x_1,y_1)})$$ is bounded since $\mathbb{R}_\pi-B_{(x_0,y_0)}$ and $\mathbb{R}_\pi-B_{(x_1,y_1)}$ are finite. Furthermore, since $\overline{B}_{(x_0,y_0)}$ and $\overline{B}_{(x_1,y_1)}$ admit finite covers with respective sets of the form $M(a,b)$ as described above, the number of circles intersecting with $$L_{(x_0,y_0)}(\overline{B}_{(x_0,y_0)})\cup L_{(x_1,y_1)}(\overline{B}_{(x_1,y_1)})$$ is finite, and the circles are thus bounded. As a result, the set of circles in $$\mathbb{R}^2=\Big{(}L_{(x_0,y_0)}(\mathbb{R}_\pi-\overline{B}_{(x_0,y_0)})\cap L_{(x_1,y_1)}(\mathbb{R}_\pi-\overline{B}_{(x_1,y_1)})\Big{)}\cup\Big{(}L_{(x_0,y_0)}(\overline{B}_{(x_0,y_0)})\cup L_{(x_1,y_1)}(\overline{B}_{(x_1,y_1)})\Big{)}$$ is bounded, which yields a contradiction as there are lines which lie outside the bounded area (and therefore do not intersect any circle).

Note: I do not claim credit for this proof; I derived part of it then found that a more formal and complete version of my ideas had already been explored here. Any detail which I may have overlooked is likely addressed on that page.

$\endgroup$
8
  • $\begingroup$ It is not clear how we should proceed if $(a,b)\cap\bigcap_{C\in S_\phi}f(C)$ without endpoints is empty nor the cardinality of the collection of such lines. $\endgroup$ – mucciolo Feb 22 '18 at 9:37
  • $\begingroup$ I disagree with your proofs. Why can't $\Bbb R_\pi - B$ look like a Cantor set ? then it would be uncountably infinite. $\endgroup$ – mercio Feb 25 '18 at 17:27
  • $\begingroup$ I've awarded the bounty to this answer, so that it doesn't go to waste. But it would be great if you could address the concerns raised in the comments above. Otherwise, you are encouraged to place the same bounty again so that the question receives more attention! There could be other solutions $\endgroup$ – Prism Feb 26 '18 at 12:29
  • $\begingroup$ @mucciolo Since $\phi$ is in $(a,b)$ and $\bigcap_{C\in S_\phi}f(C)$ is a closed set which, by definition, contains $\phi$, the only way for this intersection minus the endpoints to be empty is if $\bigcap_{C\in S_\phi}f(C)=\{\phi\}$. While this is possible (if the line with angle $\phi$ is tangential to both a circle on its "right" and one on its "left"), it seems quite clear that this cannot be the case for "many" $\phi$ (as, otherwise, one could easily find some line which goes through over 100 circles). I still think the rest of the proof holds, even if some of the sets $M$ are empty. $\endgroup$ – Romain S Feb 26 '18 at 16:21
  • $\begingroup$ @Prism I will try to sort out these comments, but will of course set another bounty if it becomes clear that this proof is flawed! $\endgroup$ – Romain S Feb 26 '18 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.