Maths Olympiad Prep

Library / /492 of 520

Combinatorics Difficulty 7.5 National olympiad, round 2 Prove it

28. C5 (FRA) IMO6{ }^{\mathrm{IMO} 6} Let p,q,np, q, n be three positive integers with p+q<np+q<n. Let (x0,x1,,xn)\left(x_{0}, x_{1}, \ldots, x_{n}\right) be an (n+1)(n+1)-tuple of integers satisfying the following conditions: (i) x0=xn=0x_{0}=x_{n}=0. (ii) For each ii with 1in1 \leq i \leq n, either xixi1=px_{i}-x_{i-1}=p or xixi1=qx_{i}-x_{i-1}=-q. Show that there exists a pair (i,j)(i, j) of distinct indices with (i,j)(0,n)(i, j) \neq(0, n) such that xi=xjx_{i}=x_{j}.

Solution

28. Note that w.l.o.g., we can assume that pp and qq are coprime. Indeed, otherwise it suffices to consider the problem in which all xix_{i}'s and p,qp, q are divided by gcd(p,q)\operatorname{gcd}(p, q). Let k,lk, l be the number of indices ii with xi+1xi=px_{i+1}-x_{i}=p and the number of those ii with xi+1xi=qx_{i+1}-x_{i}=-q (0 \leq i < n). We have k+l=nk+l=n, kplq=0kp-lq=0, and thus k=qtk=qt, l=ptl=pt, and n=(p+q)tn=(p+q)t. Consider the sequence yi=xi+p+qxiy_{i}=x_{i+p+q}-x_{i}, i=0,,npqi=0, \ldots, n-p-q. We claim that at least one of the yiy_{i}'s equals zero. We begin by noting that each yiy_{i} is of the form upvqup-vq, where u+v=p+qu+v=p+q; therefore yi=(u+v)pv(p+q)=(pv)(p+q)y_{i}=(u+v)p-v(p+q)=(p-v)(p+q) is always divisible by p+qp+q. Moreover, yi+1yi=(xi+p+q+1xi+p+q)(xi+1xi)y_{i+1}-y_{i}=\left(x_{i+p+q+1}-x_{i+p+q}\right)-\left(x_{i+1}-x_{i}\right) is 0 or ±(p+q)\pm(p+q). We conclude that if no yiy_{i} is 0 then all yiy_{i}'s are of the same sign. But this is in contradiction with the relation y0+yp+q++ynpq=xnx0=0y_{0}+y_{p+q}+\cdots+y_{n-p-q}=x_{n}-x_{0}=0. Consequently some yiy_{i} is zero, as claimed.

Second solution. As before we assume (p,q)=1(p, q)=1. Let us define a sequence of points Ai(yi,zi)(i=0,1,,n)A_{i}\left(y_{i}, z_{i}\right)(i=0,1, \ldots, n) in N02\mathbb{N}_{0}^{2} inductively as follows. Set A0=(0,0)A_{0}=(0,0) and define (yi+1,zi+1)\left(y_{i+1}, z_{i+1}\right) as (yi,zi+1)\left(y_{i}, z_{i}+1\right) if xi+1=xi+px_{i+1}=x_{i}+p and (yi+1,zi)\left(y_{i}+1, z_{i}\right) otherwise. The points AiA_{i} form a trajectory LL in N02\mathbb{N}_{0}^{2} continuously moving upwards and rightwards by steps of length 1. Clearly, xi=pziqyix_{i}=pz_{i}-qy_{i} for all ii. Since xn=0x_{n}=0, it follows that (zn,yn)=(kq,kp)\left(z_{n}, y_{n}\right)=(kq, kp), kNk \in \mathbb{N}. Since yn+zn=n>p+qy_{n}+z_{n}=n>p+q, it follows that k>1k>1. We observe that xi=xjx_{i}=x_{j} if and only if AiAjA0AnA_{i}A_{j} \| A_{0}A_{n}. We shall show that such i,ji, j with i<ji<j and (i,j)(0,n)(i, j) \neq (0, n) must exist. If LL meets A0AnA_{0}A_{n} in an interior point, then our statement trivially holds. From now on we assume the opposite. Let PijP_{ij} be the rectangle with sides parallel to the coordinate axes and with vertices at (ip,jq)(ip, jq) and ((i+1)p,(j+1)q)((i+1)p, (j+1)q). Let LijL_{ij} be the part of the trajectory LL lying inside PijP_{ij}. We may assume w.l.o.g. that the endpoints of L00L_{00} lie on the vertical sides of P00P_{00}. Then there obviously exists d{1,,k1}d \in \{1, \ldots, k-1\} such that the endpoints of LddL_{dd} lie on the horizontal sides of PddP_{dd}. Consider the translate LddL_{dd}^{\prime} of LddL_{dd} for the vector d(p,q)-d(p, q). The endpoints of LddL_{dd}^{\prime} lie on the vertical sides of P00P_{00}. Hence L00L_{00} and LddL_{dd}^{\prime} have some point XA0X \neq A_{0} in common. The translate YY of point XX for the vector d(p,q)d(p, q) belongs to LL and satisfies XYA0AnXY \| A_{0}A_{n}.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.