Advanced book on Mathematics Olympiad

382 Algebra

c=9,d=16, in which case the sum of the square roots is equal to 10. The inequality
is proved.
(V. Cârtoaje)

136.There exist finitely manyn-tuples of positive integers with the sum equal tom,so
the expression from the statement has indeed a maximal value.
We show that the maximum is not attained if two of thexi’s differ by 2 or more.
Without loss of generality, we may assume thatx 1 ≤x 2 −2. Increasingx 1 by 1 and
decreasingx 2 by 1 yields
∑

2 <i<j

xixj+(x 1 + 1 )

∑

2 <i

xi+(x 2 − 1 )

∑

2 <i

xi+(x 1 + 1 )(x 2 − 1 )

=

∑

2 <i<j

xixj+x 1

∑

2 <i

xi+x 2

∑

2 <i

xi+x 1 x 2 −x 1 +x 2 + 1.

The sum increased byx 2 −x 1 − 1 ≥1, and hence the original sum was not maximal.
This shows that the expression attains its maximum for a configuration in which the
xi’s differ from each other by at most 1. Ifmn =rn+s, with 0≤s<n, then for this
to happenn−sof thexi’s must be equal tor+1 and the remaining must be equal tor.
This gives that the maximal value of the expression must be equal to

1

2

(n−s)(n−s− 1 )r^2 +s(n−s)r(r+ 1 )+

1

2

s(s− 1 )(r+ 1 )^2.

(Mathematical Olympiad Summer Program 2002, communicated by Z. Sunik)

137.There are finitely many such products, so a smallest product does exist. Examining
the 2×2, 3×3, and 4×4 arrays, we conjecture that the smallest product is attained on the
main diagonal and is 1· 3 ··· 5 ···( 2 n− 1 ). To prove this, we show that if the permutation
σof{ 1 , 2 ,...,n}has an inversion, thena 1 σ( 1 )a 2 σ( 2 )···anσ (n)is not minimal.

i+j−

i+m+j− i+m+j+k−

i+j+k−

1

11

1

Figure 62

So assume that the inversion gives rise to the factorsi+(j+k)−1 and(i+m)+j− 1
in the product. Let us replace them withi+j−1 and(i+m)+(j+k)−1, as shown
in Figure 62. The product of the first pair is

i^2 +ik+i(j− 1 )+mi+mk+m(j− 1 )+(j− 1 )i+(j− 1 )k+(j− 1 )^2 ,