18.
A34 PROBLEMS #5
51. [1] A person buys a 30-year $100, 000 mortgage at an annual rate of
8%. What is his or her monthly payment?
52. (a) [1] Person A chooses an integer between 0 and 211 − 1, inclusive.
Person B tries to guess A’s number by asking yes-no questions.
What is the minimum number of questions needed to guarantee
that B finds A’s number? Can the questions all be chosen in
advance in an elegant way?
(b) [2.5] What if A is allowed to lie at most once?
53. [1] Let M be an n×n symmetric matrix such that each row and column
is a permutation of 1, 2, . . . , n. (“Symmetric” means that the entry in
row i and column j is the same as the entry in row j and column i.) If
n is odd, then show that every number 1, 2, . . . , n appears exactly once
on the main diagonal. For instance,
1 2 3 4 5
2 4 1 5 3
3 1 5 2 4
4 5 2 3 1
5 3 4 1 2
54. [1] Find all 10 digit numbers a0 a1 · · · a9 such that ai is the number of
digits equal to i, for all 0 ≤ i ≤ 9.
55. [1] Two circles of radius one pass through each other’s centers. What
is the area of their intersection?
'$
'$
&%
&%
56. (a) [2] Given any 1000 points in the plane, show that there is a circle
which contains exactly 500 of the points in its interior, and none
on its circumference.
1
(b) [3] Given 1001 points in the plane, no three collinear and no four
concyclic (i.e., no four on a circle), show that that there are exactly
250,000 circles with three of the points on the circumference, 499
points inside, and 499 points outside.
57. (a) [2.5] Let n be an integer, and suppose that n4 + n3 + n2 + n + 1 is
divisible by k. Show that either k or k − 1 is divisible by 5. Hint.
First show that one may assume that k is prime. Use Fermat’s
theorem for the prime k, which states that if m is not divisible by
k, then mk−1 − 1 is divisible by k. Try to avoid more sophisticated
tools.
(b) [2] Deduce that there are infinitely many primes of the form 5j +1.
58. [2] A cylindrical hole is drilled straight through and all the way through
the center of a sphere. After the hole is drilled, its length is six inches.
What is the volume that remains?
59. [2.5] Let T be a triangle. Erect an equilateral triangle on each side of T
(facing outwards). Show that the centers of these equilateral triangles
form the vertices of an equilateral triangle.
60. [5] Define a sequence X0 , X1 , . . . of rational numbers by X0 = 2 and
Xn+1 = Xn − X1n for n ≥ 0. Is the sequence bounded?
2
61. Let B = Z × Z, regarded as an infinite chessboard. (Here Z denotes
the set of integers.) Suppose that counters are placed on some subset
of the points of B. A counter can jump over another counter one
step vertically or horizontally to an empty point, and then remove the
counter that was jumped over. Given n > 0, let f (n) denote the least
number of counters that can be placed on B such that all their y-
coordinates are ≤ 0, and such that by some sequence of jumps it is
possible for a counter to reach a point with y-coordinate equal to n.
For instance, f (1) = 2, as shown by the following diagram.
y=0 s
Similarly f (2) = 4, as shown by:
y=0 s s s
(a) [2] Show that f (3) = 8 (or at least that f (3) ≤ 8 by constructing
a suitable example).
(b) [2.5] Show that f (4) = 20 (or at least that f (4) ≤ 20).
3
(c) [3] Find an upper bound for f (5).
62. [3.5] Generalize Problem 12 to n dimensions as follows. Show that there
exist n + 1 lattice points (i.e., points with integer coordinates) in Rn
such that any two of them are the same distance apart if and only if n
satisfies the following conditions:
(a) If n is even, then n + 1 is a square.
(b) If n ≡ 3 (mod 4), then it is always possible.
(c) If n ≡ 1 (mod 4), then n+1 is a sum of two squares (of nonnegative
integers). The well-known condition for this is that if n + 1 =
pa11 · · · par r is the factorization of n + 1 into prime powers, then ai
is even whenever pi ≡ 3(mod 4).
63. [5+] Let Hn = nj=1 1/j. Show that for all n ≥ 1,
P
X
d ≤ Hn + (log Hn )eHn .
d|n