4.36 Shortlisted Problems 1995 601
28. Let F (x)=f(x)− 95 for x ≥ 1. Writing k for m + 95, the given condition
becomes
F (k + F (n)) = F (k)+n, k ≥ 96,n≥ 1. (1)
Thus for x, z ≥ 96 and an arbitrary y we have F (x + y)+z = F (x +
y + F (z)) = F(x + F (F (y)+z)) = F (x)+F (y)+z, and consequently
F (x + y)=F (x)+F (y) whenever x ≥
96. Moreover, since then F (x +
y)+F (96) = F (x + y + 96) = F (x)+F (y + 96) = F (x)+F (y)+F (96)
for any x, y,weobtain
F (x + y)=F (x)+F (y),x,y∈ N. (2)
It follows by induction that F (n)=nc for all n, where F (1) = c.Equation
(1) becomes ck + c
2
n = ck + n, and yields c = 1. Hence F (n)=n and
f(n)=n + 95 for all n.
Finally,

19
k=1
f(k)=96+97+···+ 114 = 1995.
Second solution. First we show that f(n) > 95 for all n. If to the contrary
f(n) ≤ 95, we have f(m)=n + f (m +95− f(n)), so by induction
f(m)=kn+ f(m +k(95− f(n))) ≥ kn for all k, which is impossible. Now
for m>95 we have f(m + f(n)− 95) = n + f (m), and again by induction
f(m + k(f(n) − 95)) = kn + f(m) for all m, n, k. It follows that with n
fixed,
(
∀m) lim
k→∞
f(m + k(f (n)− 95))

3
− b
3
)(a
2
− b
2
) ≥ 0, i.e. a
5
+ b
5
≥
a
2
b
2
(a + b). Hence
ab
a
5
+ b
5
+ ab
≤
ab
a
2
b
2
(a + b)+ab

n
< 0, |a
n
| > |a
1
|,and
p = −a
n
. But then for sufficiently large odd k, −a
k
n
= |a
n
|
k
> (n−1)|a
1
|
k
,
so that a
k
1
+ ···+ a
k
n
≤ (n − 1)|a
1
|
k

2
)···(x−a
n
) ≤

x +
a
1
n − 1

n−1
≤ x
n−1
+x
n−2
a
1
+···+a
n−1
1
. (1)
The last inequality holds because

n−1
r

≤ (n − 1)
r
for all r ≥ 0. Multi-
plying (1) by (x − a

−1

b
2
+ b
−2

b
4
+ b
−4

···

b
2
n−1
+ b
−2
n−1

by induction. Indeed,
a
n+1
a
n
=

a
n

b
b
2
+1
+
b
3
(b
2
+1)(b
4
+1)
+ ···
···+
b
2
n
−1
(b
2
+1)(b
4
+1)...(b
2
n
+1)
.
(1)
Note that
1

+1)···(b
2
k−1
+1)
−
1
(b
2
+1)(b
4
+1)···(b
2
k
+1)
;
hence the right side in (1) equals
1
b

1 −
1
(b
2
+1)(b
4
+1)...(b
2
n
+1)


ln
A
R
j

≤ ln
⎛
⎝
n

j=1
a
j
A
·
A
R
j
⎞
⎠
=lnf(R)=0.
Therefore

n
j=1
a
j
(ln A − j ln R) ≤ 0, which is equivalent to A ln A ≤
B ln R, i.e., A
A

3
P (−1/2) ≤ 7.
Remark. It can be shown that the maximum of 7 is attained only for
P (x)=±(4x
3
− 3x).
6. Let f (x),g(x) be polynomials with integer coefficients such that
f(x)(x +1)
n
+ g(x)(x
n
+1)=k
0
. (∗)
Write n =2
r
m for m odd and note that x
n
+1=(x
2
r
+1)B(x), where
B(x)=x
2
r
(m−1)
− x
2
r
(m−2)

j
= ω
2j−1
for 1 ≤ j ≤ 2
r
.Wehave
604 4 Solutions
(ω
1
+1)(ω
2
+1)···(ω
2
r+1
+1)=2. (2)
From (∗)wealsogetf(ω
j
)(ω
j
+1)
n
= k
0
for j =1, 2,...,2
r
.Since
A = f (ω
1
)f(ω
2

Furthermore, since ω
j
+1 = (ω
1
+1)p
j
(ω
1
) for some polynomial p
j
with integer coefficients, (2) gives (ω
1
+1)
2
r
p(ω
1
)=2, where p(x)=
p
2
(x)···p
2
r
(x) has integer coefficients. But then the polynomial (x +
1)
2
r
p(x) − 2 has a zero x = ω
1
, so it is divisible by its minimal poly-

+1)Q(x)= (x
2
r
+1)Q(x)+(x
2
r
+1)Q(x)B(x)R(x)
=(x +1)
n
p(x)
n
− 2
m
+(x
n
+1)Q(X)R(x).
Therefore (x+1)
n
f(x)+(x
n
+1)g(x)=2
m
for some polynomials f(x),g(x)
with integer coefficients, and k
0
=2
m
.
7. We are given that f(x+ a +b)−f (x+ a)=f(x+ b)− f(x), where a =1/6
and b =1/7. Summing up these equations for x, x+b,...,x+6b we obtain

