9th Iberoamerican Mathematical Olympiad Problems 1994

A1.  Show that there is a number 1 < b < 1993 such that if 1994 is written in base b then all its digits are the same. Show that there is no number 1 < b < 1992 such that if 1993 is written in base b then all its digits are the same.

A2.  ABCD is a cyclic quadrilateral. A circle whose center is on the side AB touches the other three sides. Show that AB = AD + BC. What is the maximum possible area of ABCD in terms of |AB| and |CD|?

A3.  There is a bulb in each cell of an n x n board. Initially all the bulbs are off. If a bulb is touched, that bulb and all the bulbs in the same row and column change state (those that are on, turn off, and those that are off, turn on). Show that it is possible by touching m bulbs to turn all the bulbs on. What is the minimum possible value of m?

B1.  ABC is an acute-angled triangle. P is a point inside its circumcircle. The rays AP, BP, CP intersect the circle again at D, E, F. Find P so that DEF is equilateral.

B2.  n and r are positive integers. Find the smallest k for which we can construct r subsets A₁, A₂, ... , A_r of {0, 1, 2, ... , n-1} each with k elements such that each integer 0 ≤ m < n can be written as a sum of one element from each of the r subsets.

B3.  Show that given any integer 0 < n ≤ 2^1000000 we can find at set S of at most 1100000 positive integers such that S includes 1 and n and every element of S except 1 is a sum of two (possibly equal) smaller elements of S. 

Solutions

Problem A1

Show that there is a number 1 < b < 1993 such that if 1994 is written in base b then all its digits are the same. Show that there is no number 1 < b < 1992 such that if 1993 is written in base b then all its digits are the same.

Solution

Any even number 2n can be written as 22 in base n-1. In particular 1994 = 22₉₉₆.

We have to show that we cannot write 1993 = aaa ... a_b. If the number has n digits, then 1993 = a(1 + b + ... + b^n-1) = a(bⁿ - 1)/(b - 1). But 1993 is prime, so a must be 1. Hence b^n-1 + ... + b - 1992 = 0. So b must divide 1992 = 2³3.83. We cannot have n = 2, for then b = 1992 and we require b < 1992. So n > 2. But 83² = 6889 > 1993, so b must divide 24. Hence b = 2, 3, 4, 6, 8, 12, or 24. But we can easily check that none of these work:

1 + 2 + 22 + ... + 29 = 1023, 1 + ... + 210 = 2047.

1 + 3 + ... + 36 = 1093, 1 + ... + 3^7 = 3280

1 + 4 + ... + 45 = 1365, 1 + ... + 46 = 5461

1 + 6 + ... 64 = 1555, 1 + ... + 65 = 9331

1 + 8 + 82 + 83 = 585, 1 + ... + 84 = 4681

1 + 12 + 122 + 123 = 1885, 1 + ... + 124 = 22621

1 + 24 + 242 = 601, 1 + ... + 243 = 14425 

Problem 
A2 

ABCD is a cyclic quadrilateral. A circle whose center is on the side AB touches the other three sides. Show that AB = AD + BC. What is the maximum possible area of ABCD in terms of |AB| and |CD|?

Answer

(h/2 + k/2) √(hk/2 - h²/4), where h = |CD|, k = |AB|

Solution

Let the circle have center O on AB and radius r. Let ∠OAD = θ, ∠OBC = φ. Since ABCD is cyclic, ∠ADC = 180^o-φ, so ∠ODA = 90^o-φ/2. If AD touches the circle at X, then AD = AX + XD = r cot θ + r tan(φ/2). Similarly, BC = r cot φ + r tan(θ/2). Put t = tan(θ/2). Then cot θ = (1-t²)/2t, so cot θ + tan(θ/2) = (1+t²)/2t = 1/sin θ. Similarly for φ, so AD + BC = r/sin θ + r/sin φ = AO + OB = AB.

Suppose AD and BC meet at H (we deal below with the case where they are parallel). Then HCD and HAB are similar, so area HCD = (CD²/AB²) area HAB and area ABCD = (1 - CD²/AB²) area HAB. Also AB/CD = HA/HC = HB/HD = (HA+HB)/(HC+HD) = (HA+HB)/(HB-BC+HA-DA) = (HA+HB)/(HA+HB-AB). Hence HA+HB = AB²/(AB-CD), which is fixed. Now for fixed HA+HB we maximise the area of HAB by taking HA = HB and hence AD = BC.

Put h = CD, k = AB. So k cos θ + h = k. Hence cos θ = (1-h/k). Hence sin θ = √(2h/k - h²/k²). So area ABCD = ½(h+k) ½ k sin θ = (h/2 + k/2) √(hk/2 - h²/4) (*).

If AD and BC are parallel then A and B must lie on the circle, so that ∠DAB = ∠ABC = 90^o. But ABCD is cyclic, so it must be a rectangle. Hence AB = CD and area ABCD = k²/2. In this case (*) still gives the correct answer.

Thanks to Vivek Kumar Mehra

Problem A3

