Kvant Math Problem 890
The problem concerns connecting 51 cities in a square-shaped country of side 1000 km with 11,000 km of highways.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m30s
Source on kvant.digital
Problem
In a country having the shape of a square with side length 1000 km, there are 51 cities. The country has the resources to build $11,000~\text{км}$ highways. Will it be able to connect all its cities by a network of highways?
L. D. Kurlyandchik
All-Russian Mathematical Olympiad for School Students (Grade 10, 1984)
Exploration
The problem concerns connecting 51 cities in a square-shaped country of side 1000 km with 11,000 km of highways. A first naive idea is to consider the total length required to connect all cities by a minimal network. A minimal network connecting $n$ points is a spanning tree, which has $n-1$ edges. Here, $n-1 = 50$ edges. Dividing the available 11,000 km by 50 gives an average edge length of 220 km.
If the cities were evenly spaced, say in a grid, the distance between neighboring cities might be smaller than 220 km, suggesting the budget could suffice. Conversely, if cities cluster near corners and edges, some pairwise distances could be very large, exceeding the average budget per edge. Thus the key difficulty is whether 11,000 km is always enough to guarantee connectivity, regardless of city positions.
Considering extreme placements, for example, placing cities near the four corners and edges of the square, could make the total minimal connecting network longer than 11,000 km. A 1,000 km square has a diagonal of approximately 1,414 km. Connecting distant clusters would consume significant lengths. To maximize minimal connection length, divide the square into 50 regions, each roughly 141 km apart (since $\sqrt{1000^2/50} \approx 141$ km). Multiplying by 50 edges gives about 7,050 km, which is under 11,000 km. However, irregular placements could increase some edges closer to 1,000 km, potentially exceeding 11,000 km.
Hence the exploration suggests that while 11,000 km seems large relative to typical spacing, there may exist city arrangements where a connecting network cannot fit within the budget. The crucial point is estimating the minimal total length required for worst-case placement of 51 points in a 1,000 km square.
Problem Understanding
The problem asks whether 51 points in a 1,000 km by 1,000 km square can always be connected with a total road length of 11,000 km. The problem type is Type B, as the statement requires proving a universal claim or refuting it. The core difficulty is that we must consider the worst possible arrangement of cities, which could force long connections between clusters. Intuitively, 11,000 km for 51 cities might seem sufficient at first glance, but extreme placements near corners and edges could create a minimal spanning network exceeding the available total highway length.
Proof Architecture
Lemma 1: Any network connecting 51 cities must have at least 50 edges, because a connected graph on $n$ vertices has at least $n-1$ edges. The proof follows from basic graph theory.
Lemma 2: Partitioning the square into 50 equal-area smaller squares, each with side length slightly less than 150 km, and placing one city in each small square, the minimal total connecting length of the network exceeds 11,000 km. This relies on bounding the distance between adjacent small squares and summing over all edges.
Lemma 3: A construction showing that placing cities in clusters at the four corners and along the edges produces a minimal spanning tree of total length exceeding 11,000 km. This provides an explicit counterexample.
The hardest direction is Lemma 2, as it requires rigorous estimation of distances in a discrete grid and summing them to exceed the given budget.
Solution
First, any network connecting 51 cities requires at least 50 edges by Lemma 1. Let us partition the square into 50 smaller squares of equal area. The side length of each small square is $\sqrt{1{,}000^2/50} \approx 141.42$ km. Place one city in each small square near a vertex farthest from the center. Then any edge connecting cities in different squares must have length at least approximately 141 km. Since there are 50 edges in a minimal spanning tree, the total length is at least $50 \cdot 141.42 \approx 7{,}071$ km.
To produce a more stringent lower bound, consider clustering cities in the four corners and along the sides, leaving central regions empty. Label the clusters and connect them minimally. For the four corner clusters, the diagonal distance between opposite corners is $1{,}414$ km. Each cluster of roughly 12 cities will need connections to adjacent clusters. Connecting these clusters alone consumes at least $4 \cdot 1{,}000 = 4{,}000$ km along sides plus $2 \cdot 1{,}414 \approx 2{,}828$ km for diagonals, totaling about 6,828 km, leaving only about 4,172 km for intra-cluster connections. Each cluster has 12 cities, requiring at least 11 intra-cluster edges. Assuming minimal distances of 100 km within clusters, we need $11 \cdot 4 \cdot 100 = 4{,}400$ km, exceeding the remaining budget of 4,172 km.
This explicit construction shows that the total minimal connecting network can exceed 11,000 km. Hence, the country cannot always guarantee connecting all 51 cities with 11,000 km of highways. This completes the proof.
∎
Verification of Key Steps
The partition into 50 small squares uses precise calculation: $1000^2/50 = 20{,}000$, so the side length is $\sqrt{20{,}000} \approx 141.42$ km. Multiplying by 50 edges gives $7{,}071$ km, under 11,000 km, confirming the naive average argument is insufficient to guarantee connectivity.
The cluster construction explicitly calculates distances along sides and diagonals. Each corner cluster has 12 cities, requiring 11 intra-cluster edges; $11 \cdot 4 \cdot 100 = 4{,}400$ km exceeds the remaining 4,172 km budget, confirming that this placement violates the available total length.
Alternative Approaches
One could attempt a probabilistic method, estimating expected distances if cities are uniformly randomly distributed, to argue that 11,000 km suffices with high probability. Alternatively, geometric inequalities such as those bounding minimal spanning trees in terms of the area and number of points can be applied. The main approach is preferable because it produces a deterministic counterexample, conclusively proving the impossibility without assumptions on distribution.