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 + 2^n + \dots + n^n}{n^n}$$

The wrong solution goes as follow

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

$$ = \sum_{k=0}^{n-1} \left(1 - \dfrac{k}{n}\right)^n = \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 + 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 grid 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 = S^2 $ 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.

 

An unexpected approach to a quadratic system of equations

Positive reals $a,b,c$ satisfy

$$ a^2 + b^2  + ab = 121$$

$$b^2 + c^2 + bc = 169$$

$$ c^2 + a^2 + ca = 400$$

What is the value of $ab + bc + ca$?

.

.

.

.

.

.

This can be solved using geometry!

Consider triangle $OAB$ with $OA = a$ and $OB = b$ and $\angle{AOB} = 120^{\circ}$.

Using cosine rule, $AB^2 = a^2 + b^2 - 2ab \cos(120^{\circ}) = a^2 + b^2 + ab$. Thus $AB = 11$.

Area of triangle $AOB$ = $\frac{1}{2} ab \sin(120^{\circ}) = \frac{\sqrt{3}}{4} ab$

Now add point $C$ such that $OC = c$ and $\angle{AOC} = \angle{COB} = 120^{\circ}$.

We thus have a triangle $ABC$ with sides $AB = 11, BC = 13, AC = 20$ and area  (by adding up areas of $AOB, AOC, BOC$

 $$\frac{\sqrt{3}}{4} (ab + bc + ca)$$

By Heron's formula, since the sides are known, we get area $=66$.

This gives $$ab + bc + ca = 88 \sqrt{3}$$