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.

Last $m$ digits of $2^n$

 Suppose the last $m$ digits of $2^n$ is the number $d(m,n)$. For eg, the last 4 digits of $2^{24} = 16777216$ are $7216$ and so $d(4,24)$ will be the number $7216$. Another example is $d(3,10) = 24$ (or $024$ if we want to write exactly $3$ digits)

Now given a number $X$ of $m$ digits (we pad with leading zeroes to get exactly $m$ digits if needed, like $024$), for $X$ to be the last $m$ digits of some power of $2$ we must have that, there is some $n$ such that

$$ (2^n - X) = 10^m \times Y$$ 

from this it follows that $X$ must be divisible by $2^m$ and that $X$ must be relatively prime to $5$.

This we can state this as follows:

$\textbf{Necessary Conditions:}$ For a number $X$ of $m$ digits (padded with leading zeroes if needed) to be the last $m$ digits of some power of $2$, we require

$$\begin{aligned}& i) X \text{ must be divisible by } 2^m\\ & ii) \gcd(X,5) = 1\end{aligned}$$

The puzzle is to prove that, the above necessary conditions are also sufficient! i.e 

$\textbf{Prove that:}$

$\textbf{Claim:}$ If $0 < X < 10^m$ is divisible by $2^m$ and $\gcd(X,5) = 1$, then there exists some $n$ such that last $m$ digits of $2^n$ are $X$ (padded with leading zeroes if required). i.e. There is some $n$ such that $d(m,n) = X$.

For eg $X = 24$ is divisible by $8 = 2^3$ and $\gcd(24,5) = 1$. There must be a power of $2$ that ends with $024$ ($2^{10} = 1024$  for eg). Another example, $X = 408$ is divisible by $8$ and $\gcd(408,5) = 1$. The smallest power of $2$ that ends with $408$ is $2^{83}$.

Scroll down for a proof.

.

.

.

.

.

$\textbf{Proof:}$

We need $2^n - X = 10^m Y$ for some $n$. Let $X = 2^m Q$, then we need to have that

$$2^{n-m} = Q \mod 5^m$$

and $\gcd(Q,5) = 1$.

Now $2^{10} = -1 \mod 25$ and the smallest power of $2$ which is $1 \mod 25$ is $2^{20}$. 

Thus $2$ is a primitive root of $25$. Now by a standard theorem of number theory (a primitive root of $p^2$ is also a primitive of $p^t$), this implies that $2$ is a primitive root of $5^t$ for any $t$, and in particular, $t = m$.

Since $\gcd(Q,5) = 1$, there is some $r$ such that $$2^r = Q \mod 5^m$$

And we are done, as we can choose $n = r + m$. 

In fact given $0 < Q < 5^m $ such that $\gcd(Q,5) = 1$, there is a unique $r_Q$ such that $0 \le r_Q < 4 \times5^{m-1}$ and for any $n = r_Q + m \mod (4 \times 5^{m-1})$ we have $d(m,n) = 2^m Q$.

Permutation with distinct prefix sums

For a permutation $x_1, x_2, \dots, x_{100}$ of $0, 1, 2, \dots, 99$ , define 

$$S_n = \left(\sum_{j=1}^{n} x_j\right) \mod 100$$

Is there a permutation such that $S_i \neq S_j $, for all $i \neq j$?

i.e $S_1, S_2, \dots, S_{100} $ is also a permutation of $0, 1, 2, \dots, 99$?

Scroll down for a surprising solution (edit: there is a nice and  much simpler solution in the comments)

.

.

.

.

.

.

We use the fact that $101$ is a prime! 

Since $101$ is a prime, it has a primitive root $g$ and we have that:

Given $ 1 \le m \le 100$, there is a unique $0 \le e_m \le 99$ such that $$g^{e_m} = m \mod 101$$.

Note also, that the $e_i$ are distinct $\mod 100$ because $g$ is a primitive root and $g^{x} = g^{x \mod 100} \mod 101$.

Now we make the following claim:

$\textbf{Claim:}$ The sequence $$\begin{aligned}&x_1 = e_1 = 0\\&x_2 = e_2 - e_1 \mod 100\\&x_n = e_n - e_{n-1} \mod 100\\ &x_{100} = e_{100} - e_{99} \mod 100 \end{aligned} $$ 

