Kvant Math Problem 626

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m47s
Source on kvant.digital

Problem

Each side of a convex quadrilateral is divided into 8 equal parts. Corresponding division points on opposite sides are connected to each other, and the resulting cells are colored in a checkerboard pattern. Prove that the sum of the areas of the black cells is equal to the sum of the areas of the white cells.

V. V. Proizvolov

Exploration

The quadrilateral is cut by two families of lines. On one pair of opposite sides, corresponding division points are joined, producing one family of seven segments. On the other pair of opposite sides, corresponding division points are joined, producing another family of seven segments. The two families form an $8\times 8$ grid of curvilinear quadrilaterals, which are the cells to be colored alternately.

The statement resembles the well known fact that in a parallelogram subdivided into an $m\times n$ rectangular grid, the checkerboard sums are equal. Since the original quadrilateral is arbitrary, the crucial question is whether the subdivision can be transformed into an ordinary square grid by a map preserving area in a sufficiently simple way.

Let the quadrilateral be $ABCD$. A point of the quadrilateral can be represented by two parameters. If $P(t)$ is the point dividing $AB$ and $DC$ in the same ratio $t$, then the segment joining these two points is one member of the first family. Likewise, if $Q(s)$ is the point dividing $AD$ and $BC$ in the same ratio $s$, then the segment joining these two points is one member of the second family.

This suggests using bilinear coordinates. Write

$$X(u,v)=(1-u)(1-v)A+u(1-v)B+uv,C+(1-u)v,D.$$

For fixed $u$, this traces a segment joining corresponding points of $AD$ and $BC$. For fixed $v$, it traces a segment joining corresponding points of $AB$ and $DC$. Thus the given subdivision is exactly the image of the ordinary $8\times 8$ square grid in the unit square.

The next step is to understand the area element. Computing derivatives,

$$X_u=(1-v)(B-A)+v(C-D),$$

$$X_v=(1-u)(D-A)+u(C-B).$$

Their determinant is affine in each variable separately, hence of the form

$$J(u,v)=\alpha+\beta u+\gamma v.$$

The mixed term $uv$ cancels. This is the key point. If the Jacobian were an arbitrary function, the checkerboard cancellation would not be immediate.

Each cell of the subdivision corresponds to a square

$$\left[\frac{i}{8},\frac{i+1}{8}\right]\times \left[\frac{j}{8},\frac{j+1}{8}\right].$$

Its area equals the integral of $J$ over that square. Since $J$ is linear, the integral over a small square equals its area times the value of $J$ at the square's center. Thus the checkerboard difference is a weighted sum of values of a linear function at the $64$ grid centers.

The centers are

$$u_i=\frac{2i+1}{16},\qquad v_j=\frac{2j+1}{16}.$$

The checkerboard difference is

$$\sum_{i,j}(-1)^{i+j}J(u_i,v_j).$$

Because $J=\alpha+\beta u+\gamma v$, this separates into products of sums such as

$$\sum_i(-1)^i,\qquad \sum_i(-1)^i u_i,$$

all of which vanish for $i=0,\dots,7$. Hence the difference is zero.

The delicate point is proving rigorously that the Jacobian has no $uv$ term.

Problem Understanding

We are given a convex quadrilateral whose sides are divided into eight equal parts. Corresponding division points on each pair of opposite sides are connected. The resulting two families of segments partition the quadrilateral into $64$ cells, which are colored like a chessboard. We must prove that the total area of the black cells equals the total area of the white cells.

This is a Type B problem.

The core difficulty is that the quadrilateral is arbitrary, so the cells are not congruent and generally have different areas. The proof must exploit a structural property of the subdivision rather than any symmetry of the figure.

Proof Architecture

Lemma 1. The subdivision is the image of the ordinary $8\times 8$ grid of the unit square under the bilinear map

$$X(u,v)=(1-u)(1-v)A+u(1-v)B+uv,C+(1-u)v,D.$$

For fixed $u$ or fixed $v$, the image is exactly one of the connecting segments between corresponding division points.

Lemma 2. The Jacobian determinant of this bilinear map has the form

$$J(u,v)=\alpha+\beta u+\gamma v.$$

Direct differentiation shows that the coefficient of $uv$ cancels.

Lemma 3. The area of every cell equals the integral of $J$ over the corresponding small square of the unit grid.

This is the change of variables formula.

Lemma 4. For a linear function $J$, the integral over a square equals the square's area multiplied by the value of $J$ at the square's center.

This follows from averaging a linear function over a rectangle.

Lemma 5. The checkerboard weighted sum of the values of any linear function at the $64$ grid centers is zero.

The alternating sums of $1$, $u$, and $v$ all vanish.

The most vulnerable step is Lemma 2, where the cancellation of the $uv$ term must be verified explicitly.

Solution

Let the vertices of the convex quadrilateral be $A,B,C,D$ in cyclic order.

Consider the map

$$X(u,v)=(1-u)(1-v)A+u(1-v)B+uv,C+(1-u)v,D, \qquad 0\le u,v\le 1.$$

For fixed $u=u_0$ we obtain

$$X(u_0,v) =(1-v)\bigl((1-u_0)A+u_0B\bigr) +v\bigl((1-u_0)D+u_0C\bigr).$$

Hence $X(u_0,v)$ runs along the segment joining the point of $AB$ dividing it in the ratio $u_0:(1-u_0)$ to the corresponding point of $DC$ dividing it in the same ratio.

Similarly, for fixed $v=v_0$,

$$X(u,v_0) =(1-u)\bigl((1-v_0)A+v_0D\bigr) +u\bigl((1-v_0)B+v_0C\bigr),$$

