Kvant Math Problem 421

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m42s
Source on kvant.digital

Problem

For which natural numbers $m$ and $n$ ($m\lt n$) is it possible to color some cells of an infinite sheet of graph paper black so that every rectangle of size $m\times n$ contains exactly one black cell? Start with the simpler problem: consider the cases $m=2$ and $n=3$, 4, 5.

Fig. 1

S. Okhitin, 10th-grade student

Exploration

Let the cells of the infinite graph paper be indexed by integer coordinates $(x,y)$, where each cell corresponds to one pair of integers.

The condition concerns every axis-parallel rectangle consisting of exactly $m$ consecutive columns and $n$ consecutive rows. Such a rectangle is determined by its lower left corner $(a,b)$ and contains the cells

$$a\le x\le a+m-1,\qquad b\le y\le b+n-1.$$

The first question is whether the problem hides some arithmetic obstruction relating $m$ and $n$.

Testing the suggested cases gives an immediate idea. For $m=2$, $n=3$, color black all cells whose coordinates are multiples of $2$ and $3$ respectively. Then every interval of $2$ consecutive columns contains exactly one column whose index is a multiple of $2$, and every interval of $3$ consecutive rows contains exactly one row whose index is a multiple of $3$. Hence every $2\times3$ rectangle contains exactly one black cell.

The same construction works for $2\times4$ and $2\times5$. Nothing special happens in these examples.

This suggests coloring the cells

$$(km,\ell n),\qquad k,\ell\in\mathbb Z,$$

black and leaving all other cells white.

The only point requiring verification is that every block of $m$ consecutive integers contains exactly one multiple of $m$, and similarly for $n$. Once that is proved, the rectangle count becomes a product of two one dimensional counts.

The conjecture is that every pair of natural numbers $m<n$ works.

Problem Understanding

We must determine all pairs of natural numbers $m<n$ for which there exists a coloring of some cells of an infinite square grid so that every axis-parallel rectangle of size $m\times n$ contains exactly one black cell.

This is a Type A problem, a classification problem.

The proposed answer is that every pair of natural numbers $m<n$ satisfies the requirement.

The reason is that one may place black cells periodically at the intersections of every $m$th column and every $n$th row. A rectangle of width $m$ contains exactly one such special column, and a rectangle of height $n$ contains exactly one such special row, so the rectangle contains exactly one black cell.

Proof Architecture

The proof uses a single construction.

The first claim is that among any $m$ consecutive integers there is exactly one multiple of $m$; this follows from the division algorithm.

The second claim is the analogous statement for $n$.

The third claim is that if the black cells are exactly the cells $(km,\ell n)$, then an $m\times n$ rectangle contains exactly one black cell; this follows by combining the first two claims.

There is no difficult converse direction because the problem asks only for existence.

Solution

For every pair of natural numbers $m<n$, color black exactly those cells whose coordinates are of the form

$$(km,\ell n), \qquad k,\ell\in\mathbb Z.$$

All other cells are left white.

Consider an arbitrary rectangle of size $m\times n$. Its columns are indexed by

$$a,a+1,\dots,a+m-1$$

for some integer $a$, and its rows are indexed by

$$b,b+1,\dots,b+n-1$$

for some integer $b$.

We first show that among the integers

$$a,a+1,\dots,a+m-1$$

there is exactly one multiple of $m$.

Let $q$ be the unique integer satisfying

$$qm\le a<(q+1)m.$$

If $a=qm$, then $qm$ is one of the listed integers. If $a>qm$, then $(q+1)m$ lies between $a$ and $a+m-1$. In either case, at least one multiple of $m$ occurs in the list.

Two distinct multiples of $m$ differ by at least $m$, while the interval from $a$ to $a+m-1$ has length $m-1$. Hence the list cannot contain two different multiples of $m$. Thus it contains exactly one multiple of $m$.

The same argument shows that among

$$b,b+1,\dots,b+n-1$$

there is exactly one multiple of $n$.

Consequently the rectangle contains exactly one column whose index is a multiple of $m$ and exactly one row whose index is a multiple of $n$. Their intersection is a black cell. Any black cell must lie on such a column and such a row, so no other black cell can belong to the rectangle.

Hence every rectangle of size $m\times n$ contains exactly one black cell.

The required coloring exists for every pair of natural numbers $m<n$.

$$\boxed{\text{All pairs }(m,n)\text{ with }m<n}$$

Verification of Key Steps

The crucial arithmetic fact is that every block of $m$ consecutive integers contains exactly one multiple of $m$.

Take a concrete example, $m=5$. The block

$$7,8,9,10,11$$

contains the multiple $10$, while

$$10,11,12,13,14$$

contains the multiple $10$. A second multiple would have to differ by at least $5$, which is impossible inside a block of length $4$.

The second delicate point is the passage from one dimensional counting to the rectangle count. A black cell must satisfy simultaneously

$$x\equiv0\pmod m, \qquad y\equiv0\pmod n.$$

Inside the rectangle there is exactly one admissible column and exactly one admissible row. Their intersection produces one black cell, and every black cell must be that intersection. This excludes both the possibility of zero black cells and the possibility of more than one.

For the sample values suggested in the statement, namely $(2,3)$, $(2,4)$, and $(2,5)$, the construction gives black cells at

$$(2k,3\ell),\qquad (2k,4\ell),\qquad (2k,5\ell),$$

respectively, and the same argument shows that every corresponding rectangle contains exactly one black cell.

Alternative Approaches

A different construction colors black all cells satisfying a congruence

$$x+cy\equiv0\pmod{mn},$$

with a suitable choice of $c$. One can then prove that every $m\times n$ rectangle contains exactly one solution of the congruence. This approach uses modular arithmetic and counting residues.

The lattice construction used above is preferable because it reduces the problem to the elementary fact that every interval of length $m$ contains exactly one multiple of $m$. No additional number theoretic machinery is required.