USA TSTST 2016 Solutions

United States of America — TST Selection Test

Evan Chen《陳誼廷》
58th IMO 2017 Brazil and 6th EGMO 2017 Switzerland

Contents
0 Problems 2

1 Solutions to Day 1 3
1.1 TSTST 2016/1, proposed by Victor Wang . . . . . . . . . . . . . . . . . . 3
1.2 TSTST 2016/2, proposed by Evan Chen . . . . . . . . . . . . . . . . . . . 4
1.3 TSTST 2016/3, proposed by Yang Liu . . . . . . . . . . . . . . . . . . . . 6

2 Solutions to Day 2 8
2.1 TSTST 2016/4, proposed by Linus Hamilton . . . . . . . . . . . . . . . . 8
2.2 TSTST 2016/5, proposed by Linus Hamilton, Cynthia Stoner . . . . . . . 9
2.3 TSTST 2016/6, proposed by Danielle Wang . . . . . . . . . . . . . . . . . 10

1
USA TSTST 2016 Solutions Evan Chen《陳誼廷》

§0 Problems
1. Let A = A(x, y) and B = B(x, y) be two-variable polynomials with real coefficients.
Suppose that A(x, y)/B(x, y) is a polynomial in x for infinitely many values of y,
and a polynomial in y for infinitely many values of x. Prove that B divides A,
meaning there exists a third polynomial C with real coefficients such that A = B · C.

2. Let ABC be a scalene triangle with orthocenter H and circumcenter O and denote
by M , N the midpoints of AH, BC. Suppose the circle γ with diameter AH meets
the circumcircle of ABC at G 6= A, and meets line AN at Q 6= A. The tangent to
γ at G meets line OM at P . Show that the circumcircles of 4GN Q and 4M BC
intersect on P N .

3. Decide whether or not there exists a nonconstant polynomial Q(x) with integer
coefficients with the following property: for every positive integer n > 2, the
numbers
Q(0), Q(1), Q(2), . . . , Q(n − 1)
produce at most 0.499n distinct residues when taken modulo n.

4. Prove that if n and k are positive integers satisfying ϕk (n) = 1, then n ≤ 3k . (Here
ϕk denotes k applications of the Euler phi function.)

5. In the coordinate plane are finitely many walls, which are disjoint line segments,
none of which are parallel to either axis. A bulldozer starts at an arbitrary point
and moves in the +x direction. Every time it hits a wall, it turns at a right angle
to its path, away from the wall, and continues moving. (Thus the bulldozer always
moves parallel to the axes.)
Prove that it is impossible for the bulldozer to hit both sides of every wall.

6. Let ABC be a triangle with incenter I, and whose incircle is tangent to BC, CA,
AB at D, E, F , respectively. Let K be the foot of the altitude from D to EF .
Suppose that the circumcircle of 4AIB meets the incircle at two distinct points C1
and C2 , while the circumcircle of 4AIC meets the incircle at two distinct points B1
and B2 . Prove that the radical axis of the circumcircles of 4BB1 B2 and 4CC1 C2
passes through the midpoint M of DK.

2
USA TSTST 2016 Solutions Evan Chen《陳誼廷》

§1 Solutions to Day 1
§1.1 TSTST 2016/1, proposed by Victor Wang
Available online at https://aops.com/community/p6575197.

Problem statement

Let A = A(x, y) and B = B(x, y) be two-variable polynomials with real coefficients.

Suppose that A(x, y)/B(x, y) is a polynomial in x for infinitely many values of y,
and a polynomial in y for infinitely many values of x. Prove that B divides A,
meaning there exists a third polynomial C with real coefficients such that A = B · C.

This is essentially an application of the division algorithm, but the details require
significant care.
First, we claim that A/B can be written as a polynomial in x whose coefficients are
rational functions in y. To see this, use the division algorithm to get

A=Q·B+R Q, R ∈ (R(y))[x]

