Solutions

67.

(a) Consider the infinite integer lattice in the plane (i.e., the set of points with integer coordinates) as a graph, with the edges being the lines of unit length connecting nearby points. What is the minimum number of colours that can be used to colour all the vertices and edges of this graph, so that

(ii) each pair of edges that meet at a vertex get two distinct colours; AND

(iii) an edge is coloured differently than either of the two vertices at the ends?

(b) Extend this result to lattices in real n-dimensional space.

Solution 1. Since each vertex and the four edges emanating from it must have different colours, at least five colours are needed. Here is a colouring that will work: Let the colours be numbered 0, 1, 2, 3, 4. Colour the point (x, 0) with the colour x (mod 5); colour the point (0, y) with the colour 2y (mod 5); colour the points along each horizontal line parallel to the x-axis consecutively; colour the vertical edge whose lower vertex has colour m (mod 5) with the colour m+1 (mod 5); colour the horizontal edge whose left vertex has the colour n (mod 5) with the colour n + 3 (mod 5).

This can be generalized to an n-dimensional lattice where 2n+1 colours are needed by changing the strategy of colouring. The integer points on the line and the edges between them can be coloured 1 - (3) - 2- (1) - 3 - (2) - 1 and so on, where the edge colouring is in parenthesis. Form a plane by stacking these lines unit distance apart, making sure that each vertex has a different coloured vertex above and below it; use colours 4 and 5 judiciously to colour the vertical edges. Now go to three dimensions; stack up planar lattices and struts unit distance apart, colouring each with the colours 1, 2, 3, 4, 5, while making sure that vertically adjacent vertices have separate colours, and use the colours 6 and 7 for vertical struts. Continue on.

Solution 2. Consider the n- dimensional lattice. Let the colours be numbered 0, 1, 2, ¼, 2n. Assign the vertex with coordinates (x₁, x₂, ¼,x_n) the colour x₁ + 2x₂ + ¼+ nx_n, modulo 2n+1. Adjacent vertices have distinct colours. For each adjacent vertex has the same coordinates, except in one position where the coordinates differ by 1; if this is the ith coordinate, then the numbers of the two colours differ by ±i (mod 2n+1).

Consider an edge joining a vertex with colour u to one of colour v; assign this edge the colour (n+1)(u + v) (mod 2n+1). Since (n + 1)(u + v) - v º n(u - v) (mod 2n + 1), the greatest common divisor of n and 2n + 1 is 1 and u \not º v (mod 2n+1), it follows that the colour of this edge differs from v; similarly, it differs from u.

Finally, consider a pair of adjacent edges, with colours (n+1)(u + v) and (n+1)(v + w) (mod 2n+1). The difference between these colours, modulo 2n+1, is equal to (n+1)(u - w). If the edges are collinear, then this difference is ±2(n+1)i for some i with 1 £ i £ n, and this is not congruent to zero modulo 2n+1. If the edges are perpendicular, then this difference is nonzero and of the form (n+1)(±i ±j). This value, lying between -2n and 2n is not congruent to zero modulo 2n+1. Thus, adjacent edges have distinct colours.

Therefore, we can achieve our goal with 2n+1 colours, and, by looking at a vertex and its adjacent edges, we see that this is minimal.

68.

Let a, b, c > 0, a < bc and 1 + a³ = b³ + c³. Prove that 1 + a < b + c.

Solution 2. [J. Chui] Let u = (1 + a) - (b + c). Then

Solution 3. [A. Momin, N. Martin] Suppose, if possible, that (1 + a) ³ (b + c). Then

Solution 4. [H. Pan] First, observe that a = c leads to b = 1 and a contradiction of the given conditions, while a = b leads to c = 1 and a contradiction. Suppose, if possible, that that b > a > c. Then b³ + 1 > a³ + 1 = b³ + c³ > c³ + 1, and c < 1 < b. Therefore,

Thus, a must be either the largest or the smallest of the three numbers. Hence (a - b)(a - c) > 0, whence a² + bc > a(b + c). Therefore

Solution 5. [X. Li] If 1 + a² < b² + c², then

Solution 6. [P. Gyrya] Let p(x) = x³ - 3ax. Checking the first derivative yields that p(x) is strictly increasing for x > Öa. Now 1 + a ³ 2Öa > Öa and b + c ³ 2Ö[bc] > 2Öa > Öa, so both 1 + a and b + c lie in the part of the domain of p(x) where it strictly increases. Now

