A1. Find all ordered pairs (a, b) of positive integers for which
1 1 3
+ = .
a b 2018
Answer. The six ordered pairs are (1009, 2018), (2018, 1009), (1009 · 337, 674) =
(350143, 674), (1009 · 1346, 673) = (1358114, 673), (674, 1009 · 337) = (674, 350143),
and (673, 1009 · 1346) = (673, 1358114).
Solution. First rewrite the equation as 2 · 1009(a + b) = 3ab, and note that 1009
is prime, so at least one of a and b must be divisible by 1009. If both a and b are
divisible by 1009, say with a = 1009q, b = 1009r, then we have 2(q + r) = 3qr. But
qr ≥ q + r for integers q, r ≥ 2, so at least one of q, r is 1. This leads to the solutions
q = 1, r = 2 and r = 1, q = 2, corresponding to the ordered pairs (a, b) = (1009, 2018)
and (a, b) = (2018, 1009).
In the remaining case, just one of a and b is divisible by 1009, say a = 1009q. This
yields 2 · 1009(1009q + b) = 3 · 1009qb, which can be rewritten as
2 · 1009q = (3q − 2)b. Because the prime 1009 does not divide b, it must divide 3q − 2;
say 3q − 2 = 1009k. Then 1009k + 2 = 3 · 336k + k + 2 is divisible by 3, so
k ≡ 1 (mod 3). For k = 1, we get q = 337, a = 1009 · 337, b = 2q = 674. For k = 4,
we get q = 1346, a = 1009 · 1346, b = q/2 = 673. We now show there is no solution
with k > 4. Assuming there is one, the corresponding value of q is greater than 1346,
and so the corresponding
2q
b= · 1009
3q − 2
is less than 673. Because b is an integer, it follows that b ≤ 672, which implies
1 1 3 1 1 3
≥ > , contradicting + = .
b 672 2018 a b 2018
Finally, along with the two ordered pairs (a, b) for which a is divisible by 1009 and b
is not, we get two more ordered pairs by interchanging a and b.
A2. Let S1 , S2 , . . . , S2n −1 be the nonempty subsets of {1, 2, . . . , n} in some order, and let
M be the (2n − 1) × (2n − 1) matrix whose (i, j) entry is
(
0 if Si ∩ Sj = ∅;
mij =
1 otherwise.
Calculate the determinant of M .
Answer. The determinant is 1 if n = 1 and −1 if n > 1.
Solution. Note that if we take the nonempty subsets of {1, 2, . . . , n} in a different
order, this will replace the matrix M by P M P −1 for some permutation matrix P ,
and the determinant will stay unchanged. Denote the matrix M by Mn to indicate
its dependence on n. Then we will show that det(Mn+1 ) = −(det(Mn ))2 , from which
the given answer follows by induction on n because M1 has the single entry 1.
Using the order S1 , S2 , . . . , S2n −1 for the nonempty subsets of {1, 2, . . . , n}, we
arrange the nonempty subsets of {1, 2, . . . , n + 1} in the order
S1 , S2 , . . . , S2n −1 , {n + 1}, S1 ∪ {n + 1}, S2 ∪ {n + 1}, . . . , S2n −1 ∪ {n + 1}.
Then any of the first 2n − 1 subsets has empty intersection with {n + 1}, any two of
the last 2n subsets have nonempty intersection because they both contain n + 1, and
for any other choice of two nonempty subsets of {1, 2, . . . , n + 1}, whether they have
, nonempty intersection is completely determined by the relevant entry in Mn . Thus
the matrix Mn+1 has the following block form:
Mn 0n Mn
Mn+1 = 0nT 1 1nT ,
Mn 1n En
where 0n , 1n denote column vectors of length 2n − 1, all of whose entries are 0, 1
respectively, and En is the (2n − 1) × (2n − 1) matrix, all of whose entries are 1. To
find det(Mn+1 ), we subtract the middle row from each of the rows below it. This will
not affect the lower left block, it will change the lower part of the middle column from
1n to 0n , and it will replace the lower right block En by a block of zeros. Then we
can expand the determinant using the middle column (whose only nonzero entry is
now the “central” 1) to get
Mn Mn Mn O
det(Mn+1 ) = det = − det ,
Mn O Mn Mn
where the last step is carried out by switching the ith row with the (2n − 1 + i)th row
for all i = 1, 2, . . . , 2n − 1. (Because this is an odd number of row swaps, the sign of
the
determinant
is reversed.) Finally, the determinant of the block triangular matrix
Mn O
is equal to the product of the determinants of the diagonal blocks, so it
Mn Mn
equals (det(Mn ))2 , and the result follows.
10
P
A3. Determine the greatest possible value of cos(3xi ) for real numbers x1 , x2 , . . . , x10
i=1
10
P
satisfying cos(xi ) = 0.
i=1
480
Answer. The maximum value is .
49
Solution. Let zi = cos(xi ). Then the real numbers z1 , z2 , . . . , z10 must satisfy
−1 ≤ zi ≤ 1, and the given restriction on the xi is equivalent to the additional
restriction z1 + z2 + · · · + z10 = 0 on the zi . Also, note that
cos(3xi ) = cos(2xi ) cos(xi ) − sin(2xi ) sin(xi ) = (2 cos2 (xi ) − 1) cos(xi ) − 2 sin2 (xi ) cos(xi )
= 2 cos3 (xi ) − cos(xi ) − 2(1 − cos2 (xi )) cos(xi ) = 4zi3 − 3zi .
Thus we can rephrase the problem as follows: Find the maximum value of the
function f given by
10
X 10
X
f (z1 , . . . , z10 ) = (4zi3 − 3zi ) = 4 zi3
i=1 i=1
on the set
S = {(z1 , . . . , z10 ) ∈ [−1, 1]10 | z1 + · · · + z10 = 0}.
Because f is continuous and S is closed and bounded (compact), f does take
on a maximum value on this set; suppose this occurs at (m1 , . . . , m10 ) ∈ S. Let
1 1 3
+ = .
a b 2018
Answer. The six ordered pairs are (1009, 2018), (2018, 1009), (1009 · 337, 674) =
(350143, 674), (1009 · 1346, 673) = (1358114, 673), (674, 1009 · 337) = (674, 350143),
and (673, 1009 · 1346) = (673, 1358114).
Solution. First rewrite the equation as 2 · 1009(a + b) = 3ab, and note that 1009
is prime, so at least one of a and b must be divisible by 1009. If both a and b are
divisible by 1009, say with a = 1009q, b = 1009r, then we have 2(q + r) = 3qr. But
qr ≥ q + r for integers q, r ≥ 2, so at least one of q, r is 1. This leads to the solutions
q = 1, r = 2 and r = 1, q = 2, corresponding to the ordered pairs (a, b) = (1009, 2018)
and (a, b) = (2018, 1009).
In the remaining case, just one of a and b is divisible by 1009, say a = 1009q. This
yields 2 · 1009(1009q + b) = 3 · 1009qb, which can be rewritten as
2 · 1009q = (3q − 2)b. Because the prime 1009 does not divide b, it must divide 3q − 2;
say 3q − 2 = 1009k. Then 1009k + 2 = 3 · 336k + k + 2 is divisible by 3, so
k ≡ 1 (mod 3). For k = 1, we get q = 337, a = 1009 · 337, b = 2q = 674. For k = 4,
we get q = 1346, a = 1009 · 1346, b = q/2 = 673. We now show there is no solution
with k > 4. Assuming there is one, the corresponding value of q is greater than 1346,
and so the corresponding
2q
b= · 1009
3q − 2
is less than 673. Because b is an integer, it follows that b ≤ 672, which implies
1 1 3 1 1 3
≥ > , contradicting + = .
b 672 2018 a b 2018
Finally, along with the two ordered pairs (a, b) for which a is divisible by 1009 and b
is not, we get two more ordered pairs by interchanging a and b.
A2. Let S1 , S2 , . . . , S2n −1 be the nonempty subsets of {1, 2, . . . , n} in some order, and let
M be the (2n − 1) × (2n − 1) matrix whose (i, j) entry is
(
0 if Si ∩ Sj = ∅;
mij =
1 otherwise.
Calculate the determinant of M .
Answer. The determinant is 1 if n = 1 and −1 if n > 1.
Solution. Note that if we take the nonempty subsets of {1, 2, . . . , n} in a different
order, this will replace the matrix M by P M P −1 for some permutation matrix P ,
and the determinant will stay unchanged. Denote the matrix M by Mn to indicate
its dependence on n. Then we will show that det(Mn+1 ) = −(det(Mn ))2 , from which
the given answer follows by induction on n because M1 has the single entry 1.
Using the order S1 , S2 , . . . , S2n −1 for the nonempty subsets of {1, 2, . . . , n}, we
arrange the nonempty subsets of {1, 2, . . . , n + 1} in the order
S1 , S2 , . . . , S2n −1 , {n + 1}, S1 ∪ {n + 1}, S2 ∪ {n + 1}, . . . , S2n −1 ∪ {n + 1}.
Then any of the first 2n − 1 subsets has empty intersection with {n + 1}, any two of
the last 2n subsets have nonempty intersection because they both contain n + 1, and
for any other choice of two nonempty subsets of {1, 2, . . . , n + 1}, whether they have
, nonempty intersection is completely determined by the relevant entry in Mn . Thus
the matrix Mn+1 has the following block form:
Mn 0n Mn
Mn+1 = 0nT 1 1nT ,
Mn 1n En
where 0n , 1n denote column vectors of length 2n − 1, all of whose entries are 0, 1
respectively, and En is the (2n − 1) × (2n − 1) matrix, all of whose entries are 1. To
find det(Mn+1 ), we subtract the middle row from each of the rows below it. This will
not affect the lower left block, it will change the lower part of the middle column from
1n to 0n , and it will replace the lower right block En by a block of zeros. Then we
can expand the determinant using the middle column (whose only nonzero entry is
now the “central” 1) to get
Mn Mn Mn O
det(Mn+1 ) = det = − det ,
Mn O Mn Mn
where the last step is carried out by switching the ith row with the (2n − 1 + i)th row
for all i = 1, 2, . . . , 2n − 1. (Because this is an odd number of row swaps, the sign of
the
determinant
is reversed.) Finally, the determinant of the block triangular matrix
Mn O
is equal to the product of the determinants of the diagonal blocks, so it
Mn Mn
equals (det(Mn ))2 , and the result follows.
10
P
A3. Determine the greatest possible value of cos(3xi ) for real numbers x1 , x2 , . . . , x10
i=1
10
P
satisfying cos(xi ) = 0.
i=1
480
Answer. The maximum value is .
49
Solution. Let zi = cos(xi ). Then the real numbers z1 , z2 , . . . , z10 must satisfy
−1 ≤ zi ≤ 1, and the given restriction on the xi is equivalent to the additional
restriction z1 + z2 + · · · + z10 = 0 on the zi . Also, note that
cos(3xi ) = cos(2xi ) cos(xi ) − sin(2xi ) sin(xi ) = (2 cos2 (xi ) − 1) cos(xi ) − 2 sin2 (xi ) cos(xi )
= 2 cos3 (xi ) − cos(xi ) − 2(1 − cos2 (xi )) cos(xi ) = 4zi3 − 3zi .
Thus we can rephrase the problem as follows: Find the maximum value of the
function f given by
10
X 10
X
f (z1 , . . . , z10 ) = (4zi3 − 3zi ) = 4 zi3
i=1 i=1
on the set
S = {(z1 , . . . , z10 ) ∈ [−1, 1]10 | z1 + · · · + z10 = 0}.
Because f is continuous and S is closed and bounded (compact), f does take
on a maximum value on this set; suppose this occurs at (m1 , . . . , m10 ) ∈ S. Let
