Olympiad Maths Prep

Library / /7 of 14

Geometry Difficulty 8.0 National olympiad, round 2 Prove it Romania

a) Given any positive integer nn, prove that every nn points in the closed unit square [0,1]×[0,1][0, 1] \times [0, 1] can be joined by a path of length less than 2n+42\sqrt{n} + 4.

b) Prove that there exist nn points in the closed unit square [0,1]×[0,1][0, 1] \times [0, 1] that cannot be joined by a path of length less than n1\sqrt{n} - 1.

Solution

a) Let CC be an nn-point configuration in the closed unit square [0,1]×[0,1][0, 1] \times [0, 1], let m=nm = \lfloor\sqrt{n}\rfloor, and consider the snake going horizontally from 0×00 \times 0 to 1×01 \times 0, then vertically up from 1×01 \times 0 to 1×1/m1 \times 1/m, then horizontally back from 1×1/m1 \times 1/m to 0×1/m0 \times 1/m, vertically up from 0×1/m0 \times 1/m to 0×2/m0 \times 2/m, horizontally over to 1×2/m1 \times 2/m, and so on and so forth all the way up to 1×11 \times 1 or 0×10 \times 1, depending on whether mm is even or odd. The length of the snake is m+1+m1/m=m+2n+2m + 1 + m \cdot 1/m = m + 2 \le \sqrt{n} + 2. Of course, the snake does not necessarily pass through any point in CC, but it comes within 1/(2m)1/(2m) of CC. Thus, in tracing the snake, visit each point of CC by darting out, if necessary, to the nearest points in CC abreast within 1/(2m)1/(2m), and then dart back. This increases the length by at most n21/(2m)=n/m<n+2n \cdot 2 \cdot 1/(2m) = n/m < \sqrt{n} + 2, so the length of the visiting path is certainly less than 2n+42\sqrt{n} + 4.

b) Let again m=nm = \lfloor\sqrt{n}\rfloor, and consider an nn-point subconfiguration CC of the lattice {i/m×j/m:i,j=0,1,,m}\{i/m \times j/m: i, j = 0, 1, \dots, m\}. Since any two distinct points in the lattice are at least 1/m1/m distance apart, the length of a path through all of CC is at least (n1)1/m(n1)/nn1(n-1) \cdot 1/m \ge (n-1)/\sqrt{n} \ge \sqrt{n} - 1.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.