Chris Street Solved Putnam Exam practice problems

Problem, 1932 A-2. Determine all polynomials P (x) such that P (x^{2} + 1) = (P (x))^{2} + 1 and P (0) = 0.

Solution. The only such polynomial is x, the identity polynomial.

Proof. Let P (x) be such a polynomial.

Define the inductive sequence i_{0} = 0, i_{n} = i_{n−1}^{2} + 1. We make two observations about this sequence - first, that it is strictly increasing and therefore the i_{k}’s are distinct. Secondly, for all j, P (i_{j}) = i_{j}. This is easily shown by a basic induction: P (i_{0}) = P (0) = 0, by hypothesis, and if P (i_{m}) = i_{m}, then P (i_{m+1}) = P (i_{m}^{2} + 1) = P (i_{m})^{2} + 1 = i_{m}^{2} + 1 = i_{m+1}.

Now, consider the polynomial Q(x) = P (x)−x. Let n = deg Q(x). Suppose n ≥ 1. Then i_{0}, i_{1} ⋯ i_{n} are (n+1) distinct zeros of Q(x). This is a contradiction of the fundamental theorem of algebra.

Thus n = 0, and Q(x) is a constant polynomial. Since we know Q(0) = P (0) − 0 = 0, it follows that Q(x) is the polynomial identically equal to zero, and the claim is established. ■

Problem, 1977 A-4. For 0 < x < 1, express

∑_{n=0}^{∞} \frac{x^{2^{n}}}{1 − x^{2^{n+1}}}

as a rational function of x.

Solution. It is f(x) = \frac{x}{1−x}.

Proof. We desire to find

lim_{k→∞} S_{k}

where

S_{k} = ∑_{n=0}^{k} \frac{x^{2^{n}}}{1 − x^{2^{n+1}}}

First, I desire to show that this sequence S converges. This is easily seen by the fact that, for 0 < x < 1,

S_{k} = ∑_{n=0}^{k} \frac{x^{2^{n}}}{1 − x^{2^{n+1}}} ≤ ∑_{n=1}^{2^{k}} \frac{x^{n}}{1 − x^{2n}} ≤ ∑_{n=1}^{2^{k}} \frac{x^{n}}{1 − x} = \frac{1}{1 − x} ∑_{n=1}^{2^{k}} x^{n} = \frac{1 − x^{2^{k}+1}}{(1 − x)^{2}} −\frac{1}{1 − x}.

and the fact that S_{k} is strictly increasing for 0 < x < 1. Now that I know that S converges, then I know that the subsequence T_{m} = S_{2m+1} also converges and to the same limit. I write

T_{m} = ∑_{n=0}^{m} \frac{x^{2^{2n}}}{1 − x^{2^{2n+1}}} + \frac{x^{2^{2n+1}}}{1 − x^{2^{2n+2}}}

= ∑_{n=0}^{m} \frac{x^{K}}{1 − x^{2K}} + \frac{x^{2K}}{1 − x^{4K}} , where K = 2^{2n}

= ∑_{n=0}^{m} \frac{x^{K}(1 + x^{2K}) + x^{2K}}{1 − x^{4K}}

= ∑_{n=0}^{m} \frac{x^{K} + x^{2K} + x^{3K}}{1 − x^{4K}}

= ∑_{n=0}^{m} \frac{1 + x^{K} + x^{2K} + x^{3K} − 1}{(1 + x^{K} + x^{2K} + x^{3K})(1 − x^{K})}

= ∑_{n=0}^{m} \frac{1}{1 − x^{K}} − \frac{1}{1 − x^{4K}} .

Substituting back K = 2^{2n}, we have

T_{m} = ∑_{n=0}^{m} \frac{1}{1 − x^{2^{2n}}} − \frac{1}{1 − x^{2^{2n+2}}} .

From this, we see that we have a telescoping sum, and thus

T_{m} = \frac{1}{1 − x} − \frac{1}{1 − x^{2^{2m+2}}} .

Taking the limit as m → ∞, we see that the second term goes to 1 (since 0 < x < 1), and thus we have

lim_{m→∞} T_{m} = lim_{k→∞} S_{k} = \frac{1}{1 − x} − 1 = \frac{x}{1 − x}.

■

Problem, B-1 1977. Evaluate the infinite product

∏_{n=2}^{∞} \frac{n^{3} − 1}{n^{3} + 1}.

Solution. Write

P_{m} = ∏_{n=2}^{m} \frac{n^{3} − 1}{n^{3} + 1} = ∏_{n=2}^{m} \frac{(n − 1)(n^{2} + n + 1)}{(n + 1)(n^{2} − n + 1)}.

We desire lim_{m→∞} P_{m}.

Now we are going to write the k’th term in the product as

\frac{a_{k}b_{k}}{c_{k}d_{k}} , where

a_{k} = k − 1, b_{k} = k^{2} + k + 1, c_{k} = k + 1, d_{k} = k^{2} − k + 1.

Notice that a_{k} = c_{k−2} and d_{k} = b_{k−1}. Thus

P_{m} = ∏_{n=2}^{m} \frac{n^{3} − 1}{n^{3} + 1} = \frac{a_{2}b_{2}}{c_{2}d_{2}} \frac{a_{3}b_{3}}{c_{3}d_{3}} \frac{a_{4}b_{4}}{c_{4}d_{4}} ⋯ \frac{a_{m−2}b_{m−2}}{c_{m−2}d_{m−2}} \frac{a_{m−1}b_{m−1}}{c_{m−1}d_{m−1}} \frac{a_{m}b_{m}}{c_{m}d_{m}}

= \frac{a_{2}b_{2}}{c_{2}d_{2}} \frac{a_{3}b_{3}}{c_{3}b_{2}} \frac{c_{2}b_{4}}{c_{4}b_{3}} ⋯ \frac{c_{m−4}b_{m−2}}{c_{m−2}b_{m−3}} \frac{c_{m−3}b_{m−1}}{c_{m−1}b_{m−2}} \frac{c_{m−2}b_{m}}{c_{m}b_{m−1}}

= \frac{a_{2}a_{3}b_{m}}{d_{2}c_{m−1}c_{m}}

= \frac{2}{3} \frac{m^{2} + m + 1}{m^{2} + m}

Therefore lim_{m→∞} P_{m} = lim_{m→∞} \frac{2}{3} \frac{m^{2}+m+1}{m^{2}+m} = \frac{2}{3}. ■

Problem, B-5 1968. Let p be a prime number. Let J_{p} be the set of all 2 × 2

matrices ( \begin{matrix}a & b \\ c & d \end{matrix} ) whose entries are chosen from the set \{0, 1, 2, ⋯, p − 1\}

and which satisfy the conditions a + d ≡ 1 mod p and ad − bc ≡ 0 mod p. Determine how many members J_{p} has.

Solution. I do my work in the field Z_{p}, of integers mod p. We desire to