is a permutation that satisfies the distinct prefix sum property!

$\textbf{Proof:}$ 

First let's prove that $x_1, x_2, \dots, x_{100}$ is indeed a permutation of $0, 1, 2, \dots 99$.

Suppose it were not, then we must have that $x_i = x_j$ for some $i \neq j$. 

Note $x_1 = 0$ and we have that $e_{n} \neq e_{n-1} \mod 100$ (as the $e_i$ are distinct $\mod 100$). Thus we cannot have that $x_1 = x_i$ for $i \neq 1$. 

Now suppose $e_{i+1} - e_{i} = e_{j+1} - e_{j} \mod 100$ (with $0 < i, j \leq 99$). This implies that

$$g^{e_{i+1} - e_{i}} = g^{e_{j+1} - e_j} \mod 101$$

By definition, $g^{e_n} = n \mod 101$. Thus we must have that

$$ \dfrac{i+1}{i} = \dfrac{j+1}{j} \mod 101 \implies i = j \mod 101$$  

Thus $x_1, x_2, \dots, x_{100}$ is indeed a permutation of $0,1,2, \dots, 99$.

The prefix sums of the $x_i$ are just $S_n = e_1 + (e_2 - e_1) + \dots + (e_n - e_{n-1}) = e_n$.

Thus $$S_1, S_2, \dots, S_{100} = e_1, e_2, \dots, e_{100}$$

Since the $e_i$ are distinct $\mod 100$, the $S_i$ are distinct too, and we are done!

This is an original problem and this solution seems like overkill (but pretty nice if I may say so myself). If you find a simpler solution, please post in the comments.

MoMath Mindbender: 10 points and unit circles

 Another nice puzzle from Peter Winkler on the momath website.

The puzzle: Given $10$ points on the 2D plane, can you cover them all with disjoint unit circles? i.e. Can you find a set of disjoint unit circles such that each of the $10$ points lie inside the circles?

.

.

.

.

Solution:

We give a probabilistic proof!

First consider that if we were asked to use a regular hexagon of side $s$ instead (and allowing them to touch only at the sides instead of full disjointedness), we could do it easily because we can tile the plane with a regular hexagon of any given size. We just tile the plane with regular hexagons of side $s$, translating/rotating etc if points happen to lie on the hexagon sides. 

Now consider a regular hexagon, so that the radius of the inscribed circle inside the hexagon touching all its sides is $1$. The ratio of area of the circle to that of the hexagon comes out to be $\dfrac{\pi}{2\sqrt{3}} \approx 0.906 > 0.9$. 

So basically the hexagon is a "good approximation" for the unit circle and we could try to use hexagons instead, hoping none of the points lie in the areas outside the unit circle. Now could translating etc work if a point happens to lie inside the unwanted area of the hexagon, that is not part of the circle?

This is where we can use the probabilistic method. 

We are given the $10$ points. We now randomly tile the plane with regular hexagons whose inscribed circle is of radius slightly $ > 1$.  We do this so that the unit circles centered at the centers of the hexagons can be disjoint. We can choose the side length so that the probability that any given point strictly lies inside the unit circle is still $\approx 0.906$. 

Note that events are not independent (because the relative locations of the points are fixed), but by linearity of expectation, the expected number of points that lie strictly within the unit circles is $10 \times 0.906 > 9$. Thus there has to be some random arrangement of the hexagons where all the $10$ points lie inside the unit circles!

Primitive Pythagorean triples with the help of trigonometry

 Not a puzzle, just a quick note.

Primitive pythagorean triples are of the form $m^2 - n^2, 2mn, m^2 + n^2$ with $m,n$ relatively prime and of opposite parities.

We will use trigonometry to help derive this.

Let $a,b,c$ with $a^2 + b^2 = c^2$ be a primitive pythagorean triplet. This means $\gcd(a,b,c) = 1$. Note that this also implies that $a,b,c$ are pairwise coprime. Thus exactly one of $a,b,c$ is even. It cannot be $c$ as that would imply $4$ divides $a^2 + b^2$ for $a,b$ odd (which is not possible). 

Thus assume $b$ is even. 

We can now prove that 

$\textbf{Proposition:}$ With $b$ even, the highest power of $2$ that divides $b$ is different from the highest power of $2$ that divides $a+c$. 

