Math olympiad practice problems

Hint 1: Factor the expression.

Hint 2: Among three consecutive integers, one is divisible by 3 and at least one is even.

Answer: 6 divides n^3 - n for every integer n.

Factor n^3 - n = (n - 1)n(n + 1). Among any three consecutive integers, exactly one is a multiple of 3, and at least one is even. Hence their product has a factor 3 and a factor 2. Since 2 and 3 are relatively prime, it is divisible by 6. This also covers negative integers and zero.

Hint 1: A square is always nonnegative.

Hint 2: Expand (x - y)^2 and use xy = 1.

Answer: x + y >= 2, with equality exactly at x = y = 1.

We have (x + y)^2 = (x - y)^2 + 4xy = (x - y)^2 + 4 >= 4. Since x + y is positive, taking square roots gives x + y >= 2.

Equality holds exactly when (x - y)^2 = 0, or x = y. Together with xy = 1 and positivity, this forces x = y = 1. Those values attain equality.

Hint 1: Compare triangles ABD and ACD.

Hint 2: Use three equal pairs of sides, then examine the two angles at D.

Answer: AD is perpendicular to BC and angle BAD equals angle DAC.

Triangles ABD and ACD have AB = AC, BD = DC because D is the midpoint, and AD as a common side. They are congruent by the side-side-side criterion. Thus angle BAD equals angle DAC, so AD bisects angle BAC.

Congruence also gives angle BDA = angle ADC. Because B, D, C are collinear, these two angles sum to 180 degrees. Each is therefore 90 degrees, proving AD perpendicular to BC.

Hint 1: Classify the integers by their remainders modulo 4.

Hint 2: There are four remainder classes but five integers.

Answer: Two of the five integers have difference divisible by 4.

Every integer has one of the four remainders 0, 1, 2, 3 on division by 4. With five integers in four classes, the pigeonhole principle gives two in the same class. Write them as 4a + r and 4b + r. Their difference is 4(a - b), which is divisible by 4. This includes the possibility of equal integers, whose difference is 0.

Hint 1: Multiply by 6xy and complete a product.

Hint 2: The equation is equivalent to (x - 6)(y - 6) = 36. Explain why both factors are positive.

Answer: (7,42), (8,24), (9,18), (10,15), and (12,12).

Multiplying by 6xy gives xy = 6x + 6y, or (x - 6)(y - 6) = 36. Also 1/x = 1/6 - 1/y < 1/6, so x > 6; similarly y > 6. Thus both new factors are positive integers.

Since x <= y, the factor x - 6 is at most sqrt(36) = 6. The positive divisors of 36 up to 6 are 1, 2, 3, 4, and 6, giving factor pairs (1,36), (2,18), (3,12), (4,9), and (6,6).

Adding 6 to each entry gives exactly (7,42), (8,24), (9,18), (10,15), and (12,12). Each pair satisfies the product equation and hence the original equation, so the list is complete.

Hint 1: Substitute c = -(a + b).

Hint 2: Expand a^3 + b^3 - (a + b)^3 and factor.

Answer: The cube sum equals 3abc; a zero cube sum forces abc = 0.

Since c = -(a + b), we have a^3 + b^3 + c^3 = a^3 + b^3 - (a + b)^3 = -3a^2 b - 3ab^2 = -3ab(a + b) = 3abc.

If the cube sum is also zero, then 3abc = 0, so abc = 0. A product of real numbers is zero only when at least one factor is zero. Hence at least one of a, b, c is zero.

Hint 1: Compare the two smaller right triangles ABD and CAD.

Hint 2: Show they are similar with BD corresponding to AD and AD corresponding to DC.

Answer: The altitude satisfies h^2 = pq.

Because the original triangle is nondegenerate and right-angled at A, the foot D lies between B and C and p, q, h are positive. Triangles ABD and CAD are right-angled at D.

Angle ABD is angle ABC. In triangle ACD, angle CAD = 90 degrees - angle ACD = 90 degrees - angle ACB = angle ABC. Thus triangles ABD and CAD are similar by two angles, with B corresponding to A, A to C, and D to D.

The corresponding sides give BD/AD = AD/DC, or p/h = h/q. Multiplying by hq yields h^2 = pq.

Hint 1: Add all eight adjacent-pair sums.

Hint 2: If every sum were at most 9, their average would force all of them to be exactly 9. What would that imply for alternating positions?

