Let $ n\geq 3 $ be an integer and let $ p\geq 2n-3 $ be a prime number. For a set $ M $ of $ n $ points in the plane, no 3 collinear, let $ f: M\to \{0,1,\ldots, p-1\} $ be a function such that (i) exactly one point of $ M $ maps to 0, (ii) if a circle $ \mathcal{C} $ passes through 3 distinct points of $ A,B,C\in M $ then $ \sum_{P\in M\cap \mathcal{C}} f(P) \equiv 0 \pmod p $. Prove that all the points in $ M $ lie on a circle.
Problem
Source: Romanian IMO Team Selection Test TST 1996, problem 12
Tags: function, modular arithmetic, algebra, domain, combinatorics proposed, combinatorics
07.05.2010 14:34
Well, let us suppose for the sake of contradiction that there exist points $B,C$ such that no other point $\in S$ lies on the circle $C(A,B,C)$. This implies that $f(B) + f(C) \equiv 0\pmod p $. Therefore, we can say that if we have $f(B) = i$, then we must have $f(C) = p-i$. Now, let us denote $L= \sum_{X \in S} f(X)$. Consider $b$ circles passing through $A, B$ and other points of $S$ and $c$ circles passing through $A,C$ and other points of $S$. Thus applying the given condition for all such circles, we have : $L + (b-1) i \equiv 0\pmod p $ and $L + (c-1)(p-i) \equiv 0\pmod p $. This implies, $a+b - 2 \equiv 0\pmod p $. Now, remember that $b,c \ge 1$ and $b,c \le n-2$. This implies $2\le b+c \le 2n-4 <2n-3 \le p$ (Given that $p \ge 2n-3)$ This would imply that $a=b=1$, which is clearly a contradiction. Therefore, we get that for any two points $B,C \in S$, there will exist atleast one more point being to $C(A,B,C)$ lying in $S$. Therefore, all points of $S$ lie on a circle. We can indeed consider an inversion $I$ of center $A$. The set of points $S- {A}$ is transformed to the set of points $(S- {A} )'$ under the inversion. Let us call it as $M$. Also, circles $C(A, P, Q)$ with $P,Q \in S$ get transformed to lines $I_P I_Q$ using points of $M$. Thus , the condition is equivalent to : For two points of $I_P, I_Q$ in $M$, there should exist another point of $M$ lying on $I_PI_Q$. But this is true and hence we prove the inversive images are collinear thereby making the original domain concyclic.
07.05.2010 16:17
Dear Agr_94_Math, What are S and A? Please define your variables.
07.05.2010 19:07
I am very sorry Batominovski, I have used $S$ for $M$ and $A$ is the point of $ M$ for which $f(A)= 0 $.