Cute problem from IIT JEE

If $r,s,t$ are roots (you can assume they are all real) of $$x^3 + 3x^2 - 24x + 1 = 0$$ Find $$ \sqrt[3]{r} + \sqrt[3]{s} + \sqrt[3]{t}$$ If you know which year this is from, please let me know.

Scroll down for solution (and something extra).

Let $P(x) = x^3 + 3x^2 - 24x + 1$.

Note that $P(0) > 0, P(1) < 0$ and $P(24) > 0$ and so has at least two real roots. Which implies all roots are real, so we can freely take cube roots.

Now 

$$x^3 +3x^2 - 24x + 1 = x^3 + 3x^2 + 3x + 1 - 27x = (x+1)^3 - 27x$$.

Thus if $a$ is a root of $P$, then

$$ (a+1)^3 = 27a \implies 3a^{1/3} = (a + 1)$$

Thus the sum of cuberoots of P is $(r+s+t + 3)/3 = 0$.

For the extra:

We will in fact show that $\sqrt[3]{r},\sqrt[3]{s},\sqrt[3]{t}$ are roots of $x^3 - 3x + 1 = 0$.

Let $d=\sqrt[3]{r},e=\sqrt[3]{s},f=\sqrt[3]{t}$ be roots of $Q(x) = x^3 + ax^2 + bx + 1$

Thus $Q(x) = (x-d)(x-e)(x-f)$

Now if $w$ is a cuberoot of unity, then

$$Q(x)Q(wx)Q(w^2x) = (x^3 - d^3)(x^3-e^3)(x^3 - f^3) = P(x^3) = x^9 + 3x^6 -24x^3 + 1$$

With slightly tedious algebra, we see that

$$Q(x)Q(wx)Q(w^2x) = x^9 + (a^3 - 3ab + 3)x^6 + (b^3 - 3ab + 3)x^3 + 1$$

Thus we get

$$a^3 - 3ab = 0$$

$$b^3 - 3ab = -27$$ 

From the first equation either $a=0$ (in which case $b = -3$) or $a^2 = 3b$.

If $a \neq 0$, putting $b = a^2/3$ in the second results in a quadratic (in $a^3$) with complex roots. Since $a$ needs to be real (sum of real numbers) we see that $a = 0, b = -3$ and hence the cuberoots are roots of 

$$x^3 - 3x + 1 = 0$$

2 equations 3 variables

Given that $x, y, z$ are real, solve (with proof) the system of equations: $$ (x-1)(y-1)(z-1) = xyz - 1$$ $$ (x-2)(y-2)(z-2) = xyz - 2$$ part b) $x,y,z$ are allowed to be complex.

Scroll down for solution.

Let $$P(t) = (x-t)(y-t)(z-t)$$. $x,y,z$ are roots of $P(t) = 0$.

Expand and assume

$$P(t) = c - bt + at^2 - t^3$$

The two equations basically say

$$P(1) = c -1$$

and

$$P(2) = c -2$$

The first gives $a = b$

and second gives $2a - b = 3$ and thus $a=b = 3$

Thus $$P(t) = c - 3t + 3t^2 - t^3 = c -1 - (t^3 -3t^2 + 3t - 1) = (c-1) - (t-1)^3 $$

Thus $x,y,z$ are roots of 

$$(t-1)^3 = c-1$$

For $x,y,z$ to be real, we need $c=1$ and $x=y=z=1$.

If $x,y,z$ are allowed to be complex, pick a random $c$ and $x,y,z$ are $(c-1) w + 1$ where $w$ are the three cuberoots of unity.

Limit of average of $n^{1/k}$

Define $S_n$ as follows

$$ S_n =   \sum_{k=1}^{n} n^{\frac{1}{k}}$$

For eg 

$$S_{10} = 10 + 10^{1/2} + 10^{1/3} + \dots + 10^{1/10} \approx 25.4211$$

Find

$$ \displaystyle \lim_{n \to \infty} \dfrac{S_n}{n} $$ 

Scroll down for a solution.

We will solve this using the arithmetic mean geometric mean inequality!

For $k \ge 2$ let $$x_1 = x_2 = \dots = x_{k-2} = 1, x_{k-1} = x_k = \sqrt{n}$$