where Q and R are polynomials in x whose coefficients are rational functions in y, and
moreover degx B > degx R.
Now, we claim that R ≡ 0. Indeed, we have by hypothesis that for infinitely many
values of y0 that B(x, y0 ) divides A(x, y0 ), which means B(x, y0 ) | R(x, y0 ) as polynomials
in R[x]. Now, we have degx B(x, y0 ) > degx R(x, y0 ) outside of finitely many values of y0
(but not all of them!); this means for infinitely many y0 we have R(x, y0 ) ≡ 0. So each
coefficient of xi (in R(y)) has infinitely many roots, hence is a zero polynomial.
Consequently, we are able to write A/B = F (x, y)/M (y) where F ∈ R[x, y] and
M ∈ R[y] are each polynomials. Repeating the same argument now gives

A F (x, y) G(x, y)
= = .
B M (y) N (x)

Now, by unique factorization of polynomials in R[x, y], we can discuss GCD’s. So, we
tacitly assume gcd(F, M ) = gcd(G, N ) = (1). Also, we obviously have gcd(M, N ) = (1).
But F · N = G · M , so M | F · N , thus we conclude M is the constant polynomial. This
implies the result.

Remark. This fact does not generalize to arbitrary functions that are separately polynomial:
see e.g. http://aops.com/community/c6h523650p2978180.

3
USA TSTST 2016 Solutions Evan Chen《陳誼廷》

§1.2 TSTST 2016/2, proposed by Evan Chen

Available online at https://aops.com/community/p6575204.

Problem statement

Let ABC be a scalene triangle with orthocenter H and circumcenter O and denote
by M , N the midpoints of AH, BC. Suppose the circle γ with diameter AH meets
the circumcircle of ABC at G 6= A, and meets line AN at Q 6= A. The tangent to
γ at G meets line OM at P . Show that the circumcircles of 4GN Q and 4M BC
intersect on P N .

We present two solutions, one using essentially only power of a point, and the other more
involved.

¶ First solution (found by contestants). Denote by 4DEF the orthic triangle. Observe
P A and P G are tangents to γ, since OM is the perpendicular bisector of AG. Also
note that AG, EF , BC are concurrent at some point R by radical axis on (ABC), γ,
(BF EC).
Now, consider circles (P AGM ), (M F DN E), and (M BC). We already saw the point
R satisfies
RA · RG = RE · RF = RB · RC
and hence has equal powers to all three circles; but since the circles at M already, they
must actually be coaxial. Assume they meet again at T ∈ RM , say. Then ∠P T M and
∠M T N are both right angles, hence T lies on P N .
Finally H is the orthocenter of 4ARN , and thus the circle with diameter RN passes
through G, Q, N .

P A

M E

G T

Q O
F
H

R B D N C

4
USA TSTST 2016 Solutions Evan Chen《陳誼廷》

¶ Alternate solution (by proposer). Let L be diametrically opposite A on the circum-

circle. Denote by 4DEF the orthic triangle. Let X = AH ∩ EF . Finally, let T be the
second intersection of (M F DN E) and (M BC).

K P A

M E

G T
X
Q O
F
H

R B D N C

We begin with a few easy observations. First, points H, G, N , L are collinear and
∠AGL = 90◦ . Also, Q is the foot from H to AN . Consequently, lines AG, EF , HQ,
BC, T M concur at a point R (radical axis). Moreover, we already know ∠M T N = 90◦ .
This implies T lies on the circle with diameter RN , which is exactly the circumcircle of
4GQN .
Note by Brokard’s Theorem on AF HE, the point X is the orthocenter of 4M BC.
But ∠M T N = 90◦ already, and N is the midpoint of BC. Consequently, points T , X,
N are collinear.
Finally, we claim P , X, N are collinear, which solves the problem. Note P = GG ∩ AA.
Set K = HN L ∩ AP . Then by noting
N
−1 = (D, X; A, H) = (∞, N X ∩ AK; A, K)

