IMO 1995 Problem 6

The question is:

If $p$ is an odd prime, find the number of subsets of size exactly $p$ of $S = \{1,2, \dots, 2p\}$, the sum of whose elements is divisible by $p$.

On the actual test, very few students solved it. That to me is a bit surprising, but seems like the problem setters predicted well! P6 is supposed to be the hardest problem and performance of the students does indicate that to be true, and they were right in selecting this problem as P6.

Anyway.

Scroll down for a solution.

.

.

.

.

.

This seems like a textbook generating functions question, hence my surprise. Generating functions were part of the IMO toolkit in 1995. Anyway. below is one way to use generating functions.

Solution:

Consider the function

$$f(t,x) = (t + x) (t + x^2) \dots (t + x^{2p})$$

If you look at this as a polynomial in $t$, then the coefficient of $t^{2p - m}$ is a polynomial in $x$, whose $N^{th}$ coefficient (i.e coefficient of $x^N$) tells us how many $m$ elements subsets of $S$ sum to $N$.

Thus we need to look at the polynomial in $x$ which is the coefficient of $t^p$ in $f(t,x)$ and then extract the sum of coefficients of $x^0, x^{p}, x^{2p}, \dots $ from that.

For sake of simplicity let us find the polynomial in $x$ that is the sum of coefficients of $t^{0}, t^{p}, t^{2p}$ and then adjust accordingly.

Now the sum of coefficients of $t^{0}, t^{p}, t^{2p}$  is

$$P(x) = \frac{1}{p} \sum_{n = 0}^{p-1} f(w^n, x)$$

where $w$ is a primitive $p^{th}$ root of unity. 

The sum of coefficients of $x^{kp}$ in $P(x)$ computes the number of subsets of $S$ whose sum and size are both divisible by $p$. The answer for the problem as asked will be $2$ less than this number (the empty set and $S$ itself).

Now the sum of coefficients of $x^{kp}$ in $P(x)$ is again, using the primitive $p^{th}$ root of unity:

$$\frac{1}{p} \sum_{m=0}^{p-1} P(w^m)$$

$$ = \frac{1}{p^2} \sum_{m=0}^{p-1} \sum_{n=0}^{p-1} f(w^n, w^m)$$

Now we have that $$f(t,1)  =(t+1)^{2p}$$  and for $0 < m \leq p-1$, $$f(t, w^m) = ((-t)^p - 1)^2  = t^{2p} +2t^p + 1$$

Because $t^p - 1 = (t - 1)(t-w)\dots (t - w^{p-1})$ and so $(-t)^p - 1 = (-1)^p (t +1) (t+w) \dots (t + w^{p-1})$. We also have $w^{p+k} = w^k$.

Thus $f(w^n, w^m) = 4$ for $m \neq 0$.

So, by splitting $m=0$ and $m > 0$, we get

$$  \frac{1}{p^2} \sum_{m=0}^{p-1} \sum_{n=0}^{p-1} f(w^n, w^m)$$

$$  = \frac{1}{p^2} \sum_{n=0}^{p-1} (1 + w^n)^{2p} + \frac{p-1}{p^2} \sum_{n=0}^{p-1} 4$$

Now $$\frac{1}{p} \sum_{n=0}^{p-1} (w^n + 1)^{2p}$$ 

is again, just the sum of coefficients of $x^{kp}$ in $(1 + x)^{2p}$, which is $2 + \binom{2p}{p}$

Thus we get

$$\frac{2 +\binom{2p}{p}}{p} + \frac{4p - 4}{p} $$

$$ = \frac{\binom{2p}{p} - 2}{p} + 4$$

Thus after subtracting $2$ to get what the problem seeks, we get the final answer as

$$\boxed{\frac{\binom{2p}{p} - 2}{p} + 2}$$

Inverting the matrix $A[r,c] = \frac{1}{r + c}$

 Suppose $A$ is an $n \times n$  matrix defined by

$$A[r,c] = \frac{1}{r+c}, \quad 1 \le r \le n, 1 \le c \le n$$

i.e the entry in the $r^{th}$ row and $c^{th}$ column is $\frac{1}{r+c}$.

i.e

$$ A = \begin{bmatrix} \frac{1}{2} & \frac{1}{3} & \dots & \frac{1}{n+1}\\ \vdots & \vdots & \dots & \vdots\\ \frac{1}{n+1} & \frac{1}{n+2} & \dots & \frac{1}{2n} \end{bmatrix}$$

Determine the inverse of $A$.

Scroll down for a (somewhat suprising) solution.

.

.

.

.

.

Solution:

[In the below $m$ and $i$ will denote a row index and $k$ and $j$ a column index (instead of $r$ and $c$).]

Fix a $k$ ($ 1 \le k \le n$).

The $k^{th}$ column of the inverse is the solution $(a_1, a_2, \dots, a_n)$ to the system of $n$ equations

$$ \sum_{j = 1}^{n} \frac{a_j}{m + j} = \delta_{mk} ,\quad 1 \le m \le n$$

where $$\delta_{mk} = \begin{cases} 0 & m \neq k \\ 1 & m = k \end{cases}$$

