TOURNAMENT OF THE TOWNS

Senior A-Level Paper Fall 2001.

1. On the plane is a triangle with red vertices and a triangle with blue vertices. O is a point
inside both triangles such that the distance from O to any red vertex is less than the distance
from O to any blue vertex. Can the three red vertices and the three blue vertices all lie on
the same circle?

2. Do there exist positive integers a₁ < a₂ < < a₁₀₀ such that for 2≤k ≤100, the least
common multiple of a _k-1 and a_k is greater than the least common multiple of a_k and a_k+1?

3. An 8*8 array consists of the numbers 1, 2, . . ., 64. Consecutive numbers are adjacent along
a row or a column. What is the minimum value of the sum of the numbers along a diagonal?

4. Let F₁ be an arbitrary convex quadrilateral. For k≥2, F_k is obtained by cutting F_k-1 into two
pieces along one of its diagonals, flipping one piece over and then glueing them back together
along the same diagonal. What is the maximum number of non-congruent quadrilaterals in
the sequence {F_k}?

5. Let a and d be positive integers. For any positive integer n, the number a + nd contains a
block of consecutive digits which constitute the number n. Prove that d is a power of 10.

6. In a row are 23 boxes such that for 1≤k≤23, there is a box containing exactly k balls.
In one move, we can double the number of balls in any box by taking balls from another
box which has more. Is it always possible to end up with exactly k balls in the k-th box for
1≤k≤23?

7. The vertices of a triangle have coordinates (x₁, y₁), (x₂, y₂) and (x₃, y₃). For any integers h
and k, not both 0, the triangle whose vertices have coordinates (x₁+h, y₁+k), (x₂+h, y₁+k)
and (x₃ + h, y₃ + k) has no common interior points with the original triangle.

(a) Is it possible for the area of this triangle to be greater than 1/2?
(b) What is the maximum area of this triangle?

Note. The problems are worth 4, 5, 6, 6, 7, 7 and 3+6 points respectively.

Solutions to Senior A-Level Fall 2001

1. Suppose all six vertices lie on a circle with centre M. Let the line through O perpendicular
to OM cut the circle at K and L. Since M is inside the triangle with red vertices, at least
one red vertex lies on the minor arc KL and at least one red vertex lies on the major arc KL.
The same is true of the blue vertices. However, every point on the minor arc KL is inside
the circle with diameter KL, so that its distance from O is at most OK. On the other hand,
every point on the major arc KL is outside the circle with diameter KL, so that its distance
from O is at least OK. This is a contradiction.

2. We use an to denote the n-th term, even though its value may be modified along the way.
In step 1, we set a₉₉ = 9 and a₁₀₀ = 10, with lcm (a₉₉, a₁₀₀) = 90. In step k > 1, define
and then redefine a_n for each n > 100 - k to be 10 times its former
value. Hence in step 2, we define We also redefine a₉₉ = 90 and
a₁₀₀ = 100. We have lcm(a₉₈, a₉₉) = 8010 > 900 = lcm(a₉₉, a₁₀₀). We continue until step 99
has been completed. Note that once we have lcm(a_n-1, a_n) > lcm(a_n, a_n+1), this remains true
thereafter since in all subsequent modifications, each of a_n-1, a_n and a_n+1 is multiplied by
the same number. We only have to check this inequality when a_n-1 is first introduced. At
this point, Now since a_n-1 > 1. Hence

3. Since consecutive numbers occupy sqaures of opposite colours, we may assume that all numbers
on black squares are odd and all numbers on white squares are even. The diagram be low shows
that the sum may be as small as 1+3+5+7+9+11+13+39=88.

Suppose it is possible to improve on this. Clearly, the diagonal in question should contain
odd numbers, and the largest would have to be at most 37. Once this number is put down,
we must remain on the same side of this diagonal. There are exactly 16 black squares and
12 white squares on each side. Hence that largest number is 37 and only one square on the
largely empty side of the diagonal has been filled. However, there are 13 odd numbers from
38 to 64 but we have at most 12 white squares to accommodate them. Hence improvement
over 88 is impossible.

4. Let F₁ = ABC₁D₁ and let F₂ = ABC₁D₂ be obtained from F₁ by re ecting D₁ to D₂ across
the perpendicular bisector of AC₁. Reflecting alternately across the two diagonals , we obtain
F₃ = ABC₂D₂, F₄ = ABC₂D₃, F₅ = ABC₃D₃, F₆ = ABC₃D₄ and F₇ = ABC₄D₄. This
sequence of transformations permutes the sides while preserving the sum of the opposite
angles. We have and
D₁A = D₄A. If AC₁ > AC₄, then and We also have a
contradiction if AC₁ < AC₄. Hence AC₁ = AC₄ and it follows that F₁ and F₇ are congruent.
Thus the sequence {F_k} consists of at most six non-congruent quadrilaterals. If F₁ has sides
of distinct lengths and the sum of neither pair of opposite angles is 180º, we indeed have six
non-congruent quadrilaterals.

5. Let the number of digits of d be k, and that of a be m. Consider the term a +10^td where t is
an integer such that t > max{k,m}. It must contain a 1 followed by at least m zeros, so that
k > m. The next term a + (10^t + 1)d must contain two 1's separated by exactly t - 1 zeros.
Since t > k, this can only happen if the first digit of d is 1 and the remaining digits are 0's,
which means that d is a power of 10.

6. We shall prove by induction on the number n of boxes that the task is always possible. This
is clearly true for n = 1. Suppose it is true for some n≥1. Consider the next case where we
have n + 1 boxes. Line up the boxes from left to right in increasing order of the number of
balls in them, without regard to the box numbers. Transfer balls from each box to the next
one to its left, starting with the rightmost one which contains n + 1 balls.

This sequence of moves results in a cyclic permutation of the numbers of the balls. We perform
this a number of times until the (n+1)-st box contains n+1 balls. The rest of the boxes can
be sorted out by the induction hypothesis.

7. (a) The tiling on the left of the figure below shows that the area of the triangle may be 2/3 .
The coordinates of the vertices of a copy of the triangle are

(b) Let ABC be any triangle with the desired properties . Let D, E and F be the midpoints
of BC, CA and AB respectively. Extend ED to G and FD to H so that ED = DG and
FD = DH, as shown on the right of the figure above. We claim that integral translates
of the hexagon BGHCEF do not have common interior points. It will then follow that
its area is at most 1, and that the area of ABC is at most 2/3 . This maximum is attained
by the example in (a). Suppose to the contrary that BGHCEF has a common point
with an integral translate B0G0H0C0E0F0. We may assume that either E' or F' is inside
the quadrilateral BGHC. There are three cases. If E' is inside triangle DBG, then B
will be inside the integral translate A'B'C' of ABC. Similarly, if F' is inside triangle
DCH, then C will be inside A'B'C'. Finally, if either E' or F' is inside triangle DGH,
then A' will be inside ABC. Since we have a contradiction in each of the three cases,
the claim is justified.