10th Mexican Mathematical Olympiad Problems 1996

10th Mexican Mathematical Olympiad Problems 1996

A1.  ABCD is a quadrilateral. P and Q are points on the diagonal BD such that the points are in the order B, P, Q, D and BP = PQ = QD. The line AP meets BC at E, and the line Q meets CD at F. Show that ABCD is a parallelogram iff E and F are the midpoints of their sides.

A2.  64 tokens are numbered 1, 2, ... , 64. The tokens are arranged in a circle around 1996 lamps which are all turned off. Each minute the tokens are all moved. Token number n is moved n places clockwise. More than one token is allowed to occupy the same place. After each move we count the number of tokens which occupy the same place as token 1 and turn on that number of lamps. Where is token 1 when the last lamp is turned on?

A3.  Show that it is not possible to cover a 6 x 6 board with 1 x 2 dominos so that each of the 10 lines of length 6 that form the board (but do not lie along its border) bisects at least one domino. But show that we can cover a 5 x 6 board with 1 x 2 dominos so that each of the 9 lines of length 5 or 6 that form the board (but do not lie along its border) bisects at least one domino.

B1.  For which n can we arrange the numbers 1, 2, 3, ... , 16 in a 4 x 4 array so that the eight row and column sums are all distinct and all multiples of n?

B2.  Arrange the numbers 1, 2, 3, ... , n² in order in a n x n array (so that the first row is 1, 2, 3, ... , n, the second row is n+1, n+2, ... , 2n, and so on). For each path from 1 to n² which consists entirely of steps to the right and steps downwards, find the sum of the numbers in the path. Let M be the largest such sum and m the smallest. Show that M - m is a cube and that we cannot get the sum 1996 for a square of any size.

B3.  ABC is an acute-angled triangle with AB < BC < AC. The points A', B', C' are such that AA' is perpendicular to BC and has the same length. Similarly, BB' is perpendicular to AC and has the same length, and CC' is perpendicular to AB and has the same length. The orthocenter H of ABC and A' are on the same side of A. Similarly, H and B' are on the same side of B, and H and C' are on the same side of C. Also ∠AC'B = 90^o. Show that A', B', C' are collinear. 

Solutions

Problem A1

ABCD is a quadrilateral. P and Q are points on the diagonal BD such that the points are in the order B, P, Q, D and BP = PQ = QD. The line AP meets BC at E, and the line Q meets CD at F. Show that ABCD is a parallelogram iff E and F are the midpoints of their sides.

Solution

Let the diagonals meet at X. If ABCD is a parallelogram, then X is the midpoint of BD, and the midpoint of AC. Hence BX is a median of the triangle ABC and BP/PX = 2/3, so P is the centroid of ABC. Hence AE is also a median and so E is the midpoint of BC. Similarly, F is the midpoint of CD.

Now suppose E is the midpoint of BC, and F the midpoint of CD. Then EF is parallel to BC and half its length. Hence PQ = (2/3)EF, so the midpoint Y of PQ is the centroid of AEF. So if Z is the midpoint of EF, then A,Y,Z are collinear. Note that Y is also the midpoint of BD. But C,Z,Y are also collinear, so Y lies on AC. Now Y is the centroid of AEF, so AY = 2YZ. But EF=BD/2, so CZ = YZ. Hence AY = CY, so Y is also the midpoint of AC. Hence ABCD is a parallelogram. 

Problem A2

64 tokens are numbered 1, 2, ... , 64. The tokens are arranged in a circle around 1996 lamps which are all turned off. Each minute the tokens are all moved. Token number n is moved n places clockwise. More than one token is allowed to occupy the same place. After each move we count the number of tokens which occupy the same place as token 1 and turn on that number of lamps. Where is token 1 when the last lamp is turned on?

Answer

32

Solution

Label the positions 1 to 64, so that initially token k is in position k. Token k gets to position m+1 after m moves iff (m+1)k = m+1 mod 64 or (k-1)(m+1) = 0 mod 64. So if k ≠ 1, then m+1 must be a power of 2. If 2ⁿ is the highest power of 2 dividing m+1, then k-1 must be divisible by 2^6-n.

So if m+1 = 2, 6, 10, 14, 18, ... , then only 33 shares a place with token 1. If m+1 = 4, 12, 20, 28, 36, ..., then 17, 33, 49 share a place with token 1. If m+1 = 8, 24, 40, 56, ..., then 9, 17, 25, 33, 41, 49, 57 share a place with token 1. If m+1 = 16, 48, 80, ..., then 15 numbers share a place with token 1. If m+1 = 32, 96, 160, ..., then 31 numbers share a place with token 1, and if m+1 = 64, 128, 192, ..., then 63 numbers (all of them) share a place with token 1.

