4th Brazilian Mathematical Olympiad Problems 1982

4th Brazilian Mathematical Olympiad Problems 1982

1.  The angles of the triangle ABC satisfy ∠A/∠C = ∠B/∠A = 2. The incenter is O. K, L are the excenters of the excircles opposite B and A respectively. Show that triangles ABC and OKL are similar.

2.  Any positive integer n can be written in the form n = 2^b(2c+1). We call 2c+1 the odd part of n. Given an odd integer n > 0, define the sequence a₀, a₁, a₂, ... as follows: a₀ = 2ⁿ-1, a_k+1 is the odd part of 3a_k+1. Find a_n.
3.  S is a (k+1) x (k+1) array of lattice points. How many squares have their vertices in S?
4.  Three numbered tiles are arranged in a tray as shown:

Show that we cannot interchange the 1 and the 3 by a sequence of moves where we slide a tile to the adjacent vacant space.
5.  Show how to construct a line segment length (a⁴ + b⁴)^1/4 given segments length a and b.
6.  Five spheres of radius r are inside a right circular cone. Four of the spheres lie on the base of the cone. Each touches two of the others and the sloping sides of the cone. The fifth sphere touches each of the other four and also the sloping sides of the cone. Find the volume of the cone.

Solutions

Problem 1
The angles of the triangle ABC satisfy ∠A/∠C = ∠B/∠A = 2. The incenter is O. K, L are the excenters of the excircles opposite B and A respectively. Show that triangles ABC and OKL are similar.
Solution

∠AOC = 180^o - ∠A/2 - ∠C/2. But ∠KAO = ∠KCO = 90^o, so ∠AKC = ∠A/2 + ∠C/2. So considering triangle AKL, ∠ALK = 90^o - ∠A/2 - ∠C/2 = ∠B/2. Similarly, ∠ BLC = ∠B/2 + ∠C/2, so ∠BKL = ∠A/2.
Now we use the given facts that ∠C = ∠A/2 and ∠A = ∠B/2. So ∠OKL = ∠BKL (same angle) = ∠C, and ∠OLK = ∠ALK (same angle) = ∠A. Hence triangles OKL and BCA are similar.

Problem 2
Any positive integer n can be written in the form n = 2^b(2c+1). We call 2c+1 the odd part of n. Given an odd integer n > 0, define the sequence a₀, a₁, a₂, ... as follows: a₀ = 2ⁿ-1, a_k+1 is the odd part of 3a_k+1. Find a_n.
Answer
(3ⁿ - 1)/2
Solution
A simple induction shows that a_k = 3^k2^n-k - 1 for k ≤ n-1. It is certainly true for k = 0. Suppose it is true for k < n-1. Then 3a_k + 1 = 3^k+12^n-k - 2. Since n-k > 1, the odd part is 3^k+12^n-(k+1) - 1, so the result is true for k+1. That gets us as far as a_n-1 = 3^n-12 - 1. Now we want the odd part of 2(3ⁿ - 1). Certainly 3ⁿ - 1 is even. We have 3ⁿ - 1 = (-1)ⁿ - 1 = 2 mod 4 for n odd, so for n odd it is not divisible by 4. Hence for n odd we have a_n = (3ⁿ - 1)/2.

Problem 3
S is a (k+1) x (k+1) array of lattice points. How many squares have their vertices in S?
Answer
k(k+1)²(k+2)/12
Solution

The key is to consider how many squares have their vertices on the perimeter of given n+1 x n+1 array whose side are parallel to the sides of the array.
The diagram shows that there are n such squares. There are (k+1-n)² such arrays. So the total number of squares is k·1² + (k-1)2² + ... + 1·k² = ∑₁^k (k+1-i)i² = (k+1)k(k+1)(2k+1)/6 - k²(k+1)²/4 = k(k+1)²(k+2)/12.

Problem 4
Three numbered tiles are arranged in a tray as shown:
Show that we cannot interchange the 1 and the 3 by a sequence of moves where we slide a tile to the adjacent vacant space.
Solution
Write down the order of the tiles reading clockwise around the perimeter, starting at 1. We get 123 and no move changes that, so we will always get 123 after any sequence of moves. But the desired arrangement would give 132, so it is not possible.

Problem 5
Show how to construct a line segment length (a⁴ + b⁴)^1/4 given segments length a and b.
Solution

