Using Probabilistic Method in Algebra

$$ \newcommand\EE{\mathbb E} \newcommand\PP{\mathbb P} $$

Problem [Bay Area Math Olympiad 2004]

Suppose one is given $n$ real numbers, not all zero, such that their sum is zero. Prove that one can label these numbers $a_1, a2, \dots , a_n$ in such a manner that

$$ \begin{align} a_1a_2 + a_2a_3 + \dots + a_{n−1}a_n + a_n a_1 < 0 \end{align} $$

Solution

Let the given numbers be $b_1, \dots , b_n$. Let $b_{\pi(1)}, \dots , b_{\pi(n)}$ be a random permutation of the numbers where $\pi$ is a permutation of ${1,2,\dots, n}$.

The expected value,

$$ \begin{align} \EE(b_{\pi(1)}b_{\pi(2)} + b_{\pi(2)}b_{\pi(3)} + \dots + b_{\pi(n−1)}b_{\pi(n)} + b_{\pi(n)}b_{\pi(1)}) \
= -\frac{n(n-2)!}{n!} \sum_{i=1}^n b_i^2 < 0 \end{align} $$

which proves the existence of at least one permutation of the $n$ numbers having the requisite property.

Computational verification

from itertools import permutations
from math import factorial

n = 5
nums = {k: k for k in range(n-1)}
nums[n-1] = -1*sum(range(n-1))
cum_sum = 0
for p in permutations(range(n)):
    cum_sum += sum([nums[i]*nums[j] for i, j in zip(p, p[1:]+(p[0],))])
print(cum_sum/factorial(n), -1*sum(nums[i]**2 for i in range(n))/(n-1))

Problem [Rudin and Chinese Olympiad 1986]

Let $z_1, \dots , z_n$ be complex numbers. Show that there is a set $S \subseteq {1, \dots , n}$ such that

$$ \begin{align} |\sum_{j \in S} z_j \vert \geq \frac{1}{\pi} \sum_{j=1}^n \vert z_j \vert \end{align} $$

Solution

Write $z_k = \vert z_k \vert e^{i \alpha_k}$. For $-\pi \leq \theta \leq \pi$, let $S(\theta)$ be the set of all $k$ for which $cos(\alpha_k - \theta) > 0$. Then

$$ \begin{align} \left \vert \sum_{S(\theta)} z_k \right \vert = \left \vert \sum_{S(\theta)} e^{i\theta}z_k \right \vert \geq \textbf{Re}\sum_{S(\theta)} e^{i\theta}z_k = \sum_{k=1}^N|z_k|cos^{+}(\alpha_k - \theta) \end{align} $$

Choose $\theta_0$ so as to maximize the last sum, and put $S=S(\theta_0)$. This maximum is at least as large as the average of the sum over $[-\pi, \pi]$, and this average is $\pi^{-1}\sum \vert z_k \vert$, because

$$ \begin{align} \frac{1}{2\pi}\int_{-\pi}^{\pi}|cos^{+}(\alpha - \theta) d\theta = \frac{1}{\pi} \end{align} $$

for every $\alpha$.

Problem [Romania 2004]

Let $z_1, \dots , z_n$ be complex numbers. Prove that there exist numbers $a_1, \dots , a_n$, each $\pm1$, such that

$$ \begin{align} \vert \sum_{j=1}^n a_j z_j \vert ^2 \leq \sum_{j=1}^n \left\vert z_j \right\vert^2 \end{align} $$

Solution

It is easy to see that

$$ \begin{align} \EE[\vert \sum_{j=1}^n a_j z_j \vert ^2] = \left\vert z_j \right\vert^2 \end{align} $$

The required inequality follows from the expectation lemma.

Problem [Putnam 1947]

Given $P(z) = z^2+az+b$, a quadratic polynomial of the complex variable $z$ with complex coefficients $a, b$. Suppose that $\vert P(z) \vert = 1$ for every $z$ such that $\vert z \vert = 1$. Prove that $a = b = 0$.

Solution

Let $z$ be a random point on the unit circle.We have,

$$ \begin{align} \EE[z+\overline{z}] &= \frac{1}{2\pi}\int_0^{2\pi} 2 cos(x) dx = 0 \
\EE[z^2+\overline{z}^2] &= \frac{1}{2\pi}\int_0^{2\pi} 4 cos^2(x) dx - 2 = 0 \end{align} $$

Therefore,

$$ \begin{align} \EE[\left\vert P(z) \right\vert ^2] &= \EE[(z^2+az+b) (\overline{z}^2+a\overline{z}+b)] \
&= \EE[z^2\overline{z}^2 + a z^2 \overline{z} + b z^2 + a z \overline{z}^2 \
& + a^2 z \overline{z} + a z b + b \overline{z}^2 + ab \overline{z} + b^2] \ &= \EE[1 + a(z + \overline{z}) + b(z^2 + \overline{z}^2) \
&+ a^2 + ab(z + \overline{z}) + b^2] \
&= 1 + a^2 + b^2 = 1 \end{align} $$

