Darij Grinberg - Solutions to review problems

Solutions to review problems

This page is going to contain some of the solutions I submit to mathematical periodicals with problem sections such as Mathematical Reflections and The American Mathematical Monthly. Problems are usually rewritten in order to avoid excessive quoting and often to homogenize the notations used in a problem and its solution.

I don't put up solutions on this site prior to the discussion of the problem in the respective magazine, so usually they won't appear here directly after the deadline is over.

Mathematical Reflections

Solution to: Darij Grinberg, Problem U275, Mathematical Reflections 4/2013.
My solution as a PDF file. Sourcecode.
Let μ be the number-theoretical Möbius function. Let a_f be a real number for every positive integer f. Prove that
the sum of (μ(g)/g) de a_de/g over all d | m, all e | n and all g | gcd(d, e)
= the sum of f a_f over all f | mn.

Solution to: Darij Grinberg, Problem U228, Mathematical Reflections 2/2012. (Link to the solution. For the problem see 2/2012.)
My solution as a PDF file, including two unpublished alternative solutions and a generalization.
Let L/K be a separable algebraic extension of fields and let V, W and U be L-vector spaces.
Let h : V × W -> U be a K-bilinear map satisfying
h(xa, xb) = x² h(a, b) for every x ∈ L, a ∈ V and b ∈ W.
Prove that h is L-bilinear.
Notes: 1. The solution file contains three solutions, one of which generalizes the problem from separable algebraic field extensions to commutative separable algebras over commutative rings.
2. The problem can be discussed on MathLinks.

Solution to: Darij Grinberg, Problem O222, Mathematical Reflections 1/2012. (Link to the solution. For the problem see 1/2012.)
My solution (also the second published solution) as a PDF file.
Let n be a nonnegative integer. Consider two n-tuples (a₁, a₂, ..., a_n) and (b₁, b₂, ..., b_n) of nonnegative reals, and a permutation σ of the set {1,2,...,n}. For every k in the set {1,2,...,n}, let c_k be the maximum of the set
{a₁b_k, a₂b_k, ..., a_kb_k} ∪ {a_kb₁, a_kb₂, ..., a_kb_k}.
Prove that a₁b_σ(1) + a₂b_σ(2) + ... + a_nb_σ(n) ≤ c₁ + c₂ + ... + c_n.
Note: The solution file contains some background on this problem.

Solution to: Gabriel Dospinescu, Problem O219, Mathematical Reflections 1/2012. (Link to the solution. For the problem see 1/2012.)
My solution (also the second published solution) as a PDF file.
Let a, b, c, d be positive reals such that (1-c)/a + (1-d)/b + (1-a)/c + (1-b)/d ≥ 0. Prove that a(1-b) + b(1-c) + c(1-d) + d(1-a) ≥ 0.

Solution to: Titu Andreescu, Problem U111, Mathematical Reflections 1/2009. (Link to the solution. For the problem see 1/2009.)
My solution (also the second published solution) as a PDF file.
Let n be a positive integer. For every k in {0, 1, ..., n-1}, let a_k = 2 cos(π / 2^n-k). Prove that product_{k=0}^{n-1} (1-a_k) = (-1)^n-1 / (1 + a₀).

Solution to: Cezar Lupu and Valentin Vornicu, Problem U112, Mathematical Reflections 1/2009. (Link to the solution. For the problem see 1/2009.)
My solution (also the first published solution) as a PDF file.
Let x, y, z be real numbers greater or equal to 1. Prove that x^{x³+2xyz} y^{y³+2xyz} z^{z³+2xyz} ≥ (x^xy^yz^z)^yz+zx+xy.
Solution to: Titu Andreescu, Problem O111, Mathematical Reflections 1/2009. (Link to the solution. For the problem see 1/2009.)
My solution (also the second published solution) as a PDF file.
Prove that, for each integer n ≥ 0, the number (binom(n,0) + 2 binom(n,2) + 2² binom(n,4) + ...)² (binom(n,1) + 2 binom(n,3) + 2² binom(n,5) + ...)² is triangular.
Here, binom(n,m) means the (n,m)-th binomial coefficient (that is, n(n-1)...(n-m+1) / m! if m ≥ 0, and 0 otherwise).

