XI APMO

Lemma 1. Let $P$ and $Q$ be two points of $S$. The number of good circles that contain $P$ and $Q$ on their circumference is odd.



Let $N$ be the number of good circles that pass through $P$ and $Q$. Number the points on one side of the line $PQ$ by $A_1,A_2,\dots ,A_k$ and those on the other side by $B_1,B_2,\dots ,B_m$ in such a way that if $\angle P{A}_{i}Q={\alpha }_i$, $\angle P{B}_{j}Q=180-{\beta }_j$ then ${\alpha }_1>{\alpha }_2>\dots >{\alpha }_k$ and ${\beta }_1>{\beta }_2>\dots >{\beta }_m$.

Note that the angles ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k,{\beta }_1,{\beta }_2,\dots ,{\beta }_m$ are all distinct since there are no four points in $S$ that are concyclic.

Observe that the circle that passes through $P,Q$ and $A_i$ has $A_j$ in its interior when ${\alpha }_j>{\alpha }_i$, that is, when $i>j$; and it contains $B_j$ in its interior when ${\alpha }_i+180-{\beta }_j>180$, that is, when ${\alpha }_i>{\beta }_j$. Similar conditions apply to the circle that contains $P,Q$ and $B_j$.

Order the angles ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_k,{\beta }_1,{\beta }_2,\dots ,{\beta }_m$ from the greatest to least. Now transform $S$ as follows. Consider a ${\beta }_j$ that has an ${\alpha }_i$ immediately to its left in such an ordering ($\dots >{\alpha }_i>{\beta }_j\dots$). Consider a new set $S^{\prime }$ that contains the same points as $S$ except for $A_i$ and $B_j$. These two points will be replaced by $A_i^{\prime }$ and $B_j^{\prime }$ that satisfy $\angle P{A}_i^{\prime }Q={\beta }_j={\alpha }_i^{\prime }$ and $\angle P{B}_j^{\prime }Q=180-{\alpha }_i=180-{\beta }_j^{\prime }$. Thus ${\beta }_j$ and ${\alpha }_i$ have been interchanged and the ordering of the $\alpha$'s and $\beta$'s has only changed with respect to the relative order of ${\alpha }_i$ and ${\beta }_j$; we continue to have $${\alpha }_1>{\alpha }_2>\dots >{\alpha }_{i-1}>{\alpha }_i^{\prime }>{\alpha }_{i+1}>\dots >{\alpha }_k$$ and $${\beta }_1>{\beta }_2>\dots >{\beta }_{j-1}>{\beta }_j^{\prime }>{\beta }_{j+1}>\dots >{\beta }_m.$$

Analyze the good circles in this new set $S^{\prime }$. Clearly, a circle through $P,Q,A_r$ ($r\ne i$) or through $P,Q,B_s$ ($s\ne j$) that was good in $S$ will also be good in $S^{\prime }$, because the order of $A_r$ (or $B_s$) relative to the rest of the points has not changed, and therefore the number of points in the interior or exterior of this circle has not changed. The only changes that could have taken place are:

a) If the circle $P,Q,A_i$ was good in $S$, the circle $P,Q,A_i^{\prime }$ may not be good in $S^{\prime }$. b) If the circle $P,Q,B_j$ was good in $S$, the circle $P,Q,B_j^{\prime }$ may not be good in $S^{\prime }$. c) If the circle $P,Q,A_i$ was not good in $S$, the circle $P,Q,A_i^{\prime }$ may be good in $S^{\prime }$. d) If the circle $P,Q,B_j$ was not good in $S$, the circle $P,Q,B_j^{\prime }$ may be good in $S^{\prime }$.

But observe that the circle $P,Q,A_i$ contains the points $A_1,A_2,\dots ,A_{i-1},B_j,B_{j+1},\dots ,B_m$ and does not contain the points $A_{i+1},A_{i+2},\dots ,A_k,B_1,B_2,\dots ,B_{j-1}$ in its interior. Then this circle is good if and only if $i+m-j=k-i+j-1$, which we rewrite as $j-i=\frac{1}{2}(m-k+1)$. On the other hand, the circle $P,Q,B_j$ contains the points $B_{j+1},B_{j+2},\dots ,B_m,A_1,A_2,\dots ,A_i$ and does not contain the points $B_1,B_2,\dots ,B_{j-1},A_{i+1},A_{i+2},\dots ,A_k$ in its interior. Hence this circle is good if and only if $m-j+i=j-1+k-i$, which we rewrite as $j-i=\frac{1}{2}(m-k+1)$.

Therefore, the circle $P,Q,A_i$ is good if and only if the circle $P,Q,B_j$ is good. Similarly, the circle $P,Q,A_i^{\prime }$ is good if and only if the circle $P,Q,B_j^{\prime }$ is good. That is to say, transforming $S$ into $S^{\prime }$ we lose either 0 or 2 good circles of $S$ and we gain either 0 or 2 good circles in $S^{\prime }$.

