40th British Mathematical Olympiad 2004 Problems

40th British Mathematical Olympiad 2004 Problems

1.  ABC is an equilateral triangle. D is a point on the side BC (not at the endpoints). A circle touches BC at D and meets the side AB at M and N, and the side AC at P and Q. Show that BD + AM + AN = CD + AP + AQ.

2.  Show that there is a multiple of 2004 whose binary expression has exactly 2004 0s and 2004 1s.

3.  a, b, c are reals with sum zero. Show that a³ + b³ + c³ > 0 iff a⁵ + b⁵ + c⁵ > 0. Prove the same result for 4 reals.

4.  The decimal 0.a₁a₂a₃a₄... hs the property that there are at most 2004 distinct blocks a_ka_k+1...a_k+2003 in the expansion. Show that the decimal must be rational.

[more...]

39th British Mathematical Olympiad 2003 Problems

1.  Find all integers 0 < a < b < c such that b - a = c - b and none of a, b, c have a prime factor greater than 3.

2.  D is a point on the side AB of the triangle ABC such that AB = 4·AD. P is a point on the circumcircle such that angle ADP = angle C. Show that PB = 2·PD.

3.  f is a bijection on the positive integers. Show that there are three positive integers a₀ < a₁ < a₂ in arithmetic progression such that f(a₀) < f(a₁) < f(a₂). Is there necessarily an arithmetic progression a₁ < a₂ < ... < a₂₀₀₃ such that f(a₀) < f(a₁) < ... < f(a₂₀₀₃)?

4.  Let X be the set of non-negative integers and f : X → X a map such that ( f(2n+1) )² - ( f(2n) )² = 6 f(n) + 1 and f(2n) ≥ f(n) for all n in X. How many numbers in f(X) are less than 2003? 

Solutions

Problem 1

Find all integers 0 < a < b < c such that b - a = c - b and none of a, b, c have a prime factor greater than 3.

Answer

(a, b, c) = (k, 2k, 3k), (2k, 3k, 4k) or (2k, 9k, 16k), where k = 2^m3ⁿ.

Solution

It is sufficient to find solutions (A, B, C) without any common factor k which divides A, B and C, for then the complete set of solutions is (kA, kB, kC) with k = 2^m3ⁿ.

Put D = B - A, then C = A + 2D, which has the same parity as A, so A and B must have opposite parity.

Suppose A is odd. Then C is odd and greater than 1, hence a power of 3. If A > 1, then A is also a power of 3, and hence B = (A + C)/2 is also. Contradiction. So A must be 1. Suppose C = 3ⁿ. Then B = (A + C)/2 = (1 + (4 - 1)ⁿ)/2 = (1 + (-1)ⁿ + (-1)^n-14n + terms in 4² and higher)/2. Hence n is odd and B = 2 mod 4. But B is a power of 2, so B = 2 and C = 3.

Suppose A is even, then B is odd and hence a power of 3. If A is divisible by 3, then so is C. Contradiction. So A must be a power of 2. Similarly, C must be a power of 2. If A is divisible by 4, then since C is a larger power of 2, it must also be divisible by 4. Hence 2D = C - A is divisible by 4, so B is divisible by 2. Contradiction. So A must be 2. It is easy to check that (A, B, C) = (2, 3, 4) and (2, 9, 16) are solutions. It remains to show that there are no solutions with B divisible by 27.

Thanks to John Pye for the next part

Suppose there is such a solution, then we have A = 2, C a power of 2, B = 3ⁿ = 2^m - 1 ( (A+C)/2). B = 27 does not work, so B ≥ 81 and hence m ≥ 4. We have 3⁴ = 1 mod 16, so it is easy to check that 3^4k - 1 = 0 mod 16, 3^4k+1 - 1 = 2 mod 16, 3^4k+2 - 1 = 8 mod 16, 3^4k+3 - 1 = 10 mod 16. So n must be a multiple of 4. But since 3⁴ = 1 mod 5, that means 3ⁿ - 1 = 0 mod 5, so B cannot be a power of 2. Contradiction. 

Problem 2

D is a point on the side AB of the triangle ABC such that AB = 4·AD. P is a point on the circumcircle such that angle ADP = angle C. Show that PB = 2·PD.

Solution

 

Note that angle APB = angle C, so triangles BAP, PAD are similar. Hence BA/AP = PA/AD, giving PA = 2AD. Also BP/AP = PD/AD, so PB/PD = AP/AD = 2, as required. 

Problem 3

f is a bijection on the positive integers. Show that there are three positive integers a₀ < a₁ < a₂ in arithmetic progression such that f(a₀) < f(a₁) < f(a₂). Is there necessarily an arithmetic progression a₁ < a₂ < ... < a₂₀₀₃ such that f(a₀) < f(a₁) < ... < f(a₂₀₀₃)?

Solution

Thanks to Arne Smeets

Suppose f(k) = 1. Then certainly f(k) < f(k + h) for any positive integer h. Now consider the sequence f(k+1), f(k+2), f(k+4), f(k+8), f(k+16), ... . Each term is different since k is a bijection. It cannot be always decreasing, since there are only finitely many positive values less than f(k+1). So for some 2ⁿ we have f(k + 2ⁿ) < f(k + 2ⁿ⁺¹). But now k, k + 2ⁿ, k + 2ⁿ⁺¹ is the required arithmetic progression.

We can find a bijection which does not even give f(a₀) < f(a₁) < f(a₂) < f(a₃) for any arithmetic progression a₀ < a₁ < a₂ < a₃.

For example, take f(n) = 2, 1, 8, 7, ... , 3, 26, 25, ... , 9, 80, 79, ... , 27, ... (for n = 1, 2, 3, ... ). Suppose that f(a₀) < f(a₁) < f(a₂) < f(a₃). Now a₁ and a₂ cannot be in the same block, and a₂ and a₃ cannot be in the same block, so there must be a complete block between a₁ and a₃. In other words, if 3ⁿ <= a₁ < 3ⁿ⁺¹, then a₃ >= 3ⁿ⁺² and a₃ - a₁ > 2·3ⁿ⁺¹. But a₁ - a₀ < 3ⁿ⁺¹. So a₀, a₁, a₂, a₃ is not an arithmetic progression. 

Problem 4

Let X be the set of non-negative integers and f : X → X a map such that ( f(2n+1) )² - ( f(2n) )² = 6 f(n) + 1 and f(2n) >= f(n) for all n in X. How many numbers in f(X) are less than 2003?

Answer

128

Solution

Obviously f(2n) + 3 > f(2n+1) > f(2n), so f(2n+1) = f(2n) + 1 or f(2n) + 2. But f(2n)² + 6 f(n) + 1 and f(2n)² have opposite parity, so we must have f(2n+1) = f(2n) + 1. Hence f(2n) = 3 f(n).

So, in particular, f(0) = 0. Hence f(1) = 1. A trivial induction now gives that f is strictly monotonic increasing. Obviously f(128) = 3⁷ = 2187 > 2003.

f(127) = f(126) + 1 = 3 f(63) + 1 = 3 f(62) + 4 = 9 f(31) + 4 = 9 f(30) + 13 = 27 f(15) + 13 = 27 f(14) + 40 = 81 f(7) + 40 = 81 f(6) + 121 = 243 f(3) + 121 = 243 f(2) + 364 = 729 f(1) + 364 = 1093 < 2003. So the 128 distinct numbers f(0), f(1), ... , f(127) are less than 2003.

[more...]

38th British Mathematical Olympiad 2002 Problems

38th British Mathematical Olympiad 2002 Problems

1.  From the foot of an altitude in an acute-angled triangle perpendiculars are drawn to the other two sides. Show that the distance between their feet is independent of the choice of altitude.

2.  n people wish to sit at a round table which has n chairs. The first person takes an seat. The second person sits one place to the right of the first person, the third person sits two places to the right of the second person, the fourth person sits three places to the right of the third person and so on. For which n is this possible?

3.  The real sequence x₁, x₁, x₂, ... is defined by x₀ = 1, x_n+1 = (3x_n + √(5x_n² - 4) )/2. Show that all the terms are integers.

4.  S₁, S₂, ... , S_n are spheres of radius 1 arranged so that each touches exactly two others. P is a point outside all the spheres. Let x₁, x₂, ... , x_n be the distances from P to the n points of contact between two spheres and y₁, y₂, ... , y_n be the lengths of the tangents from P to the spheres. Show that x₁x₂ ... x_n ≥ y₁y₂ ... y_n. 

Solutions

Problem 1

From the foot of an altitude in an acute-angled triangle perpendiculars are drawn to the other two sides. Show that the distance between their feet is independent of the choice of altitude.

Solution

Let the triangle be ABC and the altitude AD. Let M be the midpoint of AD, and E, F the feet of the perpendiculars from D to AB and AC respectively. Angles AED and AFD are 90 deg, so AEDF is cyclic and M is the center of the circle. Hence angle EMF = 2 angle A and EF = 2 ME sin A = AD sin A = 2 (area ABC) (sin A)/BC. Similarly the distances obtained starting with the other two altitudes are 2 (area ABC) (sin B)/AC and 2 (area ABC)(sin C)/AB. But these are all equal by the sine rule. 

Problem 2

n people wish to sit at a round table which has n chairs. The first person takes an seat. The second person sits one place to the right of the first person, the third person sits two places to the right of the second person, the fourth person sits three places to the right of the third person and so on. For which n is this possible?

Solution

Answer: n = 2^m for m a non-negative integer.

Label the seats 0, 1, 2, ... , n-1. The kth person sits in seat k(k - 1)/2 for k = 1, 2, ... , n. So the seating plan is possible iff the n numbers k(k - 1)/2 are incongruent mod n for k = 1, 2, ... , n. Suppose first that n = 2^m. We have h(h - 1)/2 - k(k - 1)/2 = (h - k)(h + k - 1)/2. If h and k are unequal, then h - k and (h + k - 1) are non-zero. But they have opposite parity, and both are less than 2n, so one is odd and the other is not divisible by a higher power of 2 than 2^m. Thus (h - k)(h + k - 1)/2 cannot be divisible by 2^m. So the seating plan works for n a power of 2.