equation gives us
f(n)=f (ka + i)=f (i)+ka =(n
i
+ k)a.
Besides the zero function, this is the general solution of the given func-
tional equation. To verify this, we plug in m = ka + i, n = la + j and
obtain
f(m + f(n)) = f (ka + i + f(la + j)) = f((k + l + n
j
)a + i)
=(k + l + n
j
+ n
i
)a = f(m)+f(n).
9. From the definition of a(n)weobtain
a(n) − a([n/2]) =

1ifn ≡ 0orn ≡ 3(mod4);
−1ifn ≡ 1orn ≡ 2(mod4).
Let n =
b
k
b
k−1
...b
1
b
0
be the binary representation of n,whereweas-

be chosen in exactly

k
k/2

ways. Thus the number of positive integers
n<2
11
= 2048 with a(n)=0isequalto

0
0

+

2
1

+

4
2

+

6
3

+



,H

be respectively the
centroid of ABC, the centroid
of PBC, and the orthocenter of
PBC. Since the triangles ABC
and PBC have a common circum-
center, from the properties of the
Euler line we get
−−→
HH

=3
−−→
GG

=
−→
AP .ButAQR is exactly the im-
age of PBC under translation by
−→
AP ; hence the orthocenter of AQR
coincides with H.(Remark: This
A
B C
P
E
H
Q

AP
PZ
=
AP · CP
k
,
i.e., XZ =
k·AC·BP
AP·BP·CP
. It follows again that AC/AB = PC/PB.
Third solution. Apply an inversion with center at A and radius r,and
denote by
Q the image of any point Q. Then the given condition becomes
∠
BCP = ∠CBP, i.e., BP = PC.But
PB =
r
2
AP · AB
PB,
so AC/AB = PC/PB.
Remark. Moreover, it follows that the locus of P is an arc of the circle of
Apollonius through C.
4.37 Shortlisted Problems 1996 607
12. It is easy to see that P lies on the segment AC.LetE be the foot of
the altitude BH and Y,Z the midpoints of AC, AB respectively. Draw
the perpendicular HR to FP (R ∈ FP). Since Y is the circumcenter
of FCA,wehave∠FYA = 180
◦
− 2∠A.Also,OF PY is cyclic; hence

Second solution. As before, ∠HFY =90
◦
−∠A, so it suffices to show that
HP ⊥ FY.ThepointsO, F, P, Y lie on a circle, say Ω
1
with center at
the midpoint Q of OP.Furthermore,thepointsF, Y lie on the nine-point
circle Ω of ABC with center at the midpoint N of OH. The segment FY
is the common chord of Ω
1
and Ω, from which we deduce that NQ⊥ FY.
However, NQ HP, and the result follows.
Third solution. Let H

be the point symmetric to H with respect to
AB.ThenH

lies on the circumcircle of ABC. Let the line FP meet
the circumcircle at U, V and meet H

B at P

.SinceOF ⊥ UV, F is the
midpoint of UV. By the butterfly theorem, F is also the midpoint of PP

.
Therefore H

FP


◦
,thepointP escapes to infinity. If
∠A<45
◦
,thepointP appears on the extension of AC over C,and
∠FHP = 180
◦
− ∠A.
13. By the law of cosines applied to CA
1
B
1
,weobtain
A
1
B
2
1
= A
1
C
2
+ B
1
C
2
− A
1
C · B
1

· B
1
C
2
1
· C
1
A
2
1
≥ A
1
B · A
1
C · B
1
A · B
1
C · C
1
A · C
1
B. (1)
Now, the lines AA
1
,BB
1
,CC
1
concur, so by Ceva’s theorem, A

D
Q
EF
P R
S
a
b
c
d
e
f
2BF ≥ (a sin B + f sin C)+(c sin C + d sin B),
and similarly, 2BD ≥ (c sin A + b sin B)+(e sin B + f sin A),
2DF ≥ (e sin C + d sin A)+(a sin A + b sin C).
(1)
Next, we have the following formulas for the considered circumradii:
R
A
=
BF
2sinA
,R
C
=
BD
2sinC
,R
E
=
DF


+ ···
≥
1
2
(a + b + ···)=
P
2
,
with equality if and only if ∠A = ∠B = ∠C = 120
◦
and FB ⊥ BC etc.,
i.e., if and only if the hexagon is regular.
Second solution. Let us construct points A

,C

,E

such that ABA

F ,
CDC

B,andEFE

D are parallelograms. It follows that A

,C


being A

A

and since FA

B
∼
=
BAF, it follows that 2R
A
=
A

A

= x.
A
B
C
D
E
F
A

C

E

A

, CB = C

D = x
c
,
EF = E

D = x
e
,andED = E

F = y
e
. The original inequality we must
prove now becomes
x + y + z ≥ y
a
+ z
a
+ z
c
+ x
c
+ x
e
+ y
e
. (1)
4.37 Shortlisted Problems 1996 609
We now follow and generalize the standard proof of the Erd˝os–Mordell


with respect to the bisector of ∠E

A

C

.LetF
1
and B
1
be the
feet of the perpendiculars from A
1
to A

C

and A

E

, respectively. In that
case, A
1
F
1
= A

F = y

E

A
1
+2S
A

C

A
1
= cz
a
+ ey
a
.
Similarly, cy ≥ ex
c
+ az
c
and ez ≥ ay
e
+ cx
e
.Thus
x + y + z ≥
c
a
z
a

a
c


z
a
+ z
c
2

+

c
a
−
a
c


z
a
− z
c
2

+ ··· .
(2)
Let us set a
1
=

C

E

and hence a
1
/a = c
1
/c = e
1
/e = k.Thus

c
a
−
a
c

e
1
+

e
c
−
c
e

a
1

=0.Equation
(2) reduces to
x + y + z ≥

c
a
+
a
c


z
a
+ z
c
2

+

e
c
+
c
e


x
e
+ x
c

e
.
Equality holds if and only if a = c = e and A

= C

= E

=
center of A

C

E

, i.e., if and only if ABCDEF is regular.
Remark. From the second proof it is evident that the Erd˝os–Mordell in-
equality is a special case of the problem. if P
a
,P
b
,P
c
are the feet of the
perpendiculars from a point P inside ABC to the sides BC, CA, AB,
and P
a
PP
b
P


b
to prove the Erd˝os–Mordell inequality
for ABC and point P .
15. Denote by ABCD and EFGH the two rectangles, where AB = a, BC =
b, EF = c,andFG = d. Obviously, the first rectangle can be placed
within the second one with the angle α between AB and EF if and only
if
a cos α + b sin α ≤ c, a sin α + b cos α ≤ d. (1)
Hence ABCD can be placed within EFGH if and only if there is an
α ∈ [0,π/2] for which (1) holds.
610 4 Solutions
The lines l
1
(ax + by = c)andl
2
(bx + ay = d)andtheaxesx and y bound
aregionR. By (1), the desired placement of the rectangles is possible if
and only if R contains some point (cos α, sin α) of the unit circle centered
at the origin (0, 0). This in turn holds if and only if the intersection point
L of l
1
and l
2
lies outside the unit circle. It is easily computed that L has
coordinates

bd−ac
b
2


= R
2
. Now it is enough to show that 8OA
1
· OB

· OC

≤ R
3
. Thus
we must prove that
λµν ≤
1
8
, where
OA
1
OA
= λ,
OB
1
OB
= µ,
OC
1
OC
= ν. (1)
On the other hand, we have

8
. Hence λµν ≤
1
8
, with equality if and only
if λ = µ = ν =
1
2
. This implies that O is the centroid of ABC,and
consequently, that the triangle is equilateral.
Second solution. In the official solution, the inequality to be proved is
transformed into
cos(A − B)cos(B − C)cos(C − A) ≥ 8cosA cos B cos C.
Since
cos(B−C)
cos A
= −
cos(B−C)
cos(B+C)
=
tan B tan C+1
tan B tan C−1
, the last inequality becomes
(xy +1)(yz +1)(zx+1)≥ 8(xy− 1)(yz− 1)(zx− 1), where we write x, y, z
for tan A, tan B, tan C. Using the relation x + y + z = xyz, we can reduce
this inequality to
(2x + y + z)(x +2y + z)(x + y +2z) ≥ 8(x + y)(y + z)(z + x).
This follows from the AM–GM inequality: 2x+ y + z =(x+ y)+(x + z) ≥
2


=
BC
2sinα

,R
D
=
AD
2sinβ

.
Let ∠B + ∠D = 180
◦
.ThenA, B, C, D are concyclic and trivially R
A
+
R
C
= R
B
+ R
D
.
Let ∠B + ∠D>180
◦
.ThenD lies within the circumcircle of ABC,which
implies that β>β

. Similarly α<α


+ R
C
>R
B
+ R
D
.
18. We first prove the result in the simplest case. Given a 2-gon ABA and a
point O,leta, b, c, h denote OA, OB, AB, and the distance of O from AB.
Then D = a + b, P =2c,andH =2h, so we should show that
(a + b)
2
≥ 4h
2
+ c
2
. (1)
Indeed, let l be the line through O parallel to AB,andD the point
symmetric to B with respect to l.Then(a + b)
2
=(OA + OB)
2
=(OA +
OD)
2
≥ AD
2
= c
2
+4h

). By the case proved above, we have for
each i, d
i
+d
i+1
≥