Applying AM GM to these we get 

$$\frac{k-2 + 2\sqrt{n}}{k} \ge n^{1/k} \ge 1$$

Thus 

$$1 - \frac{2}{k} + 2 \frac{\sqrt{n}}{k} \ge n^{1/k} \ge 1$$

Now $\sum_{k=2}^{n} \frac{1}{k} = \log n + O(1)$

Thus

$$ n-1 - 2(\log n + O(1)) + 2\sqrt{n}(\log n + O(1)) \ge \sum_{k=2}^n n^{1/k} \ge n-1$$ 

And so 

$$ 2n-1 - 2(\log n + O(1)) + 2\sqrt{n}(\log n + O(1)) \ge \sum_{k=1}^n n^{1/k} \ge 2n-1$$  

Thus 

$$ 2 + O\left(\frac{\log n}{\sqrt{n}}\right) \ge \frac{S_n}{n} \ge 2 + O\left(\frac{1}{n}\right)$$

Thus $$ \frac{S_n}{n} \to 2$$

A cute problem from Turkish AYT exam

 $P(x)$ is a $4^{th}$ degree polynomial with real coefficients that satisfies

$$P(x) \ge x \quad \forall x \in R$$

$$P(1) = 1, P(2) = 4, P(3) = 3$$

Find the value of $P(4)$.

Scroll down for a solution.

Let $H(x) = P(x) - x$ and so $H(x) \ge 0 \forall x \in R$. Since $H(1) = H(3) = 0$, $H(x)$ has at least two distinct roots.

Now if there was a root of $H$ different from $1$ or $3$, then we can show that $H(c) < 0 $ for some $c \in R$. If the multiplicity of $1$ of $3$ was odd, then we can again show that $H(c) < 0$ for some $c$.

Thus we must have that

$$H(x) = A(x-1)^2(x-3)^2, A > 0$$

Since $H(2) = P(2) - 2 = 2$, we get  $A = 2$.

This gives $P(4) = H(4) + 4 = 2.3^2.1^2 + 4 = 22$. 

Sum of reciprocals of lcm

 Let $d_n$ be the least common multiple of $1,2, \dots, n$.

Show that

$$\sum_{n=1}^{\infty} \frac{1}{d_n}$$

is an irrational number.

Scroll down for a solution.

Observation 1: If $n+1$ is a power of a prime $q$, then $d_{n+1} = q d_n$, otherwise $d_{n+1} = d_n$.

Observation 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}$$

(Proof left to reader).

Let the primes in order be $p_1, p_2, \dots$.

Pick an arbitrary prime $p = p_m$ and consider for $n \ge p$

$$f_n = \frac{d_{n}}{d_{p-1}}$$

The observation 1 above also holds for $f_n$.

Note that $f_{p_j} \ge p_m p_{m+1} \dots p_{j}$ and that the inequality is strict for infinitely many $p_j$.

Now consider $$ \sum_{p_i \le k < p_{i+1}} \frac{1}{f_k}$$

By Bertrands' theorem of a prime between $n$ and $2n$ we have that $p_{i+1} < 2p_i$

and thus

$$ \sum_{p_i \le k < p_{i+1}} \frac{1}{f_k} \le \frac{p_{i+1} - p_i}{f_{p_{i}}} \le \frac{p_i - 1}{f_{p_{i}}}$$

Since $f_{p_j} \ge p_m p_{m+1} \dots p_{j}$ we get

$$ \sum_{p_i \le k < p_{i+1}} \frac{1}{f_k} \le \frac{p_i - 1}{p_m p_{m+1} \dots p_i}$$

And so (note inequality is strict, because $f_{p_j} \gt p_m p_{m+1} \dots p_{j}$ infinitely often.)

$$\sum_{n \ge p} \frac{1}{f_n} < \sum_{j \ge m} \frac{p_j - 1}{p_m \dots p_j}$$

By Observation 2 above we get

$$\sum_{n \ge p} \frac{1}{f_n} < 1$$

Now if $$\frac{a}{b} = \sum_{n=1}^{\infty} \frac{1}{d_n}$$

Pick a prime $p > b$ and consider $\frac{a d_{p-1}}{b}$ and use the above result about $f$.

