Search

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
(i) each pair of adjacent vertices gets two distinct colours; AND

(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 (x1, x2, ¼,xn) the colour x1 + 2x2 + ¼+ nxn, 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 + a3 = b3 + c3. Prove that 1 + a < b + c.
Solution 1. Since (1 + a)(1 - a + a2) = (b + c)(b2 - bc + c2), and since 1 - a + a2 and b2 - bc + c2 are positive, we have that


1 + a < b + c Û1 - a + a2 > b2 - bc + c2 .
Suppose, if possible, that 1 + a ³ b + c. Then


b2 - bc + c2
³ 1 - a + a2
Þ (b + c)2 - 3bc ³ (1 + a)2 - 3a > (1 + a)2 - 3bc
Þ (b + c)2 > (1 + a)2Þ b + c > 1 + a
which is a contradiction.

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


(1 + a)3 - (b + c)3
= u[(1 + a)2 + (1 + a)(b + c) + (b + c)2]
= u[(1 + a)2 + (1 + a)(b + c) + b2 + 2bc + c2] .
But also


(1 + a)3 - (b + c)3
= (1 + a3) - (b3 + c3) + 3a(1 + a) - 3bc(b + c)
= 0 + 3[a(1+a) - bc(b + c)] < 3bcu .
It follows from these that


0 > u[(1 + a)2 + (1 + a)(b + c) + b2 - bc + c2] = u[(1 + a)2 + (1 + a)(b + c) + 1
2
(b - c)2+ 1
2
(b2 + c2)] .
Since the quantity in square brackets is positive, we must have that u < 0, as desired.

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


0 £ (1 + a)2 - (b + c)2 = (1 + a2) - (b2 + c2)- 2(bc - a) < (1 + a2) - (b2 + c2) .
Hence 1 + a2 > b2 + c2. It follows that


(1 - a + a2) - (b2 - bc + b2) = (1 + a2) -(b2 + c2) + (bc - a) > 0
so that


(1 - a + a2) > (b2 - bc + c2) .
However


(1 + a)(1 - a + a2) = 1 + a3 = b3 + c3+ (b + c)(b2 - bc + c2) ,
from which it follows that 1 + a < b + c, yielding a contradition. Hence, the desired result follows.

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 b3 + 1 > a3 + 1 = b3 + c3 > c3 + 1, and c < 1 < b. Therefore,


bc > a Þ b3c3 > b3 + c3 - 1Þ (b3 - 1)(c3 - 1) > 0 ,
which contradicts b > 1 > c. In a similar way, we see that c > a > b cannot occur.

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


(b + c - a)3
= b3 + c3 - a3 + 3b2c + 3bc2 - 3ab2 - 3ac2 + 3a2b + 3a2c - 6abc
= 1 + 3b(a2 + bc) + 3c(a2 + bc) - 3ab(b+c) - 3ac(b+c)
= 1 + 3(b+c)[(a2 + bc) - a(b + c)] > 1
and the desired result follows.

Solution 5. [X. Li] If 1 + a2 < b2 + c2, then


(1 + a)2 = 1 + a2 + 2a < b2 + c2 + 2bc = (b + c)2 ,
whence b + c > 1 + a. On the other hand, if 1 + a2 ³ b2 + c2, then


1 + a2 - a > b2 + c2 - bc = (b3 + c3)/(b + c) > 0 ,
whereupon,


(b + c)(b2 + c2 - bc)
= b3 + c3 = 1 + a3
= (1+a)(1 + a2 - a) > (1 + a)(b2 + c2 - bc)
so that b + c > 1 + a.

Solution 6. [P. Gyrya] Let p(x) = x3 - 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


p(1 + a) = (1 + a)3 - 3a(1 + a) = 1 + a3 = b3 + c3 = (b + c)3 - 3bc(b + c) < (b + c)3 - 3a(b + c) = p(b + c)
from which it follows that 1 + a < b + c.

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

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



69.
Let n, a1, a2, ¼, ak be positive integers for which n ³ a1 > a2 > a3 > ¼ > ak and the least common multiple of ai and aj does not exceed n for all i and j. Prove that iai £ n for i = 1, 2, ¼, k.
Solution 1. The result can be established by induction. It clearly holds when i = 1. Suppose that it holds for 1 £ i £ m, so that, in particular mam £ n. The least common multiple is equal to bam+1 = cam for some positive integers b and c with c < b. If b ³ m+1, then (m + 1)am+1 £ bam+1 £ n by hypothesis.

Assume that b £ m. Then


(m + 1)am+1
= (m+1)c
b
 am £ (m+1)cn
bm
= æ
ç
è
m+1
m
ö
÷
ø
æ
ç
è
c
b
ö
÷
ø
n £ æ
ç
è
m+1
m
ö
÷
ø
æ
ç
è
b-1
b
ö
÷
ø
n
= æ
ç
è
1 - 1
m
ö
÷
ø
æ
ç
è
1 - 1
b
ö
÷
ø
n £ æ
ç
è
1 + 1
m
ö
÷
ø
æ
ç
è
1 - 1
m
ö
÷
ø
n = æ
ç
è
1 - 1
m2
ö
÷
ø
n < n
as desired. The result now follows.

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)am £ n, then the desired result for i = m + 1 follows from am+1 > am. On the other hand, suppose that (m+1)am > n. With bam+1 = cam the least common multiple of am and am+1, we have that (m+1)am > cam, so that