$\delta_{mk}$ are the entries of the identity matrix, basically and the LHS in the above is the dot product of the $m^{th}$ row of $A$ and $k^{th}$ column of $A^{-1}$.

Now consider 

$$f(x) = \sum_{j=1}^{n} \frac{a_j}{x + j} = \frac{P(x)}{Q(x)}$$

where $P(x)$ is an $(n-1)^{th}$ degree polynomial and $Q(x) = (x+1)(x+2)\dots (x+n)$.

The $n$ equations (with $\delta_{mk}$) basically mean that $1, 2, \dots, k-1, k+1, \dots, n$ are roots of $P(x)$.

Let $R(x) = (x-1)(x-2)\dots(x-n)$. Then we must have that

$$P(x) = A\frac{R(x)}{x - k}$$ 

for some constant $A$.

We also have $P(k) = Q(k)$  (because $f(k)  = \delta_{kk} = 1$) and thus $$Q(k) = P(k) =  \lim_{x \to k} A\frac{R(x)}{x-k} = A R'(k)$$

Which implies $$A = \frac{Q(k)}{R'(k)}$$

$R'(x)$ being the derivative of $R(x)$.

Thus we get the formula

$$ f(x) = \sum_{j=1}^{n} \frac{a_j}{x+j} = \frac{Q(k) R(x)}{R'(k)(x-k)Q(x)}$$ 

Now just looking at

$$ f(x) = \sum_{j=1}^{n} \frac{a_j}{x+j}$$

we get

 $$a_m = \lim_{x \to -m} f(x) (x+m)$$

i.e

$$a_m = \frac{Q(k)}{R'(k)} \lim_{x \to -m} \frac{R(x) (x+m)}{(x-k) Q(x)}$$

Now $$\lim_{x \to -m} \frac{x+m}{Q(x)} = \frac{1}{Q'(-m)}$$

Thus we get

$$a_m = -\frac{Q(k) R(-m)}{(m+k) R'(k) Q'(-m)}$$

Thus the inverse matrix $A^{-1}$ satisfies

$$A^{-1}[m, k] = -\frac{Q(k) R(-m)}{(m+k) R'(k) Q'(-m)}$$

Remember, $Q(x) = (x+1)(x+2)\dots (x+n)$ and $R(x) = (x-1)(x-2)\dots(x-n)$.

It turns out that we can rewrite the above as products of binomial coefficients, and they are all integers!

$\textbf{Additional Remarks:}$ Apparently our $A$ is a special case of a Cauchy Matrix, where $A[i,j] = \frac{1}{x_i - y_j}$ and a method similar to above works for the general case too and was solved in 1959!

Average Sum of Distances

 Given $n$ numbers $0 \le x_i \le 1$, define the function $f:[0,1] \to \mathbb{R}$ as

$$f(x) = \frac{1}{n} \sum_{i=1}^{n} |x - x_i|$$

A) Show that there is some $a \in [0,1]$ such that $$f(a) = \frac{1}{2}$$ 

B) Show that there is some $b \in [0,1]$ such that 

$$f(b) = \frac{1}{2} - \frac{1}{n} \sum_{i=1}^{n} (x_i- x_i^2)$$

Scroll down for a solution.

.

.

.

.

.

Solution:

A) Notice that $|0 - x_i| + |1 - x_i| = 1$ and thus we have that $f(0) + f(1) = 1$.  If $f(0) \leq \frac{1}{2}$ then $f(1) \geq \frac{1}{2}$ and by the intermediate value theorem, there is some $a \in [0,1]$ such that $f(a) = \frac{1}{2}$. Other cases are similar.

B) By the mean value theorem, there is some $b \in [0,1]$ such that

$$f(b) = \int_{0}^{1} f(x) dx$$

Turns out that

$$\int_{0}^{1} f(x) dx = \frac{1}{2} - \frac{1}{n} \sum_{i=1}^{n} (x_i- x_i^2)$$

It is the sum of right angled triangle areas of legs $x_i, x_i$ and $(1-x_i), (1-x_i)$. 

$\textbf{Additional Remark:}$ Result in part B can easily be used to show that if $f(x) \ge \frac{1}{2} \forall x \in [0,1]$, then $n$ must be even, with half the $x_i = 0$ and the rest $ = 1$, and $f$ a constant $= \frac{1}{2}$.

Quadratic root in $(0,1)$

 A nice little problem from the IIT JEE exam.

$a,b,c$ are real numbers such that $$2a + 3b + 6c = 0$$

Show that $ax^2 + bx + c = 0$ has a root in the interval $(0,1)$

Scroll down for a short solution.

.

.

.

.

Solution:

Consider $$ f(x) = 2a x^3 + 3bx^2 + 6cx + d$$

We have that $f(0) = d$ and $f(1) = d$. Thus by Rolle's theorem, there is some $\eta \in (0,1)$ such that $f'(\eta) = 0$.

Now $f'(x) = 6ax^2 + 6bx + 6c = 6(ax^2 + bx + c)$. 

Thus $a\eta^2 + b\eta + c = 0$ and we are done!

Exploding cyclic differences

