Parabola Volume 49, Issue 3 (2013)

2013 University of New South Wales School Mathematics

Competition
Junior Division – Problems and Solutions

Problem 1
Suppose that x, y, z are non-zero integers with no common factor except 1 such
that
x2 + y 2 = z 2 .
Prove that exactly one of these integers is a multiple of 5.

Solution
Let x, y, z ∈ Z, x, y, z 6= 0
gcd(x, y, z) = 1.
Now
x ≡ 0 1 2 3 4 mod 5
x2 ≡ 0 1 4 4 1 mod 5
2x2 ≡ 0 2 3 3 2 mod 5
So, if x ≡ y mod 5, then

z 2 = x2 + y 2 ≡ 2x2 mod 5

is possible if and only if

x≡y≡z≡0 mod 5.
This contradicts to
gcd(x, y, z) = 1.

So x 6≡ y mod 5. Thus, we have

x2 + y 2 ≡ 0 + 1(in some order) ≡1 (0.1)

or ≡ 0 + 4... ≡4 (0.2)
or ≡ 1 + 4... ≡0 (0.3)
or ≡ 4 + 4... ≡3 (0.4)

Since z 2 ≡ 3 is impossible, (0.4) cannot occur. So either (0.1), (0.2) or (0.3) occurs.
In (0.1) or (0.2) exactly one of x, y ≡ 0 mod 5; and in (0.3) neither of x, y ≡ mod 5
and z ≡ 0 mod 5.

1
Problem 2
How many integers between 100 and 100000 have exactly three identical digits
in their decimal representation. For example, 11123 and 10020 are such numbers
but 12121 is not.
Solution
The only 6-digit number in the range is 100000 fails the condition so the required
numbers have 3, 4 or 5 digits.
Let α represents the number of integers with repeating 0 and β the number of
integers with repeating non-zero digit.
For the integers computed by α, the leading digit is non-zero, so

α = α4 + α5 ,

where αj is the number of j-digit integers counted by α. So

 
j−1
9 ×
αj = |{z} × P (8, j − 4),
3 | {z }
A | {z } C
B

where A stands for the choice for the leading digit; B stands for the choice of
the places for the repeating zero; and C represents filling the remaining j − 4
positions with other digits with no repetitions. So, we compute

α = α4 + α5
 
4
=9 × 1 × 1 + 9 × ×8
3
=9 + 9 × 4 × 8
= 9 × 33 = 297.

We split the integers counted by β into three subgroups:

β = β3 + β4 + β5 ,

where βj is the number of j-digit integers within β.

Within integers counted by β, repeating digit may or may not include leading
digit, so we compute
  
j−1
9 × |{z}
βj = |{z} 1 × × P (9, j − 3)
2 | {z }
A B | {z } D
 C  
j−1
8 ×
+ |{z} × P (8, j − 4) ,
3 | {z }
B0 | {z } D0
C0

2
 where A chooses the non-zero repeating digit; B puts that digit into the leading
position; C chooses two other positions for the remaining repeating digits; D
fills the rest with no repetition; B 0 chooses another non-zero digit for the leading
position; C 0 chooses positions for the repeating digit; D0 fills the rest with no
repetition.
Skipping some elementary computations, we conclude that

β = 6516 and α + β = 6813.

Problem 3

1. Find the number which is divisible by 2 and 9 and which has 14 divisors
(including 1 and the number itself).
2. Show that there are multiple solutions in the case when the number has 15
divisors.

Solution
Let
n = 2α1 3α2 pα3 3 · . . . · pαr r
be factorisation of n into distinct primes

2 < 3 < p3 < . . . < pr

such that all αj > 0 and r ≥ 2. So

2|n → α1 ≥ 1
3|n → α2 ≥ 2

Observe that the number of divisors of n is

d(n) = (α1 + 1)(α2 + 1) · . . . · (αr + 1)

and
α1 + 1 ≥ 2 and α2 + 1 ≥ 3.

1. If d(n) = 14 = 2 × 7, then r = 2 and α1 + 1 = 2, α2 + 2 = 7. So

α1 = 1 and α2 = 6

and
n = 21 × 36 = 1458.
2. If d(n) = 15 = 3 × 5, then r = 2 and

α1 + 1 = 3 and α2 + 2 = 5

3
 or
α1 + 1 = 5 and α2 + 2 = 3.
So
α1 = 2, α2 = 4 and n = 22 · 34 = 324
or
α1 = 4, α2 = 2 and n = 24 × 32 = 144.

Problem 4

1. The plan of an art museum is an equilateral triangle consisting of 36 triangu-

lar exhibition halls (see the diagram). Each hall has passages into all adjacent
halls. Prove that you can visit at most 31 halls if you plan to enter each hall
at most once.

2. Subject to the condition that each hall is visited at most once, find the largest
number of halls that can be visited in the case that the museum is an equi-
lateral triangle and that it has k 2 exhibition halls, where k is an integer.

Solution
This problem is also in the Senior Division. See the solution given there.