count all matrices ( \begin{matrix}a & b \\ c & d \end{matrix} ), a, b, c, d ∈ Z_{p}, a + d = 1, ad = bc.

We fix a. This forces d = 1 − a. Our second equation becomes a(a − 1) = bc. Now, how many solutions does this equation have?

If a(a − 1) = 0, then either a = 0 or a = 1. In either case, the solutions are b = 0 or c = 0, which yields 2p − 1 solutions.

If a(a − 1) ≠ 0, then bc = m with m ≠ 0. Since Z_{p} is cyclic under + of order p, ∀c ≠ 0 ∈ Z_{p} ∃ exactly one b ∈ Z_{p} s.t. bc = m. This gives a total of p − 1 solutions.

Thus, all in all, there are 2(2p − 1) + (p − 2)(p − 1) = p^{2} + p solutions, and so |J_{p}| = p^{2} + p. ■

Problem, A-1 1965. At a party, assume that no boy dances with every girl but each girl dances with at least one boy. Prove that there are two couples gb and g′b′ which dance, whereas b does not dance with g′ nor does g dance with b′.

Solution. Let b be the boy that dances with the maximal number of girls. (We are here assuming a finite dance floor.) Let g′ be a girl that does not dance with b. Let b′ be a boy that g′ does dance with.

Now, there exists a girl g that does dance with b, but does not dance with b′. For if not, b′ dances with at least one more girl than b does, a contradiction to our assumption.

Now we have found the b, g, b′, g′ that solve the problem. ■

Problem, A-1 1983. How many positive integers n are there such that n is an exact divisor of at least one of the numbers 10^{40}, 20^{30}?

Solution. Call A the set of positive divisors of 10^{40}, and B the set of positive divisors of 20^{30}.

10^{40} = 2^{40}5^{40}, so all divisors have the form 2^{i}5^{j}, with i and j running independently from 0 to 40. Thus |A| = 41 × 41 = 1, 681.

20^{30} = 2^{60}5^{30}, and again all divisors have the form 2^{i}5^{j}, with i from 0 to 61 and j from 0 to 31. Thus |B| = 61 × 31 = 1, 891.

Now, to determine |A ⋂ B|, we look at the divisors of gcd(10^{40}, 20^{30}) = 2^{40}5^{30}. This has 41 × 31 = 1, 271 divisors, thus |A ⋂ B| = 1, 271.

So the desired quantity, |A ⋃ B|, is |A| + |B| − |A ⋂ B| = 1, 681 + 1, 891 − 1, 271 = 2, 301. ■

Problem, A-3 1967. Consider polynomial forms ax^{2} + bx + c with integer coefficients which have two distinct zeros in the open interval 0 < x < 1. Exhibit with a proof the least positive integer value of a for which such a polynomial exists.

Solution. What we want is

0 < −b + \sqrt{b^{2} − 4ac} < 2a, 0 < −b − \sqrt{b^{2} − 4ac} < 2a.

Manipulating the inequalities gives

\begin{matrix}−2a < & 2\sqrt{b^{2} − 4ac} < 2a \\ −a < & \sqrt{b^{2} − 4ac} < a \\ 0 < & \sqrt{b^{2} − 4ac} < a \\ 0 < & b^{2} − 4ac < a^{2}. \end{matrix}

Also we want

\frac{−b + \sqrt{b^{2} − 4ac}}{2a} ≠ 1,

thus

b^{2} − 4ac ≠ (2a + b)^{2}.

We make note that we desire c ≠ 0 to guarantee no root at 0.

We write ax^{2} + bx + c = ax^{2} − a(r_{1} + r_{2})x + c, where r_{1}, r_{2} are our roots. We have 0 < r_{1} + r_{2} < 2. Also r_{1} + r_{2} is rational (it is \frac{−b}{2a}.) Thus say r_{1} + r_{2} = \frac{p}{q}, a fraction in lowest terms. b is an integer, so q|ap, thus q|a since (p, q) = 1.

Reiterating, we have formulated the following constraints on the problem:

\begin{matrix}0 < & a^{2} (\frac{p}{q})^{2} − 4ac < a^{2}, \\ a^{2} (\frac{p}{q})^{2} − 4ac & ≠ (2a − a\frac{p}{q})^{2}, \\ (p, q) = 1, 0 < & \frac{p}{q} < 2, q|a, c ≠ 0. \end{matrix}

where I have back-substituted b = −a\frac{p}{q} into our previous inequalities.

This greatly limits the number of possibilites for (a, q, p) solution triples. For a from 1 to 4, the possibilities are (1, 1, 1), (2, 1, 1), (2, 2, 1), (2, 2, 3), (3, 1, 1), (3, 3, 1), (3, 3, 2), (3, 3, 4), (3, 3, 5), (4, 1, 1), (4, 2, 1), (4, 2, 3), (4, 4, 1), (4, 4, 3), (4, 4, 5), (4, 4, 7). We can limit these further since if (a, q, p) does not satisfy the conditions, then (b, q, p), b > a will not either. But none of the cases satisfy all of the constraints.

However, when a = 5, the polynomial 5x^{2} −5x+1 has roots (\frac{1}{2} ± \frac{\sqrt{5}}{10}), which are both in (0, 1). Hence 5 is the smallest such a that works. ■

Problem, B-2 1965. Suppose n players play a round-robin tournament (ie, every player plays every other player exactly once.) Each game results in a win or loss for a player: there are no ties. Let w_{k} be the number of wins by player k, and let l_{k} be the number of losses by player k. Show that

∑_{i=1}^{n} w_{i}^{2} = ∑_{i=1}^{n} l_{i}^{2}

Proof. Let G be the total number of games played (this number is ( \begin{matrix}n \\ 2 \end{matrix} ),

of course, but that is not important here.) The number of games played by each player is (n − 1), so we can write that, for all i, w_{i} = (n − 1) − l_{i}. Then we have

∑_{i=1}^{n} w_{i}^{2} = ∑_{i=1}^{n} w_{i}((n − 1) − l_{i})

= (n − 1) ∑_{i=1}^{n} w_{i} − ∑_{i=1}^{n} w_{i}l_{i}

= (n − 1)G − ∑_{i=1}^{n} w_{i}l_{i}

= (n − 1) ∑_{i=1}^{n} l_{i} − ∑_{i=1}^{n} l_{i}w_{i}

= ∑_{i=1}^{n} l_{i}((n − 1) − w_{i}) = ∑_{i=1}^{n} l_{i}^{2}.

■

Problem, B-4 1967. We have a hallway with n lockers, labeled 1 through n. The lockers have two possible states, open and closed. Initially they are all closed. The first kid walking down the hallway flips every locker to the opposite state (that is, he opens them all). The 2nd kid flips the locker door 2 and every other locker door after that. The kth kid flips the state of every kth locker door. After infinitely many kids have done this, which locker doors are closed and which are open?

Solution. Take locker number n. It began closed, and will be flipped σ(n) times, where σ(n) is the number of positive integer divisors of n. It will finish up closed if and only if σ(n) is an even number, and will finish up open if and only if σ(n) is odd.

