28th USA Mathematical Olympiad 1999 Problems
A1. Certain squares of an n x n board are colored black and the rest white. Every white square shares a side with a black square. Every pair of black squares can be joined by chain of black squares, so that consecutive members of the chain share a side. Show that there are at least (n2 - 2)/3 black squares.
A2. For each pair of opposite sides of a cyclic quadrilateral take the larger length less the smaller length. Show that the sum of the two resulting differences is at least twice the difference in length of the diagonals.
A3. p is an odd prime. The integers a, b, c, d are not multiples of p and for any integer n not a multiple of p, we have {na/p} + {nb/p} + {nc/p} + {nd/p} = 2, where { } denotes the fractional part. Show that we can find at least two pairs from a, b, c, d whose sum is divisible by p.
B1. A set of n > 3 real numbers has sum at least n and the sum of the squares of the numbers is at least n2. Show that the largest positive number is at least 2.
B2. Two players play a game on a line of 2000 squares. Each player in turn puts either S or O into an empty square. The game stops when three adjacent squares contain S, O, S in that order and the last player wins. If all the squares are filled without getting S, O, S, then the game is drawn. Show that the second player can always win.
B3. I is the incenter of the triangle ABC. The point D outside the triangle is such DA is parallel to BC and DB = AC, but ABCD is not a parallelogram. The angle bisector of BDC meets the line through I perpendicular to BC at X. The circumcircle of CDX meets the line BC again at Y. Show that DXY is isosceles.
Solution
28th USA Mathematical Olympiad 1999
Problem A1
Certain squares of an n x n board are colored black and the rest white. Every white square shares a side with a black square. Every pair of black squares can be joined by chain of black squares, so that consecutive members of the chain share a side. Show that there are at least (n2 - 2)/3 black squares.
Solution
Concentrate on the chain condition. We show by induction that if k squares are black and satisfy the chain condition, then at most 3k + 2 squares are black or share a side with a black square. This is obvious for k = 1. Suppose it is true for k and that we have k+1 black squares satisfying the chain condition. It must be possible to pick a black square so that the remaining k black squares still satisfy the chain condition. The remaining k black squares give at most 3k+2 black or sharing a side with a black square, and the picked square adds at most 3. That completes the induction. The result follows immediately, since we must have n2 ≤ 3k + 2, where k is the number of black squares.
Actually, it is not trivial to show that it must be possible to pick a black square so that the remaining k black squares still satisfy the chain condition. It is equivalent to showing that in any connected graph you can find a point such that if you remove the point the graph is still connected. The trick is to take two points A and B which are the maximum distance apart (distance is the minimum number of edges you must traverse to get from one to the other). The claim is that removal of either of these points leaves the graph connected. For suppose removing A left a disconnected graph, then there must be a point C such that B and C are not joined by a path when A is removed. Since they are joined when A is present, all paths joining them must pass through A and hence exceed the length of all paths from A to B. Contradiction. Problem A2
For each pair of opposite sides of a cyclic quadrilateral take the larger length less the smaller length. Show that the sum of the two resulting differences is at least twice the difference in length of the diagonals.
Solution
We prove the slightly stronger result that the difference between two opposite sides is at least the difference between the diagonals. Suppose the diagonals meet at X. Then AXB, DXC are similar. Suppose AB = kCD with k ≥ 1. Then BE = kCE and AE = kDE. Suppose CE ≥ DE. Then CD + DE > CE, so CD > CE - DE, so (k-1) CD > (k-1)(CE - DE) or AB - CD > BE - CE - AE + DE = BD - AC.
p is an odd prime. The integers a, b, c, d are not multiples of p and for any integer n not a multiple of p, we have {na/p} + {nb/p} + {nc/p} + {nd/p} = 2, where { } denotes the fractional part. Show that we can find two of a, b, c, d whose sum is divisible by p.
Solution
Solution by Michael J Doré
n denote the residue of n mod p, so n = 0, 1, 2, ... , or p-1. Thus {na/p} = na/p, and we have that na + nb + nc + nd = 2p for n not a multiple of p.
Let ω be a complex pth root of 1. We show first that ω + 2ω2 + 3ω3 + ... + (p-1)ωp-1 = p/(ω - 1). Suppose the sum is S. Then (1 - 2ω + ω2)S = ω - pωp + (p-1)ωp+1 (we need only look at the two lowest and two highest powers - the others all cancel because k - 2(k-1) + (k-2) = 0) = p(ω - 1). Hence S = p/(ω - 1).
Take residues a', b', c', d', so that aa' = bb' = cc' = dd' = 1 mod p. Then for any integers m, n we have mnaa' = mn mod p. Hence -ma' na = -mn mod p. Hence ω-ma' na = ω-mn. So na ω-ma' na = na ω-mn. Similarly for b, c, d. Take n not a multiple of p and add the four equations to get: na ω-ma' na + nb ω-mb' nb + nc ω-mc' nc + nd ω-md' nd = 2p ω-mn.
As n runs through 1, 2, ... , p-1, each of na, nb, nc, nd runs through a complete set of non-zero residues. If we take m to be not a multiple of p, then so does -mn, so adding the equations for n = 1, 2, ... , p-1, we get na ∑ kω-a'mk + ∑ k ω-b'mk + ∑ kω-c'mk + ∑ kω-d'mk = 2p(ω + ω2 + ... + ωp-1) = -2p.
Since ω-a'm is also a complex pth root of 1, we have ∑ kω-a'mk = p/(ω-a'm - 1) and similarly for the other terms. So the equation becomes: 1/(ω-a'm - 1) + 1/(ω-b'm - 1) + 1/(ω-c'm - 1) + 1/(ω-d'm - 1) = -2.
Multiplying through by (ω-a'm - 1)(ω-b'm - 1)(ω-c'm - 1)(ω-d'm - 1), expanding and simplifying, we get 2 + ω-a'm-b'm-c'm + ω-a'm-b'm-d'm + ω-a'm-c'm-d'm + ω-b'm-c'm-d'm = ω-a'm + ω-b'm + ω-c'm + ω-d'm + 2ω-a'm-b'm-c'm-d'm (*). Note that this equation is also true for m = 0 (when it is just 5 = 5). Now sum the equations for m = 0, 1, 2, ... , p-1. We have ∑ ωk = p if k is a multiple of p, and 0 otherwise. Obviously the first term ∑ 2 gives 2p and the other terms on the lhs give non-negative sums, so ∑ lhs is at least 2p. The first four terms on the rhs all have zero sum, so the last term must have sum 2p, so a' + b' + c' + d' must be a multiple of p. Thus (*) becomes ωa'm + ωb'm + ωc'm + ωd'm = ω-a'm + ω-b'm + ω-c'm + ω-d'm. Multiply through by ω-a'm and sum for m = 0, 1, 2, ... , p-1. The first term on the lhs has sum p and the others have non-negative sum. The first term on the rhs has zero sum, so one of the others must have positive sum. Hence p divides at least one of (a'+b'), (a'+c'), (a'+d'). Without loss of generality it divides a' + b'. In other words a' + b' = 0 mod p. Multiplying by ab, we get a + b = 0 mod p.
A set of n > 3 real numbers has sum at least n and the sum of the squares of the numbers is at least n2. Show that the largest positive number is at least 2.
Solution
Let the numbers be x1, x2, ... , xn. Notice first that x1 = x2 = ... = xn-1 = 2, xn = 2 - n, gives ∑ xi = (n - 1)2 + (2 - n) = n, ∑ xi2 = (n - 1)4 + (4 - 4n + n2) = n2, so the inequality is best possible.
Suppose the result is false. So we have a set of numbers with S xi ≥ n, ∑ xi2 ≥ n2 and max xi < 2. At least one of the numbers must be negative, since otherwise we have n ≥ 4, so n2 ≥ 4n > ∑ xi2. Contradiction. This allows us to assume that ∑ xi = n, for if it is greater, we may just decrease a negative xi until it becomes true (∑ xi2 will be increased, so it will remain at least n2).
Now suppose two of the xi, namely x and y, are less than 2. Then if we replace them by 2 and x + y - 2, the sum is unaffected and the sum of squares is increased by 2(2 - x)(2 - y). Since we start with all the xi less than 2, we may do this repeatedly until we reach a set with all the numbers 2 except one. Since the sum is unchanged, the other number must be 2 - n, and, as shown above, that makes the sum of the squares n2. But we have increased the sum of the squares at each step. Contradiction.
Two players play a game on a line of 2000 squares. Each player in turn puts either S or O into an empty square. The game stops when three adjacent squares contain S, O, S in that order and the last player wins. If all the squares are filled without getting S, O, S, then the game is drawn. Show that the second player can always win.
Solution
Suppose a square is such that if you play there then that allows your opponent to win on the following move. If you play an O, then your opponent must win by playing an adjacent S. So we must have S 1 2 3, where 1 and 2 are empty and you play O on square 1. But you also lose if you play S, so your opponent must then win by playing O on 2, which means that 3 must already contain an S. But now the situation is symmetrical, so that 2 is also a losing square. Thus, until someone plays on one of them, losing squares always occur in pairs.
The board has an even number of squares, so the first player always faces a board with an even number of squares not yet occupied, whereas the second player always faces a board with an odd number of squares not yet occupied. Thus provided (1) there is at least one pair of losing squares, (2) he never plays on a losing square, and (3) he makes the obvious winning move if the first player ever creates the opportunity, then the second player is sure to win, because the first player will eventually face a board with only losing squares available for play.
To make sure there is at least one pair of losing squares the second player must create it. He can always do this by placing an S on his first move well away from the first player's move and from the edges of the board. Then on his second move (assuming the first player has not been stupid enough to allow him an immediate win) he can always play another S three away from it, creating a pair of losing squares. Thereafter, he must simply take care to win if there is a winning move and otherwise to avoid losing plays.
I is the incenter of the triangle ABC. The point D outside the triangle is such DA is parallel to BC and DB = AC, but ABCD is not a parallelogram. The angle bisector of BDC meets the line through I perpendicular to BC at X. The circumcircle of CDX meets the line BC again at Y. Show that DXY is isosceles.
Solution
Let IX meet BC at Z. Then using equal tangents, (BC - CZ) + (AC - CZ) = AB, so CZ = (AC + BC - AB)/2. Suppose the excircle opposite D of DBC touches BC at Z'. Then, again considering equal tangents, DB + (BC - CZ') = DC + CZ', so CZ' = (BD + BC - DC)/2 = (AC + BC - AB)/2 = CZ, so Z' and Z coincide. Since X lies on the perpendicular to BC at Z and on the bisector of ∠BDC, it must also be the center of the excircle. Hence XC is the exterior bisector of ∠BCD. So ∠XCB = 90 - ∠BCD/2.
By construction, YDCX is cyclic, so ∠YDX = ∠YCX = ∠XCB. Also ∠BCD = ∠YCD = ∠YXD. Hence ∠YDX = 90 - ∠YXD/2. Hence YX = DX.
Labels:
USAMO
Previous Article