Cute problem with a+b+c = 2022

 $a,b,c$ are real numbers such that

$$a + b + c = 2022$$

and

$$\frac{1}{a} + \frac{1}{b} + \frac{1}{c} = \frac{1}{2022}$$

What are the possible values of 

$$\frac{1}{a^{2023}} + \frac{1}{b^{2023}} + \frac{1}{c^{2023}} $$

Try to keep the algebraic manipulations to a minimum.

[Solution]

4 people in a square with hats

I was given this puzzle by Arvind Hariharan and he has a write up with a different solution approach here: https://www.starvind.com/math/hats-to-leave-you-scratching-your-head/.

The puzzle (apparently from Riddler) is as follows:

Four people are trying to escape from a room. Guards have placed a hat on each person’s head, and each hat is one of three colors: red, yellow or blue. The four people are arranged at the vertices of a square, with an obstacle in the middle. Each person can see the hats on the heads of those on adjacent vertices of the square, but they cannot see the hat of the person diagonally across from them. They also do not know the color of the hat on their own head.

Each person must guess the color of the hat on their own head. If at least one person guesses correctly, they can all escape the room together. No communication is allowed once the hats are placed on their heads, but they can coordinate on a strategy beforehand. They also know how they will be arranged in the square.

How can they be guaranteed to escape the room?

Please stop reading if you wish to solve the puzzle by yourself.

The reason for writing this article is to discuss a strange approach to solving this problem: Giving a proof of existence of a strategy using Linear Algebra!

Since there are $3$ colours, we can work mod $3$, with $0, 1, 2$ being the colours and $x + y = x + y \mod 3$ (This is the field $\mathbb{F}_3$). Note that $2x = -x$ etc.

Let us assume the four people are $A,B,C,D$ and they are given the hat colours $a, b, c, d$, with $A,C$ and $B,D$ being diagonally opposite. Thus $A$ and $C$ only have access to $b,d$ and $B, D$ only have access to $a, c$.

Let us further assume that there is strategy where each person computes some linear combination of the colours they can see and uses it as their guess. 

For eg: $A$ guesses $x_a b + y_a d$ for some $x_a, y_b$ specific to $A$.

Now introduce the offset variable $\delta_a$ which is the amount $A$'s guess is off from their actual value. i.e.

$$ \delta_a = x_a b+ y_a d - a = x_a b + y_a d + 2a$$

Writing this equation for each of $A,B,C,D$ we see that the $\delta$'s can be captured as a matrix equation as follows

$$S \begin{bmatrix}a\\ b \\ c \\ d\end{bmatrix} =  \begin{bmatrix}\delta_a \\ \delta_b \\ \delta_c \\ \delta_d \end{bmatrix} $$

where $S$ (short for strategy) is the 4x4 matrix 

$$   \begin{bmatrix} 2 & x_a & 0 & y_a\\ x_b & 2 & y_b & 0\\ 0 & x_c & 2 & y_c\\x_d & 0 & y_d & 2 \end{bmatrix}$$

$S$ is a viable strategy if for every possible $a,b, c, d$, the atleast one of the $\delta$'s is $0$.

Now comes the key observation:

Lemma 1: For any $x, y$ at least one of $x, y, x + y, x+2y$ is $0$ (note $\mathbb{F}_3$ working mod 3). This is easily proved.

This fact can be stated in linear algebra terms

Lemma 2: Each vector in the space spanned by $u = \begin{bmatrix} 1 & 0 & 1 & 1 \end{bmatrix}$ and $v = \begin{bmatrix}0 & 1 & 1 & 2 \end{bmatrix}$ has at least one co-ordinate which is $0$, i.e. for any $x, y$, the vector $xu + yv$ has at least one co-ordinate which is $0$.

Lemma 3: Now notice that if you now have two arbitrary values $p$ and $q$ and you wanted a 1x4 vector with one of the coordinates as $p$ and other as $q$ (in some given positions), you can find (a unique) vector of the form $w = x u + y v$ which has co-ordinates $p$ and $q$ in the given positions (the other two coordinates are not "free"), as you are essentially solving $x + y = p, x + 2y = q$ or some such pair of equations from Lemma 1.

Now look at the columns of $S$

