PUTNAM PROBLEM SOLVING SEMINAR WEEK 6

The Rules. These are way too many problems to consider. Just pick a few problems in one of the sections and play around with them. The 1993 Putnam is left over from last week, but I’ve included it in case we feel like discussing some of the problems.

Invariants.

The rules of the games Sprouts and Brussels Sprouts will be explained in Vin’s session today. If you need to be reminded of the rules, just ask someone!

1. Let t be the number of turns in a completed game of Sprouts starting with n dots. Show that 3n − 1 ≥ t ≥ 2n. Show that this inequality is best possible.

2. What can you say about the number of turns in a game of Brussels Sprouts which starts with n crosses?

3. Three cities need to be connected to three factories by routes which cannot cross each other. Five villages need to be connected to each other by paths which cannot cross. Prove that both tasks are impossible. [Hint: use Euler’s formula V − E + F = 2.]

There are three types of piece in a Rubik’s cube: centers (which stay essentially fixed, but may rotate in place); edges (there are 12); and corners (there are 8). Each piece has a position (where is it?) and an orientation (is it rotated, flipped or twisted?).

4. Show that it is impossible: to swap two edges leaving all other pieces correctly located; to swap two corners leaving all other pieces correctly located; to rotate one face-center by 90^{∘} leaving all other pieces correctly placed and oriented.

5. Show that it is impossible: to flip one edge, but leave all other edges in place and unflipped; to twist one corner (by 120^{∘}) while leaving all other corners in place and untwisted.

6. A Rubik-style dodecahedron is dismantled and randomly reassembled. What is the probability that the dodecahedron can be solved from that condition? What if you have marked the face centers to detect rotations?

Now for some tiling problems. As usual there are two sides to such questions: find tilings in the “good” cases; disprove tilability in the “bad” cases.

Date: November 13, 2001.

7. Show that a chessboard with two opposite corners removed cannot be tiled with dominos.

8. We attempt to an m × n chessboard can be tiled with strips of size 1 × d (placed in either orientation). Show that this is possible if and only if d divides one of m, n. [Note: this is trivial to prove if d is prime!]

9. Let m, n > 1 be integers. We attempt to tile an m × n chessboard with pieces of the following shape:

Rotation and reflection are allowed. Show that we can succeed if and only if mn is a multiple of 8.

10. Show that there is no way to tile an m × n rectangle with pieces of the following shape:

Better still, show that there is no way to tile an m_{1} × ⋯ × m_{d} cuboid (in d dimensions) with the analogous piece made of five unit hypercubes.

Finally, some curious “bugs on squares” games.

11. Three bugs start out at points (0, 0), (3, 0), and (0, 2). They move one at a time, in any order. Each bug can only move in a direction parallel to the line connecting the other two bugs. Can two of the bugs switch places while the third ends up where it started? Can they end up at (1,1), (6,2), (3,4)?

12. A collection of n beetles, each black or white in color, is arranged in a line. On each move, a black beetle turns pink, emitting a chemical which causes its immediate neighbors to switch from black to white, or white to black (as appropriate). Already pink bugs are not affected. Under what starting conditions is it possible for all n bugs to turn pink?

13. This game is played on the quadrant m, n ≥ 0 of an infinite chessboard. A bug starts on (0, 0). If there is a bug on square (m, n) and both (m, n + 1) and (m + 1, n) are empty, then the bug replicates, and one clone jumps onto (m, n + 1) and the other clone jumps onto (m+1, n) leaving (m, n) empty. Find a strategy (or show impossiblity) for evacuating all bugs from the six squares (0, 0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0).

14. An infinite army of bugs is arrayed on the squares n ≤ 0 of an infinite chessboard. A bug can move by jumping over an adjacent bug (orthogonally, not diagonally) into an empty square. This kills the jumped-over bug, which evaporates without trace. Can the army send at least one bug to the row n = 5?

The Fifty-Fourth William Lowell Putnam Mathematical Competition (December 4, 1993).

Caution: This was perhaps the hardest Putnam in the last couple of decades.

A1. The horizontal line y = c intersects the curve y = 2x − 3x^{3} in the first quadrant as in the figure. Find c so that the areas of the two shaded regions are equal.

y = 2x − 3x^{2} y y = c  x

A2. Let (x_{n})_{n≥0} be a sequence of nonzero real numbers such that

x_{n}^{2} − x_{n−1}x_{n+1} = 1 for n = 1, 2, 3, ….

Prove there exists a real number a such that x_{n+1} = ax_{n} − x_{n−1} for all n ≥ 1.

A3. Let P_{n} be the set of subsets of {1, 2, …, n}. Let c(n, m) be the number of functions f : P_{n} → {1, 2, …, m} such that f(A ∩ B) = min{f(A), f(B)}. Prove that

c(n, m) = ∑_{j=1}^{m} j^{n}.

A4. Let x_{1}, x_{2}, …, x_{19} be positive integers each of which is less than or equal to 93. Let y_{1}, y_{2}, …, y_{93} be positive integers each of which is less than or equal to 19. Prove that there exists a (nonempty) sum of some x_{i}’s equal to a sum of some y_{j}’s.

A5. Show that

∫_{−100}^{−10} (\frac{x^{2} − x}{x^{3} − 3x + 1})^{2} dx + ∫ \frac{1}{11} \frac{1}{101} (\frac{x^{2} − x}{x^{3} − 3x + 1})^{2} dx + ∫ \frac{11}{10} \frac{101}{100} (\frac{x^{2} − x}{x^{3} − 3x + 1})^{2} dx

