Solutions

85.

Find all pairs (a, b) of positive integers
with a ¹ b for which the system
Solution 1. Suppose that the system is solvable;
note that x = 0 is not a solution. Then
cosax =
cosbx so that sinax =
esinbx where
e =
±1. Hence
(a +
eb)sinbx = 0. Since a and b are
positive and unequal, a +
eb
¹ 0,
so that sinbx = 0. Hence bx = n
p for some
integer n. Also sinax = 0, so that ax = m
p for some integer m. Hence, we must have
an = bm for some integers m and n. Since
cosm
p =
cosn
p, m and n must have
opposite parity.
Suppose that a = 2^{u} p and b = 2^{v} q with u and
v unequal integers and p and q odd. Then
x = 2^{w}p. where w is the minimum of u and v
satisfies the system of equations.
Solution 2. First, observe that x ¹ 0 for any
solution. If the system is satisfied, then

= cosax + cosbx = 2cos 
1 2

(a+b)x cos 
1 2

(ab)x 
 
Þ cos 
1 2

(a + b)x = 0 or cos 
1 2

(ab)x = 0 
 
Þ 
1 2

(a + b)x = (2k+1) 
p 2

or 
1 2

(a  b)x = (2k+1) 
p 2


 
Þ ax ±bx = (2k + 1)p for some integer k 
 
Þ sinax = sin(±bx) = ±sinbx 
 
Þ 0 = a sinax + b sinbx = (a ±b)sinbx . 


Since a
¹ b and a + b > 0, 0 = sinbx = sinax, so that
ax = m
p and bx = n
p for some integers m and n.
Since 0 = cosax + cosbx = (
1)
^{m} + (
1)
^{n}, the integers
m and n must have different parity. Hence
where m and n are integers not both even or both odd. Since
x
¹ 0, a/b = m/n, so a/b in lowest terms must have
numerator and denominator of different parities.
We now show that, for any pair a, b satisfying this condition,
there is a solution. Wolog, let a = 2uw and v = (2v+1)w, where
the greatest common divisor of 2u and 2v+1 is 1, and w is
an arbitrary positive integer. Suppose that x = p/w. Then
cosax + cosbx = cos2up+ cos(2v+1)p = 1  1 = 0 

and
a sinax + b sinbx = a sin2up+ b sin(2v+1)p = 0 + 0 = 0 

as desired.
Solution 3. Since cos^{2} ax = cos^{2} bx and
a^{2} sin^{2} ax + b^{2} sin^{2} bx, then
a^{2} cos^{2} bx + b^{2} sin^{2} bx = a^{2} Þ(b^{2}  a^{2})sin^{2} bx = 0 

so that bx = n
p for some integer. Similarly ax = m
p.
The solution can be completed as before.
Comment. Note that there are two parts to the solution
of this problem, and your writeup should make sure that these
are carefully delineated. First, assuming that there is a solution,
you derive necessary conditions on a and b that the two equations
are consistent. Then, you assume these conditions on a and
b, and then display a solution to the two equations.
A complete solution requires noting that suitable numbers
a and b actually do lead to
a solution.

86.

Let ABCD be a convex quadrilateral with
AB = AD and CB = CD. Prove that


(a) it is possible to inscribe a circle in it;


(b) it is possible to circumscribe a circle about
it if and only if AB ^BC;


