USA Mathematical Talent Search

Round 3 Solutions
Year 33 — Academic Year 2021–2022
www.usamts.org

1/3/33. In the grid below, draw horizontal and vertical segments of unit length joining pairs
of adjacent dots (some have been given to you) so that

1. every dot is connected by line segments to exactly 1 or 3 adjacent dots,

2. any dot can be reached from any other dot by following a path of segments, and

3. no area is completely enclosed by segments.

Note: “Unit length” is the length between two adjacent dots when there is no missing
dot between them. For example, we cannot draw a vertical line segment down from the dot
Create PDF with GO2PDF for free, if you wish to remove this line, click here to buy Virtual PDF Printer

in the top right corner because the length of this segment would be 2 units.

There is a unique solution, but you do not need to prove that your answer is the only
one possible. You merely need to find an answer that satisfies the constraints above. (Note:
In any other USAMTS problem, you need to provide a full proof. Only in this problem is
an answer without justification acceptable.)

Solution
 USA Mathematical Talent Search
Round 3 Solutions
Year 33 — Academic Year 2021–2022
www.usamts.org

2/3/33. Sydney the squirrel is at (0, 0) and is trying to get to (2021, 2022). She can move only
by reflecting her position over any line that can be formed by connecting two lattice points,
provided that the reflection puts her on another lattice point. Is it possible for Sydney to
reach (2021, 2022)?

Lattice points are points in the Cartesian plane where both coordinates are integers.

Solution
Create PDF with GO2PDF for free, if you wish to remove this line, click here to buy Virtual PDF Printer
We claim that it is impossible for Sydney to reach (2021, 2022).

Call a lattice point even if the sum of its coordinates is even, and odd if the sum of its
coordinates is odd. For a lattice point to be even, either both coordinates must be even or
both coordinates must be odd. For a lattice point to be odd, one coordinate must be even
and the other coordinate must be odd.

We claim that if Sydney starts at an even lattice point and is only allowed to step on
lattice points, then she can only reach even lattice points. To see this, suppose otherwise.
Then there is an even lattice point, without loss of generality (0, 0), that can reach an odd
lattice point (a, b). The midpoint of the line segment connecting these points is (a/2, b/2),
and hence the equation of the segment’s perpendicular bisector must be

y − b/2 = (−a/b)(x − a/2).

This rearranges to
2(ax + by) = a2 + b2 .
But since (a, b) is odd, exactly one of a, b is odd and the other is even, hence the right-hand
side is odd. This means that the left-hand side is odd, meaning that ax + by cannot be an
integer. Thus, any point (x, y) lying on the line cannot be a lattice point. Since Sydney can
move only by reflecting her position over a line that contains lattice points, Sydney cannot
move from an even lattice point to an odd lattice point.

Since (0, 0) is even and (2021, 2022) is odd, it is impossible for Sydney to reach (2021, 2022).
 USA Mathematical Talent Search
Round 3 Solutions
Year 33 — Academic Year 2021–2022
www.usamts.org

3/3/33. Let n be a positive integer. Let S be the set of n2 cells in an n × n grid. Call a subset
T of S a double staircase if

1. T can be partitioned into n horizontal nonoverlapping rectangles of dimensions 1 × 1,

1 × 2, ..., 1 × n, and

2. T can also be partitioned into n vertical nonoverlapping rectangles of dimensions 1 × 1,

2 × 1, ..., n × 1.

In terms of n, how many double staircases are there? (Rotations and reflections are consid-
Create PDF with GO2PDF for free, if you wish to remove this line, click here to buy Virtual PDF Printer
ered distinct.)

An example of a double staircase when n = 3 is shown below.

Solution
The answer is 4n−1 . Call a permutation of 1, 2, . . . , k a mountain if no three consecutive
elements a, b, c satisfy b = min(a, b, c). Let xk be the number of mountains with k numbers.
Our first claim is that xn = 2n−1 , and our second claim is that the answer to this problem
is x2n .

We start with the first claim that xn = 2n−1 . It is clear that x1 = 1; we will now prove
that xk = 2xk−1 for all k ≥ 2. In a mountain with k elements, the 1 must be first or last,
which has 2 choices. The remaining k − 1 elements form a mountain when all the numbers
are decreased by one. So xk = 2xk−1 , which together with x1 = 1 means xn = 2n−1 .