we see that N X bisects segment AK, as desired. (A more projective finish is to show
that P XN is the polar of R to γ).

Remark. The original problem proposal reads as follows:

Let ABC be a triangle with orthocenter H and circumcenter O and denote by
M , N the midpoints of AH, BC. Suppose ray OM meets the line parallel to
BC through A at P . Prove that the line through the circumcenter of 4M BC
and the midpoint of OH is parallel to N P .
The points G and Q were added to the picture later to prevent the problem from being
immediate by coordinates.

5
USA TSTST 2016 Solutions Evan Chen《陳誼廷》

§1.3 TSTST 2016/3, proposed by Yang Liu

Available online at https://aops.com/community/p6575217.

Problem statement

Decide whether or not there exists a nonconstant polynomial Q(x) with integer
coefficients with the following property: for every positive integer n > 2, the numbers

Q(0), Q(1), Q(2), . . . , Q(n − 1)

produce at most 0.499n distinct residues when taken modulo n.

We claim that
Q(x) = 420(x2 − 1)2
works. Clearly, it suffices to prove the result when n = 4 and when n is an odd prime p.
The case n = 4 is trivial, so assume now n = p is an odd prime.
First, we prove the following easy claim.

Claim
 — For any odd prime p, there are at least 12 (p − 3) values of a for which
1−a2
p = +1.

Proof. Note that if k 6= 0 and k 2 6= −1, then a = 1−k2

k2 +1
works.

Remark. The above identity comes from starting with the equation 1 − a2 = b2 , and writing
it as 1b − ab = 1. Then solve 1b − ab = k and 1b + ab = 1/k for a.

2
2

Let F (x) = (x2 − 1)2 . The range of F modulo p is contained within the 12 (p + 1)
quadratic residues modulo p. On the other hand, if for some t neither of 1 ± t is a
quadratic residue, then t2 is omitted from the range of F as well. Call such a value of t
useful, and let N be the number of useful residues. We aim to show N ≥ 14 p − 2.
We compute a lower bound on the number N of useful t by writing
           !
1 X 1−t 1+t 2 −2
N= 1− 1− − 1− − 1−
4 t
p p p p
     
1X 1−t 1+t
≥ 1− 1− −1
4 t p p
!
1 X  1 − t2 
= p+ −1
4 t
p
1
p + (+1) · 12 (p − 3) + 0 · 2 + (−1) · ((p − 2) − 12 (p − 3)) − 1


≥
4
1
≥ (p − 5) .
4
Thus, the range of F has size at most
1 1 3
(p + 1) − N ≤ (p + 3).
2 2 8
This is less than 0.499p for any p ≥ 11.

6
USA TSTST 2016 Solutions Evan Chen《陳誼廷》

Remark. In fact, the computation above is essentially an equality. There are only two
points where terms are dropped: one, when p ≡ 3 (mod 4) there are no k 2 = −1 in the
lemma, and secondly, the terms 1 − (2/p) and 1 − (−2/p) are dropped in the initial estimate
for N . With suitable modifications, one can show that in fact, the range of F is exactly
equal to 1

 8 (3p + 5) p ≡ 1 (mod 8)
1

1 1  (3p + 7) p ≡ 3 (mod 8)
(p + 1) − N = 81
2 2  (3p + 9) p ≡ 5 (mod 8)
 81


8 (3p + 3) p ≡ 7 (mod 8).

7
USA TSTST 2016 Solutions Evan Chen《陳誼廷》

§2 Solutions to Day 2
§2.1 TSTST 2016/4, proposed by Linus Hamilton
Available online at https://aops.com/community/p6580534.

Problem statement

Prove that if n and k are positive integers satisfying ϕk (n) = 1, then n ≤ 3k . (Here
ϕk denotes k applications of the Euler phi function.)

The main observation is that the exponent of 2 decreases by at most 1 with each
application of ϕ. This will give us the desired estimate.
Define the weight function w on positive integers as follows: it satisfies

