9th Balkan Mathematical Olympiad Problems 1992

9th Balkan Mathematical Olympiad Problems 1992

A1.  Let a(n) = 3⁴ⁿ. For which n is (m^a(n)+6 - m^a(n)+4 - m⁵ + m³) always divisible by 1992?

A2.  Prove that (2n² + 3n + 1)ⁿ ≥ 6ⁿn! n! for all positive integers.

A3.  ABC is a triangle area 1. Take D on BC, E on CA, F on AB, so that AFDE is cyclic. Prove that: area DEF ≤ EF²/(4 AD²).

A4.  For each n > 2 find the smallest f(n) such that any subset of {1, 2, 3, ... , n} with f(n) elements must have three which are relatively prime (in pairs). 

Solutions

9th Balkan 1992 Problem 1

Let a(n) = 3⁴ⁿ. For which n is (m^a(n)+6 - m^a(n)+4 - m⁵ + m³ always divisible by 1992?

Solution Answer: n odd.

1992 = 24·83. Let f(m) = (m^a(n) - m^a(n)-2 - m⁵ + m³. Factorising, we have f(m) = m³(m² - 1)(m^a(n)+1 - 1). Now if m is even, then 8 divides m³. If m is odd, then m-1 and m+1 are consecutive even numbers, so one is divisible by 4 and hence 8 divides m² - 1. One of m-1, m, m+1 must be divisible by 3. Hence 24 always divides m³(m² - 1) and hence f(m). Now if m is not divisible by 83, then m⁸² = 1 mod 83, since 83 is prime. If n is odd and m is not divisible by 83, then a(n) + 1 = (82 - 1)ⁿ + 1, which is divisible by 82 and hence m^a(n)+1 - 1 is divisible by 83. But m³ is certainly divisible by 83 if m is, so we have established that 1992 always divides f(m) for n odd.

If n is even, then a(n) + 1 = (82 - 1)ⁿ + 1 = 2 mod 82. Hence m^a(n)+1 = m² mod 83. So, in particular, if we take m = 2, then m^a(n)+1 - 1 = 3 mod 83. But 2³(2² - 1) = 24, which is also not divisible by 83. So for even n, f(2) is not divisible by 1992. 

9th Balkan 1992 Problem 2

Prove that (2n² + 3n + 1)ⁿ ≥ 6ⁿn! n! for all positive integers.

Solution

(a - x)x = a²/4 - (x - a/2)², so (a - x)x ≤ a²/4. In particular, 6(n+1-m)m ≤ 6(n+1)²/4. Now n² ≥ 1, so 6n² + 12n + 6 ≤ 8n² + 12n + 4 or 6(n+1)²/4 ≤ 2n² + 3n + 1. Hence 6(n + 1 - m)m ≤ (2n² + 3n + 1). Multiplying together the inequalities for m = 1, ... , n we get 6ⁿ n! n! ≤ (2n² + 3n + 1)ⁿ.

Alternatively, with more insight, by Michael Lipnowski:

n(n+1)(2n+1)/6 = 1² + 2² + ... + n², so (2n² + 3n + 1)/6 = (1² + 2² + ... + n²)/n ≥ n!^2/n by AM/GM.

9th Balkan 1992 Problem 3

ABC is a triangle area 1. Take D on BC, E on CA, F on AB, so that AFDE is cyclic. Prove that: area DEF ≤ EF²/(4 AD²).

Solution

Extend AD to meet the circumcircle of ABC again at P. Then ∠DEF = ∠DAF (circle AFDE) = ∠PAB (same angle) = ∠PCB (circle ABPC). Similarly, ∠DFE = ∠DAE = ∠PAC = ∠PBC. So triangles DEF and PCB are similar. So area DEF = (EF²/BC²) area PCB. But triangles PCB and ABC have the same base BC, so area PCB = (PD/AD) area ABC = PD/AD. Hence area DEF = (EF²/BC²) (PD/AD).

BC = BD + DC, so 1/BC² = 1/(BC + CD)² ≤ 1/(4 BD.DC) by AM/GM. But ABPC is cyclic, so BD.DC = AD.PD. Hence 1/BC² ≤ 1/(4 AD.PD). Hence area DEF ≤ EF²/( 4 AD²).

9th Balkan 1992 Problem 4

For each n > 2 find the smallest f(n) such that any subset of {1, 2, 3, ... , n} with f(n) elements must have three which are relatively prime (in pairs).

Solution

Answer: f(6m) = f(6m+1) = 4m+1, f(6m+2) = 4m+2, f(6m+3) = 4m+3, f(6m+4) = f(6m+5) = 4m+4.

Let S_n = {1, 2, ... , n}. Now 4m members of S_6m are divisible by 2 or 3 (or both). So f(6m) > 4m. Now suppose X is a subset of S_6m with 4m+1 members. Then one of the sets {1, 2, ... , 6}, {7, 8, ... , 12}, ... , {6m-5, ... 6m} must contain 5 or more members of X. Suppose it is {6r+1, 6r+2, 6r+3, 6r+4, 6r+5, 6r+6}. Then it must contain at least one of {6r+2, 6r+3, 6r+5}, {6r+1, 6r+3, 6r+4}, or {6r+1, 6r+4, 6r+5} all of which have relatively prime members. (Consider for example {6r+2, 6r+3, 6r+5}. If s > 1 divides 6r+3 and 6r+5, then it divides their difference 2, so it must be 2, but 2 does not divide 6r+3. Similarly, for the other cases.) That establishes that f(6m) = 4m+1.

For n = 6m+1, the argument is the same except that any subset X of S_6m+1 must either contain 5 elements of some {6r+1, 6r+2, ... , 6r+6} or 5 elements of {6m-5, 6m-4, 6m-3, 6m-2, 6m-2, 6m, 6m+1}. So we have to deal with the case where it contains 5 elements of {6m-5, 6m-4, 6m-3, 6m-2, 6m-1, 6m, 6m+1}. But in that case it must include 3 elements from {6m-5, 6m-3, 6m-2, 6m-1, 6m+1} which are all relatively prime.

For n = 6m+2, the argument is similar except that we have to show that any 6 elements of {6m-5, 6m-4, 6m-3, 6m-2, 6m-1, 6m, 6m+1, 6m+2} include 3 which are relatively prime. But 6 elements must include at least 3 from {6m-5, 6m-3, 6m-2, 6m-1, 6m+1} which are all relatively prime.

For n = 6m+3, we have to show that any 7 elements of {6m-5, 6m-4, 6m-3, 6m-2, 6m-1, 6m, 6m+1, 6m+2, 6m+3} include 3 which are relatively prime. But 7 elements must include 3 from {6m-5, 6m-3, 6m-2, 6m-1, 6m+1} which are all relatively prime.

For n = 6m+4, we have to show that any 8 elements of {6m-5, ... , 6m+4} include 3 which are relatively prime, but again they must include 3 of {6m-5, 6m-3, 6m-2, 6m-1, 6m+1} which are all relatively prime.

Finally, for n = 6m+5, we have to show that any 8 elements of {6m-5, ... 6m+5} include 3 which are relatively prime. But the 8 can only include at most 2 of 6m+3, 6m+4, 6m+5 (which are all relatively prime), and at most all of 3 of {6m-4, 6m, 6m+2}, so again it must include at least 3 of {6m-5, 6m-3, 6m-2, 6m-1, 6m+1} which are all relatively prime.