Now we show the second claim that there are x2n double staircases. The existence of a
horizontal 1 × n rectangle means all n columns are nonempty, and similarly the vertical n × 1
rectangle means all n rows are nonempty. So the n horizontal rectangles are all in different
rows, and similarly the n vertical rectangles are all in different columns.

Let H be the sequence of horizontal rectangle sizes by row, and similarly define V .
We claim both H and V are mountains. Suppose H contains three elements a, b, c with
b = min(a, b, c). Without loss of generality, we assume the n in H comes before b. Be-
cause c > b, there exists a column containing a cell of the 1 × c rectangle but not the 1 × b
rectangle. This column contains a cell of the 1 × n rectangle too, which means the column
 USA Mathematical Talent Search
Round 3 Solutions
Year 33 — Academic Year 2021–2022
www.usamts.org

contains a cell, a gap, and a cell in order (not necessarily consecutive). This contradicts our
previous conclusion that each column contains a single vertical rectangle tile. Therefore H
is a mountain, and similarly V is a mountain.

For our final step, we prove any pair H and V of mountains gives exactly one double
staircase. The fact that each row contains one horizontal tile and each column contains one
vertical tile makes it clear at most one such subset exists. To show a double staircase exists
for any mountains H and V , let T contain the squares whose row and column sizes form H
and V sum to at least n + 1. For any k with 1 ≤ k ≤ n, there are exactly k numbers m with
Create PDF with GO2PDF for free, if you wish to remove this line, click here to buy Virtual PDF Printer
1 ≤ m ≤ n and m + k ≥ n + 1, so all the row and column sizes will be correct. Because H
and V are mountains, for any k the numbers n, n − 1, n − 2, . . . , n − k + 1 form a consec-
utive block in H and V in some order, so each row or column can be formed from a single
horizontal or vertical tile. This shows that T works. Therefore, exactly one double staircase
exists given any pair of mountains H and V , so the number of double staircases is x2n = 4n−1 .
 USA Mathematical Talent Search
Round 3 Solutions
Year 33 — Academic Year 2021–2022
www.usamts.org

4/3/33. Let ABC be a triangle whose vertices are inside a circle Ω. Prove that we can choose
two of the vertices of ABC such that there are infinitely many circles ω that satisfy the
following properties:

1. ω is inside of Ω,

2. ω passes through the two chosen vertices, and

3. the third vertex is in the interior of ω.

Create PDF with GO2PDF for free, if you wish to remove this line, click here to buy Virtual PDF Printer

Solution
Let O be the center of Ω. Suppose the circumcircle of ABC is completely contained
within Ω. Without loss of generality let minor arc AB of the circumcircle of ABC not
contain point C. Let M be the midpoint of AB, let N be the midpoint of minor arc AB, let
P be a point on the open segment M N , and let γP denote the circumcircle of ABP. Since
C is on the circumcircle of ABN, we know that C is in the interior of the circumcircle of γP
(i.e. ∠AP B + ∠ACB > 180◦ ). When P = N we know γP is completely contained in Ω and
taking P to be any point sufficiently close to N will have the same result by continuity.

N
A
P
M B

C γP

Now we consider the case when the circumcircle is not completely contained in Ω. With-
out loss of generality, we assume that AO, BO ≤ CO. Consider the circle γ centered at
O passing through C. If either A or B is on γ, then the other is strictly inside γ and we
proceed exactly as in the next case.

Let γr be the image of γ under the homothety centered at C with factor r. As r shrinks
from 1 toward 0, eventually γr will first intersect exactly one of A or B (it cannot intersect
both simultaneously or the circumcircle of ABC would be completely inside of Ω). Call this
circle γ 0 . Without loss of generality we will assume γ 0 passes through C and B.
 USA Mathematical Talent Search
Round 3 Solutions
Year 33 — Academic Year 2021–2022
www.usamts.org

γ!

A
γ
C

0 to buy Virtual PDF Printer

Then we can see that γ is one circle satisfying the conditions of the problem. Let P be
Create PDF with GO2PDF for free, if you wish to remove this line, click here