(c) if AB ^BC and R and r are the respective
radii of the circumscribed and inscribed circles, then the
distance between the centres of the two circles is equal to
the square root of R^{2} + r^{2}  rÖ[(r^{2} + 4R^{2})].
Comment. Most students picked up the typo in part (c)
in which AC was given instead of the intended BC. I am sorry
for the mistake. However, this does happen from time to time even
on competitions, and you should be alert. From the context of this
problem, the intention was probably pretty clear (in fact, some
of you might not have realized that there was an error). The rule
in such a situation is that, if you feel that there is an error,
make a reasonable
nontrivial interpretation of the problem,
state it clearly and solve it.
Solution 1. (a) Triangles ABC and ADC are congruent
(SSS) with the congruence implemented by a reflection in
AC. Hence AC bisects angles DAB and DCB. The
angle bisectors of ÐADB and ÐABC are reflected
images and intersect in I, a point on AC. Since I is
equidistant from the four sides of the kite ABCD, it is
the centre of its incircle.
(b) If AB ^BC, then the circle with diameter AC passes
through B. By symmetry about AC, it must pass through D
as well. Conversely, let \frak C be the circumcircle
of ABCD. The circle goes to itself under reflection
in AC, so AC must be a diameter of \frak C.
Hence ÐABC = ÐADC = 90^{°}.
(c) Let I be the incentre and O the circumcentre of
ABCD; both lie on AC. Suppose that J and K are
the respective feet of the perpendiculars to AB and
BC from I, and P and Q the respective feet of
the perpendiculars to AB and BC from O. Let
x = AB  and y = BC . Then

x y

= 
x  r r

Þ xy = r(x + y) . 

Since
AO
 =
OC
 = R,
4R
^{2} = x
^{2} + y
^{2}. Noting that x and y both exceed r,
we have that

= x^{2} + y^{2} + 2xy = 4R^{2} + 2r(x + y) 
 
Þ (x + y  r)^{2} = r^{2} + 4R^{2} 
 
Þ x + y = r + 
 _______ Ör^{2} + 4R^{2}

. 


Now

= JP ^{2} + KQ ^{2} = (JB  
1 2

AB )^{2}+ (KB  
1 2

BC )^{2} 
 
= 2r^{2}  r(x + y) + 
1 4

(x^{2} + y^{2}) = r^{2}  r 
 _______ Ör^{2} + 4R^{2}

+ R^{2} , 


yielding the desired result.
Solution 2. (a) Since triangles ADB and CDB are
isosceles, the angle bisectors of A and C right bisect
the base BD and so they coincide. The line AC is an
axis of reflective symmetry that interchanges B and D,
and also interchanges the angle bisectors of B and D.
The point P where one of the bisectors intersects the
axis AC is fixed by the reflection and so lies on the
other bisector. Hence, P is common to all four angle
bisectors, and so is equidistant from the four sides of the
quadrilateral. Thus, we can inscribe a circle inside
ABCD with centre P.
(b) Since AC is a line of symmetry, ÐB = ÐD.
Note that, ABCD has a circumcircle Û
pairs of opposite angles sum to 180^{°} ÛÐB + ÐD = 180^{°} Û ÐB = ÐD = 90^{°}. This establishes the result.
(c) [R. Barrington Leigh] Let a, b and c be the respective
lengths of the segments BC, AC and AB. Let O and I
be, respectively, the circumcentre and the incentre for the
quadrilateral. Note that both points lie on the diagonal AC.
Wolog, we may take a ³ c.
We observe that ÐABI = 45^{°} and that BI is the
hypotenuse of an isosceles right triangle with arms of length
r. We have, by the Law of Cosines,

= R^{2} + 2r^{2}  2Ö2Rr cosÐIBO 
 
= R^{2} + 2r^{2}  2Ö2Rr 
é ê
ë

cos 
æ ç
è

ÐABO 
p 4


ö ÷
ø


ù ú
û


 
= R^{2} + 2r^{2}  2Ö2Rr [cosÐABO (1/Ö2)+ sinÐABO (1/Ö2)] 
 
= R^{2} + 2r^{2}  2Rr [cosÐABO + cosÐCBO] 
 
= R^{2} + 2r^{2}  2Rr [cosÐBAC + cosÐBCA] 
 
= R^{2} + 2r^{2}  2Rr 
æ ç
è


a+c b


ö ÷
ø


 
= R^{2} + 2r^{2}  r(a + c) , 