There is a bulb in each cell of an n x n board. Initially all the bulbs are off. If a bulb is touched, that bulb and all the bulbs in the same row and column change state (those that are on, turn off, and those that are off, turn on). Show that it is possible by touching m bulbs to turn all the bulbs on. What is the minimum possible value of m?

Answer

n odd, n is minimum
n even, n² is minimum

Solution

If n is odd, touch each bulb in the first column. Then bulbs in the first column are each switched n times, which is odd and so end up on. All other bulbs are switched just once, and so end up on. n is obviously minimal, because if m < n, then there is a bulb which is not switched at all (there must be a column with no bulb touched and a row with no bulb touched, so the bulb in that column and row is not switched).

In n is even, touch each bulb. Then each bulb is switched 2n-1 times, so ends up on. We show that it is not possible to do better.

Note first that there is no benefit in touching a bulb more than once, so each must be touched zero of one times. Thus we can represent the scheme as an array of 0s and 1s, where 0 means that the corresponding bulb is not touched, and 1 means that it is touched.

Let A, B, C, D be four values at the corners of a rectangle. We claim that A+B has the same parity as C+D. Let L_AB be the number of 1s in the row AB are touched, similarly L_BC (the number of 1s in the column BC), L_CD, L_DA. Since bulb A is switched we must have L_AB + L_DA + A odd (note that L_AB + L_DA double-counts the no. of touches of A). Similarly, L_BC + L_CD + C is odd, so A + C + (L_AB + L_BC + L_CD + L_DA) is even. Similarly, considering B and D, we find that B + D + (L_AB + L_BC + L_CD + L_DA) is even, so A+C and B+D have the same parity. Adding B+C to both, we get that A+B and C+D have the same parity. It follows that either A = D and B = C, or A ≠ D and B ≠ D.

Keeping A and B fixed, we can now vary C (and hence D). It follows that either the row through B matches that through A, or it has every cell different (to the corresponding cell in row A). Similarly for the other rows. So we have k rows of one type and n-k rows which are equal to its "complement". Suppose first that k = n, so that all rows are the same. If we have all 1s, then we have a solution. If we have all 0s, we obviously do not have a solution. So suppose there is a 0 and a 1 in each row. Then the total count at a 1 is n-1 higher than at a 0 (because of the extra n-1 1s in the same column). So they cannot both be odd (because n is even). Contradiction.

Finally suppose there is a row and a complement row. So position A in one is 1, then position B in the same column in the other has 0. If a row has h 1s, then a complement row has n-h 1s. The column has z 1s, so A has z+h-1 or z+n-h-1 1s, and B has z+h or z+n-h 1s. But since n is even, z+h and z+n-h have the same parity, so A and B have opposite parity. Contradiction. So the only solution for n even is all 1s. 

Problem B1

ABC is an acute-angled triangle. P is a point inside its circumcircle. The rays AP, BP, CP intersect the circle again at D, E, F. Find P so that DEF is equilateral.

Solution

Let the angle bisector of A meet BC at A'. Let the perpendicular bisector of AA' meet the line BC at X. Take the circle center X through A and A'. Similarly, let the angle bisector of B meet AC at B' and let the perpendicular bisector of BB' meet the line AC at Y. Take the circle center Y through B and B'. The two circles meet at a point P inside the triangle, which is the desired point.

PAB and PED are similar, so DE/AB = PD/PB. Similarly, DF/AC = PD/PC, so DE/DF = (AB/AC)(PC/PB). Thus we need PB/PC = AB/AC. So P must lie on the circle of Apollonius, which is the circle we constructed with center X. Similarly, it must lie on the circle of Apollonius with center Y and hence be one of their points of intersection. It also lies on the third circle and hence we choose the point of intersection inside the triangle.

 Problem B2

n and r are positive integers. Find the smallest k for which we can construct r subsets A₁, A₂, ... , A_r of {0, 1, 2, ... , n-1} each with k elements such that each integer 0 ≤ m < n can be written as a sum of one element from each of the r subsets.

Answer

smallest integer such that k^r ≥ n.

Solution

We can form at most k^r distinct sums, so k^r must be ≥ n.

Now consider A₁ = {0, 1, 2, ... , k-1}, A₂ = {0, k, 2k, ... , (k-1)k}, A₃ = {0, k², 2k², ... , (k-1)k²}, ... , A_r = {0, k^r-1, 2k^r-1, ... , (k-1)k^r-1}. Then for any non-negative integer m < k^r, we can write m with r digits in base k (using leading zeros as necessary) and hence as a sum of one element from each A_i. This subset works for (k-1)k^r-1 < n ≤ k^r. For smaller n above (k-1)^r we cannot use all the elements given above, but we do not need them, so we just replace the elements which are too large by arbitrary elements under n.

For example, suppose n = 17, r = 4. We need k = 3. So we form A₁ = {0, 1, 2}, A₂ = {0, 3, 6}, A₃ = {0, 9, 18}, A₄ = {0, 27, 54}. Now 18, 27, 54 are unnecessary, so we pad out A₃ and A₄ with other elements. We could take A₃ = {0, 1, 9}, A₄ = {0, 1, 2}.