Conversely, suppose n = 2^m(2a + 1). If a <= 2^m, take h = 2^m + a + 1, k = 2^m - a. Then h - k = 2a + 1, h + k - 1 = 2^m+1, so h(h - 1)/2 and k(k - 1)/2 are equal mod n. If a > 2^m, then take h = 2^m + a + 1, k = a - 2^m + 1. Then h - k = 2^m+1, h + k - 1 = 2a + 1. So again h(h - 1)/2 and k(k - 1)/2 are equal mod n. So no seating plan is possible if n is not a power of 2. 

Problem 3

The real sequence x₁, x₁, x₂, ... is defined by x₀ = 1, x_n+1 = (3x_n + √(5x_n² - 4) )/2. Show that all the terms are integers.

Solution

(2x_n+1 - 3x_n)² = 5x_n² - 4, so x_n+1² - 3x_n+1x_n + x_n² = -1. Subtracting the corresponding equation for n-1 gives: x_n+1² - 3x_n(x_n+1 - x_n-1) - x_n-1² = 0. So (x_n+1 - x_n)(x_n+1 - 3x_n + x_n-1) = 0. But it is obvious from the definition that x_n+1 >= 3/2 x_n, so x_n+1 - x_n is non-zero. Hence x_n+1 = 3x_n - x_n-1. But x₀ = 1, x₁ = 2, so by a trivial induction all x_n are integral. 

Problem 4

S₁, S₂, ... , S_n are spheres of radius 1 arranged so that each touches exactly two others. P is a point outside all the spheres. Let x₁, x₂, ... , x_n be the distances from P to the n points of contact between two spheres and y₁, y₂, ... , y_n be the lengths of the tangents from P to the spheres. Show that x₁x₂ ... x_n ≥ y₁y₂ ... y_n.

Solution

It is sufficient to show that if two circles centers O and O' both with radius 1 touch at X and P is a point outside the circles with tangents PY, PZ to the two circles, then PY·PZ ≤ PX². Let the angle between PX and the line of centers be θ and the distances PX, PY, PZ be x, y, z respectively. By the cosine formula, PO² = x² + 1 - 2x cos θ, so y² = x² - 2x cos θ. Similarly, z² = x² + 2x cos θ. Hence y²z² = x⁴ - 4x²cos²θ ≤ x⁴.

[more...]

37th British Mathematical Olympiad 2001 Problems

37th British Mathematical Olympiad 2001 Problems

1.  A has a marbles and B has b < a marbles. Starting with A each gives the other enough marbles to double the number he has. After 2n such transfers A has b marbles. Find a/b in terms of n.

2.  Find all integer solutions to m²n + 1 = m² + 2mn + 2m + n.

3.  ABC is a triangle with AB greater than AC. AD is the angle bisector. E is the point on AB such that ED is perpendicular to BC. F is the point on AC such that DE bisects angle BEF. Show that ∠FDC = ∠BAD.

4.  n dwarfs with heights 1, 2, 3, ... , n stand in a circle. S is the sum of the (non-negative) differences between each adjacent pair of dwarfs. What are the maximum and minimum possible values of S? 

Solutions

Problem 1

A has a marbles and B has b < a marbles. Starting with A each gives the other enough marbles to double the number he has. After 2n such transfers A has b marbles. Find a/b in terms of n.

Solution

After 2 transfers A has 2(a - b) = 4a - 2N marbles, where N = a + b. Suppose A has a_n marbles after 2n transfers. We have just shown that a_n+1 = 4a_n - 2N. Put c_n = a_n - 2N/3, then c_n+1 = 4c_n. We have c₀ = a - 2N/3, so c_n = 4ⁿa - 4ⁿ2N/3. Hence a_n = 4ⁿa - 4ⁿ2N/3 + 2N/3 = (4ⁿ + 2)a/3 - 2(4ⁿ - 1)b/3. We require a_n = b and hence a/b = (2.4ⁿ + 1)/(4ⁿ + 2).

Note that we have not so far proved that there is a solution for n. We have just showed that if there is a solution then a/b has that ratio. It might be that one person has a negative number of marbles at some point. Fortunately, we do not have to worry whether the question requires us to show that n is possible, because it is easy to show that it is. The key observation is that if one person goes negative, then they remain negative. But after 2n moves neither A nor B is negative, so they cannot have been negative at any intermediate stage. 

Problem 2

Find all integer solutions to m²n + 1 = m² + 2mn + 2m + n.

Solution

Answer: (m, n) = (-1, -1), (0, 1), (1, -1), (2, -7), or (3, 7).

We have m²(n - 1) = 2m(n + 1) + n - 1 = 2m(n - 1) + 4m + (n - 1). Put k = n - 1 and this becomes m²k = 2mk + 4m + k (*).

If k = 0, then m = 0. This gives the solution m = 0, n = 1. If m = 0, then k = 0, so we assume m and k are non-zero. From (*) m must divide k and k must divide 4m. Put k = mh. Then h divides 4, so h = ±1, ±2 or ±4. Also we can write (*) as (m² - 2m - 1)h - 4 = 0.

If h = 1, then m² - 2m - 5 = 0, which has no integral solutions. If h = -1, then m² - 2m + 3 = 0, which has no integral solutions. If h = 2, then m² - 2m - 3 = 0, which has solutions m = -1 or 3. If h = -2, then m² - 2m + 1 = 0, so m = 1. If h = 4, then m² - 2m - 2 = 0, which has no integral solutions. If h = -4, then m² - 2m = 0, which has solutions m = 0, 2. 

Problem 3

ABC is a triangle with AB greater than AC. AD is the angle bisector. E is the point on AB such that ED is perpendicular to BC. F is the point on AC such that DE bisects ∠BEF. Show that ∠FDC = ∠BAD.

Solution

CD bisects ∠A and DE is the external bisector of ∠FEA. Hence D is an excenter of AEF and DF is an external bisector of ∠AFE.

∠BED = 90^o - ∠B, so ∠AEF = 2 ∠B, so ∠AFE = ∠C - ∠B. Hence ∠CFD = (180^o - (∠C - ∠B))/2 = 90^o - ∠C/2 + ∠B/2. Hence ∠FDC = 180^o - (90^o - ∠C/2 + ∠B/2) - C = 90^o - ∠B/2 - ∠C/2 = ∠A/2 = ∠BAD. 

Problem 4

n dwarfs with heights 1, 2, 3, ... , n stand in a circle. S is the sum of the (non-negative) differences between each adjacent pair of dwarfs. What are the maximum and minimum possible values of S?

Solution

Answer: min 2n - 2, max [n²/2].

The minimum is obviously 2(n-1). The difference between 1 and n is n-1 and the sum of the signed differences as we go from n to 1 either way round the circle must be n-1. The sum of the unsigned differences must be at least as large, so S ≥ 2(n-1). This is achieved by the order 1, 2, 3, ... , n.

The maximum is almost obvious. If the numbers are a₁, a₂, ... , a_n. Then each difference is a_i+1 - a_i or - a_i+1 + a_i. So the total of all the differences is k₁a₁ + k₂a₂ + ... + k_na_n, where each k_i is -2, 0 or 2 and their sum is 0. So permuting back to 1, 2, ... , n the sum is h₁ + 2h₂ + 3h₃ + ... + nh_n, where each h_i is 0 or ±2 and the sum of the h_i is 0. If n = 2m, this is maximised by taking h₁ = h₂ = ... = h_m = -2 and h_m+1 = ... = h_2m = 2, giving a sum of 2m². If n = 2m+1, it is maximised by taking h₁ = ... = h_m = -2, h_m+1 = 0, h_m+2 = ... = h_2m+1 = 2, giving a sum of 2m(m+1).

Checking that this can be achieved, we take: 1, 2m, 2, 2m-1, 3, 2m-2, ... , m-1, m+2, m, m+1 in the even case and 1, 2m+1, 2, 2m-1, 3, 2m-3, ... , m-1, m+3, m, m+2, m+1 in the odd case.

[more...]

36th British Mathematical Olympiad 2000 Problems

36th British Mathematical Olympiad 2000 Problems

1.  Two circles meet at A and B and touch a common tangent at C and D. Show that triangles ABC and ABD have the same area.

2.  Find the smallest value of x² + 4xy + 4y² + 2z² for positive reals x, y, z with product 32.

3.  Find positive integers m, n such that (m^1/3 + n^1/3 - 1)² = 49 + 20 (6^1/3).

4.  Find a set of 10 distinct positive integers such that no 6 members of the set have a sum divisible by 6. Is it possible to find such a set with 11 members? 

Solutions

Problem 1

Two circles meet at A and B and touch a common tangent at C and D. Show that triangles ABC and ABD have the same area.

Solution

Let the common tangent meet the line AB at X. We have XC² = XA·XB = XD². So C and D are equidistant from the line AB. 

Problem 2

Find the smallest value of x² + 4xy + 4y² + 2z² for positive reals x, y, z with product 32.

Solution

Answer: 96.

We have (x + 2y)² ≥ 8xy with equality iff x = 2y. Hence (x + 2y)² + 2z² ≥ 256/z + 2z² with equality iff x = 2y. We have z² + 128/z - 48 = (z - 4)²(z + 8)/z ≥ 0 with equality iff z = 4 (for positive z). Hence 256/z + 2z² ≥ 96 with equality iff z = 4. So the expression given has minimum value 96, achieved only at x = 4, y = 2, z = 4. 

Problem 3

Find positive integers m, n such that (m^1/3 + n^1/3 - 1)² = 49 + 20 (6^1/3).

Solution

