A strange but interesting Bulgarian Olympiad problem

 The problem is interesting because the result is nice. It is strange (to me) because I have a strange proof, which I don't think I can find in an exam setting. Not sure what the official etc solutions are, but I expect it will be something much simpler.

Anyway, the problem is:

$a_n$ is a sequence such that $a_1 = 1$ and

$$a_{n+1} = \frac{n}{a_n} + \frac{a_n}{n}   \quad \forall n \ge 1$$.

Show that $[a_n^2] = n$ for $n \ge 4$.  ($[x]$ is the integer part of $x$).

Scroll down for a solution.

.

.

.

.

Let $b_n = a_n^2$, the we have that

$$b_{n+1} = \frac{n^2}{b_n} + \frac{b_n}{n^2} + 2 $$

We also have $a_4 = 2 + \frac{1}{6}$ and so $b_4 = 4 + \frac{2}{3} + \frac{1}{36}$. 

So first assume $b_n$ satisfies $n < b_n < n+1$, being true for $n=4$. Then we proceed by induction.

Let us try to find a lower bound for $b_{n+1}$

Now

$$\frac{b_n}{n^2} + \frac{n^2}{b_n} + 2 > \frac{n}{n^2} + \frac{n^2}{n+1} + 2 = n+1 + \frac{1}{n} + \frac{1}{n+1}$$

Trying the same for an upper bound we get

$$\frac{b_n}{n^2} + \frac{n^2}{b_n} + 2 < \frac{n+1}{n^2} + \frac{n^2}{n} + 2  = n + 2 + \frac{n+1}{n^2}$$

We fail to get the upper bound we need (i.e $n+2$), because the lower bound $b_n > n$ is too small for us to get something smaller than $n+2$.

Perhaps we could change $n < b_n < n+1$ to $n + c_n < b_n < n + 1$.

Notice that we got $c_n = \frac{1}{n} + \frac{1}{n-1}$ from the lower bound computations earlier.

And the bound holds for $n = 4$, so if we are able to prove the upper bound of $b_n < n+1$, we will be done.

Let us try to find $d_n$ such that

$$\frac{n+1}{n^2} + \frac{n^2}{n + d_n} + 2  = n + 2$$

If $c_n > d_n$, then we will be done, because instead of $d_n$ if we choose a bigger number, the value of the expression will decrease and this expression with $c_n$ instead of $d_n$ is an upper bound for $b_{n+1}$.

Doing a bit of algebra gives us

$$d_n = \frac{n^2 + n}{n^3 - n - 1}$$

Our $c_n$ we chose was

$$c_n = \frac{1}{n} + \frac{1}{n-1} = \frac{2n-1}{n(n-1)}$$

Since $nc_n \to 2$ while $n d_n \to 1$, we have some hope that this might work.

Now for $n > 2$, $n^3 - n - 1 > n^3 - n^2$ and so

$$d_n = \frac{n^2 + n}{n^3 - n - 1} < \frac{n^2 + n}{n^3 - n^2} = \frac{n + 1}{n(n-1)}$$

For $n > 2$, $2n - 1 > n + 1$ and so

$$ d_n < \frac{n+1}{n(n-1)} < \frac{2n-1}{n(n-1)} = c_n$$

And so we  have the following:

$$n < n + d_n < n + c_n < b_n < n + 1$$

which holds for $n = 4$. And by induction we prove that

$$ n + 1 + c_{n+1} < b_{n+1} < n + 2$$

Thus for $n \ge 4$, $$[a_n^2] = [b_n] = n$$

Periodicity of integer parts of n!/e.

Follow up of the previous puzzle.

Let $M$ be a given positive integer $ > 1$. Let $$S_n = \left\lfloor \frac{n!}{e} \right\rfloor$$

Show that sequence $S_0, S_1, S_2, \dots$ is periodic $\mod M$ with period $2M$.

i.e show that $S_{n+2M} = S_n \mod M$

Scroll down for a solution.

.

.

.

.

Based on the previous puzzle solution, we have that

$$S_n = n! \sum_{k=1}^{m} \frac{2k}{(2k+1)!}$$

where $2m+1$ is the largest odd number $\leq n$.