Suppose n has the prime factorization p_{1}^{i_{1}}p_{2}^{i_{2}} ⋯ p_{k}^{i_{k}}, the p_{m}’s prime. Then

σ(n) = ∏_{m=1}^{k}(i_{m} + 1).

Notice that σ(n) is odd if and only if each of the i_{m}’s is even. Thus, σ(n) is odd if and only if n is a perfect square. Therefore, the open lockers will be exactly those whose number is a perfect square: that is, the 1st, 4th, 9th, etc. All other doors will be closed. ■

Alternative proof of fact used above. (Without using unique factorization) The divisors of n come in pairs: that is, if p is an integer divisor of n, then n/p is an integer divisor of n. Hence, the number of divisors for a given n will be even unless for some divisor p, p = n/p - which is to say, n = p^{2}. ■

Problem, A-1 1977. Consider all lines that meet the graph of

y = 2x^{4} + 7x^{3} + 3x − 5

in four distinct points, say (x_{i}, y_{i}), i = 1, 2, 3, 4. Show that

\frac{x_{1} + x_{2} + x_{3} + x_{4}}{4}

is independent of the line, and find its value.

Solution. Remember that a polynomial with real coefficients may be written as

c_{n}x^{n} + c_{n−1}x^{n−1} + ⋯ + c_{1}x + c_{0} = c_{n}(x − r_{1})(x − r_{2}) ⋯ (x − r_{n−1})(x − r_{n}),

where r_{1}, r_{2}, ⋯ r_{n} are the roots of the polynomial in ℂ, with multiplicities. Multiplying out and equating coefficients gives us the useful identity

c_{n−1} = c_{n}(−r_{1} − r_{2} − ⋯ − r_{n−1} − r_{n}).

To apply this fact to our problem, let’s call the line which intersects the polynomial in question L(x) = mx + b (we know it has a finite slope m, since no vertical line will meet the function in more than one place.) Now notice that x_{1}, x_{2}, x_{3}, x_{4} are roots of the polynomial y −L(x) = 2x^{4} +7x^{3} +(3−m)x−5−b. Since this polynomial is of degree 4, and each of x_{1} ⋯ x_{4} are distinct, these are all of the roots.

Thus, we have

7 = 2(−x_{1} − x_{2} − x_{3} − x_{4})

which gives that

\frac{x_{1} + x_{2} + x_{3} + x_{4}}{4} = −\frac{7}{8}.

Notice that this value is entirely independent of the values of m or b. ■

Problem, A-1 1978. Let A be any set of 20 distinct integers chosen from the arithmetic progression 1, 4, 7, ⋯, 100. Prove that there must be two distinct integers in A whose sum is 104.

Solution. Consider the disjoint sets A_{1} = {1}, A_{2} = {52}, A_{3} = {4, 100}, A_{4} = {7, 97}, A_{5} = {10, 94}, ⋯, A_{17} = {46, 58}, A_{18} = {49, 55}. The union of these sets gives you the complete geometric progression. Also notice that the sum of the elements in each of A_{3}, A_{4} ⋯ A_{18} is 104.

At most 2 elements of A can be chosen from the sets A_{1} and A_{2}. Hence at least 18 are chosen from the 16 different sets A_{3}, A_{4} ⋯ A_{18}. Then there is a set A_{j}, j ≥ 3, such that both elements of A_{j} are chosen. (Indeed, there are at least two such sets, but we only need one.) But these two elements add to 104. ■

Problem, A-2 1988. A not uncommon calculus mistake is to believe that the product rule for derivatives says that (fg)′ = f′g′. If f(x) = e^{x^{2}}, determine, with proof, whether there exists an open interval (a, b) and a non-zero function g defined on (a, b) such that the wrong product rule is true for x in (a, b).

Solution. Let g(x) = e^{x}(2x − 1)^{1/2}, differentiable on the open interval (\frac{1}{2}, ∞). Now

\begin{aligned}f(x) & = e^{x^{2}} \\ g(x) & = e^{x}(2x − 1)^{1/2} \\ f′(x) & = 2xe^{x^{2}} \\ g′(x) & = e^{x}(2x − 1)^{−1/2} + e^{x}(2x − 1)^{1/2} \end{aligned}

and

(f(x)g(x))′ = e^{x^{2}}(e^{x}(2x − 1)^{−1/2} + e^{x}(2x − 1)^{1/2}) + 2xe^{x^{2}}e^{x}(2x − 1)^{1/2}
= e^{x^{2}}e^{x}(2x − 1)^{−1/2} − (1 − 2x)e^{x^{2}}e^{x}(2x − 1)^{−1/2} + 2xe^{x^{2}}e^{x}(2x − 1)^{1/2}
= 2xe^{x^{2}}e^{x}(2x − 1)^{−1/2} + 2xe^{x^{2}}e^{x}(2x − 1)^{1/2}.

This is equal to

\begin{aligned}f′(x)g′(x) & = 2xe^{x^{2}}(e^{x}(2x − 1)^{−1/2} + e^{x}(2x − 1)^{1/2}) \\ & = 2xe^{x^{2}}e^{x}(2x − 1)^{−1/2} + 2xe^{x^{2}}e^{x}(2x − 1)^{1/2} \end{aligned}

Hence we have found a g(x) that satisfies the requirements, and we are done. ■

The sketch work. The answer was of course not pulled out of ether, but this work was done on scratch paper to determine the correct answer.

What we want is

[e^{x^{2}}g(x)]′ = [e^{x^{2}}]′g′(x),

or

\begin{aligned}2xe^{x^{2}}g(x) + e^{x^{2}}g′(x) & = 2xe^{x^{2}}g′(x) \\ 2xe^{x^{2}}g(x) + e^{x^{2}}g′(x) − 2xe^{x^{2}}g′(x) & = 0 \\ e^{x^{2}}(2xg(x) + (1 − 2x)g′(x)) & = 0 \end{aligned}

Since e^{x^{2}} is always positive for real x, this equation is only true if

2xg(x) + (1 − 2x)g′(x) = 0.

Solving for g′(x) yields

g′(x) = (1 + \frac{1}{2x − 1}) g(x).

This is a simple differential equation; notice that if G(x) is an antiderivative of (1 + \frac{1}{2x−1}), then a solution is

g(x) = e^{G(X)}.

An antiderivative of (1 + \frac{1}{2x−1}) is x + \frac{1}{2} log(2x − 1). Thus a solution is

g(x) = e^{x+ \frac{1}{2} log(2x+1)} = e^{x}(2x − 1)^{1/2}.

Now we are ready to pull this function out of our hat to solve the problem! ■

Problem, A-2, 1987. The sequence

{1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 2, 0, ⋯ }

is obtained by writing the positive integers in order. If the 10^{n}’th digit in this sequence occurs in the part of the sequence in which the m-digit numbers are placed, define f(n) to be m. For example f(2) = 2 because the 100th digit enters the sequence in the placement of the two-digit integer 55. Find, with proof, f(1987).