A little experimentation gives (2·6^1/3 + 2·6^2/3 - 1)² = 49 + 20·6^1/3. So we can take m = 48, n = 288. 

Problem 4

Find a set of 10 distinct positive integers such that no 6 members of the set have a sum divisible by 6. Is it possible to find such a set with 11 members?

Solution

Thanks to Arne Smeets

Take five integers = 0 mod 6 and five = 1 mod 6. Then any six must include at least one and at most five = 1 mod 6 and hence their sum cannot be 0 mod 6.

Amongst any 5 numbers there must be 3 with sum = 0 mod 3. (If three numbers have the same residue, then their sum = 0 mod 3. If not, then there must be at least one for each residue, and 0 + 1 + 2 = 0 mod 3.) So given 11 numbers, we can pick a₁, a₂, a₃ with a₁ + a₂ + a₃ = 0 mod 3. From the remaining 8, we can pick another three: b₁, b₂, b₃. From the remaining 5 we can pick another three: c₁, c₂, c₃. Two of the sums a₁ + a₂ + a₃, b₁ + b₂ + b₃, c₁ + c₂ + c₃ must have the same parity, so their sum is even. Thus we have 6 numbers with sum = 0 mod 6.

[more...]

35th British Mathematical Olympiad 1999 Problems

35th British Mathematical Olympiad 1999 Problems

1.  Let X_n = {1, 2, 3, ... , n}. For which n can we partition X_n into two parts with the same sum? For which n can we partition X_n into three parts with the same sum?

2.  A circle is inscribed in a hexagon ABCDEF. It touches AB, CD and EF at their midpoints (L, M, N respectively) and touches BC, DE, FA at the points P, Q, R. Prove that LQ, MR, NP are concurrent.

3.  Show that xy + yz + zx ≤ 2/7 + 9xyz/7 for non-negative reals x, y, z with sum 1.

4.  Find the smallest possible sum of digits for a number of the form 3n² + n + 1 (where n is a positive integer). Does there exist a number of this form with sum of digits 1999? 

Solutions

Problem 1

Let X_n = {1, 2, 3, ... , n}. For which n can we partition X_n into two parts with the same sum? For which n can we partition X_n into three parts with the same sum?

Solution

The sum of all the elements of X_n is n(n+1)/2. This is odd for n = 1, 2 mod 4 and even for n = 0, 3 mod 4, so a necessary condition for two parts is that n = 0 or 3 mod 4. It is also sufficient. For n = 0 mod 4, there are an even number of pairs (1, n), (2, n-1), (3, n-2), ... each with the same sum, so we can take half the pairs in one part and half in the other. For n = 3 mod 4, there are an even number of pairs (4, n), (5, n-1), (6, n-2), ... each with the same sum, so we take half in one part and half in the other. Then we put 1 and 2 in one part and 3 in the other.

A necessary condition is that 3 divides n(n+1), so n is not 1 mod 3. That is not sufficient, because we obviously cannot divide X₂ or X₃ into three equal parts. However, it is sufficient for larger n.

Let N = n(n+1)/6. For n not 1 mod 3, this is an integer. Take a subset A of X_n by using the greedy algorithm: we repeatedly pick the largest remaining element until we get the required sum N. Thus A consists of a sequence of consecutive integers ending with n and possibly one additional element. Now take another subset B of the remaining elements, using the same algorithm. The remaining elements are 1, 2, ... , m for some m with at most one element missing. The algorithm cannot fail for A and can only fail for B if either: (1) the missing element is 1 and after picking m, m-1, ... , m-k we want 1 to complete the set, or (2) the missing element is 2, and after picking m, m-1, ... , m-k we want 2 to complete the set (we can continue with 1 but then get stuck). In case (1), we can use replace m-k and pick m-k-1 and 2. In case (2) we can replace m-k (and 1 if we got that far) and pick m-k-1 and 3.

Thus we can always get two sets with sum N. But then the remaining elements must also have sum n.

Comment. This is a weaker version of the result that if 1 + 2 + 3 + ... + n = mk, with n ≥ m, then we can divide the set into k parts with equal sum. See ASU 88/20

Problem 2

A circle is inscribed in a hexagon ABCDEF. It touches AB, CD and EF at their midpoints (L, M, N respectively) and touches BC, DE, FA at the points P, Q, R. Prove that LQ, MR, NP are concurrent.

Solution

The key is that PN is perpendicular to LM. So the three lines are the altitudes of the triangle LMN and hence concurrent.

Let the center of the circle be O. Let ∠AOL = x, so ∠LOB = x (L midpoint of AB), ∠BOP = x also (BP = BL) and ∠ROA = x. Similarly, let ∠POC = y. So ∠COM = y (CM = CP), ∠DOM = y (M midpoint of CD), ∠DOQ = y (DM = DQ). Similarly, let ∠QOE = z, so ∠EON = z (EN = EQ), ∠NOF = z (N midpoint of EF), ∠FOR = z (FN = FR). Thus 4(x + y + z) = 360^o and hence x + y + z = 90^o.

∠LOM = 2x + 2y, so if OX is the perpendicular bisector of LM, then ∠LOX = x + y. Similarly, ∠PON = 4y + 2z, so if OY is the perpendicular bisector of PN, then angle POY = 2y + z. ∠LOP = 2x, so ∠LOY = 2x + 2y + z. Hence ∠XOY = 2x + 2y + z - (x + y) = x + y + z = 90^o. In other words the perpendicular bisectors of LM and PN are perpendicular. Hence LM and PN are perpendicular, which is all we need. [Obviously, a similar argument establishes that that LQ, MR are also altitudes of LMN.] 

Problem 3

Show that xy + yz + zx ≤ 2/7 + 9xyz/7 for non-negative reals x, y, z with sum 1.

Solution

If x ≥ 7/9, then 1 ≤ 9x/7, so xy ≤ 9xyz/7. Also (y + z) ≤ 2/9, so xy + xz < 2/9 < 2/7. Thus in this case xy + yz + zx < 2/7 + 9xyz/7. So assume x < 7/9, and hence 1 - 9x/7 > 0.

We have yz ≤ (y+z)²/4 with equality iff y = z and hence yz ≤ (1 - x)²/4. So it is sufficient to show that (1 - 9x/7)(1 - x)²/4 + x(1 - x) ≤ 2/7, or equivalently (7 - 9x)(1 - x)² + 28x(1 - x) <= 8. Expanding, 9x³ + 3x² - 5x + 1 >= 0 or (x + 1)(3x - 1)² ≥ 0, which is obviously true (for non-negative x), with equality iff x = 1/3. Thus the inequality holds, with equality iff x = y = z = 1/3. 

Problem 4

Find the smallest possible sum of digits for a number of the form 3n² + n + 1 (where n is a positive integer). Does there exist a number of this form with sum of digits 1999?

Solution

Answer: n = 8 gives 201 with sum of digits 3. Yes, eg take n = 10²²² - 1.

The only one digit number has sum of digits 5. 3n² + n + 1 = n(3n+1) + 1 and n and 3n+1 have opposite parity, so 3n² + n + 1 must be odd. In particular, the last digit cannot be 0, so for n > 1 the number has at least two non-zero digits (the first and the last) and hence the sum of digits is at least 2. It can only be 2 if the number is 10^a + 1 and hence n(3n+1) = 10^a. But n and 3n+1 are relatively prime, so we must have n = 2^a, 3n+1 = 5^a. But (5/2)^a > 6 for a > 1, so there are no solutions with a > 1. If a = 1, then n = 2, so 3n+1 = 7 not 5, so a = 1 is not a solution either. Thus the sum of digits cannot be 2.

n = 8 gives 201 with sum of digits 3, so that is the best possible.

We claim that if n = 10^m - 1, then 3n² + n + 1 = 29...950...03, where there are m-1 9s and m-1 0s. Thus if we take m = 222, then we get a number with 221 9s, one 2, one 3 and one 5, so the sum of digits is 1999.

To prove the assertion, note that 3n² + n + 1 = 3·10^2m - 6·10^m + 3 + 10^m = (3·10^m-1 - 1) 10^m+1 + 5·10^m + 3. Now 3·10^m-1 - 1 is an m-digit number 29...9. Multiplying by 10^m+1 means it is followed by m+1 zero digits. But 5·10^m + 3 is an m+1 digit number 50...03, so the sum is as claimed.

[more...]

34th British Mathematical Olympiad 1998 Problems

34th British Mathematical Olympiad 1998 Problems

1.  A station issues 3800 tickets covering 200 destinations. Show that there are at least 6 destinations for which the number of tickets sold is the same. Show that this is not necessarily true for 7.

2.  The triangle ABC has ∠A > ∠C. P lies inside the triangle so that ∠PAC = ∠C. Q is taken outside the triangle so that BQ parallel to AC and PQ is parallel to AB. R is taken on AC (on the same side of the line AP as C) so that ∠PRQ = ∠C. Show that the circles ABC and PQR touch.

3.  a, b, c are positive integers satisfying 1/a - 1/b = 1/c and d is their greatest common divisor. Prove that abcd and d(b - a) are squares.

4.  Show that:     xy + yz + zx = 12

      xyz - x - y - z = 2 have a unique solution in the positive reals. Show that there is a solution with x, y, z distinct reals.

Solutions

Problem 1

A station issues 3800 tickets covering 200 destinations. Show that there are at least 6 destinations for which the number of tickets sold is the same. Show that this is not necessarily true for 7.

Solution

There is some ambiguity as to whether the station can issue 0 tickets for a particular destination. Suppose 5 destinations had 0 tickets, then would it be true that the station issued "3800 tickets covering 200 destinations"? It would be more natural to say 3800 tickets covering 195 destinations. However, the point is not important, because the result is true either way.

If we allow zero, then the smallest possible number of tickets that could be sold if no more than 5 destinations had the same number of tickets would be 5(1 + 2 + ... + 39) = 5·39·40/2 = 3900. The number of tickets would obviously be higher if we did not allow zero. In any case, only 3800 tickets were sold, so at least 6 destinations have the same number of tickets.