$\textbf{Proof:}$ Since $a,c$ are odd and relatively prime, we must have that $\gcd(a+c, c-a) = 2$. Thus $a+c = 2u$ and $c-a = 2v$ for some odd $u,v$. Now if $b = 2w$ for some odd $w$ (if we assume that the highest power of $2$ that divides $b$ is same as $a+c$), then $b^2 = (c+a)(c-a) \implies w^2 = uv$. Since $w^2 = 1 \mod 4$, this implies $u = v$ mod $4$, and thus $a = u - v = 0 \mod 4$, not possible.

Now consider the triangle $$B = (0,0), C = (a, 0), A = (a,b)$$

Draw the anglular bisector $BD$ of angle $B$ such that $D$ lies on $AC$. By the angular bisector theorem, $CD/DA = a/c$ and hence $CD = \frac{ab}{a+c}$. Thus we have that

$$\tan \left(\frac{B}{2}\right) = \frac{CD}{BC} = \frac{b}{a+c} = \frac{n}{m}$$

For some $n, m$ relatively prime.  Since the highest power of $2$ that divides $b$ is different from that of $a+c$, $n,m$ are of opposite parities.

Now using $\tan 2x = \frac{2 \tan x}{1 - \tan^2 x}$ we get

$$\frac{b}{a} = \tan B = \frac{2 n/m}{1 - (n/m)^2} = \frac{2nm}{m^2 - n^2}$$

We can show that $2mn$ and $m^2 -n^2$ are relatively prime if $m,n$ are relatively prime and of opposite parities: if a prime $p > 2$ divides the numerator, it has to divide one of $m,n$ and cannot divide the denominator also. The denominator is also odd, so their $\gcd$ cannot be $2$.

Thus $$b = 2mn, a = m^2 - n^2, c = m^2 + n^2$$

