Maths Olympiad Prep

Library / /58 of 61

Combinatorics Difficulty 7.0 National Olympiad Prove it Ibero-American Mathematical Olympiad

Problem:

AA and BB are opposite corners of an n×nn \times n board, divided into n2n^{2} squares by lines parallel to the sides. In each square the diagonal parallel to ABAB is drawn, so that the board is divided into 2n22 n^{2} small triangles. The board has (n+1)2(n+1)^{2} nodes and a large number of line segments, each of length 11 or 2\sqrt{2}. A piece moves from AA to BB along the line segments. It never moves along the same segment twice and its path includes exactly two sides of every small triangle on the board. For which nn is this possible?

Solution

Solution:

The diagram above shows that n=2n=2 is possible (the path is AHEFGHCDIHBAHEFGHCDIHB). Now suppose n>2n > 2.

Note that if XX is any vertex except AA or BB, then an even number of segments with endpoint XX must be in the path.

Let FF be the bottom left-hand vertex. Two sides of the triangle EFGEFG are in the path, so at least one of EFEF and FGFG is. But EFEF and EGEG are the only segments with endpoint FF, so an even number of them must be in the path, so both are in the path. Hence, again considering EFGEFG, EGEG is not in the path. Hence, considering EHGEHG, EHEH and HGHG are in the path.

EE has an even number of segments on the path, so CECE is not on the path. Hence (considering CEHCEH) CHCH is on the path. Similarly, GJGJ is not on the path and HJHJ is on the path. An even number of segments at HH are on the path, so DHDH and HIHI are either both on the path or neither is on the path. But (considering DHIDHI) at least one must be, so they both are. Hence DIDI is not, and CDCD is not.

Since n>2n>2, CC is not the top left vertex. Considering MCDMCD, MCMC and MDMD are both on the path. Considering DLIDLI, DLDL is on the path. There must be an even number of segments at DD, so DPDP is on the path. Hence MPMP is not. Now MM cannot be the top left vertex (with n=3n=3) because then it should have an odd number of segments, whereas it would have two (MCMC and MDMD). So there must be a vertex NN above MM. Considering NMPNMP, MNMN must be in the path. But now MM has an odd number of segments. Contradiction.

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

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