However, 6(1 + 2 + ... 33) + 34 + 400 = 6·33·34/2 + 434 = 3800 and 6·33 + 2 = 200, so there could be 6 destinations with just 1 ticket, 6 with just 2 tickets and so on, up to 6 with just 33 tickets, then 1 destination with 34 tickets and 1 with 400 tickets. In this case there is no group of 7 or more destinations with the same number of tickets. 

Problem 2

The triangle ABC has ∠A > ∠C. P lies inside the triangle so that ∠PAC = ∠C. Q is taken outside the triangle so that BQ parallel to AC and PQ is parallel to AB. R is taken on AC (on the same side of the line AP as C) so that ∠PRQ = ∠C. Show that the circles ABC and PQR touch.

Solution

Let the lines BQ and AP meet at X. We show that the circles touch at X.

By construction ∠PAC = ∠C. BQ is parallel to AC, so ∠BXA = ∠C. Also by construction ∠PRQ = ∠C. So ∠PRQ = ∠PXQ and hence X lies on the circle PQR. But since ∠BXA (another name for ∠PXQ) = ∠C, X also lies on the circle ABC.

Finally, since PQ is parallel to AB, ∠BAX = ∠QPX, so the angles made by the tangents at X to the circles ABC and PQR with the chord BQX are the same. Hence the tangents coincide and the circles touch at X. 

Problem 3

a, b, c are positive integers satisfying 1/a - 1/b = 1/c and d is their greatest common divisor. Prove that abcd and d(b - a) are squares.

Solution

Let A = a/d, B = b/d, C = c/d, so that A, B, C have greatest common divisor 1. We have 1/A - 1/B = 1/C, so AB = C(B - A). We show that (B - A) must be a square.

If not, then there is a prime p such that the highest power of p dividing (B - A) is p^2r+1 for some r. Now if p^r+1 divides A, then it also divides B = (B - A) + A. Hence p^2r+2 divides AB. But p cannot divide C (since A, B, C have no common factor), so p^2r+2 divides (B - A). Contradiction. So at most p^r divides A, and similarly B. Hence at most p^2r divides AB and hence (B - A). Contradiction. That establishes that (B - A) is a square. But ABC(B - A) = ABAB, so ABC(B - A) is a square, and hence also ABC(B - A)/(B - A) = ABC.

Hence (b - a)d = d²(B - A) and abcd = d⁴ABC are squares. 

Problem 4

Show that:     xy + yz + zx = 12
      xyz - x - y - z = 2

have a unique solution in the positive reals. Show that there is a solution with x, y, z distinct reals.

Solution

Obviously 2, 2, 2 is a solution (in the positive reals). If we regard z as known, then we have x + y = (11z - 2)/(z² + 1), xy = (z² + 2z + 12)/(z² + 1). So necessary and sufficient conditions for x, y, z to be positive reals are: (11z - 2)² > 4(z² + 2z + 12)(z² + 1) (*) (which ensures that x and y are real) and z > 2/11 (which then ensures that they and z are positive).

(*) becomes 4z⁴ + 8z³ - 69z² + 52z + 44 ≤ 0, or (z - 2)²(2z + 11)(2z + 1) ≤ 0. This is satisfied for -11/2 ≤ z ≤ -1/2 and z = 2. So the only positive solution is z = 2 (and hence x = 2, y = 2 also, since the problem is symmetrical between x, y and z).

For other real solutions we should look at values in the range -11/2 to -1/2. z = -1 does not help (we get the non-distinct -1, -1, -11/2). z = -2 gives x = - (12 + 2√21)/5, y = - (12 - 2√21)/5, which are real and distinct.

A better solution to the first part was provided by Arne Smeets

So assume x, y, z are postive and put w = (xyz)^1/3. Using AM/GM on xy + yz + zx = 12, we get 12 ≥ 3 w², so w ≤ 2. Using AM/GM on the other equation we get w³ ≥ 2 + 3w, or (w - 2)(w + 1)² >= 0, so w ≥ 2. Hence w = 2. But we only get equality in AM/GM if the terms are equal, so x = y = z = 2.

Read more:

[more...]

33rd British Mathematical Olympiad 1997 Problems

33rd British Mathematical Olympiad 1997 Problems

1.  M and N are 9-digit numbers. If any digit of M is replaced by the corresponding digit of N (eg the 10s digit of M replaced by the 10s digit of N), then the resulting integer is a multiple of 7. Show that if any digit of N is replaced by the corresponding digit of M, then the resulting integer must be a multiple of 7. Find d > 9, such that the result remains true when M and N are d-digit numbers.

2.  ABC is an acute-angled triangle. The median BM and the altitude CF have equal length, and ∠MBC = ∠FCA. Show that ABC must be equilateral.

3.  Find the number of polynomials of degree 5 with distinct coefficients from the set {1, 2, ... , 9} which are divisible by x² - x + 1.

4.  Let S be the set {1/1, 1/2, 1/3, 1/4, ... }. The subset {1/20, 1/8, 1/5} is an arithmetic progression of length 3 and is maximal, because it cannot be extended (within S) to a longer arithmetic progression. Find a maximal arithmetic progression in S of length 1996. Is there a maximal arithmetic progression in S of length 1997?

Problem 1

M and N are 9-digit numbers. If any digit of M is replaced by the corresponding digit of N (eg the 10s digit of M replaced by the 10s digit of N), then the resulting integer is a multiple of 7. Show that if any digit of N is replaced by the corresponding digit of M, then the resulting integer must be a multiple of 7. Find d > 9, such that the result remains true when M and N are d-digit numbers.

Solution

Let M = m₈10⁸ + m₇10⁷ + ... + m₀ and N = n₈10⁸ + ... + n₀. We have:
n₈10⁸ + m₇10⁷ + m₆10⁶ + ... + m₁10 + m₀ = 0 mod 7
m₈10⁸ + n₇10⁷ + m₆10⁶ + ... + m₁10 + m₀ = 0 mod 7
m₈10⁸ + m₇10⁷ + n₆10⁶ + ... + m₁10 + m₀ = 0 mod 7
...
m₈10⁸ + m₇10⁷ + m₆10⁶ + ... + n₁10 + m₀ = 0 mod 7
m₈10⁸ + m₇10⁷ + m₆10⁶ + ... + m₁10 + n₀ = 0 mod 7

Adding all but the first equation we get:
8m₈10⁸ + (n₇ + 7m₇) 10⁷ + (n₆ + 7m₆) 10⁶ + ... + (n₀ + 7m₀) = 0 mod 7. Hence
m₈10⁸ + n₇10⁷ + n₆10⁶ + ... + n₀ = 0 mod 7, which shows that substituting the first digit from M into N gives a number divisible by 7.

Similarly, adding all but the second equation, we find that substituting the second digit from M into N gives a number divisible by 7, and so on.

Obviously the same argument works for any d = 2 mod 7. 

Problem 2

ABC is an acute-angled triangle. The median BM and the altitude CF have equal length, and ∠MBC = ∠FCA. Show that ABC must be equilateral.

Solution

Solution by Paul Smith

Put ∠MBC = ∠FCA = x. Since M is the midpoint of AC and ∠AFC = 90^o, M must be the center of the circle through A, F, C, so MF = MC = MA. Put MF = k. Then CF = 2k cos x.

But ∠MBC = ∠FCA = ∠FCM = ∠MFC, so MFBC is cyclic. Hence ∠BMC = ∠CFB = 90^o. So BM/k = cot MBC = cot x. But CF = BM, so sin x = 1/2. Hence x = 30^o. Hence ∠C = 60^o. Also ∠A = 90^o - angle FCA = 60^o. So the triangle is equilateral.

I originally had this appalling slog:

Let the side lengths be BC = a, CA = b, AB = C and let CF = BM = m. Let ∠MBC = ∠FCA = x. By the cosine formula we have: c² = m² + b²/4 - mb cos BMA, a² = m² + b²/4 + mb cos BMA. Adding, m² = a²/2 + c²/2 - b²/4 (1).

From triangle FCA, m = b cos x. By the cosine formula to MBC, b²/4 = m² + a² - 2am cos x. Hence b²/4 = m² + a² - 2am²b = (b - 2a)m²/b + a². Hence b = 2a or m² = b(b + 2a)/4.

Suppose b = 2a. If m <= a, then B lies inside or on the circle center M radius MA and hence ∠ABC ≥ 90^o. But we are told the triangle is acute-angled, so ∠ABC < 90^o. Hence m > a. But CF ≤ CB = a. Contradiction. So we cannot have b = 2a.

Hence m²= b(b + 2a)/4, so from (1), 2a² + 2c² - b² = b² + 2ab or b² = a² + c² - ab.

Let k be the area of ABC. By Heron's formula we have that 16k² = (a + b + c)(a + b - c)(a - b + c)(-a + b + c) = - a⁴ - b⁴ - c⁴ + 2a²b² + 2b²c² + 2c²a². But 16k² is also 4m²c² = c²b(b + 2a). So we have -a⁴ - b⁴ + 2a²b² + c²(2a² - 2ab + b²) - c⁴ = 0. Substituting for c² ( = b² - a² + ab) we get: 0 = -4a⁴ - b⁴ + 2a²b² - 3b³a + 6a³b = (a - b)(2a + b)(2a² - 2ab - b²).

Clearly 2a + b is non-zero. If 2a² - 2ab - b² = 0, then 3a² = (a + b)², so b = (√3 - 1)a. Then substituting in the previous relation for c, we get c = b/√2. So we have for some k, a = (1 + √3)k, b = 2k, c = (√2)k. But then a² > b² + c², so the triangle is not acute-angled. So we must have a = b. Then using the previous relation for c, we get c = a also. 

Problem 3

