680 Number Theory
x 0 =m^2 +n^2 ,x 0 +y 0 − 2 z 0 =p^2 +q^2 ,z 0 −x 0 =mp+nq.In that case,
y 0 =p^2 +q^2 + 2 z 0 −x 0 =p^2 +q^2 + 2 mp+ 2 nq+m^2 +n^2 =(m+p)^2 +(n+q)^2
and
z 0 =m(m+p)+n(n+q),contradicting our assumption.
We therefore can construct inductively an infinite sequence of triples of positive
numbers(xn,yn,zn),n≥0, none of which admits the representation from the statement,
and such thatxn+yn+zn>xn+ 1 +yn+ 1 +zn+ 1 for alln. This is of course impossible,
and the claim is proved.
(short list of the 20th International Mathematical Olympiad, 1978)
714.First solution: Chooseksuch that
x+k
n≤x<x+k+ 1
n.
Thenx+jnis equal toxforj = 0 , 1 ,...,n−k−1, and tox+1 forx =
n−k,...,n−1. It follows that the expression on the left is equal tonx+k. Also,
nx=nx+k, which shows that the two sides of the identity are indeed equal.
Second solution: Definef:R→N,
f(x)=x+⌊
x+1
n⌋
+···+
⌊
x+n− 1
n⌋
−nx.We have
f(
x+1
n)
=
⌊
x+1
n⌋
+···+
⌊
x+
n− 1
n⌋
+
⌊
x+
n
n⌋
−nx+ 1 =f(x).Therefore,fis periodic, with period^1 n. Also, sincef(x)=0 forx∈[ 0 ,^1 n), it follows
thatfis identically 0, and the identity is proved.
(Ch. Hermite)
715.Denote the sum in question bySn. Observe that
Sn−Sn− 1 =⌊x
n⌋
+
⌊
x+ 1
n⌋
+···+
⌊
x+n− 1
n⌋
=
⌊x
n⌋
+
⌊
x
n+
1
n⌋
+···+
⌊
x
n+
n− 1
n