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 $0$ 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!

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.

Chebyshev plus one

 A puzzle inspired by a recent problem from the JEE 2026 advanced math paper.

Find the value of 

$$ \prod_{k=0}^{4} \left(1 - \sqrt{2} \cos \left(\frac{(2k+1)\pi}{11}\right)\right)^2 $$

Scroll down for a solution.

.

.

.

.

.

The actual value is $$ \frac{(\sqrt{2} - 1)^2}{32}$$

We will prove the following identity:

$\textbf{Proposition:}$

$$1 + \cos ((2n+1) \theta) = 2^{2n} (1 + \cos \theta) \prod_{k=0}^{n-1} \left( \cos \theta - \cos \left(\frac{(2k+1)\pi}{2n+1}\right)\right)^2$$

Setting $\theta = \frac{\pi}{4}$ and $n = 5$ in the above solves the puzzle.

So let's try to prove the above identity.

$\textbf{Proof:}$

We first make the following claim:

$\textbf{Lemma:}$ There is a polynomial $T$ of degree $2n+1$ and leading coefficient $2^{2n}$ such that $T(\cos \theta) = \cos (2n+1)\theta$

$\textbf{Proof of Lemma:}$ This is easily proved using complex numbers and DeMoivre's formula. So we will skip it.

Now $\cos (2n+1)\theta = -1$ for $\theta = \frac{(2k+1)\pi}{2n+1}$, $k = 0 \dots n$

Differentiating $T(\cos \theta) = \cos (2n+1)\theta$ we get

$$T'(\cos \theta) \sin \theta = (2n+1) \sin (2n+1)\theta$$

Thus for $k = 0, \dots n-1$, we have that $T'\left(\cos \frac{(2k+1)\pi}{2n+1}\right) = 0$

Thus the $\cos \frac{(2k+1)\pi}{2n+1}$ are double roots of $T(x) + 1 = 0$, for $k = 0 \dots n-1$. Since the leading coefficient is $2^{2n}$, we have the factorization of $T + 1$

$$T(x) + 1= 2^{2n} (x + 1) \prod_{k=0}^{n-1} \left(x - \cos \left(\frac{(2k+1)\pi}{2n+1}\right) \right)^2$$

The $x+1$ factor corresponds to $k = n$, and the rest correspond to the double roots for $k=0, \dots, n-1$, totaling $2n+1$ in number, which is the degree of $T$.

Setting $x = \cos \theta$ gives us the identity we wanted to prove.

An arithmetic limit that gives the geometric mean

 Let $a_1, a_2, \dots a_k$ be positive reals.

Show that

$$ \lim_{n \to \infty} \left(\dfrac{a_1^{\frac{1}{n}} + \dots + a_k^{\frac{1}{n}}}{k}\right)^n = \sqrt[k]{a_1 a_2 \dots a_k}$$

Scroll down for a solution that does not use "calculus".

.

.

.

.

.

A repeated use of (weighted) AM $\ge$ GM does it. 

Using weighted AM-GM we have that

$$\dfrac{x_1 \times \frac{1}{x_1} + \dots + x_k \times \frac{1}{x_k}}{x_1 + \dots + x_k} \ge \sqrt[x_1 + \dots + x_k] { \frac{1}{x_1^{x_1}} \dots \frac{1}{x_k^{x_k}}}$$

And so

$$ x_1^{\frac{x_1}{S}} \dots x_k^{\frac{x_k}{S}} \ge \dfrac{x_1 + \dots + x_k}{k}$$

Where $S = x_1 + \dots + x_k$.

And so we have the following (by adding the classic AM-GM on the right) and taking the $n^{th}$ powers

$$\left(x_1^{\frac{x_1}{S}} \dots x_k^{\frac{x_k}{S}}\right)^n \ge \left(\dfrac{x_1 + \dots + x_k}{k}\right)^n \ge \left(\sqrt[k]{x_1 \dots x_k}\right)^n$$

Now set $x_j = a_j^{\frac{1}{n}}$ (and so $x_j^n = a_j$)

Now as $n \to \infty, \frac{x_j}{S} \to \frac{1}{k}$.

Therefore 

$$\left(x_1^{\frac{x_1}{S}} \dots x_k^{\frac{x_k}{S}}\right)^n = a_1^{\frac{x_1}{S}} \dots a_k^{\frac{x_k}{S}} \to \sqrt[k]{a_1 \dots a_k}$$

We also have

$$\left(\sqrt[k]{x_1 \dots  x_2}\right)^n =  \sqrt[k]{a_1 \dots a_k}$$

