OTIS Application

Alhimar

Contents

1 Geometry 1

2 Inequalities 2

3 Additional Problems 4

1 Geometry
I follow the same notation used in EGMO. Thus given a triangle ABC, (ABC) refers to its circumcircle
and ∡ABC is the angle from segment AB to segment BC considered anti-clockwise (assuming A, B, C
are placed clockwise) mod 180, i.e. it is the directed angle between them. Given a circle ω, with center
O, and point X, the power of X with respect to ω will be represented by Πω (X).

Problem A.1. Given a triangle ABC, let P and Q be points on segments AB and AC, respectively,
such that AP = AQ. Let S and R be distinct points on segment BC such that S lies between B and
R, ∠BP S = ∠P RS, and ∠CQR = ∠QSR. Prove that P , Q, R, S are concyclic.

Proof. Observe that by the converse of the Alternate Segment Theorem, circles (P RS) and (QRS)
are tangent to AB and AC since ∡BP S = ∡P RS and ∡CQR = ∡QSR. Assume that these circles, i.e.
←→
(P RS) and (QRS) are distinct. They share points R and S, thus their radical axis must be line RS.
However,

Π(P RS) (A) = AP 2 = AQ2 = Π(QRS) (A).

.
Thus, A must lie on their radical axis. However, this would imply A lies on line BC which is a
contradiction. Therefore, (P RS) and (QRS) are the same, thus P , Q, R, S, must be concyclic.

Problem A.2. Let ABC be a triangle with circumcenter O. The points P and Q are interior points
of the sides CA and AB respectively. Let K, L, M be the midpoints of BP , CQ, P Q. Suppose that
line P Q is tangent to the circumcircle of ∆KLM . Prove that OP = OQ.

Proof. Let the circumcircle of ∆ABC be ω and let R be the circumradius. Observe that :

OP = OQ ⇐⇒ R2 − OP 2 = R2 − OQ2 ⇐⇒ Πω (P ) = Πω (Q).

1
.
It suffices to show that AQ · QB = AP · P C. We prove it like so,

∡LKM = ∡LM P
= ∡AP M [Midpoint theorem]
∡M LK = ∡QM K
= ∡M QA. [Midpoint theorem]

Thus, by AA critirion, ∆M LK ∼ ∆P QA. We get our desired result as follows :

AP MK 2M K QB
= = = .
AQ ML 2M L PC
We are done after rearranging.

Problem A.3. Let ABCD be a quadrilateral whose diagonals are perpendicular and meet at E. Prove
that the reflections of E across the sides of ABCD are concyclic.

Proof. Consider the homothety with center E of factor 12 . This would map the reflection of E across
lines AB, BC, CD, DA to the feet of the altitudes dropped from E to the base in triangles ∆ABE,
∆BCE, ∆CDE, ∆DAE, respectively. We also name the feets P . Q, R, S respectively.

∡SP Q = ∡SP E + ∡EP Q

= ∡SAE + ∡EBQ
∡SRQ = ∡SRE + ∡ERQ
= ∡SDE + ∡ECQ
∡SP Q + ∡QRS = ∡SAE + ∡EBQ + ∡EDS + ∡QCE
= 180◦ = 0.

Thus P QRS is a cyclic quadrilateral.

2 Inequalities
Problem B.1. Suppose that a2 + b2 + c2 = 1 for positive real numbers a, b, c. Find the minimum
possible value of
ab bc ca
+ + .
c a b
.
√
Solution. The answer is 3. Observe :

ab bc ca 2 X ab 2
   
+ + = + 2(a2 + b2 + c2 ). (1)
c a b cyc
c

ab 2
P

We can bound cyc c with ease.
 
ab 2 bc 2



X  ab 2 X c + a X
≥ ≥ a2 = 1. [AM-GM]
cyc
c cyc
2 cyc

2
Thus, (1) can be written as
 2
ab bc ca
+ + ≥ 1 + 2(a2 + b2 + c2 ) = 3.
c a b
√
Since a, b, c > 0, we can say that the lower bound is 3. It is attained when a = b = c = √1 . Thus
3
√
3 is the answer .

Problem B.2. Let a, b, c be positive real numbers such that a2 + b2 + c2 + (a + b + c)2 ≤ 4. Prove that

ab + 1 bc + 1 ca + 1
2
+ 2
+ ≥ 3.
(a + b) (b + c) (c + a)2

Proof. Observe :

4 ≥ a2 + b2 + c2 + (a + b + c)2 = 2(a2 + b2 + c2 + ab + bc + ca)

2 ≥ 2(ab + bc + ca) [a2 + b2 + c2 ≥ ab + bc + ca]
1 ≥ ab + bc + ca. (1)

We can now homogenize and solve with (1) and AM-GM.