the midpoint of minor arc BC on γ 0 . Then, by adjusting P slightly on the perpendicular

bisector of BC, we can ensure the resulting circumcircles of BCP do not intersect Ω and
contain A.
 USA Mathematical Talent Search
Round 3 Solutions
Year 33 — Academic Year 2021–2022
www.usamts.org

5/3/33. Let a, b, c, d be positive real numbers. Prove that d is an integer if and only if there
are positive real numbers e, f satisfying
$ % 
x+a

c

b
+ x+e
=
d f

for all real numbers x. (For a real y, byc is the greatest integer less than or equal to y.)

Solution
Create PDF with GO2PDF for free, if you wish to remove this line, click here to buy Virtual PDF Printer

First, we will show that if e, f exist, then d is a positive integer. We start this by showing
that f = bd. Let x = N b − a for a variable integer N . Then the condition becomes
   
N c N e−a
+ = + .
d d f /b f

For byc = bzc to be true, we must have |y − z| < 1. Therefore, for all integers N , we have
 
N c N e − a 
 + − −  < 1.
d d f /b f 

Simplifying,    
N 1 − b + c − e − a  < 1.
 
 d f d f 
If d1 6= fb , then we can choose an N for which the expression inside the absolute value is as
large as we want, which would violate the inequality. Therefore, d1 = fb , or f = bd, as desired.

For k an integer, let L(k) be the set of x for which the left side of the original expression
is equal to k, and similarly define R(k) for the right side. Observe that no matter what e
we choose, for any k, R(k) is always an interval of length f , or rather length bd. Therefore,
L(k) must also be an interval of length bd for every k.

On the other hand, L(k) is the set of values for which

 
x+a
kd ≤ + c < kd + d.
b

Or, equivalently 
x+a
0≤ + c − kd < d.
b
The floor term in the middle equals a particular integer m exactly when x is in an interval
of length b, regardless of m and a. So the length of the interval L(k) is b times the number
of integers m for which the above inequality holds. But this length must also equal bd.
 USA Mathematical Talent Search
Round 3 Solutions
Year 33 — Academic Year 2021–2022
www.usamts.org

Therefore, d must be an integer, as desired.

Now we do the other direction: we show e, f exist if d is a positive integer. We start with
the following lemma.

Lemma: If q is a positive integer and r is a real number, then for all integers n, we have
   
n+r n + brc
= .
q q
Create PDF with GO2PDF for free, if you wish to remove this line, click here to buy Virtual PDF Printer
Proof: The left side is equal to k exactly when

kq ≤ n + r < kq + q.

Because kq and kq+q are both integers, only the integer part of the middle expression matters
for determining whether the inequality is satisfied. So the inequality above is equivalent to

kq ≤ bn + rc < kq + q.

We simplify the middle expression:

kq ≤ n + brc < kq + q.

This is exactly the condition for the right side to equal k. So both sides of the equation are
the same, and the lemma is proven.

Instead of choosing e, f now, we will derive the equation we want from the ground up
and find the values at the end. To start, for any real x, there exists an integer k and a real
number r with 0 ≤ r < b such that x = kb − a + r. This implies that
 
x+a
k= .
b

Next, observe that since 0 ≤ r/b < 1, we have bcc + rb = bcc for all such r. So we have
 

that for all integers k and r with 0 ≤ r < b that

 $ %
k + bcc + rb
 
k + bcc
= .
d d

Applying the lemma to both sides of the equation, we have

k + bcc + rb
   
k+c
= .
d d
This implies that    
k+c kb − a + r + bbcc + a
= .
d bd
 USA Mathematical Talent Search
Round 3 Solutions
Year 33 — Academic Year 2021–2022
www.usamts.org

Recall that both x = kb − a + r and k = x+a

 
b
. We substitute both identities into the above,
obtaining that for all x, $ % 
x+a

c

b
+ x + bbcc + a
= .
d bd
This is the equation we wanted if we set f = bd and e = bbcc + a. The proof is now complete.

Create PDF with GO2PDF for free, if you wish to remove this line, click here to buy Virtual PDF Printer

Problems by Thomas Lam, Kevin Ren, and USAMTS Staff.

c 2022 Art of Problem Solving Initiative, Inc.