Solutions Australian Mathematical Olympiad Committee

Mixed 1 2021 Mentor Program

Y1. For a positive integer n let R(n) be the number obtained by writing the digits of n in reverse
order. The number n is called a palindrome if n = R(n).
Find all three-digit numbers n such that n ⇥ R(n) is a five digit palindrome.

Answers 101, 102, 201, 202, 111, 112, 211, 212, 121, 122, 221
Solution
If n ends in a zero, then nR(n) also ends in a zero and thus cannot be a palindrome.
Write n = 100a + 10b + c where a, c 6= 0. Then

nR(n) = (100a + 10b + c)(100c + 10b + a)

= 10000ac + 1000b(a + c) + 100(a2 + b2 + c2 ) + 10b(a + c) + ac.

Since this number has 5 digits, we must have ac  9.

If b(a + c) > 9 then the leftmost digit will be greater than ac and thus cannot be equal to the
rightmost digit. Thus b(a + c)  9.
Similarly a2 + b2 + c2  9.
Since a, c 1, we have b2  7. Thus b = 0, 1, 2.
If b = 0 we want a2 + c2  9 thus 1  a, b  2.
If b = 1, we want a + c  9 and a2 + c2  8 and ac  9. Thus again 1  a, b  2.
If b = 2, we want a + c  4, a2 + b2  5, ac  9. Thus (a, b) = (1, 1); (1, 2) or (2, 1).
Thus the answers are 101, 102, 201, 202, 111, 112, 211, 222, 121, 122 and 221. (But not 222.) ⇤

33
Solutions Australian Mathematical Olympiad Committee
Mixed 1 2021 Mentor Program

Y2. Tim is teaching a class of 14 students. He asks each student the following two questions:
• “How many other students in the class have the same first name as you?”
• “How many other students have the same last name as you?”
It turns out that each number from 0 to 6 occurs among the 28 answers.
(a) Prove that there are two students with the same first name and the same last name.
(b) A student is called unique if no other student in the class has the same first name and the same
last name. Find the maximum possible number of unique students.

Answer (a) – (b) 7

(a) Let G be the bipartite graph whose blue vertices are the set of first names and whose red vertices
are the set of last names. An edge between a blue vertex and a red vertex corresponds to a
person having that first name and that last name. Thus there are exactly 14 edges. We want
to prove that G contains a double edge.
Solution 1
The given data tells us that for n = 1, 2, 3, 4, 5, 6, 7, there is at least one vertex of degree n.
So the total degree is at least 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Since there are 14 edges, the
total degree is exactly 14 ⇥ 2 = 28. Hence for n = 1, 2, 3, 4, 5, 6, 7, there is exactly one vertex of
degree n and no other degrees occur. This implies that the graph has exactly 7 vertices.
Consider the vertex of degree 7. Since G contains exactly 7 vertices, this vertex is connected to
at most 6 other other vertices, and so by the pigeonhole principle there is a double edge. ⇤
Solution 2
The total valence of blue vertices is 14, as is the total valence of red vertices. Thus the total
number of possible pairs consisting of a red vertex and a blue vertex is either 1 ⇥ 6, 2 ⇥ 5 or
3 ⇥ 4, all of which are less than 14. So one of these pairs occurs at least twice as an edge. ⇤
(b) Solution
As in solution 2 to part (a), the total valence of blue vertices is equal to 14, as is the total
valence of red vertices. This implies that the valence set of one colour (WLOG blue) is one
of (i) {7, 6, 1}, (ii) {7, 5, 2}, (iii) {7, 4, 3}, (iv) {6, 5, 3}. Let us examine possibilities for edges
between red and blue vertices. The total number of red-blue pairs is 3 ⇥ 4 = 12. Let D, N, S
denote the number of red-blue pairs having at least 2, exactly 1, exactly 0, respectively, edges
between them. Note that S = 12 D N .
Estimate D : By the pigeonhole principle double edges are incident at the following vertices:
(i) 7,6; (ii) 7,5; (iii) 6,5 (these are red vertices); (iv) 6,5. Thus D 2
Estimate N : In (i) 1 is not connected to (at least) three of {2, 3, 4, 5}. In (ii) 2 is not connected
to two of {1, 3, 4, 6} and 1 is not connected to two of {2, 5, 7}. In (iii) 1 is not connected to
two of {3, 4, 7} and 2 is not connected to one of {3, 4, 7}. In (iii) 1 is not connected to two of
{3, 5, 6} and 2 is not connected to one of {3, 5, 6}. Thus N 3.
From above, S = 12 D N  12 3 2 = 7. The following example shows that 7 is possible.
2 3 4 5