since b = 2R and both triangle AOB and COB are isosceles
with arms of length R.
By looking at the area of DABC in two ways, we have that
ac = r(a+c). Now
(a + c  r)^{2} = a^{2} + c^{2} + r^{2} + 2[ac  r(a+c)] = a^{2} + c^{2} + r^{2} = 4R^{2} + r^{2} , 

so that a + c = r +
Ö[(4R
^{2} + r
^{2})]. (The positive root
is selected as a and c both exceed r.) Hence

= R^{2} + 2r^{2}  r[r + 
 _______ Ö4R^{2} + r^{2}

] 
 
= R^{2} + r^{2}  r 
 _______ Ör^{2} + 4R^{2}

. 



87.

Prove that, if the real numbers a, b,
c, satisfy the equation
for each positive integer n, then at least one of a and
b is an integer.
Solution. We first show that a + b = c.
Suppose, if possible, that c > a + b. Let
n
³ (c
 a
 b)
^{1}. Then
ënc û > nc  1 > n(a + b) > ëna û+ ënb û 

yielding a contradiction. Similarly, if c < a + b and
n
³ 2(a + b
 c)
^{1}, then
ënc û £ nc £ na  1 + nb  1 < ëna û+ ënb û 

again yielding a contradiction. Hence a + b = c.
Let a = ëa û+ a,
b = ëb û+ b and c = ëc û+g. From the condition for n = 1, we have
ëa û+ ëb û = ëc û.
Then, ëna û = ënëa û+ naû = nëa û+ ënaû
with similar equations for b and c. Putting this together
gives that ënaû+ ënbû = ëngû, for all n ³ 1. As in the
first part of the solution, we have that a+ b = g, from which { na} +{ nb} = { ng} for all n ³ 1, where
{ x } denotes the fractional part x  ëx û
of x.
We first show that a, b and g cannot all
be positive and rational. For, if they were rational, then
for some positive integers i, j, k
with k ³ 2, we would have
a = i/k, b = j/k and g = (i+j)/k.
Then ëkaû = i = ë(k1)aû+ 1, with similar relations for b and g. Thus,
ëkaû+ ëkbû ëkgû [ë(k1)aû+ ë(k1)bû ë(k1)gû] = 1 

so that
ën
aû+
ën
bû =
ën
gû must fail for either n = k
or n = k
1.
Wolog, suppose that all of a, b, g are
positive with a irrational. Let p be a nonnegative integer
for which a+ pb < 1 £ a+ (p+1)b and
suppose that e = 1  (a+ pb). Since
a+ b = g < 1, it follows that p ³ 1.
We show that there is a positive integer m ³ 2 for which
a+ pb < { ma}. Let t = é1/eù and consider the intervals [i/t, (i+1)/t)
where 0 £ i £ t1. By the Pigeonhole Principle, one of
these intervals must contain two of the numbers { 2a},{ 4a}, ¼, { 2(t+1)a}, say { qa}
and { ra} with q ³ r + 2. Thus,
{ qa}  { ra}  < 1/t £ e.
Since
{ qa}  { ra} = (q  r)aëqaû+ ëraû = (q  r)a±I 

for some integer I, either { (q
 r)
a} <
e
or { (q
 r)
a} > 1
 e.
In the first case, we can find a positive integer s for which
1 > s { (q  r) a} > 1  e. Since
s(q  r)a = së(q  r)aû+ s{ (q  r)a} , 

it follows that
{ s(qr)a} = s { (q  r) a} > 1  e . 

Thus, in either case, we can find m
³ 2 for which
a+ p
b = 1
 e < { m
a}.
Now, { ma} > a,
{ mg} = { ma} + { mb} ³ { ma} > a+ pb ³ a+ b = g 

and
{ mb} = { mg}  { ma} < 1  (a+ pb) = 1  [a+ (p+1)b b] £ 1  (1  b) = b . 

Hence,
ëmaû = ma { ma} = (m1)a ({ ma}  a) < (m1)a 