From this, we can easily derive the following recurrence

$$\begin{aligned}& S_{2n+1} = (2n+1) S_{2n} + 2n \\& S_{2n} = 2n S_{2n-1} \end{aligned}$$

First notice that for any $k \ge 0$,  $S_{2kM} = 2kM S_{2M-1} = 0 \mod M$.

Now an induction like argument (on $(k,r)$) shows that $S_{2kM + r} \mod M$ is independent of $k$ and thus $S_n \mod M$ is periodic with period $2M$

Integer part of n!/e

 This is a classic puzzle. I am hoping the solution is new (unlikely though). Anyway.

The problem is: 

Show that the integer part of  $\dfrac{n!}{e}$ is always an even number, for positive integer $n$.

Scroll down for a solution.

.

.

.

.

.

We will use the following two:

$\textbf{Claim 1}$: 

$$\frac{1}{e} = \sum_{n=1}^{\infty} \frac{2n}{(2n+1)!}$$

$\textbf{Proof:}$

Use

$$\frac{1}{(2n)!} - \frac{1}{(2n+1)!} = \frac{2n}{(2n+1)!}$$

and $$e^x = 1 + \frac{x}{1!} + \frac{x^2}{2!} + \dots $$

(put $x = -1$ above). 

$\textbf{Claim 2}$:

$$\sum_{k = 1}^{n} \frac{a_k - 1}{a_1 a_2 \dots a_k} = 1 - \frac{1}{a_1 a_2 \dots a_n}$$

$\textbf{Proof:}$ Telescoping.

$$ \frac{a_n - 1}{a_1 a_2 \dots a_n} = \frac{1}{a_1 a_2 \dots a_{n-1}} - \frac{1}{a_1 a_2 \dots a_n}$$

Now back to the problem. 

$$\frac{N!}{e} = \sum_{n=1}^{\infty} \frac{2n N!}{(2n+1)!}$$

If $M = 2m+1$ is the largest odd integer $\leq N$ then we have

$$\frac{N!}{e} = \sum_{n=1}^{m} 2n \frac{N!}{(2n+1)!} + N! \sum_{n=m+1}^{\infty} \frac{2n}{(2n+1)!}$$ 

The first $\sum_{n=1}^{m}$ term is an even integer and the second term

$$N! \sum_{n=m+1}^{\infty} \frac{2n}{(2n+1)!} < \sum_{n=m+1}^{\infty} \frac{2n}{(2m+3)(2m+5)\dots(2n+1)} = 1$$

The equality of $1$ is because of claim 2 above (put $a_1, a_2, \dots = 2m+3, 2m+5, \dots$). 

Thus the integer part of $\frac{N!}{e}$ is an even integer. 

$\textbf{Additional Remarks:}$ Note that the above proof can be easily modified to give the following recurrence relation for $S_n = \lfloor n!/e \rfloor$.

$$\begin{aligned}&S_{2n+1} = (2n+1) S_{2n} + 2n \\ &  S_{2n} = 2n S_{2n-1}\end{aligned}$$

which yields the sequence $$0,0,2,8,44, 264, 1854, \dots$$

OEIS entry is here.

Starting Decimal Digits of Integer Square Roots

 Here is a cute result.

Given a finite string of digits $S = a_1 \dots a_k$, show that there is a positive integer $N$ such that the fractional part of $\sqrt{N}$ is of the form $0.S... = 0.a_1 \dots a_k \dots$.

For eg, is $S = "414"$, we have that $\sqrt{2} = 1.414\dots$ and fractional part is $0.414\dots$.

Scroll down for a solution.

.

.

.

.

.

Given $S = a_1 \dots ...a_k$, treat it as the number $M = a_1 a_2\dots a_k$.

We can also assume $a_k < 9$ (otherwise, we can just extend $S$ by the digit $0$).

Now consider $X = 10^{2k} + M$.

There are $2X+1$ numbers between $X^2$ and $(X+1)^2$ (not including $(X+1)^2$). Since $X \ge 10^{2k}$, some number among those is divisible by $10^{2k}$. Say it is $P = 10^{2k} Q$.

We have that