Solution 7. Consider the function g(x) = x(1 + a³ - x) = x(b³ + c³ - x). Then g(1) = g(a³) = a³ and g(b³) = g(c³) = (bc)³. Since a³ < (bc)³ and the graph of g(x) is a parabola opening down, it follows that b³ and c³ lie between 1 and a³.

Now consider the function h(x) = x^1/3 + (b³ + c³ - x)^1/3 = x^1/3 + (1 + a³ - x)^1/3 for 0 £ x £ 1 + a³. Then h(1) = h(a³) = 1 + a and h(b³) = h(c³) = b + c. The graph of h(x) resembles an inverted parabola, so since b³ and c³ lie between 1 and a³, it follows that 1 + a < b + c, as desired.

69.

Let n, a₁, a₂, ¼, a_k be positive integers for which n ³ a₁ > a₂ > a₃ > ¼ > a_k and the least common multiple of a_i and a_j does not exceed n for all i and j. Prove that ia_i £ n for i = 1, 2, ¼, k.

Assume that b £ m. Then

Solution 2. We can obtain the result by induction, it being known when i = 1. Suppose that the result holds up to i = m. If (m + 1)a_m £ n, then the desired result for i = m + 1 follows from a_m+1 > a_m. On the other hand, suppose that (m+1)a_m > n. With ba_m+1 = ca_m the least common multiple of a_m and a_m+1, we have that (m+1)a_m > ca_m, so that

70.

Let f(x) be a concave strictly increasing function defined for 0 £ x £ 1 such that f(0) = 0 and f(1) = 1. Suppose that g(x) is its inverse. Prove that f(x)g(x) £ x² for 0 £ x £ 1.

Solution. Let 0 < v £ u. Then, taking t = (u-v)/u in the definition of concavity, we have that

Comment. A special case is that f(x) = x^k for 0 < k < 1, so that g(x) = x^1/k. Then f(x)g(x) = x^{k + (1/k)} and the result holds since 0 £ x £ 1 and k + (1/k) ³ 2.

71.

Suppose that lengths b, c and i are given. Construct a triangle ABC for which |AC | = b. |AB | = c and the length of the bisector AD of angle A is i (D being the point where the bisector meets the side BC).

Construction. Construct an isosceles triangle ABT with the lengths of AB and AT both equal to c and the length of AT equal to i(b+c)/b. Cut AD off AT to have the length i, and let C be the intersection of AD and the line through A parallel to BT.

Proof of construction. Since ÐBAT = ÐBTA = ÐCAT, the segment AT bisects angle BAC. The length of AD is i and the length of AB is c, by construction. From the similar triangles, DBT and ADC, we find that the length of AC is i multiplied by c = |BT | and divided by [i(b+c)/b] - i = ic/b = |DT |.

Feasibility. In order for the construction to work, we require that the sum of the lengths of AB and BT exceed that of AT. This requires 2c > i(b+c)/b or i < 2bc/(b+c).

Solution 2. Analysis. Let q be equal to angles BAD and CAD, where ABC is the required triangle with bisector AD. Since the area of DABC is the sum of the areas of DABD and DADC, we have that bc sin2q = i(b+c)sinq, whence cosq = (b + c)i/2bc.

Sketch of construction and proof. By Euclidean means it is possible to construct the lengths b + c, (b + c)i, 2bc and (b+c)/2bc using proportionalities. Thus, we can obtain the cosine of the angle q, and so find q itself. Construct triangle ABC with the respective lengths of AB and AC equal to c and b and ÐBAC = 2q. The calculation in the analysis can be used to verify that the length of the bisector is equal to 2bccosq/(b+c), and so equal to i. Note that for q to be found, it is necessary to have (b+c)i £ 2bc.

72.

The centres of the circumscribed and the inscribed spheres of a given tetrahedron coincide. Prove that the four triangular faces of the tetrahedron are congruent.

Solution 2. Let R and r be respectively the circumradius and the inradius of ABCD, let the faces BCD, ACD, ABD and ABC touch the insphere in the respective points P, Q, T, S, and let O be the common centre of the insphere and the circumsphere. Since triangle OSA is right with |OS | = r and |OA | = R, we have that |SA | = Ö[(R² - r²)]. Similarly, |SB | = |SC | = Ö[(R² - r²)], so that S is the centre of a circle with radius Ö[(R² - r²)] passing through A, B, C. The same can be said about P, Q, T, and the faces that contain them.

It can be seen that DABT º DABS, DACQ º DACS, DADQ º DADT, DBCP º DBCS, DBDP º DBDR and DCDP º DCDQ. Now

Obtaining other similar angle equalities, we can determine that the faces are equiangular. Taking note of common sides, we can then deduce their congruence.