Maths Olympiad Prep

Library / /64 of 68

Combinatorics Difficulty 6.7 National Olympiad Prove it Estonia

Given is an m×mm \times m table with 2n2n distinct unit squares marked with a ring (2nm22n \le m^2). Juku wishes to connect these 2n2n rings into pairs using nn (possibly curved) lines in a way that meets the following conditions:
(1) Each line begins from some ring and ends in some other ring;
(2) Every two unit squares visited by the same line one after another have a common side;
(3) No two lines (including their endpoints) visit a common unit square;
(4) No line visits the same unit square more than once.
Prove that the sum of the numbers of unit squares visited by the lines is either always even or always odd, no matter of how Juku draws the lines.

Solutions — 2

Solution 1

Color the unit squares black and white in such a way that unit squares with a common side are of different color. Each line goes from a black square to a white square and vice versa; thus whenever the endpoints of a line are in squares of equal color, the line visits an odd number of squares, and otherwise, the line visits an even number of squares. Let kk squares out of the ones marked with ring be black. Among the lines drawn by Juku, let aa lines have both endpoints in black squares, bb lines have both endpoints in white squares, and cc lines have endpoints in squares of different color. Then 2a+c=k2a + c = k and a+b+c=na + b + c = n, implying a+b=nk+2aa + b = n - k + 2a. Hence the numbers a+ba+b and nkn-k have equal parity.
Let the numbers of squares visited by the lines sum up to ss. Then ss can be expressed as the sum of a+ba+b odd numbers and cc even numbers, whence ss and a+ba+b have equal parity. Consequently, ss and nkn-k have equal parity. Since nkn-k does not depend on the way Juku draws the lines, ss must be always even or always odd.

Solution 2

Every line can be considered as a sequence of unit movements, each having one of four possible directions (right, left, up, down). Thus the number of unit squares visited by a line is k+1k+1 where kk is the number of unit movements. Let a,b,c,da, b, c, d be the numbers of unit movements of the line in different directions (right, left, up and down, respectively); then the end of the line is located aba-b units to the right and cdc-d units upwards from the beginning of the line. Since aba-b and a+ba+b have equal parity, as do cdc-d and c+dc+d, the numbers k=(a+b)+(c+d)k = (a+b) + (c+d) and (ab)+(cd)(a-b) + (c-d) have equal parity.
Let the line start in column xAx_A and row yAy_A and end in column xBx_B and row yBy_B. Then xBxA=abx_B - x_A = a - b and yByA=cdy_B - y_A = c - d, whence the number of unit squares visited by the line has the same parity as the number xBxA+yByA+1x_B - x_A + y_B - y_A + 1. But the latter has the same parity as xB+xA+yB+yA+1x_B + x_A + y_B + y_A + 1. Summing up these numbers for all lines, we obtain that the total number of unit squares visited by the lines has the same parity as the number sx+sy+ns_x + s_y + n where sxs_x and sys_y are the sum of all column numbers and all row numbers, respectively, of the squares containing a ring. But this sum does not depend on the way how Juku connects the rings, which proves the desired claim.

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.