A1: Suppose on the contrary that there exist t_{1}, t_{2} ∈ T with t_{1}t_{2} ∈ U and u_{1}, u_{2} ∈ U with u_{1}u_{2} ∈ T. Then (t_{1}t_{2})u_{1}u_{2} ∈ U while t_{1}t_{2}(u_{1}u_{2}) ∈ T, contradiction.

A2: The integral converges iff a = b. The easiest proof uses “big-O” notation and the fact that (1 + x)^{1/2} = 1 + x/2 + O(x^{2}) for |x| < 1. (Here O(x^{2}) means bounded by a constant times x^{2}.)

So

\sqrt{x + a} − \sqrt{x} = x^{1/2}(\sqrt{1 + a/x} − 1) = x^{1/2}(1 + a/2x + O(x^{−2})),

hence

\sqrt{\sqrt{x + a} − \sqrt{x}} = x^{1/4}(1 + a/4x + O(x^{−2})

and similarly

\sqrt{\sqrt{x} − \sqrt{x − b}} = x^{1/4}(1 + b/4x + O(x^{−2}).

Hence the integral we’re looking at is

∫_{b}^{∞} x^{1/4}((a − b)/4x + O(x^{−2}) dx.

The term x^{1/4}O(x^{−2}) is bounded by a constant times x^{−7/4}, whose integral converges. Thus we only have to decide whether x^{−3/4}(a − b)/4 converges. But x^{−3/4} has divergent integral, so we get convergence if and only if a = b (in which case the integral telescopes anyway).

A3: Let D and E be the numbers d_{1} … d_{9} and e_{1} … e_{9}, respectively. We are given that (e_{i} − d_{i})10^{9−i} + D ≡ 0 (mod 7) and (f_{i} − e_{i})10^{9−i} + E ≡ 0 (mod 7) for i = 1, …, 9. Sum the first relation over i = 1, …, 9 and we get E − D + 9D ≡ 0 (mod 7), or E + D ≡ 0 (mod 7). Now add the first and second relations for any particular value of i and we get (f_{i} −d_{i})10^{9−i} +E +D ≡ 0 (mod 7). But we know E +D is divisible by 7, and 10 is coprime to 7, so d_{i} − f_{i} ≡ 0 (mod 7).

A4: Let s_{k} = x_{1} + ⋯ + x_{k} − k(n − 1)/n, so that s_{n} = s_{0} = 0. These form a cyclic sequence that doesn’t change when you rotate the necklace, except that the entire sequence gets translated by a constant. In particular, it makes sense to choose x_{i} for which s_{i} is maximum and make that one x_{n}; this way s_{i} ≤ 0 for all i, which gives x_{1} + ⋯ + x_{i} ≤ i(n − 1)/n, but the right side may be replaced by i − 1 since the left side is an integer.

A5: Everyone (presumably) knows that the set of solutions of a system of linear first-order differential equations with constant coefficients is n-dimensional, with basis vectors of the form f_{i}(t)v⃗_{i} (i.e. a function times a constant vector), where the v⃗_{i} are linearly independent. In particular, our solution x⃗(t) can be written as ∑_{i=1}^{n} c_{i}f_{i}(t)v⃗_{1}.

Choose a vector w⃗ orthogonal to v⃗_{2}, …, v⃗_{n} but not to v⃗_{1}. Since x⃗(t) → 0 as t → ∞, the same is true of w⃗ · x⃗; but that is simply (w⃗ · v⃗_{1})c_{1}f_{1}(t). In other words, if c_{i} ≠ 0, then f_{i}(t) must also go to 0.

However, it is easy to exhibit a solution which does not go to 0. The sum of the eigenvalues of the matrix A = (a_{ij}), also known as the trace of A, being the sum of the diagonal entries of A, is nonnegative, so A has an eigenvalue λ with nonnegative real part, and a corresponding eigenvector v⃗. Then e^{λt}v⃗ is a solution that does not go to 0. (If λ is not real, add this solution to its complex conjugate to get a real solution, which still doesn’t go to 0.)

Hence one of the c_{i}, say c_{1}, is zero, in which case x⃗(t) · w⃗ = 0 for all t.

A6: View this as a random walk/Markov process with states (i, j, k) the triples of integers with sum 0, corresponding to the difference between the first, second and third rows with their average (twice the number of columns). Adding a new column adds on a random permutation of the vector (1, 0, −1). I prefer to identify the triple (i, j, k) with the point (i − j) + (j − k)ω + (k − i)ω^{2} in the plane, where ω is a cube root of unity. Then adding a new column corresponds to moving to one of the six neighbors of the current position in a triangular lattice.

What we’d like to argue is that for large enough n, the ratio of the probabilities of being in any two particular states goes to 1. Then in fact, we’ll see that eventually, about six times as many matrices have a = b − 1, b = c − 1 than a = b = c. This is a pain to prove, though, and in fact is way more than we actually need.

Let C_{n} and A_{n} be the probability that we are at the origin, or at a particular point adjacent to the origin, respectively. Then C_{n+1} = A_{n}. (In fact, C_{n+1} is 1/6 times the sum of the probabilities of being at each neighbor of the origin at time n, but these are all A_{n}.) So the desired result, which is that C_{n}/A_{n} ≥ 2/3 for some large n, is equivalent to A_{n+1}/A_{n} ≥ 2/3.

Suppose on the contrary that this is not the case; then A_{n} < c(2/3)^{n} for some constant n. However, if n = 6m, the probability that we chose each of the six types of moves m times is already (6m)!/[m!^{6}6^{6m}], which by Stirling’s approximation is asymptotic to a constant times m^{−5/2}. This term alone is bigger than c(2/3)^{n}, so we must have A_{n+1}/A_{n} ≥ 2/3 for some n. (In fact, we must have A_{n+1}/A_{n} ≥ 1 − ϵ for any ϵ > 0.)

B1: For a given π, no more than three different values of π(x) are possible (four would require one part each of size at least 1,2,3,4, and that’s already more than 9 elements). If no such x, y exist, each pair (π(x), π′(x)) occurs for at most 1 element of x, and since there are only 3 × 3 possible pairs, each must occur exactly once. In particular, each value of π(x) must occur 3 times. However, clearly any given value of π(x) occurs kπ(x) times, where k is the number of distinct partitions of that size. Thus π(x) can occur 3 times only if it equals 1 or 3, but we have three distinct values for which it occurs, contradiction.

B2: For those who haven’t taken enough physics, “rolling without slipping” means that the perimeter of the ellipse and the curve pass at the same rate, so all we’re saying is that the perimeter of the ellipse equals the length of one period of the sine curve. So set up the integrals:

∫_{0}^{2π} \sqrt{(−a sin θ)^{2} + (b cos θ)^{2}} dθ = ∫_{0}^{2πa} \sqrt{1 + (c/a cos x/a)^{2}} dx.

Let θ = x/a in the second integral and write 1 as sin^{2} θ + cos^{2} θ and you get

∫_{0}^{2π} \sqrt{a^{2} sin^{2} θ + b^{2} cos^{2} θ} dθ = ∫_{0}^{2π} \sqrt{a^{2} sin^{2} θ + (a^{2} + c^{2}) cos^{2} θ} dθ.

Since the left side is increasing as a function of b, we have equality if and only if b^{2} = a^{2} + c^{2}.

B3: For n = 1 we obviously get 45, while for n = 3 the answer is 0 because it both changes sign (because determinants are alternating) and remains unchanged (by symmetry) when you switch any two rows other than the first one. So only n = 2 is left. By the multilinearity of the determinant, the answer is the determinant of the matrix whose first (resp. second) row is the sum of all possible first (resp. second) rows. There are 90 first rows whose sum is the vector (450, 405), and 100 second rows whose sum is (450, 450). Thus the answer is 450 × 450 − 450 × 405 = 45 × 450 = 20250.

B4: The infinite continued fraction is defined as the limit of the sequence L_{0} = 2207, L_{n+1} = 2207 − 1/L_{n}. Notice that the sequence is strictly decreasing (by induction) and thus indeed has a limit L, which satisfies L = 2207 − 1/L, or rewriting, L^{2} − 2207L + 1 = 0. Moreover, we want the greater of the two roots.

Now how to compute the eighth root of L? Notice that if x satisfies the quadratic x^{2} − ax + 1 = 0, then we have

0 = (x^{2} − ax + 1)(x^{2} + ax + 1) = x^{4} − (a^{2} − 2)x^{2} + 1.

Clearly, then, the positive square roots of the quadratic x^{2} − bx + 1 satisfy the quadratic x^{2} − (b^{2} + 2)^{1/2}x + 1 = 0. Thus we compute that L^{1/2} is the greater root of x^{2} − 47x + 1 = 0, L^{1/4} is the greater root of x^{2} − 7x + 1 = 0, and L^{1/8} is the greater root of x^{2} − 3x + 1 = 0, otherwise known as (3 + \sqrt{5})/2.

B5: This problem is dumb if you know the Sprague-Grundy theory of normal impartial games (see Conway, Berlekamp and Guy, Winning Ways, for details). I’ll describe how it applies here. To each position you assign a nim-value as follows. A position with no moves (in which case the person to move has just lost) takes value 0. Any other position is assigned the smallest number not assigned to a valid move from that position.

For a single pile, one sees that an empty pile has value 0, a pile of 2 has value 1, a pile of 3 has value 2, a pile of 4 has value 0, a pile of 5 has value 1, and a pile of 6 has value 0.

You add piles just like in standard Nim: the nim-value of the composite of two games (where at every turn you pick a game and make a move there) is the “base 2 addition without carries” (i.e. exclusive OR) of the nim-values of the constituents. So our starting position, with piles of 3, 4, 5, 6, has nim-value 2 ⊕ 0 ⊕ 1 ⊕ 0 = 3.

A position is a win for the player to move if and only if it has a nonzero value, in which case the winning strategy is to always move to a 0 position. (This is always possible from a nonzero position and never from a zero position, which is precisely the condition that defines the set of winning positions.) In this case, the winning move is to reduce the pile of 3 down to 2, and you can easily describe the entire strategy if you so desire.

B6: Obviously α, β, γ have to be greater than 1, and no two can both be rational, so without loss of generality assume that α and β are irrational. Let {x} = x − ⌊x⌋ denote the fractional part of x. Then m ∈ S(α) if and only if f(m/α) ∈ (1−1/α, 1)∪{0}. In particular, this means that S(α) ∩ {1, …, n} contains ⌈(n + 1)/α⌉ − 1 elements, and similarly. Hence for every integer n,

n = ⌈\frac{n + 1}{α}⌉ + ⌈\frac{n + 1}{β}⌉ + ⌈\frac{n + 1}{γ}⌉ − 3.

Dividing through by n and taking the limit as n → ∞ shows that 1/α + 1/β + 1/γ = 1. That in turn implies that for all n,

\{−\frac{n + 1}{α}\} + \{−\frac{n + 1}{β}\} + \{−\frac{n + 1}{γ}\} = 2.

Our desired contradiction is equivalent to showing that the left side actually takes the value 1 for some n. Since the left side is an integer, it suffices to show that {−(n + 1)/α} + {−(n + 1)/β} < 1 for some n.

A result in ergodic theory (the two-dimensional version of the Weil equidistribution theorem) states that if 1, r, s are linearly independent over the rationals, then the set of points ({nr}, {ns} is dense (and in fact equidistributed) in the unit square. In particular, our claim definitely holds unless a/α + b/β = c for some integers a, b, c.

On the other hand, suppose that such a relation does hold. Since α and β are irrational, by the one-dimensional Weil theorem, the set of points ({−n/α}, {−n/β} is dense in the set of (x, y) in the unit square such that ax + by is an integer. It is simple enough to show that this set meets the region {(x, y) ∈ [0, 1]^{2} : x + y < 1} unless a + b is an integer, and that would imply that 1/α + 1/β, a quantity between 0 and 1, is an integer. We have our desired contradiction.