\ ..

Problem 1

(a) Let ABC be a right-angled triangle whose vertices have integer coordinates and whose legs lie along edges of the squares with <A=90^o, AB=m and AC=n. Let us consider the mxn rectangle ABCD as shown in the figure.

For an arbitrary polygon P let us denote by S₁(P) the total area of the black part of P and by S₂(P) the total area of its white part.

When m and n are of the same parity the colouring of the rectangle ABCD is centrally symmetric about the midpoint of the hypotenuse BC. Hence S₁(ABC) = S₁(BCD) and S₂(ABC) = S₁(BCD). Therefore

f(m, n) = | S₁(ABC) - S₂(ABC) | = 1/2 | S₁(ABCD) - S₂(ABCD) |.

Hence f(m, n) = 0 for m, n both even and f(m, n) = 1/2 for m, n both odd.

(b) If m, n are both even or both odd the results follows from (a). Suppose now that m is odd and n is even. Consider a point L on AB such that AL = m -1 as shown below.

Since m - 1 is even we have f(m - 1, n) = 0, i.e., S₁(ALC) = S₂(ALC). Therefore

f(m, n) = | S₁(ABC) - S₂(ABC) | = | S₁(LBC) - S₂(LBC) |

Area LBC = n/2 1/2 max {m, n}

(c) Let us compute f(2k + 1,2k). As in (b) we will consider a point L on AB such that AL = 2k. As f(2k, 2k) = 0 and S₁(LBC) = S₂(ALC) we have

f(2k + 1,2k) = | S₁(LBC) - S₂(LBC) |.

The area of the triangle LBC is k. Suppose without loss of generality that the diagonal LC is all black (see figure below). Then the white part of LBC consists of several triangles BLN_2k, M_2k-1L_2k-1N_2k-1, ... , M₁L₁N₁, each of them being similar to BAC. Their total area is

.

Therefore

and thus

This function takes arbitrarily large values.

Problem 2

Let us denote the diameters which are perpendicular bisectors of AB and AC by b and c respectively. Let us fix an orientation for arcs. Then the notation PQ defines a unique arc on the circle.

Let X, Y be the second intersections of the circle with the lines BV and CW respectively. Then the chord CY is the mirror image of the chord AU in c.

Thus YC = AU. Similarly XB = AU. Then XB = YC and hence the line segments BX and YC are symmetric with respect to the diameter d which passes through the midpoint of BY, with X being the mirror image of C and Y being the mirror image of B.

As the point T lies on the line d, the perpendicular bisector of both BY and CX, we have TB = TY and TC = TX.

Then AU = BX = BT + TX = BT + CT.

Problem 3

For any permutation = ( y₁, y₂, ... , y_n ) of ( x₁, x₂, ... , x_n ) denote by S() the value of the sum y₁ + 2y₂ + ... + ny_n. Let r = (n + 1)/2. It has to be shown that |S()| r for some permutation .

Let ₀ be the identity permutation ₀ = ( x₁, ... , x_n ) and let be the reverse permutation = ( x_n , ... , x₁ ). If |S(₀)| r or |S()| r, the claim is true. Assume for the sequel that |S(₀)| > r and |S()| > r. Note that

S(₀) + S() = ( x₁ + 2x₂ + ... + nx_n ) + ( x_n + 2x_n-1 + ... + nx₁ ) = (n + 1)( x₁ + ... + x_n ),

and hence | S(₀) + S() | = n + 1 = 2r. Since each one of the numbers S(₀) and S() exceeds r in absolute value, they must have opposite signs. Accordingly, one of them is grater than r and the other one is smaller than -r.

Starting from ₀, we are able to obtain any permutation by successive transpositions of neighbouring elements. In particular, there exists a chain of permutations ₀, ₁, ... , _m such that _m = and, for each i {0, ... , m-1}, the permutation     _i+1 arises from _i by interchanging two of its neighbouring terms.

This means that if _i = ( y₁ , ... , y_n) and _i+1 = ( z₁ , ... , z_n), then there is an index k {1, ... , n - 1} such that

z_k = y_k+1 ,    z_k+1 = y_k ;       z_j = y_j     for jk, k + 1.

And since the numbers x_i do not exceed r in absolute value,