so $X(u,v_0)$ runs along the segment joining corresponding points of $AD$ and $BC$.

Therefore the lines

$$u=\frac{k}{8},\qquad v=\frac{\ell}{8}, \qquad k,\ell=0,1,\dots,8,$$

are mapped precisely to the lines used in the construction. The $64$ cells correspond to the $64$ squares

$$R_{ij} = \left[\frac{i}{8},\frac{i+1}{8}\right] \times \left[\frac{j}{8},\frac{j+1}{8}\right], \qquad 0\le i,j\le 7.$$

Let

$$J(u,v)=\det(X_u,X_v).$$

Differentiating,

$$X_u=(1-v)(B-A)+v(C-D),$$

$$X_v=(1-u)(D-A)+u(C-B).$$

Introduce

$$P=B-A,\qquad Q=C-D,$$

$$R=D-A,\qquad S=C-B.$$

Then

$$X_u=P+v(Q-P), \qquad X_v=R+u(S-R).$$

Hence

$$\begin{aligned} J(u,v) &=\det(P,R) +u,\det(P,S-R) +v,\det(Q-P,R) \ &\quad +uv,\det(Q-P,S-R). \end{aligned}$$

Now

$$Q-P=(C-D)-(B-A)=A-B+C-D,$$

and

$$S-R=(C-B)-(D-A)=A-B+C-D.$$

Thus $Q-P=S-R$, and therefore

$$\det(Q-P,S-R)=0.$$

Consequently

$$J(u,v)=\alpha+\beta u+\gamma v$$

for suitable constants $\alpha,\beta,\gamma$.

Let $c_{ij}$ be the center of $R_{ij}$:

$$c_{ij} = \left( \frac{2i+1}{16}, \frac{2j+1}{16} \right).$$

Since $J$ is linear in $u$ and $v$, its average value over a square equals its value at the center of that square. Since every $R_{ij}$ has area $1/64$,

$$\iint_{R_{ij}} J(u,v),du,dv = \frac1{64},J(c_{ij}).$$

By the change of variables formula, this integral is exactly the area of the corresponding cell.

Let

$$\varepsilon_{ij}=(-1)^{i+j},$$

where adjacent cells have opposite signs. The difference between the total black area and the total white area is

$$\begin{aligned} \Delta &= \sum_{i,j}\varepsilon_{ij} \iint_{R_{ij}}J(u,v),du,dv \ &= \frac1{64} \sum_{i,j}\varepsilon_{ij}J(c_{ij}). \end{aligned}$$

Write

$$J(u,v)=\alpha+\beta u+\gamma v.$$

Then

$$\begin{aligned} \sum_{i,j}\varepsilon_{ij}J(c_{ij}) &= \alpha\sum_{i,j}\varepsilon_{ij} +\beta\sum_{i,j}\varepsilon_{ij}u_i +\gamma\sum_{i,j}\varepsilon_{ij}v_j, \end{aligned}$$

where

$$u_i=\frac{2i+1}{16}, \qquad v_j=\frac{2j+1}{16}.$$

Since

$$\sum_{i=0}^{7}(-1)^i=0,$$

we obtain

$$\sum_{i,j}\varepsilon_{ij} = \left(\sum_i(-1)^i\right) \left(\sum_j(-1)^j\right) =0.$$

Also,

$$\sum_{i,j}\varepsilon_{ij}u_i = \left(\sum_i(-1)^iu_i\right) \left(\sum_j(-1)^j\right) =0,$$

and similarly

$$\sum_{i,j}\varepsilon_{ij}v_j = \left(\sum_i(-1)^i\right) \left(\sum_j(-1)^jv_j\right) =0.$$

Hence

$$\sum_{i,j}\varepsilon_{ij}J(c_{ij})=0,$$

so $\Delta=0$.

Thus the total area of the black cells equals the total area of the white cells.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the computation of the Jacobian. Writing

$$X_u=P+v(Q-P),\qquad X_v=R+u(S-R),$$

produces a possible $uv$ term

$$uv,\det(Q-P,S-R).$$

A careless computation might leave this term present. The identity

$$Q-P=(C-D)-(B-A)=A-B+C-D$$

and

$$S-R=(C-B)-(D-A)=A-B+C-D$$

shows that the two vectors are equal, so their determinant is exactly zero.

The second delicate step is replacing the integral over a cell by the value at its center. This is valid because $J$ is linear. For a linear function

$$J(u,v)=\alpha+\beta u+\gamma v,$$

the average value over any rectangle equals the value at the rectangle's midpoint. The statement would fail for a quadratic function, which is why eliminating the $uv$ term is essential.

The third delicate step is the checkerboard cancellation. The factorization

$$\sum_{i,j}(-1)^{i+j}u_i = \left(\sum_i(-1)^iu_i\right) \left(\sum_j(-1)^j\right)$$

uses that $u_i$ depends only on $i$. Since the second factor is zero, the whole sum vanishes regardless of the first factor.

Alternative Approaches

The same bilinear parametrization can be used in a more conceptual way. The area form is represented by a function $J(u,v)$ that is affine in each variable separately. The alternating checkerboard sum acts as a discrete second difference operator. Such an operator annihilates every function of the form $\alpha+\beta u+\gamma v$. Since $J$ has exactly this form, the total signed area is zero.

Another approach uses finite differences directly. The area of a cell can be expressed through a mixed difference of a suitable area function of the parameters $u$ and $v$. For a bilinear parametrization that area function is a polynomial of degree at most two, and the alternating $8\times8$ checkerboard sum telescopes completely. The Jacobian method is preferable because it isolates the geometric content in a single computation and makes the cancellation transparent.