Limit of sum of first $n^{th}$ powers.

 Came across this problem recently, posed as apparently an IIT JEE exam question (though I haven't been able to find the exact year). This is a horrible question for the exam (which is usually multiple choice with negative marking) because it rewards bad students and punishes the good students. And as expected, the IIT JEE coaching class solution I found for this was utterly wrong. A sad state of affairs.

Here is the gist of the question (the actual question was a bit different, but this is the crux of the question).

Find $$\lim_{n \to \infty} \dfrac{1^n + 2^n + \dots + n^n}{n^n}$$

The wrong solution goes as follow

$$\lim \sum_{j=1}^{n} \left(\dfrac{j}{n}\right)^n = \lim \sum_{k=0}^{n-1} \left(\dfrac{n-k}{n}\right)^n$$

$$ = \lim \sum_{k=0}^{n-1} \left(1 - \dfrac{k}{n}\right)^n = \lim \sum_{k=0}^{n-1} e^{-k} = \dfrac{e}{1-e}$$

The step going to $e^{-k}$ is wrong, without some additional justification. In fact, it can be justified using theorems (like monotone/dominated convergence theorems) which is not in the syllabus of IIT JEE. A good student who does not know those theorems will likely be stuck, while a bad student will happily get the right answer by using pretty faulty reasoning.

Below is an attempt to prove that the limit is $\dfrac{e}{e-1}$ using "elementary" means.

The steps are similar till

$$  \dfrac{1^n + 2^n + \dots + n^n}{n^n} = \sum_{k=0}^{n-1} \left(1 - \dfrac{k}{n}\right)^n$$

At this point we try to give upper and lower bounds which ultimately give us the limit we seek,

We use $e^{x} \ge 1 + x$ multiple times. 

Setting $x = \frac{-k}{n}$ gives us $e^{-k/n} \ge (1 - k/n)$ and thus $$ \left(1 - \dfrac{k}{n}\right)^n \le e^{-k}$$

Setting $x = \frac{t}{1-t}$ gives us $e^{t/(1-t)} \ge \frac{1}{1-t}$, and so $e^{t} \ge (1-t)^{t-1}$ and thus $(1-t)^{1-t} \ge e^{-t}$

Setting $t = \frac{k}{n}$ and rearranging gives us

$$\left(1 - \dfrac{k}{n}\right)^n \ge \left(1 - \dfrac{k}{n}\right)^k e^{-k}$$

By Bernouli's inequality $\left(1 - \dfrac{k}{n}\right)^k \ge \left(1 - \dfrac{k^2}{n}\right)$ and so we have the bounds

$$e^{-k} \ge \left(1 - \dfrac{k}{n}\right)^n \ge \left(1 - \dfrac{k^2}{n}\right) e^{-k}$$

Taking the sum from $k = 0$ to $n-1$, and noticing that $\sum k^2 e^{-k}$ is $O(1)$ and hence $\frac{1}{n}\sum k^2e^{-k} \to 0$ as $n \to \infty$ gives us the result.

Powers of 2 as integer parts of irrational multiples

Suppose $\alpha$ is an irrational number in $(0, 2)$.

Prove that there exist infinitely many positive integers $n$ such that the integer part of $n \alpha$  (i,e $[n \alpha]$) is a power of $2$.

Solution.

.

.

.

.

.

Since $\alpha$ is irrational, so is $\beta = \frac{1}{\alpha}$. The binary expansion of $\beta$ contains the binary digit $1$ infinitely often (otherwise it would be rational).

This means, for infinitely many $m$ we have the following

$$2^{m} \beta = N_m + f_m$$

with $N_m$ is the integer part of $2^m\beta$ and $f_m$ is the fractional part, with $\dfrac{1}{2} < f_m < 1$. We choose $m$ so that $2^m \beta$ has $1$ just after the "binary" point.

Now since $\alpha < 2$, $\beta > \frac{1}{2}$ and thus

$$2^{m}\beta + \beta > N_m + f_m + \frac{1}{2} > N_m + 1$$

And thus we have

$$2^{m} \beta < N_m + 1 < 2^m \beta + \beta$$

Dividing by $\beta$ gives

$$2^{m} < (N_m+1) \alpha < 2^m  + 1$$

i.e 

$$ [(N_m+1) \alpha] = 2^m$$

Since we had infintely many choice for $m$, we are done.

Replicating Amoebas

 This is a puzzle from Peter Winkler who himself got it from some field medalist apparently.

You have an amoeba at $(0,0)$. An amoeba can replicate by splitting itself,  and placing them one to the right and one above.

So if an amoeba is at $(x,y)$ after the replication of that, there will be no amoeba at $(x,y)$, one at $(x+1, y)$ and one at $(x, y+1)$.

This replication can only happen if the two target spots are empty. Otherwise the amoeba will not replicate. 

For eg starting with $(0,0)$ consider the following.

A split, now we have $(1,0)$ and $(0,1)$. 

The $(0,1)$ splits, now we have $(1,0), (1,1), (0,2)$.

Now if the $(1,0)$ wants to split, it cannot, because one of the targets $(1,1)$ is occupied.

Ok now for the puzzle.

You start with one amoeba at $(0,0)$. 

How many replications do we need to clear the square (including the inside of it) $(0,0), (2,0), (2,2), (0,2)$ of amoebas?

Solution.

.

.

.

.

.

The answer is, it is impossible to clear that grid!

We come up with an invariant. Give weight $1$ to the initial amoeba. If an amoeba of weight $w$ splits, give weights $\frac{w}{2}$ to each of its clones. Thus the total weight of amoebas is preserved.

Now the weights are non-positive powers of $2$ and given the location of the amoeba, you can actually determine its weight.

The weights look something like this ($(0,0)$ is bottom left of matrix)

$$\begin{matrix} \vdots & \vdots & \vdots & \vdots \\ \frac{1}{8} & \frac{1}{16} & \frac{1}{32} & \frac{1}{64} &\dots \\ \frac{1}{4} & \frac{1}{8} & \frac{1}{16} & \frac{1}{32}  & \dots \\ \frac{1}{2} & \frac{1}{4} & \frac{1}{8} & \frac{1}{16} & \dots \\ 1 & \frac{1}{2} & \frac{1}{4} & \frac{1}{8} & \dots \end{matrix}$$

Now the sum of all the weights in the square of our interest  is $$ 1 + 2 \times \frac{1}{2} + 3 \times \frac{1}{4} + 2 \times \frac{1}{8}  + \frac{1}{16} = 3 \frac{1}{16}$$

The sum of weights of all the possible spaces is $S + \frac{S}{2} + \frac{S}{4} + \dots = 2S $ where $S$ is the sum of the weights of the bottom row. 

It is easily seen that $S=2$, so the whole infinite grid sum is $4$.

Thus the sum of weights outside our grid of interest is no more than $4 - 3\frac{1}{16} < 1$.

Thus it is impossible to clear that grid, starting with a single amoeba at $(0,0)$, of initial weight $1$: there has to be some amoeba inside the grid to preserve the total weight of $1$.

A generalization of sum of squares

 Let $A_1, A_2 \dots A_n$ be $n$ points in the 2D plane, with centroid $M$.

Show that for any point $P$ in the plane

$$ \sum_{i = 1}^{n} PA_{i}^2 = n PM^2  + \sum_{i=1}^{n} MA_{i}^2$$

Bonus: Given a magic fairy that tells you the sum of squares of distances of any point $P$ to $A_1, A_2, \dots, A_m$ where you don't know $m$ or the $A_i$, show that you can find $m$ in a finite number of queries to the magic fairy.

Solution

.

.

.

.

.

Surprisingly this has an easy proof using complex numbers!

Let $a_1, a_2, \dots, a_n$ be complex numbers that sum to $0$,

Then we have that for any complex number $z$,

$$\sum_{i=1}^{n} |z-a_i|^2 = \sum_{i=1}^{n} (z-a)\overline{(z-a)} = $$

$$ \sum_{i=1}^{n} (z\overline{z} - z\overline{a_i} -\overline{z}a_i + a_i\overline{a_i}) = $$

$$ n z \overline{z} + \sum_{i=1}^{n} a_i\overline{a_i}  = n |z|^2 + \sum_{i=1}^{n} |a_i|^2$$

This gives us the identity we seek. The centroid $M$ corresponds to $0$, the sum of $a_i$.

The bonus puzzle solution follows along the lines of the previous guessing puzzle, and I will leave it to you.

Guessing the area from sum of squares of distances

 There is an equilateral triangle $ABC$ in the 2D plane. You don't know where it is, but have access to a magical fairy that, given a point $P$ in the same plane, will give you the value of $$f(P) = |PA|^2 + |PB|^2 + |PC|^2$$ i.e. the sum of squares of distances from $P$ to $A,B,C$ (henceforth we will drop the absolute sign)

i) Can you find out the area of triangle $ABC$ using only a finite number of queries to the fairy?