Find the number of polynomials of degree 5 with distinct coefficients from the set {1, 2, ... , 9} which are divisible by x² - x + 1.

Solution

Answer: 624.

This seems to be a laborious exercise in counting. Suppose that the polynomial is (x² - x + 1)(ax³ + bx² + cx + d). Multiplying out, we find that the coefficients are: a, b-a, c-(b-a), b-(c-d), c-d, d. Put e = b-a, f = c-d. Then the coefficients are: a, e, d+f-e, a+e-f, f, d. Put k = e-f. Then the coefficients are: a, f+k, d-k, a+k, f, d. Suppose k > 0. Put g = d-k. then the coefficients are (rearranging the order) a, f, g, a+k, f+k, g+k. Similarly, if k < 0, put h = -k, and the coefficients are a, e, d+h, a-h, e+h, d. Putting g = a-h and rearranging the order we get: d, e, g, d+h, e+h, g+h. The two types (k positive and negative) obviously do not overlap and there are evidently equal numbers of each. So we have to find the number of sets a, f, g, a+k, f+k, g+k. By symmetry, the number of sets must be 6 times the number with a < f < g. However, I cannot see an elegant way to count the number with a < f < g. Simply listing them gives 52 possibilities.

if k = 1, a = 1, f = 3, then g can be 5, 6, 7, or 8.  

if k = 1, a = 1, f = 4, then g can be 6, 7 or 8

if k = 1, a = 1, f = 5, then g can be 7 or 8

if k = 1, a = 1, f = 6, then g must be 8

if k = 1, a = 2, f = 4, then g can be 6, 7 or 8

if k = 1, a = 2, f = 5, then g can be 7 or 8

if k = 1, a = 2, f = 6, then g must be 8

if k = 1, a = 3, f = 5, then g can be 7 or 8

if k = 1, a = 3, f = 6, then g must be 8

if k = 2, a = 1, f = 2, then g can be 5, 6 or 7

if k = 2, a = 1, f = 4, then g can be 5 or 7

if k = 2, a = 1, f = 5, then g must be 6

if k = 2, a = 1, f = 6, then g must be 7

if k = 2, a = 2, f = 3, then g can be 6 or 7

if k = 2, a = 2, f = 5, then g must be 6

if k = 2, a = 2, f = 6, then g must be 7

if k = 2, a = 3, f = 4, then g must be 7

if k = 2, a = 3, f = 6, then g must be 7

if k = 3, a = 1, f = 2, then g can be 3 or 6

if k = 3, a = 1, f = 3, then g must be 5

if k = 3, a = 1, f = 5, then g must be 6

if k = 3, a = 2, f = 3, then g must be 4

if k = 3, a = 2, f = 4, then g must be 6

if k = 3, a = 3, f = 4, then g must be 5

if k = 3, a = 4, f = 5, then g must be 6

if k = 4, a = 1, f = 2, then g can be 3 or 4

if k = 4, a = 1, f = 3, then g must be 4

if k = 4, a = 2, f = 3, then g can be 4 or 5

if k = 4, a = 2, f = 4, then g must be 5

if k = 5, a = 1, f = 2, then g must be 3 or 4

if k = 5, a = 1, f = 3, then g must be 4

if k = 5, a = 2, f = 3, then g must be 4

if k = 6, a = 1, f = 2, then g must be 3

Comment: can anyone come up with a better solution!

Problem 4

Let S be the set {1/1, 1/2, 1/3, 1/4, ... }. The subset {1/20, 1/8, 1/5} is an arithmetic progression of length 3 and is maximal, because it cannot be extended (within S) to a longer arithmetic progression. Find a maximal arithmetic progression in S of length 1996. Is there a maximal arithmetic progression in S of length 1997?

Solution

Let k = 1/1993! . Then h divides k for h = 1, 2, ... , 1996, but not for 1997, which is prime. Hence 1/k, 2/k, 3/k, ... , 1996/k is a maximal arithmetic progression in S of length 1996 (extending it would require 0 or 1997/1993! to be in S, which they are not).

6.1998 - 1 = 11987 is prime. So put k = 11986! and consider the progression 5/k, 11/k, 17/k, ... , 11981/k. It has 1997 terms in S. It cannot be extended, because -1/k and 11987/k are not in S.

[This conceals some work, because we have to try 2·1998 - 1 (factor 5), 3·1998 - 1 (factor 13), 3·1998 - 2 (factor 2), 4·1998 - 1 (factor 61), 4·1998 - 2 (factor 2), 4·1998 - 3 (factor 3), 5·1998 - 1 (factor 7), 5·1998 - 2 (factor 2), 5·1998 - 3 (factor 3), 5·1998 - 4 (factor 2), before hitting on 6·1998 - 1 (and checking that requires checking divisibility by about 25 primes).]

[more...]

32nd British Mathematical Olympiad 1996 Problems

32nd British Mathematical Olympiad 1996 Problems

1.  Find all non-negative integer solutions to 2^m + 3ⁿ = k².

2.  The triangle ABC has sides a, b, c, and the triangle UVW has sides u, v, w such that a² = u(v + w - u), b² = v(w + u - v), c² = w(u + v - w). Show that ABC must be acute angled and express the angles U, V, W in terms of the angles A, B, C.

3.  The circles C and C' lie inside the circle S. C and C' touch each other externally at K and touch S at A and A' respectively. The common tangent to C and C' at K meets S at P. The line PA meets C again at B, and the line PA' meets C' again at B'. Show that BB' is a common tangent to C and C'.

4.  Find all positive real solutions to w + x + y + z = 12, wxyz = wx + wy + wz + xy + xz + yz + 27. 

Solutions

Problem 1

Find all non-negative integer solutions to 2^m + 3ⁿ = k².

Solution

Answer: 2⁰ + 3¹ = 2², 2³ + 3⁰ = 3² , 2⁴ + 3² = 5².

If m = 0, then 3ⁿ = k² - 1 = (k + 1)(k - 1). But if 3 divides both k + 1 and k - 1, then it divides their difference 2, which is impossible, so k - 1 = 1 and we have the solution m = 0, n = 1, k = 2.

If m = 1, then k² - 2 = 3ⁿ. But squares are 0 or 1 mod 3, so k² - 2 is 1 or 2 mod 3, so n must be 0. But that does not give a solution. So we may assume m > 1. Hence k² = 3ⁿ = (4 - 1)ⁿ = (-1)ⁿ mod 4. But squares are 0 or 1 mod 4, so n must be even. Put n = 2s. Then 2^m = k² - 3^2s = (k + 3^s)(k - 3^s). So both k + 3^s and k - 3^s are powers of 2. Suppose k - 3^s = 2^a and k + 3^s = 2^b, so that m = a + b. Then 2.3^s = 2^b - 2^a. So a = 1 and 3^s = 2^b-1 - 1. But 2^b-1 - 1 = (-1)^b-1 - 1 mod 3, so b - 1 must be even or s = 0.

If s = 0, then b - 1 = 1, so m = 3 and we have the solution 2³ + 3⁰ = 3².

So suppose b -1 is even. Put b - 1 = 2r, then 3^s = (2^r - 1)(2^r + 1). But 3 cannot divide both 2^r - 1 and 2^r + 1 or it divides their difference, which is 2. So we must have 2^r - 1 = 1 and hence r = s = 1, b = 2r+1 = 3, n = 2s = 2, m = a + b = 4 and we have the solution 2⁴ + 3² = 5².   

Problem 2

The triangle ABC has sides a, b, c, and the triangle UVW has sides u, v, w such that a² = u(v + w - u), b² = v(w + u - v), c² = w(u + v - w). Show that ABC must be acute angled and express the angles U, V, W in terms of the angles A, B, C.

Solution

Thanks to Arne Smeets

a² + b² - c² = u(v + w - u) + v(w + u - v) - w(u + v - w) = w² - (u - v)² = 2uv(1 - cos W) > 0. Similarly, b² + c² - a² > 0, and c² + a² - b² > 0. So ABC is acute-angled.

We have ab = √(uv(w² - u² - v² + 2uv) ) = uv √( 2(1 - cos W) ), so cos C = (a² + b² - c²)/2ab = √ ((1 - cos W)/2 ) = sin W/2 = cos(90^o - W/2). Thus W = 180^o - 2C. Similarly for the other angles. 

Problem 3

Thanks to Arne Smeets

The circles C and C' lie inside the circle S. C and C' touch each other externally at K and touch S at A and A' respectively. The common tangent to C and C' at K meets S at P. The line PA meets C again at B, and the line PA' meets C' again at B'. Show that BB' is a common tangent to C and C'.

Solution

 

Let the centers of C, C' be O, O'. We have PA·PB = PK2 = PA'·PB', so triangles PAA' and PB'B are similar. Hence ∠PA'A = ∠PBB'. Let W be the center of S. A homothecy center A takes O to W, C to S and B to P, so ∠BOA = ∠PWA. Hence ∠PBB' = ∠PA'A = ½ ∠PWA = ½ ∠BOA = ∠BOM, where M is the midpoint of AB.

∠OMB = 90^o, so ∠OBB' = 180^o - ∠PBB' - ∠MBO = 90^o. Hence BB' is tangent to C. Similarly, it is tangent to C'. 

Problem 4

Find all positive real solutions to w + x + y + z = 12, wxyz = wx + wy + wz + xy + xz + yz + 27.

Answer

w = x = y = z = 3 is the only solution.

Solution

Put p = √(wxyz). By AM/GM applied to wx, wy, wz, xy, xz, yz we have p ≤ (wx + wy + wz + xy + xz + yz)/6 = p²/6 - 27/6, so (p - 3)² ≥ 36. Hence |p - 3| ≥ 6. But p is positive, so p ≥ 9. Hence wxyz ≥ 81. But applying AM/GM to w, x, y, z we have √p ≤ 3, with equality iff w = x = y = z. So wxyz ≤ 81 with equality iff w = x = y = z.

Read more:

[more...]

