Solutions for advanced problems "A" in November, 2001 
In this page only the sketch of the solutions are published; in some cases only the final results. To achieve the maximum score in the competition more detailed solutions needed.
A. 275. The numbers 1^{2}, 2^{2}, 3^{2}, ..., (n^{2})^{2} are written in increasing order into an nxn array:

A number is selected from each row, such that no two numbers belong to the same column. What are the possible values of the sum of the selected numbers?
From the idea of T. Terpai
Solution. Suppose we have chosen the a_{i}th element out of the ith row, where i=1,2,...,n. The numbers a_{1},...,a_{n} represent a permutation of 1,2,...,n, and the sum of the selected numbers is
\(\displaystyle \sum_{i=1}^n\big((i1)n+a_i\big)^2=n^2\sum_{i=1}^n(i1)^2+\sum_{i=1}^na_i^2+2n\sum_{i=1}^n(i1)a_i.\)
The values of the first two sums do not depend on the choice of the numbers a_{i}:
\(\displaystyle n^2\sum_{i=1}^n(i1)^2=n^2\cdot{(n1)n(2n1)\over6}={n^3(n1)(2n1)\over6},\)
\(\displaystyle \sum_{i=1}^na_i^2=\sum_{i=1}^ni^2={n(n+1)(2n+1)\over6}.\)
According to the ordering theorem, the third sum is minimum if the numbers a_{i} form a decreasing sequence, and maximum if they form an increasing sequence. Thus the lowest and highest values are
\(\displaystyle 2n\sum_{i=1}^n(i1)(ni+1)=2n\cdot{(n1)n(n+1)\over6},\)
and
\(\displaystyle 2n\sum_{i=1}^n(i1)i=2n\cdot{(n1)n(n+1)\over3}.\)
It is easy to check with a little calculation that for small values of n, the possible values of \(\displaystyle \sum_{i=1}^n(i1)a_i\) are as follows:

