Advanced book on Mathematics Olympiad

682 Number Theory

(Korean Mathematical Olympiad, 1997)

718.The functionf:[ 1 ,n(n 2 +^1 )]→R,

f(x)=

− 1 +

√

1 + 8 x

2

,

is, in fact, the inverse of the increasing bijective functiong:[ 1 ,n]→[ 1 ,n(n 2 +^1 )],

g(x)=

x(x+ 1 )

2

.

We apply the identity proved in the introduction togin order to obtain

∑n

k= 1

⌊

k(k+ 1 )

2

⌋

+

n(n 2 + 1 )

∑

k= 1

⌊

− 1 +

√

1 + 8 k

2

⌋

−n=

n^2 (n+ 1 )

2

.

Note thatk(k 2 +^1 )is an integer for allk, and so

∑n

k= 1

⌊

k(k+ 1 )

2

⌋

=

∑n

k= 1

k(k+ 1 )

2

=

1

2

∑n

k= 1

(k^2 +k)=

n(n+ 1 )

4

+

n(n+ 1 )( 2 n+ 1 )

12

=

n(n+ 1 )(n+ 2 )

6

.

The identity follows.

719.The property is clearly satisfied ifa=bor ifab=0. Let us show that if neither of
these is true, thenaandbare integers.
First, note that for an integerx, 2 x= 2 xifx−x∈[ 0 ,^12 )and 2 x= 2 x+ 1
ifx−x∈[^12 , 1 ). Let us see which of the two holds foraandb.If 2 a= 2 a+1, then

a 2 b=b 2 a= 2 ab+b= 2 ab+b.

This implies 2 b= 2 b+ba, and sobais either 0 or 1, which contradicts our working
hypothesis. Therefore, 2 a= 2 aand also 2 b= 2 b. This means that the fractional
parts of bothaandbare less than^12. With this as the base case, we will prove by induction
that 2 ma= 2 maand 2 mb= 2 mbfor allm≥1.
The inductive step works as follows. Assume that the property is true formand let
us prove it form+1. If 2 m+^1 a= 2  2 ma, we are done. If 2 m+^1 a= 2  2 ma+1,
then

a 2 m+^1 b=b 2 m+^1 a= 2  2 mab+b= 2 m+^1 ab+b= 2 m+^1 ab+ 1.