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², 3², ..., (n²)² are written in increasing order into an nxn array:

1²	2²	...	n²
(n+1)²	(n+2)²	...	(2n)²
...	...		...
(n²-n+1)²	(n²-n+2)²	...	(n²)²

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_ith element out of the i-th row, where i=1,2,...,n. The numbers a₁,...,a_n represent a permutation of 1,2,...,n, and the sum of the selected numbers is

$\displaystyle \sum_{i=1}^n\big((i-1)n+a_i\big)^2=n^2\sum_{i=1}^n(i-1)^2+\sum_{i=1}^na_i^2+2n\sum_{i=1}^n(i-1)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(i-1)^2=n^2\cdot{(n-1)n(2n-1)\over6}={n^3(n-1)(2n-1)\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(i-1)(n-i+1)=2n\cdot{(n-1)n(n+1)\over6},$

and

$\displaystyle 2n\sum_{i=1}^n(i-1)i=2n\cdot{(n-1)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(i-1)a_i$ are as follows:

n	possible values of $\sum_{i=1}^n(i-1)a_i$
1	0
2	1, 2
3	4, 5, 7, 8
4	10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

For all n$\displaystyle ge$5, $\displaystyle \sum_{i=1}^n(i-1)a_i$ assumes every integer value between $\displaystyle {(n-1)n(n+1)\over6}$ and $\displaystyle {(n-1)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₁,...,a_m+1, such that a_m+1=m+1 or a₁=m+1.

If a_m+1=m+1 then

$\displaystyle \sum{i=1}^n(i-1)a_i=\sum_{i=1}^ma_i+(m-1)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={(m-1)m(m+1)\over6}+m(m+1)$ and $\displaystyle B={(m-1)m(m+1)\over3}+m(m+1)={m(m+1)(m+2)\over3}$.

If a₁=m+1, then

$\displaystyle \sum_{i=1}^n(i-1)a_i=\sum_{i=2}^{m+1}(i-1)a_i=\sum_{i=1}^mia_{i+1}=$

$\displaystyle =\sum_{i=1}^m(i-1)a_{i+1}+\sum_{i=1}^na_{i+1}=\sum_{i=1}^m(i-1)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={(m-1)m(m+1)\over6}+{m(m+1)\over2}={m(m+1)(m+2)\over6}$ and $\displaystyle D={(m-1)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(n-1)(2n-1)\over6}+{n(n+1)(2n+1)\over6}+2n\cdot{(n-1)n(n+1)\over6}={n(2n^4-n^3+3n^2+n+1)\over6},$

the largest member is

$\displaystyle {n^3(n-1)(2n-1)\over6}+{n(n+1)(2n+1)\over6}+2n\cdot{(n-1)n(n+1)\over3}={n(2n^4+n^3+3n^2-n+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₁, ..., x_n is $(n^\alpha-1)^n$ , where $alpha$ $ge$ 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₁,x₂,...,x_n is m, then

f(x₁)+f(x₂)+...+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₁,...,x_n is (n^{$\displaystyle alpha$}-1)ⁿ, 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₁=c/m, t₂=d/m. Then 1$\displaystyle le$t₁$\displaystyle le$t₂, and the statement is that

g(t₂)$\displaystyle ge$min(g(t₁),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^{\alpha-1\over\alpha+1}-1<0.$

Let h(t) denote the left-hand 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^{\alpha-1\over\alpha+1}-1,\qquad h(1)=0;$

$\displaystyle h'(t)={2\alpha\over\alpha+1}t^{\alpha-1\over\alpha+1}-m+{\alpha-1\over\alpha+1}mt^{-{2\over\alpha+1}},\qquad h'(1)={2\over\alpha+1}(\alpha-m);$

$\displaystyle h''(t)={2\alpha(\alpha-1)\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$ $alpha$ .

Case 4. : $alpha$ >1 and m> $alpha$ .

In case 1, h(t)=(1-m)(t-1) $ge$ 0 for all t>1, thus h $ge$ 0 in the interval (1, $infty$ ).

In case 2, h(t)=(1-m)(t-1)<0 for all t>1, thus h<0 in the interval (1, $infty$ ).

In case 3, h''>0 for h'(1) $ge$ 0 and t>1, thus h'>0 in the entire interval (1, $infty$ ). As h(1)=0, it follows that h>0 in the interval (1, $infty$ ).

In case 4, h'(1)<0, and h''<0 in the interval (1,m/ $alpha$ ). Thus h'<0 in that interval. As h(1)=0, it follows that h<0 in the interval (1,m/ $alpha$ ]. In the interval (m/ $alpha$ , $infty$ ), h''>0, that is, the function h is convex down. As h(m/ $alpha$ )<0 and $\lim\limits_\infty h=\infty$ , it follows that there exists a real number $varrho$ >1, such that h<0 on the interval (1, $varrho$ ), and h>0 on the interval ( $varrho$ , $infty$ ).

In either case, if h(t₂) $ge$ 0, then h $ge$ 0 in the entire interval (t₂, $infty$ ), that is, g' $le$ 0. Hence the function g monotonically decreases in the interval [t₂, $infty$ ), and $g(t_2)\ge\lim\limits_\infty g=1.$ If h(t₂) $le$ 0, then h $le$ 0 in the interval (1,t₂), that is, g' $ge$ 0. Thus g imonotonically increases, and és g(t₁) $le$ g(t₂). Lemma 1 is proved.

Proof for lemma 2. The proof is by induction. If n=1 then only x₁=m is possible, and the statement is meaningless. Assume that n $ge$ 2, and the statement is true if the number of variables is less than that.

The sequence x₁,...,x_n contains both a number not greater than m, and a number not smaller than m. We can suppose, for example, that x₁ $le$ m $le$ x₂. Let y₁ denote the smaller number out of m and x₁x₂/m, and let y₂ denote the larger number. Then x₁ $le$ y₁ $le$ y₂ $le$ x₂ and y₁y₂=x₁x₂. With lemma 1, it follows that

(2)	f(x₁)+f(x₂) $ge$ min(f(y₁)+f(y₂),1)=min(f(m)+f(y₂),1).

The geometric mean of the numbers y₂,x₃,...,x_n is also m. The assumption can be applied, and we get

(3)	f(y₂)+f(x₃)+...+f(x_n) $ge$ min((n-1)f(m),1).

If f(x₁)+f(x₂)>1, then f(x₁)+...+f(x_n) $ge$ f(x₁)+f(x₂)>1, and hence the statement is true. If f(x₁)+f(x₂) $le$ 1, then (2) states that f(x₁)+f(x₂) $ge$ f(m)+f(y₂). Using this result, and (3), we have

f(x₁)+f(x₂)...+f(x_n) $ge$ f(m)+f(y₂)+f(x₃)+...+f(x_n) $ge$

$ge$ f(m)+min((n-1)f(m),1)=min(nf(m),f(m)+1) $ge$ min(nf(m),1).

Thus lemma 2 is proved, and so is the statement of the problem

A. 277. Let H₁ be an n-sided polygon. Construct the sequence H₁, H₂, ..., 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 k-th neighbour in the counterclockwise direction. Prove that if n is a prime, then the polygons H₁ 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 n-sided polygons.

For every integer 0<k<n, let $tau$ _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= $tau$ _k(H_k), and we need to prove that the n-gon $tau$ _n-1( $tau$ _n-2(... $tau$ ₂( $tau$ ₁(H₁))...)) is similar to H₁.

First we shall prove that the transformations commute, that is, for all integers k,m and every array P of n numbers, $tau$ _m( $tau$ _k(P))= $tau$ _k( $tau$ _m(P)). Let the points of P be p₁, ..., p_n. Then, with all the indices taken modulo n,

- the ith point of the polygon $tau$ _k(P) is 2p_i+k-p_i;

- the ith point of the polygon $tau$ _m(P) is 2p_i+m-p_i;

- the ith point of the polygon $tau$ _m( $tau$ _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 $tau$ _k( $tau$ _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 $tau$ _m( $tau$ _k(P)) and $tau$ _k( $tau$ _m(P)) are identical.

It follows from the commutativity of the composition of transformations that the transformations $tau$ ₁, $tau$ ₂, ..., $tau$ _n-1 can be carried out in any order, the result will always be the same.

Let H₁=(h₁,...,h_n) and H_n=(g₁,...,g_n). As every transformation replaces the points by a linear combination, each of the points g₁, ..., g_n can be expressed as an appropriate linear combination of the points h₁, ..., 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₀, a₁, ..., a_n-1 that for all i,

(4)	g_i=a₀h_i+a₁h_i+1+...+a_n-1h_i+n-1.

Now let us prove that a₁=a₂=...=a_n-1.

For any integer 0<m<n, let $pi$ _m denote the permutation (x₁,...,x_n) $to$ (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,

$tau$ _k( $pi$ _m(P))= $pi$ _m( $tau$ _km(P)).

By applying this identity (n-1) times, we get

$tau$ _n-1( $tau$ _n-2(... $tau$ ₁( $pi$ _m(H₁))...))= $pi$ _m( $tau$ _(n-1)m( $tau$ _(n-2)m(... $tau$ _m(H₁)...))).

As n is a prime, each of $tau$ ₁, ..., $tau$ _n-1 occurs exactly once among the transformations $tau$ _m, $tau$ _2m, ..., $tau$ _(n-1)m. Thus the right-hand side is $pi$ _m(H_n)=(g_m,g_2m,...,g_nm).

Apply the transformations on the left-hand side to the polygon $pi$ _m(H₁)=(h_m,h_2m,...,h_nm). It follows from identity (4) that the ith member of the resulting array of n points is

a₀h_im+a₁h_(i+1)m+...+a_n-1h_(i+n-1)m.

Putting the results together, we have that for all i,

a₀h_im+a₁h_(i+1)m+...+a_n-1h_(i+n-1)m=

=g_im=a₀h_im+a₁h_im+1+...+a_n-1h_im+n-1.

The coefficient of h_(i+1)m is a₁ on the left-hand side, and a_m on the right-hand side, therefore a_m=a₁. As this is true for all 0<m<n, a₁=a₂=...=a_n-1.

The ith edge vector of the polygons H₁ and H_n is h_i+1-h_i, and g_i+1-g_i=(a₀-a₁)(h_i+1-h_i). Thus the two polygons are similar, with a ratio of a₀-a₁.

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₁ 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₀ or X_-1=X_n-1.

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 $\varepsilon=\cos{2\pi\over n}+i\sin{2\pi\over n}$ be the first complex nth root of unity. The Fourier transform of the array is the array $varphi$ (X), such that for each j,

$\varphi(X)_j=\sum_{m=0}^{n-1}\varepsilon^{mj}\cdot X_m.$

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, $varphi$ (c^.X)=c^. $varphi$ (X).

- The Fourier transform has an inverse. It is easy to check that,

$X_j={1\over n}\sum_{m=0}^{n-1}\varepsilon^{-mj}\cdot\varphi(X)_m.$

Like in solution 1, let $tau$ _k be the transformation that reflects every element of an array in its kth successor, that is,

$tau$ _k(X)_j=2X_j+k-X_j.

It follows from the definitions of the Fourier transform and $tau$ _k that for any arrayx of n numbers,

$\varphi(\tau_k(x))_j=\sum_{m=0}^{n-1}\varepsilon^{jm}\cdot\tau_k(x)_m=\sum_{m=0}^{n-1}\varepsilon^{jm}\cdot(2x_{m+k}-x_m)=$

$=2\varepsilon^{-kj}\sum_{m=0}^{n-1}\varepsilon^{j(m+k)}\cdot x_{m+k}-\sum_{m=0}^{n-1}\varepsilon^{jm}\cdot x_m=(2\varepsilon^{-jk}-1)\varphi(x)_j,$

that is,

$varphi$ ( $tau$ _k(x))=(1,2 $varepsilon$ ^-k-1,2 $varepsilon$ ^-2k-1,...,2 $varepsilon$ ^-(n-1)k-1)^. $varphi$ (x).

Applying this to every 0<k<n, we have

$\varphi(\tau_{n-1}(\tau_{n-2}(\dots\tau_2(\tau_1(x))\dots)))_j=\prod_{k=1}^{n-1}(2\varepsilon^{-kj}-1)\varphi(x)_j.$

If j=0, then $\prod_{k=1}^{n-1}(2\varepsilon^{-kj}-1)=1$ . If 0<j<n, then -- as n is a prime -- $\prod_{k=1}^{n-1}(2\varepsilon^{-kj}-1)=\prod_{k=1}^{n-1}(2\varepsilon^k-1)$ . Let C denote this number.

Thus we obtain

(5)	$varphi$ ( $tau$ _n-1( $tau$ _n-2(... $tau$ ₂( $tau$ ₁(x))...)))=(1,C,C,...,C)^. $varphi$ (x).

Consider the arrays $varphi$ (H₁) and $varphi$ (H_n) of n numbers. Because of the choice of the centroid, $varphi$ (H₁)₀=0, and thus (5) can also be written in the following form:

$varphi$ (H_n)= $varphi$ ( $tau$ _n-1( $tau$ _n-2(... $tau$ ₂( $tau$ ₁(H₁))...)))=C^. $varphi$ (H₁).

Hence H_n=C^.H₁, that is, H_n is obtained from H₁ by an enlargement from 0 with a scale factor of C.

Remark. With the polynomial

p(t)=(t- $varepsilon$ )(t- $varepsilon$ ²)^.(t- $varepsilon$ ^n-1)=x^n-1+x^n-2+...+x+1,

we get

$C=\prod_{k=1}^{n-1}(2\varepsilon^k-1)=\varepsilon^{1+2+...+(n-1)}p(2)=\varepsilon^{n(n-1)/2}(2^n-1)=2^n-1.$

(Using that n is an odd prime, and n(n-1)/2 is divisible by n.)

Already signed up?
New to KöMaL?