International Mathematics Competition
for University Students
2026

IMC2026: Day 2, Problem 10

Problem 10. An infinite chessboard of size \(\displaystyle d>0\) is obtained by colouring the interiors of the squares of an infinite square grid of side length \(\displaystyle d\) alternately white and black following the usual chessboard pattern. The points belonging to the grid lines have neither colour and the grid may be translated and rotated arbitrarily in the plane.

Is it true that for any finite set of points \(\displaystyle p_1,\ldots,p_n\) in the plane, there exist \(\displaystyle d\in(0,1)\) and an infinite chessboard of size \(\displaystyle d\) such that all the points \(\displaystyle p_i\) lie in white squares?

David Hruška, Czech Academy of Sciences, Prague

Solution. We prove that the statement is true.

The standard one-dimensional Dirichlet approximation theorem says that, for every real \(\displaystyle \alpha\) and positive integer \(\displaystyle Q\), there are integers \(\displaystyle p,q\) with \(\displaystyle 1\leq q\leq Q\) and \(\displaystyle |q\alpha-p|<1/Q\). We need its simultaneous form, sometimes called multidimensional Dirichlet approximation. Its role here is to approximate all coordinates at once using the same multiplier \(\displaystyle K\):

Lemma. For real numbers \(\displaystyle \alpha_1,\dots,\alpha_m\) and a positive integer \(\displaystyle Q\), there exists an integer \(\displaystyle K\) with \(\displaystyle 1\leq K\leq Q^m\) such that

\(\displaystyle \lvert K\alpha_j-p_j\rvert<\frac1Q \qquad (j=1,\dots,m) \)

for suitable integers \(\displaystyle p_1,\dots,p_m\).

Proof. Consider the \(\displaystyle Q^m+1\) points

\(\displaystyle \bigl(\{k\alpha_1\},\dots,\{k\alpha_m\}\bigr)\in[0,1)^m, \qquad k=0,1,\dots,Q^m. \)

Split \(\displaystyle [0,1)^m\) into \(\displaystyle Q^m\) half-open cubes of side length \(\displaystyle 1/Q\). By the pigeonhole principle, two of the \(\displaystyle Q^m+1\) points lie in the same cube; denote their indices by \(\displaystyle k<\ell\). For \(\displaystyle K=\ell-k\), subtracting the two coordinatewise gives integers \(\displaystyle p_1,\dots,p_m\) satisfying the required inequalities and proves the lemma.

Let the points be \(\displaystyle (x_1,y_1),\dots,(x_N,y_N)\) and apply the lemma with \(\displaystyle m=2N\) and \(\displaystyle Q=5\). We obtain an integer \(\displaystyle 1\leq K\leq 5^{2N}\) and integers \(\displaystyle p_i,q_i\) such that

\(\displaystyle |Kx_i-p_i|<\tfrac15, \qquad |Ky_i-q_i|<\tfrac15 \qquad (i=1,\dots,N). \)

Thus, after multiplication by the same integer \(\displaystyle K\), every coordinate is ``close'' to an integer.

Take an axes-aligned checkerboard of size

\(\displaystyle d=\frac1{2K}\leq\frac12<1, \)

translated by \(\displaystyle d/2\) in each coordinate, i.e. with the origin being the center of one square and let us colour this square white. The grid lines then satisfy \(\displaystyle x/d+1/2\in\mathbb Z\) and \(\displaystyle y/d+1/2\in\mathbb Z\) and a point \(\displaystyle (x,y)\) which does not belong to any grid line is white precisely when

\(\displaystyle \left\lfloor\frac{x}{d}+\frac12\right\rfloor + \left\lfloor\frac{y}{d}+\frac12\right\rfloor \equiv 0\pmod 2. \)

Write \(\displaystyle Kx_i=p_i+\delta_i\) with \(\displaystyle |\delta_i|<1/5\). The choice \(\displaystyle d=1/(2K)\) makes the main term \(\displaystyle 2p_i\) even, while the translation by \(\displaystyle d/2\) keeps the small error inside the same square. Indeed,

\(\displaystyle \frac{x_i}{d}+\frac12 =2Kx_i+\frac12 =2p_i+\underbrace{2\delta_i+\frac12}_{=:\varepsilon_i}. \)

Since \(\displaystyle |2\delta_i|<2/5\), we have

\(\displaystyle 0<\varepsilon_i<1, \)

so

\(\displaystyle \left\lfloor\frac{x_i}{d}+\frac12\right\rfloor=2p_i, \)

which is even. The same argument gives

\(\displaystyle \left\lfloor\frac{y_i}{d}+\frac12\right\rfloor=2q_i, \)

also even. Hence the sum of the two square indices is even, so every point lies in a white square. The strict inequalities \(\displaystyle 0<\varepsilon_i<1\) also show that no point lies on a grid line.