is a rational number.

A6. The infinite sequence of 2’s and 3’s

2, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 2, 3, 3, 3, 2, … has the property that, if one forms a second sequence that records the number of 3’s between successive 2’s, the result is identical to the given sequence. Show that there exists a real number r such that, for any n, the n^{th} term of the sequence is 2 if and only if n = 1 + ⌊rm⌋ for some nonnegative integer m. (Note: ⌊x⌋ denotes the largest integer less than or equal to x.)

B1. Find the smallest positive integer n such that for every integer m, with 0 < m < 1993, there exists an integer k for which

\frac{m}{1993} < \frac{k}{n} < \frac{m + 1}{1994}.

B2. Consider the following game played with a deck of 2n cards numbered from 1 to 2n. The deck is randomly shuffled and n cards are dealt to each of two players, A and B. Beginning with A, the players take turns discarding one of their remaining cards and announcing its number. The game ends as soon as the sum of the numbers on the discarded cards is divisible by 2n + 1. The last person to discard wins the game. Assuming optimal strategy by both A and B, what is the probability that A wins?

B3. Two real numbers x and y are chosen at random in the interval (0,1) with respect to the uniform distribution. What is the probability that the closest integer to x/y is even? Express the answer in the form r + sπ, where r and s are rational numbers.

B4. The function K(x, y) is positive and continuous for 0 ≤ x ≤ 1, 0 ≤ y ≤ 1, and the functions f(x) and g(x) are positive and continuous for 0 ≤ x ≤ 1. Suppose that for all x, 0 ≤ x ≤ 1,

∫_{0}^{1} f(y)K(x, y) dy = g(x)  and  ∫_{0}^{1} g(y)K(x, y) dy = f(x).

Show that f(x) = g(x) for 0 ≤ x ≤ 1.

B5. Show there do not exist four points in the Euclidean plane such that the pairwise distances between the points are all odd integers.

B6. Let S be a set of three, not necessarily distinct, positive integers. Show that one can transform S into a set containing 0 by a finite number of applications of the following rule: Select two of the three integers, say x and y, where x ≤ y and replace them with 2x and y − x.

The Forty-Ninth William Lowell Putnam Mathematical Competition (December 3, 1988)

This Putnam was not as hard as that of 1993, but of course no Putnam can be described as “easy”.

A1. Let R be the region consisting of the points (x, y) of the cartesian plane satisfying both |x| − |y| ≤ 1 and |y| ≤ 1. Sketch the region R and find its area.

A2. 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 nonzero function g defined on (a, b) such that this wrong product rule is true for x in (a, b).

A3. Determine, with proof, the set of real numbers x for which

∑_{n=1}^{∞} (\frac{1}{n} csc \frac{1}{n} − 1)^{x}

converges.

A4.

(a) If every point of the plane is painted one of three colors, do there necessarily exist two points of the same color exactly one inch apart?

(b) What if “three” is replaced by “nine”?

Justify your answers.

A5. Prove that there exists a unique function f from the set ℝ^{+} of positive real numbers to ℝ^{+} such that

f(f(x)) = 6x − f(x)  and  f(x) > 0  for all x > 0.

A6. If a linear transformation A on an n-dimensional vector space has n + 1 eigenvectors such that any n of them are linearly independent, does it follow that A is a scalar multiple of the identity? Prove your answer.

B1. A composite (positive integer) is a product ab with a and b not necessarily distinct integers in {2, 3, 4, … }. Show that every composite is expressible as xy + xz + yz + 1, with x, y, and z positive integers.

B2. Prove or disprove: if x and y are real numbers with y ≥ 0 and y(y + 1) ≤ (x + 1)^{2}, then y(y − 1) ≤ x^{2}.

B3. For every n in the set ℤ^{+} = {1, 2, … } of positive integers, let r_{n} be the minimum value of |c − d\sqrt{3}| for all nonnegative integers c and d with c + d = n. Find, with proof, the smallest positive real number g with r_{n} ≤ g for all n ∈ ℤ^{+}.

B4. Prove that if ∑_{n=1}^{∞} a_{n} is a convergent series of positive real numbers, then so is ∑_{n=1}^{∞}(a_{n})^{n/(n+1)}.

B5. For positive integers n, let M_{n} be the 2n + 1 by 2n + 1 skew-symmetric matrix for which each entry in the first n subdiagonals below the main diagonal is 1 and each of the remaining entries below the main diagonal is −1. Find, with proof, the rank of M_{n}. (According to one definition, the rank of a matrix is the largest k such that there is a k × k submatrix with nonzero determinant.)

One may note that

M_{1} = (\begin{matrix}0 & −1 & 1 \\ 1 & 0 & −1 \\ −1 & 1 & 0 \end{matrix}) and M_{2} = (\begin{matrix}0 & −1 & −1 & 1 & 1 \\ 1 & 0 & −1 & −1 & 1 \\ 1 & 1 & 0 & −1 & −1 \\ −1 & 1 & 1 & 0 & −1 \\ −1 & −1 & 1 & 1 & 0 \end{matrix}) .

B6. Prove that there exist an infinite number of ordered pairs (a, b) of integers such that for every positive integer t the number at + b is a triangular number if and only if t is a triangular number.

(The triangular numbers are the t_{n} = n(n + 1)/2 with n in {0, 1, 2, … }.)

This handout, and other useful things, can (soon) be found at

http://math.stanford.edu/˜ vakil/stanfordputnam.html