4h
2
i
+ p
2
i
. Summing these inequalities for i =1,...,n
and squaring, we obtain
4D
2
≥


n
i=1

4h
2
i
+ p
2
i


. But this follows immediately from the Minkowski inequality.
Equality holds if and only if it holds in (1) and in the Minkowski inequality,
i.e., if and only if d
1
= ··· = d
n
and h
1
/p
1
= ··· = h
n
/p
n
. This means
that F is inscribed in a circle with center at O and p
1
= ···= p
n
,soF is
a regular polygon and O its center.
19. It is easy to check that after 4 steps we will have all a, b, c, d even. Thus
|ab−cd|,|ac−bd|,|ad−bc| remain divisible by 4, and clearly are not prime.
The answer is no.
Second solution. After one step we have a + b + c + d =0.Thenac− bd =
ac + b(a + b + c)=(a + b)(b + c)etc.,so
|ab − cd|·|ac− bd|·|ad− bc| =(a + b)
2
(a + c)
2

2
).
In particular, 481 = 13 · 37 | x
4
+ y
4
. We have the following lemma.
Lemma. Suppose that p | x
4
+ y
4
,wherex, y ∈ Z and p is an odd prime,
where p ≡ 1(mod8).Thenp | x and p | y.
Proof. Since p | x
8
− y
8
and by Fermat’s theorem p | x
p−1
− y
p−1
,we
deduce that p | x
d
− y
d
,whered =(p− 1, 8). But d =8,sod | 4. Thus
p | x
4
− y

