Advanced book on Mathematics Olympiad

Combinatorics and Probability 771

This number is equal to

m^1989 −m^663 −m^153 −m^117 +m^51 +m^39 +m^9 −m^3 ,

since the−1’s in the formula for the cardinalities of theUn’s cancel out.
(Chinese Mathematical Olympiad, 1989)

904.Here we apply a “multiplicative’’ inclusion–exclusion formula for computing the
least common multiple of several integers, which states that the least common multiple
[x 1 ,x 2 ,...,xn]of the numbersx 1 ,x 2 ,...,xnis equal to

x 1 x 2 ···xn

1

(x 1 ,x 2 )(x 1 ,x 3 )···(xn− 1 ,xn)

(x 1 ,x 2 ,x 3 )···(xn− 2 ,xn− 1 ,xn)···.

For three numbers, this formula reads

[a, b, c]=abc

1

(a, b)(b, c)(a, c)

(a,b,c),

while for two numbers, it reads

[a, b]=ab

1

(a, b)

.

Let us combine the two. Square the first formula; then substitute the productsab,bc,
andcausing the second. In detail,

[a, b, c]^2 =ab·bc·ca

1

(a, b)^2 (b, c)^2 (c, a)^2

(a,b,c)^2

=[a, b][b, c][c, a](a, b)(b, c)(c, a)

1

(a, b)^2 (b, c)^2 (c, a)^2

(a,b,c)^2

=[a, b][b, c][c, a]

(a,b,c)^2

(a, b)(b, c)(c, a)

.

The identity follows.

905.We solve the problem for the general case of a rectangular solid of widthw, length
l, and heighth, wherew, l, andhare positive integers. Orient the solid in space so that
one vertex is atO=( 0 , 0 , 0 )and the opposite vertex is atA=(w,l,h). ThenOAis
the diagonal of the solid.
The diagonal is transversal to the planes determined by the faces of the small cubes, so
each time it meets a face, edge, or vertex, it leaves the interior of one cube and enters the
interior of another. Counting by the number of interiors of small cubes that the diagonal
leaves, we find that the number of interiors thatOAintersects is equal to the number of
points onOAhaving at least one integer coordinate.