uniolympiads Ελληνικά

IMC 2026, Day 2, Problem 10

An infinite chessboard of size d>0d > 0 is obtained by colouring the interiors of the squares of an infinite square grid of side length dd 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 p1,…,pnp_1, \dots, p_n in the plane, there exist d∈(0,1)d \in (0, 1) and an infinite chessboard of size dd such that all the points pip_i lie in white squares?

Original from the official PDFAn infinite chessboard of size d > 0 is obtained by colouring the interiors of the squares of an infinite square grid of side length 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 p1,...,pn in the plane, there exist d ∈ (0,1) and an infinite chessboard of size d such that all the points pi lie in white squares?

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(proposed by 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 α\alpha and positive integer QQ, there are integers p,qp, q with 1≤q≤Q1 \le q \le Q and ∣qα−p∣<1/Q|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 KK:

Lemma. For real numbers α1,…,αm\alpha_1, \ldots, \alpha_m and a positive integer QQ, there exists an integer KK with 1≤K≤Qm1 \le K \le Q^m such that

∣Kαj−pj∣<1Q(j=1,…,m)|K\alpha_j - p_j| < \frac{1}{Q} \qquad (j = 1, \ldots, m)
for suitable integers p1,…,pmp_1, \ldots, p_m.

Proof. Consider the Qm+1Q^m + 1 points

({kα1},…,{kαm})∈[0,1)m,k=0,1,…,Qm.\big(\{k\alpha_1\}, \ldots, \{k\alpha_m\}\big) \in [0,1)^m, \qquad k = 0, 1, \ldots, Q^m.
Split [0,1)m[0,1)^m into QmQ^m half-open cubes of side length 1/Q1/Q. By the pigeonhole principle, two of the Qm+1Q^m + 1 points lie in the same cube; denote their indices by k<ℓk < \ell. For K=ℓ−kK = \ell - k, subtracting the two coordinatewise gives integers p1,…,pmp_1, \ldots, p_m satisfying the required inequalities and proves the lemma.

Let the points be (x1,y1),…,(xN,yN)(x_1, y_1), \ldots, (x_N, y_N) and apply the lemma with m=2Nm = 2N and Q=5Q = 5. We obtain an integer 1≤K≤52N1 \le K \le 5^{2N} and integers pi,qip_i, q_i such that

∣Kxi−pi∣<15,∣Kyi−qi∣<15(i=1,…,N).|Kx_i - p_i| < \tfrac{1}{5}, \qquad |Ky_i - q_i| < \tfrac{1}{5} \qquad (i = 1, \ldots, N).
Thus, after multiplication by the same integer KK, every coordinate is “close” to an integer.

Take an axes-aligned checkerboard of size

d=12K≤12<1,d = \frac{1}{2K} \le \frac{1}{2} < 1,
translated by d/2d/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 x/d+1/2∈Zx/d + 1/2 \in \mathbb{Z} and y/d+1/2∈Zy/d + 1/2 \in \mathbb{Z} and a point (x,y)(x, y) which does not belong to any grid line is white precisely when
⌊xd+12⌋+⌊yd+12⌋≡0(mod2).\left\lfloor \frac{x}{d} + \frac{1}{2} \right\rfloor + \left\lfloor \frac{y}{d} + \frac{1}{2} \right\rfloor \equiv 0 \pmod{2}.

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

xid+12=2Kxi+12=2pi+2δi+12⏟=:εi.\frac{x_i}{d} + \frac{1}{2} = 2Kx_i + \frac{1}{2} = 2p_i + \underbrace{2\delta_i + \frac{1}{2}}_{=:\varepsilon_i}.
Since ∣2δi∣<2/5|2\delta_i| < 2/5, we have
0<εi<1,0 < \varepsilon_i < 1,
so
⌊xid+12⌋=2pi,\left\lfloor \frac{x_i}{d} + \frac{1}{2} \right\rfloor = 2p_i,
which is even. The same argument gives
⌊yid+12⌋=2qi,\left\lfloor \frac{y_i}{d} + \frac{1}{2} \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 0<εi<10 < \varepsilon_i < 1 also show that no point lies on a grid line.

Transcribed from the official solutions, pages 7–8. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?