Maths Olympiad Prep

Library / /309 of 377

Geometry Difficulty 5.5 AIME, harder Prove it United States

Problem:
A sphere is the set of points at a fixed positive distance rr from its center. Let S\mathcal{S} be a set of 2010-dimensional spheres. Suppose that the number of points lying on every element of S\mathcal{S} is a finite number nn. Find the maximum possible value of nn.

Solutions — 2

Solution 1

Solution:
The answer is 22 for any number of dimensions. We prove this by induction on the dimension.

Note that 1-dimensional spheres are pairs of points, and 2-dimensional spheres are circles.

Base case, d=2d=2:
The intersection of two circles is either a circle (if the original circles are identical and in the same place), a pair of points, a single point (if the circles are tangent), or the empty set. Thus, in dimension 22, the largest finite number of intersection points is 22, because the number of pairwise intersection points is 00, 11, or 22 for distinct circles.

We now prove that the intersection of two kk-dimensional spheres is either the empty set, a (k1)(k-1)-dimensional sphere, or a kk-dimensional sphere (which only occurs if the original spheres are identical and coincident). Consider two spheres in kk-dimensional space, and impose a coordinate system such that the centers of the two spheres lie on one coordinate axis. Then the equations for the two spheres become identical in all but one coordinate:

(x1a1)2+x22++xk2=r12(x1a2)2+x22++xk2=r22 \begin{aligned} & (x_{1}-a_{1})^{2} + x_{2}^{2} + \ldots + x_{k}^{2} = r_{1}^{2} \\ & (x_{1}-a_{2})^{2} + x_{2}^{2} + \ldots + x_{k}^{2} = r_{2}^{2} \end{aligned}

If a1=a2a_{1} = a_{2}, the spheres are concentric, and so they are either nonintersecting or coincident, intersecting in a kk-dimensional sphere. If a1a2a_{1} \neq a_{2}, then subtracting the equations and solving for x1x_{1} yields x1=r12a12r22+a222(a2a1)x_{1} = \frac{r_{1}^{2} - a_{1}^{2} - r_{2}^{2} + a_{2}^{2}}{2(a_{2} - a_{1})}. Plugging this into either equation above yields a single equation that describes a (k1)(k-1)-dimensional sphere.

Assume we are in dimension dd, and suppose for induction that for all kk less than dd, any two distinct kk-dimensional spheres intersecting in a finite number of points intersect in at most two points. Suppose we have a collection of dd-dimensional spheres s1,s2,,sms_{1}, s_{2}, \ldots, s_{m}. Without loss of generality, suppose the sis_{i} are distinct. Let tit_{i} be the intersection of sis_{i} and si+1s_{i+1} for 1i<m1 \leq i < m. If any tit_{i} are the empty set, then the intersection of the tit_{i} is empty. None of the tit_{i} is a dd-dimensional sphere because the sis_{i} are distinct. Thus each of t1,t2,,tm1t_{1}, t_{2}, \ldots, t_{m-1} is a (d1)(d-1)-dimensional sphere, and the intersection of all of them is the same as the intersection of the dd-dimensional spheres. We can then apply the inductive hypothesis to find that t1,,tm1t_{1}, \ldots, t_{m-1} intersect in at most two points. Thus, by induction, a set of spheres in any dimension which intersect at only finitely many points intersect at at most two points.

We now exhibit a set of 220092^{2009} 2010-dimensional spheres, and prove that their intersection contains exactly two points. Take the spheres with radii 2013\sqrt{2013} and centers (0,±1,±1,,±1)(0, \pm 1, \pm 1, \ldots, \pm 1), where the sign of each coordinate is independent from the sign of every other coordinate. Because of our choice of radius, all these spheres pass through the points (±2,0,0,,0)(\pm 2, 0, 0, \ldots, 0). Then the intersection is the set of points (x1,x2,,x2010)(x_{1}, x_{2}, \ldots, x_{2010}) which satisfy the equations x12+(x2±1)2++(x2010±1)2=2013x_{1}^{2} + (x_{2} \pm 1)^{2} + \cdots + (x_{2010} \pm 1)^{2} = 2013. The only solutions to these equations are the points (±2,0,0,,0)(\pm 2, 0, 0, \ldots, 0) (since (xi+1)2(x_{i} + 1)^{2} must be the same as (xi1)2(x_{i} - 1)^{2} for all i>1i > 1, because we may hold all but one of the ±\pm choices constant, and change the remaining one).