so that
ë(m
1)
û =
ëm
aû;
ëmgû = mg { mg} = (m1)g ({ mg}  g) < (m1)g 

so that
ë(m
1)
gû =
ëm
gû;
and
ëm
bû = m
b { m
b} > (m
1)
b ³ ë(m
1)
bû, so that
ë(m
1)
bû+ 1 =
ëm
bû.
Hence
ën
aû+
ën
bû =
ën
gû must fail for either n = m
or n = m
1.
The only remaining possibility is that either a or b
vanishes, i.e., that a or b is an integer. This
possibility is feasible when the other two variables have the
same fractional part.

88.

Let I be a real interval of length 1/n. Prove
that I contains no more than ^{1}/_{2}(n+1) irreducible
fractions of the form p/q with p and q positive integers,
1 £ q £ n and the greatest common divisor of
p and q equal to 1.
Comment. The statement of the problem needs a slight
correction. The result does not apply for closed intervals of
length 1/n whose endpoints are consecutive fractions with
denominator n. The interval [1/3, 2/3] is a counterexample.
So we need to strengthen the hypothesis to exclude this case, say
by requiring that the interval be open (
i.e., not include
its endpoints), or by supposing that not both endpoints are
rational. Alternatively, we could change the bound to
^{1}/
_{2}(n+3) and ask under what circumstances this bound
is achieved.
Solution 1. We first establish a lemma: Let
1 £ q £ n. Then there exists a positive integer
m for which ^{1}/_{2}(n+1) £ mq £ n.
For, let m = ën/q û. If q > n/2, then m = 1
and clearly ^{1}/_{2}(n+1) £ mq = q £ n. If
q £ n/2, then (n/q)  1 < m £ (n/q), so that
and
^{1}/
_{2}(n+1)
£ mq
£ n.
Let p/q and p¢/q¢ be two irreducible fractions in I with
m and m¢ corresponding integers as determined by the lemma.
Suppose, if possible, that mq = m¢q¢. Then

ê ê
ê


p q

 
p¢ q¢


ê ê
ê

= 
ê ê
ê


mp mq

 
m¢p¢ mq


ê ê
ê

³ 
1 mq

³ 
1 n

, 

contradicting the fact that no two fractions in I can be distant
at least
^{1}/
_{n}.
It follows that the mapping p/q ® mq from the set
of irreducible fractions in I into the set of integers in
the interval [(n+1)/2, n] is oneone. But the latter set has
at most n  ((n+1)/2) + 1 = (n+1)/2 elements, and the result
follows.
Solution 2. [M. Zaharia] For 1 £ i £ ^{1}/_{2}(n+1),
define
S_{i} = { 2^{j}(2i  1) : j = 0, 1, 2, ¼} . 

(Thus, S
_{1} = { 1, 2, 4, 8,
¼}, S
_{3} = { 3, 6, 12, 24,
¼} and S
_{5} = { 5, 10, 20, 40,
¼}, for example.) We show
that each S
_{i} contains at most one denominator not exceeding
n among the irreducible fractions in I. For suppose

a 2^{u}(2i  1)

and 
b 2^{v}(2i  1)



are distinct irreducible fractions in I, with u
£ v.
Then

ê ê
ê


a 2^{u}(2i  1)

 
b 2^{v}(2i  1)


ê ê
ê

= 
ê ê
ê


2^{vu}a  b 2^{v}(2i  1)


ê ê
ê

³ 
1 2^{v}(2i  1)

³ 
1 n

. 

But I cannot contain two fractions separated by a distance of
1/n or larger. Thus, we get a contradiction, and it follows that
there cannot be more than one fraction with a denominator in each
of the at most (n+1)/2 sets S
_{i}. The result follows.

89.