am+1 = c
b
am £ c
c+1
am £ m
m+1
am £ n
m+1
and the result follows.


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) £ x2 for 0 £ x £ 1.
Comment. Begin with a sketch. The graph of the function is like a bow on top of a bowstring along the line y = x. As x increases, the slope of the chord from the origin to (x, f(x)) decreases. The solution begins with an analytic verification of this fact, using the definition of concavity.

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


f(v) ³ vf(u) + (u - v)f(0)
u
= vf(u)
u
 .
When (u, v) = (1, x), this yields f(x) ³ x, so that x = g(f(x)) ³ g(x) (since g(x) is an increasing function). Let (u, v) = (x, g(x)) to obtain, for x ¹ 0 that


x = f(g(x)) ³ g(x)f(x)
x
 .
It is straightforward to verify now that f(x)g(x) £ x2 for all x Î [0, 1].

Comment. A special case is that f(x) = xk for 0 < k < 1, so that g(x) = x1/k. Then f(x)g(x) = xk + (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).
Solution 1. Analysis. Let AD meet the line through B parallel to AC in T. Then ÐBTA = ÐTAC = ÐTAB, so that |BT | = |AB | = c. By similar triangles, we have that |DT | = ic/b so that |AT | = i(b+c)/b.

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 1. Let O be the common centre of the circumscribed and inscribed spheres of the tetrahedron ABCD. The plane BCO bisects the dihedral angle formed by the planes BCD and BCA, so that the circles determined by BCD and BCA in these planes must be congruent. Thus, ÐBAC = ÐBDC = a, say. Similarly, we find that ÐABC = ÐADC = b, ÐABC = ÐADC = g, ÐACB = ÐADB = f, ÐBAD = ÐBCD = y, and ÐBAD = ÐBCD = w. From the sum of angles of various triangles, we find that b+ g = y+ w, a+ g = f+ w and a+ b = y+ f, whence a = f, b = y, g = w. >From this, we see that all the triangles are similar, and congruence follows from the fact that each pair of triangles have corresponding sides in common.

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 | = Ö[(R2 - r2)]. Similarly, |SB | = |SC | = Ö[(R2 - r2)], so that S is the centre of a circle with radius Ö[(R2 - r2)] 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


ÐABS + ÐACS = 90° - ÐBCS = 90° - ÐBCP = ÐBDP + ÐCDP
and


ÐABT + ÐBDT = 90° - ÐDAT = 90° - ÐDAQ = ÐACQ + ÐDCQ .
Since ÐABS = ÐABT, ÐACS = ÐACQ, ÐBDP = ÐBDT and ÐCDP = ÐDCQ, it follows that ÐABS - ÐCDP = ±(ÐACS - ÐBDP) = 0° so ÐABC = ÐBCD.

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