31st British Mathematical Olympiad 1995 Problems

31st British Mathematical Olympiad 1995 Problems

1.  Find all positive integers a ≥ b ≥ c such that (1 + 1/a)(1 + 1/b)(1 + 1/c) = 2.

2.  ABC is a triangle. D, E, F are the midpoints of BC, CA, AB. Show that ∠DAC = ∠ABE iff ∠AFC = ∠ADB.

3.  x, y, z are real numbers such that x < y < z, x + y + z = 6 and xy + yz + zx = 9. Show that 0 < x < 1 < y < 3 < z < 4.

4.  (1) How many ways can 2n people be grouped into n teams of 2?

(2) Show that (mn)! (mn)! is divisible by m!ⁿ⁺¹ n!^m+1 for all positive integers m, n.

Solutions

Problem

Find all positive integers a ≥ b ≥ c such that (1 + 1/a)(1 + 1/b)(1 + 1/c) = 2.

Solution

Answer: (a, b, c) = (5, 4, 3), (8, 3, 3), (7, 6, 2), (9, 5, 2), (15, 4, 2).

We have 1 + 1/a ≤ 1 + 1/b ≤ 1 + 1/c. So 2 ≤ (1 + 1/c)³. But (1 + 1/c)³ is a decreasing function of c and c = 4 gives 125/64 < 2. So the only possible values of c are 1, 2, 3. If c = 1, then (1 + 1/a)(1 + 1/b) = 1, which is obviously impossible. So c = 2 or 3.

We may write the expression as (c + 1)(a + b + 1) = (c - 1)ab. Suppose c = 2. Then (b - 3)a = 3b + 3. If b ≥ 7, then (b - 3)a ≥ 4a ≥ 4b ≥ 3b + 7 > 3b + 3. Contradiction. (b - 3)a = 3b + 3, so b - 3 must be positive. Thus we need only consider b = 4, 5 and 6. These give the three solutions with c = 2 shown above.

Suppose c = 3. Then 2ab = 4(a + b + 1), so ab = 2a + 2b + 2. So (b - 2)a = 2b + 2. If b ≥ 5, then (b - 2)a ≥ 3a ≥ 3b ≥ 2b + 5 > 2b + 2. Contradiction. But b - 2 must be positive, so we need only consider b = 3 and 4. That gives the two solutions shown above for c = 3. 

Problem 2

ABC is a triangle. D, E, F are the midpoints of BC, CA, AB. Show that ∠DAC = ∠ABE iff ∠AFC = ∠ADB.

Solution

The medians meet at the centroid G. DF is parallel to AC, so ∠FDG = ∠DAC (alternate angles) = ∠ABE (given) = ∠FBG (same angle). So FGDB is cyclic. So ∠ADB = ∠GDB (same angle) = 180^o - ∠GFB = ∠AFC. 

Problem 3

x, y, z are real numbers such that x < y < z, x + y + z = 6 and xy + yz + zx = 9. Show that 0 < x < 1 < y < 3 < z < 4.

Solution

(x + y) = 6 - z, so 9 = xy + yz + zx = xy + z(6 - z). Hence (z - 3)² = xy. Similarly, (x - 3)² = yz and (y - 3)² = zx. If any of x, y, z are zero, then two of (z - 3)², (y - 3)² and (x - 3)³ are zero, so two of x, y, z are equal, whereas we are told they are all unequal. Hence none of x, y, z are zero.

We also have that xy, yz and zx are all non-negative. So we cannot have x < 0 and y and z > 0 (for then xy < 0). Equally, we cannot have y < 0 and z > 0 (for then yz < 0). Finally, we cannot have x, y, z all negative, for then x + y + z would be negative. So x, y, z are all positive.

We have x + y = 6 - z. Also xy < (x + y)²/4 (strict inequality since x and y are unequal). So (6 - z)²/4 + (6 - z)z > 9 or 4z - z² > 0. Hence z < 4. If z ≤ 2, then since x < y < z, we have x + y + z < 6. Contradiction. hence z > 2. So |z - 3| < 1. But xy = (z - 3)², so xy < 1. So x < 1.

But (x - 3)² = yz, so yz > 4. But z < 4, so y > 1. If y ≥ 3, then x + y + z > y + z > 2y > 6. Contradiction. So y < 3.

Finally, (x - 3)(y - 3)(z - 3) = xyz - 3(xy + yz + zx) + 9(x + y + z) - 27 = xyz > 0. But (x - 3)(y - 3) > 0, so z > 3. 

Problem 4

(1) How many ways can 2n people be grouped into n teams of 2?
(2) Show that (mn)! (mn)! is divisible by m!ⁿ⁺¹ n!^m+1 for all positive integers m, n.

Solution

(1) Let the number of ways be t(n). Then t(1) = 1 and t(n) = (2n-1) t(n-1). So t(n) = 1.3.5 ... (2n-1). We can also write this as (2n)! /(2.4.6 ... 2n) = (2n)! / (2ⁿn!).

(2) The first part is evidently intended as a hint. Consider the number of ways of dividing mn people into m teams of n people. It is the number of ways of arranging mn people into a line divided by the number of ways of ordering the m teams times the number of ways or ordering each team = (mn)! / ( n! m!ⁿ ). So this must be integral. Similarly, (mn)! / ( m! n!^m ) is integral and hence their product.

[more...]

30th British Mathematical Olympiad 1994 Problems

30th British Mathematical Olympiad 1994 Problems

1.  Find the smallest integer n > 1 such that (1² + 2² + 3² + ... + n²)/n is a square.

2.  How many incongruent triangles have integer sides and perimeter 1994?

3.  A, P, Q, R, S are distinct points on a circle such that ∠PAQ = ∠QAR = ∠RAS. Show that AR(AP + AR) = AQ(AQ + AS).

4.  How many perfect squares are there mod 2ⁿ?

Solutions

Problem 1

Find the smallest integer n > 1 such that (1² + 2² + 3² + ... + n²)/n is a square.

Solution

We want (n+1)(2n+1)/6 = m². But n+1 and 2n+1 are coprime. Also 2n+1 is odd, so we must have either (1) 2n+1 = a², n+1 = 6b² or (2) 2n+1 = 3a², n+1 = 2b². But 2n+1 = 2(n+1) - 1, so in case (1) we have a² + 1 = 12b². But squares are 0 or 1 mod 3, so a² + 1 is 1 or 2 mod 3, whereas 12b² is 0 mod 3. So case (1) is not possible.

In case (2) we have 4b² - 1 = 3a², so either 2b + 1 = c², 2b - 1 = 3d² or 2b + 1 = 3d², 2b - 1 = c², so c² = 3d² ± 2. We now try successively, d = 1, 2, ... . d = 1 gives c = 1, b = 1, n = 1. But we are given n > 1. d = 2 fails, d = 3 gives a = 15, b = 13, n = 337.

Checking: (337 + 1)(2.337 + 1)/6 = 169.225 = (13.15)². 

Problem 2

How many incongruent triangles have integer sides and perimeter 1994?

Solution

Answer: 82834.

We assume a triangle is not allowed to be degenerate with zero area. Let t_n be the number of incongruent triangles with perimeter n and integer sides. Calculating the first few terms, we find t₁ = t₂ = 0, t₃ = 1 (111), t₄ = 0, t₅ = 1 (122), t₆ = 1 (222), t₇ = 2 (133, 223), t₈ = 1 (233), t₉ = 3 (144, 234, 333).

Suppose the triangle has sides a, b, c with a ≤ b ≤ c. The only restrictions are that a > 0 and a + b > c. Now consider a-1, b-1, c-1. This will be a triangle with perimeter 3 shorter unless a = 1 or a + b = c + 1. But if a = 1, then we must have b = c and hence a + b = c + 1. So a-1, b-1, c-1 is either a triangle or a degenerate triangle. Conversely, if a-1, b-1, c-1 is a triangle or a degenerate triangle, then a, b, c is a triangle. So if we put d_n as the number of degenerate triangles with perimeter n (including those with shortest side zero), then t_n+3 = t_n + d_n.

Obviously d_odd = 0. d_2n = the number of pairs a ≤ b with a + b = n, which is just [n/2] + 1 (for example 4 = 0 + 4 = 1 + 3 = 2 + 2). So we have t₁₉₉₄ = t₁₉₉₁ = t₁₉₈₈ + 498 = t₁₉₈₅ + 498 = t₁₉₈₂ + 496 + 498 = t₁₉₇₉ + 496 + 498 = t₁₉₇₆ + 495 + 496 + 498 = ... = 1 + 3 + 4 + 6 + 7 + ... + 496 + 498. There are 498 x 2/3 terms, which can be grouped into pairs with sum 499 (1 and 498, 3 and 496 etc), so the sum is 166 x 499.

Alternative solution

Assume a ≤ b ≤ c. We must have c < 1994/2, so the largest possible value of c is 996. Also c ≥ 1994/3, so c ≥ 665. If c = 665, then the only solution is a = 664, b = 665. If c = 666, then the solutions are a = 662, b = 666, or a = 663, b = 665, or a = b = 664. Evidently if c is odd, then the number of pairs (a, b) is one greater than for c - 1 (if the smallest and largest possible a for c-1 are h and k, then the largest and smallest for c are h-2 and k-1), but if c is even then the number of pairs is two greater than for c-1 (the largest and smallest are h-2 and k). Hence the total number of possibilities is 1 + 3 + 4 + 6 + 7 + ... + 498 (for c = 996 the possibilities are a = 2 up to a = 499). 

Problem 3

A, P, Q, R, S are distinct points on a circle such that ∠PAQ = ∠QAR = ∠RAS. Show that AR(AP + AR) = AQ(AQ + AS).

Solution

Take X on the ray AQ so that QX = AS, and take Y on the ray AR so that RY = AP. Then we have to show that AQ·AX = AR·AY, so it is sufficient to show that QRYX is cyclic.