2
±···±n
2
.Since
(n +1)
2
− (n +2)
2
− (n +3)
2
+(n +4)
2
=4,
we observe that if our claim is true for c,thenitisalsotrueforc± 4.
Thus it remains only to prove the claim for c =0, 1, 2, 3. But one
immediately finds 1 = 1
2
,2=−1
2
− 2
2
− 3
2
+4
2
,and3=−1
2
+2
2
,

2
+2
2
+ ···+19
2
=
2470 = 1996 + 2 · 237; hence it is enough to write 237 as a sum of
distinct squares. Since 237 = 14
2
+5
2
+4
2
, we finally obtain
1996 = 1
2
+2
2
+3
2
− 4
2
− 5
2
+6
2
+···+13
2
− 14
2

2
ab
≥ 2, we obtain α + β ≥ αβ + 2, or equivalently
4.37 Shortlisted Problems 1996 613
(α − 1)(β − 1) ≤−1. But α ≥ 1, and therefore β = 0. It follows that
a>b
2
, i.e., a = b
2
+ c for some c>0. Now the given equation becomes
b
3
+2bc +

c
2
b

=

b
4
+2b
2
c+b
2
+c
2
b
3

b
2
(c+1)+c
2
b
3
+bc
≥ (c − 1)b. This simplifies to
c
2
(b
2
− 1) + b
2
(c(b
2
− 2)− (b
2
+1))≤ 0. (2)
Since c ≥ 2andb
2
− 2 ≥ 0, the only possibility is b = 2. But then (2)
becomes 3c
2
+8c− 20 ≤ 0, which does not hold for c ≥ 2.
Hence the only solutions are (n, n
2
+1)and(n
2
+1,n), n ∈ N.

.
It remains to give an example of such a function g.LetP
1
,P
2
,Q
1
,Q
2
be
thesetsofprimesoftheforms3k+1, 3k+2, 4k+1, and 4k+3, respectively.
It is well known that these sets are infinite. Take any bijection h from
P
1
∪ P
2
onto Q
1
∪ Q
2
that maps P
1
bijectively onto Q
1
and P
2
bijectively
onto Q
2
. Now define g as follows: g(1) = 1, and for n = p