Continuing in this way, we may continue to transform $S$ until we obtain a new set $S_0$ such that the angles ${\alpha }_1^{\prime },{\alpha }_2^{\prime },\dots ,{\alpha }_k^{\prime },{\beta }_1^{\prime },{\beta }_2^{\prime },\dots ,{\beta }_m^{\prime }$ satisfy $${\beta }_1^{\prime }>{\beta }_2^{\prime }>\dots >{\beta }_m^{\prime }>{\alpha }_1^{\prime }>{\alpha }_2^{\prime }>\dots >{\alpha }_k^{\prime }$$ and such that the number of good circles in $S_0$ has the same parity as $N$. We claim that $S_0$ has exactly one good circle. In this configuration, the circle $P,Q,A_i$ does not contain any $B_j$ and the circle $P,Q,B_r$ does not contain any $A_s$ (for all $i,j$), because ${\alpha }_a+(180-{\beta }_b)<180$ for all $a,b$. Hence, the only possible good circles are $P,Q,B_{m-n+1}$ (which contains the $n-1$ points $B_{m-n+2},B_{m-n+3},\dots ,B_m$), if $m-n+1>0$, and the circle $P,Q,A_n$ (which contains the $n-1$ points $A_1,A_2,\dots ,A_n$), if $n\le k$. But, since $m+k=2n-1$, which we rewrite as $m-n+1=n-k$, exactly one of the inequalities $m-n+1>0$ and $n\le k$ is satisfied. It follows that one of the points $B_{m-n+1}$ and $A_n$ corresponds to a good circle and the other does not. Hence, $S_0$ has exactly one good circle, and $N$ is odd.

Now consider the $\left(\genfrac{}{}{0ex}{}{2n+1}{2}\right)$ pairs of points in $S$. Let $a_{2k+1}$ be the number of pairs of points through which exactly $2k+1$ good circles pass. Then $$a_1+a_3+a_5+\dots =\left(\genfrac{}{}{0ex}{}{2n+1}{2}\right)$$ But then the number of good circles in $S$ is $$\begin{array}{rl}\frac{1}{3}(a_1+3a_3+5a_5+7a_7+\dots )& \equiv a_1+3a_3+5a_5+7a_7+\dots \\ & \equiv a_1+a_3+a_5+a_7+\dots \\ & \equiv \left(\genfrac{}{}{0ex}{}{2n+1}{2}\right)\\ & \equiv n(2n+1)\\ & \equiv n(\mathrm{mod}2)\end{array}$$ Here we have taken into account that each good circle is counted 3 times in the expression $a_1+3a_3+5a_5+7a_7+\dots$. The desired result follows.

Alternative Proof of Lemma 1:

Let $A_1,A_2,\dots ,A_{2n-1}$ be the $2n-1$ given points other than $P$ and $Q$. Invert the plane with respect to point $P$. Let $O,B_1,B_2,\dots ,B_{2n-1}$ be the images of points $Q,A_1,A_2,\dots ,A_{2n-1}$, respectively, under this inversion. Call point $B_i$ "good" if the line $O{B}_i$ splits the points $B_1,B_2,\dots ,B_{i-1},B_{i+1},\dots ,B_{2n-1}$ evenly, leaving $n-1$ of them to each side of it. (Notice that no other $B_j$ can lie on the line $O{B}_i$, or else the points $P,Q,A_i$ and $A_j$ would be concyclic.) Then it is clear that the circle through $P,Q$ and $A_i$ is good if and only if point $B_i$ is good. Therefore, it suffices to prove that the number of good points is odd.

Notice that the good points depend only on the relative positions of rays $O{B}_1,O{B}_2,\dots ,O{B}_{2n-1}$, and not on the exact positions of points $B_1,B_2,\dots ,B_{2n-1}$. Therefore we may assume, for simplicity, that $B_1,B_2,\dots ,B_{2n-1}$ lie on the unit circle $\Gamma$ with center $O$.

Let $C_1,C_2,\dots ,C_{2n-1}$ be the points diametrically opposite to $B_1,B_2,\dots ,B_{2n-1}$ in $\Gamma$. As remarked earlier, no $C_i$ can coincide with one of the $B_j$'s. We will call the $B_i$'s "white points", and the $C_i$'s "black points". We will refer to these $4n-2$ points as the "colored points".

Now we prove that the number of good points is odd, which will complete the proof of the lemma. We proceed by induction on $n$. If $n=1$, the result is trivial. Now assume that the result is true for $n=k$, and consider $2k+1$ white points $B_1,B_2,\dots ,B_{2k+1}$ on the circle $\Gamma$ (no two of which are diametrically opposite), and their diametrically opposite black points $C_1,C_2,\dots ,C_{2k+1}$. Call this configuration of points "configuration 1". It is clear that we must have two consecutive colored points on $\Gamma$ which have different colors, say $B_i$ and $C_j$. Now remove points $B_i,B_j,C_i$ and $C_j$ from $\Gamma$, to obtain "configuration $2^{\prime \prime }$", a configuration with $2k-1$ points of each color.

It is easy to verify the following two claims: 1. Point $B_i$ is good in configuration 1 if and only if point $B_j$ is good in configuration 1. 2. Let $k\ne i,j$. Then point $B_k$ is good in configuration 1 if and only if it is good in configuration 2.

It follows that, by removing points $B_i,B_j,C_i$ and $C_j$, the number of good points can either stay the same, or decreases by two. In any case, its parity remains unchanged. Since we know, by the induction hypothesis, that the number of good points in configuration 2 is odd, it follows that the number of good points in configuration 1 is also odd. This completes the proof.

Another Approach to Lemma 1:

One can give another inductive proof of lemma 1, which combines the ideas of the two proofs that we have given. The idea is to start as in the first proof, with the characterization of the points inside a given circle.

Then we transform the set $S$ by removing the points $A_i$ and $B_j$ instead of replacing them by $A_i^{\prime }$ and $B_j^{\prime }$.

It can be shown that every one of the remaining circles going through $P$ and $Q$ contained exactly one of $A_i$ and $B_j$. Therefore, the only good circles we could have gained or lost are $P,Q,A_i$ and $P,Q,B_j$.

Finally, we show that either both or none of these circles were good, so the parity of the number of good circles isn't changed by this transformation.