Solution to: Cezar Lupu and Pham Huu Duc, Problem O112, Mathematical Reflections 1/2009. (Link to the solution. For the problem see 1/2009.)
My solution (not published) as a PDF file.
Let a, b, c be positive real numbers. Prove that
(a³+abc) / (b+c)² + (b³+abc) / (c+a)² + (c³+abc) / (a+b)² ≥ 3/2 · (a³+b³+c³)/(a²+b²+c²).

Solution to: Gabriel Dospinescu, Problem O114, Mathematical Reflections 1/2009. (Link to the solution. For the problem see 1/2009.)
My solution (also the first published solution) as a PDF file.
Prove that for all real numbers x, y, z, the following inequality holds:
(y²+yz+z²) (z²+zx+x²) (x²+xy+y²) ≥ 3(x²y+y²z+z²x) (xy²+yz²+zx²).

The American Mathematical Monthly

Solution to: Anon, Problem A5715, AMM February 1970, in a generalized version.
My solution as a PDF file.
(Generalized statement:) Let R be a commutative ring with unity. Let a₁, a₂, ..., a_n as well as b₁, b₂, ..., b_n be elements of R such that a₁ b₁ + a₂ b₂ + ... + a_n b_n = 1, and such that any two indices i and j with i < j satisfy b_i b_j = 0.
Let T be a free R-module with basis (e₁, e₂, ..., e_n). Let S be the R-submodule of T generated by b₁ e₁, b₂ e₂, ..., b_n e_n. Show that T/S is a free R-module of rank n-1.
Solution to: Marian Tetiva, Problem 11391, AMM November 2008.
My solution as a PDF file. Longer (more detailed) version.
Let p be some prime, s some positive integer. Also, let k and n be integers such that n ≥ k ≥ p^s - p^s-1. Let x₁, x₂, ..., x_n be integers. Assume that (p,s,k) ≠ (2,2,2) and (s,k) ≠ (1,p-1). Prove that both of the sums
sum of ( (-1)^j · (binomial coefficient (n-k+j) over j) · (number of all (k-j)-element subsets T of {1,2,...,n} such that the sum of x_t over all t in T is divisible by p) ) over j = 0, 1, ..., k
and
sum of ( (-1)^j · (binomial coefficient (n-k+j) over j) · (number of all (k-j)-element subsets T of {1,2,...,n} such that the sum of x_t over all t in T is not divisible by p) ) over j = 0, 1, ..., k
are divisible by p^s.
Solution to: Omran Kouba, Problem 11392, AMM November 2008.
My solution as a PDF file.
A point M in the plane of a regular n-gon P is orthogonally projected onto each side of this n-gon. Assume that these projections all lie inside the respective sides of the n-gon. Then, the n segments joining M to the vertices of P, as well as the n segments joining M to these projections, subdivide the n-gon P into 2n triangles. We label these triangles by 1, 2, ..., 2n in a counterclockwise way. Prove that the sum of the areas of the triangles with odd labels is half the area of P.

Solution to: Cosmin Pohoata, Problem 11393, AMM November 2008.
My solution as a PDF file.
In triangle ABC, let M and Q be points on the segment AB, let N and R be points on the segment CA, and let P and S be points on the segment BC. Denote m = BM / MA, n = CN / NA, p = CP / PB, q = AQ / QB, r = AR / RC, s = BS / SC. Prove that the lines MN, PQ and RS are concurrent if and only if mpr + nqs + mq + nr + ps = 1.
Solution to: M. Farrokhi D.G., Problem 11395, AMM November 2008.
My solution as a PDF file.
Let G be the group of all continuous bijections of [0,1] to itself. If H is a finite subgroup of G, then prove that |H| = 1 or |H| = 2.
Solution to: Stanley Huang, Problem 11398, AMM December 2008.
My solution as a PDF file.
If the incenter I of a triangle ABC is equidistant from the orthocenter and the circumcenter, then prove that the middle-sized angle of triangle ABC is 60 degrees, and that the circumradius of triangle IBC equals to that of triangle ABC (if A is the vertex of triangle ABC with the middle-sized angle).
Solution to: Marius Cavachi, Problem 11401, AMM December 2008.
My solution as a PDF file.
Let A be a nonsingular square matrix whose entries are integers. Suppose that for every positive integer k, there is a matrix X with integer entries such that A = X^k.
Prove that A is the identity matrix.