where a, b ∈ Z and a
2
+ b
2
= r.
614 4 Solutions
(a) If r is even, then a + b is even whenever a
2
+ b
2
= r (a, b ∈ Z). Thus
the parity of x + y does not change after each move, so we cannot
reach (19, 0) from (0, 0).
If 3 | r,thenbotha and b are divisible by 3, so if a point (x, y)can
be reached from (0, 0),wemusthave3| x. Since 3  19, we cannot get
to (19, 0).
(b) We have r =73=8
2
+3
2
,soeachmoveiseither(x, y) → (x±8,y±3)
or (x, y) → (x ± 3,y± 8). One possible solution is shown in Fig. 1.
(c) We have 97 = 9
2
+4
2
. Let us partition A as B∪C,whereB =
{(x, y) ∈A|4 ≤ y ≤ 7}. It is easily seen that moves of the type
(x, y) → (x ± 9,y± 4) always take us from the set B to C and vice
versa, while the moves (x, y) → (x± 4,y± 9) always take us from C to

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
◦·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
◦·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
◦·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
◦·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
◦·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
◦·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·

•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•

n
possible colorings.
It follows that the total number of considered colorings is (2
n
− 2) + 2
n
=
2
n+1
− 2.
26. Denote the required maximum size by M
k
(m, n). If m<
n(n+1)
2
,then
trivially M = k, so from now on we assume that m ≥
n(n+1)
2
.
First we give a lower bound for M.Letr = r
k
(m, n) be the largest integer
such that r +(r +1)+··· +(r + n − 1) ≤ m. This is equivalent to
nr ≤ m −
n(n−1)
2
≤ n(r +1),sor =

m

m−1
2

at least one of i and m − i must be excluded from S.Nowlet
us assume that n>2 and that the result holds for n − 1. Suppose that
S ⊆{1, 2,...,k} does not contain n distinct elements with the sum m,
and let x be the smallest element of S. We may assume that x ≤ r
k
(m, n),
because otherwise the statement is clear. Consider the set S

= {y − x |
y ∈ S, y = x}.ThenS

is a subset of {1, 2,...,k− x} no n − 1elements
of which have the sum m − nx. Also, it is easily checked that n − 1 ≤
m − nx − 1 ≤ k − x, so we may apply the induction hypothesis, which
yields that
|S|≤1+k − x − r
k
(m− nx, n − 1) = k −

m − x
n − 1
−
n
2

. (2)
On the other hand,

a contradiction.
Suppose that C is a quadrilateral, say ABCD, with E lying within
ABCD. Then the triangles ABE,BCE, CDE,DAE contain some points
P, Q, R, S of B that form two disjoint triangles. It follows that there are
two points of A inside ABCD, which is a contradiction.
Finally, suppose that C is a triangle with two points of A inside. Then C is
the union of five disjoint triangles with vertices in A, so there are at least
five points of B inside C
. These five points make at least three disjoint
triangles containing three points of A. This is again a contradiction.
It follows that no such sets A,B exist.
28. Note that w.l.o.g., we can assume that p and q are coprime. Indeed, oth-
erwise it suffices to consider the problem in which all x
i
’s and p, q are
divided by gcd(p, q).
616 4 Solutions
Let k, l be the number of indices i with x
i+1
− x
i
= p and the number
of those i with x
i+1
− x
i
= −q (0 ≤ i<n). From x
0
= x
n

y
i
is 0 then all y
i
’s are of the same sign. But this is in contradiction with
the relation y
0
+ y
p+q
+ ···+ y
n−p−q
= x
n
− x
0
= 0. Consequently some
y
i
is zero, as claimed.
Second solution. As before we assume (p, q) = 1. Let us define a sequence
of points A
i
(y
i
,z
i
)(i =0, 1,...,n)inN
2
0
inductively as follows. Set A

i
for all i.Sincex
n
= 0, it follows that (z
n
,y
n
)=(kq, kp), k ∈ N.Since
y
n
+ z
n
= n>p+ q, it follows that k>1. We observe that x
i
= x
j
if
and only if A
i
A
j
 A
0
A
n
. We shall show that such i, j with i<jand
(i, j) =(0,n)mustexist.
If L meets A
0
A

00
.
Hence L
00
and L