Solution. I will define the function g(n) as follows: g(n) gives the number of elements in the sequence after the number n has been placed in the sequence. For example, g(1) = 1, g(9) = 9, g(10) = 11, g(101) = 195.

To find a formula for g(n) and to solve the problem, we will write, instead of g(n), g(10^{k} + l), where 10^{k} is the largest power of 10 less than or equal to n, and l is n − 10^{k}. Then, if k satisfies g(10^{k} + l) = 10^{1987}, then f(1987) = k + 1.

To write a closed form expression for g(10^{k} + l), we notice that 10^{k} + l of the numbers from 1 to 10^{k} + l have at least 1 digit. 10^{k} + l − 9 of the numbers from 1 to 10^{k} + 1 have at least 2 digits. 10^{k} + l − 99 of the numbers from 1 to 10^{k} + 1 have at least 3 digits, and so on. Thus an expression for g(10^{k} + 1) is

g(10^{k} + l) = (k + 1)l + ∑_{i=0}^{k}(10^{k} − 10^{i} + 1)

which, evaluating the geometric sum and simplifying, gives

g(10^{k} + l) = \frac{9(k + 1)10^{k} − 10^{k+1} + 1}{9} + (k + 1)(l + 1).

Now we solve

\begin{aligned}10^{1987} & = \frac{9(k + 1)10^{k} − 10^{k+1} + 1}{9} + (k + 1)(l + 1) \\ 10^{1987} & = (k + 1)10^{k} + (k + 1)(l + 1) + \frac{1 − 10^{k}}{9} \end{aligned}

Now set k = 1983. This gives on the right side

1.984 × 10^{1986} + 1984(l + 1) + \frac{1}{9} − \frac{10}{9} × 10^{1982}

Setting this equal to 10^{1987}, we find that

8.016 × 10^{1986} + \frac{10}{9}10^{1982} − \frac{1}{9} = 1984(l + 1).

Now we see that 1984(l + 1) has to equal approximately 8.016 × 10^{1986} to make the equation true. Since l may range from 0 to 9 × 10^{1986} − 1, we see that l can be chosen appropriately. Thus k = 1983, and f(1987) = 1984. ■

Problem, A-5 1988. Prove that there exists a unique function from the set ℝ^{+} of positive real numbers to ℝ^{+} such that

f(f(x)) = 6x − f(x)

and f(x) > 0 for all x > 0.

Solution. First, notice that f(x) = 2x is a solution: certainly 2x > 0 for x > 0, and f(f(x)) = 4x = 6x − 2x = 6x − f(x).

Now we must prove that no other function works.

So suppose that another function, g(x), satisfies these conditions. Suppose that, at x = k, g(k) = 2k + c. Now, what is g^{(n)}(k), where g^{(n)} is the function iterated n times (ie, g^{(1)}(k) = g(k), g^{(2)}(k) = g(g(k)), etc.)? I claim that g^{(n)}(k) = a_{n}k + b_{n}c, where a_{n} and b_{n} are sequences defined by

\begin{matrix}a_{0} = 1, & a_{1} = 2 \\ b_{0} = 0, & b_{1} = 1 \\ a_{n} = 6a_{n−2} − a_{n−1}, & b_{2} = 6b_{n−2} − b_{n−1}, for n ≥ 2 \end{matrix}

This is easily proved by an induction using the formula g^{(n)} = 6g^{(n−2)} − g^{(n−1)}. Similarly, it is easy to show that a_{i} = 2^{i} for all i. Now, for all odd n ≥ 1, b_{n} > 0, and for all even n ≥ 2, b_{n} < 0. To show this, note that b_{1} = 1, b_{2} = −1. Now suppose that this holds for b_{m}, b_{m+1}, m some odd number greater than 1. Then, b_{m+2} = 6b_{m} − b_{m+1} - a positive minus a negative, which is positive. Similarly, b_{m+3} = 6b_{m+1} − b_{m+2} - a negative minus a positive. Thus, the result is established.

Along with this, note that |b_{n}| > 6|b_{n−2}|. Since b_{1} = 1 and b_{2} = −1, b_{2m+1} > 6^{m} and b_{2m+2} < −(6^{m}). Thus

lim_{n→∞} \frac{−a_{n}}{b_{n}} = lim_{n→∞} − (\frac{2}{\sqrt{6}})^{n} = 0.

Now, since a_{n}k + b_{n}c > 0, we have c > (−a_{n})/b_{n}k for b_{n} positive, and c < (−a_{n})/b_{n}k for b_{n} negative. We have seen that (−a_{n})/b_{n} → 0 as n → ∞, thus c is bounded above by a sequence whose limit is 0, and bounded below by a sequence whose limit is zero, and so must equal 0 itself. Thus g(x) = f(x), and this proves the uniqueness of the solution. ■

Problem, B-2 1966. Prove that among any ten consecutive integers at least one is relatively prime to each of the others.

Solution. Call the numbers n, n + 1, n + 2, ⋯, n + 9. Suppose that the statement is not true: that is, for every n + i, 0 ≤ i ≤ 9, there exists a n + j, 0 ≤ j ≤ 9, such that (n + i, n + j) ≠ 1 and i ≠ j.

Then n+i and n+j share a common prime divisor, p. Let n+i = pm_{1}, n+j = pm_{2}. Then |(n + i) − (n + j)| = |i − j| = |p(m_{1} − m_{2})|. Since |i − j| ≤ 9, p is one of 2, 3, 5, or 7.

Therefore, it follows that every element of {n, n + 1, ⋯, n + 9} is divisible by at least one of 2, 3, 5, or 7.

Let M_{a} be the subset of {n, n + 1, ⋯, n + 9} containing all the members divisible by a.

Then |M_{2}| ≤ 5, |M_{3}| ≤ 4, |M_{5}| ≤ 2, |M_{7}| ≤ 2.

Notice that |M_{6}| ≥ 1, and that if |M_{3}| = 4, then |M_{6}| = 2. (2 of the 4 divisors of 3 must be even.) Thus |M_{3}| − |M_{6}| ≤ 2.

Also, if |M_{5}| = 2, then |M_{10}| = 1 (one of the divisors of 5 is even.) Thus |M_{5}| − |M_{10}| ≤ 1.

Similarly, if |M_{7}| = 2, then |M_{14}| = 1. Thus |M_{7}| − |M_{14}| ≤ 1.

Now this gives

|M_{2} ∪ M_{3} ∪ M_{5} ∪ M_{7}| ≤ |M_{2}| + (|M_{3}| − |M_{6}|) + (|M_{5}| − |M_{10}|) + (|M_{7}| − |M_{14}|).

But the quantity on the left is 10, and the quantity on the right is ≤ 5+2+1+1 = 9, thus we have a contradiction 10 ≤ 9. Therefore, it must be that for some n+i no such j exists, and thus this n + i is relatively prime to every other element of the set. ■

