2025 USAMO Problems/Problem 3
Contents
[hide]Problem
Alice the architect and Bob the builder play a game. First, Alice chooses two points 
and 
in the plane and a subset 
of the plane, which are announced to Bob. Next, Bob marks infinitely many points in the plane, designating each a city. He may not place two cities within distance at most one unit of each other, and no three cities he places may be collinear. Finally, roads are constructed between the cities as follows: for each pair 
of cities, they are connected with a road along the line segment 
if and only if the following condition holds: For every city 
distinct from 
and 
, there exists 
such that 
is directly similar to either 
or 
. Alice wins the game if (i) the resulting roads allow for travel between any pair of cities via a finite sequence of roads and (ii) no two roads cross. Otherwise, Bob wins. Determine, with proof, which player has a winning strategy.
Note: 
is directly similar to 
if there exists a sequence of rotations, translations, and dilations sending 
to 
, 
to 
, and 
to 
.
Solution 1
https://artofproblemsolving.com/wiki/index.php/File:2025_USAMO_PROBLEM_3.jpeg
The answer is that Alice wins. Let’s define a Bob-set V to be a set of points in the plane with no three collinear and with all distances at least 1. The point of the problem is to prove the following fact. Claim — Given a Bob-set V ⊆ R 2 , consider the Bob-graph with vertex set V defined as follows: draw edge ab if and only if the disk with diameter ab contains no other points of V on or inside it. Then the Bob-graph is (i) connected, and (ii) planar. Proving this claim shows that Alice wins since Alice can specify S to be the set of points outside the disk of diameter P Q. Proof that every Bob-graph is connected. Assume for contradiction the graph is disconnected. Let p and q be two points in different connected components. Since pq is not an edge, there exists a third point r inside the disk with diameter pq. Hence, r is in a different connected component from at least one of p or q — let’s say point p. Then we repeat the same argument on the disk with diameter pr to find a new point s, non-adjacent to either p or r. See the figure below, where the X’ed out dashed edges indicate points which are not only non-adjacent but in different connected components.
In this way we generate an infinite sequence of distances δ1, δ2, δ3, . . . among the non-edges in the picture above. By the “Pythagorean theorem” (or really the inequality for it), we have δi2 ≤ δi-12− 1 and this eventually generates a contradiction for large i, since we get 0 ≤ δi2≤ δi2− (i − 1). Proof that every Bob-graph is planar. Assume for contradiction edges ac and bd meet, meaning abcd is a convex quadrilateral. WLOG assume ∠bad ≥ 90◦ (each quadrilateral has an angle at least 90◦ ). Then the disk with diameter bd contains a, contradiction.
Remark. In real life, the Bob-graph is actually called the Gabriel graph. Note that we never require the Bob-set to be infinite; the solution works unchanged for finite Bob-sets. However, there are approaches that work for finite Bob-sets that don’t work for infinite sets, such as the relative neighbor graph, in which one joins a and b iff there is no c such that d(a, b) ≤ max{d(a, c), d(b, c)}. In other words, edges are blocked by triangles where ab is the longest edge (rather than by triangles where ab is the longest edge of a right or obtuse triangle as in the Gabriel graph). The relative neighbor graph has fewer edges than the Gabriel graph, so it is planar too. When the Bob-set is finite, the relative distance graph is still connected. The same argument above works where the distances now satisfy δ1 > δ2 > . . . instead, and since there are finitely many distances one arrives at a contradiction.
However for infinite Bob-sets the descending condition is insufficient, and connectedness actually fails altogether. A counterexample is to start by taking An ≈ (2n, 0) and Bn ≈ (2n + 1, √ 3) for all n ≥ 1, then perturb all the points slightly so that B1A1 > A1A2 > A2B1 > B1B2 > B2A2 > A2A3 > A3B2 > B2B3 > B3A3 > · · · . In that case, {An} and {Bn} will be disconnected from each other: none of the edges AnBn or B n A n+1 are formed. In this case the relative neighbor graph consists of the edges A1A2A3A4 · · · and B1B2B3B4 · · · . That’s why for the present problem, the inequality δi2 ≤ δi-12− 1 plays such an important role, because it causes the (squared) distances to decrease appreciably enough to give the final contradiction.
See Also
| 2025 USAMO (Problems • Resources) | ||
| Preceded by Problem 2 |
Followed by Problem 4 | |
| 1 • 2 • 3 • 4 • 5 • 6 | ||
| All USAMO Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