dd
have some point X = A
0
in common. The translate Y
of point X for the vector d(p, q) belongs to L and satisfies XY  A
0
A
n
.
29. Let the squares be indexed serially by the integers: ...,−1, 0, 1, 2,... .
When a bean is moved from i to i + 1 or from i +1 to i for the first
time, we may assign the index i to it. Thereafter, whenever some bean
is moved in the opposite direction, we shall assume that it is exactly the
one marked by i, and so on. Thus, each pair of neighboring squares has a
bean stuck between it, and since the number of beans is finite, there are
only finitely pairs of neighboring squares, and thus finitely many squares
on which moves are made. Thus we may assume w.l.o.g. that all moves
occur between 0 and l ∈ N and that all beans exist at all times within
[0,l].
Defining b
i
to be the number of beans in the ith cell (i ∈ Z)andb the
total number of beans, we define the semi-invariant S =


i−1
+ x
i+1
− 2x
i
∈{0, 1} . (1)
Thus it is enough to show that given b
i
≥ 0, the sequence {x
i
}
i∈Z
of
nonnegative integers satisfying (1) is unique.
Suppose the assertion is false, i.e., that there exists at least one sequence
b
i
≥ 0 for which there exist distinct sequences {x
i
} and {x

i
} satisfying (1).
We may choose such a {b
i
} for which min{

i∈Z
x
i


j
decreased
by 1 also satisfy (1) for a sequence {b
i
} where b
j−1
,b
j
,b
j+1
is replaced
with b
j−1
+1,b
j
− 2,b
j+1
+ 1. This contradicts the assumption of minimal
min{

i∈Z
x
i
,

i∈Z
x

i

2
f(x), and since g is a bijection,
we obtain fg(x)=gf(x), i.e., x ∈ T .
x ∈ T .Thenfg(x)=gf(x), so g
2
f(x)=gfg(x). It follows that
f
3
(x)=g
2
f(x)=gfg(x)=fg
2
(x), and since f is a bijection, we
obtain x ∈ S.
Hence x ∈ S∩T in both cases. Similarly, f (x) ∈ T and g(x) ∈ S again
imply x ∈ S ∩ T .
Lemma 2. f(S ∩ T )=g(S ∩ T )=S ∩ T .
Proof. By symmetry, it is enough to prove f (S ∩ T )=S ∩ T ,orinother
words that f
−1
(S∩T )=S∩ T .SinceS∩ T is finite, this is equivalent
to f (S ∩ T ) ⊆ S ∩ T .
Let f (x) ∈ S ∩ T .Thenifg(x) ∈ S (since f(x) ∈ T ), Lemma 1 gives
x ∈ S ∩ T ; similarly, if g(x) ∈ T , then by Lemma 1, x ∈ S ∩ T .
Now we return to the problem. Assume that f (x) ∈ S.Ifg(x) ∈ S,then
g(x) ∈ T ,sofromLemma1wededucethatx ∈ S ∩ T . Then Lemma 2
claims that g(x)
∈ S ∩ T too, a contradiction. Analogously, from g(x) ∈ S
we are led to f(x) ∈ S. This finishes the proof.
618 4 Solutions

,wehavef(m, n) ≤
1
2
+ |w(EAC) − b(EAC)|≤
1
2
+ S(EAC)=
1
2
+
n−1
2
=
n
2
. Therefore f (m, n) ≤
1
2
min(m, n).
(c) Let us calculate f(m, n)form =2k+1, n =2k, k ∈ N.WithE defined
as in (b), we have BE = BC =2k. If the square at B is w.l.o.g. white,
CE passes only through black squares. The white part of EAC then
consists of 2k similar triangles with areas
1
2
i
2k
i
2k+1
=

,...,1, 2,...,x
n
).
Also, for any two sequences A, B we denote their concatenation by AB.
It clearly holds that
AB = A B. The sequences R
1
,R
2
,... are given by
R
1
= (1) and R
n
= R
n−1
(n)forn>1.
We consider the family of sequences Q
ni
for n, i ∈ N, i ≤ n, defined as
follows:
Q
n1
=(1),Q
nn
=(n), and Q
ni
= Q
n−1,i−1
Q

= Q
n−1,i
. This follows by induction, because Q
ni
=
Q
n−1,i−1
Q
n−1,i
= Q
n−2,i−1
Q
n−2,i
= Q
n−1,i
for n ≥ 3, i ≥ 2 (the cases
i =1andn =1, 2 are trivial). Now R
1
= Q
11
and
R
n
= R
n−1
(n)=Q
n−1,1
...Q
n−1,n−1
(n)=Q

one of them is 1.
3. (a) For n = 4, consider a convex quadrilateral ABCD in which AB =
BC = AC = BD and AD = DC, and take the vectors
−−→
AB,
−−→
BC,
−−→
CD,
−−→
DA.Forn = 5, take the vectors
−−→
AB,
−−→
BC,
−−→
CD,
−−→
DE,
−→
EA for any
regular pentagon ABCDE.
(b) Let us draw the vectors of V as originated from the same point O.
Consider any maximal subset B ⊂ V , and denote by u the sum of all
vectors from B.Ifl is the line through O perpendicular to u,thenB
contains exactly those vectors from V that lie on the same side of l as
u does, and no others. Indeed, if any v ∈ B lies on the same side of l
,
then |u + v|≥|u|; similarly, if some v ∈ B lies on the other side of l,
then |u − v|≥|u|.

7431
⎤
⎥
⎥
⎦
.
620 4 Solutions
This construction can be generalized. Suppose that we are given an
n × n coveralls matrix A
n
.LetB
n
be the matrix obtained from A
n
by adding 2n to each entry, and C
n
the matrix obtained from B
n
by
replacing each diagonal entry (equal to 2n + 1 by induction) with 2n.
Then the matrix
A
2n
=

A
n
B
n
C

is a desired coveralls matrix.
It follows that we can find a coveralls matrix whenever n is a power
of 2.
Second solution for part b. We construct a coveralls matrix explicitly
for n =2
k
. We consider the coordinates/cells of the matrix elements
modulo n throughout the solution. We define the i-diagonal (0 ≤ i<
n) to be the set of cells of the form (j, j + i), for all j.Wenotethat
each cross contains exactly one cell from the 0-diagonal (the main
diagonal) and two cells from each i-diagonal. For two cells within an
i diagonal, x and y, we define x and y to be related if there exists a
cross containing both x and y. Evidently, for every cell x not on the
0-diagonal there are exactly two other cells related to it. The relation
thus breaks up each i-diagonal (i>0) into cycles of length larger
than 1. Due to the diagonal translational symmetry (modulo n), all
the cycles within a given i-diagonal must be of equal length and thus
of an even length, since n =2
k
.
The construction of a coveralls matrix is now obvious. We select a
number, say 1, to place on all the cells of the 0-diagonal. We pair
up the remaining numbers and assign each pair to an i-diagonal, say
(2i, 2i+1). Going along each cycle within the i-diagonal we alternately
assign values of 2i and 2i + 1. Since the cycle has an even length, a
cell will be related only to a cell of a different number, and hence each
cross will contain both 2i and 2i +1.
5. We shall prove first the 2-dimensional analogue:
Lemma. GivenanequilateraltriangleABC and two points M, N on
the sides AB and AC respectively, there exists a triangle with sides

n−1
.
(b) Suppose w.l.o.g. that gcd(c, a) = 1. We look for a solution of the form
x = p
m
,y= p
n
,z= qp
r
, p,q,m,n,r∈ N.
Then x
a
+ y
b
= p
ma
+ p
nb
and z
c
= q
c
p
rc
, and we see that it is enough
to assume ma − 1=nb = rc (there are infinitely many such triples
(m, n, r)) and q
c
= p +1.
7. Let us set AC = a, CE = b, EA = c. Applying Ptolemy’s inequality for

a
b + c
+
b
c + a
+
c
a + b
.
Hence it is enough to prove that
a
b + c
+
b
c + a
+
c
a + b
≥
3
2
. (1)
If we now substitute x = b + c, y = c + a, z = a + b and S = a + b + c the
inequality (1) becomes equivalent to S(1/x +1/y +1/y)− 3 ≥ 3/2which
follows immediately form 1/x +1/y +1/z ≥ 9/(x + y + z)=9/(2S).
Equality occurs if it holds in Ptolemy’s inequalities and also a = b = c.
The former happens if and only if the hexagon is cyclic. Hence the only
case of equality is when ABCDEF is regular.
8. (a) Denote by b and c the perpendicular bisectors of AB and AC re-
spectively. If w.l.o.g. b and AD do not intersect (are parallel), then

and by M
i
the midpoint of the arc A
i+1
A
i+2
that
does not contain A
i
.Firstwehave
that O
i+1
O
i+2
is the perpendicular
bisector of IB
i
, and thus it contains
the circumcenter R
i
of A
i
B
i
I.Ad-
ditionally, it is easy to show that
T
i+1
A
i

A
2
A
3
I
B
1
B
2
B
3
R
3
R
1
Now, the lines T
1
O
1
,T
2
O
2
,T
3
O
3
are concurrent at I. By Desargues’s the-
orem, the points of intersection of O
i+1

while the image of the line A
i+1
A
i+2
is
the circle IA

i+1
A

i+2
that is tangent to B

i
B

i+2
,andB

i
B

i+2
.Thesethree
circles have equal radii, so their centers P
1
,P
2
,P
3

B

2
B

3
. It follows that A

1
B

1
,A

2
B

2
,A

3
B

3
are concurrent
at some point J

, i.e., that the circles A
i
B

,...,−a
k
.Then
P (x) can be factored as
P (x)=C(x + a
1
)···(x + a
k
)(x
2
− b
1
x + c
1
)···(x
2
− b
m
x + c
m
), (1)
where x
2
− b
i
x + c
i
are quadratic polynomials without real roots.
Since the product of polynomials with positive coefficients is again a poly-
nomial with positive coefficients, it will be sufficient to prove the result


x
i
=
n+2

i=0
C
i
x
i
,
where
C
i
=
n!

(b + c +1)i
2
− ((b +2c)n +(2b +3c +1))i + c(n
2
+3n +2)

x
i
i!(n − i +2)!
.
The coefficients C
i


n +1
i

P (i)=0.
Proof. See (SL81-13).
Suppose to the contrary that the degree of f is at most p − 2. Then it
follows from the lemma that
0=
p−1

i=0
(−1)
i

p − 1
i

f(i) ≡
p−1

i=0
f(i)(modp),
624 4 Solutions
since

p−1
i

=

n=0
[(n +1)
k+1
− n
k+1
] ≡ (k +1)S
k
+
k−1

i=0

k +1
i

S
i
(mod p),
and the inductive step follows.
(2) Using the primitive root g modulo p.Then
S
k
≡ 1+g
k
+ ···+ g
k(p−2)
=
g
k(p−1)
− 1

n
. Then the other r − 1 girls can choose
their partners in B(n − 1,r− 1) ways and g
n
can choose any of the
remaining 2n− r boys. Thus, the total number of choices in this case
is (2n − r)B(n − 1,r− 1).
(ii) g
n
is not dancing. Then there are exactly B(n− 1,r) possible choices.
Therefore, for every n ≥ 2 it holds that
B(n, r)=(2n − r)B(n − 1,r− 1) + B(n − 1,r)forr =2,...,n.
Here we assume that B(n, r)=0forr>n, while B(n, 1) = 1 + 3 +···+
(2n − 1) = n
2
.
It is directly verified that the numbers A(n, r) satisfy the same initial
conditions and recurrence relations, from which it follows that A(n, r)=
B(n, r) for all n and r ≤ n.
14. We use the following nonstandard notation: (1
◦
)forx, y ∈ N, x ∼ y means
that x and y have the same prime divisors; (2
◦
)foraprimep and integers
r ≥ 0andx>0, p
r
 x means that x is divisible by p
r
, but not by p

α
 a − 1andp
β
 k,thenp
α+β
 a
k
− 1.
Proof. We use induction on β.Ifβ = 0, then
a
k
−1
a−1
= a
k−1
+···+a+1≡ k
(mod p) (because a ≡ 1), and it is not divisible by p.
Suppose that the lemma is true for some β ≥ 0, and let k = p
β+1
t
where p  t. By the induction hypothesis, a
k/p
= a
p
β
t
= mp
α+β
+1
for some m not divisible by p. Furthermore,

, all summands except for the last one are
divisible by p
α+β+2
. Hence p
α+β+1
 a
k
−1, completing the induction.
Now let a
k
− 1 ∼ a− 1forsomea, k > 1. Suppose that p is an odd prime
divisor of k, with p
β
 k. Then putting X = a
p
β
−1
+ ···+ a +1wealso
have (a − 1)X = a
p
β
− 1 ∼ a − 1; hence each prime divisor q of X must
also divide a− 1. But then a
i
≡ 1(modq)foreachi ∈ N
0
,whichgivesus
X ≡ p
β
(mod q). Therefore q | p

4
− 1 ∼ a
2
− 1 to hold. Similarly, we must have d =1.
Therefore all possible triples (b, m, n) with m>nare (2
s
− 1, 2, 1).
15. Let a + bt, t =0, 1, 2,..., be a given arithmetic progression that contains
asquareandacube(a, b > 0). We use induction on the progression step
b to prove that the progression contains a sixth power.
(i) b = 1: this case is trivial.
(ii) b = p
m
for some prime p and m>0. The case p
m
| a trivially reduces
to the previous case, so let us have p
m
 a.
Suppose that gcd(a, p)=1.Ifx, y are integers such that x
2
≡ y
3
≡ a
(here all the congruences will be mod p
m
), then x
6
≡ a
3