$$   \begin{bmatrix} 2 & x_a & 0 & y_a\\ x_b & 2 & y_b & 0\\ 0 & x_c & 2 & y_c\\x_d & 0 & y_d & 2 \end{bmatrix}$$

Each column has $0$ and $2$ in some positions, thus by Lemma 3, there is an $S$ where each column of $S$ can be written as a vector of the form $x u + y v$.

Thus we see that for such an $S$, the offset vector $\begin{bmatrix}\delta_a \\ \delta_b \\ \delta_c \\ \delta_d \end{bmatrix}$, which is essentially a linear combination of the columns of $S$ is thus also a linear combination of $u$ and $v$ and by Lemma 2, has to have at least one co-ordinate which is $0$. 

Hence such an $S$ is a strategy which solves the puzzle. This $S$ can actually be computed easily, which we will leave to the reader.

Note that this generalizes, for example you could have a strategy for 6 people with 5 colours where each person could see all but one.

Sum of reciprocals of smooth numbers

 Let $a_1, a_2, \dots, a_n$ be $n \ge 1$ distinct odd integers with no prime factors $\gt 5$.

Show that

$$ \sum_{i=1}^{n} \dfrac{1}{a_n} \lt \frac{15}{8}$$

[Solution]

A point and a parallelogram

 Suppose $ABCD$ is a parallelogram and $P$ is a point on the same plane as $ABCD$.

Show that the locus of points $P$ such that

$$|PA|^2 + |PB|^2 + |PC|^2 + |PD|^2 = \text{constant}$$

is either a circle or nothing, depending on the constant.

What is the radius of the circle, if the parallelogram side lengths are $L$ and $W$ and the constant is $K$?

[Solution]

Lead against a confident slam

This is a hand from the PanIIT inter IIT bridge tournament conducted online in 2020/2021. 

Both vul, IMPS. You hold 8x, A9x, Q7xxxx, K9.

Partner passes, RHO opens 1S, you pass. LHO bids 4NT, RHO shows two keycards without Q and LHO bids 6S.

What would you lead?

Given that you hold HA, DQ and CK and LHO jumped directly to 4NT, it is very likely they have a distributional hand with a long and good club suit. The club finesse declarer needs is working, even if they can only take it once.

At the table I tried the lead of C9 from K9. This turned out to be a lucky lead as you can see from the four hands below.

IMPS  Both	North ♠ AQ7 ♥ J ♦ K ♣ AQJ76532
West ♠ 84 ♥ A92 ♦ Q76532 ♣ K9		East ♠ T62 ♥ K87643 ♦ T98 ♣ 4
	South ♠ KJ953 ♥ QT5 ♦ AJ4 ♣ T8

W	N	E	S
		P	1S
P	4NT	P	5H
P	6S	P	P
P

Declarer decide to spurn the club finesse and went up with the CA and could no longer make the contract!

Cover the plane with strips

 In the 2D plane, a strip is the space between (and including) two parallel lines (which extend to infinity in both directions). The width of a strip is the distance between the two parallel lines that make up a strip. The width of a strip is non-zero (otherwise we just call it a line).

Can you fully cover the 2D plane with strips the sums of whose widths is finite? (Proof required of course).

Scroll down for a solution.

Consider a circle of radius $R$. A strip of width $w_i$ can cover an area at most $2w_iR$.

So strips of total width $w$ (infinite number of strips or not), can cover at most an area of $2wR$.

For sufficiently large $R$, $\pi R^2 \gt 2wR$. So we cannot cover the plane with strips the sum of widths of which is finite.

IMO 2019 Q1

 This problem from IMO 2019 (international maths olympiad) was surprisingly easier than expected.

Find all functions $f: Z \to Z$ such that

$$ f(2a) + 2f(b) = f(f(a+b)) \quad \quad \forall a,b \in Z$$

$Z$ is the set of integers.

A British Math Olympiad problem

 Find all non-negative integers $a, b$ such that

$$ \sqrt{a} + \sqrt{b} = \sqrt{2019}$$

Cute INMO problem (2011)

 A cute problem from the Indian national Math Olympiad (of 2011 I believe).

Find all real $(x,y)$ such that

$$16^{x^2 + y} + 16^{y^2 + x} = 1 $$