$$X^2 \leq 10^{2k}Q < (X+1)^2$$

which implies

$$ X \leq 10^k \sqrt{Q} < (X + 1)$$

i.e

$$ 10^k + \frac{M}{10^k} \leq \sqrt{Q} < 10^{k} + \frac{M + 1}{10^k}$$

And thus $Q$ is the required number.

For eg for $S = 2026$, we get $Q = 100004053$ and $\sqrt{Q} = 10000.2026479\dots$.

Relocating a Hydra

There are infinite rooms, numbered with the integers.

 There is initially a single hydra in room $0$. Each room can hold any number of hydras.

At any time, you can either:

i) Cut off the head of one of the hydras in room $n$, and that results in two hydra spawning, one in room $n-1$ and one in room $n+1$. 

ii) If there are hydras in both room $n-1$ and room $n+1$, you can cut off the heads of one hydra each in both those rooms, and that results in a single hydra spawning in room $n$.

Starting with one hydra in room $0$, with some  sequence of the above head-cuts, can you relocate the hydras to some other room $R$? (i.e. you end up with some number of hydras only in room $R$ and nowhere else). 

What are the possible values of this $R$?

Scroll down for a solution.

.

.

.

.

.

Suppose there are $a_n$ hydra in room $n$.

Consider the function

$$f(z) = \sum a_n z^n $$

Now by chopping off a hydra head in room $n$, the change in the value of $f$ is

$$ z^{n-1} - z^n + z^{n+1} = z^{n-1}(z^2 - z + 1)$$

The other step (which is basically a reverse of the other) results in a change of 

$$-z^{n-1}(z^2 - z + 1)$$

Now if we pick $z = -w$ where $w$ is the cube root of unity, we see that $f(-w)$ is unchanged!

Initially $f(-w) = 1$. If we manage to get exactly r hydras in room $R$ (and no other hydras), then we must have that

$$1 = r (-w)^R$$

This implies $r = 1$ and $R = 6k$.

Thus it is necessary that $R$ must be a multiple of $6$.

It is also sufficient!

All we need to demonstrate is that we can relocated the hydra to room 6.

Now consider the transformation (which shows the state of the rooms -1 to 7)

$$\begin{aligned}& \dots 0 1 0 0 0 0 0 0 \dots \\& \dots 1 0 1 0 0 0 0 0 \dots \\& \dots 1 1 0 1 0 0 0 0 \dots \\& \dots 1 1 1 0 1 0 0 0 \dots \\& \dots 0 2 0 0 1 0 0 0 \dots\end{aligned}$$

Now the steps above are reversible, can be done in any direction starting from anywhere where there is a hydra.

So we apply the above set of steps (call it the 1 to 2-1 step) to the single hydra above to get (note we are no longer showing the room -1 and room 7)

$$ \dots 2 0 0  2 0 0 1\dots $$

Now apply the 1 to 2-1 step in the left direction to the single hydra to get

$$  \dots 2 0 0 3 0 0 2 \dots$$

Now we apply the reverse of the 1 to 2-1 steps (thus effectively changing a 2-1 to 1) to get

$$ \dots 1 0 0 2 0 0 2 \dots $$

And again to get

$$ \dots 0 0 0 1 0 0 2  \dots $$

And again

$$ \dots  0 0 0 0 0 0  1  \dots $$

Which gives us the relocated hydra in room 6, and we are done!

Infinite Version of Fox in a Hole

 The fox-in-a hole is a classic puzzle where there is a fox in one of 5 holes along the x-axis. Every morning you can check a hole for the fox. If you find it, you win. Otherwise that evening the fox moves to an adjacent hole. You can check any hole the next morning and so on. The goal is to catch the fox, irrespective of where it starts from.

An infinite version is as follows.

There are holes along the x-axis on the points $1,2, \dots$ i.e the positive integers. There is a fox in some hole somewhere. Your goal is to catch it. 

Everyday you can check any hole in the morning. If you miss, that evening the fox moves to an adjacent hole (the only hole adjacent to hole 1 is hole 2). You check again the next morning and if you miss the fox moves in the evening and so on.

Can you eventually catch the fox?