| S(_i+1) - S(_i) | = | kz_k + (k + 1)z_k+1 - ky_k (k + 1)y_k+1 |
= | y_k - y_k+1 | | y_k | + | y_k+1 | 2r.

This shows that the distance between any two successive numbers in the sequence S(₀), S(_i) , ... , S(_m) is not greater than 2r.

Recall that the numbers S(₀) and S(_m), regarded as points of the real line, lie putside the interval [-r, r], on distinct sides of it. It follows that at least one of the numbers S(_i) has to hit an interval. Thus we have S(_i) r for a certain _i, and the assertion is proved.

Problem 4

(a) Let n > 1 be an integer. Suppose that a silver n x n matrix A exists. Let x be a fixed element of {1, 2, ... , 2n -1} which does not appear on the diagonal of A. (Such an element exists, since there are only n elements on the diagonal but 2n - 1 elements in total.) The union of the ith row and the ith column we shall call it ith cross. The element x appears in each cross exactly once. If x is the (i , j)th entry of A, then it belongs to the ith cross and also to the jth cross. In this case we say that these crosses are x-linked. (For example, in the matrix A below the 1st and the 4th crosses are 6-linked.) This implies that all n crosses are partitioned into pairs of x-linked ones, and therefore n is even. But 1997 is an odd number.

(b) For n = 2

is a silver matrix. For n = 4 we have already several of them, for example

The construction of A can be generalized. Suppose that an n x n silver matrix exists. Then 2n x 2n silver matrix D can be constructed as follows:

where B is the n x n matrix obtained from A by adding 2n to each entry, and C is the matrix obtained from A by adding 2n to each entry, and C is the matrix obtained from B by replacing all its diagonal entries by 2n. This matrix will be again a silver matrix. To prove this let us consider the ith cross of D. Suppose that i n; the other case is similar. This cross is composed of the ith cross of A, the ith row of B and the ith column of C. The ith cross of A contains numbers {1, 2, ... , 2n -1}. The ith row of B and the ith column of C together contain the numbers {2n, 2n + 1 , ... , 4n - 1}.

Problem 5

Let a, b be a solution, let d be the greatest common divisor of a and b and let a = du, b = dv, with integers u, v being coprime, The given equation is equivalent to

Comparing the exponents dv² and u in (1), we distinguish three cases.

Case 1. dv² = u. Then (1) implies u = v. Since u, v are coprime, we get u = v = 1; and dv² = u yields d = 1. Hence a = b = 1, which is a solution.

Case 2. dv² > u. Rewriting (1) as

we see that u^dv2 divides v^u. Since u, v are coprime, u =1 and (2) becomes

Now, if d =1 then by (3) v = 1 and the inequality dv² > u fails to hold. And for d 2 we have

d^dv2-1 2^2v2-1 2^2v-1 > v     for v = 1, 2, 3, ... ;

The last inequality is easily verified by induction on v. This contradicts (3) and shows that there are no solutions in this case.

Case 3. dv² < u. (Hence u > d.) Rewriting (1) as

We see that v^u divides u^dv2. Since u, v are coprime, v = 1 and (4) becomes

The exponentiation bases in (5) satisfy the inequality u > d; hence the exponents satisfy the opposite inequality d < u - d.

By (5), any prime divisor p is of d is also a divisor of u. Taking y, z to be the greatest exponents with p^y | u, p^z | d, we obtain from (5) yd = z(u - d), which shows that y > z. Thus d divides u, so u = kd or a certain integer k. Note that k 3 because u>2d. Substituting u = kd into (5), we get

It follows that d cannot be 1. Therefore d 2.

If k = 3, then by (6) d = 3, whence u = 9, a = 27, b = 3.
If k = 4, then by (6) d² = 4, whence d = 2, u = 8, a = 16, b = 2.
If k 5, then d^k-2 2^k-2 > k (by easy induction) and (6) fails.

Thus, the equation has three solutions: (a, b) = (1, 1), (27, 3) and (16, 2).

Problem 6

If n = 2k + 1 is any odd integer greater than 1, then every representation of n in the given form has a "1" as one of its summands. Deleting we obtain a representation of the number 2k. And conversely, by attaching a "1" to a representation of 2k we obtain a representation of 2k + 1. The correspondence that results is obviously bijective. The recursion formula follows:

Further, if n = 2k is any positive even integer, then every representation of n in the given form is one of the following two types: either it contains some terms equal to 1 or it does not contain such terms. In the first case we can delete one "1" to obtain a representation of 2k - 1: as before, we see that there is a bijection between the "first-type" representations of 2k and all representations of 2k - 1. In the case of a "second-type" representation (with no terms equal to 1), we can divide all its terms by 2 and obtain a representation of k; and also this correpondence is bijective. The second recursion formula follows:

Both of these formulae hold for any integer k1. Obviously, f(1) = 1. Let us additionally define f(0) = 1; then the formula (1) holds for k = 0 as well. It follows from (1) and (2) that the function f is non-decreasing.

According to (1), the number f(2k - 1) in the formula (2) can be replaced by f(2k - 2), yielding the equation

f (2k) - f (2k - 2) = f (k)     for k = 1, 2, 3, ... .

Taking any integer n1 and summing these equations up over k = 1 , ... , n, we obtain the following formula:

We pass the two-sided estimation of the sequence ( f(2ⁿ): n = 1, 2, 3, ... ). The upper estimate is easy: in the formula (3) all the summands are not greater than the last one. And since 2 = f(2) f(n) for n2, we get

f (2n) = 2 + ( f (2) + ... + f(n) ) 2 + (n - 1) f(n)

f(n) + (n - 1) f(n) = nf(n)      for n = 2, 3, 4, ... .

Consequently,

f(2ⁿ) 2^n-1 . f(2^n-1) 2^n-1 . 2^n-2 . f(2^n-2) 2^n-1 . 2^n-2 . 2^n-3 . f(2^n-3)

... 2^{(n-1) + (n -2) + ... + 1} . f(2) = 2^{n (n-1)/2} . 2.

And since 2^{n (n-1)/2} . 2 < 2^n2/2 for n3, the upper estimate results.

To work out the lower estimate, we first show that

f (b + 1) - f(b) f(a + 1) - f(a)

(4)

whenever b a 0 are integers of the same party. Indeed: if a and b are both even, then in view of (1) we have zeros on both sides of (4); and if a and b are odd, then by (2) we get f(b + 1) - f(b) = f( (b + 1)/2 ), f(a + 1) - f(a) = f( (a + 1)/2 ) and the inequality in (4) holds because the function f is non-decreasing.

Let us take any integers r k 1, r even, and substitute subsequently in (4) the numbers a = r - j, b = r + j for j = 0, ... , k - 1. Then add the inequalities that result, to obtain

f (r + k) - f(r) f(r + 1) - f(r - k + 1).

Since r is even, we have f(r + 1) = f(r), and hence

f (r + k) + f(r - k + 1) 2 f(r)      for k = 1, ... , r..

Summing these inequalities up over k = 1 , ... , r we get

f(1) + f(2) + ... + f(2r)2r f(r).

In view of (3) the sum on the left-hand side is equal to f(4r) - 1. Thus

f(4r) 2r f(r) + 1 > 2r f(r)      for every integer r2.

Taking r = 2^m-2 we hence obtain

To ensure that r = 2^m-2 is even, m ought to be an integer greater than 2; note, however, that (5) is also true for m = 2.

Finally, let n be any integer greater than 1. If l is a positive integer such that 2l n, then applying the inequality (5) for m = n, n-1, ... , n - 2l + 2 we get

f (2ⁿ) > 2^n-1 . f (2^n-2) > 2^n-1 . 2^n-3 . f (2^n-4) > 2^n-1 . 2^n-3 . 2^n-5 . f (2^n-6)

> ... > 2^{(n-1) + (n -3) + ... + (n - 2l + 1)} . f (2^n-2l) = 2^{l (n - l)} . f (2^{n - 2l}).

Now, if n is even, take l = n/2; and if n is odd, take l = (n - 1)/2. The resulting inequalities are:

f(2ⁿ) > 2^n2/4 . f(2⁰) = 2^n2/4      for n even,

f(2ⁿ) > 2^{(n2 - 1)/4} . f(2¹) = 2^{(n2 - 1)/4} . 2 > 2^n2/4      for n odd.

We have obtained the required lower estimate for every integer n 2. (It is also valid for n = 1, as can be verified directly.)

feedbacks: webmaster@oma.org.ar