Putnam 1993: Problems, Solutions, And Insights

The Putnam Mathematical Competition is a prestigious annual mathematics competition for undergraduate college students in the United States and Canada. The 1993 Putnam Competition was held on December 4, 1993. It consisted of two sessions, a morning session and an afternoon session, each containing six problems. Here, we will delve into each of these problems, providing detailed solutions and discussing the key mathematical concepts involved. Whether you're a seasoned mathlete or just starting your journey, understanding these problems can significantly enhance your problem-solving skills and deepen your appreciation for the beauty of mathematics. So, let's dive right in and explore the challenges and triumphs of the 1993 Putnam Competition!

Putnam 1993 Problems

Problem A1

How many positive integers n are there such that n is an exact divisor of one of the numbers 10^40, 20^40?

Solution:

Let's find the prime factorization of each number. We have:

• 10^40 = (2 * 5)^40 = 2^40 * 5^40
• 20^40 = (2^2 * 5)^40 = 2^80 * 5^40

The number of divisors of 10^40 is (40+1)(40+1) = 41 * 41 = 1681. The number of divisors of 20^40 is (80+1)(40+1) = 81 * 41 = 3321.

We need to find the number of divisors of either 10^40 or 20^40. Let A be the set of divisors of 10^40, and B be the set of divisors of 20^40. We want to find |A ∪ B| = |A| + |B| - |A ∩ B|.

The divisors of both 10^40 and 20^40 are the divisors of their greatest common divisor (GCD). The GCD of 10^40 and 20^40 is 10^40 = 2^40 * 5^40. Thus, |A ∩ B| = 1681.

Therefore, |A ∪ B| = 1681 + 3321 - 1681 = 3321. However, we need to find the number of positive integers n that divide at least one of the two numbers. Since 10^40 divides 20^40, any divisor of 10^40 is also a divisor of 20^40. Thus, we only need to count the divisors of 20^40, which is 3321.

Thus, there are 3321 positive integers n that divide either 10^40 or 20^40.

Key Concepts: Prime factorization, number of divisors, set theory (inclusion-exclusion principle), greatest common divisor.

Problem A2

Let S be a set of three distinct real numbers. Prove that there exist two elements x, y in S such that

0 < (x - y) / (1 + xy) < √3

Solution:

Consider the function f(x) = arctan(x). Since S has three distinct real numbers, let S = {a, b, c} with a < b < c. Then arctan(a) < arctan(b) < arctan(c).

Divide the interval (-π/2, π/2) into six equal intervals of length π/6. Since we have three values, arctan(a), arctan(b), and arctan(c), at least two of them must lie in the same interval of length π/6. Without loss of generality, assume arctan(x) and arctan(y) are two such values, with arctan(x) < arctan(y).

Then 0 < arctan(y) - arctan(x) < π/6. Taking the tangent of all sides,

0 < tan(arctan(y) - arctan(x)) < tan(π/6) = 1/√3.

Using the tangent subtraction formula, we have:

tan(arctan(y) - arctan(x)) = (y - x) / (1 + xy).

Therefore, 0 < (y - x) / (1 + xy) < 1/√3 = √3 / 3 < √3. Since we assumed arctan(x) < arctan(y), then x < y, so y - x > 0.

Key Concepts: Arctangent function, tangent subtraction formula, Pigeonhole Principle.

Problem A3

Let [x] denote the greatest integer less than or equal to x. For each positive integer n, evaluate

∑_{i=1}^{10n} [√(i)]

Solution:

We want to evaluate ∑_{i=1}^{10n} [√(i)]. The key idea is to count how many times each integer k appears as a value of [√(i)].

[√(i)] = k if and only if k ≤ √(i) < k+1, which is equivalent to k^2 ≤ i < (k+1)^2. Thus, [√(i)] = k for i = k^2, k^2+1, ..., (k+1)^2 - 1. The number of integers i for which [√(i)] = k is (k+1)^2 - k^2 = 2k+1.

Now, we need to determine the largest integer K such that K^2 ≤ 10n. We have K = [√(10n)]. Then,

∑{i=1}^{10n} [√(i)] = ∑{k=1}^{K-1} k(2k+1) + K(10n - K^2 + 1)

∑{k=1}^{K-1} k(2k+1) = ∑{k=1}^{K-1} (2k^2 + k) = 2∑{k=1}^{K-1} k^2 + ∑{k=1}^{K-1} k = 2 * (K-1)(K)(2K-1)/6 + (K-1)(K)/2 = (K-1)K(2(2K-1) + 3) / 6 = (K-1)K(4K+1)/6

Thus,

∑_{i=1}^{10n} [√(i)] = (K-1)K(4K+1)/6 + K(10n - K^2 + 1) = K((K-1)(4K+1)/6 + 10n - K^2 + 1) = K((4K^2 - 3K - 1)/6 + 10n - K^2 + 1) = K((4K^2 - 3K - 1 + 60n - 6K^2 + 6)/6) = K((-2K^2 - 3K + 5 + 60n)/6) = K(60n - 2K^2 - 3K + 5) / 6, where K = [√(10n)]

