330 Methods of Proof
With indices taken modulok+1, there exist two termsxjandxj+ 1 such thatxj>0,
xj+ 1 <0, andxj+xj+ 1 >0. Without loss of generality, we may assume that these terms
arexkandxk+ 1. Define a new sequence byyj =xj,j≤k−1,yk=xk+xk+ 1 .By
the inductive hypothesis,y 1 ,y 2 ,...,ykhas a unique good cyclic shift. Expandykinto
xk,xk+ 1 to obtain a good cyclic shift ofx 1 ,x 2 ,...,xk+ 1. This proves the existence. To
prove uniqueness, note that a good cyclic shift ofx 1 ,x 2 ,...,xk+ 1 can start only with one
ofx 1 ,x 2 ,...,xk(sincexk+ 1 <0). It induces a good cyclic shift ofy 1 ,y 2 ,...,ykthat
starts at the same term; hence two good cyclic shifts of the longer sequence would produce
two good cyclic shifts of the shorter. This is ruled out by the induction hypothesis, and
the uniqueness is proved.
(G. Raney)
20.We induct onm+n. The base casem+n=4 can be verified by examining the
equalities
1 + 1 = 1 +1 and 1+ 2 = 1 + 2.Now let us assume that the property is true form+n=kand prove it form+n=k+1.
Without loss of generality, we may assume thatx 1 =maxixiandy 1 =maxiyi,x 1 ≥y 1.
Ifm=2, then
y 1 +y 2 =x 1 +x 2 +···+xn≥x 1 +n− 1 ≥y 1 +n− 1.It follows thaty 1 =x 1 =norn−1,y 2 =n−1,x 2 =x 3 = ··· =xn=1. Consequently,
y 2 =x 2 +x 3 +···+xn, and we are done. Ifm>2, rewrite the original equality as
(x 1 −y 1 )+x 2 +···+xn=y 2 +···+ym.This is an equality of the same type, with the observation thatx 1 −y 1 could be zero, in
which casex 1 andy 1 are the numbers to be suppressed.
We could apply the inductive hypothesis ify 1 ≥n, in which casey 2 +···+ymwere
less thanmn−y 1 <(m− 1 )n. In this situation just suppress the terms provided by the
inductive hypothesis; then movey 1 back to the right-hand side.
Let us analyze the case in which this argument does not work, namely wheny 1 <n.
Theny 2 +y 3 +···+ym≤(m− 1 )y 1 <(m− 1 )n, and again the inductive hypothesis
can be applied. This completes the solution.
21.Letfbe the function. We will constructgandhsuch thatf=g+h, withgan odd
function andha function whose graph is symmetric with respect to the point( 1 , 0 ).
Letgbe any odd function on the interval[− 1 , 1 ]for whichg( 1 )=f( 1 ). Define
h(x)=f(x)−g(x),x∈[− 1 , 1 ]. Now we proceed inductively as follows. Forn≥1, let
h(x)=−h( 2 −x)andg(x)=f(x)−h(x)forx∈( 2 n− 1 , 2 n+ 1 ], and then extend these
functions such thatg(x)=−g(−x)andh(x)=f(x) −g(x)forx∈[− 2 n− 1 ,− 2 n+ 1 ).