Problem 5
We wish to label the vertices of a regular polygon with 45 sides using the dig-
its 0, 1, . . . , 9. Can this be done such that for every pair of digits there is an edge
labelled by these digits?
Solution
Such labelling cannot be done. A digit ’a’ forms 9 pairs with other digits. To
accommodate these pairs, the digit ’a’ must be next to at least 5 vertices. So, at
least 50 vertices are required.

Problem 6
You are given n different weights and a balance. On every move, you add one
more weight to one of the sides of the balance.

4
 1. Prove that there is a strategy such that the left hand side of the balance is
lower after the first move; the right hand side of the balance is lower after
the second move; the left hand side is lower after the third move; and so on.
2. We assign the “word” LRLRLR. . . to the strategy above. The letter ‘L’ means
that the left hand side is lower; the letter ‘R’ means that the right hand side
is lower.
For any “word” of length n of letters ‘L’ and ‘R’, find a strategy which will
correspond to that word according to the rules above.

Solution
The strategy is based on the following lemma.
Lemma Let m1 < m2 < . . . < mk . If

Sodd = m1 + m3 + . . . and Seven = m2 + m4 + . . . ,

then
Seven > Sodd if k even
and
Sodd > Seven if k odd.
That is, the sum which has the heaviest weight is the largest.
Proof of Lemma The proof has two parts. If k is even, then we add the following
inequalities:
m1 < m2
m3 < m4
..
.
mk−1 < mk
On the other hand, if k is odd, then we add the following inequalities

0 < m1
m2 < m3
..
.
mk−1 < mk

Now the required strategy is described as follows. It is convenient to describe the

strategy in reverse. That is, we give the final distribution of weights first and then
we explain how to choose the weight to remove on each step until the balance is
empty.

1. Let
m1 < m2 < . . . < mn
be the weights;

5
2. put all odd indexed weights on one side of the balance and all even indexed
weights on the other side such that the heaviest weight is on the left hand
side, if the last letter of the word is ’L’; or the right hand side if the letter is
’R’;
3. on every move, you remove the last letter from the word and a weight from
the balance as follows:
(a) you remove the heaviest if the letter at the back changes from ’L’ to ’R’
or from ’R’ to ’L’;
(b) otherwise, you remove the lightest weight if the letter at the back of the
word does not change.

6
 Senior Division – Problems and Solutions

Problem 1
In this problem you may assume the following result.
Ptolemy’s Theorem:
If ABCD is a cyclic quadrilateral, that is a quadrilateral inscribed in a circle, then

BD · AC = AD · BC + AB · DC.

Suppose ABCDE is a regular pentagon inscribed in a circle. Let P be any point

on the arc BC. Prove that

P A + P D = P B + P C + P E.

B E

P O

C D

Solution
Since we have to prove

PA + PD = PB + PC + PE

7
we may assume (by applying a dilation) that
AB = BC = CD = DE = EA = 1.
The five diagonals of the regular pentagon have the same length so assume that
AC = BD = CE = DA = EB = d.
With six points on the circle there are
 
6
= 15
4
quadruples of points to which Ptolemy’s Theorem can be applied. Fortunately
the 5 sets corresponding to the points of that pentagon give the same equation.
Consider the quadrilateral ABCD:
AC · BD = AB · CD + AD · BC d2 = 1 + d (0.5)
The exact value of d,
1 p
d = (1 + 5),
2
is not needed.
Apply Ptolemy’s Theorem to P BAE:
P A · BE = P B · AE + P E · AB, P A · d = P B + P E (0.6)
and to P CDE:
P D · CE = P C · DE + P E · CD, P D · d = P C + P E. (0.7)
Add (0.6) and (0.7)
P B + P C + 2P E = P A · d + P D · d (0.8)
Apply Ptolemy’s to P AED:
P E · AD = P A · ED + P D · AE, P E · d = P A + P D,
so
1 1
P E = P A + P D.
d d
Substitute in (0.8)
1 1
P B + P C + P E = P A(d − ) + P D(d − ).
d d
But from (0.5)
1
d− =1
d
and
PB + PC + PE + PA + PD
as required.

8
Problem 2
1. The plan of an art museum is an equilateral triangle consisting of 36 triangu-
lar exhibition halls (see the diagram). Each hall has passages into all adjacent
halls. Prove that you can visit at most 31 halls if you plan to enter each hall
at most once.

2. Subject to the condition that each hall is visited at most once, find the largest
number of halls that can be visited in the case that the museum is an equi-
lateral triangle and that it has k 2 exhibition halls, where k is an integer.
Solution
Starting from the top and working systematically along each row it appears that
one can only visit 36 − 5 = 31 rooms.

Let ak be the number of rooms which can be visited, then apparently

k = 1 2 3 4 5 6
ak = 1 3 7 13 21 31
and for k, in general,

ak = k 2 − (k − 1) = k 2 − k + 1.

Indeed, the method described above shows that

a6 ≥ 31 and ak ≥ k 2 − k + 1,

in general. To see that 31 is the most possible, colour the up triangles red and the
down triangles white.

9
 Each path must go . . . RWRW. . . There are 21 red triangles and 15 white triangles