Prove that there is only one triple of positive
integers, each exceeding 1, for which the product of any two of
the numbers plus one is divisible by the third.
Solution 1. Let a, b, c be three numbers with the
desired property; wolog, suppose that 2
£ a
£ b
£ c.
Since a
(bc + 1), a has greatest common divisor
1 with each of b and c. Similarly, the greatest common
divisor of b and c is 1. Since ab + bc + ca + 1
is a multiple of each of a, b, c, it follows that
ab + bc + ca + 1 is a multiple of abc. Therefore,
abc
£ ab + bc + ca + 1.
Since a, b, c are distinct and so 2 £ a < b < c,
we must have a ³ 2 and b ³ 3. Suppose, if possible
that b ³ 4, so that c ³ 5. Then abc ³ 40
and
ab + bc + ca + 1 £ 
abc 5

+ 
abc 2

+ 
abc 4

+ 1 £ 
19abc 20

+ 
abc 40

< abc , 

a contradiction. Hence b must equal 3 and a must equal 2.
Since c
(ab+1), c must equal 7. The triple
(a, b, c) = (2, 3, 7) satisfies the desired condition and
is the only triple that does so.
Solution 2. As in Solution 1, we show that
abc £ ab + bc + ca + 1, so that
1 £ 
1 a

+ 
1 b

+ 
1 c

+ 
1 abc

. 

However, if a
³ 3, the right ride of the inequality
cannot exceed (1/3) + (1/4) + (1/5) + (1/60) = 4/5 < 1.
Hence a = 2. If a = 2 and b
³ 4, then b
³ 5
(why?) and the right side cannot exceed (1/2) + (1/5)+ (1/7) + (1/70) = 6/7 < 1. Hence (a, b) = (2, 3).
If now c exceeds 7, then c
³ 11 and the right side of
the inequality cannot exceed (1/2) + (1/3) + (1/11) + (1/66) = 31/33 < 1. Hence c
£ 7, and we are now led to the solution.
Solution 3. [P. Du] As in Solution 1, we show that
a, b, c are pairwise coprime and that ab + bc + ca + 1 is
a multiple of abc. Assume 2 £ a < b < c. Then
abc > ac and bc(a  1) ³ bc > ac ³ a(b + 1) > ab + 1,
whence, adding these, we get 2abc  bc > ac + ab + 1,
so that 2abc > ab + bc + ca + 1. Hence,
abc = ab + bc + ca + 1 = bc  (ca)b + bc + bc  (ba)c + 1 = 3bc  (ca)b  (cb)a + 1 < 3bc 

so that a < 3. Hence a = 2. Plugging this into the
equation yields
bc = 2b + 2c + 1 = 4c  2(c  b) + 1 < 4c 

so that b < 4. Hence b = 3, and we find that
6c = 6 + 5c + 1 or c = 7.
Solution 4. [O. Ivrii] As before, we show that a, b and
c are pairwise coprime, and take 2 £ a < b < c. Then
bc ab + ac + 1. Since bc > ac + 1 and bc > ab + 1,
we have that 2bc > ab + ac + 1. Hence bc = ab + ac + 1, so that
(bc + 1) + ab = 2(ab + 1) + ac. Since a divides each of
bc + 1, ab and ac, but is coprime with ab + 1, it
follows that a divides 2. Hence a = 2 and
bc = 2(b + c) + 1 Þ (b  2)(c  2) = 5Þ (b, c) = (3, 7) . 

Solution 5. As above, we can take 2 £ a < b < c. Since

(ab + 1) c

· 
(ca + 1) b

= a^{2} + 
a c

+ 
a b

+ 
1 bc

, 

we see that (a/c) + (a/b) + (1/(bc)) is a
positive integer less than 3.
Suppose, if possible, that
(a/c) + (a/b) + (1/(bc)) = 2. Then ab + ac + 1 = 2bc, whence
b(c  a) + c(b  a) = 1, an impossibility. Hence
a(b + c) + 1 = bc, so that
2 = (bc + 1)  a(b + c) . 

Since both terms on the right are divisible by a, 2 must
be a multiple of a. Hence a = 2, and we obtain
(b
 2)(c
 2) = 5, so that (b, c) = (3, 7).