X ab + 1 X 2ab + bc + ca
≥
cyc
(a + b)2 cyc
4ab
√
X 4 a3 b3 c2 X √c
≥ = √4
cyc
ab cyc ab
√ √ √ !
c a b
≥3 √ 4
· √
4
·√4
= 3.
ab bc ca

Problem B.3. Let a, b, c, d be positive reals with (a + c)(b + d) = 1. Prove that

a3 b3 c3 d3 1
+ + + ≥ .
b+c+d c+d+a d+a+b a+b+c 3

Proof 1/2. Here, σi denotes the ith elementary symmetric polynomial of a, b, c, d. The following is
due to Hölder,
!1 !1
4 4
X X a3 1 1 X
a(b + c + d) (1) 4 (1) 4 ≥ a.
cyc cyc
b + c + d cyc

Thus,
X a3 (a + b + c + d)4 σ14 σ4
≥ = = 51 . (1)
16 · 2σ2
X
cyc
b+c+d 16 · a(b + c + d) 2 σ2
cyc

3
We conclude via Maclaurin.
4 2
s

σ1 σ2 σ12 1 23
4 ≥ 4 ⇐⇒ ≥ 4 = .




1 2
σ2 2
3
σ1 a+b+c+d p
= ≥ (a + c)(b + d) = 1.
2 2
σ14 25
≥ .
σ2 3
X a3 σ4 1
Thus, recalling (1), ≥ 51 ≥ .
cyc
b+c+d 2 σ2 3

Proof 2/2.
X a3 1 X 3 X 1
≥ · a · [Chebyshev]
cyc
b+c+d 4 cyc cyc
b + c +d
1 X X 2 X 1
≥ · a· a · [Chebyshev]
16 cyc cyc cyc
b+c+d
1 X X X 1
= · a2 · (b + c + d) ·
16 · 3 cyc cyc cyc
b + c +d
1 X 2
≥ · a . [AM-HM] (1)
3 cyc

Thus, it suffices to minimize a2 + b2 + c2 + d2 - which can be done by multiple applications of AM-GM

on the condition.

1 = (a + c)2 (b + d)2 = (a2 + 2ac + c2 )(b2 + 2bd + d2 )

≤ 4(a2 + c2 )(b2 + d2 )
1 p 2 a2 + b2 + c2 + d2
≤ (a + c2 )(b2 + d2 ) ≤ .
2 2
X a3 1
We can now write (1) as ≥ .
cyc
b+c+d 3

3 Additional Problems
Problem C.1. Write a computer program to find the number of ordered pairs of prime numbers (p, q)
such that when
N = p2 + q 3
is written in decimal (without leading zeros), each digit from 0 to 9 appears exactly once. Submit the
numerical answer and the source code for the program.

Solution. My horrid code in python :

4
 1 from math import *
2

3 # function that returns all primes <= an integer input

4 def primes_till ( num ) :
5 # Sieve of Eratosthenes
6 primes = [ i for i in range (2 , num +1) ]
7 i = 2
8 while i *i <= num :
9 if ( i in primes ) : primes = [ n for n in primes if n % i !=0 or n == i ]
10 i +=1
11 return primes
12

13 counter = 0
14 possibleP = primes_till ( int ( sqrt (9876543210) ) )
15

16 # Checking all combinations of (p , q )

17 for q in possibleP :
18 if ( q **3 > 9876543210) : break
19 for p in possibleP :
20 N = p **2 + q **3
21 if ( N < 123456789) : continue
22 list = sorted ([ int ( i ) for i in str ( N ) ])
23 if list == [0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]:
24 counter += 1
25

26 print ( counter )

The output is 1270 .

Problem C.2. Find all functions f : R →

− R for which
f (xf (x) + f (y)) = f (x)2 + y
holds for all real numbers x and y.

Solution. The answer is f (x) = ±x. We can show that this function indeed satisfies the condition as
follows :
LHS = f (xf (x) + f (y)) = ±(±x2 ± y) = x2 + y
RHS = f (x)2 + y = (±x)2 + y = x2 + y
To prove that the condition implies f (x) = ±x it suffices to show f is an involution since this collapses
the problem into an example from the recommended reading. This can be done quite easily by isolated
parts.
Fixing x, notice that the RHS can be any real number, i.e. any member of the the codomain,
as y varies. Thus f must be surjective, since for each real number there exist a real number that the
function f maps onto it.
This implies ∃X s.t. f (X) = 0. Plugging x = X in the condition gives us f (f (y)) = y for each
y in R. Thus f is an involution. Proceeding very similarly to the First Example in Section 3.2. of the
OTIS Excerpts :
f (xf (x) + f (y)) = f (x)2 + y
f (xf (x) + t) = f (x)2 + f (t) [y = f (t)]
2
So, f (f (x) + f (t)) = xf (x) + t
= f (x2 + f (t))