Solution to: Catalin Barboianu, Problem 11402, AMM December 2008.
My solution as a PDF file.
Given a continuous function f from [0, 1] to the set of nonnegative reals such that f(0) = f(1) = 0 and every 0 < x < 1 satisfies f(x) > 0. Prove that there exists a square which has two of its vertices in the interval (0,1) on the x-axis and its other two vertices on the graph of f.
Solution to: Yaming Yu, Problem 11403, AMM December 2008.
My solution as a PDF file. Longer (more detailed) version.
For every nonnegative integer n, find the degree of the polynomial
sum of ( (binomial coefficient n over i) (-x)^n-i (x+0) (x+1) ... (x+i-1) ) over i = 0, 1, ..., n
in the variable x over the field of rational numbers.
Solution to: A. A. Dzhumadil'daeva, Problem 11406, AMM January 2009.
My solution as a PDF file. Longer (more detailed) version.
For any positive integer n, prove that
sum of ( (binomial coefficient n over i) · (2i-1)!! · (2(n-i)-1)!! ) over (i = 0, 1, ..., n) = 2ⁿ n!,
where k!! denotes the product of all elements of the set {1, 2, ..., k} which have the same parity as k (in particular, 0!! = (-1)!! = 1).
Solution to: Erwin Just, Problem 11407, AMM January 2009.
My solution as a PDF file. Longer (more detailed) version.
If p is a prime greater than 3, show that every ring R (not necessarily commutative, and possibly even without unity) which satisfies x¹ + x³ + x⁵ + ... + x^2p-1 = 0 for every x in R must be the trivial ring (i. e. the ring with one element only).
Solution to: Paolo Perfetti, Problem 11409, AMM January 2009.
My solution as a PDF file.
For positive reals α and β satisfying β > α, prove that the limit of
sum of ( n (log n) (-1)ⁿ (product of (α + k log k) / (β + (k+1) log (k+1)) over k = 2, 3, ..., n) over n = 2, 3, ... N)
for N → ∞ exists.