1 6 7 ⇤

34
Solutions Australian Mathematical Olympiad Committee
Mixed 1 2021 Mentor Program

p
Y3. Let a 6= 2 be a given positive real number. Let x1 , x2 , . . . be a sequence of real numbers which
satisfy x1 = a and xn+1 = x2n + x1n .
p p 1
Prove that there exists an integer m such that 2 < xm < 2 + 22012 .

Solution
⇣ ⌘ p p
1 2
For n 1 we have xn+1 = 2
xn + xn
2 by the AM–GM. Thus xn > 2 for n > 1.
x2n +2
Furthermore, the inequality xn > xn+1 = 2xn
now holds true for n > 1 because it reduces to x2n > 2
which we have already proven.
p p
Thus x2 , x3 , . . . is a decreasing sequence bounded below by 2. Write xn = 2 + "n for each n > 1.
Then p p
p 2 + "n 1 2 + "n 1 p "n
2 + "n+1 = +p < + p = 2+ .
2 2 + "n 2 2 2
"n
Thus "n+1 < 2 . This proves that the error term becomes arbitrarily small. In particular there is a
1
value of m such that "m < 22012 as wanted. ⇤

35
Solutions Australian Mathematical Olympiad Committee
Mixed 1 2021 Mentor Program

Y4. Let M and N be the two intersection points of two circles 1 and 2 . Let A and D be points
on 1 and 2 , respectively. Lines AM and AN intersect 2 for the second time at points B and C,
respectively. Lines DM and DN intersect 1 for the second time at points E and F , respectively.
Furthermore it is known that points M , N , F , A, E are cyclic in that order around 1 and that
AB = DE.
Prove that points A, F , C and D are cyclic.

Solution
Since \N EM = \N AM and \M DN = \M BN , we have 4N ED ⇠ 4N AB (AA).
Similar switching yields 4N EA ⇠ 4N DB.
Since AB = ED this yields 4N AB ⌘ 4N ED.
Thus AN = N E and N B = N D. Hence N AB and N ED are similar isosceles triangles with common
apex N . It follows that
\N F A = \N EA = \DBN = \DCN
and so AF CD is cyclic. ⇤

A
D

C B
F
E

36
Solutions Australian Mathematical Olympiad Committee
Mixed 1 2021 Mentor Program

Y5. Find the number of partitions of the set {1, 2, . . . , n} into three subsets A1 , A2 , A3 , some of
which may be empty, such that the following conditions are satisified:

(i) After the elements of every subset have been put in ascending order, every two consecutive
elements of any subset have di↵erent parity.
(ii) If A1 , A2 , A3 are all nonempty, then in exactly one of them the minimal number is even.

Answer 2n 1

Solution
WLOG let 1 2 A1 and WLOG if A2 is nonempty then its minimal element is even and WLOG if
A3 is nonempty then its minimal element is an odd number greater than 1. To make A2 and A3
nonempty we artificially add 1 to A2 and 0 to A3 to make them nonempty. Note that this does not
change a thing except now that no set is empty.
We now claim inductively that as we add the numbers 2, 3, . . . , n to one of A1 , A2 , A3 one at a time,
there are exactly two possibilities at each stage.
The parity sequence of the maximal elements of A1 , A2 , A3 before 2 is added is (1, 1, 0). Thus 2
may be placed in either A1 or A2 but not A3 . Thus after 2 is placed the parity sequence is (0, 1, 0)
or (1, 0, 0). Thus there are two possibilities for placing 3 resulting in parity sequences of (1, 1, 0) or
(1, 0, 1) or (0, 1, 1). From here on placing an even number results in a parity sequence of (1, 0, 0, ) or
(0, 1, 0) or (1, 0, 0) leaving exactly two possibilities for placing the next odd number. When this next
odd number is placed it results in the parity sequence (1, 1, 0) or (1, 0, 1) or (0, 1, 1) leaving exactly
two possibilities for placing the next even number. Thus we have established our claim.
Since there are n 1 numbers to be placed, each having two possible placements, this implies that
the answer is 2n 1 . ⇤