Problem, B-4 1960. Consider the arithmetic progression a, a + d, a + 2d ⋯, where a and d are positive integers. For any positive integer k, prove that the progression has either no exact kth powers, or infinitely many.

Solution. It suffices to prove that, if one kth power is in the progression, there exists a larger kth power in the progression.

Thus, suppose that j^{k} = a + id for some positive integers j, i. We will show that there exists an integer b > 0 and an integer m > 0 such that (j + b)^{k} = a + id + md.

Write

(j + b)^{k} = ∑_{q=0}^{k} ( \begin{matrix}k \\ q \end{matrix} ) j^{q}b^{k−q}

= j^{k} + ∑_{q=0}^{k−1} ( \begin{matrix}k \\ q \end{matrix} ) j^{q}b^{k−q}

= a + id + ∑_{q=0}^{k−1} ( \begin{matrix}k \\ q \end{matrix} ) j^{q}b^{k−q}

= a + id + b ∑_{q=0}^{k−1} ( \begin{matrix}k \\ q \end{matrix} ) j^{q}b^{k−q−1}

Now notice that if we set b = d, then we have

(j + d)^{k} = a + id + md

with m = ∑_{q=0}^{k−1} ( \begin{matrix}k \\ q \end{matrix} ) j^{q}d^{k−q−1}, the sum of positive integers and therefore a

positive integer itself, and we are done. ■

Problem, A-1 1961. The graph of the equation x^{y} = y^{x} in the first quadrant (i.e., the region where x > 0 and y > 0) consists of a straight line and a curve. Find the coordinates of the intersection point of the line and the curve.

Solution. Let y = cx, c > 0. Then we desire to find pairs (x, c) that satisfy

x^{cx} = (cx)^{x}.

These quantities are positive, so we can take logarithms. We write:

x^{cx} = (cx)^{x}
cx log x = x log(cx)
cx log x = x(log x + log c)
x(log x + log c − c log x) = 0.

Since x > 0, this is true iff

log x + log c − c log x = 0
(1 − c) log x = − log c.

Notice that if c = 1, the above equation becomes vacuous. This only says that c = 1 is a solution for any x, or equivalently an (x, y) pair satisfying x = y is a (trivial) solution to the problem. Here is our straight line set of solutions.

To continue, we suppose that c ≠ 1. Then it is proper to divide by (c − 1):

log x = \frac{log c}{c − 1}, c ≠ 1.

This is the equation of the solution curve, giving x in terms of c. By dividing by (c − 1), we eliminated the solution line and created a singular point at the intersection point. So now we want to find what the limiting value of x is as this curve approaches the c = 1 solution line. Hence we find

lim_{c→1} \frac{log c}{c − 1} = 1

by L’Hospital’s rule. Thus, at the intersection point, log x = 1, or x = e. Since this point is on the line y = x, y = e also, and so the intersection point is (e, e). ■

Problem, A-2 2001. You have coins C_{1}, C_{2}, ⋯, C_{n}. For each k, coin C_{k} is biased so that, when tossed, it has probability \frac{1}{2k+1} of falling heads. If the n coins are tossed, what is the probability that the number of heads is odd? Express the answer as a rational function of n.

Solution. Define O_{n} to be the probability that the number of heads for n coins is odd, and E_{n} the probability that the number of heads is even. Then we have the relations

O_{n} + E_{n} = 1,  for all n
O_{n} = \frac{1}{2n + 1}E_{n−1} + \frac{2n}{2n + 1}O_{n−1}, for n ≥ 2.

Rewriting the second equation using the first, we obtain

\begin{aligned}O_{n} & = \frac{1}{2n + 1}(1 − O_{n−1}) + \frac{2n}{2n + 1}O_{n−1} \\ O_{n} & = \frac{1}{2n + 1} + \frac{2n − 1}{2n + 1}O_{n+1}. \end{aligned}

Now I make the claim that O_{n} = \frac{n}{2n+1} for all n. We verify this by induction on n, the number of coins:

For n = 1 we can easily compute O_{1} = \frac{1}{3}, hence the claim is valid for this value of n. Assume that the claim is true for some m ≥ 1. Then, by our recurrence relation,

O_{m+1} = \frac{1}{2m + 3} + \frac{2m + 1}{2m + 3}O_{m}
O_{m+1} = \frac{1}{2m + 3} + \frac{2m + 1}{2m + 3} \frac{m}{2m + 1}, by inductive hypothesis,
O_{m+1} = \frac{1}{2m + 3} + \frac{m}{2m + 3} = \frac{m + 1}{2m + 3},

which has the desired form. This completes the induction and proves the claim.

Thus the desired probability, written as a rational function of n, is O_{n} = \frac{n}{2n+1}. ■

Problem, A-5 2001. Prove that there exist unique positive integers a, n such that

a^{n+1} − (a + 1)^{n} = 2001.

Solution. Any such a satisfies the polynomial

x^{n+1} − (x + 1)^{n} − 2001

which has constant coefficient −2002 and leading coefficient 1. Thus, by the Rational Root Theorem and the fact that a is a positive integer, a is a positive integer divisor of 2002 = 2 × 7 × 11 × 13.

Also, a ≠ 1001, since 1001^{n} ≡ 1 mod 10 for all n, and 1002^{n} is not divisible by 10 for any n - thus, 1001^{n} − 1002^{n−1} ≢ 1 mod 10 for all n.

Exactly the same observation shows that a ≠ 11, a ≠ 91, a ≠ 1.

Now a ≠ 14, since 14^{n} ≡ 2 mod 6 for odd n, and 14^{n} ≡ 4 mod 6 for even n > 0. 15^{n} ≡ 3 mod 6 for all n > 0. However, 2001 ≡ 3 mod 6. 2 − 3 ≢ 3 mod 6 and 4 − 3 ≢ 3 mod 6.

The situation mod 6 is the same for 26 and for 182, thus a ≠ 26, a ≠ 182. a ≠ 2, for if 2^{n+1} − 3^{n} = 2001 for some n > 0, then 2^{n+1} = 3(3^{n−1} + 667),

which cannot be since 3 does not divide any power of 2.

a ≠ 143, since 143^{n} ≡ 8 mod 9 for odd n and 143^{n} ≡ 1 mod 9 for even n. 144 ≡ 0 mod 9. However, 2001 ≡ 3 mod 9, and this is neither 8 nor 1.

a ≠ 154, since n = 1 is not a solution, 154^{n} ≡ 0 mod 8 for all n > 2, and 155^{n} ≡ 5, 1 mod 8 depending on the parity of n. 2001 ≡ 1 mod 8 and neither (0 − 1) nor (0 − 5) is congruent to 1 mod 8.

Similarly, considering 2002 and 2003 mod 8 yields a ≠ 2002.

a ≠ 77, since 77^{n} ≡ 1, 2 mod 3 depending on the parity of n, and 78^{n} ≡ 0 mod 3. However, 2001 ≡ 0 mod 3, and neither 1 nor 2 is congruent to 0 mod 3.

