Maths Olympiad Prep

Library / Iranian Mathematical Olympiad /71 of 270

Iranian Mathematical Olympiad

Geometry Difficulty 6.1 National Olympiad Prove it Iran

Consider lattice points of a 6×76 \times 7 grid. We start with two points AA, BB. We say two points XX, YY are connected if one can reflect several times with respect to points AA, BB and reach from XX to YY. What is the minimum number of connected components, over all choices of AA, BB?

Solution

We claim the answer is 88. Let us first find the points in a connected component. Let lPl_P be the line passing through a point PP and parallel to ABAB. Let lP′l'_P be the reflection of lPl_P with respect to ABAB. First note that the reflection of any point PP with respect to each of AA and BB lies on lP′l'_P. Hence, any point connected to PP lies on lPl_P or lP′l'_P.

We claim if PP is connected to a point QQ, then QQ can be attained by some number of transformations by ±2AB→\pm 2\overrightarrow{AB} and at most one reflection with respect to AA: the combination of any two reflections with respect to AA, BB is a transformation.

Transforming by ±2AB→\pm 2\overrightarrow{AB} does not change the parity of coordinates, so if we define an equivalence relation P≡QP \equiv Q if and only if P=Q+2nAB→P = Q + 2n\overrightarrow{AB}, n∈Zn \in \mathbb{Z}, points will form at least 1414 classes. Every connected component has points from at most two classes. Note that AA and BB are not connected and their components consist of exactly one class, so we have at least 88 components.

As an example, which is easy to verify, take the two points having only half a unit distance from the center of the table as AA, BB.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.