You have $n > 1$  numbers $a_1, a_2, \dots, a_n$.

At each step, you replace $$a_1, a_2, \dots, a_n$$ with $$a_1 - a_n, a_2 - a_1, a_3 - a_2, \dots, a_n - a_{n-1}$$

Now starting initially with $$a_1, a_2, \dots, a_n = 1, 0, 0, \dots, 0$$ you continue the above step $N$ times.

Let $S_N$ be the largest among the absolute values of the resulting $n$ numbers.

Show that there is a real number $\beta \ge \sqrt{2}$ (independent of $N$), such that

$$ S_N \ge \dfrac{\beta^N}{n}$$

i.e some of the numbers become exponentially large (could be negative), even though the total sum is $0$.

Scroll down for a solution.

.

.

.

.

.

.

We use complex numbers!

Since $n > 1$, we can find an $n^{th}$ root of unity $\zeta$, such that $ |\zeta - 1| \ge \sqrt{2}$.

 We can easily see this geometrically: $ |\zeta - 1|$ is the distance between $\zeta$ and $1$, so we just pick one of the vertices of the $n$-gon formed by the $n^{th}$ roots of unity that lies in the positive $y$ and negative $x$ quadrant.

Now given the state of numbers after $m$ steps as $a_1, a_2, \dots a_n$ define $$ V_m = \sum_{k=1}^{n} a_k \zeta^{k-1}$$

Note that $$|V_m| \le \sum_{k=1}^{n} |a_k \zeta^{k-1}| \le n S_m$$

Now consider 

$$V_m (1 - \zeta) = \sum_{k=1}^{n} a_k \zeta^{k-1} - \sum_{k=1}^{n} a_k \zeta^k $$

$$ = \sum_{k=1}^n (a_k - a_{k-1}) \zeta^{k-1} = V_{m+1}$$

with the convention that $a_{0} = a_n$ and using the fact that $\zeta^n = 1$.

Thus we have that $$V_{m+1} = V_m (1 - \zeta)$$

Now $V_0 = 1$ and therefore we have that

$$V_N = (1 - \zeta)^N$$

Thus we have that

$$n S_N \ge |V_N| = |1 - \zeta|^N $$

i.e.

$$ S_N \ge \dfrac{\beta^N}{n}$$

where $\beta = |1 - \zeta| \ge \sqrt{2}$.

$\textbf{Additional Remarks (Getting a Formula):}$

In fact, we can show that we can read off the exact values we get after $N$ steps, from the coefficients in the expansion of $(1 - x)^N$, subject to collapsing higher degree terms with $x^n = 1$, $x^{n+1} = x$ etc. 

Since the transformations are linear and $1,0,\dots,0$ is a cyclic shift of $0,\dots,1\dots, 0$, this is enough to give a general formula starting with any initial set of numbers.

Another approach to get a formula is to just use matrices and diagonalize/convert to jordan normal form etc.

Yet another approach is to view the cyclic sequence $a_1, a_2, \dots a_n$ as the infinite sequence $a_1, a_2, \dots, a_n, a_1, a_2, \dots, a_n, a_1, a_2 \dots $ and apply the forward difference formula, and replacing $a_{kn + r}$ with $a_r$.

A Nice Croatian Math Olympiad problem with $\log_k$ and $k^{th}$ roots

 For a positive integer $n \ge 2$, prove that

$$\left[\log_2 n\right] + \left[\log_3 n\right] + \dots + \left[\log_n n\right] = \left[\sqrt{n}\right] + \left[\sqrt[3]{n}\right] + \dots + \left[\sqrt[n]{n}\right]$$

$[x]$ is the integer part of $x$

Scroll down for a solution.

.

.

.

.

.

.

Solution:

We will show that this equality is basically saying that the sum of sums of rows = sum of sums of columns in a matrix, for a certain matrix.

Consider the $n \times n $ matrix $A$ such that the entry of row $m$ and column $k$ is $1$ if $$\sqrt[m]{n} \ge k$$ and $0$ otherwise.

Since $\sqrt[m]{n} \le n$,  row $m$ has exactly $$\left[\sqrt[m]{n}\right]$$ ones

Thus the sum of sum of rows is

$$ n + \left[\sqrt{n}\right] + \left[\sqrt[3]{n}\right] + \dots + \left[\sqrt[n]{n}\right]$$

Now let us try to count the number of ones in column $k$.

For $k=1$, the numbers of ones is exactly $n$, because $\sqrt[m]{n} \ge 1$ for any $m \ge 1$.

For $k \ge 2$, number of ones will be all the $m$ that satisfy $1 \le m \le n$ and

$$ \sqrt[m]{n} \ge k$$

i.e number of $1 \le m \le n$ such that

$$ \log_k n \ge m$$

Since for $2 \le k$, $\log_k n \le n$, there are exactly $$\left[\log_k n\right]$$ ones in column $k$ 

Therefore the sum of sums of columns is

$$ n + \left[\log_2 n\right] + \left[\log_3 n\right] + \dots + \left[\log_n n\right] $$

Now equating the sum of sums of rows to the sum of sums of columns gives us the result.