Scroll down for a solution.

.

.

.

.

.

Solution:

It is enough if we can solve a finite version of this!

$\textbf{Infinite from finite}$

Suppose you knew the fox was at hole $ \leq N$ and that there was an algorithm to catch it within $f(N)$ days if that were so. If we run the algorithm for $f(N)$ days and don't catch the fox, then we know it started at a hole $> N$. 

We can use this to solve the infinite version as follows:

Consider the sequence $x_n$, defined as $x_1 = 1$ and

$$x_{n+1} = f(x_1) + f(x_2) + \dots + f(x_n) + n$$

Clearly $x_{n+1} - \sum_{i=1}^{n} f(x_i) \to \infty$ and so, given any $M > 0$, eventually $$x_n > M + f(x_1) + f(x_2) + \dots + f(x_{n-1})$$

Our infinite version strategy is now:

Assume the fox is at a hole $\leq x_1$. Run the finite algorithm for $x_1$. If we don't catch it, assume it is at hole $\leq x_2$ and run the finite algorithm for $x_2$ and so on.

If the fox started at hole $M$ initially, then after $n$ steps of the above, the fox will at max be at the hole $M + f(x_1) + \dots + f(x_n)$.

Thus eventually, one of our $x_K$ will be greater than the current hole of the fox, and we will catch it, when we run the finite algorithm for $x_K$.

$\textbf{Finite Algorithm}$

A finite algorithm for $\leq N$ is as follows:

Assume the fox started at an even spot and make a sweep down from $2[(N+1)/2]$. If we don't catch it, we know it started at an odd number and is at a hole $\leq N + 2[(N+1)/2]$. We can now make another sweep down, starting with a high enough hole numbered with the correct parity.

This gives $f(N) = O(N)$, and we eventually catch the fox in $O(M)$ days, where $M$ is the initial hole of the fox.

Oddness of Binomial Coefficients

 There are well known theorems like Lucas' or Kummer's which allow one to figure out exactly which binomial coefficients $\binom{n}{k}$ are odd.

The goal of this (slightly open ended) puzzle is to not use these theorems and still come up with a characterization of the $n,k$ for which $\binom{n}{k}$ is an odd number.

Scroll down for one simple "elementary" way.

.

.

.

.

.

We prove the following:

$\textbf{Claim:}$ Given an $n = \sum 2^{e_i}, e_i \text{ distinct} $ , then we have that $\binom{n}{k}$ is odd iff $k$ is the sum of some subset of the $2^{e_i}$. i.e $k$ is written only using the "set" bits of $n$. The empty set corresponds to $k = 0$.

$\textbf{Proof:}$

Consider polynomials where the coefficients are either $0$ (for even) or $1$ for odd, with the rule that $1 + 1 = 0$.

So we have $1 - 777x$ being equivalent to $1 + x$, because negative of odd is still odd etc.

And $13 + 200x + 999x^2 $ is equivalent to $1 + x^2$ since $200$ becomes $0$ and even times anything is even and so evens act like zero.

[In advanced terms we are working over $GF(2)$]

Now consider $(1 + x)^2 = 1 + 2x + x^2 = 1 + x^2$

Similarly $$(1  + x)^4 = ((1 + x)^2)^2 = (1 + x^2)^2 = 1 + x^4$$

Thus by induction we see that

$$(1 + x)^{2^m} = 1 + x^{2^m}$$

Thus if $n = \sum 2^{e_i}$ (i.e we look at the binary representation of $n$) then

$$(1 + x)^n = \prod (1 + x)^{2^{e_i}} = \prod \left(1 + x^{2^{e_i}}\right)$$

Now

$$\prod \left(1 + x^{2^{e_i}}\right) = \sum x^{m_i}$$

where $m_i$ are exactly the numbers which can be written as the sum of some subset of $2^{e_i}$. Since this gives a binary representation of $m_i$, the representation is unique and the coefficient is $1$.

This proves the above claim.

$\textbf{Additional Remark:}$ This method also works for an arbitrary prime $p$ and we have the following:

$\textbf{Claim:}$ $\binom{n}{k}$ is not divisible by $p$ iff each digit of $k$ in base-$p$ is $\leq$ the corresponding digit in $n$ (in base-$p$).

