Maths Olympiad Prep

Library / /5 of 13

, 2013

Combinatorics Difficulty 7.5 National olympiad, round 2 Prove it Saudi Arabia

The set GG is defined by the points (x,y)(x, y) with integer coordinates, 1x51 \leq x \leq 5 and 1y51 \leq y \leq 5. Determine the number of five-point sequences (P1,P2,P3,P4,P5)\left(P_{1}, P_{2}, P_{3}, P_{4}, P_{5}\right) such that for 1i5,Pi=(xi,i)1 \leq i \leq 5, P_{i}=\left(x_{i}, i\right) is in GG and x1x2=x2x3=x3x4=x4x5=1\left|x_{1}-x_{2}\right|= \left|x_{2}-x_{3}\right|=\left|x_{3}-x_{4}\right|=\left|x_{4}-x_{5}\right|=1.

Solution

Let us count the number of five-point sequences according to the position of point P3P_{3}.

Figure 1

Because the horizontal line of equation y=3y=3 is a symmetry axis for this figure, the number of sequences with x3=ix_{3}=i is equal to the number of sequences with x3=6ix_{3}=6-i, for i=1,2i=1,2.

Figure 2

Similarly, the vertical line of equation x=3x=3 is a symmetry axis for this figure, so that the number NiN_{i} of three-point sequences (P1,P2,P3)\left(P_{1}, P_{2}, P_{3}\right) ending at P3P_{3} with x3=ix_{3}=i is equal to the number of three-point sequences (P3,P4,P5)\left(P_{3}, P_{4}, P_{5}\right) starting at P3P_{3}, with x3=ix_{3}=i, for i=1,2,3i=1,2,3. Therefore, the number of five-point sequences (P1,P2,P3,P4,P5)\left(P_{1}, P_{2}, P_{3}, P_{4}, P_{5}\right) with x3=ix_{3}=i is Ni2N_{i}^{2}. Hence, the total number of five-point sequences (P1,P2,P3,P4,P5)\left(P_{1}, P_{2}, P_{3}, P_{4}, P_{5}\right) is
2(N12+N22)+N32. 2\left(N_{1}^{2}+N_{2}^{2}\right)+N_{3}^{2} .
It is easy to see that N1=2N_{1}=2, since the only possibilites for x4,x5x_{4}, x_{5} are x4=2x_{4}=2 and x5=1x_{5}=1 or 33.

Figure 3

It is also easy to see that N2=3N_{2}=3, since x4=1x_{4}=1 or 33 and x5=2x_{5}=2 in the first case and 22 or 44 in the second case.

Figure 4

Finally, N3=4N_{3}=4, since x4=2x_{4}=2 or 44, and x5=1x_{5}=1 or 33 in the first case, and 33 or 55 in the second case.

Figure 5

Hence, the number of sequences is 2(22+32)+42=422\left(2^{2}+3^{2}\right)+4^{2}=42.

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 and solution reproduced as published; topic and difficulty added by this site.