Romanian Problem Book

l

File: b75-77

Romanian Problem Book

Version 0

1975"

t;

i­ i,

i

l L

75. \ (A 1). The positive numbers aI, a2, ... , an, bl ~ bz ~ ... ~ b.; satisfy the inequal­

ities ... ,

Prove that

va; + va2 + ... + ~ ~ Vb; + Vb; + ... + A.

Solution. yields

for each k

The solution uses Abel's summation formula. The AM-GM inequality

= 1,2, ... ,11., so we have

fill + va;- + ... +~ ~

~ [(~ + ~+ ... + ~) + (~+ ~ + ... + Jb:)].

In view of this, it suffices to prove that

If we set

(k=l,2, ... ,n), ~

then Sk

Tk by hypothesis, so

1 (1 y'l);; Jb

-al + -a2 + ... + -an = -Sn + Jl);

Vb;

_I_Tn

~

+(

,

Jb;;

1 __.1_) T

~.;r;:

n- l

+ ... +

1)

n- l

75.2 (A 2). Find the maximum value of

~ak ~

1, k = 1,2, ...

5n -

("_1Vb; v'b21_)

This finishes the proof.

where 1/2

- Vb::

,11..

1

l

i;

(1

+ ... + -

- -

1)

51

<

,~Vb;-

= ~ +.. v-,;; + ... + vfb;:. '

File: b75-77

Romanian Problem Book Solution. Let

"'b n

ak

= ~ + Ck,

= L "2 + Ck (1

n

where 0

) (1

)

"2 -

Ck+l

:s Ck :s ~; k = 1,~, .. , ,11.. 1

11.

an+l

1

n

= 4" + 2" LCk - 2"

k=l

The equality

k=1

= al

implies

Cn+l

=

bn =

Version 0

Cn,

~-

hence l:~=1 Ck

Then

n LCk+l k=1

n LCkCk+l. k=l

= l:~=1 Ck+l'

and, therefore

n

L

Ck Ck+l·

k=1

Since

Ck

2: 0, k

for Ck = 0, k is n] 4.

=

= 1,2, ... ,11., we obtain bn :::; 11./4. The equality holds, for instance, 1,2, ... ,n, that is, ak = 1/2, k = 1,2, ... ,11.. So the maximum value of bn '

