This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

Problem A-1

How many primes among the positive integers, written as usual in base

10, are such that their digits are alternating 1's and 0's, beginning

and ending with 1?

Problem A-2

Evaluate \int_0^a \int_0^b \exp(\max{b^2 x^2, a^2 y^2}) dy dx where a and

b are positive.

Problem A-3

Prove that if 11z^10 + 10iz^9 + 10iz - 11 = 0, then |z| = 1. (Here z is

a complex number and i^2 = -1.)

Problem A-4

If \alpha is an irrational number, 0 < \alpha < 1, is there a finite

game with an honest coin such that the probability of one player winning

the game is \alpha? (An honest coin is one for which the probability of

heads and the probability of tails are both 1/2. A game is finite if

with probability 1 it must end in a finite number of moves.)

Problem A-5

Let m be a positive integer and let G be a regular (2m + 1)-gon

inscribed in the unit circle. Show that there is a positive constant A,

independent of m, with the following property. For any point p inside G

there are two distinct vertices v_1 and v_2 of G such that

1 A | |p - v_1| - |p - v_2| | < --- - ---. m m^3

Here |s - t| denotes the distance between the points s and t.

Problem A-6

Let \alpha = 1 + a_1 x + a_2 x^2 + ... be a formal power series with

coefficients in the field of two elements. Let