We show first how to get the square and the square root. Take ABC with ∠A = 90^o, altitude AD length a and BD = 1. Then by similar triangles BC/AB = AB/BD, so BC = AB²/BD = AB² = a² + 1. Hence CD = a².

Conversely, we can take BD = 1, CD = a and then construct A (as the intersection of the perpendicular at D and the circle diameter BC) length √a.
So now given a, b construct a², b². Then take a right-angled triangle with those lengths as its shorter sides and the hypoteneuse is √(a⁴ + b⁴). Finally, take the square root to get the required length.

Problem 6
Five spheres of radius r are inside a right circular cone. Four of the spheres lie on the base of the cone. Each touches two of the others and the sloping sides of the cone. The fifth sphere touches each of the other four and also the sloping sides of the cone. Find the volume of the cone.
Answer (1/3)πr³(2√2+1)³.
Solution

 

The left-hand diagram shows the four spheres on the base. Evidently AC = 2r√2. The right-hand diagram shows a vertical section through A, C and the center O of the top sphere. P is the apex of the cone and QR is a diameter of its base. Evidently PQR is similar to OAC and its sides are parallel and a distance r outside the corresponding sides of OAC.
Also AOC is congruent to ABC, so ∠AOC = 90^o. Hence ∠QPR = 90^o also and so OP = r√2. The altitude from O in AOC has length AC/2 = r√2. Hence the altitude from P in PQR has length OP + r√2 + r = (2√2+1)r. Thus radius of the cone's base is also (2√2+1)r and its volume is (1/3)πr³(2√2+1)³.

[Read More...]

3rd Brazilian Mathematical Olympiad Problems 1981

3rd Brazilian Mathematical Olympiad Problems 1981

1.  For which k does the system x² - y² = 0, (x-k)² + y² = 1 have exactly (1) two, (2) three real solutions?

2.  Show that there are at least 3 and at most 4 powers of 2 with m digits. For which m are there 4?

3.  Given a sheet of paper and the use of a rule, compass and pencil, show how to draw a straight line that passes through two given points, if the length of the ruler and the maximum opening of the compass are both less than half the distance between the two points. You may not fold the paper.

4.  A graph has 100 points. Given any four points, there is one joined to the other three. Show that one point must be joined to all 99 other points. What is the smallest number possible of such points (that are joined to all the others)?

5.  Two thieves stole a container of 8 liters of wine. How can they divide it into two parts of 4 liters each if all they have is a 3 liter container and a 5 liter container? Consider the general case of dividing m+n liters into two equal amounts, given a container of m liters and a container of n liters (where m and n are positive integers). Show that it is possible iff m+n is even and (m+n)/2 is divisible by gcd(m,n).

6.  The centers of the faces of a cube form a regular octahedron of volume V. Through each vertex of the cube we may take the plane perpendicular to the long diagonal from the vertex. These planes also form a regular octahedron. Show that its volume is 27V. 

Solutions

Problem 1

For which k does the system x² - y² = 0, (x-k)² + y² = 1 have exactly (1) two, (2) three real solutions?
Answer
(1) k = ±√2, (2) k = ±1.
Solution
We have (x-k)² + x² = 1, so 2x² - 2kx + k²-1 = 0. This has 0, 1 or 2 real solutions according as k² >2, =2 or <2.
k = √2 gives x = 1/√2, y = 1/√2 or -1/√2, so there are two solutions to the original set. Similarly for k = -√2.
If |k| < √2, then x = ½k ±½√(2-k²), y = ± x. That gives 4 solutions unless one of the values of x is 0, in which case we get 3 solutions. So k = 1 gives x, y = 0, 0 or 1, 1 or 1, -1. k = -1 gives x, y = 0, 0 or -1, 1 or -1, -1.

Problem 2
Show that there are at least 3 and at most 4 powers of 2 with m digits. For which m are there 4?
Solution
Take n to be the smallest integer such that 2ⁿ ≥ 10^m-1. Then 2^n-1 < 10^m-1, so 2ⁿ⁺² < 8·10^m-1 < 10^m. So 2ⁿ, 2ⁿ⁺¹ and 2ⁿ⁺² all have m digits. Thus there are at least 3 powers of 2 with m digits.
2^n-1 ≥ 5·10^m-2 (otherwise 2ⁿ < 10^m-1). Hence 2ⁿ⁺⁴ ≥ 32·5·10^m-2 > 10^m, so 2ⁿ⁺⁴ has more than m digits. Thus there are at most 4 powers of 2 with m digits.
There are 4 if there is an integer between (m-1)/log₁₀2 and (m/log₁₀2 - 3).

