A path from $ (0,0)$ to $ (n,n)$ on the lattice is made up of unit moves upward or rightward. It is balanced if the sum of the x-coordinates of its $ 2n+1$ vertices equals the sum of their y-coordinates. Show that a balanced path divides the square with vertices $ (0,0)$, $ (n,0)$, $ (n,n)$, $ (0,n)$ into two parts with equal area.
Problem
Source: Central American Olympiad 2002, problem 6
Tags: geometry, calculus, integration, symmetry
azjps
30.12.2009 19:31
The level lines $ x + y = k$, $ k \in \{0,1,\ldots,2n\}$ combined pass through each of the lattice unit squares in the $ n\times n$ grid exactly once, and intersect our path at exactly one lattice point each. Verify that if a balanced path has a point $ (x_i,y_i)$ with $ y_i \ge x_i$, the level line $ x + y = (x_i + y_i)$ passes through $ \frac {y_i - x_i}2$ unit lattice squares between $ (x_i,y_i)$ and $ \left(\frac {x_i + y_i}{2},\frac {x_i + y_i}{2}\right)$, and similarly for $ x_i > y_i$, and thus the area of the bottom half can be found via the formula $ \frac {n^2}2 + \sum_{i = 0}^{2n} \frac {y_i - x_i}{2}$.
Edit: Indeed, TZF's explanation was essentially my motivation.
TZF
30.12.2009 19:53
I like azjps's solution a lot because it can be rephrased in a very intuitive way in terms of "integral" if you see the symmetry of the problem.
Perform the change of variables $ u = x + y$ and $ v = x - y$. At each step, $ \Delta (u,v) = (1, \pm 1)$, and the problem amounts to showing that the "integral" of the path in u-v space is $ 0$ iff. the sum of the $ v$ coordinates is $ 0$. The integral is the difference in area between the two sections. The desired equality can be easily be shown by doing a trapezoidal sum:
$ I = \sum_{i = 1}^{2n} \frac {v_i + v_{i - 1}}{2} = - \frac {v_0 + v_{2n}}{2} + \sum_{i = 0}^{2n} v_i = \sum_{i = 0}^{2n} v_i = \sum _{i = 0}^{2n} (x_i - y_i)$, where I used the fact that the endpoints are known to have $ v_0 = v_{2n} = 0$.
Below: Path shown in u-v space, with the x-y gridlines drawn in blue. This path is balanced because $ I = \sum v_i$ $ = 0 + 1 + 0 + 1 + 2 + 1 + 2 + 1 + 0 - 1 - 2 - 1 + 0 - 1 - 2 - 1 + 0 = 0$
prasanna1712
12.09.2011 22:35
I believe there is a simpler solution using Pick's Formula.
skyletter
08.05.2015 19:16
I am for prasanna1712.
GOLDENNAC
09.09.2024 22:35
Un poco feo para omcc.