1st Australian Mathematical Olympiad Problems 1979

1.  A graph with 10 points and 35 edges is constructed as follows. Every vertex of one pentagon is joined to every edge of another pentagon. Each edge is colored black or white, so that there are no monochrome triangles. Show that all 10 edges of the two pentagons have the same color.

2.  Two circles (not necessarily equal) intersect at A and B. A point P travels clockwise around the first circle at a constant speed, completing one revolution a minute. Another point Q travels clockwise around the second circle at a constant speed, also completing one revolution a minute. The two points pass through A simultaneously. Show that P, B and Q are collinear and that there is a fixed point C such that CP = CQ at all times.

3.  8 flower pots A, B, C, D, E, F, G, H are arranged in a circle. A frog starts at A and jumps to an adjacent pot (B or H). The frog always jumps to an adjacent pot, makes n jumps, ends up at E, but does not visit E until then. Show that n must be even and that the number of possible routes is ( (2 + √2)^m - (2 - √2)^m)/√2, where n = 2m+2. 

Solutions

Problem 1

A graph with 10 points and 35 edges is constructed as follows. Every vertex of one pentagon is joined to every edge of another pentagon. Each edge is colored black or white, so that there are no monochrome triangles. Show that all 10 edges of the two pentagons have the same color.

 

Solution

This surprisingly awkward. Label one pentagon A₁A₂A₃A₄A₅ and the other B₁B₂B₃B₄B₅. Suppose one of the pentagon edges AA' from A is black. Suppose 3 edges from A to the other pentagon are black. Then two of the points in the other pentagon (joined to A by a black edge) must be joined by an edge, which must be white. Call them B and B'. But the triangle AA'B has two black edges AA' and AB, so the third A'B must be white. Similarly, AA'B' has AA' and AB' black, so A'B' must be white. But now A'BB' has all edges white. Contradiction. So at most 2 edges from A to the other pentagon are black.

If the other pentagon edge from A is white, then the same argument would show that at most 2 edges from A to the other pentagon are white. But there are 5 such edges. So the other pentagon edge from A must be black. Repeating the argument allows us to go around the pentagon and deduce that all its edges are black.

Similarly, we can show that the other pentagon is monochrome. Suppose one is white and one is black. Take A to be a vertex of the black pentagon. Then the argument above shows that 3 of the edges from A to the other pentagon must be white. But two of the points in the other pentagon joined to A by a white edge must be joined and that gives a white triangle. Contradiction. So the two pentagons are the same color. 

Problem 2

Two circles (not necessarily equal) intersect at A and B. A point P travels clockwise around the first circle at a constant speed, completing one revolution a minute. Another point Q travels clockwise around the second circle at a constant speed, also completing one revolution a minute. The two points pass through A simultaneously. Show that P, B and Q are collinear and that there is a fixed point C such that CP = CQ at all times.

 

Solution

Let the circles have centers O, O'. Let C be the reflection of A in the perpendicular bisector of OO'. We show that triangles COP, QO'C are congruent. We have OP = OA (pts on circle) = O'C (reflection). Also OC = O'A (reflection) = O'Q (pts on circle). Also ∠AOP = ∠AO'Q (P and Q circle at same rate), and ∠AOC= ∠AO'C (reflection), so ∠COP = ∠CO'Q. So the triangles are congruent. Hence CP = CQ.

Now ∠ABP = ½∠AOP or 180^o-½∠AOP, and ∠ABQ = ½∠AO'Q or 180^o-½∠AO'Q. Hence ∠ABP = ∠ABQ or ∠ABP + ∠ABQ = 180^o. Either way, P,Q,B are collinear.

This is almost the same as IMO 79/A3.

Problem 3

8 flower pots A, B, C, D, E, F, G, H are arranged in a circle. A frog starts at A and jumps to an adjacent pot (B or H). The frog always jumps to an adjacent pot, makes n jumps, ends up at E, but does not visit E until then. Show that n must be even and that the number of possible routes is ( (2 + √2)^m - (2 - √2)^m)/√2, where n = 2m+2.

 

Solution

Let m be the number of clockwise jumps. Then n-m is the number of anticlockwise jumps and we have m - (n-m) = ±4, so n = 2m±4, which is even. So the number of ways is zero for n odd.

Let u_n be the number of routes from A, and let v_n be the number of routes from C. By symmetry the number of routes from G is also v_n. Now consider u_n+2 (for n > 0). After 2 jumps, the frog is at A (2 possibilities), C (1 possibility) or G (1 possibility), so u_n+2 = 2u_n + 2v_n (1). Similarly, v_n+2 = 2v_n + u_n (2) for n > 0 (note that the second jump cannot take the frog to E because the frog may not reach E until its last jump). Writing (1) as 2v_n = u_n+2 - 2u_n and substituting in (2) we get u_n+4 - 4u_n+2 + 2u_n = 0.

Put u_2m+2 = a_m, then we have a_m+2 - 4a_m+1 + 2a_m = 0. That has solution a_m = A(2+√2)^m + B(2-√2)^m for some constants A, B. But it is obvious that a₀ = u₂ = 0, a₁ = u₄ = 2, so A + B = 0, 2(A+B) + √2 (A-B) = 2. Hence A = 1/√2, B = -1/√2.