Consider $n$ disks $C_{1}; C_{2}; ... ; C_{n}$ in a plane such that for each $1 \leq i < n$, the center of $C_{i}$ is on the circumference of $C_{i+1}$, and the center of $C_{n}$ is on the circumference of $C_{1}$. Define the score of such an arrangement of $n$ disks to be the number of pairs $(i; j )$ for which $C_{i}$ properly contains $C_{j}$ . Determine the maximum possible score.
Problem
Source: APMO 2007
Tags: induction, combinatorics unsolved, combinatorics
probability1.01
31.03.2007 10:21
Oh man... it is rather sad that I did not solve this during the contest, but here's a proof (with a few easy parts left out) that I came up with later that day: The maximum score is ${ n-1 \choose 2}$. It is easy to construct an example... just let $C_{i+1}$ be entirely contained within $C_{i}$ for $1 \le i \le n-2$. To prove this is optimal, for each $k$, let $S_{k}$ be the score generated among the circles $C_{i}$, with $1 \le i \le k$. Furthermore, let $a_{k}$ be the number of circles $C_{i}$, $i < k$, such that the centre of $C_{k}$ lies within $C_{i}$. WLOG $C_{n}$ is the largest circle. We will prove by induction that $S_{k}-a_{k}\le{k-1 \choose 2}$ for $k \le n-1$. In the base case, obviously $S_{0}-a_{0}= 0$. Now suppose $S_{k}-a_{k}\le{k \choose 2}$; then let $t$ be the number of circles $C_{i}$, $i \le k$, which $C_{k+1}$ intersects. Considering that $C_{k+1}$ can not contain or be contained in a circle which it intersects, we have $S_{k+1}\le S_{k}+k-t$. Meanwhile, if the centre of the circle $C_{k+1}$ lies outside a circle $C_{i}$, $i \le k$, then since the centre of $C_{k}$ lies on $C_{k+1}$, either $C_{i}$ does not contain the centre of $C_{k}$ or $C_{k+1}$ intersects $C_{i}$. We can conclude then that $a_{k+1}\ge a_{k}+1-t$ (Why?). Therefore, $S_{k+1}-a_{k+1}\le S_{k}+k-t-a_{k}-1+t \le{k-1 \choose 2}+k-1 ={k \choose 2}$, and our induction is complete. With that, we know $S_{n-1}-a_{n-1}\le{n-2 \choose 2}$. Now recall that $C_{n}$ is the largest circle, so if $C_{n}$ is to contribute to the score, it must contain some other circles. However, the centre of $C_{n-1}$, which is a point on $C_{n}$, is contained by $a_{n-1}+1$ circles. Hence $C_{n}$ can only contain up to $(n-1)-(a_{n-1}+1) = n-2-a_{n-1}$ other circles, so $S_{n}\le S_{n-1}+n-2-a_{n-1}\le n-2+{n-2 \choose 2}={n-1 \choose 2}$ as desired.
dhthstn
01.04.2007 10:58
you can use induction with inductive hypothesis like this:there are n circle $C_{1}...C_{n}$ such that $C_{i+1}$ does not contain $C_{i}$;$C_{1}$ does not contain C_n then the maximum score is $(n-1)\choose 2$,assume it's true for all number less than n consider n circle $C_{1}...C_{n}$ with the property $C_{i}$ is isn't contained in $C_{i+1}$;a pair $(i;j)$ is score 1 if $C_{i}$ contain $C_{j}$ If none of $C_{i}$ contain $C_{i+1}$ for all $1\leq\ i\leq\ n$(subscript is consider mod n) then note that 2 pair $(i;j)$ and $(j;i)$ score at most 1 (since if $C_{i}$ contain $C_{j};C_{j}$ don't contain $C_{i}$) and none of $(i;i+1)$ and $(i+1;i)$ score 1;the score is at most $n\choose 2$ -$n$< $(n-1)\choose 2$ we are done assume wlog that $C_{n}$ contain $C_{1}$(since we can relabel) then $C_{1}$ can't contain $C_{n-1}$ since $C_{n}$ doesn't contain $C_{n-1}$.we prove that the score $C_{n}$ make is less than $n-2$.assume the contrary it score $n-1$ then for $i<n$,one of $(i;n)$ and $(n;i)$ must score 1.Then $C_{n-1}$ contain $C_{n}$ and since $C_{n-1}$ doesn't contain $C_{n-2}$;$C_{n-2}$ must contain $C_{n}$...so keep doing that at the end we get $C_{1}$ contain $C_{n}$,contradiction delete $C_{n}$ and apply the inductive hypothesis, $C_{n}$ can score at most $n-2$ so we have the score is at most $\frac{(n-2)(n-3)}{2}$$+n-2=\frac{(n-1)(n-2)}{2}$
MathPanda1
09.03.2017 05:19
Is this right? Let a pair be bad if their circles intersect. Choose the largest circle $C_i$. Now we consider $C_{i-1}, C_{i-2}, ...$ in that order (where $0 = n, -1 = n-1$, etc.). Consider the graph with $n$ vertices representing the circles such that there is an edge iff the two circles share some area. Note that the condition implies that the graph is connected. Consider $C_{j-1}$. The center of the circle lies on $C_j$. Note that we can slowly dilate $C_{j-1}$ about its center from being a point circle. Since the circle cannot cover $C_i$ (since $C_i$ is the largest circle), and the circles are essentially "connected" to each other, $C_{j-1}$ will have to intersect at least another circle already processed. Thus, every circle we process will add a bad pair. Thus, there are at least $n-1$ bad pairs, and so a score of at most $\frac{(n-1)(n-2)}{2}$ points.
math90
09.03.2017 15:03
Yes, MathPanda1.
MathPanda1
09.03.2017 17:14
Cool, thank you very much for your confirmation!
vsathiam
08.04.2017 22:59
MathPanda1 wrote: Cool, thank you very much for your confirmation! I had your solution minus the graph theory part (Just invoked the condition directly and found a working config)
alexiaslexia
11.03.2021 06:35
First thoughts: A problem which is $\textit{really}$ worth doing for a long time --- and I didn't regret any time spent doing this problem for $\sim 6$ hours. While saying so, despite the simple statement, I do think that it's not easy to process; and it's easy to lose sight of $\textit{what's possible}$ and $\textit{what's impractical}$.
A similar experience to 2019 C4, (slightly biased) much harder than what it seems like. Reflecting on this problem is certainly fun due to a lot of factors (mainly due to the richness of the configuration(s) and their bounding connectivity, the nonsymmetric nature of the circles --- which $\textbf{can}$ be converted to open non-convex figures, and why distances can destroy or build a new system of thought.)
Or well, it could just be me using the $\textit{quote-unquote}$ tools which are strong in the 2021 meta and weak/non-functioning in the old unknown meta of 2007 back then.
Assume $A$ properly contains $B$ iff $B$'s interior lies inside or on the interior of $A$ (so the circles are virtually open sets, boundary not included --- so tangency is proper) but $B \ne A$; so it's not possible for $B$ to be inside $A$ and $A$ to be inside $B$ simultaneously. I assumed this meaning from the common term $\textit{proper divisor}$ where $n$'s proper divisors are its divisors except itself.
$\color{green} \rule{25cm}{2pt}$
$\color{green} \textbf{A Simple Observation.}$ Let $X \subset Y$ be the assertion that all members of $X$ is in $Y$, with $X \ne Y$ (copying the definition of properly contained here.)
Also, let $A, B$ and $C$ be three set of $\textit{things}$ (anything in particular: people, integers, uncountable/countable particles in space) so that $A \subset C$, $A \cap B \ne \varnothing$ and $A \not\subset B$.
Then, $C \not\subset B$; and $B \cap C \ne \varnothing$.
$\color{green} \rule{25cm}{0.4pt}$
$\color{green} \textbf{Proof.}$ Easy. Since $A \not\subset B$, there exists an element $a \in A$ where $a \not\in B$. Since $A \subset C$, then $a \in C$; so $C \not\subset B$ since $C$ has an element that $B$ does not have.
Secondly, consider an element $i \in A \cap B$. That element is also an element of $C$, so $i \in B\cap C$; so $B \cap C \ne \varnothing.$
$\color{green} \rule{25cm}{0.4pt}$
$\color{green} \text{What Does That Mean?}$ Consider circles $C_i$ and $C_j$ so that $C_i$ intersects $C_j$ (i.e. they two form a normal-Venn-diagram.) If another circle $C$ properly contains $C_i$, then it cannot be inside $C_j$ or disconnect from $C_j$ completely.
This means that if $C$'s score against $C_i$ is positive, and if $C$'s score against $C_j$ is positive, then $C$ $\textbf{must}$ contain $C_j$, too. $\blacksquare$
$\color{red} \rule{25cm}{2pt}$
$\color{red} \textbf{A More Complicated Result.}$ Make a graph $G$ so that its vertices $V_1,V_2,\ldots,V_k$ represent circles $C_1,C_2,\ldots,C_k$, and edges will connect $V_i$ to $V_j$ iff circles $C_i$ and $C_j$ intersect (in their usual way: they form a normal-Venn-diagram.)
Let $G$ connected. If a random circle $C$ is exterior to a circle $C_1$ (or fully outside/contains $C_1$), and that circle's score against the $k$ circles in $G$ is full, then the circle $C$ is exterior to $\textbf{all of them.}$
$\color{red} \rule{25cm}{0.4pt}$
$\color{red} \textbf{Proof.}$ Not so obvious, isn't it? However, using $\color{green} \text{What Does That Mean}$ clears this up easily; let we would like to prove that $C$ contains $C_a$ for some $a$.
Consider a path in $G$ (in the usual sense) from $V_1$ to $V_a$ and let the path be in the form
\[ V_{i_1} = V_1 - V_{i_2} - \ldots - V_{i_c} = V_a \]Then, by chain reasoning $C$ contains $V_{i_2}$, $V_{i_3}$, up to $V_{i_c} = V_a$. Thus the proof is complete.
$\color{cyan} \rule{25cm}{2pt}$
$\color{cyan} \textbf{Defining intersections and borders.}$ Up to now, we've only used what-if circles which is always assumed to score fully against the circles before that.
Define $X$ intersects $Y$ iff there exists an element $x \in X-Y$, $y \in Y-X$ and $i \in X \cap Y$. When we have defined the interior and exterior of these (closed) sets, we define their border to be every point in which its neighborhood is not all interior points or exterior points.
Then, if there exists two sets $S_1$ and $S_2$ so that $S_2$'s border contains an interior point of $S_1$ and $S_2$ has a point that $S_1$ doesn't, then $S_1$ intersects $S_2$.
$\color{cyan} \rule{25cm}{2pt}$
$\color{cyan} \textbf{Proof.}$ Let $b$ be the border point of $S_2$ which is inside $S_1$. Then, as $b$ is inside $S_1$, there exists a point $p,q$ sufficiently near to $b$ so that both of them are still in the interior of $S_1$ --- with a twist: $p$ inside $S_2$ and $q$ outside it.
Those two points exist by the definition of border: $b$'s neighborhood, however small it is, must contain an interior point and an exterior point to be able to be called a border. By that reasoning, $p$ belongs to $S_1 \cap S_2$ and $q$ belongs to $S_1-S_2$.
Let $r$ be a point that belongs to $S_2$ but not $S_1$. Recapping, we get that $p$ belongs to $S_1 \cap S_2$ and $q$ belongs to $S_1-S_2$. So, the set $S_1-S_2$, $S_2-S_1$ and $S_1 \cap S_2$ are nonempty, and the proof is completed.
[asy][asy]usepackage("tikz");label("\begin{tikzpicture}
\definecolor{bfffqq}{rgb}{0.7490196078431373,1,0}
\definecolor{cczzqq}{rgb}{0.8,0.6,0}
\definecolor{ffccww}{rgb}{1,0.8,0.4}
\definecolor{ffqqqq}{rgb}{1,0,0}
\definecolor{qqffff}{rgb}{0,1,1}
\definecolor{ffxfqq}{rgb}{1,0.4980392156862745,0}
\draw [line width=1.2pt,color=qqffff] (-6.304112554112552,0.4532034632034633) circle (2.2000448416220855cm);
\draw [line width=1.2pt,color=qqffff] (-4.13,0.79) circle (1.1979794117656644cm);
\draw [line width=1.2pt,color=qqffff] (-5.213203463203461,1.3016883116883113) circle (0.5604193307494106cm);
\draw [line width=1.2pt,color=ffqqqq] (-4.9846320346320345,0.79) circle (4.636770407497834cm);
\draw [line width=1.2pt,color=ffccww] (-0.38203463203463006,0.22809523809523824) circle (0.9917105498373231cm);
\draw [shift={(-0.38203463203463006,0.22809523809523824)},line width=1.2pt,color=cczzqq] plot[domain=1.2359898160144938:5.042430048661032,variable=\t]({1*3.030839284647634*cos(\t r)+0*3.030839284647634*sin(\t r)},{0*3.030839284647634*cos(\t r)+1*3.030839284647634*sin(\t r)});
\draw [shift={(-0.38203463203463006,0.22809523809523824)},line width=1.2pt,color=ffccww] plot[domain=2.3916774267223544:3.7739463618427003,variable=\t]({1*8.475296858916549*cos(\t r)+0*8.475296858916549*sin(\t r)},{0*8.475296858916549*cos(\t r)+1*8.475296858916549*sin(\t r)});
\draw [shift={(-0.38203463203463006,0.22809523809523824)},line width=1.2pt,color=bfffqq] plot[domain=2.526954826454062:3.491220074187166,variable=\t]({1*10.003940229332981*cos(\t r)+0*10.003940229332981*sin(\t r)},{0*10.003940229332981*cos(\t r)+1*10.003940229332981*sin(\t r)});
\draw[fill=ffxfqq] (-0.38203463203463006,0.22809523809523824) circle (2pt);
\draw[color=ffxfqq] (-0.38203463203463006+0.35,0.22809523809523824) node {$O_5$};
\draw [fill=qqffff] (-6.304112554112552,0.4532034632034633) circle (2pt);
\draw[color=qqffff] (-6.304112554112552,0.4532034632034633+0.35) node {$O_1$};
\draw [fill=qqffff] (-4.13,0.79) circle (2pt);
\draw[color=qqffff] (-3.9872294372294346+0.1,1.1545021645021643-0.05) node {$O_2$};
\draw [fill=qqffff] (-5.213203463203461,1.3016883116883113) circle (2pt);
\draw[color=qqffff] (-5.078138528138525-0.27,1.6739826839826835-0.1) node {$O_3$};
\draw [fill=ffqqqq] (-4.9846320346320345,0.79) circle (2pt);
\draw[color=ffqqqq] (-4.9846320346320345+0.25,0.79-0.25) node {$O_4$};
\draw[color=ffccww] (-7.485064935064932+0.85,-3.797878787878786-0.3) node {Inter. + 1};
\draw[color=cczzqq] (-2.2729437229437197-0.85,2.85147186147186) node {Inter. + 2};
\draw[color=ffccww] (0.6534632034632066-0.1,1.0159740259740258+0.5) node {Inter. + 1};
\draw[color=bfffqq] (-9.649567099567097-0.3,-2.8281818181818172-0.65) node {Intersection constant};
\end{tikzpicture}");[/asy][/asy]
$\color{magenta} \rule{25cm}{2pt}$
$\color{magenta} \textbf{Whole Structure, Step-by-step.}$ (This is a bit hard to put to words; but I think I've done all I can to word this efficiently.)
First, transform the problem statement from $O_i$ (center of $C_i$) being in the circumference of $C_{i+1}$ to $O_{i+1}$ being in the circumference of $C_i$.
Then, start with a random circle $C_1$; call that moment $t_1$. Denote by $t_i$ the moment after placing $i$ circles from $C_1$ to $C_i$ in order. This is (almost) equivalent to the method in $\#4$ of placing $C_i$ first, then $C_{i-1}$, up to $C_{i-(n-1)} = C_{i+1}$ last. (Then again, this Solution structurally similar to that, but I didn't believe the premise beforehand and tried to make it comprehensive)
For each moment $t_i$, define $G_i$ to be the graph formed with intersections, $I_i$ to be the counter to identify the number of intersections that has formed, and $L_i$ the locus of $C_{i+1}$'s center (or $C_i$'s circumference, for that matter.)
Arguably, the most important constant is this: let $N_i$ to be the number of connected components in $t_i$. This number will (expectedly) relate to all three things mentioned above.
The Claims are then:
From the $N_i$ connected components of the circles (or the figures, I might say), $\textbf{clear layers}$ are formed; the first layer/component is entirely inside all other $N_i-1$ layers and et cetera,
$L_i$ is always at the outermost component,
and finally, if $I_i = I_{i-1}$, then $N_i = N_{i-1}+1$; similarly, if $N_{i-1} - N_i = k \geq 0$, then $I_i \geq I_{i-1} + k +1$.
$\color{magenta} \rule{25cm}{0.4pt}$
$\color{magenta} \textbf{Proof.}$ This is done inductively. Since there is only one circle on $t_1$, the three statements are trivial. Let the statement to be true for $i = M$ (a large $M$ for accentuation), and we'd like to prove it for $i = M+1$.
However, the three statements are weaker than you might imagine; it's sufficient to use the second condition to prove all three statements (except for the first; it will use both the first and the second, for that matter.)
Name the connected components/layers in $t_M$ to be $S_1,S_2,\ldots,S_{N_M}$. We will tackle the easy case first: let $C_{M+1}$ gains full score against the $M$ given circles. Provided that that circle is exterior of $C_M$ (due to the problem condition), by $\color{red} \text{A More Complicated Result}$ then it lies outside the layer $S_{N_M}$.
This will add a new layer $S_{N_{M+1}}$ outside the existing layers; and the three statements will hold immediately.
Now consider the case when $C_{M+1}$ reaches up to the $k+1^{\text{th}}$ outermost layer (the layer $S_{N_M}$ is considered the first outermost layer), then it will intersect all those layers since $C_{M+1}$ has a point outside $S_{N_M}$ (as its center lie on that layer) and has a point inside $S_{N_{M-k}}$ (which also lies on each of $S_{N_{M-k+i}}$, $1 \leq i \leq k$).
So, the outermost $k+1$ layers will merge into one, meaning that $N_{M+1} = N_{M}-k$, the number of created intersections will increase by $k+1$, and $L_{M+1}$ is on that aforementioned layer; which is the outermost layer among the $N_M-k$ new layers; and the structure mentioned in the first statement is naturally formed as all the non-intersected layers will all be inside the $N_M-k^{\text{th}}$ layer. $\blacksquare$ $\blacksquare$
[asy][asy]usepackage("tikz");label("\begin{tikzpicture}
\definecolor{ffqqqq}{rgb}{1,0,0}
\definecolor{qqffff}{rgb}{0,1,1}
\definecolor{ffxfqq}{rgb}{1,0.4980392156862745,0}
\draw [line width=1.2pt,color=qqffff] (-6.304112554112552,0.4532034632034633) circle (2.2000448416220855cm);
\draw [line width=1.2pt,color=qqffff] (-4.13,0.79) circle (1.1979794117656644cm);
\draw [line width=1.2pt,color=qqffff] (-5.213203463203461,1.3016883116883113) circle (0.5604193307494106cm);
\draw [line width=1.2pt,color=ffqqqq] (-4.9846320346320345,0.79) circle (4.636770407497834cm);
\draw [shift={(-0.38203463203463006,0.22809523809523824)},line width=1pt,dash pattern=on 7pt off 2.8pt,color=ffxfqq] plot[domain=1.5622738058679497:4.014631845434289,variable=\t]({1*5.926354750449396*cos(\t r)+0*5.926354750449396*sin(\t r)},{0*5.926354750449396*cos(\t r)+1*5.926354750449396*sin(\t r)});
\draw[fill=ffxfqq] (-0.38203463203463006,0.22809523809523824) circle (2pt);
\draw[color=ffxfqq] (-0.38203463203463006+0.35,0.22809523809523824) node {$O_n$};
\draw [fill=qqffff] (-6.304112554112552,0.4532034632034633) circle (2pt);
\draw[color=qqffff] (-6.304112554112552-0.34,0.4532034632034633+0.35-0.35) node {$O_1$};
\draw [fill=qqffff] (-4.13,0.79) circle (2pt);
\draw[color=qqffff] (-3.9872294372294346+0.1,1.1545021645021643-0.05) node {$O_2$};
\draw [fill=qqffff] (-5.213203463203461,1.3016883116883113) circle (2pt);
\draw[color=qqffff] (-5.078138528138525-0.27,1.6739826839826835-0.1) node {$O_3$};
\draw [fill=ffqqqq] (-4.9846320346320345,0.79) circle (2pt);
\draw[color=ffqqqq] (-4.9846320346320345+0.25,0.79-0.25) node {$O_4$};
\end{tikzpicture}");[/asy][/asy]
$\color{blue} \rule{25cm}{2pt}$
$\color{blue} \textbf{A Quick Finish: Connectivity.}$ Resume the above process until $C_{n-1}$. For the last circle $C_n$, there are two ways to proceed: the complicated and simple way.
$\color{blue} \rule{25cm}{0.4pt}$
$\color{blue} \textbf{1: Explicit Counting.}$ Let there are $l$ layers at $t_{n-1}$. Since there are $1$ layer and $0$ intersection counter at $t_1$; while after each moment, the total number of $N_i$ and $I_i$ will increase by at least $1$, so there are at least $n-1-l$ intersections that have occured.
Now since the circle $C_n$ will have a point outside the outermost layer, and a point inside the innermost layer (that is, the center of $C_1$), so there are at least $l$ more intersections that are formed. In total, that creates $n-1$ intersections. So, as each intersection of pairs of circles will hinder one score, the total maximum of score is
\[ \binom{n}{2} - (n-1) = \dfrac{n(n-1)}{2} - (n-1) = \binom{n-1}{2} \]$\color{blue} \textbf{2: Connectivity.}$ Turns out, we don't need to use the third statement to prove that $G_n$ is connected!
Let there are $l$ layers at $t_{n-1}$. Following the third paragraph of the proof (the $k+1^{\text{th}}$ outermost layer one), $C_n$'s scope will range through the outermost layer to the innermost, implying that $C_n$ will unify all connected components into one simple layer. By then, all circles are connected --- and by the basic property of a connected graph; there are at least $n-1$ edges in one.
We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$
Note: Don't forget the construction! Hopefully, after you've attempted this problem and read through this very long exposition, lots of them will pop up naturally as a result of experimentation.
With that said, the easy one to mention is the config so that each $C_i$ will be contained properly in $C_{i+1}$, for each $1 \leq i \leq n-1$ (according to my renewed convention that $O_{i+1}$ is in the circumference of $C_i$).
Also, the Motivation for this is interesting to write, but I think this post is already lengthy and motivated enough for the reader to understand most of it without much questioning. If anything, almost all of the above schemes (and the ones in post $\#2,3,4$) are due to induction in removing quirky circles:
the closest one tho this post is probably $\#2$, with defining an outer layer consisting of one large circle, and see how tight the intersections and scoring for $C_n$ are
post $\#3$ abuses the fact that after converted to an open-set system, the centers of the circles are useless; and the fact that $C_2$ is not inside $C_1$, $\ldots$, $C_1$ is not inside $C_n$ makes up grounds to assume that $C_i$ must be inside $C_{i+1}$ for the score to not plummet ultimately; and remove either $C_i$ or $C_{i+1}$ with suboptimal degree,
and this is basically just $\#4$ with comprehensive details on why $G_n$ is connected.