Comment. The last part is a bad question. The solution given (which is the official solution) is not really a solution at all, because it does not tell us when there is such an integer. But, of course, there is no better solution, so a hapless competitor is liable to waste time searching for something that does not exist.

Problem 3
Given a sheet of paper and the use of a rule, compass and pencil, show how to draw a straight line that passes through two given points, if the length of the ruler and the maximum opening of the compass are both less than half the distance between the two points. You may not fold the paper.
Solution

Note that we can draw an arbitrarily long line through a given point by repeatedly extending a short line. We can also find the midpoint of an arbitrary line segment. For suppose the segment is PQ. Take a distance k which is less than the maximum opening of the compass and less than the length of the ruler. Starting at P and using the compasses, mark off q distances of k leaving a final distance of r < k to Q. Now bisect the final segment of r as usual and a segment length k. Then mark off q distances of k/2 and one of r/2 from P to get the midpoint.

So suppose the points given are A and B. Take any lines through A and B meeting at C. Let M₁, N₁ be the midpoints of AC, BC respectively. Then take M₂, N₂ as the midpoints of M₁C, N₁C respectively, and so on until we get M_nN_n < k. We can now join M_n and N_n to get a line parallel to the desired line AB. That allows us to draw a short line through A in the right direction. We mark off a point X on AC with AX = M_nC, then draw circles center A radius M_nN_n and center X radius CN_n to intersect at a point Y with AXY congruent to M_nCN_n and hence Y on AB. Now extend AY to get AB.

Problem 4

A graph has 100 points. Given any four points, there is one joined to the other three. Show that one point must be joined to all 99 other points. What is the smallest number possible of such points (that are joined to all the others)?

Answer
97
Solution

Suppose that no point is joined to all the others. Then given any point X we can find Y not joined to X. So take arbitrary A and C. Then take B not joined to A and D not joined to C. Then the four points A, B, C, D do not meet the required condition. Contradiction.

So find X₁ joined to all the other 99 points. Now repeat the argument for the other 99 points, that gives a point X₂ joined to the other 98. But it is also joined to X₁, so it is joined to all other 99 points. Now repeat for the other 98 points and so on. The last time we can repeat is when we have already found X1, X2, ... , X96 leaving four points. We can now take X97 joined to the other three and hence to all other 99. Thus we can get at least 97 points each joined to all points except itself.

That is best possible, because we can take the graph with 100 points including A, B, C and all edges except AB, BC and CA. That clearly has at most 97 points each joined to all points except itself, but it obviously satisfies the condition.

Problem 5

Two thieves stole a container of 8 liters of wine. How can they divide it into two parts of 4 liters each if all they have is a 3 liter container and a 5 liter container? Consider the general case of dividing m+n liters into two equal amounts, given a container of m liters and a container of n liters (where m and n are positive integers). Show that it is possible iff m+n is even and (m+n)/2 is divisible by gcd(m,n).

Solution

Call the containers L₈, L₅, L₃. Fill L₅ from L₈, then fill L₃ from L₅, leaving 2 in L₅. Empty L₃ into L₈. Empty L₅ into L₃ (so now L₈ has 6, L₅ has 0, L₃ has 2). Fill L₅ from L₈. Fill L₃ from L₅. Empty L₃ into L₈. Now L₅ and L₈ each contain 4.

Now consider the general case. It is an easy induction that the amount in each container is always a multiple of gcd(m,n). Use induction on the number of steps, and note that the only possible move is to replace a, b by D, a+b-D, where D is one of 0, m, n, m+n. So it is certainly a necessary condition that (m+n)/2 is divisible by gcd(m,n). In particular, it must be an integer and so m+n must be even. So it remains to show that if m+n is even and (m+n)/2 is a multiple of gcd(m,n) then we can get (m+n)/2 into L_m.