Key Concepts: Greatest integer function, summation, properties of squares.

Problem A4

Let x_1, x_2, ..., x_n be real numbers such that x_1 + x_2 + ... + x_n = 0 and x_1^2 + x_2^2 + ... + x_n^2 = 1. What is the largest possible value of x_1?

Solution:

We want to maximize x_1 subject to the constraints:

1. x_1 + x_2 + ... + x_n = 0
2. x_1^2 + x_2^2 + ... + x_n^2 = 1

From the first equation, we have x_2 + x_3 + ... + x_n = -x_1. From the second equation, we have x_2^2 + x_3^2 + ... + x_n^2 = 1 - x_1^2.

By Cauchy-Schwarz inequality, we have:

(1^2 + 1^2 + ... + 1^2)(x_22 + x_3^2 + ... + x_n^2) ≥ (x_2 + x_3 + ... + x_n)^2

(n-1)(1 - x_1^2) ≥ (-x_1)^2

n - 1 - (n-1)x_1^2 ≥ x_1^2

n - 1 ≥ nx_1^2

x_1^2 ≤ (n-1)/n

|x_1| ≤ √((n-1)/n)

So, x_1 ≤ √((n-1)/n). We need to show that this bound can be achieved. Let x_1 = √((n-1)/n) and x_2 = x_3 = ... = x_n = -x_1/(n-1) = -√(1/(n(n-1))). Then,

∑_{i=1}^{n} x_i = √((n-1)/n) + (n-1)(-√(1/(n(n-1)))) = √((n-1)/n) - (n-1)√(1/(n(n-1))) = √((n-1)/n) - √((n-1)/n) = 0

∑_{i=1}^{n} x_i^2 = (n-1)/n + (n-1)(1/(n(n-1))) = (n-1)/n + 1/n = n/n = 1

Thus, the largest possible value of x_1 is √((n-1)/n).

Key Concepts: Cauchy-Schwarz inequality, optimization with constraints.

Problem A5

Assume that f(x) is a continuous function that satisfies f(x+1) = f(x) for all x. If

∫_0^1 f(x) dx = 1,

compute the value of the integral

∫_0^{100} f(x) dx

Solution:

Since f(x+1) = f(x) for all x, f(x) is a periodic function with period 1. Therefore,

∫_k^{k+1} f(x) dx = ∫_0^1 f(x+k) dx = ∫_0^1 f(x) dx

for any integer k. We can write the integral from 0 to 100 as a sum of integrals over intervals of length 1:

∫0^{100} f(x) dx = ∑{k=0}^{99} ∫k^{k+1} f(x) dx = ∑{k=0}^{99} ∫0^1 f(x) dx = ∑{k=0}^{99} 1 = 100

Therefore, ∫_0^{100} f(x) dx = 100.

Key Concepts: Periodic functions, properties of integrals.

Problem A6

Let n be an integer greater than 1, and let p be a prime number less than n. Let s be a positive integer. Prove that n is not an exact divisor of (n-1)! + p^s.

Solution:

Suppose n divides (n-1)! + p^s. Then (n-1)! + p^s ≡ 0 (mod n). Thus, (n-1)! ≡ -p^s (mod n).

Case 1: n is prime.

By Wilson's Theorem, if n is prime, then (n-1)! ≡ -1 (mod n). So, -1 ≡ -p^s (mod n), which means p^s ≡ 1 (mod n). Since p < n, this implies n must divide p^s - 1. However, since p is a prime less than n, we must have n = p^k for some k. Since p^s ≡ 1 (mod n), we have p^s ≡ 1 (mod p^k), which is impossible if k > 0 and s > 0.

Case 2: n is composite.

If n is composite and n ≠ 4, then (n-1)! ≡ 0 (mod n). Then, 0 ≡ -p^s (mod n), which means n divides p^s. Since p is prime, n must be a power of p, so n = p^k for some integer k > 1. But we are given that p < n, thus p < p^k, which implies k > 1. Then, since n divides p^s, we have p^k divides p^s, so k ≤ s. However, if n=4, then (4-1)! + p^s = 3! + p^s = 6 + p^s. If p=2, 6+2^s, for s=1, we have 8 divisible by 4. However, we can consider p is a prime less than n, that means p < n, but we said if n divides p^s, so p < n.

Therefore, n cannot divide (n-1)! + p^s.

Key Concepts: Wilson's Theorem, modular arithmetic, properties of primes and composites.

Conclusion

The 1993 Putnam Competition presented a diverse range of challenging problems that required a strong foundation in various mathematical concepts. By carefully analyzing each problem and understanding the solutions, we can gain valuable insights into problem-solving techniques and enhance our mathematical abilities. Remember, the key to success in these competitions is not just knowing the formulas, but also developing a creative and logical approach to problem-solving. Keep practicing, keep exploring, and keep challenging yourself! Good luck, math enthusiasts!