uniolympiads Ελληνικά

IMC 2004, Day 1, Problem 4

Suppose n≥4n \ge 4 and let MM be a finite set of nn points in R3\mathbb{R}^3, no four of which lie in a plane. Assume that the points can be coloured black or white so that any sphere which intersects MM in at least four points has the property that exactly half of the points in the intersection of MM and the sphere are white. Prove that all of the points in MM lie on one sphere.

Original from the official PDFSuppose n ≥ 4 and let M be a finite set of n points in R 3 , no four of which lie in a plane. Assume that the points can be coloured black or white so that any sphere which intersects M in at least four points has the property that exactly half of the points in the intersection of M and the sphere are white. Prove that all of the points in M lie on one sphere. [20 points]

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. Define f:M→{−1,1}f : M \to \{-1, 1\}, f(X)={−1, if X is white1, if X is blackf(X) = \left\{\begin{array}{c} -1, \text{ if } X \text{ is white} \\ 1, \text{ if } X \text{ is black}\end{array}\right.. The given condition becomes ∑X∈Sf(X)=0\sum_{X\in S} f(X) = 0 for any sphere SS which passes through at least 4 points of MM. For any 3 given points AA, BB, CC in MM, denote by S(A,B,C)S(A,B,C) the set of all spheres which pass through AA, BB, CC and at least one other point of MM and by ∣S(A,B,C)∣|S(A,B,C)| the number of these spheres. Also, denote by ∑\sum the sum ∑X∈Mf(X)\sum_{X\in M} f(X).

We have

0=∑S∈S(A,B,C)∑X∈Sf(X)=(∣S(A,B,C)∣−1)(f(A)+f(B)+f(C))+∑(1)0 = \sum_{S\in S(A,B,C)} \sum_{X\in S} f(X) = (|S(A,B,C)| - 1)(f(A) + f(B) + f(C)) + \sum \tag{1}
since the values of AA, BB, CC appear ∣S(A,B,C)∣|S(A,B,C)| times each and the other values appear only once.

If there are 3 points AA, BB, CC such that ∣S(A,B,C)∣=1|S(A,B,C)| = 1, the proof is finished.

If ∣S(A,B,C)∣>1|S(A,B,C)| > 1 for any distinct points AA, BB, CC in MM, we will prove at first that ∑=0\sum = 0.

Assume that ∑>0\sum > 0. From (1) it follows that f(A)+f(B)+f(C)<0f(A) + f(B) + f(C) < 0 and summing by all (n3)\binom{n}{3} possible choices of (A,B,C)(A,B,C) we obtain that (n3)∑<0\binom{n}{3}\sum < 0, which means ∑<0\sum < 0 (contradicts the starting assumption). The same reasoning is applied when assuming ∑<0\sum < 0.

Now, from ∑=0\sum = 0 and (1), it follows that f(A)+f(B)+f(C)=0f(A) + f(B) + f(C) = 0 for any distinct points AA, BB, CC in MM. Taking another point D∈MD \in M, the following equalities take place

f(A)+f(B)+f(C)=0f(A)+f(B)+f(D)=0f(A)+f(C)+f(D)=0f(B)+f(C)+f(D)=0\begin{aligned} f(A) + f(B) + f(C) &= 0 \\ f(A) + f(B) + f(D) &= 0 \\ f(A) + f(C) + f(D) &= 0 \\ f(B) + f(C) + f(D) &= 0 \end{aligned}
which easily leads to f(A)=f(B)=f(C)=f(D)=0f(A) = f(B) = f(C) = f(D) = 0, which contradicts the definition of ff.

Transcribed from the official solutions, page 2. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?