If m = n, then that is trivial. So assume m > n. Put d = m-n. Now suppose that after some moves we have got k in the L_n and the rest (m+n-k) in the L_m+n. Fill L_m from L_m+n, then fill L_n from L_m. That gives m-(n-k) = k+d in L_m. Now k+d = qn + r for some 0 ≤ r < n. Repeatedly (or more precisely q times) fill L_n from L_m and empty it into L_m+n, finally pour the remainder of r from L_m into L_n. So starting with all the wine in L_m+n (ie k = 0), and iterating this process we get [hd] in L_n where [hd] denotes the residue of hd mod n.

Now we may put (m+n)/2 = Qn + R, where 0 ≤ R < n. Since n and (m+n)/2 are multiples of gcd(m,n), so is R. But gcd(m,n) = gcd(d,n). So R is a multiple of gcd(d,n). But that means we can write R = hd - h'n for some non-negative integers h, h'. In other words, R = [hd] for some non-negative integer h. Hence we can get R into L_n. Now empty L_m into L_m+n, empty L_n into L_m and then Q times fill L_n from L_m+n and empty it into L_m, giving Qn+R in L_m as required.

Problem 6

The centers of the faces of a cube form a regular octahedron of volume V. Through each vertex of the cube we may take the plane perpendicular to the long diagonal from the vertex. These planes also form a regular octahedron. Show that its volume is 27V.

Solution

Let the cube have side k. A, B are two adjacent vertices of the small octahedron, and AX = BX = k/2 and ∠AXB = 90^o, so AB = k/√2.

The large octahedron has the vertices of the cube at the center of its faces. The line joining the centers of OPS and OQR is parallel to PQ and 2/3 the length. But it is also k√2, so the side of the large octaheron is (3/2)k√2 = 3k/√2 or 3 x the side of the small octahedron. Hence the volume of the large octahedron is 3³ = 27 x the volume of the small.

[Read More...]

2nd Brazilian Mathematical Olympiad Problems 1980

2nd Brazilian Mathematical Olympiad Problems 1980

1.  Box A contains black balls and box B contains white balls. Take a certain number of balls from A and place them in B. Then take the same number of balls from B and place them in A. Is the number of white balls in A then greater, equal to, or less than the number of black balls in B?

2.  Show that for any positive integer n > 2 we can find n distinct positive integers such that the sum of their reciprocals is 1.

3.  Given a triangle ABC and a point P₀ on the side AB. Construct points P_i, Q_i, R_i as follows. Q_i is the foot of the perpendicular from P_i to BC, R_i is the foot of the perpendicular from Q_i to AC and P_i is the foot of the perpendicular from R_i-1 to AB. Show that the points P_i converge to a point P on AB and show how to construct P.

4.  Given 5 points of a sphere radius r, show that two of the points are a distance ≤ r √2 apart. 

Solutions

Problem 1

Box A contains black balls and box B contains white balls. Take a certain number of balls from A and place them in B. Then take the same number of balls from B and place them in A. Is the number of white balls in A then greater, equal to, or less than the number of black balls in B?
Answer
Equal.
Solution
Suppose we move n balls from A to B, then x white balls from B and n-x black balls from B. That leaves x black balls in B. So both numbers equal x.

Problem 2
Show that for any positive integer n > 2 we can find n distinct positive integers such that the sum of their reciprocals is 1.
Solution
We have 1/2 + 1/3 + 1/6 = 1. Now we have 1/2 + 1/4 + 1/8 + ... + 1/2ⁿ + 1/2ⁿ = 1, replace the second 1/2ⁿ by (1/2 + 1/3 + 1/6) 1/2ⁿ to get n+3 terms (n ≥ 1): 1/2 + 1/4 + 1/8 + ... + 1/2ⁿ⁺¹ + 1/(3·2ⁿ) + 1/(3·2ⁿ⁺¹) = 1. For example:
1/2 + 1/4 + 1/6 + 1/12 = 1
1/2 + 1/4 + 1/8 + 1/12 + 1/24 = 1

Problem 3
Given a triangle ABC and a point P₀ on the side AB. Construct points P_i, Q_i, R_i as follows. Q_i is the foot of the perpendicular from P_i to BC, R_i is the foot of the perpendicular from Q_i to AC and P_i is the foot of the perpendicular from R_i-1 to AB. Show that the points P_i converge to a point P on AB and show how to construct P.
Solution

