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.

A trigonometric problem from IIT JEE 1995

 The IIT JEE 1995 subjective maths paper had some nice problems. Already posted an integral, previously.

Here is a trigonometric one.

Find the smallest positive $\rho$ such that the equation in $x$ $$\cos (\rho \sin x) = \sin (\rho \cos x)$$ has a solution in $[0, 2\pi]$.

Scroll down for a solution.

.

.

.

.

.

Let's first try to find some $\rho$. Notice that for $x = \frac{\pi}{4}$  to be a solution we need $$\cos \left(\frac{\rho}{\sqrt{2}}\right) = \sin\left(\frac{\rho}{\sqrt{2}}\right)$$

We can try $$\frac{\pi}{2} - \frac{\rho}{\sqrt{2}} =  \frac{\rho}{\sqrt{2}}$$

giving us $$\rho = \frac{\pi}{2\sqrt{2}}$$

 Thus the answer we seek must $ \leq \frac{\pi}{2\sqrt{2}}$.

Now if $\cos x = \cos y $ then we must have that $x = 2n\pi \pm y$ and so $\cos (\rho \sin x) = \sin (\rho \cos x)$ gives us

$$\rho \sin x = 2n\pi \pm \left(\frac{\pi}{2} - \rho \cos x\right)$$

i.e

$$\rho (\sin x \pm \cos x) = 2n \pi \pm \frac{\pi}{2}$$

i.e $$ \sqrt{2} \rho \sin (x \pm \frac{\pi}{4}) = 2n\pi \pm \frac{\pi}{2}$$

Since $0 < \rho \le \frac{\pi}{2\sqrt{2}}$  and $|\sin \theta| \leq 1$, we must have that $n = 0$ and

$$\sqrt{2} \rho |\sin (x \pm \frac{\pi}{4})| = \frac{\pi}{2}$$

This implies that $ \rho \geq \frac{\pi}{2\sqrt{2}}$.

Thus the least possible value is $\rho = \frac{\pi}{2\sqrt{2}}$.

An integral from IIT JEE 1995 entrance exam

 Back in the 20th century, the IIT JEE entrance exam used to have some pretty good subjective questions.

 Unfortunately, the format now is objective questions only, and these days it feels like the students in the coaching classes are taught to game the exams rather than learn the concepts: a regrettable outcome of removing the subjective questions. While one could argue that there are issues with having subjective questions, has it really been worthwhile?

Anyway, this is a cute integral problem from the 1995 JEE maths entrance exam.

Prove, using induction, that

$$\int_{0}^{\pi} \dfrac{1 - \cos mx} {1 - \cos x} \text {  dx} = m \pi$$

Scroll down for solutions.

.

.

.

.

.

1) $\textbf{A fully elementary induction based solution:}$ Everything in this solution falls in the syllabus for IIT JEE and we could expect students to be able to come up with this during the exam.

Let $$I_m = \int_{0}^{\pi} \dfrac{1 - \cos mx} {1 - \cos x} \text {  dx}$$

It is easy to verify that $I_m = m \pi$ for $m = 0, 1$.

Now $$I_{m+1} - I_m = \int_{0}^{\pi} \dfrac{\cos mx - \cos (m+1)x}{1 - \cos x}$$

Now using the formula $\cos 2A - \cos 2B = 2 \sin(A+B)\sin(B-A)$ and $1 - \cos x = 2 \sin^2 \left(\frac{x}{2}\right)$we get

$$I_{m+1} - I_m = \int_{0}^{\pi} \dfrac{2\sin ((m + \frac{1}{2})x) \sin \frac{x}{2}}{2\sin^2 \left(\frac{x}{2}\right)} = \int_{0}^{\pi} \dfrac{\sin ((m + \frac{1}{2})x)}{\sin \frac{x}{2}}$$

[A more knowledgeable reader will recognize the Dirichlet Kernel and cut short the rest of the proof]

Making the substitution $x = 2u$ gives us

$$ I_{m+1} - I_m = 2 \int_{0}^{\frac{\pi}{2}} \dfrac{\sin ((2m+1)u)}{\sin u} \text{ du}$$

Let $$J_m = \int_{0}^{\frac{\pi}{2}} \dfrac{\sin ((2m+1)u)}{\sin u} \text{ du}$$

Note that $2J_0 = \pi$. 

Now we have that

$$J_{m} - J_{m-1}= \int_{0}^{\frac{\pi}{2}} \dfrac{\sin ((2m+1)u) - \sin ((2m-1)u)}{\sin u} \text{ du}$$

Now using $\sin(A+B) - \sin(A-B) = 2 \cos A \sin B$ gives us

$$J_{m} - J_{m-1} = \int_{0}^{\frac{\pi}{2}} \dfrac{2 \cos (2mu) \sin u}{\sin u} = \int_{0}^{\frac{\pi}{2}} 2 \cos (2mu) =   0$$