From the above we can conclude that $a$ = $b$ = 0.

Problem [Putnam Feb. 1958]

If $a_0, a_1, \dots , a_n$ are real numbers satisfying

$$ \begin{align} \frac{a_0}{1} + \frac{a_1}{2} + \dots + \frac{a_n}{n + 1} = 0, \end{align} $$

show that the equation $a_0 + a_1x + a_2x^2 + \dots + a_n x^n = 0$ has at least one real root.

Solution

Let $X \sim \mathcal{U}(0,1)$. The random variable $Y = a_0 + a_1X + a_2X^2 + \dots + a_n X^n$ is non negative on $[0,1]$ and it has an expectation given by

$$ \begin{align} \EE(Y) = \EE(a_0) + a_1\EE(X) + a_2\EE(X^2) + \dots + a_n \EE(X^n) \
= \frac{a_0}{1} + \frac{a_1}{2} + \dots + \frac{a_n}{n + 1} = 0 \end{align} $$

Using the expectation lemma, the fact that the polynomial $a_0 + a_1x + a_2x^2 + \dots + a_n x^n$ is continuous on $[0,1]$ and the Intermediate Value Theorem, it is easy to see the existence of a root $x \in [0,1]$ for the equation $a_0 + a_1x + a_2x^2 + \dots + a_n x^n = 0$.

Problem

Let $p$ and $q$ be non negative numbers that add up to $1$. Let $m$ and $n$ be non negative integers. Prove that

$$ \begin{align} (1 − p^m)^n + (1 − q^n)^m \geq 1 \end{align} $$

Solution

Consider a random m-by-n matrix in which each cell is filled with a $1$ with probability $p$, and a $0$ with probability $q$.

Let $A$ be the event that every row has at least one $1$.

Probability that every column has a zero is $q^n$. Probability that a row has at least one $1$ is $1-q^n$.

Probability that every row has at least one $1$ is $\PP[A] = (1-q^n)^m$.

Let $B$ be the event that every column to have at least one $0$.

Probability that every row has a one is $p^m$. Probability that a column has at least one $0$ is $1-p^m$.

Probability that every column has at least one $0$ is $\PP[B] = (1-p^m)^n$.

$$ \begin{align} \PP(A \cup B) = 1 &= \PP(A) + \PP(B) - \PP(A \cap B) \ &= (1 − p^m)^n + (1 − q^n)^m - \PP(A \cap B) \end{align} $$

Therefore,

$$ \begin{align} (1 − p^m)^n + (1 − q^n)^m = 1 + \PP(A \cap B) \geq 1 \end{align} $$

as $\PP(A \cap B) \geq 0$.

Problem [USAMO 2012/6]

For integer $n\geq2$, let $x_1, x_2, \ldots, x_n$ be real numbers satisfying $x_1+x_2+\ldots+x_n=0$ and $x_1^2+x_2^2+\ldots+x_n^2=1$.

For each subset $A\subseteq{1, 2, \ldots, n}$, define $S_A=\sum_{i\in A}x_i$.(If $A$ is the empty set, then $S_A=0$.)

Prove that for any positive number $\lambda$, the number of sets $A$ satisfying $S_A\geq\lambda$ is at most $2^{n-3}/\lambda^2$.

For which choices of $x_1, x_2, \ldots, x_n, \lambda$ does equality hold?

Solution

As $\sum_{i=1}^n x_i = 0$ and $\sum_{i=1}^n x_i^2 = 1$, we have $\sum_{1 \leq i < j \leq n} x_ix_j = -1/2$. We have

$$ \begin{align} \EE[S_A^2] = \frac{1}{2^n} \left\{ 2^{n-1} \left(\sum_{i=1}^n x_i^2 + \sum_{1 \leq i < j \leq n}^n x_i x_j \right) \right\} = \frac{1}{4} \end{align} $$

From Markov’s inequality, we have

$$ \begin{align} \PP[S_A \geq \lambda] \leq \frac{1}{2} \PP[S_A^2 \geq \lambda^2] = \frac{1}{8 \lambda^2} \end{align} $$

Therefore the fraction of sets $A$ satisfying $S_A \geq \lambda$ is given by $2^{n-3}/\lambda^2$.

Note that if equality holds, every subset $A$ of $N$ has $S_A\in{-\lambda,0,\lambda}$.

It immediately follows that $(x_1,x_2,\ldots , x_n)$ is a permutation of $(\lambda,-\lambda,0,0,\ldots , 0)$.

Since we know that $\sum_{i=1}^{n} x_i^2=1$, we have that $\lambda=1/\sqrt{2}$.