MathLabs

Problem 6

Let p,q,n p,q,n be positive integers with p+q<n p+q<n . Let x0,x1,…,xn x_0,x_1,\ldots,x_n be integers with x0=xn=0 x_0=x_n=0, and for each 1≤i≤n1\le i\le n let xi−xi−1=p x_i-x_{i-1}=p or −q-q . Show that there exist i<j i<j , with (i,j)≠(0,n)(i,j)\ne(0,n), such that xi=xj x_i=x_j .
Step 1 of 4: Count the two kinds of steps
Previous stepNext step
In plain words

Count the two kinds of steps

pr=qspr=qs
Detailed analysis

Let r r be the number of +p+p steps and s s the number of −q-q steps. Then r+s=n r+s=n and pr=qs pr=qs . Divide p,q p,q and all xi x_i by their gcd, so assume gcd⁡(p,q)=1\gcd(p,q)=1.