Thus $J_m = J_0$, and so $I_{m+1} - I_{m} = 2J_m = 2J_0 = \pi$ and so $I_{m} = m \pi$ by induction.

2) $\textbf{Elementary proof 2:}$  Show that $I_{m+1} + I_{m-1} = 2I_m$.

3) $\textbf{Elementary proof 3:}$ Show that:

$$ \frac{1 - \cos mx}{1 - \cos x} =  m + 2 \sum_{k=1}^{m} (m-k) \cos kx$$

This basically comes from the first proof (or even the second), or we can use complex numbers etc.

Note that this formula actually allows you to compute the indefinite integral.

4) $\textbf{Possibly advanced proof:}$ Looks like the function is just the Fejer Kernel (multiplied by $m$) and result is immediate: we are convolving it with $\eta(x) = 1$ and the result is the cesaro summation of $\eta$ evaluated at $0$. Of course, the proofs around the Fejer Kernel etc are taken for granted and this could possibly be a circular argument.

Guessing a rational number

 An algorithm puzzle after a long time.

I am thinking of a rational number $r$: $$\begin{aligned}&r = \frac{p}{q} \\& 0 \leq \frac{p}{q} \leq 1\\& \gcd(p,q) = 1\end{aligned}$$ 

Your goal is to guess $r$. At each step, you guess a rational number $g$ and I tell you whether $r > g, r = g$ or $r < g$. 

Can you guess $r$ in polynomial in $\log q$ guesses?

.

.

.

.

.

This is actually a math problem..

The main idea is to work with the simple canonical continued fraction representations of the rationals. We guess each "digit" of the continued fraction representation: $$r = [a_0; a_1, \dots, a_n] = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\dots}}}$$

It can be shown that the "digits" (i.e the $a_k$) are all $O(q)$ and that the number of digits $n$, is $O(\log q)$, as the representation basically comes out of the extended euclidean algorithm for finding the $\gcd$ of $p$ and $q$. 

The guessing of each digit turns out to be binary search like and so we ultimately get an algorithm that makes $O(\log^2 q)$ guesses.

We are motivated by the following theorem (which we won't prove here):

$\textbf{Theorem:}$ Let $s = [a_0; a_1, \dots, a_n]$ and $t = [b_0; b_1, \dots, b_m]$ be canonical representations (so $a_n \neq 1$ and $b_m \neq 1$). Let $k$ be the first position where $s$ and $t$ differ, i.e $a_k \neq b_k$ and $a_i = b_i \forall i < k$. Then we have the following

$$\text{sign}(s-t) = (-1)^k \text{sign}(a_k - b_k)$$ 

where $$\text{sign}(x) = \begin{cases} 1 & x > 0 \\ 0 & x = 0 \\ -1 & x < 0 \end{cases}$$  

What this means is that to compare two continued fractions, it is enough to compare the digits at the first position they differ.

For eg $\frac{16}{11} = [1; 2,5]$ and $\frac{26}{21} = [1;4,5]$ and we have that $ \frac{16}{11} > \frac{26}{21}$, because they differ at $k=1$, and $2 < 4$ (so we flip the comparison because of the $(-1)^k$ term).

We also have the following (which we will actually use):

$\textbf{Observation:}$ Suppose $s = [a_0; a_1, \dots, a_n]$.  Now for $0 \leq m \leq n$, with a slight abuse of notation, we see that $s = [a_0; a_1, \dots, a_m + \epsilon]$ where $0 \le \epsilon \le 1$ and looking at it as a function of $\epsilon$, 

1) $s$ lies between $[a_0; a_1, \dots, a_m]$ and $[a_0; a_1, \dots, a_m + 1]$ (but could be equal to one of them).

2) if $b \neq a_m$, then $s$ does not lie between $[a_0; a_1, \dots, a_{m-1}, b]$ and $[a_0; a_1, \dots, a_{m-1}, b+1]$ (but could be equal to one of them).

This gives rise to the following algorithm.

$\textbf{Algorithm:}$

To guess $a_0$, do a binary search, comparing $r$ with $[x+1]$ and $[x]$. We vary $x$ in the standard binary search fashion. If $r$ lies in between them, then we have $a_0 = x$. If $r$ is strictly in-between, then $r$ has more digits.

Once we have $a_0$, to guess $a_1$, compare $r$ with $[a_0; x]$ and $[a_0; x+1]$. If $r$ is in-between, then $a_1 = x$, and if $r$ is strictly in-between, then $r$ has more digits. We vary $x$ in a  binary search way, but keeping in the mind increasing $x$ decreases the value of the fraction.

Once we have $a_0, a_1$, we compare with $[a_0; a_1, x]$ and $[a_0; a_1, x+1]$ and so on computing the rest of the $a_k$, keeping in mind the $(-1)^k$ factor in the above theorem.