so a maximal path can contain no more than 16 red and 15 white triangles, so a6 ≤
31. Thus,
a6 = 31.

If there are k 2 exhibition halls, then the number of red halls is

1
1 + 2 + . . . + k = k(k + 1)
2
and the number of white halls is
1
1 + 2 + . . . + (k − 1) = k(k − 1).
2
So the maximal possible path visits

1 1
k(k − 1) + k(k − 1) + 1 = k 2 − k + 1
2 2
halls.

Problem 3
Given an integer n, find the largest integer k such that 3k is a factor of
n
23 + 1.

Give an argument to justify your answer.

Solution
For a few initial values of n, we have
0
n = 0 : 23 + 1 = 3,

n = 1 : 23 + 1 = 8 + 1 = 9,
2
n = 2 : 23 + 1 = 512 + 1 = 27 × 19.
Thus, we hypothesise
k =n+1

10
 and a proof by induction is available. Assume
n
23 + 1 = 3n+1 × An

with n ≥ 2 and (3, An ) = 1. Then,

n+1 n
23 + 1 = (23 )3 + 1
n n n
= 23 + 1 (23 )2 − 23 + 1

= 3n+1 An (3n+1 An − 1)2 − (3n+1 An − 1) + 1

= 3n+1 An 3n+1 3n+1 An − 2An − An + 3

= 3n+2 An 3n 3n+1 An − 3An + 1

which is divisible by exactly 3n+2 but not 3n+3 as required. Since k = n + 1

for n = 0, 1, 2, . . . the proof by induction is complete.

Problem 4
Suppose that x1 , x2 , x3 and y1 , y2 , y3 are positive real numbers such that

0 < x1 y1 < x2 y2 < x3 y3

and
x1 + x2 + x3 ≥ y 1 + y 2 + y 3 .
Prove that
1 1 1 1 1 1
+ + ≤ + + .
x1 x 2 x3 y1 y2 y3
Solution
Unfortunately this question is wrong as can be seen by taking x1 small relative
to y1 , y2 and y3 . For example, let

1 1 1 3
(x1 , x2 , x3 ) = (1, 4, 4) with + + =
x1 x2 x3 2
and
1 1 1 13
(y1 , y2 , y3 ) = (2, 3, 4) with + + = ,
y1 y2 y3 12
then

0 < x1 y1 < x2 y2 < x3 y3 ,

x1 + x2 + x3 ≥ y1 + y2 + y3
1 1 1 1 1 1
and + + > + + .
x1 x2 x3 y1 y2 y3

11
Problem 5
Each of the numbers x1 , . . . , xn is either 1 or −1 and furthermore

x1 x2 + x2 x3 + . . . + xn−1 xn + xn x1 = 0.

Prove that n is a multiple of 4.

Solution
Let
y1 = x1 x2 , y2 = x2 x3 , . . . , yn = xn x1 .
Clearly,
yj = ±1, j = 1, 2, . . . , n.
Now the sum of an odd number of odd numbers is odd, so if
n
X
yj = 0,
j=1

then n is even.
Let us show that n is a multiple of 4. If
n
X
yj = 0
j=1

with n = 2k, then k of the yj ’s are 1 and k of the yj ’s are −1. Consider,

y1 y2 · . . . · yn = x21 x22 · . . . · x2n = 1,

since each x2j = 1. Thus, the number of negative yj ’s, which is k, is even. So n = 2k
is a multiple of 4.
Alternative Solution
We may assume x1 = 1. Consider the signs of x1 , x2 , . . . , xn , x1 as

+ + ... + − − ... − +... + −... − ... + ...+

The number of negative yj ’s is the number of times +− or −+ occurs in the

sequence. Clearly +− and −+ occur the same number of times so k is even,
and n = 2k is a multiple of 4.

Problem 6
Seven people have access to a bank vault. The vault is secured with a number of
locks, and for each lock, some but not all of the seven people have a key. Find
the minimal number of locks needed so that any 4 of them can open the vault
whereas any 3 of them cannot. For the minimal number of locks, specify the
required distribution of the keys among the people.

12
Solution
The required number of locks is
 
7
n= = 35.
3

Assume first that we have some amount of locks installed and some distribution
of keys between the people such that the conditions of the problem are met. That
is, every group of three people cannot open the vault and any group of four can
open the vault.
In this case, for every group of three people, there is a unique lock such that this
group cannot open this lock, i.e., none in the group has a key to the lock. Indeed,
if this was not so, that is, if there was two different groups of three people, say A
and B, and a lock, say L, such that both A and B cannot open the lock L, then,
by joining a person from B to the group A, we end up with a group of four peo-
ple which cannot open the lock L. This is in contradiction with the assumption
above. Hence, every
group of three people has at least one unique lock associated
with it. There are 73 groups of 3 people and so the number of locks is at least
 
7
= 35.
3

This number of locks is sufficient to

ensure the requirement of the problem. In-
7
deed, given that that we install 3 locks, we associate uniquely a lock with a
group of three people and we give keys to this lock to everyone but the associ-
ated group of three.

13