75.3 (A3). Consider the sets of real numbers A = {al,a2,"'} and B such that al = bl and

bn + l = bn (1 - an + l ) + (1 - bn )an + l

= {b l , b2, ... }

for any positive integer n. Prove that ~ E A if and only if ~ E B.

.j1i

Solution. Assume ~ EA. Then either ~ = al (= positive integer, 11., such that an+l = ~, in which case

bd,

so ~ E B, or there exists a

• If ~ E B, then ~ = bl (= ad, so ~ E A, or there exists a positive integer, 11., such that bn + 1 = ~. Let -no be the least su;h positive integer. Then

which implies (2a n o+ l - 1)(2bn o that ano+l = ~, hence ~ E A.

I.'

If

lit

-

1) = O. Since the choice of no gives bn o =1= ~, it follows

75.4 (SG 1). Given a cone, consider the set 51 formed by the planes which are parallel to its base and divide the cone into n solids of equal volumes, and the, set 52 formed by the planes which are also parallel to the cone's base but divide its lateral surface into 11. parts of equal areas. Prove that 51 n 52 =1= 0 if and only if n contains at least one factor which is a power, with an exponent greater than 2, of a prime. Solution. Let hI, h 2 , ... ,h n - 1 be the altitudes of the cones formed by the planes in 51 and iI, i z , . . . , i n - I those determined by the elements of 52. The cone with the altitude h k is similar to the original one; the ratio of similitude is hkl H, where H is the altitude of the given cone. Since the ratio of their volumes is kin, one obtains

k=I,2,oo.,n-1.

Ii

•

1

2

Romanian Problem Book

File: b75-77

Version 0

Similarly,

~ H

..

=

3fT. V;"

1= 1,2, ... ,12-1.

If 51 n 8 2 =I- (/) then there exist k, I E {I, 2, ... , 12-1} such that h k = it. It follows that yJk/n = and so 12k 2 = 13. Clearly, I k (otherwise 12 = I, which is absurd). Let p be a prime factor of I which is not .a factor of k. Then I = nip ~nd gcd( k, p) = 1, hence 12k!. = 1n 3]} implies that 12 contains ]i as a factor. Conversely, if 12 contains p3 as a factor then 12 = 12lp3. Considering k = 11,1 and I = p12l, we get nk 2 = [3, which is equivalent to hk = i/ and 51 n 82 0.

vrrn,

i=

i=

75. 5 (NT 1). Let p and q be relatively prime odd integers, greater than 1. Prove that

Solution. Let 5 be the set of all integers of the form kp - Iq, where 1 ::; k ::; (q - 1)/2 and 1 ::; l ::; (p - 1)/2. All its elements are nonzero and pairwise distinct. Indeed, if. we assume that kp - l q = 0 then p divides lq, and since gcd'(p, q) = 1, P II, absurd since p > I. And if we set kIP -/ lq = k 2 P - / 2q for k l i= k 2 , it follows that (k l - k 2)p = (l1 -l2)q, hence p I (It -l2 )q, so since gcd(p, q) = 1, p I It -lz, absurd since 1 ::; it, 12 ::; (p - 1)/2 and 11 =1= h imply 0 < III -1 2 1 < p. Therefore 5 contains P;1 . q;l elements. For a fixed k;

lk(; J

of them are positive. Indeed, kp - lq

numbers 1,2, ... ,

2:.

(P - I ) / 2 l -/ i I [=1

p

l~) J.

Hence, 5 contains

J negative . ones.

Tl lUS

> 0 is equivalent to I <

7, so I can be any of the

¥J positive elements, and similarly

2:.1~/)/2l

,

p-1

q-1

=--.-­ 2 2

75.6 (PG 1). Prove that for any 12 greater than 3 there exists a convex polygon with 12 sides, not all equal, such that the sum of the distances from any interior point to its sides ' is a constant.

L

Solution. Note first that the only triangle with the property that the sum of the distances from any interior point to its sides is a constant is the equilateral one, whence the condition 12 > 3. Take a convex n-gon with the given property. Choose a direction not parallel to any of its sides and, drawing two parallels to this direction, cut off two vertices together with parts of the sides having them as endpoints, as shown in the figure. We obtain a convex polygon with 12 + 2 sides, and one can assume that the two newly formed sides have different lengths (clearly the cut can be performed in a convenient way to ensure this). The new polygon also has the stated properties. Indeed, not all of its sides are equal. Furthermore, the sum of the distances from any interior point to its sides is equal to the sum 51 of the distances

t."

3

, t

,

Romanian Problem Book

File: b75-77

Version 0

from the same point to the sides of the old polygon plus the sum 52 of the distances from the point to the two parallels. But 51 is a constant according to the induction hypothesis, and ~ is also a constant, being equal to the distance between two fixed parallel lines. Hence 5 = 51 + 52 is a constant, too. The above argument shows that the property in question can be transmitted from n to n + 2. In order to prove it by induction, we just need to check the base cases n = 4 and 11 = 5. For 11 = 4 it suffices to take any rectangle. The case n = 5 is, however, not obvious if considered directly. But we can start with an equilateral triangle which is known to satisfy our conditions, to perform the construction described above and obtain the desired pentagon. 75.7 (SG2). For a tetrahedron, 1', let 5(1') be the set which consists of the midpoints of the edges, the feet of the altitudes of each face, and the midpoints of the segments which connect, on each face, the orthocenter with the vertices. Prove that if 5(1') contains a subset, 5'(1'), which lies on a sphere, such that two faces of T contain each at least three points of 5'(1') but 5'(1') is not a subset of the union of the two faces then: a) 5(1') contains at most 24 elements;

b) the opposite edges of T are perpendicular;

c) 5 (1'J lies on a sphere.

Solution. Let T = ABCD. One knows that the points considered on each face are concyclic (they lie on the Euler's of the face). Assume that ABC and ABD are the faces that each contain at least three points of 5'(1'). Since the sphere on which 5'(1') lies contains three points on the face ABC, it contains the entire Euler's circle of ABC, in particular the midpoints of AC and BC. Similarly, the above sphere contains all points of 5(1') from ABD, in particular the midpoints of AD and BD. Since 5'(1') is not contained in the union of the two faces, there exists a point, say on the face BCD, which does not belong to ABC and ABD, but is situated on 5'(1'), and hence on the sphere containing 5'(1'). But this sphere contains, also, the midpoints of BC and BD, so it contains the entire Euler's circle of BCD, in particular the midpoint of CD. Since the midpoint of AC and AD also belong to this sphere, the Euler's circle of ADC is situated on the sphere. Hence 5(1') is on the sphere, and c) is proven. Consider the edge AB. It contains its midpoint, P, and the feet of the altitudes from C and D, q and R, respectively. These three points are on a sphere, and AB is a line, so they cannot be all distinct. We distinguish the .. following. cases:

1. P = Q = R. Then AB 1- CD and AB 1- DR, so AB 1- CD. 2. P:j:. Q

= R.

Analogously, AB 1- CD.

3. Q:j:. P = R.

4. Q

L

l

=P f

R.

The cases 3 and 4 are eliminated by the following lemma: In an isosceles triangle, the Euler's circle is tangent to the unequal side. The proof is obvious. In the case 3, for example, the triangle B D A is isosceles (D A = DB), hence AB IS tangent to the sphere on which 5(1') lies, so P = Q = R, absurd. Similarly for case 4. 4

1 I

Romanian Problem Book

File: b75-77

Version 0

Reiterating the above reasoning, it follows that the opposite edges are pairwise perpen­ dicular, hence b) is proven. In case 2, we obtain the maximum number of points: 6 edges times 2J)()ints plus 4 faces times 3 points, 24 points in all, so a) is also proven. 75.8 (SG3). Given four parallel planes, construct a cube having four noncoplanar vertices situated one in each of the given planes. How many such cubes of different sizes can be built? Solution. Any four vertices of a cube which are not situated in the same plane deter­ mine a tetrahedron. There are four such possible cases of nonsimilar tetrahedra. There are figures missing here in the original. Given four parallel planes, PI, P2,P3 ,P4 in that order, and a tetrahedron ABCD, there exists a unique tetrahedron A' B' C' D' similar to ABC D with A', B', C', D' in PI, P2, P3, P4, respecti vely. Indeed, consider E and F on AD such that AE, EF, F D are proportional to the distances between PI and p-, P2 and P3, P3 and P4, respectively. Construct also EG II FC and F H II E B. G E AC, H E B D. The planes BEG and H FC are parallel. Considering the planes' through A. and D parallel to these, we get four parallel planes whose mutual distances are proportional to the distances between the original ones. Constructing, with a convenient ratio of proportionality, the figure similar to the figure above, we obtain the desired cube. Uniqueness follows immediately (start from the final construction and go back through similarity to the original one). Considering another tetrahedron W XY Z nonsimilar to ABCD whose vertices are situ­ ated in the four planes, we obtain, in general, other sizes of the tetrahedron's edges. Let, then, VI V2 V3 V4 be a tetrahedron and define for the set of permutations of {I, 2, 3, 4} the binary relation rv by ~.

~

.. II11-.. '

This is an equivalence relation, and the number of equivalence classes gives the number of tetrahedra similar to the given one and whose vertices are situated on the four planes. For the first case there exists a single such class .(the tetrahedron is regular). In the second case, there exist 4 cla.sses, and for each of the cases 3 and 4 there exist 12 classes. Thus the answer to the second part of the problem is 29. 75.9 (A4). Solve the system

sin a:l cos X2

t

L

where

:1:1

+ .r2 + ... + ;l.:n

= sin X2 cos X3 = ... = sin X n-l cos X n = sin X n cos Xl, =

Tr

and 0 :S

Xk

:S

¥-'

k = 1,2, ... ,n.

Solution. We consider three cases.

Case 1: None of the numbers sin Xk, cos Xk is zero.

5

Romanian Problem Book

File: b75-77

Version 0

then sin Xl = sin X2 and, from the first equation, we obtain cos X2 = cos X3, so X2 = X3. Similarly, X3 = X4, and so on; thus Xk = ;, k = 1,2, ... , n. If X~ =f X2, assume that Xl < X2. Then sin Xl < sin X2, hence cos X2 > cos X3, and so X2 < X3. Repeating this argument, we get Xl < X2 < ... < X n < Xl, absurd. Case 2: There exists an m E {1,2, ... ,n} such that sinx m = O. Then X m = 0 and sin Xm-l cos X m = sinz..; cos Xm+l = 0, hence sin Xm-l = O. Thus :rm-l = O. Continuing this process, one obtains Xk = 0, k = 1, 2,.~. ,n, which violates the condition Xl + X2 + ... + X n = tt, Case 3: There exists an mE {1, 2, ... , n} such that cos X m = O. Then X m = I and If

Xl

= X2

o = sin 1: m - l

cos X m = sin X m cos Xm+l = 0,

hence cos XII/+J = O. Therefore Xm+l = T' Repeating this reasoning, we obtain k = 1,2, ... , n . which impliesn = 2. ­ In conclusion, the system has the unique solution Xl = X2 = ... = X n = ~.

Xk

= T,

75. 10 (A 5). Determine all functions f: Q ~ Q which satisfy the equation

f(x for every

X,

+ y) + f(x

- y)

= 2(f(x) + f(y) + 1)

y E Q.

Solution. For X = Y = 0 we obtain f(O) = -1, and X = 0 gives f(y) ery y E Q, so f is even. Let X = ky, where k is a positive integer. Then

f((k

+ l)y) -

f(ky) = f(ky) - f((k - 1)y)

= f( -y)

for ev­

+ 2(f(y) + 1).

Replacing k: by 1,2, ... , q and adding up the resulting relations, we obtain

f(qy) - f((q - 1)y) = (2q - 1)(f(y)

t.iii

+ 1).

Letting q be, successively, 1,2, ... , n., and adding up the relations obtain, we get

f(ny)

+ 1 = n 2 (f (y ) + 1}

(1)

01'

1

f(y) + 1 = 2(f(ny) n

+ 1)

\

for any y E Q. Then

f

(~) +1= n

-;(f(1) n

+ 1),

By (1) and (2),

f

... ~'.

fk.'

.

k.

ill

c::) +

1

=f

(m . ~) + 1 = m(f (~) + 1) = :: (f(1) + 1). 2

6

(2)

L

L

L s,

I'

~

i­

File: b75-77

Romanian Problem Book

Since / is even, we conclude that the general form of the solution is c = /(1) + 1 is a generic rational number.

=a (Xl +X2 +X4)Xa = a (Xl + Xa + X4 )X2 = a (X2 + Xa + X4)XI = a, where a E R.

Solution. Set

l.l

ii ··ij·;

8

l

~

i­

L

!;

II.

j,

.L:4):l:4

= a

(s -

Xa)X3

=a

(8 -

X2)X2

= a

(8 -

XI)Xl

= a,

(va!3,V03,va!3,v a j 3)

xi - SXl + a = 0 or

and

Case 3:

= ~(8 = - J-a, X3

:1:1

=

,l:2

-

i

~ ""

it

+a= 0

x~

-

sXa

+a = 0

x~

-,-'SX4

SX

+a = =

S

+ a = 0.

°

with roots !(s ± vs 2

one gets 2s ± 2vs 2

-

-

4a),

4a = s,

(-va!3,-va!3,-va!3,-va!3). = !(s + vs 2 -

4a) or vice versa. It = O. Thus, for a =I 0, the system has no X4

(O,s,O,O),

(0,0,8,0),

(8,0,0,0).

°

4a) and X3 = X4 = ~(s + vs 2 - 4a). In this case, .s = =V~a. Onegets the solution (-Fa, -~,~,~)

V82

-

Note. In a similar manner, one can solve the system

k = 1,2, ... ,n

I,.,

~'

SX2

and Xl = X2 = X4 and the five other permutations of it. ., In conclusion, for a =I 0, the system -admits the eight solutions d~cribed in cases 1 and 3, and for a = 0, the four described in case 2 (all the others become (0,0,0,0), which is included in case 2).

...

ill

x~ -

+ Xa + X4

Xl

(O,O,O,S),

u;r;,

I.

-

= X2 = X3 == ~(s - V82 - 4a) and then follows that 28 ± vs 2 - 4a = s, and hence a solutions in case 2; for a = 0, it has the solutions

Case 2:

L

t

(s -

The system becomes

Case 1: .1;1 = .1:2 =.1:3 = .1:4. From Xl + X2 so s = ±4~. This yields the solutions

\

L

L

= :1:1 + X2 + X3 + X4.

Hence Xl, X2, :r3,.1:4 are zeros of the equation x 2 \Ve distinguish the following cases.

~

1M

1, where

(Xl +X2 +Xa)X4

~.

t

Ie (x) = cx2 -

75.~1 (A6). Solve, in complex numbers, the system

t

L

II.

Version 0

for

'It

= 3 or n

~

5.

7

Romanian Problem Book

File: b75-77

Version 0

75.12 (A 7). Determine the realnumbers a,'b,c,d for which m~x(a, b

+ c + d) =

max(b, a + c + d) = max(c, a

+ b + d)

= max(d, a

+ b + c) =

1.

State and solve the analogous problem for n numbers. Solution. Clearly, none of the four numbers is greater than 1. If at least three of the numbers, say a, b, c, are equal to 1 then n:rax(d, a + b + c) = 3 =I=- 1. if two of these numbers are equal to 1, for instance a, b then c and d are less than 1, and a +b+d

= a + b + c = 1,

hence c = d = -1. We obtain the solution (11, -1, -1) and its other five permutations. If exactly one of the numbers is 1, say a, then b, c, dare all less than 1, and a

+ c + d = a + b+ d = a + b+ c = .

1,

so b = c = d = O. This yields the solution (1,0,0,0) and its other three permutations. If all the numbers are less than 1 then b+c+d=a+c+d=a+b+d=a+b+c= 1.

Adding these equations, we obtain 3( a + b + c + d) = 4, and so (~, ~, ~, ~). Extension. For n ~ 3, determine the real numbers aI, a2, ... ,an such that

for each k

= 1,2, ... , n,

75.13 (NT2). Find a polynomial, P(n), with integer coefficients, such that P(n) is divisible by 33 for any positive integer n. (i

L

+ 4n

Solution. 'Write

for any positive integer '11. Let Q(n) = -1 - 3n - gn(r~-l). Then Q(1'i) + 4 n = 0 (mod 3 3 ) . Considering the poly­ nomial P( /I,) = 28Q( n), we obtain a polynomial with integer coefficients such that P(n)

for any positive integer

+ 4 = 27Q(n) + [Q(n) + 4 == 11

H

]

0 (mod 33 ) ,

ri,

75.14 (C 1). If a, b, c are the 'lengths of the sides of a triangle with perimeter 6 and A, B, C the measures, in radians, of its angles, prove that

27r ::; aA

+ bB + cC < 37r. 8

Ii

I'

Romanian Problem Book

File: b75-77

Version 0

Solution. More generally, we will prove that

1r

-3< Indeed, the triangle inequality a

aA + bB + cC a+b+c

< b + c can be aA . a+b+c

tt

<-. 2

(1)

written as 2a

< a.t- b + c, hence

A <-. 2

Adding up this and the analogous inequalities for Band C, we obtain the right-hand side of (1). To prove the left-hand side, observe th~t a :S b if and .only if A ~ B. Thus one always has (a - b)(A - B) 2: 0, and, similarly, (b - c)(B - C) ~·O, (c - a)(C - A) 2: O. Then i

L

(u - b)(A - B)

Since A

+ B + C = zr , the latter

+ (b -

c)(B - C)

+ (c -

a)(C - A) 2:

o.

is easily transformed to the form

a(3A - 1r)

+ b(3B -

1r)

+ c(3C -

1r) 2: 0,

,

Ii

II

which is clearly equivalent to the left-hand side of (1). 75.15 (PG2). Consider the lines f 1 and f 2 which pass through a point, A. A variable circle, 0, which contains A, intersects, for the second time, the lines f 1 and f 2 at Band C. Let .M and .TV denote the midpoints of the arcs ACE and ABC, respectively; 0 1 the circle through A which is tangent to BM at Band O 2 the circle through A which is tangent to C N at C. The circles 0 1 and O 2 intersect again at T. Find the locus of T. Solution. One distinguishes four cases according as the circle 0 intersects f 1 and f 2 in the region I, II, III, or IV. Without loss of generality, one may assume that this occurs in region 1. There are figures missing here in .the original.

,

L

The circle 0 is tangent to B.M at B, so I..MB0 1 = 90°, and since 0 1 belongs to the perpendicular bisector of AB, it follows that 0 1 is the opposite diametral point of M in the circle O. Similarly, O 2 is the opposite diametral point of N. Since 00 1 ..L AB and 00 2 ..L AC, it follows that 1..0 100 2 = 180° - I..BAC, hence 1..01020 = I..A/2. But the line of centers of two circles is perpendicular to their common chord, so 0 102 ..L AT. And since 0 102 ..LAC, it follows that I.. CAT = 1..01 0 20 = I..A/2. Therefore T belongs to one of the two bisectors of the angles formed by f 1 and f 2 . Conversely, one can prove that any point situated on one of the two bisectors of the angles at A, except for A itself, is the intersection of some circles 0 1 and O 2 with the given property. In conclusion, the locus of T consists of the two bisectors of the angles formed by f 1 and £2, minus their intersection A.

9

Romanian Problem Book

File: b75-77

Version 0

75. 16 (A 8) . Let n be an integer greater' than 1. Prove that there is no irrational number a such that

:Ja+ va

2

-

1+

Va - Va

2

-

1

is rational. Solution. We will prove by induction that if x + l/x is rational then x n + l/x n is rational for any positive integer n. This clearly holds for n = 1. Assuming it true for 1 ~ k ~ n - 1 and applying the identity

xn

+ ~n x

= (x

+ 2:.) X

(x n-1 + _n 11 ) _ (xn-2 x

-

+ _ 1 ), X n-2

we deduce that the statement is also true for k = n. This completes the induction. Assume now that there exists an irrational number a such that

Va + J a 2

is rational. Setting

.7:

=

xn

Va + Ja2 +~ :r n

=

-

1+

Va - va

2

-

1

1, we obtain from above that

(a + Va

2 -

1) +

(a - J a

2 -

1) =

2a

is rational, a contradiction.

r

L

75.17 (C 2). Let 5 be a set with S elements and M a set with the largest number of 4-element subsets of 5, such that, if A and B are distinct parts of M, then An B has at most 2 elements. How many elements does M have? Let JII! = {51, 52, ... , 5 n } and Sf, 52"'" S'4n be the 3-element subsets of 5 1,52, ... ,5n . By hypothesis, 5f, 52" .. ,5' 4n are pairwise distinct. Their number can­ not exceed (~) = 56, the number of 3-element subsets of M. Hence 4n ~ 56, i. e. n ~ 14. For 5 = {1,2, ... ,S}, the set consisting of {1,2,3,4},.{1,2,5,6}, {1,2, 7,8}, {3,4,5,6}, {3,4, 7,8}, {5,6, 7,8}, {1,3,5, 7}, {1,3,6,8}, {1,4,5,8}, {1,4,6, 7}, {2,4,6,8}, {2,4,5, 7}, {2, 5, 6, I}, {2. :3, 5. 8} has the desired properties. Solution.

75. 18 (C 3). Let

,1:1, £2,"

X1X2 Prove that

'/1

. ,X n

E {-I, 1} be such that

+ X2X3 + ... + Xn-1Xn + XnXl = O.

is divisible by 4.

\

Solution. Each of the n terms on the left-hand side of the given equality is either 1 or -1. Let k be the number of -1 'so The remaining n - k terms are 1's, and since the sum of all terms is 0, we must have k = n - k, so n = 2k. Moreover,

so k has to be even. Therefore n, which is twice k, is divisible by 4.

10

Romanian Problem Book

File: b75-77

Version 0

75. 19 (P G 3) . Consi del' a circle of radius 1 and the points Al , A 2 , ... ,An in its plane. Prove that the circle contains a point, P, such that

...

PAl

+ P A 2 + ... + P An

~

n,

-

Solution. Consider any point Po on the given circle, different from AI, A 2 , • • • ,An. If POA 1 + PoA 2 + ... + PoA n ~ n, we are done. If not, one has

(1) Call PI the opposite diametral point of Po on the circle. From the triangle inequality,

so

n

n

k=l

k=l

L POAk + L PIAk ~ 2n. Hence, by (1), PI Al erty.

+ P I .42 + ... + PI An

~

n, and, therefore, PI has the required prop­

75.20 (PG4). Give an example of two noncongruent quadrilaterals which have the angles, respectively, congruent, the diagonals, respectively, congruent, and equal perime­ ters.

~

Solution. Consider an isosceles trapezoid, ABCD, whose diagonals have length 1, and whose angles at the base are 30°. Let A' and B' be the feet of the altitudes from A and B, respectively, and set BB' = x. We get B'C' = xV3, BC = 2x, DB' = )1- x 2 , so AB = A' B' = )1 - x2 - xV3. The perimeter of the trapezoid is p(x) = 4x + 2)1 - x 2 . We will show that there exist XI,X2 E (0,1), Xl i= X2, such that p(xd = P(X2), i. e. that p is not one-to-one in (0, 1). Set Xl = sina, a E (0, f), and X2 = sinb, bE (0, ~), b =1= a. Then p(xd = P(X2) is equiv­ alent to 4 sin a + 2 cos a = 4 sin b + 2 cos b, which, after standard trig manipulations, trans­ lates into tan = 2. Notice that 2 tan- 1 2 E (~, 7l"). Considering ,

arb

~1 .•. •.

Ii

.r} = sina

and

X2

= sin(2tan- 1 2 -

a),

for some a E (0, I)' we obtain two quadrilaterals (even trapezoids) which satisfy the stated conclitions.

75.21 (C4). Prove that any polynomial with real coefficients can be written as the difference of some two increasing polynomial functions (over the reals). Solution. Let P(x) = ao + alX + ... + anx n. Then

11

Romanian Problem Book where M and if Ixl

File: b75-77

Version 0

> max(/all, 2Ia21, nlanl). Note that 'if Ixl ~ 1 then 1 + Ixl + '" + !xn-Il > 1 then 1 + Ixl + + Ixn-Il < nx 2n. Hence, for any real number x, IP'(x) < Mn(x

~ n,

+ x 2n )j.

Consider the polynomials

Pdx) = P(x)