w(ab) = w(a) + w(b);

w(2) = 1; and
w(p) = w(p − 1) for any prime p > 2.

By induction, we see that w(n) counts the powers of 2 that are produced as ϕ is repeatedly
applied to n. In particular, k ≥ w(n).
From w(2) = 1, it suffices to prove that w(p) ≥ log3 p for every p > 2. We use strong
induction and note that
 
p−1
w(p) = w(2) + w ≥ 1 + log3 (p − 1) − log3 2 ≥ log3 p
2

for any p > 2. This solves the problem.

Remark. One can motivate this solution through small cases 2x 3y like 2x 17w , 2x 3y 7z ,
2x 11t .
Moreover, the stronger bound
n ≤ 2 · 3k−1
is true and best possible.

8
USA TSTST 2016 Solutions Evan Chen《陳誼廷》

§2.2 TSTST 2016/5, proposed by Linus Hamilton, Cynthia Stoner

Available online at https://aops.com/community/p6580545.

Problem statement

In the coordinate plane are finitely many walls, which are disjoint line segments,
none of which are parallel to either axis. A bulldozer starts at an arbitrary point
and moves in the +x direction. Every time it hits a wall, it turns at a right angle
to its path, away from the wall, and continues moving. (Thus the bulldozer always
moves parallel to the axes.)
Prove that it is impossible for the bulldozer to hit both sides of every wall.

We say a wall v is above another wall w if some point on v is directly above a point on w.
(This relation is anti-symmetric, as walls do not intersect).
The critical claim is as follows:

Claim — There exists a lowest wall, i.e. a wall not above any other walls.

Proof. Assume not. Then we get a directed cycle of some length n ≥ 3: it’s possible to
construct a series of points Pi , Qi , for i = 1, . . . , n (indices modulo n), such that the
point Qi is directly above Pi+1 for each i, the segment Qi Pi+1 does not intersect any
wall in its interior, and finally each segment Pi Qi is contained inside a wall. This gives
us a broken line on 2n vertices which is not self-intersecting.
Now consider the leftmost vertical segment Qi Pi+1 and the rightmost vertical segment
Qj Pj+1 . The broken line gives a path from Pi+1 to Qj , as well as a path from Pj+1 to
Qi . These clearly must intersect, contradiction.

Remark. This claim is Iran TST 2010.

Thus if the bulldozer eventually moves upwards indefinitely, it may never hit the
bottom side of the lowest wall. Similarly, if the bulldozer eventually moves downwards
indefinitely, it may never hit the upper side of the highest wall.

9
USA TSTST 2016 Solutions Evan Chen《陳誼廷》

§2.3 TSTST 2016/6, proposed by Danielle Wang

Available online at https://aops.com/community/p6580553.

Problem statement

Let ABC be a triangle with incenter I, and whose incircle is tangent to BC, CA,
AB at D, E, F , respectively. Let K be the foot of the altitude from D to EF .
Suppose that the circumcircle of 4AIB meets the incircle at two distinct points C1
and C2 , while the circumcircle of 4AIC meets the incircle at two distinct points B1
and B2 . Prove that the radical axis of the circumcircles of 4BB1 B2 and 4CC1 C2
passes through the midpoint M of DK.

¶ First solution (Allen Liu). Let X, Y , Z be midpoints of EF , F D, DE, and let G

be the Gergonne point. By radical axis on (AEIF ), (DEF ), (AIC) we see that B1 ,
X, B2 are collinear. Likewise, B1 , Z, B2 are collinear, so lines B1 B2 and XZ coincide.
Similarly, lines C1 C2 and XY coincide. In particular lines B1 B2 and C1 C2 meet at X.
A

B2
C2

F X

E
Y
G
Z
C1
B1
B D C
T
W

Note G is the symmedian point of DEF , so it is well-known that XG passes through

