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 4 of 4: Force a zero displacement
Previous stepNext step
In plain words

Force a zero displacement

xi=xi+hx_i=x_{i+h}
Detailed analysis

If no di d_i were zero, consecutive multiples of h h could not change from positive to negative because their difference has magnitude at most h h ; all di d_i would have one sign. But d0+dh+⋯+d(k−1)h=xkh−x0=xn−x0=0 d_0+d_h+\cdots+d_{(k-1)h}=x_{kh}-x_0=x_n-x_0=0, impossible. Thus di=0 d_i=0 for some 0≤i≤n−h0\le i\le n-h , and i+h<n i+h<n or at least i+h≠i i+h\ne i ; this is the required pair, not (0,n)(0,n) because h<n h<n .