Maths Olympiad Prep

Library / /256 of 299

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it Iran

Consider an n×nn \times n array of points. For a subset AA of the edges of this array (i.e. the lattice edges), we denote by V(A)V(A) the set of vertices of AA and by J(A)J(A) the set of connected components of AA. For each natural number ll, prove that
l2minAl(V(A)J(A))l2+l2+1. \frac{l}{2} \le \min_{|A| \ge l} (|V(A)| - |J(A)|) \le \frac{l}{2} + \sqrt{\frac{l}{2}} + 1.
(For a set XX, by X|X| we mean the number of elements of XX).

Solution

First we prove the lower bound. Throughout the solution, we denote by viv_i and lil_i the number of vertices and edges of the ii-th connected component, respectively. Each lattice point has 4 adjacent lattice points, and so the degree of each vertex in a connected component is at most 4. Clearly, the degree of the rightmost vertex in each row of a connected component is at most 3 and similar statement holds for the leftmost vertex in each row, and the topmost and the bottommost vertex in each column of a connected component. Thus, we have at least 4 vertices of degree 3 and so
2li=Sum of Degrees in the i-th Connected Component4vi4 2l_i = \text{Sum of Degrees in the } i\text{-th Connected Component} \le 4v_i - 4
Summing these inequalities for all connected components yields
2A4vi1l2V(A)J(A) 2|A| \le 4 \sum v_i - 1 \Rightarrow \frac{l}{2} \le |V(A)| - |J(A)|
And this implies the left inequality.

Now we go to the right inequality. We know that there are (n+1)2(n+1)^2 vertices and 2n(n+1)2n(n+1) edges in an (n+1)×(n+1)(n+1) \times (n+1) array of points. Let nn be the greatest positive integer such that 2n(n+1)l2n(n+1) \le l. So we can write l=2n(n+1)+kl = 2n(n+1) + k, where 0k<4(n+1)0 \le k < 4(n+1) is an integer. We will introduce a graph with ll edges, satisfying the right inequality. Firstly, consider an n×nn \times n square, which has 2n(n+1)2n(n+1) edges. If k>0k > 0, we start to add some edges to the square. Suppose that the point (0,0)(0,0) is the leftmost point of the top side of the square. We add the edge connecting (1,0)(-1,0) to (0,0)(0,0). Then edges connecting (1,1)(-1,-1) to (1,0)(-1,0) and (0,1)(0,-1). In the same manner, if we need more edges we choose the next edge on the square perimeter (counterclockwise) and add two edges to the graph using that edge. Let tt be the number of sides in the square perimeter, which have been used in our process. Thus, we have added t+1+kt2t + 1 + \lfloor \frac{k-t}{2} \rfloor new vertices for constructing kk edges. We know tk2(n+1)t \le \lfloor \frac{k}{2(n+1)} \rfloor. Therefore, we have (n+1)2+t+kt2+1(n+1)^2 + t + \frac{k-t}{2} + 1 vertices in one connected component. So we must prove
(n+1)2+k+t2<l2+l2+1=n(n+1)+k2+n(n+1)+k2+1 (n+1)^2 + \frac{k+t}{2} < \frac{l}{2} + \sqrt{\frac{l}{2}} + 1 = n(n+1) + \frac{k}{2} + \sqrt{n(n+1) + \frac{k}{2}} + 1
Which is in turn equivalent to
n2+tn+t24<n2+n+k2 n^2 + tn + \frac{t^2}{4} < n^2 + n + \frac{k}{2}
If t=1t = 1, the inequality is obvious. And if t=2t = 2, the inequality will be n+1k2n + 1 \le \frac{k}{2} which is again true because 2=t=k2(n+1)2 = t = \lceil \frac{k}{2(n+1)} \rceil and so k2(n+1)k \ge 2(n + 1). So the assertion is proved.

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.