a ≠ 22, since 22^{n} ≡ 4 mod 12 for n > 1, and 23^{n} ≡ 1, 11 mod 12 depending on the parity of n. 2001 ≡ 9 mod 12 and neither (4 − 1) nor (4 − 11) = (4 + 1) are congruent to 9 mod 12.

a ≠ 7, since if n > 0 is even, 7^{n} ≡ 1 mod 12 and 8^{n−1} ≡ 8 mod 12. If n is odd, 7^{n} ≡ 7 mod 12 and 8^{n−1} ≡ 4 mod 12. 2001 ≡ 9 mod 12. In neither case is 7^{n+1} − 8^{n} ≡ 9 mod 12.

a ≠ 286, since 286^{n} ≡ 1 mod 15 for all n, and 287^{n} ≡ 1, 2, 4, 8 mod 15 depending on the value of n mod 4. 2001 ≡ 6 mod 15, and none of (1 − 1), (1 − 2), (1 − 4), (1 − 8) is congruent to 6 mod 15.

Thus we have accounted for all of the divisors of 2002 except 13. 13^{n+1} − 14^{n} ≡ 1 mod 10 if and only if n ≡ 2 mod 4. Also, 13^{n+1} − 14^{n} ≡ 10 mod 11 if and only if n ≡ 2 mod 11. Thus possible solutions are n = 2, 46, 90 · · ·. Sure enough, 13^{3} −14^{2} = 2001, and we know that a is unique. To show that no other n is a solution, we need only note that 14^{46} > 13^{47}. Of course, this is difficult to verify directly by hand, but may be proven by many methods of estimation. One (very easy) way to do it, using the fact that (1 + \frac{1}{n})^{n+1} > e for all n, is:

(\frac{14}{13})^{46} = ((1 + \frac{1}{13})^{14})^{3} (\frac{14}{13})^{4} > e^{3} > (\frac{5}{2})^{3} > 13.

Thus the value of n is unique as well, and the single solution in positive integers is

13^{3} − 14^{2} = 2001.

■

Problem, B-1, 2001. Let n be an even positive integer. Write the numbers 1, 2 ⋯, n^{2} in the squares of an n×n grid so that the kth row, from left to right, is

(k − 1)n + 1, (k − 1)n + 2, ..., (k − 1)n + n.

Color the squares of the grid so that half of the squares in each row and in each column are red and the other half are black (a checkerboard coloring is one possibility.) Prove that for each coloring, the sum of the numbers on the red squares is equal to the sum of the numbers on the black squares.

Solution. Let a valid coloring be given.

Define α_{ij} = −1 if the square in row i, column j is colored black, and α_{ij} = +1 if the square in row i, column j is colored red. Then the problem stated is equivalent to the following:

Show

∑_{i=1}^{n} ∑_{j=1}^{n} α_{ij}((i − 1)n + j) = 0,

where

∑_{i=1}^{n}α_{ij} = 0 for any j,

∑_{j=1}^{n}α_{ij} = 0 for any i.

To show this, we now simply evaluate the sum:

∑_{i=1}^{n} ∑_{j=1}^{n} α_{ij}((i − 1)n + j) = ∑_{i=1}^{n} ∑_{j=1}^{n} α_{ij}in − ∑_{i=1}^{n} ∑_{j=1}^{n} α_{ij}n + ∑_{i=1}^{n} ∑_{j=1}^{n} jα_{ij}

= n ∑_{i=1}^{n} i ∑_{j=1}^{n} α_{ij} − n ∑_{i=1}^{n} ∑_{j=1}^{n} α_{ij} + ∑_{j=1}^{n} j ∑_{i=1}^{n} α_{ij}

= n ∑_{i=1}^{n}(i × 0) − n ∑_{i=1}^{n} 0 + ∑_{j=1}^{n}(j × 0)

= 0,

and we are done. ■

Problem, B-3 2001. For any positive integer n let ⟨n⟩ denote the closest integer to \sqrt{n}. Evaluate

∑_{n=1}^{∞} \frac{2^{⟨n⟩} + 2^{−⟨n⟩}}{2^{n}} .

Solution. Suppose i is an integer such that k^{2} ≤ i ≤ (k + 1)^{2}, k an integer. Since (k + \frac{1}{2})^{2} = k^{2} + k + \frac{1}{4}, if i > k^{2} + k, then ⟨i⟩ = k + 1. Otherwise, ⟨i⟩ = k.

From this we see that the set of all integers i such that ⟨i⟩ = k is the set of i satisfying (k − 1)^{2} + (k − 1) + 1 ≤ i ≤ k^{2} + k, or k^{2} − k + 1 ≤ i ≤ k^{2} + k.

If we take the sum over just those i such that ⟨i⟩ = k, we get

∑_{i=k^{2}−k+1}^{k^{2}+k} \frac{2^{k} + 2^{−k}}{2^{i}} = (2^{k} + 2^{−k}) ∑_{i=k^{2}−k+1}^{k^{2}+k} (\frac{1}{2})^{i} .

This is a geometric series; evaluating we obtain:

(2^{k} + 2^{−k}) (\frac{1 − (\frac{1}{2})^{k^{2}+k+1}}{1 − \frac{1}{2}} − \frac{1 − (\frac{1}{2})^{k^{2}−k+1}}{1 − \frac{1}{2}} )

Simplifying we obtain:

2^{−k^{2}+2k} − 2^{−k^{2}−2k}.

Now the desired sum is:

∑_{k=1}^{∞}(2^{−k^{2}+2k} − 2^{−k^{2}−2k})

How do we evaluate this? All we need do is notice that −k^{2} − 2k = −(k + 2)^{2} + 2(k + 2), and thus the sum telescopes:

(2^{1} − 2^{−3}) + (2^{0} − 2^{−8}) + (2^{−3} − 2^{−15}) + (2^{−8} − 2^{−24}) ⋯

...and the only terms remaining in the sum as n → ∞ are 2^{0} + 2^{1} = 3. Thus the desired sum is 3. ■

Problem, A-3 1968. Prove that a list can be made of all the subsets of a finite set in such a way that

(i.) The empty set is first in the list,

(ii.) each subset occurs exactly once, and

(iii.) each subset in the list is obtained either by adding one element to the preceding subset or by deleting one element of the preceding subset.

Solution. For a set of n elements, the problem is equivalent to this one: can we write a list of all strings of length n on the alphabet {0, 1}, where each string occurs once and only once, the first string is the string of n zeroes, and each string in the list thereafter may be obtained from the previous one by toggling exactly one of the characters (that is, changing one 0 to a 1, or one 1 to a 0.)

To show how such a list is constructed, we will induct on n. If n = 1, then clearly the only viable list is 0, 1. Now suppose a list can be constructed for n = m, m ≥ 1. Then to construct a list for m + 1 objects do the following:

For the first half of the list, copy down the list for m elements, adding a 0 to the front of each element. For the second half of the list, copy down the list for m elements backwards, adding a 1 to the front of each element.

Does this list satisfy the requirements? The string of m + 1 zeroes is first on the list. Each possible string appears exactly once. From inductive hypothesis, each half of the list has the property that each successive element is obtained by changing exactly one of the characters. The only thing to prove is that this property holds between the last element of the first half and the first element of the second half. But clearly it does, since the first element of the second half is the last element of the first half with the leading 0 changed to a 1. Thus we have constructed a list which works, and by the induction we can do so for any n. ■

Problem, B-2 1961. Let a, b be given positive real numbers with a < b. If two points are selected at random from a straight line of length b, what is the probability that the distance between them is at least a?

Solution. Without loss of generality, we will assume that the straight line is the interval [0, b]. Suppose the two points p, q are at least distance a apart.

There are three cases: the first, p < a, in which q ∈ [p + a, b]. The total area in which q can fall is b − p − a.

The second is when a ≤ p ≤ b−a, in which either q ∈ [0, p−a] or q ∈ [p+a, b]. The total area is b − 2a.

The third case is when b − a < p, in which case q ∈ [0, p − a]. The total area here is p − a.

Call the event that p is as in the first case C_{1}, in the second case C_{2}, and in the third case C_{3}. Then the total probability is

P (C_{1})E(C_{1}) + P (C_{2})E(C_{2}) + P (C_{3})E(C_{3})

where E(C_{i}) is the expected probability of picking an acceptable q given p in case i. In terms of interval areas, this expression can be written as

\frac{a}{b} \frac{1}{a} ∫_{0}^{a} \frac{(b − p − a)}{b}dp + \frac{b − 2a}{b} \frac{1}{b − 2a} ∫_{a}^{b−a} \frac{(b − 2a)}{b}dp + \frac{a}{b} \frac{1}{a} ∫_{b−a}^{b} \frac{p − a}{b}dp.

which we simplify to

\frac{1}{b^{2}} ∫_{0}^{a}(b − p − a)dp + \frac{b − 2a}{b^{2}} ∫_{a}^{b−a} dp + \frac{1}{b^{2}} ∫_{b−a}^{b}(p − a)dp.

which evaluates to

\frac{1}{b^{2}} (ab − \frac{a^{2}}{2} − a^{2}) + \frac{(b − 2a)^{2}}{b^{2}} + \frac{1}{b^{2}} (\frac{b^{2}}{2} − ab − \frac{(b − a)^{2}}{2} + a(b − a))

or, simplified,

\frac{(b − a)^{2}}{b^{2}} = P (|p − q| ≥ a).

■

Problem, A-5 1956. Given n objects arranged in a row, a subset of these objects is called unfriendly if no two of its elements is consecutive. Show that

the number of unfriendly subsets each having k elements is ( \begin{matrix}n − k + 1 \\ k \end{matrix} ).

Solution. I will show a one-to-one correspondence between the set of unfriendly k-subsets and the set of k-subsets of n − k + 1 objects. The result then follows.

We have the objects labelled 1, 2, ⋯, n.

Take a given unfriendly k-subset S. Write it as S = {e_{0}, e_{1}, ⋯, e_{k−2}, e_{k−1}}, where the e_{i} are the numbers of the elements in the subset. Order the e_{i} so that e_{0} < e_{1} < e_{2} < ⋯ < e_{k−1}. Then, for each e_{i}, i ≥ 1, e_{i} > e_{i−1} + 1 (since no objects are consecutive). Each set of e_{i} then uniquely defines a unfriendly k-subset.

Now define the set S′ = {e_{0}, e_{1}−1, e_{2}−2, ⋯, e_{k−1}−(k−1)}. Each successive element is larger than the previous, and the very largest an element may be is (n−(k−1)) = (n−k+1). Thus S′ is a k-subset of {1, ⋯, n−k+1}. Clearly for two different unfriendly k-subsets we will obtain two different S′ in this fashion.

If we are given a k-subset K of {1, ⋯, n−k+1}, written as {f_{0}, f_{1}, ⋯, f_{k−1}}, with f_{0} < f_{1} < f_{2} < ⋯ < f_{k−1}, then we can construct the new set K′ = {f_{0}, f_{1} + 1, f_{2} + 2 ⋯ f_{k−1} + (k − 1)}. Clearly this is an unfriendly subset of {1, 2, 3, ⋯, n} with k elements. Taking two different such subsets results in two different unfriendly subsets.

Thus the one-to-one relationship is demonstrated, and the claim is proven. ■

Problem, A-1 1975. Supposing that an integer n is the sum of two triangular numbers,

n = \frac{a^{2} + a}{2} + \frac{b^{2} + b}{2},

write 4n + 1 as the sum of two squares, 4n + 1 = x^{2} + y^{2}, and show how x and y can be expressed in terms of a and b.

Show that, conversely, if 4n+1 = x^{2}+y^{2}, then n is the sum of two triangular numbers.

Solution. If n is the sum of two triangular numbers, n = \frac{a^{2}+a}{2} + \frac{b^{2}+b}{2}, then 4n + 1 = x^{2} + y^{2}, where x = a + b + 1 and y = b − a. Verifying this claim is simply a matter of algebra.

So now I concentrate on the second part. Since 4n + 1 is odd, it follows that one of x, y is even and one of x, y is odd. So just suppose, without loss of generality, that x is even and y is odd, and write x = 2l, y = 2m + 1, with l, m integers. Then, 4n + 1 = 4l^{2} + 4m^{2} + 4m + 1 and n = l^{2} + m^{2} + m.

Thus it’s all good if I prove that, for any integers l, m, l^{2} + m^{2} + m is the sum of two triangular numbers. Let c = l + m and d = l − m. Then, l^{2} + m^{2} + m = \frac{c^{2}+c}{2} + \frac{d^{2}+d}{2} and we are done. ■

Sketch work. The proof above is succinct and one hundred percent correct, but perhaps it is a bit odd how I came up with the relations for a, b, c, d to pull out of my hat at the appropriate times.

For the first part, for example, I suggested to myself a relationship of the form x = c_{1}a+c_{2}b+c_{3}, with c_{1}, c_{2}, c_{3} some constants. Producing three examples and solving the system of equations was enough to theorize the exact formula for x and a formula for y quickly followed. My answer to the second part was produced the same way. Here is the (slightly messy) algebra verifying them:

4n + 1 = 2a^{2} + 2a + 2b^{2} + 2b + 1 =
(a^{2} + 2a + 2ab + b^{2} + 2b + 1) + (b^{2} − 2ab + a^{2}) = (a + b + 1)^{2} + (b − a)^{2}
= x^{2} + y^{2}, and

\begin{aligned}\frac{(l + m)(l + m + 1)}{2} + \frac{(l − m)(l − m + 1)}{2} & = \frac{1}{2}(2l^{2} + 2m^{2} + 2m) \\ & = l^{2} + m^{2} + m. \end{aligned}

