Maths Olympiad Prep

Library / /48 of 48

Combinatorics Difficulty 7.8 National olympiad, round 2 Prove it Greece

A square ABCDABCD is divided into n2n^2 equal small elementary squares, by drawing parallel lines to its sides. A spider starts from AA moving only to the right and up and tries to approach point CC. Every movement of the spider consists of kk steps right and mm steps up or of mm steps right and kk steps up (which can be done in any way she wants).
The spider makes ll “movements” and in the sequel moves only to the right or up without any restriction. If n=mln = m \cdot l, find the number of all possible routes the spider can follow to approach point CC, where n,m,k,ln, m, k, l are positive integers and k<mk < m.

Solution

We suppose that the square is placed into a Cartesian system of coordinates with origin A(0,0)A(0,0) and axes on the sides ABAB and ADAD, as in the figure 7. Let the spider start from AA and make its first movement (mm steps right and kk steps up or mm steps up and kk right). In the figure you can see the case m=4,k=3m = 4, k = 3.

Figure 1

After the first movement the spider can be on the point M(k,m)M(k,m) or on the point N(m,k)N(m,k). The number of ways the spider can approach the point M(k,m)M(k,m) or the point N(m,k)N(m,k) are equal to the combinations of k+mk+m elements taken kk at a time, that is
(k+mk)=(k+mm)=v. \binom{k+m}{k} = \binom{k+m}{m} = v.

After the second movement the spider can be at three different points: K(2k,2m)K(2k, 2m), L(k+m,k+m)L(k+m, k+m), and T(2m,2k)T(2m, 2k) with corresponding number of ways v2v^2, 2v22v^2, and v2v^2.
The point MM can be approached by vv different ways from AA. The point KK can be approached by vv different ways from MM. Hence the point KK can be approached by v2v^2 different ways from point AA.

Figure 2

In a similar fashion we can find that point TT can be approached by v2v^2 different ways from point AA. The point LL can be approached by v2v^2 different ways by following the route A,M,LA, M, L and by v2v^2 different ways by following the route A,N,LA, N, L. Hence point LL can be approached by 2v22v^2 different ways from point AA.

Similarly, we conclude that after the third movement the spider can be placed in four different points that can be approached by (33)v3\binom{3}{3} \cdot v^3, (32)v3\binom{3}{2} \cdot v^3, (31)v3\binom{3}{1} \cdot v^3, and (30)v3\binom{3}{0} \cdot v^3 different ways, respectively. Therefore, after the completion of the ll movements, the spider will be placed at l+1l+1 different points, lying on the line with equation: x+y=l(k+m)x + y = l(k+m).

Figure 3

If r=mkr = m-k, then these points are the following:
A0(lm,lk), A1(lmr,lk+r), A2(lm2r,lk+2r), , Al(lmlr,lk+lr)Al(lk,lm). A_0(lm, lk),\ A_1(lm-r, lk+r),\ A_2(lm-2r, lk+2r),\ \dots,\ A_l(lm-lr, lk+lr) \equiv A_{l}(lk, lm).
These points can be approached by (ll)vl\binom{l}{l} \cdot v^l, (ll1)vl\binom{l}{l-1} \cdot v^l, (ll2)vl\binom{l}{l-2} \cdot v^l, \dots, and (l0)vl\binom{l}{0} \cdot v^l different ways from the point AA. The point C(ml,ml)C(ml, ml) can be approached from the point:

A0(lm,lk),  with ((mllm)+(mllk)mllk)=(mllkmllk)=(lrlr)=1, way. A_0(lm, lk),\ \text{ with } \binom{(ml-lm)+(ml-lk)}{ml-lk} = \binom{ml-lk}{ml-lk} = \binom{lr}{lr} = 1, \text{ way.}
A1(lmr,lk+r),  with ((mllm+r)+(mllkr)r)=(mllkr), ways. A_1(lm-r, lk+r),\ \text{ with } \binom{(ml-lm+r)+(ml-lk-r)}{r} = \binom{ml-lk}{r}, \text{ ways.}
A2(lm2r,lk+2r),  with ((mllm+2r)+(mllk2r)2r)=(mllk2r), ways. A_2(lm-2r, lk+2r),\ \text{ with } \binom{(ml-lm+2r)+(ml-lk-2r)}{2r} = \binom{ml-lk}{2r}, \text{ ways.}
Al(lk,lm),  with ((mllk)+(mllm)mllk)=(lrlr)=1, way. A_l(lk, lm),\ \text{ with } \binom{(ml-lk)+(ml-lm)}{ml-lk} = \binom{lr}{lr} = 1, \text{ way.}
Hence the point C(ml,lm)C(ml, lm) can be approached from point AA by:
vl((ll)(lr0)+(ll1)(lrr)+(ll2)(lr2r)++(l0)(lrlr)) ways. v^l \left( \binom{l}{l} \cdot \binom{lr}{0} + \binom{l}{l-1} \cdot \binom{lr}{r} + \binom{l}{l-2} \cdot \binom{lr}{2r} + \cdots + \binom{l}{0} \cdot \binom{lr}{lr} \right) \text{ ways.}

(*) Moving from the point (i,j)(i, j) to the point (i+k,j+m)(i+k, j+m) of the grid with direction right and up, can be made by (k+mk)=(k+mm)\binom{k+m}{k} = \binom{k+m}{m} different ways. The procedure of finding the number of ways is the same as the procedure we have used at the first movement.

Note. In the case where mk=r=1m-k = r = 1, then the number of all possible ways becomes:
vl((ll)(l0)+(ll1)(l1)+(ll2)(l2)++(l0)(ll))=vl(2ll)=(k+mm)l(2ll). v^l \left( \binom{l}{l} \cdot \binom{l}{0} + \binom{l}{l-1} \cdot \binom{l}{1} + \binom{l}{l-2} \cdot \binom{l}{2} + \cdots + \binom{l}{0} \cdot \binom{l}{l} \right) = v^l \binom{2l}{l} = \binom{k+m}{m}^l \binom{2l}{l}.

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.