uniolympiads English

IMC 2026, Ημέρα 2, Θέμα 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?

Πρωτότυπο από το επίσημο 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?

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(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.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 7–8. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;