So in the first 64 moves, 32·1 + 16·2 + 8·4 + 4·8 + 2·16 + 1·32 = 192 numbers share a place with 1. After 64 moves every token is back at its starting point. So after 10 such rounds 1920 bulbs are turned on and all the numbers are back at their starting points. Now when 1 reaches 31 on the next round we another 1+3+1+7+1+3+1+15+1+3+1+7+3+1 = 48 lights are turned on, for a total of 1968. When it moves to 32 the remaining 28 lights are turned on. 

Problem A3

Show that it is not possible to cover a 6 x 6 board with 1 x 2 dominos so that each of the 10 lines of length 6 that form the board (but do not lie along its border) bisects at least one domino. But show that we can cover a 5 x 6 board with 1 x 2 dominos so that each of the 9 lines of length 5 or 6 that form the board (but do not lie along its border) bisects at least one domino.

Solution

Consider first the 6 x 6 board. Each of the 10 lines length 6 divides the board into two parts, each with an even number of squares. But if just one domino straddles a line, then there must be an odd number of squares each side of the line. Contradiction. So an even number of dominos must straddle each line. So if at least one domino straddles each line, then at least two do. But a domino can only straddle one line and there are < 2·10 dominos.

The diagram shows a possible solution for a 5 x 6 board.

Problem B1

For which n can we arrange the numbers 1, 2, 3, ... , 16 in a 4 x 4 array so that the eight row and column sums are all distinct and all multiples of n?

Answer

1,2,4

Solution

1+2+...+16 = 2³17, so if the row sums are all multiples of n, then n must divide 2³17. But if all the row and column sums are multiples of 17, then the largest is at least 8·17 and hence the numbers add up to more than 8·17. Contradiction. So n must be 1, 2, 4 or 8. If n = 8, then the largest row/column sum must be at least 64. But the largest possible row/column sum is 16+15+14+13 = 58 < 64. So n must be 1, 2 or 4. The example below shows that these are all possible.

1  8  3  4  16
 5  6  7  2  20
 9 10 11 14  44
13 16 15 12  56

28 40 36 32  

Problem B2

Arrange the numbers 1, 2, 3, ... , n² in order in a n x n array (so that the first row is 1, 2, 3, ... , n, the second row is n+1, n+2, ... , 2n, and so on). For each path from 1 to n² which consists entirely of steps to the right and steps downwards, find the sum of the numbers in the path. Let M be the largest such sum and m the smallest. Show that M - m is a cube and that we cannot get the sum 1996 for a square of any size.

Solution

If we take any four numbers ABCD with A, B in the same row, C, D in the same row, A, D in the same column and B, C in the same column:

... A ... B
 ...
... D ... C

Then B < D, so A + D + C > A + B + C. Hence the maximal path must be down the first column and then along the bottom row. Thus M = 1 + n+1 + 2n+1 + ... + n²-n+1 + n²-n+2 + ... + n² = (3n³-4n²+5n-2)/2. Similarly, the minimal path must be along the first row and down the last column, so m = 1 + 2 +...+ n-1 + n(1 + 2 + ... + n) = (n³+2n²-n)/2. Hence M-m = (n-1)³.

We have m = 1905 for n = 15 and 2296 for n = 16, so for a path of length 1996 we must have n ≤ 15. Similarly M = 1781 for n = 11 and 2333 for n = 12, so for length 1996 we must have n ≥ 12. So we need n = 12, 13, 14 or 15.

It is easy to see that by a sequence of moves of the type:

A to AB 
BC    C

we can go from any path to the minimal path. But each move of this type reduces the total by n-1. So any path total must = (n³+2n²-n)/2 mod n-1. For n = 12 this gives 1002 mod 11 = 1 mod 11. But 1996 = 5 mod 11, so 12 does not work. For n = 13, it gives 1261 = 1 mod 12, but 1996 = 4 mod 12, so 13 does not work. For n = 14, it gives 1561 = 1 mod 13, but 1996 = 7 mod 13, so 14 does not work. For n = 15, it gives 1905 = 1 mod 14, but 1996 = 8 mod 14, so 15 does not work. Thus we cannot get a path length 1996.