We have QR = SR (because they subtend equal angles at A), QX = SA (by construction) and ∠RQX = 180^o - ∠AQR = ∠RSA. So triangles QRX and SRA are congruent. So ∠YRX = ∠RXA + ∠RAX. But ∠RXA = ∠RXQ (same angle) = ∠RAS (congruent triangles). So ∠YRX = ∠RAX + ∠RAS = ∠RAX + ∠QAP (given as equal) = ∠PAR. But RX = AR (QRX and SRA congruent) and RY = AP (by construction). So RYX and APR are congruent. So ∠RYX = ∠APR = ∠AQR = 180^o - ∠RQX. So QRYX is cyclic. 

Problem 4

How many perfect squares are there mod 2ⁿ?

Solution

Answer: n odd (2^n-1 + 5)/3, n even (2^n-1 + 4)/3.

We find the first few:

2: 0, 1

4: 0, 1

8: 0, 1, 4

16: 0, 1, 4, 9

32: 0, 1, 4, 9, 16, 17, 25

64: 0, 1, 4, 9, 16, 17, 25, 33, 36, 41, 49, 57

a² = b² mod 2ⁿ iff (2a)² = (2b)² mod 2ⁿ⁺², so the number of even squares mod 2ⁿ⁺² equals the number of squares mod 2ⁿ. This suggests looking separately at the odd and even squares. Let u_n be the number of odd squares mod 2ⁿ and v_n be the number of even squares mod 2ⁿ.

(2a + 1)² = (2b + 1)² mod 2ⁿ is equivalent to 4a² + 4a = 4b² + 4b mod 2ⁿ, which is equivalent to a² + a = b² + b mod 2^n-2 or (a - b)(a + b + 1) = 0 mod 2^n-2. But a - b and a + b + 1 have sum 2a + 1 which is odd, so they have opposite parity, so either a - b = 0 mod 2^n-2 or (a + b + 1) = 0 mod 2^n-2. Thus just 3 other odd numbers have the same square as (2a + 1), namely (2a + 2^n-1 + 1), -(2a + 1) and -(2a + 2^n-1 + 1). So there are 2^n-3 different odd squares mod 2ⁿ. In other words, v_n = 2^n-3.

Now u_n = u_n-2 + v_n-2 = u_n-4 + v_n-4 + v_n-2 etc. So the total number of squares u_2m + v_2m = v_2m + v_2m-2 + v_2m-4 + ... + v₄ + u₄ = 2^2m-3 + 2^2m-5 + ... + 2 + 2 = 2(4^m-2 + 4^m-3 + ... + 1) + 2 = 2(4^m-1 - 1)/3 + 2 = (2^n-1 + 4)/3.

Similarly, the total number of squares for n odd is (2^n-1 + 5)/4.

[more...]

29th British Mathematical Olympiad 1993 Problems

29th British Mathematical Olympiad 1993 Problems

1.  The angles in the diagram below are measured in some unknown unit, so that a, b, ... , k, l are all distinct positive integers. Find the smallest possible value of a + b + c and give the corresponding values of a, b, ... , k, l.

2.  p > 3 is prime. m = (4^p - 1)/3. Show that 2^m-1 = 1 mod m.

3.  P is a point inside the triangle ABC. x = ∠BPC - ∠A, y = ∠CPA - ∠B, z = ∠APB - ∠C. Show that PA sin A/sin x = PB sin B/sin y = PC sin C/sin z.

4.  For 0 < m < 10, let S(m, n) is the set of all positive integers with n 1s, n 2s, n 3s, ... , n ms. For a positive integer N let d(N) be the sum of the absolute differences between all pairs of adjacent digits. For example, d(122313) = 1 + 0 + 1 + 2 + 2 = 6. Find the mean value of d(N) for N in S(m, n). 

Solutions

Problem

The angles in the diagram below are measured in some unknown unit, so that a, b, ... , k, l are all distinct positive integers. Find the smallest possible value of a + b + c and give the corresponding values of a, b, ... , k, l. 

Solution

Answer: 20.

We require the angles to satisfy: a + g + h = d + e + f = c + k + l = b + i + j = g + f + i = h + e + l = d + j + k = a + b + c. (One of these equations is dependent on the others.)

So we have to find some integer k which can be partitioned in many different ways as the sum of three distinct integers. Suppose a + b + c + ... + l = n. The smallest possible value of n is 1 + 2 + 3 + ... + 12 = 78 (since the numbers are all distinct). But note that each number occurs twice in the equations above, so 8k = 2n, or n = 4k. So n must be a multiple of 4 and hence its smallest value is 80. Note also that a + b + c = k, so minimising a + b + c is equivalent to minimising n.

If n = 80, the only possibilities are {1, 2, 3, ... , 9, 10, 12, 13} or {1, 2, ... , 10, 11, 14}. At this point it is not obvious how to proceed. A good deal of trial and error produces a = 1, b = 6, c = 13, d = 8, e = 3, f = 9, g = 7, h = 12, i = 4, j = 10, k = 2, l = 5. So there is a solution for k = 20, so 20 is the required minimum. 

Problem 2

p > 3 is prime. m = (4^p - 1)/3. Show that 2^m-1 = 1 mod m.

Solution

By Fermat, So 4^p = 4 mod p, so 3m = 3 mod p. But p > 3 and prime, so m = 1 mod p. Also 4^p - 1 is odd, so m is odd and hence m - 1 is even. So we may write m - 1 = 2kp. Hence 2^m-1 = 4^pk = (3m + 1)^k. Expanding by the binomial theorem, we see that (3m + 1)^k = 1 mod m and hence 2^m-1 = 1 mod m.

 Problem 3

P is a point inside the triangle ABC. x = ∠BPC - ∠A, y = ∠CPA - ∠B, z = ∠APB - ∠C. Show that PA sin A/sin x = PB sin B/sin y = PC sin C/sin z.

Solution

Extend AP, BP, CP to meet the circumcircle again at D, E, F respectively. Consider the triangle PEC. We have ∠PEC = ∠BEC (same angle) = A (E on circumcircle). Also ∠BPC = ∠PEC + ∠ECP, so ∠ECP = x. Hence sin A/sin x = PC/PE. Similarly, sin B/sin y = PA/PF. So we have to show that PA·PC/PE = PB·PA/PF or PC/PE = PB/PF. But CF and BE are chords intersecting at P, so PC·PF = PB·PE.

The other equation follows similarly. 

Problem 4

For 0 < m < 10, let S(m, n) is the set of all positive integers with n 1s, n 2s, n 3s, ... , n ms. For a positive integer N let d(N) be the sum of the absolute differences between all pairs of adjacent digits. For example, d(122313) = 1 + 0 + 1 + 2 + 2 = 6. Find the mean value of d(N) for N in S(m, n).

Solution

Answer: n(m² - 1)/3.

Consider the number of ways of placing two different digits h and k next to each other in positions 1 and 2. The other mn - 2 digits can be permuted in (mn-2)! ways. But there are m-2 groups of n identical digits and 2 groups of n-1 identical digits, so the total number of ways is (mn-2)! / (n!^m-2 (n-1)!²). This is independent of the identity of h and k. There are 2(m-1) pairs h, k with difference 1, 2(m-2) pairs with difference 2, and so on, up to 2 pairs with difference m-1. Thus the total absolute difference between the first two digits (totalled over all members of S(m, n) ) is 2( (m-1)1 + (m-2)2 + ... + 1(m-1) )(mn-2)! /( n!^m-2 (n-1)!²) = f(m, n).

Exactly the same argument applies to the total absolute difference for positions 2 and 3, 3 and 4 and so on up to mn-1 and mn. Thus the total of d(N) over all members of S(m, n) is f(m, n) (mn-1). There are (mn)! / n!^m members of S(m, n), so the mean is f(m, n) (mn-1) n!^m/ (mn)! .

We have (m-1)1 + (m-2)2 + ... + 1(m-1) = (m + 2m + 3m + ... + m.m) - (1² + 2² + ... + m²) = m²(m+1)/2 - m(m+1)(2m+1)/6 = m(m+1)(3m - 2m - 1)/6 = m(m² - 1)/6. Hence the mean is 1/3 m(m² - 1) n!²/( (n-1)!² mn) = n(m² - 1)/3.

It is worth checking this for a few small values. Obviously the mean for S(1, n) = {11...1} is zero, which checks. We have S(2, 1) = {12, 21}, mean 1, which checks. We have S(2, 2) = {1122, 1212, 1221, 2112, 2121, 2211} mean 2, which checks.

As a further check, we found 2(m-1 + m-2 + ... + 1) (mn-2)! / (n!^m-2 (n-1)!²) = m(m-1) (mn-2)! /( n!^m-2 (n-1)!² ) numbers with different digits in positions 1 and 2. There are also m.(mn-2)!/( n!^m-1 (n-2)! ) numbers with the same first digit in positions 1 and 2. So in total we have (mn-2)!/n!^m (m(m-1) n² + m n(n-1) ) = (mn-2)!/n!^m mn ((m-1) n + n-1 ) = (mn)!/n!^m as required.

[more...]

28th British Mathematical Olympiad 1992 Problems

28th British Mathematical Olympiad 1992 Problems

1.  p is an odd prime. Show that there are unique positive integers m, n such that m² = n(n + p). Find m and n in terms of p.

2.  Show that 12/(w + x + y + z) ≤ 1/(w + x) + 1/(w + y) + 1/(w + z) + 1/(x + y) + 1/(x + z) + 1/(y + z) ≤ 3(1/w + 1/x + 1/y + 1/z)/4 for any positive reals w, x, y, z.

3.  The circumradius R of a triangle with sides a, b, c satisfies a² + b² = c² - R². Find the angles of the triangle.