It is clear from the diagram that Q_nQ_n+1 = P_nP_n+1 cos B, R_nR_n+1 = Q_nQ_n+1 cos C and P_nP_n+1 = R_n-1R_n cos A. Hence P_nP_n+1 = kⁿ P₀P₁, where |k| = |cos A cos B cos C| < 1. If we take the direction A to B as positive, then the signed distance P_nP_n+1 may be positive or negative, but the series 1 + |k| + |k|² + |k|³ + ... converges to 1/(1-|k|), so P₀P₁ + P₁P₂ + P₂P₃ + ... is absolutely convergent and hence convergent. So the points P_i converge to a point P on the line AB.

Take any point P' on AB, Take Q' as the foot of the perpendicular from P' to BC. Now take R' as the intersection of the lines through P' perpendicular to AB and through Q' perpendicular to AC. Now P'Q'R' is similar to the desired triangle PQR. Since B, P', P are collinear and B, Q', Q are collinear, it follows that B, R', R must be collinear. Thus extend BR' to meet AC at R. It is now straightforward to construct Q, then P. 

Problem 4
Given 5 points of a sphere radius r, show that two of the points are a distance ≤ r √2 apart.
Solution

Suppose the result is false so that we can find 5 points with the distance between any two > r√2. Then the angle subtended by any two at the center of the sphere is > 90^o. Take one of the points to be at the north pole. Then the other four must all be south of the equator. Two must have longitude differing by ≤ 90^o.

It is now fairly obvious that these two points subtend an angle ≤ 90^o at the center. To prove it we may take rectangular coordinates with origin at the center of the sphere so that both points have all coordinates non-negative. Suppose one is (a, b, c) and the other (A, B, C). Then since both lie on the sphere a² + b² + c² = A² + B² + C² = r², and the square of the distance between them is (a-A)² + (b-B)² + (c-C)² ≤ (a² + b² + c²) + (A² + B² + C²) = 2r², so the distance ≤ r√2, as required.

[Read More...]

1st Brazilian Mathematical Olympiad Problems 1979

1st Brazilian Mathematical Olympiad Problems 1979

1.  Show that if a < b are in the interval [0, π/2] then a - sin a < b - sin b. Is this true for a < b in the interval [π, 3π/2]?

2.  The remainder on dividing the polynomial p(x) by x² - (a+b)x + ab (where a and b are unequal) is mx + n. Find the coefficients m, n in terms of a, b. Find m, n for the case p(x) = x²⁰⁰ divided by x² - x - 2 and show that they are integral.

3.  The vertex C of the triangle ABC is allowed to vary along a line parallel to AB. Find the locus of the orthocenter.

4.  Show that the number of positive integer solutions to x₁ + 2³x₂ + 3³x₃ + ... + 10³x₁₀ = 3025 (*) equals the number of non-negative integer solutions to the equation y₁ + 2³y₂ + 3³y₃ + ... + 10³y₁₀ = 0. Hence show that (*) has a unique solution in positive integers and find it.

5.(i)   ABCD is a square with side 1. M is the midpoint of AB, and N is the midpoint of BC. The lines CM and DN meet at I. Find the area of the triangle CIN. (ii)   The midpoints of the sides AB, BC, CD, DA of the parallelogram ABCD are M, N, P, Q respectively. Each midpoint is joined to the two vertices not on its side. Show that the area outside the resulting 8-pointed star is 2/5 the area of the parallelogram.

(iii)   ABC is a triangle with CA = CB and centroid G. Show that the area of AGB is 1/3 of the area of ABC.

(iv)   Is (ii) true for all convex quadrilaterals ABCD? 

Solutions

Problem 1

Show that if a < b are in the interval [0, π/2] then a - sin a < b - sin b. Is this true for a < b in the interval [π, 3π/2]?

Answer

Yes.

Solution

We have b = (b+a)/2 + (b-a)/2, a = (b+a)/2 - (b-a)/2, so sin b - sin a = (sin((b+a)/2) cos((b-a)/2) + sin((b-a)/2) cos((b+a)/2) ) - (sin((b+a)/2) cos((b-a)/2) - sin((b-a)/2) cos((b+a)/2) ) = 2 sin((b-a)/2) cos((b+a)/2) ≤ 2 sin((b-a)/2) < 2 (b-a)/2 = b-a.

