文档介绍：Mathematics Olympiad Coachs Seminar, Zhuhai, China 1
03/23/2004
Number Theory
1. Prove that for every positive integer n there exists an n-digit number divisible by 5n all of whose
digits are odd.
2. Determine all finite nonempty sets S of positive integers satisfying
i + j
is an element of S for all i, j in S,
gcd(i, j)
where gcd(i, j) is the mon divisor of i and j.
3. Suppose that the set {1, 2, · · · , 1998} has been partitioned into disjoint pairs {ai, bi} (1 ≤ i ≤ 999)
so that for all i, |ai − bi| equals 1 or 6. Prove that the sum
|a1 − b1| + |a2 − b2| + · · · + |a999 − b999|
ends in the digit 9.
Solution: Let k denote the number of pairs {ai, bi} with |ai − bi| = 6. Then the sum in question
is k · 6 + (999 − k) · 1 = 999 + 5k, which ends in 9 provided k is even. Hence it suffices to show that
k is even.
Write k = kodd +keven, where kodd (resp. keven) is equal to the number of pairs {ai, bi} with ai, bi both
odd (resp. even). Since there are as many even numbers as odd numbers between 1 and 1998, and
since each pair {ai, bi} with |ai −bi| = 1 contains one number of each type, we must have kodd = keven.
Hence k = kodd + keven is even as claimed.
4. For a real number x, let bxc denote the largest integer that is less than or equal to x. Prove that
¹ º
(n − 1)!
n(n + 1)
is even for every positive integer n.
5. Let p1, p2, p3, . . . be the prime numbers listed in increasing order, and let x0 be a real number between
0 and 1. For positive integer k, define
½ ¾
pk
xk = 0 if xk−1 = 0, if xk−1 6= 0,
xk−1
where {x} = x − bxc denotes the fractional part of x. Find, with proof, all x0 satisfying 0 < x0 < 1
for which the sequence x0, x1, x2, . . . eventually es 0.
Solution: The sequence eventually es 0 if and only if x0 is a rational number.
First we prove that, for k ≥ 1, every rational term xk has a rational predecessor xk−1. Suppose xk is
rational. If xk = 0 then either xk−1 = 0 or pk/xk−1 is a positive