Note that the characterization we got earlier for $p=2$ is equivalent to this.

Sum of Large and Small divisors of 24n + 1

 Suppose $N = 24n + 1$ is a positive integer, which is not a perfect square. ($n$ is also a positive integer).

A large divisor of $N$ is a divisor of $N$ which is $ > \sqrt{N}$.

A small divisor of $N$ is a divisor of $N$ which is $ < \sqrt{N}$.

Let $L$ be the sum of the large divisors of $N$ and let $S$ be the sum of the small divisors of $N$.

Show that $$ L = S  \mod 24$$ 

For eg, $145 = 29 \times 5$ has the divisors $1, 5, 29, 145$ and $145 + 29 = 6 = 1 + 5 \mod 24$.

Scroll down for a solution.

.

.

.

.

Solution:

Any number $a$ which is relatively prime to $24$ is of the form $a = 6m \pm 1$.

Now $$a^2 - 1 = 36m^2 \pm 12m = 12m (3m \pm 1) = 0 \mod 24$$

This is because $m(3m \pm 1)$ is an even number (either $m$ is even, or $3m \pm 1$ is).

Now since $N$ is not a perfect square, we can pair off the divisors of $N$ as $sl = N$ with $s$ being a small divisor and $l$ being a large divisor.

Note that both $s$ and $l$ are relative prime to $24$, with $sl = 1 \mod 24$.

Now $s^2 - sl =  1 - 1 = 0 \mod 24$, i.e $s(s-l) = 0 \mod 24$. Since $\gcd(s, 24) = 0$, we must have that $s = l \mod 24$.

Thus $\sum s = \sum l \mod 24$.

$\textbf{Additonal Remarks:}$ Similarly we can show that the sum of divisors of a number of the form $24 n - 1$ is divisible by $24$.

An Integral Limit from Berkeley Math Problems Book

The book "Berkeley Problems in Mathematics" contains some hardcore math problems which Berkeley had used for its Phd program clearing requirement in the 70s and 80s.

Here is a nice one from there.

Suppose $f:[0,1] \to \mathbb{R}$ is a continuous function. Find

$$\lim_{n \to \infty} n \int_{0}^{1} x^n f(x) dx$$

Scroll down for a couple of solutions:

.

.

.

.

$\textbf{Solution 1}:$

This is a "heavyweight" and uses the Weierstrass approximation theorem.

The approximation theorem says that any continuous function on a closed interval can be approximated as close as we want, using just polynomials.

We first begin with the observation that for any fixed $M$

$$\lim_{n \to \infty} n \int_{0}^{1} x^n x^M dx = \lim_{n \to \infty} \frac{n}{n + M + 1} = 1$$

This implies that, for any polynomial $P$ we have that

$$\lim_{n \to \infty} n \int_{0}^{1} x^n P(x)dx = P(1)$$

For ease of notation, let $$I(n,g) = n\int_{0}^{1} x^n g(x) dx$$

Now given our $f$ and an $\epsilon > 0 $, there is a polynomial $P_{\epsilon}$ such that $$|f(x) - P_{\epsilon}(x)| < \epsilon \quad \forall x \in [0,1]$$

i,e

$$-\epsilon + P_{\epsilon}(x)  \le f(x) \le \epsilon + P_{\epsilon}(x)$$

And thus we have

$$ I(n, -\epsilon) + I(n, P_{\epsilon}) \leq I(n,f) \leq I(n, \epsilon) + I(n, P_{\epsilon})$$

i.e.

$$ \frac{-n\epsilon}{n+1} + I(n, P_{\epsilon}) \leq I(n,f) \leq \frac{n\epsilon}{n+1} + I(n, P_{\epsilon})$$

Taking $n \to \infty$ we get

$$-\epsilon + P(1) \leq \liminf I(n,f) \leq \limsup I(n,f) \leq \epsilon + P(1)$$

And thus

$$-2\epsilon + f(1) \leq \liminf I(n,f) \leq \limsup I(n,f) \leq 2\epsilon + f(1)$$

SInce $\epsilon > 0$ was arbitrary, it follows that