+ Nfn(x + X 2n+1),

Vve have P(.r) = PI (1') - P2(.t'). Also, PI and P2 are increasing functions, because

P;(x)

= P'(x) + Nfn(l + (2n + 1)x 2n) 2:: P'(x) + Mn(l + x 2n) > 0

and P~(x) = 1\([n(1

+ (2n + 1)x 2n) > 0

for any x E R. 75.22 (PG5). Prove that among any nine points situated in the interior of a square of side 1, there are three which form a triangle of area no more than l/S. Solution. Consider the line segment joining the midpoints of the two pairs of opposite sides of the square. They divide it into four congruent smaller squares. By the pigeonhole principle, one of these contains at least three of he given points, say A, B, C. One of the parallels through A, B, C to the sides of the smaller square will intersect the opposite side of 6ABC. Assume this is the parallel through A. Let it meet BC at A', and let B', C' be the projections of B, C onto AA', respectively. Then ,( BB , + C C') ABC = ABA , + ACA ,=1 -AA 2

.:

< -1 . -1 . -1 - 2 2 2

1

= ­ S'

and the claim follows. 75.23 (C 5). Prove that the equation

admits integer solutions if and only if n = 4. Solution. For n = 4, the equation admits integer solutions, for example (1,1,0,0). One easily checks that there are no solutions for n = 1,2,3, so let us assumethat n 2:: 5. Write the equation as follows: ') ? ( (;fl-:r2t+(:rl-;T3t+···+ XI-X n)2 + ( X2-x3 )2 + ...

+ ( xn-l-x n )2 =n.

(1)

~

Each unknown occurs n - 1 times in the left-hand side of (1), and out of the G) terms, at most n are nonzero. Hence at least n terms are 0, and since (~) - n > (n;2) for n 2:: 5, there are at least n - 1 unknowns appearing in zero terms.

~";"'.'

12

II

L

G) -

Romanian Problem Book

File: b75-77

Version 0

On the other hand, assume that each of the numbers Xl, X2, ... ,X n appears in a zero term. Then ;1:1 = X2 = ... = :Tn , and (Xl,X2,'" ,x n) is not a solution of (1). We in­ fer fro~p here that all the unknowns except one are equal. If Xl = X2 = ... = Xn-l = X and

Xn

i=

X,

(1) reduces to (11, -

Vn~l <

surd (because 1

<

if and only if

= 4.

11,

l)(x n -

x)2

=

Hence

11,.

IX n -

xl =

Vn~l'

which is ab­

2). In conclusion, the given equation admits integer solutions

.

­

75.24 (A 9). Let a1, a2, . . . ,an be real numbers. Determine the real numbers Xl, X2, Xl :::; X2 :::; ... :::; X n, such that max lak - xkl

... ,xn,1

l$k$n

~ ~ii

•

is minimized. Solution. Consider any nondecreasing real number sequence Xl, X2, ... ,Xk and set .M = max- $/.;$11 la/.; - Xk I. Then ak - NI :::; Xk :::; ak + M for k = 1,2, ... ,11" and if i < i, we obtain a, - 111 :::; Xi :::; Xj :::; aj + M. Thus M ~ ai~aj whenever 1 :::; i < j ::; 11" so

M > -

a,>

Ii

L fl.:.

It

l

max

a' - a' l

l$i<j$n

2

J

= Mo.

(1)

'''.Te will show that .Mo is the required minimum. All that remains is to find real num­ bers X'l, X2, ...• X: n such that Xl :::; X2 ::; ..• ::; X n and maXl$k$n lak - Xk I :::; Mo. To do this, observe that the definition of kIo implies ai - aj ::; 2Mo for any i, j, i < j. Then max{ aI, a2, ... ,ak} - ak :::; 21v[0 for each k = 1,2, ... ,11" which can be written as

This means that

Thus. setting

Xk

= -lvIo + max{al,a2,'"

,ad, we have Xl::; X2:::;'"

:::;,x n and

~ The proof is complete. 75 25 (SG4). On the edges of a tetrahedron, A IA 2A3A4 , considervsorne points, Bij, B i j E AjA j , i,j E {I, 2, 3, 4}. Prove that he spheres circumscribed about the four tetrahe­ dra AIB12B13B14, A2B12B23B24, A3B13B23B34' A4Bl4B24B34 have a common point. Solution. This is a three-dimensional variant of the following theorem from plane geometry: e .

Let AI. Bs ; C l be points on the sides BC, CA, AB of the triangle ABC, respec­ tively. Then the circumcircles of the triangles ABCI, BCA I, CAB I have a common point. 13

Romanian Problem Book

File: b75-77

Version 0

Indeed, let the circles ABlC l and BClA I meet again at P. For definiteness, assume that P is interior to 6ABC. From the cyclic quadrilaterals ABIPC l and BAlPC l we have LfbPCl = 1800 - LA, LClPA l = 180 0 - LB, so LAIP B, = 360

0 -

(LBlPC l

+ LCIPAd =

LA + LB = 180

0 -

LC.

The latter means that Al C B 1 P is also cyclic, and the proof is complete.

-

To prove the main result, denote by S, the sphere through Ai, Bi], Bik' Bil (assuming {i, j, k, I} = {1, 2, 3, 4}). Let Cijk be the intersection of 51 with the plane AiAjAk. Consider also {Dij} = 5i n 5j, {Md = Cjkl n Cn, n Cu», and let I be an inversion with center AI. The images I(C1ij) are lines, dij, and since Al ¢ Dli' the images I(DIi) = Wi are circles. The inversion is a bijection, therefore d ij and Wi lie in PI; also, {I(B l i)} = dij n dik nWi and {I(A1il} = dj k n Wj n Wk, {i,), k} = {2, 3, 4}. By the statement proved above, we con­ clude that the circles wz, W3, W4 have a common point P. Hence D 12 n D 13 n D 14 = Q, where Q = I-I (P). Thus (51 n 52) n (51 n 53) n (51 n 54) = Q, i. e. the spheres 51, 52, S3, S4 have a point in common. 75. 26 (C 6). Prove that among .any ten consecutive positive integers, there exists at least one which is relatively prime with any of the other nine.

,

i1

Solution. Our array of ten consecutive positive integers contains five odd numbers. Among them, there are at most two which are divisible by 3, one multiple of 5, and at most one multiple of 7. Hence, at least one of these five odds is note divisible by 3,5,7 (and, of course, by 2). Call this number m, and suppose it is not relatively prime with any of the other nine. Then the array contains a number n such that gcd( m, n) = d > 1. The difference m - n is then divisible by d, and since 1m - nl ::; 9, its divisor d can only be 2, 3, 5 or 7. None of these can occur since, on the other hand, d divides m-a contradiction. 75.27 (C 7). Consider a partition of the plane into' congruent equilateral triangles.

Does there exist a square whose vertices are all vertices of these triangles? Solution. Assume that the equilateral triangles are of side length 1. Consider a coordinate system whose x-axis lies on the line containing the side of a certain triangle. Let 1V[ and N be any vertices of the equilateral triangles of the partition. Their z- and ycoordinates differ by numbers of the form ~ and for some integers k and e. Then the distance between any two vertices of the grid has the form! vu 2 + 3v 2 with u, v integers. Now, if there is a square satisfying the hypothesis then certain integers a, b, c, d should satisfy the equality (1)

If

We will prove that this is impossible by observing that 2 enters the prime factorization of any number u z + 3v 2 with an even power. (This implies that (1) cannot hold.) Indeed, let u = 2'c p , v = 2Y q , where p, q are odd. If x =f:. y then u 2 + 3v 2 is the product of 2m in (x ,y) and an odd number, so we are done. And if x = y, we obtain

+ 3v 2 = 22 x [p 2 + 3q 2 ] . The square of each odd number is 1 modulo 8, so p Z + 3q 2 = 4 (mod 8). This implies that u 2 + 3v 2 is divisible by 22 x + 2 but not by 2 2 x + 3 , and theclaim is proven. u2

14

File: b75-77

Romanian Problem Book

Version 0

Thus, the answer to the question is negative. ' ,

75.28 (C8). Prove that if the binomial coefficient prime, ~en 'It ;::: pili.

G)

is divisible by p'"; where p is a

Solution. The exponent of a prime p in the factorizatio~ of n! into primes is L:i2::1

l;· J,

therefore the exponent of p in the factorization of (~) is' E(p) =

~

(l; J -l:, J -l

n ;. k

J) .

If G) is divisible by pm then E(p) ;::: m. Since the sum in E(p) has a finite number of terms, let the rthe term be the last nonzero one. Then

l;: J l;J l +

>

n; k

J'

so n ;:::p". It is known that for any real z , y. So

_, <1' Ih.',·..

II

which means that E(p) :S 1'. We conclude that r ;::: E(p) ;::: m, and so n

~

pr ;::: pm.

75.29 (A 10). Consider a polynomial P with integer coefficients and some distinct integers aI, a2,'" ,an' Prove that if there exists a permutation a of the set {I, 2, ... , n} such that P(ak) = a(J'(k), k = 1,2, ... , n, then a 0 a is the identity. Solution. The statement is true if a is the identity permutation e. If not, assume on the contrary that o 0 a =1= e. This means that there is a k ~ 3 and k distinct inte­ gers b1 , b2, . . . , bk among aI, a2, ... ,an such that P(b e) = be+l for R = 1,2, ... , k (here and henceforth, the indices are taken modulo k). Now, if P is a polynomial with integer coefficients, and u, v arbitrary distinct integers, thenu- v divides P(u) - P(v). Then be - be+l divides P(b.e) - P(be+l) = be+l - be+2 for R = 1,2, ... ,k. Hence for each I!. = 1,2, ... , k there is an integer qe such that

~ ill

(1) Multiplying out the equalities (1) and simplifying, we get qlq2'" qk = 1. Thus q.e = ±1 for t = 1,2, ... , k. Actually, no qe can be -1, since otherwise (1) yields be = be+2' and 6} , b2 , ... ,b k are distinct by hypothesis. But ql = q2 = ... = qk leads to a contradiction , either. Indeed, in this case,

15

File: b75-77

Romanian Problem Book and the sum of these equal numbers is O. impossible.

Version 0

Then bi = b2 = ... = bk , and this is again

75."'30 (C9). A sloppy tailor uses a machine to cut 120 square patches of side 1 from a 25 x 20 rectangle sheet. Prove that, no matter how he performs the cutting, he can still cut a circular patch of diameter 1 from the remaining material, Solution. For each square, Sk, consider the "rounded square", Rk, obtained from Sk by adding four 1 x ~ rectangles on its sides and four quarter-circles of radius ~ at the corners. The area of R~~ is 1 + 4· ~ + i = 3 + i, k = 1,2, ... ,120. Note that

120 (3

+ ~) < 360 + 30 x 3.2 = 24 x 19.

It then follows from the pigeonhole principle that the rounded rectangles Rk do not cover the 24 x 19 rectangle, whose sides are parallel to those of the original one, at a distance of ~ from them. Any disk of radius ~, centered at one of the uncovered points of the 24 x 19 rectangle, does not have any point in common with the squares Sk. Hence it is contained in the remainin~ material.

75.31 (A 11). Given that the equation ax 2 + bx + c = 0, where a, b, c are integers and a > O. has two distinct zeros in (0,1), prove that a;::: 5 and give an example of such an equation for a = 5. Solution. Let P(x) = a;1·2 + bx + c. The zeros Xl',:C2 of P are in (0,1), so the inte­ gers P(O) and P(l) are nonzero, and hence IP(O)P(I)I;::: 1. Since P(x) = a(x - XI)(X - X2) and a > 0, this can be written as

(1) Now, by the AM-GM inequality, we have x(l - x) ::; and only if x = ~. Then

i

for x E (0,1), with equality if

I

L

x2(1 - X2) ::;

1

4'

(2)

therefore

\

(3)

Note that the inequality is strict since, by hypothesis, Xl and X2 cannot be both equal to ~. Combined with (1), (3) yields a 2 > 16, and since a is a positive integer, we obtain a;::: 5. Since 1(0)f(2) 2:: :2 implies a 2 > 32 and a ;::: 6, the only suitable example for a = 5 is the equation 5a:(:c - 1) + 1 = O.

75.32 (NT3). Let a2 digi ts of a9.

= :2 and

{(1I+1

= (11. + l)U 16

n

for n,

= 2,3, ... ,8.

Find the last two

Romanian Problem Book

File: b75-77

Version 0

Solution. Note first that a6 = 6 as is even since as > 1. Also, 7 = -1 (mod 4) and a7 = 7a 6 == (-lt 6 == 1 (mod 4). A t~vial induction shows that 84 k + 1 8 (mod 10) for each nonnegative k. Then a8 = 8 a 7 == 8 (mod 10), so as = lOR + 8 for some nonnegative integer Z, By the binomial theorem, gas = (10 - Its == -10(10l + 8) + 1 (mod 100),

=

so

ag

== -79 == 21 (mod 100). Therefore, the last two digits of

75.33 (A 12). Prove that for any

Are the conditions

XI.: :::;

Xk

...

ag

are 21.

E [1,2], k = 1,2, .. . ,17"

:2 essential?

Solution. The condition :rk E [1,2] is equivalent standard manipulation. gives

to(Xk -

l)(xk - 2) :::; 0, which, after a

')

;Lh,

+ ~ :::; 3,

k = 1,2, ...

,17,.

XJ.~

,

L

Adding up over k = 1,2, ...

,17"

we obtain

(1)

l

On the other hand, from the AM-GM inequality,

(2)

Clearly (1) and (2) yield the desired result. The conditions :r/.: :::; 2 essential. Indeed, set Then fll(.r)

'" .q. )('" 1)2 = ( {; { ; .q.

11.

3

Xl

= X2 = ... = Xn-l = 1 and X n = X > 2.

. l = x: [(x - 2)17,2 - (x

-' 1)(2x -\Vn

For .r > 2, we have lim .n. -+ 00 In (x) = 00, and therefore j n(x) hence the original inequality is violated.

> a for

17,

+ (x

- 1)2].

sufficiently large;

75.34 (SG5). Consider a pyramid, OABCD, where ABCD is a square, and the projection of 0 on ABCD is its center. Determine the locus of centers of spheres which pass through V and intersect the edges OA, OB, OC, OD at four coplanar points. 17

File: b75-77

Romanian Problem Book

Version 0

Solution. Suppose a sphere with center S passes through 0 and meets the edges OA, DB, OC, OD in the coplanar points A', B', C', D', respectively, We start by proving that A' B' C~ D' is an isosceles trapezoid. Indeed, let P be the center of ABCD, and let P' = A' C' n B' D'. The lines A' C' and B'D' are contained in the planes 0 A' C' and 0 B' D', so P' is contained in their intersection, the line OP. Now imagine rotating 60AC at 90° about OP, so that it lands on 60BD; we then have the following diagram.

r

L

. ~I

I have some difflculties with both the diagram and the argument following it; it is probably Titu who will help. Going back to the main solution, we observe that the locus in question splits into two parts, corresponding to whether A'B' II C'D' or A'D' II B'C'. Suppose that A'B' II C'D'. Let 0 1 , 0:3, O~, 0(3 be the circumcenters of 0 AB, OC D, 0 A' B', OC' D', respectively. 5 must lie 011 the perpendicular bisector of the segments A' B' and C' D', which is the plane 00 10:3. In fact, 5 is the intersection in the plane 00 103 of the perpendiculars to 00 1 at O~ and to 00 3 at 0; . . Now since O~, 0; can lie anywhere along the line segments 00 1 and 00 3 , the locus in this case is the rhombus, whose sides are formed by the perpendiculars to 00 1 at 0 and 0 1 and to 00 3 at 0 and 0 3 . The desired locus is the union of this rhombus with' the rhombus obtained from the other case, which is simply the same figure, rotated about its axis of symmetry OP by 90°.

75.35 (A 13). Prove that every infinite arithmetic progression of positive integers:

a) contains an infinite geometric progression;

b) contains, for any odd n, a geometric progression of length n whose sum of terms is

equal to the sum of some n consecutive terms of the arithmetic progression. Solution. a) Let the first term of the arithmetic progression be a and its common difference d. Consider the set {a(1 + d)n}~=o' It is an infinite geometric progression, and its elements are terms of the given progression, because

is divisible by d.. b) Consider the geometric progression {a(1 metic progression, because a( 1

+ nd)

. l

-

+ nd)i}

a = a

:01.

Its terms are all in the arith­

· L (.n {nd)l n

j=l

)

J

is a multiple of d. The sum of this progression

a(1

+ nd)n nd

a

= -.

t (1~)

nd J=l .

J

18

(nd)j

=a

t .

J=

(~) (nd)j-1 1

J

File: b75-77

Romanian Problem Book is clearly divisible by

So (l(l+~~)n_(t

17"

Version 0

and

= n( a + kcl), where k =

t )=2

(~) (17,d)j-2 ~

17,; 1 for all n.

J

Thus the sum equa.ls

and the proof is complete.

\

I;

~

19