37
Solutions Australian Mathematical Olympiad Committee
Mixed 1 2021 Mentor Program

Y6. In this problem k denotes a positive integer.

(a) For which k do there exist two distinct integers lying strictly between k 2 and (k + 1)2 , whose
product is a perfect square?
(b) For which k do there exist three distinct integers lying strictly between k 3 and (k + 1)3 , whose
product is a perfect cube?
(c) For which k do there exist four distinct integers lying strictly between k 4 and (k + 1)4 , whose
product is a perfect fourth power?

(Note that x is said to lie strictly between y and z if y < x < z.)

Answers (a) not possible for any k (b) all k 2 (c) all k 1
Solution

(a) We show that no such integers a, b exist.

Suppose, for the sake of contradiction, that there are integers a, b such that k 2 < a < b < (k+1)2
and ab is a perfect square.
Let a = ms2 where m > 1 is square-free. Since ab is square, b = mt2 for some integer t s + 1.
Then ( k+1
k
)2 > ab = ( st )2 ( s+1
s
)2 . Thus k < s. But then b = mt2 m(s + 1)2 > (k + 1)2 .
Contradiction. ⇤
(b) We look for numbers a, b which satisfy k 3 < a2 < ab < b2 < (k + 1)3 . To this end let a2 be the
smallest square which is greater than k 3 and let b = a + 1. Thus (a 1)2  k 3 < a2 . Thus
3 3 3
k 2 < a  1 + k 2 and b = a + 1  2 + k 2 . We now only need b2 < (k + 1)3 to hold, i.e.
3 3
4 + 4k 2 + k 3 < (k + 1)3 = k 3 + 3k 2 + 3k + 1 , 3k 2 + 3k + 1 > 4 + 4k 2 .
p 3 3
But for k 2 we have 3k + 1 > 4 and 3k 2 3 2k 2 > 4k 2 . So the inequality holds for k 2.
For the k = 1 it is obvious that 5 and 7 can’t be used. This leaves 2, 3, 4, 6. But no three of
these multiply to a perfect cube because the product is divisible by 3 but not by 27. ⇤
4
(c) Let a be such that (a 1)3  k 4 < a3 . Thus a  1 + k 3 . Let b = a + 1 and c = a + 2. Our
numbers shall be a3 , b3 , ac2 , bc2 . Note that these are increasing order and have product equal to
(abc)4 . We now only need bc2 = (a + 1)(a + 2)2 < (k + 1)4 , i.e.
4 4 8 4
(2 + k 3 )(3 + k 3 )2 < (k + 1)4 , 17 + 8k 3 + 21k 3 < 4k 3 + 6k 2 + 4k.
8 4
But for k 8 we have 8k 3  4k 3 and 21k 3 < 6k 2 and 17 < 4k. So it works for all k 8.
The case k = 1 works with 3, 6, 8, 9 since the product is 1296 = 64 .
The case k = 2 works with 3r, 6r, 8r, 9r for r = 7 (and r = 8).
For k = 3, 4, 5, 6, 7, we seek quadruples that are closer together. To do this, replace r with 10
from the case k = 2 to get 30, 60, 80, 90. Then shu✏e factors by replacing 30 with 50 and 90
with 54. (Thus the case k = 2 also works with 50, 54, 60, 80, but this is merely a side point.)
Then, k = 3, 4, 5, 6, 7 work with 50r, 54r, 60r, 80r for r = 2, 6, 15, 30, 50, respectively. ⇤

38