For all n\(\displaystyle ge\)5, \(\displaystyle \sum_{i=1}^n(i1)a_i\) assumes every integer value between \(\displaystyle {(n1)n(n+1)\over6}\) and \(\displaystyle {(n1)n(n+1)\over3}\). The proof is by induction. As shown above, the statement is true for n=4.
If the statement is true for some n=m, then in the case n=m+1, consider the sequences a_{1},...,a_{m+1}, such that a_{m+1}=m+1 or a_{1}=m+1.
If a_{m+1}=m+1 then
\(\displaystyle \sum{i=1}^n(i1)a_i=\sum_{i=1}^ma_i+(m1)m,\)
and we get the same sums as in the case n=m, but incremented by m(m+1). These sums are, therefore, the integers between \(\displaystyle A={(m1)m(m+1)\over6}+m(m+1)\) and \(\displaystyle B={(m1)m(m+1)\over3}+m(m+1)={m(m+1)(m+2)\over3}\).
If a_{1}=m+1, then
\(\displaystyle \sum_{i=1}^n(i1)a_i=\sum_{i=2}^{m+1}(i1)a_i=\sum_{i=1}^mia_{i+1}=\)
\(\displaystyle =\sum_{i=1}^m(i1)a_{i+1}+\sum_{i=1}^na_{i+1}=\sum_{i=1}^m(i1)a_{i+1}+{m(m+1)\over2},\)
thus here we get the same sums again, but this time incremented by \(\displaystyle {m(m+1)\over2}\). The resulting sums are, therefore, the integers between \(\displaystyle C={(m1)m(m+1)\over6}+{m(m+1)\over2}={m(m+1)(m+2)\over6}\) and \(\displaystyle D={(m1)m(m+1)\over3}+{m(m+1)\over2}\).
It is easy to check that if m\(\displaystyle ge\)4 then C<A\(\displaystyle le\)D<B, and thus all integers between C and B are represented. This completes the proof.
Answer: For n\(\displaystyle ne\)3, the possible values of the sum of the elements selected from the table are in arithmetic progression, where the lowest member is
\(\displaystyle {n^3(n1)(2n1)\over6}+{n(n+1)(2n+1)\over6}+2n\cdot{(n1)n(n+1)\over6}={n(2n^4n^3+3n^2+n+1)\over6},\)
the largest member is
\(\displaystyle {n^3(n1)(2n1)\over6}+{n(n+1)(2n+1)\over6}+2n\cdot{(n1)n(n+1)\over3}={n(2n^4+n^3+3n^2n+1)\over6},\)
and the common difference is 2n.
Fof n=3, the result is similar, but with the middle term of the sequence, 95 missing; the possible values are 83, 89, 101 and 107.
A. 276. The product of the positive numbers x_{1}, ..., x_{n} is , where 1 is a real number. Prove that
\(\displaystyle \sum_{i=1}^n{1\over(x_i+1)^{1/\alpha}}\ge1.\)
Solution. Let \(\displaystyle f(t)={1\over(t+1)^{1/\alpha}}\). We shall prove the following two lemmas:
Lemma 1. If a\(\displaystyle le\)b\(\displaystyle le\)c\(\displaystyle le\)d are positive numbers, and ad=bc, then
f(a)+f(d)\(\displaystyle ge\)min(f(b)+f(c),1).
Lemma 2. If the geometric mean of the numbers x_{1},x_{2},...,x_{n} is m, then
f(x_{1})+f(x_{2})+...+f(x_{n})\(\displaystyle ge\)min(n^{.}f(m),1).
The statement of the problem is a special case of lemma 2, because if the product of the positive numbers x_{1},...,x_{n} is (n^{\(\displaystyle alpha\)}1)^{n}, i.e. their geometric mean is m=n^{\(\displaystyle alpha\)}1, then n^{.}f(m)=1.
Proof for lemma 1. Let \(\displaystyle m=\sqrt{ad}=\sqrt{bc}\), and
\(\displaystyle g(t)=f(mt)+f(m/t)=\bigg(mt+1\bigg)^{{1\over\alpha}}+\bigg({m\over t}+1\bigg)^{{1\over\alpha}}\)
for all positive t, and t_{1}=c/m, t_{2}=d/m. Then 1\(\displaystyle le\)t_{1}\(\displaystyle le\)t_{2}, and the statement is that
g(t_{2})\(\displaystyle ge\)min(g(t_{1}),1).
It follows from the definition that \(\displaystyle \lim\limits_\infty g=1.\)
Let us examine the monotonicity of the function g on the interval [1,\(\displaystyle infty\)). The derivative of the function g is
\(\displaystyle g'(t)={m\over\alpha}\left(\bigg(mt+1\bigg)^{{\alpha+1\over\alpha}}+{1\over t^2}\bigg({m\over t}+1\bigg)^{{\alpha+1\over\alpha}}\right),\)
which is positive if and only if
\(\displaystyle \bigg(mt+1\bigg)^{\alpha+1\over\alpha\)t^2\bigg({m\over t}+1\bigg)^{\alpha+1\over\alpha}.">
By raising to the \(\displaystyle {\alpha\over\alpha+1}\)th power and rearranging, we have
\(\displaystyle t^{2\alpha\over\alpha+1}mt+mt^{\alpha1\over\alpha+1}1<0.\)
Let h(t) denote the lefthand side. For further investigation, we will need the first two derivatives of the function h, and the values of h(1) and h'(1):
\(\displaystyle h(t)=t^{2\alpha\over\alpha+1}mt+mt^{\alpha1\over\alpha+1}1,\qquad h(1)=0;\)
\(\displaystyle h'(t)={2\alpha\over\alpha+1}t^{\alpha1\over\alpha+1}m+{\alpha1\over\alpha+1}mt^{{2\over\alpha+1}},\qquad h'(1)={2\over\alpha+1}(\alpham);\)
\(\displaystyle h''(t)={2\alpha(\alpha1)\over(\alpha+1)^2}t^{{\alpha+3\over\alpha+1}}\bigg(t{m\over\alpha}\bigg).\)
Now let us distinguish the following cases, depending on the values of m and \(\displaystyle alpha\):
Case 1. : \(\displaystyle alpha\)=1 and m\(\displaystyle le\)1.
Case 2. : \(\displaystyle alpha\)=1 and m>1.
Case 3. : \(\displaystyle alpha\)>1 and m\(\displaystyle le\).
Case 4. : >1 and m>.
In case 1, h(t)=(1m)(t1)0 for all t>1, thus h0 in the interval (1,).
In case 2, h(t)=(1m)(t1)<0 for all t>1, thus h<0 in the interval (1,).
In case 3, h''>0 for h'(1)0 and t>1, thus h'>0 in the entire interval (1,). As h(1)=0, it follows that h>0 in the interval (1,).
In case 4, h'(1)<0, and h''<0 in the interval (1,m/). Thus h'<0 in that interval. As h(1)=0, it follows that h<0 in the interval (1,m/]. In the interval (m/,), h''>0, that is, the function h is convex down. As h(m/)<0 and , it follows that there exists a real number >1, such that h<0 on the interval (1,), and h>0 on the interval (,).
In either case, if h(t_{2})0, then h0 in the entire interval (t_{2},), that is, g'0. Hence the function g monotonically decreases in the interval [t_{2},), and If h(t_{2})0, then h0 in the interval (1,t_{2}), that is, g'0. Thus g imonotonically increases, and és g(t_{1})g(t_{2}). Lemma 1 is proved.
Proof for lemma 2. The proof is by induction. If n=1 then only x_{1}=m is possible, and the statement is meaningless. Assume that n2, and the statement is true if the number of variables is less than that.
The sequence x_{1},...,x_{n} contains both a number not greater than m, and a number not smaller than m. We can suppose, for example, that x_{1}mx_{2}. Let y_{1} denote the smaller number out of m and x_{1}x_{2}/m, and let y_{2} denote the larger number. Then x_{1}y_{1}y_{2}x_{2} and y_{1}y_{2}=x_{1}x_{2}. With lemma 1, it follows that
(2)  f(x_{1})+f(x_{2})min(f(y_{1})+f(y_{2}),1)=min(f(m)+f(y_{2}),1). 
The geometric mean of the numbers y_{2},x_{3},...,x_{n} is also m. The assumption can be applied, and we get
(3)  f(y_{2})+f(x_{3})+...+f(x_{n})min((n1)f(m),1). 
If f(x_{1})+f(x_{2})>1, then f(x_{1})+...+f(x_{n})f(x_{1})+f(x_{2})>1, and hence the statement is true. If f(x_{1})+f(x_{2})1, then (2) states that f(x_{1})+f(x_{2})f(m)+f(y_{2}). Using this result, and (3), we have
f(x_{1})+f(x_{2})...+f(x_{n})f(m)+f(y_{2})+f(x_{3})+...+f(x_{n})
f(m)+min((n1)f(m),1)=min(nf(m),f(m)+1)min(nf(m),1).
Thus lemma 2 is proved, and so is the statement of the problem
A. 277. Let H_{1} be an nsided polygon. Construct the sequence H_{1}, H_{2}, ..., H_{n} of polygons as follows. Having constructed the polygon H_{k}, H_{k+1} is obtained by reflecting each vertex of H_{k} through its kth neighbour in the counterclockwise direction. Prove that if n is a prime, then the polygons H_{1} and H_{n} are similar.
Solution 1. In order to be able to formulate auxiliary statements more accurately, the following solution uses arrays of n points rather than nsided polygons.
For every integer 0<k<n, let _{k} denote the transformation that maps an array of n points onto another by reflecting each point in its kth successor. The definition of the transformation can be extended to any integer k if k is considered modulo n.
The statement is that H_{k+1}=_{k}(H_{k}), and we need to prove that the ngon _{n1}(_{n2}(..._{2}(_{1}(H_{1}))...)) is similar to H_{1}.
First we shall prove that the transformations commute, that is, for all integers k,m and every array P of n numbers, _{m}(_{k}(P))=_{k}(_{m}(P)). Let the points of P be p_{1}, ..., p_{n}. Then, with all the indices taken modulo n,
 the ith point of the polygon _{k}(P) is 2p_{i+k}p_{i};
 the ith point of the polygon _{m}(P) is 2p_{i+m}p_{i};
 the ith point of the polygon _{m}(_{k}(P)) is 2(2p_{i+m+k}p_{i+m})(2p_{i+k}p_{i})=4p_{i+m+k}2p_{i+k}2p_{i+m}+p_{i};
 the ith point of the polygon _{k}(_{m}(P)) is 2(2p_{i+k+m}p_{i+k})(2p_{i+m}p_{i})=4p_{i+m+k}2p_{i+k}2p_{i+m}+p_{i}.
Thus the arrays _{m}(_{k}(P)) and _{k}(_{m}(P)) are identical.
It follows from the commutativity of the composition of transformations that the transformations _{1}, _{2}, ..., _{n1} can be carried out in any order, the result will always be the same.
Let H_{1}=(h_{1},...,h_{n}) and H_{n}=(g_{1},...,g_{n}). As every transformation replaces the points by a linear combination, each of the points g_{1}, ..., g_{n} can be expressed as an appropriate linear combination of the points h_{1}, ..., h_{n}. As the sequence of transformations is symmetrical with respect to the cyclic permutation of the indices, the coefficients of the various linear combinations can be obtained from each other by cyclic permutations, that is, there exist such constants a_{0}, a_{1}, ..., a_{n1} that for all i,
(4)  g_{i}=a_{0}h_{i}+a_{1}h_{i+1}+...+a_{n1}h_{i+n1}. 
Now let us prove that a_{1}=a_{2}=...=a_{n1}.
For any integer 0<m<n, let _{m} denote the permutation (x_{1},...,x_{n})(x_{m},x_{2m},...,x_{nm}). (This is really a permutation if n is a prime.) By substituting the definition, it can be seen that for every integer k and every array P of n numbers,
_{k}(_{m}(P))=_{m}(_{km}(P)).
By applying this identity (n1) times, we get
_{n1}(_{n2}(..._{1}(_{m}(H_{1}))...))=_{m}(_{(n1)m}(_{(n2)m}(..._{m}(H_{1})...))).
As n is a prime, each of _{1}, ..., _{n1} occurs exactly once among the transformations _{m}, _{2m}, ..., _{(n1)m}. Thus the righthand side is _{m}(H_{n})=(g_{m},g_{2m},...,g_{nm}).
Apply the transformations on the lefthand side to the polygon _{m}(H_{1})=(h_{m},h_{2m},...,h_{nm}). It follows from identity (4) that the ith member of the resulting array of n points is
a_{0}h_{im}+a_{1}h_{(i+1)m}+...+a_{n1}h_{(i+n1)m}.
Putting the results together, we have that for all i,
a_{0}h_{im}+a_{1}h_{(i+1)m}+...+a_{n1}h_{(i+n1)m}=
=g_{im}=a_{0}h_{im}+a_{1}h_{im+1}+...+a_{n1}h_{im+n1}.
The coefficient of h_{(i+1)m} is a_{1} on the lefthand side, and a_{m} on the righthand side, therefore a_{m}=a_{1}. As this is true for all 0<m<n, a_{1}=a_{2}=...=a_{n1}.
The ith edge vector of the polygons H_{1} and H_{n} is h_{i+1}h_{i}, and g_{i+1}g_{i}=(a_{0}a_{1})(h_{i+1}h_{i}). Thus the two polygons are similar, with a ratio of a_{0}a_{1}.
Solution 2. This solution uses complex numbers, and the so called finite Fourier transform . The polygons are considered to be arrays of n complex numbers. In order to make calculations simpler, let us place H_{1} onto the complex plane so that its centroid should be 0.
If X is an array of n numbers, let X_{j} denote its jth element. The indices are always meant modulo n, for example, X_{n}=X_{0} or X_{1}=X_{n1}.
Arrays of n compex numbers can be added term by term, subtracted, and multiplied by scalars. In addition, define the finite Fourier transform of an array of n numbers as follows. Let be the first complex nth root of unity. The Fourier transform of the array is the array (X), such that for each j,
There are several interesting properties and applications of the Fourier transform. See, for example, Algorithms, by P. Gács and L. Lovász. Now we are going to use the following properties:
 For any number c and array X of n numbers, (c^{.}X)=c^{.}(X).
 The Fourier transform has an inverse. It is easy to check that,
Like in solution 1, let _{k} be the transformation that reflects every element of an array in its kth successor, that is,
_{k}(X)_{j}=2X_{j+k}X_{j}.
It follows from the definitions of the Fourier transform and _{k} that for any arrayx of n numbers,
that is,
(_{k}(x))=(1,2^{k}1,2^{2k}1,...,2^{(n1)k}1)^{.}(x).
Applying this to every 0<k<n, we have
If j=0, then . If 0<j<n, then  as n is a prime  . Let C denote this number.
Thus we obtain
(5)  (_{n1}(_{n2}(..._{2}(_{1}(x))...)))=(1,C,C,...,C)^{.}(x). 
Consider the arrays (H_{1}) and (H_{n}) of n numbers. Because of the choice of the centroid, (H_{1})_{0}=0, and thus (5) can also be written in the following form:
(H_{n})=(_{n1}(_{n2}(..._{2}(_{1}(H_{1}))...)))=C^{.}(H_{1}).
Hence H_{n}=C^{.}H_{1}, that is, H_{n} is obtained from H_{1} by an enlargement from 0 with a scale factor of C.
Remark. With the polynomial
p(t)=(t)(t^{2})^{.}(t^{n1})=x^{n1}+x^{n2}+...+x+1,
we get
(Using that n is an odd prime, and n(n1)/2 is divisible by n.)