4.  Each edge of a connected graph with n points is colored red, blue or green. Each point has exactly three edges, one red, one blue and one green. Show that n must be even and that such a colored graph is possible for any even n > 2. X is a subset of 1 < k < n points. In order to isolate X from the other points (so that there is no edge between a point in X and a point not in X) it is necessary and sufficient to delete R red edges, B blue edges and G green edges. Show that R, B, G are all even or all odd. 

Solutions

Problem 1

p is an odd prime. Show that there are unique positive integers m, n such that m² = n(n + p). Find m and n in terms of p.

Solution

We have (k² + k)² = k²(k² + 2k + 1). So if p = 2k + 1, then m = k² + k, n = k² is always a solution (whether or not p is prime).

4m² = 4n² + 4np, so 4m² + p² = (2n+p)². Hence p² = (2n+p+m)(2n+p-m). But p is prime, so the only way of expressing p² as a product of two unequal numbers is p² x 1. Hence 2n+p-m = 1, 2n+p+m = p². Solving for m and n, we get n = (p² - 2p + 1)/4 = (p-1)²/4, m = (p² - 1)/2. 

Problem 2

Show that 12/(w + x + y + z) ≤ 1/(w + x) + 1/(w + y) + 1/(w + z) + 1/(x + y) + 1/(x + z) + 1/(y + z) ≤ 3(1/w + 1/x + 1/y + 1/z)/4 for any positive reals w, x, y, z.

Solution

The left-hand inequality is just the harmonic mean inequality applied to w+x, w+y etc. We have 1/(w + x) + ... ≥ 6²/(w + x + w + y + ... ) = 36/( 3(w + x + y + z) ).

The harmonic mean inequality applied to w and x gives 1/w + 1/x ≥ 4/(w + x). So applying it to the other pairs also and adding we get 3(1/w + 1/x + 1/y + 1/z) ≥ 4(1/(w + x) + ... ), which is the right-hand inequality. 

Problem 3

The circumradius R of a triangle with sides a, b, c satisfies a² + b² = c² - R². Find the angles of the triangle.

Solution

Answer: A = B = 30^o and C = 120^o.

We have a = 2R sin A etc (if O is the circumcenter, then ∠BOC = 2A). So we have that sin²A + sin²B = sin²C - 1/4. We try to simplify this. Put C = 180^o - A - B, then sin C = sin(A + B) = sin A cos B + cos A sin B. Hence we get sin²A + sin²B = sin²A cos²B + cos²A sin²B + 2 sin A cos A sin B cos B - 1/4. Hence 2 sin²A sin²B = 2 sin A cos A sin B cos B - 1/4, or sin A sin B (sin A sin B - cos A cos B) = -1/8 or sin A sin B cos C = -1/8.

It is not clear why this should determine A, B, C. We suspect that maybe sin A sin B cos C >= -1/8 with equality only at the angles we want (that is a common ruse). sin A and sin B must be positive, so cos C must be negative. For fixed A + B, we maximise sin A sin B by taking A = B (for 2 sin A sin B = cos(A - B) - cos(A + B) ). So sin A sin B cos C >= sin²A cos(180^o - 2A) = - sin²A cos 2A = - sin²A (1 - 2 sin²A). To minimise this we must maximise k(1 - 2k), where k = sin²A. Maximising k(1 - 2k) is equivalent to maximising 2k(1 - 2k) which is achieved by taking 2k = 1 - 2k, so we want k = 1/4 and hence sin A = 1/2, so A = B = 30^o and C = 120^o. The value then of sin A sin B cos C is indeed -1/8, so as predicted we have sin A sin B cos C >= -1/8 with equality iff A = B = 30^o and C = 120^o. Since we are told that we do have equality, the angles are fixed. 

Problem 4

Each edge of a connected graph with n points is colored red, blue or green. Each point has exactly three edges, one red, one blue and one green. Show that n must be even and that such a colored graph is possible for any even n > 2. X is a subset of 1 < k < n points. In order to isolate X from the other points (so that there is no edge between a point in X and a point not in X) it is necessary and sufficient to delete R red edges, B blue edges and G green edges. Show that R, B, G are all even or all odd.

Solution

The number of edges is 3n/2. This must be integral, so n must be even. Take a regular 2m-gon. Make the sides alternately red and blue and draw the main diagonals (connecting each point to the opposite point) green. Then each vertex has three edges, one of each color.

Suppose X has m vertices. There must be R red, B blue, and G green edges with just one end a point of X. Suppose there are r red, b blue and g green edges with both ends at a point of X. We have R + 2r = m, B + 2b = m, G + 2g = m. Hence R, B and G have the same parity.

[more...]

27th British Mathematical Olympiad 1991 Problems

27th British Mathematical Olympiad 1991 Problems

1.  ABC is a triangle with ∠B = 90^o and M the midpoint of AB. Show that sin ACM ≤ 1/3.

2.  Twelve dwarfs live in a forest. Some pairs of dwarfs are friends. Each has a black hat and a white hat. Each dwarf consistently wears one of his hats. However, they agree that on the nth day of the New Year, the nth dwarf modulo 12 will visit each of his friends. (For example, the 2nd dwarf visits on days 2, 14, 26 and so on.) If he finds that a majority of his friends are wearing a different color of hat, then he will immediately change color. No other hat changes are made. Show that after a while no one changes hat.

3.  A triangle has sides a, b, c with sum 2. Show that a² + b² + c² + 2abc < 2.

4.  Let N be the smallest positive integer such that at least one of the numbers x, 2x, 3x, ... , Nx has a digit 2 for every real number x. Find N. Failing that, find upper and lower bounds and show that the upper bound does not exceed 20. 

Solutions

Problem 1

ABC is a triangle with ∠B = 90^o and M the midpoint of AB. Show that sin ACM ≤ 1/3.

Solution

Take AM = MB = 1 and let BC = x. Then CM² = x² + 1, CA² = x² + 4. Applying the cosine rule to triangle ACM, we get cos ACM = (2 + x²)/(x⁴ + 5x² + 4)^1/2. We claim that this is at least 2√2)/3 with equality iff x = √2. Certainly angle ACM < 90^o, so cos ACM is positive so the claim is equivalent to 9(x⁴ + 4x² + 4) ≥ 8(x⁴ + 5x² + 4), or x⁴ - 4x² + 4 ≥ 0, or (x² - 2)² ≥ 0, which establishes the result. Thus the maximum value of sin ACM is (1 - 8/9)^1/2 = 1/3.

Alternative solution

Let N be the midpoint of AC. Let G be the centroid (intersection of BN and CM). Let P be the foot of the perpendicular from N to CM. Then sin ACM = NP/NC = NP/NB (angle B is 90^o, so N is the center of the circle ABC) = NP/3NG. But NP/NG ≤ 1 with equality iff BN and CM are perpendicular. 

Problem 2

Twelve dwarfs live in a forest. Some pairs of dwarfs are friends. Each has a black hat and a white hat. Each dwarf consistently wears one of his hats. However, they agree that on the nth day of the New Year, the nth dwarf modulo 12 will visit each of his friends. (For example, the 2nd dwarf visits on days 2, 14, 26 and so on.) If he finds that a majority of his friends are wearing a different color of hat, then he will immediately change color. No other hat changes are made. Show that after a while no one changes hat.

Solution

Consider the number of friendly pairs who wear a different color. It must increase if a dwarf changes his hat. But it cannot increase indefinitely. [The details of the visiting rota are irrelevant.] 

Problem 3

A triangle has sides a, b, c with sum 2. Show that a² + b² + c² + 2abc < 2.

Solution

Each side must be shorter than the sum of the other two. So a < 1, b < 1, c < 1. Hence 2(1 - a)(1 - b)(1 - c) > 0, or 2 - 2(a + b + c) + 2(ab + bc + ca) - 2abc > 0, or -2 + 2(ab + bc + ca) - 2abc > 0. Subtracting (a + b + c)² = 4 gives the required result. 

Problem 4

Let N be the smallest positive integer such that at least one of the numbers x, 2x, 3x, ... , Nx has a digit 2 for every real number x. Find N. Failing that, find upper and lower bounds and show that the upper bound does not exceed 20.

Solution

Answer: 12.

A real number may have infinitely many digits. The strategy therefore has to be to exhibit some rational number which requires N to get a 2, and then to show that for any real number some special digit, such as the first, is a 2 for some multiple <= N.

A little experimentation reveals that for most integers fairly small multiples suffice. We notice that 15 requires 8, but most seem to need less.

If x has first digit 7, 8 or 9, then 3x has first digit 2. If x has first digit 5 or 6, then 4x has first digit 2. If x has first digit 4, then 5x has first digit 2. If x has first digit 3, then 7x has first digit 2. Obviously, if x has first digit 2, then 1x has first digit 2. So we need only consider numbers with first digit 1.

If x has second digit 2, we are home. If x has second digit 0 (including of course the case x has no second digit), 1, 3 or 4, then 2x has first digit 2. If x has second digit 5, then 8x has second digit 2.

It is convenient to notice that x and 10x behave the same way, so we can restrict x to be between 1 and 10. The analysis above shows that we need only consider 1.6 ≤ x < 1.9. If 5/3 ≤ x < 2, then 20 ≤ 12x < 30.

We might also look at 5/3. Its multiples are 1.66... , 3.33... , 5, 6.66... , 8.33... , 10, 11.66... , 13.33... , 15, 16.66... , 18.33... , 20. So it requires N = 12.

So we are left with 1.6 ≤ x < 5/3. The first digit is not 2 for N up to 12. But we notice that 2x has a 2 for 1.6 ≤ x < 1.65, and for 1.66 ≤ x < 1.665 and for 1.666 ≤ x ≤ 1.6665 and so on. Also 5x has a 2 for 1.64 ≤ x < 1.66 and for 1.664 ≤ x < 1.666 and so on. Thus 2x or 5x has a 2 for any x in the range 1.6 ≤ x < 5/3.

Note that there are other x which require N = 12, such as 1.6795 and 1.6835.

[more...]