Thus $$ \left(\dfrac{a_1^{\frac{1}{n}} + \dots + a_k^{\frac{1}{n}}}{k}\right)^n = \left(\dfrac{x_1 + \dots + x_k}{k}\right)^n \to \sqrt[k]{a_1 \dots a_k}$$

by the sandwich theorem and we are done.

Maximizing a trigonometric expression (IIT JEE prep question with cute solutions)

Found this cute problem in some IIT JEE prep material. The question as posed there, was a single answer multiple choice question, to find the maximum value. Anyway the puzzle here is:

For what $x \in [0, 2\pi]$ does the expression

$$ \cos x (\sin x + \sqrt{\sin^2 x + 1})$$

take the maximum value? What is the maximum value? No calculus allowed.

Scroll down for solutions.

.

.

.

.

.

$\textbf{Method 1}$: One nice method is to use vector algebra. Consider the formula:

$$ u.v = |u | |v| \cos \theta$$

with $u = (\sin x, \cos x),  v= (\cos x, \sqrt{\sin^2 x + 1})$. 

The expression in question (say $f$) is $f = u.v$ with $|u| = 1$ and $|v| = \sqrt{2}$. Thus  $f \leq \sqrt{2}$. $f$ will be $ = \sqrt{2}$ iff $u$ and $v$ are parallel. And so we are looking for solutions of

$$\sin x \sqrt{\sin^2 x + 1} = \cos^2 x$$

Since $\cos x = 0$ cannot be a solution, we can divide by $\cos^2 x$ and rewrite as

$$\tan x \sqrt{\tan^2 x + \sec^2 x} = 1$$

If $t = \tan x$, then this is 

$$ t \sqrt{2t^2 + 1} = 1$$

Which is a quadractic in $t^2$ with the solution $ t  = \frac{1}{\sqrt{2}}$.

Thus $x$ must satisfy $\tan x = \frac{1}{\sqrt{2}}$. We can verify that it is indeed a solution.

$\textbf{Method 2}:$ This is also a nice solution.

Let $$f = \cos x (\sin x + \sqrt{\sin^2 x + 1})$$

Clearly $\cos x = 0$ cannot be it. So assume $\cos x \neq 0$.

Now this looks quite similar to formula for the root of a quadratic.

$$ f = \frac{ - ( -\sin x) + \sqrt{(-\sin x)^2 - 4 \left(\frac{\sec x}{2}\right) \left(\frac{-\cos x}{2}\right)}}{2 \times\frac{\sec x}{2}}$$

Thus $f$ is the root of $ax^2 + bx + c$ with $a = \frac{\sec x}{2}, b = -\sin x, c = \frac{-\cos x}{2}$.

Thus we have that

$$ \frac{\sec x}{2} f^2 - f \sin x - \frac{\cos x}{2} = 0$$

Multiplying by $2\sec x$ gives us

$$ \sec^2 x f^2 - 2f \tan x - 1 = 0$$

i.e

$$f^2 + \tan^2 x f^2 - 2f \tan x = 1$$

$$ f^2 + (f \tan x - 1)^2 = 2$$

Since $(f\tan x -1)^2 \ge 0$, we must have $f^2 \le 2$. For $f^2 = 2$ (and so $f = \sqrt{2}$) we need $f\tan x = 1$, ie $\tan x = \frac{1}{f} = \frac{1}{\sqrt{2}}$. This is easily verified.

Colouring grid points (problem by Edgar Dijkstra)

 A problem due to Edgar Dijkstra.

You have an $N \times N$ grid of squares  and you have some number of squares on the grid marked as "special" squares. Show that you can colour each of the special squares red or blue, such for any row or column, the number of red squares is within one of the number of blue squares.

Scroll down for a solution.

.

.

.

.

.

This is a graph theory problem. 

You can view the grid as a bipartite graph, with the rows being the left set and the columns being the right set. There will be an edge between row $r$ and column $c$ iff the intersection of those is a special square. Thus it is enough to prove that we can colour the edges of a bipartite graph red or blue so that for each vertex the red degree is within one of the blue degree.

We prove by induction on the number of edges.  

Base cases are easy to verify.

If the graph is a tree (or a forest), pick any leaf node (vertex of degree one) and delete the edge that connects it to its tree. The rest can be coloured by induction. We can now add this edge back and colour it appropriately, without violating the constraint at the vertices where it is connected.

If the graph is not a tree/forest, it has a cycle. Since it is a bipartite graph, this cycle must be of even length. We alternately colour the edges of this cycle red and blue. Now colour the rest of the edges inductively.