ii) Can you find the minimum number of queries you need to (and are sufficient) to guess the area?

iii) Can you find the locations of the three vertices?

Solution

.

.

.

.

.

Part i)

In a previous post we showed the following:

For any triangle $ABC$ with centroid $M$ and any point $P$ in the same plane

$$ PA^2 + PB^2 + PC^2 = 3 PM^2 + AM^2 + BM^2 + CM^2$$

(Can easily be proven using complex numbers too, if required).

i.e we have $$f(P) = 3 PM^2 + S$$

where $S$ is a constant, independent of $P$ (and is actually a constant times the area of $ABC$, for equilateral $ABC$).

Now pick points $X, Y$ (say $(0,0), (1,0)$) and query the fairy for $X$ and $Y$.

We have that $$f(X) - f(Y) = 3(XM^2 - YM^2)$$

i.e $M$ lies on the locus of points $Q$ such that $$QX^2 - QY^2 = k$$

$k$ is a constant.

By simple co-ordinate geometry, this actually can easily be seen to be a line perpendicular to $XY$ (extended, if needed).

Thus using two points, we narrow down $M$, the centroid of $ABC$ to a straight line. With another point $Z$ (say $(0, 1)$), we get another line, and take the intersection of the two lines.

Once we have the location of $M$, we can compute $XM^2$ directly, and then use the already obtained $f(X)$ to compute the area of the equilateral triangle $ABC$, using

$$ AM^2 + BM^2 + CM^2 = f(X) - 3 XM^2$$

Thus three queries are sufficient. 

Part ii)

Three queries are also necessary.

Suppose two were enough, (say X and Y), then as before $M$ lies on a line perpendicular to $XY$. Now if $M$ were the actual point, then the reflection $M'$ of $M$ on $XY$ gives the same $f(X)$ and $f(Y)$. Thus two queries are not enough.

Part iii)

Pinpointing the vertices is impossible! Any rotation of the $ABC$ around the centroid gives the same $f(P)$ values.