$$\lim_{n \to \infty} I(n, f) = f(1)$$

$\textbf{Solution2:}$

This is more elementary. 

Let $$c_n = \frac{1}{\sqrt[n]{n}}$$

Note that $c_n < 1$, $\lim c_n = 1$ and $\lim c_n^{n+1} = 0$ 

Now since $f$ is continuous, we can bound $f(x)$ in some interval $[m,M]$ and thus

$$\frac{mn}{n+1} c_n^{n+1} \leq n\int_{0}^{c_n} x^n f(x)dx \leq \frac{Mn}{n+1}c_n^{n+1}$$

Thus $$\lim_{n \to \infty} n \int_{0}^{c_n} x^n f(x)dx = 0$$

Since $c_n \to 1$, given an $\epsilon > 0 $, for sufficiently large $n$, we have that

$$|f(x) - f(1)| < \epsilon \quad \forall x \in [c_n, 1]$$

And we get

$$ \frac{n(f(1) - \epsilon)}{n+1} (1 - c_n^{n+1}) \leq n\int_{c_n}^{1} x^n f(x) dx \leq \frac{n(f(1) + \epsilon)}{n+1}(1 - c_n^{n+1})$$ 

Taking $n \to \infty$ we get

$$f(1) - \epsilon \leq \liminf n \int_{c_n}^{1} x^n f(x)dx \leq \limsup n \int_{c_n}^{1} x^n f(x)dx \leq f(1) + \epsilon$$

Since $\epsilon$ was arbitrary it follows that

$$\lim_{n \to \infty} n \int_{c_n}^{1} x^n f(x) dx = f(1)$$

Thus 

$$\lim_{n \to \infty} n \int_{0}^{1} x^n f(x) dx = $$

$$\lim_{n \to \infty} n\int_{0}^{c_n} x^n f(x) dx + \lim_{n \to \infty} n\int_{c_n}^{1} x^n f(x)$$

$$ = 0 + f(1) = f(1)$$

A nice Indian RMO problem from 2025

The RMO (short for regional maths olympiad) is the test required to be passed, to be eligible for participating in the national level maths olympiad. The top 50 or so from the national olympiad then go through 2-3 months of training and testing and top 6 are then selected to represent India in the international maths olympiad.

The following nice problem appeared in the RMO 2025: 

Show that there are no positive rationals $x,y$ such that

$$ x + y + \frac{1}{x} + \frac{1}{y} = 2025$$

Seems like a difficult one for the levels expected in the RMO. 

Anyway. Scroll down for a solution.

.

.

.

.

Solution:

Let $x = \frac{a}{b}$ and $y = \frac{c}{d}$ where $\gcd(a,b) = \gcd(c,d) = 1$

Rewriting as 

$$ x + \frac{1}{x} + y + \frac{1}{y} = 2025 $$

we get

$$ (a^2 + b^2) cd + (c^2 + d^2) ab = 2025 abcd$$

This implies that $(c^2 + d^2)ab$ is divisible by $cd$.

Now $c(c^2 + d^2) - d (cd) = c^3$ and $d(c^2 + d^2) - c (cd) = d^3$

Thus gcd of $c^2 + d^2$ and $cd$ divides both $c^3$ and $d^3$, and thus must be $1$.

Therefore $cd$ divides $ab$.

In a similar fashion, $ab$ divides $cd$.

Thus we must have that $ab = cd$

So we can now rewrite as

$$a^2 + b^2 + c^2 + d^2 = 2025 ab = 0 \mod 3$$

Now exactly zero or two of $a,b,c,d$ must be divisible by $3$, which gives $$a^2 + b^2 + c^2 + d^2 \neq 0 \mod 3$$

Thus there cannot be such rational $x,y$.

A very nice problem!

$\textbf{Additional Remarks:}$ There actually are integers $N \neq 4$ such that

$$x + y + \frac{1}{x} + \frac{1}{y} = N$$

has solutions in positive rationals.

For eg $x = 10, y = \dfrac{2}{5}$ gives $N = 13$.

The above proof shows that there are no solutions if $N = 0 \mod 3$.

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 (removing 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!