Answer: At least one adjacent pair has sum at least 10.

Each number appears in exactly two adjacent-pair sums, so the total of those eight sums is 2(1 + 2 + ... + 8) = 72. Their average is 9.

Suppose no adjacent sum is at least 10. Because the sums are integers, they are all at most 9. Their total 72 then forces every sum to be exactly 9. If three successive entries are a, b, c, we get a + b = b + c = 9, hence a = c. This repeats a number in distinct positions, contrary to using each number once. Therefore some adjacent sum is at least 10.

Hint 1: Squares have remainder 0 or 1 modulo 3.

Hint 2: Show that a, b, and c would all be divisible by 3, producing a smaller positive solution.

Answer: No positive integer triple satisfies the equation.

Suppose a positive solution exists, and choose one with c as small as possible. Modulo 3, a square is 0 or 1. Since a^2 + b^2 is 0 modulo 3, both squares must be 0 modulo 3. Thus a = 3u and b = 3v for positive integers u, v.

Substitution gives 9(u^2 + v^2) = 3c^2, or c^2 = 3(u^2 + v^2). Hence 3 divides c^2 and therefore c; write c = 3w. The original equation now reduces to u^2 + v^2 = 3w^2.

This is another positive solution with w = c/3 < c, contradicting the minimal choice of c. The assumption of a solution is impossible.

Hint 1: For positive u and v, u/v + v/u >= 2 follows from (u - v)^2 >= 0.

Hint 2: Apply the three-variable reciprocal inequality to u = b + c, v = c + a, w = a + b.

Answer: The sum is at least 3/2, with equality exactly when a = b = c.

For any positive u, v, w, expand (u + v + w)(1/u + 1/v + 1/w). The three diagonal terms sum to 3, and each of the three pairs u/v + v/u, v/w + w/v, w/u + u/w is at least 2, since for example u/v + v/u - 2 = (u - v)^2/(uv) >= 0. Therefore the product is at least 9, with equality exactly when u = v = w.

Set s = a + b + c and take u = s - a, v = s - b, w = s - c. These are positive and sum to 2s, so 1/(s - a) + 1/(s - b) + 1/(s - c) >= 9/(2s).

Now a/(s - a) = s/(s - a) - 1, and similarly for the other terms. Their sum is at least s x 9/(2s) - 3 = 3/2. Equality requires s - a = s - b = s - c, equivalent to a = b = c; any positive equal triple attains it.

Hint 1: Use BH perpendicular to AC and CH perpendicular to AB to express angle BHC in terms of angle BAC.

Hint 2: Reflection preserves angle BHC. A and H' are on opposite sides of BC, so use the supplementary opposite-angle test for a cyclic quadrilateral.

Answer: The reflection H' is on the circumcircle of triangle ABC.

Let angle BAC be alpha. Because the triangle is acute, H is inside it. In triangle BHC, angle HBC = 90 degrees - angle ACB, and angle HCB = 90 degrees - angle ABC. Thus angle BHC = angle ABC + angle ACB = 180 degrees - alpha.

Reflection in BC fixes B and C and preserves angles, so angle BH'C = angle BHC = 180 degrees - alpha. H' is on the opposite side of BC from A, since H is on the same side as A.

The simple quadrilateral A-B-H'-C has opposite angles BAC and BH'C summing to 180 degrees. By the converse of the cyclic-quadrilateral angle theorem, its four vertices lie on a circle. Thus H' lies on the circle through A, B, and C.

Hint 1: Classify a tiling by the domino or pair of dominoes covering its left edge.

Hint 2: Derive T_n = T_(n-1) + T_(n-2), then examine the recurrence modulo 2.

Answer: T_n is even if and only if n = 2 modulo 3.

We have T_0 = 1 and T_1 = 1. For n >= 2, the leftmost column is either covered by one vertical domino, leaving a 2 by (n - 1) board, or by the ends of two horizontal dominoes. In the second case both horizontal dominoes are forced, leaving a 2 by (n - 2) board. These cases are disjoint and exhaustive, so T_n = T_(n-1) + T_(n-2).

Modulo 2, this gives T_(n+3) = T_(n+2) + T_(n+1) = T_n + 2T_(n+1), which has the same parity as T_n for every n >= 0. Thus the parity has period 3. The first three values are 1, 1, 2, with parities odd, odd, even. Therefore T_n is even exactly for n = 2 modulo 3.