/ 1 if every block of zeros in the binary expansion of n / has an even number of zeros in the block, a_n = { \ 0 otherwise. (For example, a_36 = 1 because 36 = 100100_2 and a_20 = 0 because 20 = 10100_2.) Prove that \alpha^3 + x \alpha + 1 = 0.

Problem B-1

A dart, thrown at random, hits a square target. Assuming that any two

points of the target of equal area are equally likely to be hit, find

the probability that the point hit is nearer to the center than to any

edge. Express your answer in the form (a \sqrt(b) + c) / d, where a, b,

c, d are integers.

Problem B-2

Let S be a non-empty set with an associative operation that is left and

right cancellative (xy = xz implies y = z, and yx = zx implies y = z).

Assume that for every a in S the set { a^n : n = 1, 2, 3, ... } is

finite. Must S be a group?

Problem B-3

Let f be a function on [0,\infty), differentiable and satisfying

f'(x) = -3 f(x) + 6 f(2x)

for x > 0. Assume that |f(x)| <= \exp(-\sqrt(x)) for x >= 0 (so that

f(x) tends rapidly to 0 as x increases). For n a non-negative integer,

define

\mu_n = \int_0^\infty x^n f(x) dx

(sometimes called the nth moment of f).

a. Express \mu_n in terms of \mu_0.

b. Prove that the sequence { \mu_n 3^n / n! } always converges, and that

the limit is 0 only if \mu_0 = 0.

Problem B-4

Can a countably infinite set have an uncountable collection of non-empty

subsets such that the intersection of any two of them is finite?

Problem B-5

Label the vertices of a trapezoid T (quadrilateral with two parallel

sides) inscribed in the unit circle as A, B, C, D so that AB is parallel

to CD and A, B, C, D are in counterclockwise order. Let s_1, s_2, and d

denote the lengths of the line segments AB, CD, and OE, where E is the

point of intersection of the diagonals of T, and O is the center of the

circle. Determine the least upper bound of (s_1 - s_2) / d over all such

T for which d \ne 0, and describe all cases, if any, in which it is

attained.

Problem B-6

Let (x_1, x_2, ..., x_n) be a point chosen at random from the

n-dimensional region defined by 0 < x_1 < x_2 < ... < x_n < 1.

Let f be a continuous function on [0, 1] with f(1) = 0. Set x_0 = 0 and

x_{n+1} = 1. Show that the expected value of the Riemann sum

\sum_{i = 0}^n (x_{i+1} - x_i) f(x_{i+1})

is \int_0^1 f(t)P(t) dt, where P is a polynomial of degree n,

independent of f, with 0 \le P(t) \le 1 for 0 \le t \le 1.

competition/tests/math/putnam/putnam.1990.s

Problem A-1

How many primes among the positive integers, written as usual in base

10, are such that their digits are alternating 1's and 0's, beginning

and ending with 1?

Solution:

Exactly one, namely 101. 1 is not prime; 101 is prime. The sum

100^n + 100^{n - 1} + ... + 1 is divisible by 101 if n is odd,

10^n + 10^{n - 1} + ... + 1 if n is even. (To see the second part,

think about 101010101 = 102030201 - 1020100 = 10101^2 - 1010^2.)

Problem A-2

Evaluate \int_0^a \int_0^b \exp(\max{b^2 x^2, a^2 y^2}) dy dx where a and

b are positive.

Solution:

Split the inner integral according to the max{}. The easy term becomes

an integral of t e^{t^2}. The other term becomes an easy term after you

switch the order of integration. Your answer should have an e^{(ab)^2}.

Problem A-3

Prove that if 11z^10 + 10iz^9 + 10iz - 11 = 0, then |z| = 1. (Here z is

a complex number and i^2 = -1.)

Solution:

z is not zero, so divide by z^5 to make things a bit more symmetric.

Now write z = e^{i \theta} and watch the formula dissolve into a simple

trigonometric sum. The 11 sin 5 \theta term dominates the sum when that

sine is at its maximum; by this and similar considerations, just *write

down* enough maxima and minima of the function that it must have ten

real roots for \theta. (This cute solution is due to Melvin Hausner,

an NYU math professor.)

Problem A-4

If \alpha is an irrational number, 0 < \alpha < 1, is there a finite

game with an honest coin such that the probability of one player winning

the game is \alpha? (An honest coin is one for which the probability of

heads and the probability of tails are both 1/2. A game is finite if

with probability 1 it must end in a finite number of moves.)

Solution:

Yes. Write \alpha in binary---there's no ambiguity since it's irrational.

At the nth step (n >= 0), flip the coin. If it comes up heads, go to the

next step. If it comes up tails, you win if the nth bit of \alpha is 1.

Otherwise you lose. The probability of continuing forever is zero. The

probability of winning is \alpha.

This problem could have been better stated. Repeated flips of the coin

must produce independent results. The note that ``finite'' means only

``finite with probability 1'' is hidden inside parentheses, even though

it is crucial to the result. In any case, this problem is not very

original: I know I've seen similar problems many times, and no serious

student of probability can take more than ten minutes on the question.

Problem A-5

Let m be a positive integer and let G be a regular (2m + 1)-gon

inscribed in the unit circle. Show that there is a positive constant A,

independent of m, with the following property. For any point p inside G

there are two distinct vertices v_1 and v_2 of G such that

1 A | |p - v_1| - |p - v_2| | < --- - ---. m m^3

Here |s - t| denotes the distance between the points s and t.

Solution:

Place G at the usual roots of unity. Without loss of generality assume

that p = re^{i\theta} is as close to 1 as to any other vertex; in other

words, assume |\theta| <= 2\pi / (4m + 2) = \pi / (2m + 1). Now take the

distance between p and the two farthest (not closest!) vertices. Make

sure to write | |X| - |Y| | as the ratio of | |X|^2 - |Y|^2 | to |X| + |Y|.

I may have miscalculated, but I get a final result inversely proportional

to (4m + 2)^2, from which the given inequality follows easily with, say,

A = 0.01.

Alternate solution:

The maximum distance between p and a point of G is achieved between two

almost-opposite corners, with a distance squared of double 1 + \cos\theta

for an appropriately small \theta, or something smaller than 2 - A/m^2

for an appropriate A. Now consider the set of distances between p and

the vertices; this set is 2m + 1 values >= 0 and < 2 - A/m^2, so that

there are two values at distance less than 1/m - A/m^3 as desired.

Problem A-6

Let \alpha = 1 + a_1 x + a_2 x^2 + ... be a formal power series with coefficients in the field of two elements. Let / 1 if every block of zeros in the binary expansion of n / has an even number of zeros in the block, a_n = { \ 0 otherwise. (For example, a_36 = 1 because 36 = 100100_2 and a_20 = 0 because 20 = 10100_2.) Prove that \alpha^3 + x \alpha + 1 = 0.

Solution:

(Put a_0 = 1, of course.) Observe that a_{4n} = a_n since adding two zeros

on the right end does not affect the defining property; a_{4n + 2} = 0

since the rightmost zero is isolated; and a_{2n + 1} = a_n since adding

a one on the right does not affect the defining property. Now work in the

formal power series ring Z_2[[x]]. For any z in that ring that is a

multiple of x, define f(z) as a_0 + a_1 z + a_2 z^2 + ... . Clearly

f(z) = f(z^4) + z f(z^2) by the relations between a's. Now over Z_2,

(a + b)^2 = a^2 + b^2, so f(z) = f(z)^4 + z f(z)^2. Plug in x for z and

cancel the f(x) to get 1 = \alpha^3 + x \alpha as desired.

Problem B-1

A dart, thrown at random, hits a square target. Assuming that any two

points of the target of equal area are equally likely to be hit, find

the probability that the point hit is nearer to the center than to any

edge. Express your answer in the form (a \sqrt(b) + c) / d, where a, b,

c, d are integers.

Solution:

This is straightforward. The closer-to-the-center region is centered on

a square of side length \sqrt 2 - 1; surrounding the square and meeting

it at its corners are parabolic sections extending out halfway to the

edge. b is 2 and d is 6; have fun.

Problem B-2

Let S be a non-empty set with an associative operation that is left and

right cancellative (xy = xz implies y = z, and yx = zx implies y = z).

Assume that for every a in S the set { a^n : n = 1, 2, 3, ... } is

finite. Must S be a group?

Solution:

Yes. There is a minimal m >= 1 for which a^m = a^n for some n with n > m;

by cancellation, m must be 1. We claim that a^{n-1} is an identity in S.

For ba = ba^n = ba^{n-1}a, so by cancellation b = ba^{n-1}, and similarly

on the other side. Now a has an inverse, a^{n-2}. This problem is not new.

Problem B-3

Let f be a function on [0,\infty), differentiable and satisfying

f'(x) = -3 f(x) + 6 f(2x)

for x > 0. Assume that |f(x)| <= \exp(-\sqrt(x)) for x >= 0 (so that

f(x) tends rapidly to 0 as x increases). For n a non-negative integer,

define

\mu_n = \int_0^\infty x^n f(x) dx

(sometimes called the nth moment of f).

a. Express \mu_n in terms of \mu_0.

b. Prove that the sequence { \mu_n 3^n / n! } always converges, and that

the limit is 0 only if \mu_0 = 0.

Solution:

The only trick here is to integrate \mu_n by parts the ``wrong way,''

towards a higher power of x. A bit of manipulation gives the formula for

\mu_n as \mu_0 times n! / 3^n times the product of 2^k / (2^k - 1) for

1 <= k <= n. Part b is straightforward; the product converges since the

sum of 1 / (2^k - 1) converges (absolutely---it's positive).

Problem B-4

Can a countably infinite set have an uncountable collection of non-empty

subsets such that the intersection of any two of them is finite?

Solution:

Yes. A common example for this very well-known problem is the set of

rationals embedded in the set of reals. For each real take a Cauchy

sequence converging to that real; those sequences form the subsets of

the countably infinite rationals, and the intersection of any two of

them had better be finite since the reals are Archimedian. Another

example, from p-adics: Consider all binary sequences. With sequence

a_0 a_1 a_2 ... associate the set a_0, a_0 + 2a_1, a_0 + 2a_1 + 4a_2,

etc.; or stick 1 bits in all the odd positions to simplify housekeeping

(most importantly, to make the set infinite). Certainly different

sequences give different sets, and the intersection of two such sets

is finite.

Alternative solution:

Let C be a countable collection of non-empty subsets of A with the property

that any two subsets have finite intersection (from now

on we call this property, countable intersection property). Clearly

such a collection exists. We will show that C is not maximal, that is,

there exists a set which does not belong to C and it intersects finitely

with any set in C. Hence by Zorn's lemma, C can be extended to an

uncountable collection.

Let A1, A2, .... be an enumeration of sets in C. Then by axiom of choice,

pick an element b sub i from each of A sub i - Union {from j=1 to i-1} of

A sub j. It is easy to see that each such set is non-empty. Let B be the

set of all b sub i's. Then clearly B is different from each of the A sub i's

and its intersection with each A sub i is finite.

Yet another alternative solution:

Let the countable set be the lattice points of the plane. For each t in

[0,pi) let s(t) be the lattice points in a strip with angle of inclination

t and width greater than 1. Then the set of these strips is uncountable.

The intersection of any two is bounded, hence finite.

More solutions:

The problem (in effect) asks for an uncountable collection of

sets of natural numbers that are "almost disjoint," i.e., any two

have a finite intersection. Here are two elementary ways to

get such a collection.

1. For any set A={a, b, c, ...} of primes, let A'={a, ab, abc, ...}.

If A differs from B then A' has only a finite intersection with B'.

2. For each real number, e.g. x=0.3488012... form the set

S_x={3, 34, 348, 3488, ...}. Different reals give almost disjoint sets.

Problem B-5

Label the vertices of a trapezoid T (quadrilateral with two parallel

sides) inscribed in the unit circle as A, B, C, D so that AB is parallel

to CD and A, B, C, D are in counterclockwise order. Let s_1, s_2, and d

denote the lengths of the line segments AB, CD, and OE, where E is the

point of intersection of the diagonals of T, and O is the center of the

circle. Determine the least upper bound of (s_1 - s_2) / d over all such

T for which d \ne 0, and describe all cases, if any, in which it is

attained.

Solution:

Center the circle at the origin and rotate the trapezoid so that AB and

CD are horizontal. Assign coordinates to A and D, polar or rectangular

depending on your taste. Now play with s_1 - s_2 / d for a while;

eventually you'll find the simple form, after which maximization is

easy. The answer, if I've calculated right, is 2, achieved when rotating

the trapezoid by 90 degrees around the circle would take one vertex into

another. (A right triangle, with the hypoteneuse the length-two diamater

and d = 1, is a degenerate example.)

Alternative solution:

Let a be the distance from O (the center of the circle) to AB (that is

the side with length s1), and b the distance from O to CD. Clearly,

a = sqrt(1-s1*s1/4) and b = sqrt(1-s2*s2/4). Then with some mathematical

jugglery, one can show that (s1-s2)/d = (s1*s1-s2*s2)/(b*s1-a*s2).

Then differentiating this with respect to s1 and s2 and equating to

0 yields s1*s1+s2*s2=4, and hence s1=2*b and s2=2*a. The value of (s1-s2)/d

for these values is then 2. Hence (s1-s1)/d achieves its extremeum when

s1*s1+s2*s2=4 (that this value is actually a maximum is then easily seen),

and the lub is 2.

Problem B-6

Let (x_1, x_2, ..., x_n) be a point chosen at random from the

n-dimensional region defined by 0 < x_1 < x_2 < ... < x_n < 1.

Let f be a continuous function on [0, 1] with f(1) = 0. Set x_0 = 0 and

x_{n+1} = 1. Show that the expected value of the Riemann sum

\sum_{i = 0}^n (x_{i+1} - x_i) f(x_{i+1})

is \int_0^1 f(t)P(t) dt, where P is a polynomial of degree n,

independent of f, with 0 \le P(t) \le 1 for 0 \le t \le 1.

Solution:

Induct right to left. Show that for each k, given x_{k-1}, the

expected value at a point chosen with x_{k-1} < x_k < ... < x_n < 1

is a polynomial of the right type with the right degree. It's pretty

easy once you find the right direction. 0 \le P(t) \le 1 comes for

free: if P(t) is out of range at a point, it is out of range on an

open interval, and setting f to the characteristic function of that

interval produces a contradiction.

Continue to: