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 3 of 4: Analyze blocks
Previous stepNext step
In plain words

Analyze blocks

di=xi+h−xi≡0(modh)d_i=x_{i+h}-x_i\equiv0\pmod h
Detailed analysis

In any block of h h consecutive steps, if e e are +p+p steps, its displacement is ep−(h−e)q=(e−q)h ep-(h-e)q=(e-q)h . Hence each di d_i is a multiple of h h . Also di+1−di d_{i+1}-d_i is the difference of two steps and is one of 0,h,−h0,h,-h .