the midpoint of DK. So we just have to prove G lies on the radical axis.
First, note that 4DEF is the cevian triangle of the Gergonne point G. Set V =
XY ∩ AB, W = XZ ∩ AC, and T = BW ∩ CV .
We begin with the following completely projective claim.

10
USA TSTST 2016 Solutions Evan Chen《陳誼廷》

Claim — The points X, G, T are collinear.

Proof. It suffices to view 4XY Z as any cevian triangle of 4DEF (which is likewise any
cevian triangle of 4ABC). Then

• By Cevian Nest on 4ABC, it follows that AX, BY , CZ are concurrent.

• Hence 4BY V and 4CZW are perspective.

• Hence 4BZW and 4CY V are perspective too.

• Hence we deduce by Desargues theorem that T , X, and BZ ∩ CY are collinear.

• Finally, the Cevian Nest theorem applied on 4GBC (which has cevian triangles
4DF E, 4XZY ) we deduce G, X, and BZ ∩ CY , proving the claim.

One could also proceed by using barycentric coordinates on 4DEF .

Remark (Eric Shen). The first four bullets can be replaced by non-projective means: one
can check that BZ ∩ CY is the radical center of (BIC), (BB1 B2 ), (CC1 C2 ) and therefore
it lies on line XT .

Now, we contend point V is the radical center (CC1 C2 ), (ABC) and (DEF ). To see
this, let V 0 = ED ∩ AB; then (F V 0 ; AB) is harmonic, and V is the midpoint of F V 0 ,
and thus V A · V B = V F 2 = V C1 · V C2 .
So in fact CV is the radical axis of (ABC) and (CC1 C2 ).
Similarly, BW is the radical axis of (ABC) and (BB1 B2 ). Thus T is the radical center
of (ABC), (BB1 B2 ), (CC1 C2 ).
This completes the proof, as now XT is the desired radical axis.

¶ Second solution (Evan Chen). As before, we just have to prove G lies on the radical
axis.

11
USA TSTST 2016 Solutions Evan Chen《陳誼廷》

Q′
B2
C2
F
U′
Q V
X
P′ K U
P E
I
Y G T
M
Z W T′
C1 R S
B1

B R′ D S′ C

Construct parallelograms GP F Q, GRDS, GT U E such that P, R ∈ DF , S, T ∈ DE,

Q, U ∈ EF . As F G bisects P Q and is isogonal to F Z, we find P QED, hence P QRU , is
cyclic. Repeating the same logic and noticing P R, ST , QU not concurrent, all six points
P QRST U are cyclic. Moreover, since P Q bisects GF , we see that a dilation with factor
2 at G sends P Q to P 0 , Q0 ∈ AB, say, with F the midpoint of P 0 Q0 . Define R0 , S 0 ∈ BC
similarly now and T 0 , U 0 ∈ CA.
Note that EQP DS 0 is in cyclic too, as ]DS 0 Q = ]DRS = ]DEF . By homothety
through B, points B, P , X are collinear; assume they meet (EQP DS 0 ) again at V . Thus
EV QP DS 0 is cyclic, and now

]BV S 0 = ]P V S 0 = ]P QS = ]P T S = ]F ED = ]XEZ = ]XV Z

hence V lies on (BQ0 S 0 ).

Since F B k QP , we get EV F B is cyclic too, so XV · XB = XE · XF now; thus X
lies on the radical axis of (BS 0 Q0 ) and (DEF ). By the same argument with W ∈ BZ,
we get Z lies on the radical axis too. Thus the radical axis of (BS 0 Q0 ) and (DEF ) must
be line XZ, which coincides with B1 B2 ; so (BB1 B2 ) = (BS 0 Q0 ).
Analogously, (CC1 C2 ) = (CR0 U 0 ). Since G = Q0 S 0 ∩ R0 U 0 , we need only prove that
Q R0 S 0 U 0 is cyclic. But QRSU is cyclic, so we are done.
0

The circle (P QRST U ) is called the Lemoine circle of ABC.

12