■

Problem, A-5 1969. Let u(t) be a continuous function in the system of differential equations

\frac{dx}{dt} = −2y + u(t), \frac{dy}{dt} = −2x + u(t).

Show that, regardless of the choice of u(t), the solution of the system which satisfies x = x_{0}, y = y_{0} at t = 0 will never pass through (0, 0) unless x_{0} = y_{0}. When x_{0} = y_{0}, show that for any positive value t_{0} of t, it is possible to choose u(t) so the solution is at (0, 0) when t = t_{0}.

Solution. Combining the two equations in the system, we have

x′ − y′ = 2(x − y).

So let Q(t) = x(t) − y(t). Then the above becomes Q′(t) = 2Q(t), with the general solution Q(t) = ce^{2t}, with c a constant. Using the initial conditions, c = x_{0} − y_{0}. Notice that unless c = x_{0} − y_{0} = 0, Q(t) is never 0 for any t. Thus, unless x_{0} = y_{0}, x(t) ≠ y(t) for all t, and the solution will never pass through the point (0, 0).

That finishes the first part of the problem. Now, to tackle the second.

If x_{0} = y_{0}, then Q(t) = 0 for all t and thus x(t) = y(t). Then, the first equation in the system becomes

\frac{dx}{dt} = −2x + u(t).

Now, we are given t_{0} ≠ 0. Pick

u(t) = 2x_{0} − \frac{x_{0}}{t_{0}} (2t + 1).

This is a continuous u for t_{0} ≠ 0. In this case, the solution for x(t) is

x(t) = (1 − \frac{t}{t_{0}} )x_{0}.

At t = 0, x(t) = x_{0} = y_{0} = y(t), and at t = t_{0}, x(t) = y(t) = 0. Thus we have shown the existence of an appropriate u(t) and are done. ■

Problem, A-6 1973. Prove that it is impossible for seven distinct straight lines to be situated in the Euclidean plane so as to have at least six points where exactly three of these lines intersect and at least four points where exactly two of these lines intersect.

Solution 1. This is the pretty solution. Any two nonparallel lines in the

Euclidean plane intersect in exactly one point. Thus there are at most ( \begin{matrix}7 \\ 2 \end{matrix} ) =

21 points of intersection.

In a place where exactly two lines intersect, there are ( \begin{matrix}2 \\ 2 \end{matrix} ) = 1 of these

points used up.

In a place where exactly three lines intersect, there are ( \begin{matrix}3 \\ 2 \end{matrix} ) = 3 of these

points used up.

So then, to have six three-intersection points and four two-intersection points, we require 3 × 6 + 4 × 1 = 22 intersection points. However, we have only 21. ■

Solution 2. This is a longer and perhaps less elegant solution, but does show how one can hammer at a problem with the Pigeonhole Principle until it roughly resembles something trivial...

1. We refer to the lines as L_{1}, L_{2}, ⋯ L_{7}.

2. Two nonparallel lines in the plane intersect in exactly one point.

3. A corollary to (2): if L_{i} and L_{j} meet in a 2-intersection, they do not meet in a 3-intersection, and vice versa. Neither can a pair of lines meet in two different 3-intersections.

4. Also from (3), if a line is in 3 different 3-intersections, then it intersects all 6 of the other lines.

5. No line can appear in 4 different 3-intersections, since then one other line appears with it in 2 3-intersections, violating (3).

6. There are 6 3-intersections, involving 18 lines. There are 7 different lines, thus 4 lines appear in at least 3 3-intersections each. By (5), these 4 lines appear in exactly 3 3-intersections.

7. Call these four lines L_{1}, L_{2}, L_{3}, L_{4}. Each of these lines intersects every other line, by (4).

8. From (7), that means that all four of our 2-intersections must involve lines chosen from L_{5}, L_{6}, L_{7}. But only three possible choices exist: L_{5}L_{6}, L_{5}L_{7}, L_{6}L_{7}.

Therefore the seven solution lines do not exist. ■

Problem, A-4 1998. Define the sequence a_{n} as follows: a_{0} = 0, a_{1} = 1, and a_{n+2} is obtained by writing the digits of a_{n+1} immediately followed by the digits of a_{n}. When is a_{n} divisible by 11?

Solution. First, it is clear that the number of digits in a_{n} is F_{n}, the nth Fibonnaci number. The number F_{n} is even iff n is divisible by 3.

Remember the divisibility test for 11: a base 10 integer number is divisible by 11 iff, when one begins with the first digit of the number, subtracts from it the second digit, adds to that the third digit, subtracts the fourth, and so on, once finished, obtains a multiple of 11 as the sum. For example 1331 is divisible by 11 since 1 − 3 + 3 − 1 = 0.

Let b_{n} be the count obtained in this fashion for a_{n} (it is actually 11 minus the number’s remainder modulus 11.) Thus b_{0} = 0, b_{1} = 1, b_{2} = 1, b_{3} = 2 and so on.

Clearly, either b_{n+2} = b_{n+1} + b_{n} or b_{n+2} = b_{n+1} − b_{n}, depending on whether there are an even or odd number of digits in a_{n+1}. If the number is even, it is the former expression, and if the number is odd, it is the latter expression. This only depends on the remainder of n modulus 3.

From this we can see that if we ever have b_{n} = b_{n−3k} and b_{n−1} = b_{n−1−3k}, we have b_{j} = b_{j−3k} for all following j.

Simple computation shows that b_{7} = 0 = b_{1} and b_{8} = 1 = b_{2}. Hence we begin to cycle forever after that. No n_{i} with i from 1 to 6 is 0. Thus, a_{n} is divisible by 11 if and only if n = 6k + 1 for some integer k. ■

Problem, B-6 1998. Show that for any integers a, b, c, we can find a positive integer n such that n^{3} + an^{2} + bn + c is not a perfect square.

Solution. Recall that a perfect square q is always congruent to 0 or 1 mod 4. Thus it is sufficient if we produce an n such that the above expression is not congruent to either 0 or 1 mod 4.

If a + b + c ≡ 1, 2 mod 4, set n = 1. Then n^{3} + an^{2} + bn + c ≡ 1 + a + b + c mod 4 and we are done.

Otherwise, if c ≡ 2, 3 mod 4, set n = 4. Then n^{3} + an^{2} + bn + c ≡ c mod 4 and we are done.

Otherwise, if b ≡ 1, 3 mod 4, set n = 2. Then n^{3} + an^{2} + bn + c ≡ 2b + c mod 4. Since c ≡ 0, 1 mod 4, we are done.

Now, if none of the above work, then b ≡ 0, 2 mod 4, c ≡ 0, 1 mod 4, and a + b + c ≡ 0, 3 mod 4. Set n = 3. Then n^{3} + an^{2} + bn + c ≡ 3 + 2b + a + b + c mod 4. This is congruent to either 2 or 3 mod 4. We are done! ■