The second case is trivial because both x and -sin x are increasing in the interval [π, 3π/2].

Problem 2

The remainder on dividing the polynomial p(x) by x² - (a+b)x + ab (where a and b are unequal) is mx + n. Find the coefficients m, n in terms of a, b. Find m, n for the case p(x) = x²⁰⁰ divided by x² - x - 2 and show that they are integral.

Answer

m = (2²⁰⁰-1)/3, n = (2²⁰⁰+2)/3.

Solution

p(x) = q(x)(x-a)(x-b) + mx + n. So putting x = a, b we get p(a) = ma + n, p(b) = mb + n. Solving, m = (p(a)-p(b))/(a-b), n = (p(b)a-p(a)b)/(a-b).

In the case given a = 2, b = -1, so m = (2²⁰⁰-1)/3, n = (2²⁰⁰+2)/3. Note that 2 = -1 mod 3, so 2²⁰⁰ = 1 mod 3 and hence 2²⁰⁰ - 1 is a multiple of 3, so m is integral. n = m+1, so n is also integral.

Problem 3

The vertex C of the triangle ABC is allowed to vary along a line parallel to AB. Find the locus of the orthocenter.

Answer

A parabola.

Solution

Take axes so that A is (-a,0), B is (a,0) and C is (k,b). Then the orthocenter lies on the line x = k. The line AC has gradient b/(k+a), so the perpendicular has gradient -(k+a)/b. Hence the altitude from B has equation y + (x-a)(k+a)/b = 0. So the intersection is x = k, y = -(k-a)(k+a)/b. So the locus is all or part of the parabola by = a²-x². But we can get an orthocenter with any x-coordinate (by taking C to have the same x-coordinate), so we can get all points on the parabola.

Problem 4

Show that the number of positive integer solutions to x₁ + 2³x₂ + 3³x₃ + ... + 10³x₁₀ = 3025 (*) equals the number of non-negative integer solutions to the equation y₁ + 2³y₂ + 3³y₃ + ... + 10³y₁₀ = 0. Hence show that (*) has a unique solution in positive integers and find it.

Answer

x₁ = x₂ = ... = x₁₀ = 1.

Solution

We have 1³ + 2³ + ... + 10³ = 3025. Now x_i is a positive integer solution to (*) iff y_i = x_i - 1 are all non-negative and satisfy (y₁+1) + 2³(y₂+1) + 3³(y₃+1) + ... + 10³(y₁₀+1) = 3025 and hence y₁ + 2³y₂ + 3³y₃ + ... + 10³y₁₀ = 0. But that clearly has the unique solution y_i = 0, so the unique solution to (*) is x_i = 1.

Problem 5

(i)   ABCD is a square with side 1. M is the midpoint of AB, and N is the midpoint of BC. The lines CM and DN meet at I. Find the area of the triangle CIN.

(ii)   The midpoints of the sides AB, BC, CD, DA of the parallelogram ABCD are M, N, P, Q respectively. Each midpoint is joined to the two vertices not on its side. Show that the area outside the resulting 8-pointed star is 2/5 the area of the parallelogram.

(iii)   ABC is a triangle with CA = CB and centroid G. Show that the area of AGB is 1/3 of the area of ABC.

(iv)   Is (ii) true for all convex quadrilaterals ABCD?

Answer

(i) 1/20, (iv) no.

Solution

(i) CIN is similar to DCN, so area CIN = (CN/DN)² area DCN = ( (1/2)/(√5/2) )² 1/4 = 1/20.

(ii) If we stretch the plane parallel to one of the squares sides then all areas are increased by the same factor and hence the ratio (area CIN/area ABCD) is unchanged. If we now shear parallel to one of the sides, areas are unchanged, so the ratio (area CIN/area ABCD) remains 1/20. Thus the result holds for parallelograms. The area outside the star is made up of 8 small triangles, each area 1/20, so it is 2/5.

(iii) Let the median be AM. Then AGB and ABC have the same base AB, so area AGB/area ABC = GM/AM = 1/3. [This is trivial, but they wanted to give a hint for part (iv)]

(iv) If we take A and B close together, then we get the same figure as in (iii) and so the ratio tends to 1/3. Hence the 2/5 result is not true for all convex quadrilaterals.

[Read More...]