A surprising expression with nested square roots

 Simplify 

$$ \frac{\sqrt{10 + \sqrt{1}} + \sqrt{10 + \sqrt{2}} + \dots + \sqrt{10 + \sqrt{99}}}{\sqrt{10 - \sqrt{1}} + \sqrt{10 - \sqrt{2}} + \dots + \sqrt{10 - \sqrt{99}}}$$

Scroll down for simplified form and solution.

The expression is equal to $\sqrt{2} + 1$.  Surprising!

Scroll down for solution.

Let $a + b $ = 100. 

Now

$$\sqrt{10 - \sqrt{a}} \sqrt{10 + \sqrt{a}} = \sqrt{100 - a}  = \sqrt{b}$$

Let $u = \sqrt{10 + \sqrt{a}}$ and $v = \sqrt{10 - \sqrt{a}}$

So $20 = u^2 + v^2$

and $\sqrt{b} = uv$

Thus

$$\sqrt{20 + 2\sqrt{b}} = \sqrt{u^2 + v^2 + 2uv} = u+v$$

Similarly

$$\sqrt{20 - 2\sqrt{b}} = \sqrt{u^2 + v^2 - 2uv} = u-v$$

Thus if 

$$P = \sum_{a=1}^{99} \sqrt{10 + \sqrt{a}}$$

and

$$Q = \sum_{a=1}^{99} \sqrt{10 - \sqrt{a}}$$

We get 

$$ \sqrt{2} P = P + Q$$ and

$$\sqrt{2} Q = P - Q$$

This gives us $$\frac{P}{Q} = \sqrt{2} + 1$$

Putnam 2012 B4 generalization

 Let $c \gt 0$ be a real number and $a_n$ be a sequence such that $a_0 = 1$ and $$a_{n+1} = a_n  + e^{-c a_n}$$

Show that

$$\lim_{n \to \infty} (ca_n - \log n) = \log c$$

($\log$ is $\log$ to base $e$)

The Putnam problem was with $c = 1$ and only asked for proof of existence of the limit.

Scroll down for a solution.

Consider $b_n = e^{a_n}$ then we get that $b_{0} = e$ and

$$ b_{n+1} = b_n e^{1/(b_n)^c}$$

We can easily show that $a_n$ is unbounded (proof by contradiction) and so is $b_n$ and thus $\frac{1}{b_{n}^c} \to 0$.

The recurrence for $a_n$ gives us

$$b_{n+1}^c = b_{n}^c e^{c/(b_n)^c}$$

Expanding the $e^{\dots}$ part we get

$$b_{n+1}^c = b_{n}^c ( 1 + \frac{c}{b_{n}^c} + O\left(\frac{1}{b_{n}^{2c}}\right)) = b_{n}^c + c + O\left(\frac{1}{b_{n}^c}\right)$$

This telescopes to give us

$$b_{n}^c - b_{0}^c = nc + \sum_{k=0}^{n} O\left(\frac{1}{b_{k}^c}\right)$$

And so

$$\frac{b_{n}^c - b_{0}^c}{n} = c + \frac{\sum_{k=0}^{n} O\left(\frac{1}{b_{k}^c}\right)}{n}$$

Thus

$$ \frac{b_{n}^c}{n} \to c$$

Taking logarithms gives the result.

A cute problem from New Zealand Maths Olympiad

 

In the image above, ABCD is a square, and BX = DY, X lying on BC, and Y on CD extended.

P is the intersection point of the diagonal BD and XY. 

Show that PY = PX. 

(Diagram not to scale!)

Try using pure geometric methods only.

Solution diagram below:

Nested square roots

Let $f(a)$ be the number of positive integers $x$ such that $$ \sqrt{x + \sqrt{x + a}}$$ is a positive integer. 

 Show that there are infinitely many positive integers $a$ such that $f(a) = 1$

Scroll down for a solution.

Note that for $x = a^2 - a$, $\sqrt{x + \sqrt{x+a}} = a$ is an integer for positive integer $a$ and thus $f(a) \ge 1$ for positive integer $a$.

Now suppose $$\sqrt{x + \sqrt{x+a}} = p$$

Some algebra gives us that 

$$x^2 - (2p^2+1)x + (p^4 - a) = 0$$

For this to have an integer solution we need the discriminant to be a perfect square. 

And so

$$(2p^2 + 1)^2 - 4(p^4 - a) = q^2$$

Which leads to

$$4a +1 = (q-2p)(q+2p)$$

Thus if $4a+1$ is prime, there is a unique solution.

Since there are infinitely many primes of the form $4a+1$, we are done.

An integral with a parameter.

The problem is to evaluate (with proof) $$f(a) = \int_{0}^{\infty} \frac{x^2}{(x^2 - a^2)^2 + x^2} \text{ d}x$$ where $a$ is a real number.


Scroll down for a solution.






Surprisingly, the answer is independent of $a$!.

For $a=0$, the integral is the standard $\int_{0}^{\infty} \frac{dx}{1+x^2} = \frac{\pi}{2}$. A valuable tool when evaluating integrals is substitution and it really helps here. First, assume $a \neq 0$, and make the substitution $u = \frac{a^2}{x}$ This gives us that $$f(a) = \int_{0}^{\infty} \frac{\frac{a^4}{u^2}}{((\frac{a^4}{u^2} - a^2)^2 + \frac{a^4}{u^2})} \frac{a^2\text{d}u}{u^2}$$ $$ = \int_{0}^{\infty} \frac{a^2}{(u^2 - a^2)^2 + u^2} \text{ d}u$$ $$ = \int_{0}^{\infty} \frac{a^2}{(x^2 - a^2)^2 + x^2} \text{ d}x$$ Thus by adding the original, we get that $$2f(a) = \int_{0}^{\infty} \frac{x^2 + a^2}{(x^2 - a^2)^2 + x^2} \text{ d}x$$ $$ = \int_{0}^{\infty} \frac{1 + \frac{a^2}{x^2}}{(x - \frac{a^2}{x})^2 + 1} \text{ d}x$$ Now make the substitution $u = x - \frac{a^2}{x}$ to get $$2f(a) = \int_{-\infty}^{\infty} \frac{1}{u^2 +1} \text{ d}u = \pi$$ And so $$\int_{0}^{\infty} \frac{x^2}{(x^2 - a^2)^2 + x^2} \text{ d}x = \frac{\pi}{2}$$ Note: The substitutions need to be justified because technically, the integral is an improper integral, but we leave that to the reader :)

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 $w\sqrt[3]{c-1}  + 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]