Therefore, the maximum possible value of nn is 22.

Solution 2

Solution:
Answer: 2 The answer is 2 for any number of dimensions. We prove this by induction on the dimension.

Note that 1-dimensional spheres are pairs of points, and 2-dimensional spheres are circles.

Base case, d=2d=2 : The intersection of two circles is either a circle (if the original circles are identical, and in the same place), a pair of points, a single point (if the circles are tangent), or the empty set. Thus, in dimension 2, the largest finite number of intersection points is 2, because the number of pairwise intersection points is 0, 1, or 2 for distinct circles.

We now prove that the intersection of two kk-dimensional spheres is either the empty set, a (k1)(k-1)-dimensional sphere, a kk-dimensional sphere (which only occurs if the original spheres are identical and coincident). Consider two spheres in kk-dimensional space, and impose a coordinate system such that the centers of the two spheres lie on one coordinate axis. Then the equations for the two spheres become identical in all but one coordinate:
(x1a1)2+x22++xk2=r12(x1a2)2+x22++xk2=r22 \begin{aligned} & \left(x_{1}-a_{1}\right)^{2}+x_{2}^{2}+\ldots+x_{k}^{2}=r_{1}^{2} \\ & \left(x_{1}-a_{2}\right)^{2}+x_{2}^{2}+\ldots+x_{k}^{2}=r_{2}^{2} \end{aligned}
If a1=a2a_{1}=a_{2}, the spheres are concentric, and so they are either nonintersecting or coincident, intersecting in a kk-dimensional sphere. If a1a2a_{1} \neq a_{2}, then subtracting the equations and solving for x1x_{1} yields x1=r12a12r22+a222(a2a1)x_{1}=\frac{r_{1}^{2}-a_{1}^{2}-r_{2}^{2}+a_{2}^{2}}{2\left(a_{2}-a_{1}\right)}. Plugging this in to either equation above yields a single equation that describes a (k1)(k-1)-dimensional sphere.

Assume we are in dimension dd, and suppose for induction that for all kk less than dd, any two distinct kk-dimensional spheres intersecting in a finite number of points intersect in at most two points. Suppose we have a collection of dd-dimensional spheres s1,s2,,sms_{1}, s_{2}, \ldots, s_{m}. Without loss of generality, suppose the sis_{i} are distinct. Let tit_{i} be the intersection of sis_{i} and si+1s_{i+1} for 1i<m1 \leq i < m. If any tit_{i} are the empty set, then the intersection of the tit_{i} is empty. None of the tit_{i} is a dd-dimensional sphere because the sis_{i} are distinct. Thus each of t1,t2,,tm1t_{1}, t_{2}, \ldots, t_{m-1} is a (d1)(d-1)-dimensional sphere, and the intersection of all of them is the same as the intersection of the dd-dimensional spheres. We can then apply the inductive hypothesis to find that t1,,tm1t_{1}, \ldots, t_{m-1} intersect in at most two points. Thus, by induction, a set of spheres in any dimension which intersect at only finitely many points intersect at at most two points.

We now exhibit a set of 220092^{2009} 2010-dimensional spheres, and prove that their intersection contains exactly two points. Take the spheres with radii 2013\sqrt{2013} and centers (0,±1,±1,,±1)(0, \pm 1, \pm 1, \ldots, \pm 1), where the sign of each coordinate is independent from the sign of every other coordinate. Because of our choice of radius, all these spheres pass through the points (±2,0,0,,0)( \pm 2, 0, 0, \ldots, 0). Then the intersection is the set of points (x1,x2,,x2010)\left(x_{1}, x_{2}, \ldots, x_{2010}\right) which satisfy the equations x12+(x2±1)2++(x2010±1)2=2013x_{1}^{2}+\left(x_{2} \pm 1\right)^{2}+\cdots+\left(x_{2010} \pm 1\right)^{2}=2013. The only solutions to these equations are the points (±2,0,0,,0)( \pm 2, 0, 0, \ldots, 0) (since (xi+1)2\left(x_{i}+1\right)^{2} must be the same as (xi1)2\left(x_{i}-1\right)^{2} for all i>1i>1, because we may hold all but one of the ±\pm choices constant, and change the remaining one).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.