5
Thus f (x)2 = x2 , which implies f (x) = ±x for each x in R.
We can prove f (x) is not pointwise i.e. it is either +x for each x or −x for each x, by contradiction.
Assume there exist a and b in R such that f (a) = a and f (b) = −b. So,

f (f (a)2 + f (b)) = af (a) + b

=⇒ f (a2 − b) = a2 + b

Thus ±(a2 − b) = a2 + b which implies a or b must be 0. We can thus conclude f (x) = ±x.

Problem C.3. Let a, b, c, d be real numbers such that b − d ≥ 5 and all zeros x1 , x2 , x3 , and x4
of the polynomial P (x) = x4 + ax3 + bx2 + cx + d are real. Find the smallest value the product
(x1 2 + 1)(x2 2 + 1)(x3 2 + 1)(x4 2 + 1) can take.

Solution.
4
Y Y Y Y
(xk + 1) = (xk + i)(xk − i) = (−i − xk ) · (i − xk )
k=1 k k k
P (i)P (−i) = (−i)4 + a(−i)3 + b(−i)2 + c(−i) + d

· (i)4 + a(i)3 + b(i)2 + c(i) + d

= (1 + ai − b − ci + d)(1 − ai − b + ci + d)
|P (i)|2 = (1 + b − d)2 + (a − c)2 ≥ (b − d − 1)2 ≥ 42 = 16

Of course, equality holds when a = c and b − d = 5, which happens when x1 = x2 = x3 = x4 = 1. Thus

16 is the answer.

Problem C.4. Ana and Banana are playing a game. First Ana picks a word, which is defined to be a
nonempty sequence of capital English letters. Then Banana picks a nonnegative integer k and challenges
Ana to supply a word with exactly k subsequences which are equal to Ana’s word. Ana wins if she is
able to supply such a word, otherwise she loses. For example, if Ana picks the word TST, and Banana
chooses k = 4, then Ana can supply the word TSTST which has 4 subsequences which are equal to
Ana’s word. Which words can Ana pick so that she can win no matter what value of k Banana chooses?

Remark. I used the hint given by Batominovshi here.

Solution. It is obvious that if Ana chooses a string like A then she wins no matter what k Banana
chooses, since she can simple supply a string with A repeated k times. Playing with the string TST
reveals to be an answer as well. If Banana chooses k = 2, Ana may simple supply TSST, for k = 3
TSSST, and so on. However something like AAA doesn’t work. For k = 2, no solution can exist. We
can prove this easily by contradiction. If we assume that a solution exists, it must have more than three
A in it (otherwise the two subsequence will be the same). Thus one subsequence must be AAAA,
which has 4 subsequences equal to the original string - Contradiction!
This gives some motivation for the two claims I make. Before which I introduce some terminology.
Let S be any string of capital English letters. Ai represent capital English letters and ni represents the
number of times it repeats in sequence back to back. We represent S as follows :

S = A1 A1 A1 ...A1 A2 A2 A2 ...A2 ... A A A ...Ar

| {z } | {z } | r r {zr }
n1 times n2 times nr times

6
A sequence of length ni composed exclusively of the letter Ai will be called the i-th block.Also, let α1
be the number of times A1 appears in S (this includes all Ai equal to A1 as well) . Note that for integer
i ≥ 2, Ai is unequal Ai−1 and Ai+1 i.e. it is unequal to its neighbours. Now we make the two claims.
Claim 1. Given a word S such that

S = A1 A1 A1 ...A1 A2 A2 A2 ...A2 ... A A A ...At .

| {z } | {z } | t t{zt }
n1 times n2 times nt times

If there does not exist s such that ns = 1, then Bob Wins.

Proof of Claim 1. The proof of this will be a more general version of why AAA does not work. We
consider what happens when Bob chooses k = 2.
We assume the contrary that Ana wins by supplying some string W . W has exactly two subse-
quences equal to S. These two subsequences must be distinct so there must exist some m such that
their Am blocks are formed from different parts of W . So W has the letter Am appear atleast nm + 1
times in such a way that nm may be chosen to form a block Am in the subsequence. This implies that
we have more than nm +1


nm = nm + 1 ≥ 3 subsequences. Contradiction!

Claim 2. Given a word S such that

S = A1 A1 A1 ...A1 A2 A2 A2 ...A2 ... As ... A A A ...At .

| {z } | {z } | t t{zt }
n1 times n2 times nt times

If there exist s such that ns = 1. Then Ana wins.

Proof of Claim 2. We can easily show that we have k solutions by constructing the following solution
W
W = A1 A1 A1 ...A1 A2 A2 A2 ...A2 ... As As As ...As ... At At At ...At .
| {z } | {z } | {z } | {z }
n1 times n2 times k times nt times

We have k choices for Ak and only 1 choice for everything else. Thus there exactly k subsquences equal
to S.

We have thus shown, by the contrapositive of Claim 1 and Claim 2, that Ana wins if and only if there
exist a block αs in the word Ana picks such that ns = 1.