Solution to: Finbarr Holland, Problem 11415, AMM February 2009.
My solution as a PDF file. Warning: it's very long and boring (because written down with maximal detail - I really had to do this to get sure it was right).
Show that the determinant of the sum of n positive-definite Hermitian complex 2x2 matrices is greater or equal to the sum of their largest eigenvalues times the sum of their smallest eigenvalues. (Actually, the problem states this in a slightly different way, but that's the main point.)
If my solution is correct, it renders the "positive-definite" condition useless. In order to make sure it is correct, I have written out every single step of the proof, but a residual uncertainty remains. You should best scroll down to Lemma 2 (it's on page 14) immediately after reading Lemma 1, because the proof of Lemma 1 is well-known.

Solution to: Cezar Lupu and Tudorel Lupu, Problem 11417, AMM February 2009.
My solution as a PDF file.
Given a real-valued continuously differentiable function f on the interval [0,1] such that the integral of f(x)dx from 1/3 to 2/3 equals 0. Prove that
(integral of (f '(x))²dx from 0 to 1) ≥ 27 (integral of f(x)dx from 0 to 1)².
Solution to: Christopher Hillar, Problem 11422, AMM March 2009.
My solution as a PDF file.
Let H be a real symmetric square matrix whose eigenvalues are pairwise distinct. Let A be a real matrix of the same size. Let H₀ = H, let H₁ = AH₀ - H₀A and let H₂ = AH₁ - H₁A. Assume that the matrices H₁ and H₂ are symmetric. Prove that AA^t = A^tA (in other words, prove that the matrix A is normal).
Solution to: Emeric Deutsch, Problem 11424, AMM March 2009.
My solution as a PDF file. Longer (more detailed) version.
Given some integer n > 1, compute the number of all elements (a₁,a₂,...,a_n) of {0,1}ⁿ for which the number of all i in {1,2,...,n-1} satisfying a_i = a_i+₁ = 0 equals the number of all i in {1,2,...,n-1} satisfying a_i = a_i+₁ = 1.
Solution to: M. L. Glasser, Problem 11426, AMM April 2009.
My solution as a PDF file.
Simplify Γ(1/14) Γ(9/14) Γ(11/14) / (Γ(3/14) Γ(5/14) Γ(13/14)), where Γ denotes the gamma function.
Solution to: Marius Cavachi, Problem 11433, AMM May 2009.
My solution as a PDF file.
Let n be a positive integer. Let A₁, A₂, ..., A_n, B₁, B₂, ..., B_n, C₁, C₂, ..., C_n be 3n points on the unit sphere S². Prove that there exists a point P on S² satisfying
(sum of |P-A_k|² over k = 1, 2, ..., n) = (sum of |P-B_k|² over k = 1, 2, ..., n) = (sum of |P-C_k|² over k = 1, 2, ..., n).
Solution to: Slavko Simic, Problem 11434, AMM May 2009.
My solution as a PDF file. Longer (more detailed) version.
Let n be an integer such that n ≥ 2. Let x₁, x₂, ..., x_n be distinct real numbers, and let p₁, p₂, ..., p_n be positive numbers such that p₁ + p₂ + ... + p_n = 1. Prove that the fraction
((p₁x₁³ + p₂x₂³ + ... + p_nx_n³) - (p₁x₁ + p₂x₂ + ... + p_nx_n)³) / (3 ((p₁x₁² + p₂x₂² + ... + p_nx_n²) - (p₁x₁ + p₂x₂ + ... + p_nx_n)²))
is not smaller than the smallest of the numbers x₁, x₂, ..., x_n, but not greater than the greatest of these numbers either.
Solution to: Panagiote Ligouras, Problem 11435, AMM May 2009.
My solution as a PDF file.
For every triangle with sidelengths a, b, c, inradius r and circumradius R, prove that
a²bc / ((a+b)(a+c)) + b²ca / ((b+c)(b+a)) + c²ab / ((c+a)(a+b)) ≤ 9/2 r R.
Solution to: Greg Oman, Problem 11451, AMM 2009.
My solution as a PDF file.
Let k and n be positive integers satisfying k > 1. Let R be a ring (not necessarily having an identity, and not necessarily commutative). Assume that:
(i) There exists an element of R which is not nilpotent.
(ii) If x₁, x₂, ..., x_k are any k nonzero elements of R, then x₁ⁿ + x₂ⁿ + ... + x_kⁿ = 0.
Prove that R is a division ring, that is, the nonzero elements of R form a group under multiplication.
Solution to: Donald Knuth, Problem 11452, AMM 2009.
My solution as a PDF file.
Let n be a positive integer.
We identify every permutation π ∈ S_n with the n-letter string π(1) π(2) ... π(n) over the alphabet {1,2,...,n}. Let us say that two permutations a₁a₂...a_k-1a_ka_k+1...a_n and a_ka_k-1...a₂a₁a_k+1...a_n (written as n-letter strings) are pre-equivalent when k = n or when a_k+1 exceeds all of a₁, a₂, ..., a_k. Also we say that two permutations in S_n are equivalent whenever they can be obtained from each other by a sequence of such flips (i. e., we define the relation ”equivalent” to be the reflexive, symmetric and transitive closure of the relation ”pre-equivalent”). For example, 321 ≡ 123 ≡ 213 ≡ 312 and 132 ≡ 231 in S₃.
Show that the number of equivalence classes of permutations in S_n is equal to the n-th Euler secant-and-tangent number for every n. (The n-th Euler secant-and-tangent number is defined as the number of ”up-down” permutations of length n, by which we mean permutations like 25341 (written as strings) that alternately rise and fall beginning with a rise.)
Solution to: Richard Stanley, Problem 11453, AMM 2009.
My solution as a PDF file. Longer (more detailed) version.
(Generalized version of the problem:) Let Δ be a finite collection of finite sets. Assume that every subset of every set which lies in Δ must itself lie in Δ. Let k be a nonnegative integer such that every G in Δ such that |G| ≤ k satisfies
2^k+1-|G| | (sum of (-1)^|F| over all F in Δ such that G is a subset of F).
Then, prove that 2^k+1 | |Δ|.
Solution to: Cezar Lupu and Vicentiu Radulescu, Problem 11458, AMM October 2009.
My solution as a PDF file.
Let a₁, a₂, ..., a_n be nonnegative reals, and r be a positive integer. Prove that
(sum of (i^rj^ra_ia_j) / (i+j-1) over all 1 ≤ i,j ≤ n)² ≤ (sum of m^r-1a_m over all m = 1,2,...,n) · (sum of (i^rj^rk^ra_ia_ja_k) / (i+j+k-2) over all 1 ≤ i,j,k ≤ n).

One day I might add a solution to #11397 (I am still pondering whether to write up a proof of Karamata...).

Project PEN (Problems in Elementary Number Theory)

Solution to: Problem E16, a. k. a.: Mathematics Magazine, Problem 1392 by George Andrews.
(This links to my solution on the PEN server. A local version can be found here: Solution to Project PEN Problem E 16.)

If n is a positive integer, and p is a prime lying in the interval ]n, 4n/3], then prove that p divides sum_{j=0}^{n} binom(n,j) ⁴, where binom(n,j) means n! / (j! (n-j)!).

My solution (which generalizes the problem three times) is an edited and extended version of my posting in MathLinks topic #150539 (which only generalizes it one time).
Other PEN solutions posted by me on MathLinks. You can find them all on the MathLinks forum in a better readable format; I am just including them here for the sake of completeness.

Octogon

This was a Vietnamese project at creating a journal for mathematical problems. Sadly, it has not kicked off.

A modulus and square root inequality.
PDF file. Also, the sourcecode.

For any four reals a, b, c, d, prove that

|a + b - c - d| + |a + c - b - d| + |a + d - b - c| ≥ |sqrt(a² + b²) - sqrt(c² + d²)| + |sqrt(a² + c²) - sqrt(b² + d²)| + |sqrt(a² + d²) - sqrt(b² + d²)|.

Problems from the Book (diverse mathematical problems)

Solution to: Problem 19.9.
PDF file.

Let n be a positive integer. Let w₁, w₂, ..., w_n be n reals. Prove the inequality

sum_{i=1}^{n} sum_{j=1}^{n} ijw_iw_j / (i+j-1) ≥ (sum_{i=1}^{n} w_i)².

Click here for a longer and more complete version of the solution. (Warning: the completeness comes at the cost of readability.)

QED-Mathematikolympiade (click here for a description of this context)

Solutions to several problems in German

Solution to 4th QEDMO, Problem 13.
PDF file.
This is a more detailed and (in my opinion) more readable version of the solution which I posted on MathLinks. Click on this link to see other solutions as well.

Let n and k be integers such that 0 ≤ k ≤ n. Prove that

sum_{u=0}^{k} ((n+u-1) binom u) (n binom (k-2u)) = ((n+k-1) binom k).

Here, (a binom b) means the binomial coefficient a! / (b! (a-b)!) if 0 ≤ b ≤ a, and 0 otherwise.

Solution to 7th QEDMO, Problem 8 (a slight extension of American Mathematical Monthly problem #E2353 by J. G. Rau).
PDF file.
Long version, for verification purposes rather than for reading.

Let (a₁, a₂, ..., a_n) be an n-tuple of reals. Let (b₁, b₂, ..., b_n) be an n-tuple of positive reals. We are searching for a permutation π of the set {1,2,...,n} that minimizes the sum

a_π₍₁₎ (b_π₍₁₎+b_π₍₂₎+...+b_π_(n)) + a_π₍₂₎ (b_π₍₂₎+b_π₍₃₎+...+b_π_(n)) + ... + a_π_(n) b_π_(n).

Prove that any permutation π that satisfies a_π₍₁₎ / b_π₍₁₎ ≤ a_π₍₂₎ / b_π₍₂₎ ≤ ... ≤ a_π_(n) / b_π_(n) minimizes this sum.

Solution to 6th QEDMO 2009, Problem 4 (the Cauchy identity) .
PDF file.

[Boring and close to unreadable. I wrote it only to make sure my solution holds before proposing the problem in a contest.]

Other problems and solutions

At least |S|^k-1 · (|S| - 1) frontiers: a graph theory problem.
PDF file. Also, the sourcecode.

Let S be a finite set, and k be a positive integer. Let A be a subset of S^k satisfying |A| = |S|^k-1. Let B = S^k \ A. We let F be the set of all pairs (a, b) ∈ A × B such that the k-tuples a and b differ in at most one entry. Prove that |F| ≥ |S|^k-1 · (|S| - 1).

All sources: Mathematical Reflections, American Mathematical Monthly, QEDMO, PFTB and PEN.

Solutions to review problems

Back to the main site

Darij Grinberg