3rd Brazilian Mathematical Olympiad Problems 1981
1. For which k does the system x2 - y2 = 0, (x-k)2 + y2 = 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 x2 - y2 = 0, (x-k)2 + y2 = 1 have exactly (1) two, (2) three real solutions? Answer
(1) k = ±√2, (2) k = ±1.
Solution
We have (x-k)2 + x2 = 1, so 2x2 - 2kx + k2-1 = 0. This has 0, 1 or 2 real solutions according as k2 >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-k2), 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 2n ≥ 10m-1. Then 2n-1 < 10m-1, so 2n+2 < 8·10m-1 < 10m. So 2n, 2n+1 and 2n+2 all have m digits. Thus there are at least 3 powers of 2 with m digits.
2n-1 ≥ 5·10m-2 (otherwise 2n < 10m-1). Hence 2n+4 ≥ 32·5·10m-2 > 10m, so 2n+4 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)/log102 and (m/log102 - 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 M1, N1 be the midpoints of AC, BC respectively. Then take M2, N2 as the midpoints of M1C, N1C respectively, and so on until we get MnNn < k. We can now join Mn and Nn 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 = MnC, then draw circles center A radius MnNn and center X radius CNn to intersect at a point Y with AXY congruent to MnCNn and hence Y on AB. Now extend AY to get AB.
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 X1 joined to all the other 99 points. Now repeat the argument for the other 99 points, that gives a point X2 joined to the other 98. But it is also joined to X1, 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 L8, L5, L3. Fill L5 from L8, then fill L3 from L5, leaving 2 in L5. Empty L3 into L8. Empty L5 into L3 (so now L8 has 6, L5 has 0, L3 has 2). Fill L5 from L8. Fill L3 from L5. Empty L3 into L8. Now L5 and L8 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 Lm.
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 Ln and the rest (m+n-k) in the Lm+n. Fill Lm from Lm+n, then fill Ln from Lm. That gives m-(n-k) = k+d in Lm. Now k+d = qn + r for some 0 ≤ r < n. Repeatedly (or more precisely q times) fill Ln from Lm and empty it into Lm+n, finally pour the remainder of r from Lm into Ln. So starting with all the wine in Lm+n (ie k = 0), and iterating this process we get [hd] in Ln 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 Ln. Now empty Lm into Lm+n, empty Ln into Lm and then Q times fill Ln from Lm+n and empty it into Lm, giving Qn+R in Lm 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 = 90o, 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 33 = 27 x the volume of the small.
Labels:
Brazilian Mathematical Olympiad
Previous Article
